KR20010052246A - Optimized rate-compatible turbo encoding - Google Patents

Abstract

Turbo encoding methods and apparatus utilize a set of rate-compatible turbo codes that are optimized at high code rates and derived from universal construction codes. The turbo code has a rate-compatible puncturing pattern. The method encodes a signal at a first and a second encoder using a higher code rate and a universal best rate 1/2 configuration code, wherein the first encoder and the second encoder each for each information bit. Generate a plurality of parity bits of; Puncturing each of the plurality of parity bits at each encoder with a highest puncturing pattern at a higher rate; And puncturing each of the plurality of parity bits at each encoder with the lowest puncturing pattern at a lower rate. In a variant, the best rate 1/2 configuration code represents the combination of polynomial 1 + D ² + D ³ (octal 13), and 1 + D + D ³ (octal 15), where D is the data bit. The turbo encoder is provided with hardware implementing the present invention.

Description

OPTIMIZED RATE-COMPATIBLE TURBO ENCODING}

Forward error correction (FEC) is required for terrestrial and satellite radio systems to provide high-quality communications over RF propagation channels resulting in signal waveforms and spectral distortion, including signal attenuation (free-space propagation loss) and multipath inflow fading. do. With these drawbacks, one must consider the design of wireless transmission and receiver equipment, the design of modulation formats, error control schemes, design objectives to choose demodulation and decoding techniques, and hardware components that together provide an efficient balance between system performance and implementation complexity. . Due to differences in propagation channel characteristics, such as between terrestrial and satellite communication channels, the design of the system will naturally vary significantly. Similarly, existing communication systems continue to evolve to meet the increased system requirements for new higher rates or more robust communication services.

In the case of terrestrial cellular mobile radio telephones, the analog mobile telephone system (AMPS) is an exemplary first generation system: U.S. IS-136 and European GSM Time Division Multiple Access (TDMA) standards and U.S. The IS-95 Code Division Multiple Access (CDMA) standard is a second generation system; The broadband CDMA standard currently under development (ie, CDMA 2000 in the US and UTRA in Europe) is a third generation system.

In third generation systems, the development of flexible, high-speed data communication services is of great interest. Preferred features include the ability to perform rate adaptation and satisfy various quality-of-service (QOS) conditions.

Conventional forward error correction (FEC) schemes for communication systems include the use of convolutional codes, block codes such as Reed-Solomon or BCH codes, and / or abbreviated coding schemes.

Turbo codes are a relatively new class of block code that is being argued to provide bit error rates (BER) that approach the theoretical limits for critical classes of channels idealized by cyclic soft-decision decoding methods. to be.

The turbo encoder typically consists of two systemic cyclic convolutional codes ("constituent codes") separated by an interleaver that randomizes the representation order of the information bits for the second constituent encoder associated with the first constituent encoder. It consists of parallel associations. The performance of the turbo code depends on the configuration code, interleaver, information block size (generally increasing with high data rate), and the number of decoder iterations. For certain turbo codes with mixed configuration codes, the block size and the number of decoder iterations can be ideally adjusted to trade off performance, delay and implementation complexity requirements. However, as the block size changes, a new interleaver is required that matches the clock size.

In a CDMA network with a synchronization base station, the forward link channel (from the base station to the user terminal) can be designed to be orthogonal using, for example, Walsh Hamad spreading sequence. However, in the case of a reverse link channel (from user terminal to base station) operating asynchronously using a pseudo orthogonal spreading sequence, this is generally not possible. Thus, the reverse link in a synchronous CDMA network is typically more interfering and may therefore require a stronger FEC (via a lower rate code) than the forward link channel.

For asynchronous CDMA networks, the forward and reverse link channels are somewhat similar in terms of interference level, so it is possible to use a common FEC scheme (or at least one similar FEC scheme) on the two links.

The flexibility and high performance of turbo code is becoming a potentially promising technology for advanced data communications services. Thus, it is desirable to identify turbo coding FEC schemes and turbo codes that optimally match various data conditions and respective data rates and coding rates while minimizing implementation complexity.

The present invention advantageously addresses this and other needs by providing a method for designing and using universally optimized turbo code and rate-compatible puncturings to support increasing redundancy schemes such as automatic repeat request (ARQ). Correcting.

<Summary of invention>

In its most basic form, the invention provides, in one embodiment as a method of processing data, a set of rate-compatible turbo codes that are optimized at high code rates and have compatible puncturing patterns in data services derived from universal component codes. It features code. The method encodes a signal at a first and a second encoder using a universal best rate 1/2 configuration code in accordance with an upper code rate and a lower code rate, wherein the first encoder and the second encoder each have data. Generate a respective plurality of parity bits for the bits; Puncturing each of the plurality of parity bits at each encoder with a highest puncturing pattern at a higher rate; And puncturing each of the plurality of parity bits at each encoder with the lowest puncturing pattern at a lower rate.

In a variant, using a set of rate-compatible Turbo codes derived from an optimal universal rate 1/3 configuration code, the turbo codes having similar configuration codes and compatible puncturing patterns A method of processing data in a data service includes encoding a signal having the best rate 1/3 in the first and second encoders, wherein each encoder generates a respective plurality of parity bits for each data bit. -; Puncturing the plurality of parity bits with a higher rate puncturing pattern; And puncturing the plurality of parity bits with the lowest puncturing pattern at a lower rate.

In another variant, rate-compatible using a set of rate-compatible turbo codes, the set having turbo codes optimized for code rate 1/4 and having different code rates and rate-compatible puncturing patterns The turbo encoding method encodes a signal at a first and a second encoder using an upper code rate and a lower code rate and a universal best rate 1/4 configuration code-the first encoder and the second encoder. Generates each of a plurality of parity bits for each data bit; Puncturing each of the plurality of parity bits at each encoder with a highest puncturing pattern at a higher rate; And puncturing each of the plurality of parity bits at each encoder with the lowest puncturing pattern at a lower rate.

In another embodiment, the encoding system uses a set of rate-compatible turbo codes derived from the best universal rate 1/2 configuration code, the set having a compatible puncturing pattern, wherein the encoding system comprises a first and a second one. Second Encoder-Each encoder includes a plurality of shift registers and first and second adders respectively coupled to selected portions of the first and second adders in a configuration corresponding to the best universal rate 1/2 configuration code. box-; And a puncturer configured to puncture the plurality of data outputs from each of the first and second encoders, wherein the puncturing is predetermined according to the set of compatible puncturing patterns. Determined by the turbo code rate.

In another variation, the encoding system uses a set of rate-compatible turbo codes derived from optimal universal rate 1/3 configuration codes, wherein the rate-compatible turbo codes have similar configuration codes and compatible puncturing patterns. And the encoding system comprises: first and second encoders, each encoder coupled to a selected portion of the first and second adders in a configuration corresponding to the plurality of shift registers and the rate 1/3 configuration code, respectively; Comprising a first and a second adder; And a puncturer configured such that the first and second encoders puncture a plurality of data outputs from the first and second encoders, wherein the puncturing is a predetermined turbo code in accordance with the set of compatible puncturing patterns. Determined by the rate.

Another variation of the system uses a set of rate-compatible turbo codes having universal constituent codes and rate-compatible puncturing patterns for different code rates, the system comprising first and second Encoders, each encoder including a plurality of shift registers and first and second adders respectively coupled to selected portions of first and second adders in a configuration corresponding to the universal configuration code; And a puncturer configured to puncture a plurality of data outputs from the first and second encoders, the puncturing being determined by a predetermined turbo code rate in accordance with the set of compatible puncturing patterns. .

<Brief Description of Drawings>

These and other aspects, features, and advantages of the present invention will become more apparent from the following more detailed description presented in conjunction with the following drawings.

1 is a code division multiple access (CDMA) digital cellular mobile radio system hardware diagram.

2 is a hardware diagram of a CDMA digital cellular mobile radio system in which an embodiment of the present invention may be implemented.

3 is a functional block diagram of a turbo code encoder modified for use with the present invention.

4 is a functional block diagram of an overall turbo decoder.

5, 6, 7 and 8 show turbo code rate 1/2 and rate 1/3 of interleaver size 1000, 512 and 1024 bits when the turbo code uses candidate configuration codes represented as d (D) and n (D). Shows bit error rate (BER) performance for signal to noise ratio (SNR).

FIG. 9 illustrates puncturing schemes for optimizing a rate 1/4 turbo code. FIG.

10, 11 and 12 show BER / FER performance of configuration code # 1-3, which is a frame size of 512 bits.

FIG. 13 is a diagram showing BER / FER performance of configuration code # 1 in which configuration code # 1 has a frame size of 1024 bits and consistent results are obtained in sizes 2048 and 3072 bits, respectively. FIG.

FIG. 14 shows the BER / FER performance of a selected rate 1/4 turbo code at frame size 512 with consistent results at sizes 1024, 2048 and 3072 bits, respectively.

Figure 15 is a comparison of the preferred turbo code B for another puncturing scheme with a frame size of 512 bits.

16 shows a layout of candidate puncturing patterns for turbo codes of rates 1/3 and 1/2 when the configuration code has rate 1/3.

FIG. 17 is a comparison of rate 1/3 puncturing scheme in frame size 512 bits. FIG.

FIG. 18 shows a rate 1/2 puncturing scheme at 512 bits of frame size with consistent results at 1024, 2048 and 3072 bits, respectively.

FIG. 19 is a block diagram of a preferred universally configured encoder for turbo code optimized at code rates 1/2 and 1/3 to vary interleaver depth. FIG.

FIG. 20 is a functional block diagram for rate 1/4 turbo code optimized to code rate 1/2 and rate 1/3 including interleaving and puncturing (rate 1/3, and rate 1/2 use similar processing). FIG.

21 is a puncturing pattern diagram for a rate 3/8 turbo code.

FIG. 22 shows 3/8 turbo codes with results optimized at code rate 1/2 and rate 1/3 at sustained frame size 512 bits at 1024, 2048 and 3072 bits, respectively.

23 is a puncturing pattern diagram for rate 4/9 turbo code.

FIG. 24 shows a rate 4/9 turbo code optimized at code rate 1/2 and rate 1/3 using frame size 512 bits. FIG.

25 is a functional block diagram of a preferred configuration encoder for turbo code optimized at code rate 1/4.

FIG. 26 is a functional block diagram of a rate 1/4 turbo code optimized to rate 1/4 including interleaving and puncturing (rate 1/3 and rate 1/2 use similar processing). FIG.

27 is a puncturing pattern diagram for rate 2/9 turbo code.

FIG. 28 shows a rate 2/9 turbo code optimized at code rate 1/4 using a frame size of 512 bits. FIG.

FIG. 29 is an initial puncturing pattern diagram for rate 3/8 turbo code. FIG.

30 illustrates a rate 3/8 turbo code optimized at code rate 1/4 using a frame size of 512 bits.

FIG. 31 is a functional block diagram of a preferred universal encoder for rate 1/2 and rate 1/3 turbo codes varying interleaver depth. FIG.

32 is a preferred comparison of rate 1/4 FER optimized turbo codes with convolutional codes at 512 bits of frame size with consistent results at 1024, 2048 and 3072 bits.

Appendix A is a collective set of drawings, hereinafter referred to as 'like' drawings, curves, or simulations or equivalents.

Corresponding reference characters refer to corresponding elements throughout the several views.

The present invention relates to error correction in data communications, and more particularly to forward error correction (FEC). In particular, the present invention is an emerging 3 where flexibility in supporting a wide range of system conditions related to transmission data rate, channel coding rate, quality of service measurement (ie delay, bit error rate, frame error rate) and implementation complexity is very desired. TECHNICAL FIELD The present invention relates to the selection and use of optimal turbo codes in high performance data communication systems such as terrestrial cellular mobile radio and satellite telephone systems.

The following description of the invention should not be taken in a limiting sense, but merely for illustrating the overall principle of the invention. The scope of the invention should be determined with reference to the claims.

Two main features of the present invention are: 1) Forward Air Calibration (FEC) for data services based on specific "universal" turbo codes demonstrated to provide near-optimal performance over a wide range of information block sizes and code rates. ), And 2) there is a method that allows a particular turbo code with the above-described desirable properties to be designed.

Turbo codes are particularly well suited for data applications due to their excellent error correction capabilities with low signal-to-noise (SNR) ratios and the flexibility to compromise bit error rate (BER) and frame error rate (FER) performance to handle delays. It is supposed to be done. The data service under consideration in the embodiments described below conforms to the third generation code division multiple access (CDMA) cellular mobile radio standard under development, and is typically more resistant to delay than low rate voice services.

However, the Universal Turbo Codes (and methods of obtaining such codes) specified below are also applicable to other systems such as cellular or other wireless communication systems, as well as other cellular mobile radio systems (i.e. European time division multiple access (used for GSM). Applicable to data services in the TDMA) standard). Several specific turbo codes have been identified that provide different optimizations with respect to these conditions. Other codes may also be possible.

To optimize the performance of turbo code for data services, you have a set of "universal" constituent codes that provide optimal or near optimal performance in combination with various different interleaver depths and turbo code rates. It is desirable to avoid tailoring each optimization of the turbo code.

Referring first to FIG. 1, an exemplary conventional digital cellular mobile radio system using a direct sequence code division multiple access (CDMA) mobile station to base station (or reverse) link is shown using a convolutional encoder and a Viterbi decoder. have. This basic coding and interleaving is equally applicable to other multiple access systems, such as time division multiple access (TDMA), used in known GSM standards.

1 also illustrates a base station to mobile station (or forward) link in a cellular mobile radio system. In transmission system 100, the system assembles user information bits from a data terminal device (not shown) into fixed length frames of N bits per frame 106 input to convolutional encoder 108 (of rate r). Segmentation processor 104. Convolutional encoder 108 is coupled to a synchronization and framing processor 104 that generates an N / r code symbol 110 at the input of channel interleaver 112 coupled to convolutional encoder 108. The channel interleaver 112 performs pseudo random shuffling of the code symbol 110 and outputs the code symbol 110 to a spread spectrum modulator 114 coupled to the channel interleaver 112. Spread spectrum modulator 114 uses a user specific transmit PN-code generated by PN converter 116 coupled to spread spectrum modulator 114 to spread spectrum carried on an RF carrier to mobile station RF transmitter 118. Generate a signal. The mobile station RF transmitter 118 is also coupled to a spread spectrum modulator 114 where a high power amplifier (not shown) coupled to the transmit antenna 120 copies the signal to the base station. Spread-spectrum modulation and RF transmission techniques are known to those skilled in the art of spread spectrum communication systems.

Mobile station ( ^A mobile station signal received at base station receive antenna 122) ^A mobile station signal The signal from is amplified in base station RF receiver 124 and demodulated in spread spectrum demodulator 128 which despreads the signal using the same PN code used by mobile station RF transmitter 118. The demodulated symbol is deinterleaved by the channel interleaver 130 and input to the Viterbi decoder 132. The decoded information bits are reconstructed into receive data block 136 and forwarded to the data terminal equipment at the receive end of the system.

Referring next to FIG. 2, shown is a hardware system for a digital cellular mobile radio system embodying an embodiment of the present invention. As above, although the same block diagram shows the forward link, the reverse link is shown. In addition, although a CDMA system is used as an example, those skilled in the art may consider the present invention to be applied to other systems such as TDMA.

The transmit data block 202 from the data terminal equipment is segmented and framed to a fixed frame length in the segmentation processor 204 and applied to the turbo code encoder 208. The output from encoder 208 is supplied to channel interleaver 212 to pseudo randomize the code symbols. Channel interleaver 212 provides an output to spread spectrum modulator 214 that generates a spread spectrum that is conveyed to mobile station RF transmitter 218 on an RF carrier using a user specific PN-code from PN generator 216. do. The channel interleaver 212 is distinct from the turbo code interleaver (not shown) which is a component of the encoder 208. Mobile station RF transmitter 218 coupled to transmit antenna 220 uses a high power amplifier (not shown) of transmit antenna 220 to copy the signal to the base station.

A signal from the mobile station received at base station antenna 222 is amplified at base station RF receiver 224 to spread the signal using the same PN-code as used by mobile station RF transmitter 218 ( Demodulated at 228). The demodulated symbol is deinterleaved by the channel DE-interleaver 230 and input to the turbo code decoder 232. The decoded information bits from the turbo code decoder 232 are reconstructed by the reconstruction processor 234 into the receive data block 236 and forwarded to the data terminal device of the receive end.

Referring to FIG. 3, the basic structure of the turbo code is characterized by the parallel abbreviation of two simple component codes in encoder # 1 306 and encoder # 2 308. Two configuration encoders, namely, encoder # 1 306 and encoder # 2 308, process the same information bit stream 302, whereas encoder # 2 308 has an encoder bit # 2 308 (configuration Since the interleaver 304 rearranges it before it reaches the encoder 308, the encoder # 1 306 processes the information bits 302 in a different order than the order in which the information bits 302 are processed. This configuration allows the sequence of information bits 302 to cause encoder # 1 306 to generate a low-hamming weight output 310, which also allows encoder # 2 308 to achieve superior performance of the turbo code. The likelihood of equalizing the output 314 to enable performance is reduced.

In addition to the information bits 302 (also referred to as the system bits 302), both of the encoders 306 and 308 generate parity bits 310 and 314 punctured by the puncturer 312 to provide some overall turbo code. Achieve rate. It can also puncture systemic bits.

The configuration code of the turbo code is usable systematically, a cyclic convolution code. The simplest and most widely known cyclic convolutional code has a rate 1/2 and the following transfer function:

G (D) = [1, n (D) / d (D)]

Where n (D) and d (D) are binary polymorphisms that specify the feed forward and feedback connections of the encoder, respectively.

The rate of the turbo code is changed by changing the selection of output bits 310,314 for puncturing or transmission. In all cases below, "1" indicates transmission and "0" indicates puncturing.

3 also shows two possible puncturing pattern results from the puncturer 312. Alternately puncturing the parity bits between encoders 306 and 308 results in a turbo code rate r = 1/2. The transmission of all parity bits in the two encoders 306,308 will result in a code rate r = 1/3.

It is not possible to achieve lower turbo code rates of less than one third without increasing the number of configuration encoders or increasing the number of output parity bits per configuration encoder. The latter is often desirable to reduce implementation complexity. In this case, one skilled in the art considers a rate 1/3 systemic cyclic convolutional code with the transfer function as follows.

G (D) = [1, n ₁ (D) / d (D), n ₂ (D) / d (D)]

By using these two configuration codes, puncturing or erasing will provide any turbo code rate between 1/5 and one.

The turbo code is decoded using an iterative decoding method as shown in the block diagram of FIG.

Each configuration code is individually decoded using similar estimates of other configuration decoders 406 or 416 as 'a priori' information. The configuration decoders 406 and 416 must be of soft-input / soft-output type, such as a Maximum A Posteriori (MAP) algorithm, a sub-optimal Soft-Output Viterbi Algorithm (SOVA), or variations thereof. After both of the component decoders have processed the data, the process can be repeated.

In practice, turbo decoders 406 and 416 are often limited to a fixed number of iterations that meet the implementation complexity and performance goals of the system.

4 is an overall block diagram of a turbo decoder. Soft information associated with the information bits 404, parity bits for the first encoder 402, and parity bits for the second encoder 402 'are received from the demodulator. First, the first decoder 406 uses the received information 404 and the received parity bits 402 to generate a soft decision 408 for the information bits. Soft decision 408 is interleaved by interleaver 412 whose output is soft decision 414. The soft decision 414 is supplied to the second decoder 416 as a priori information.

The second decoder 416 receives the soft decision 414 described above, and is then interleaved by the interleaver 422 and fed to the second decoder 406 as a priori information, an enhanced soft decision 420 for the information bits. ) The whole process is repeated as many times as necessary. The final output 420 is obtained by making a hard or soft decision of the first or second decoder.

According to the present invention, single mother motherboard turbo codes and various puncturing patterns can be obtained to derive uniform good codes for various code rates and information block sizes.

First, according to a trade-off between performance and implementation complexity, a methodology for determining universal construct code by limiting the initial pool of possible universal construct codes is developed. According to the present invention, performance studies using different status codes indicate that the 8-state configuration code provides a good tradeoff.

Universal configuration code is first optimized according to the main code rate of the targeted application. For example, in the case of CDMA data communication, separate optimizations may be performed for the forward and reverse links, since often the reverse link requires a lower code rate for higher coding gain.

The next step, described in more detail below, is used to generate turbo codes optimized for rates 1/2 and 1/3.

1) transfer function of the form G (D) = [1, n (D) / d (D)], where d (D) is a primitive polynomial and n (D) starts with 1 and ends with D ³ Select a candidate systemic rate 1/2 configuration encoder with &lt; RTI ID = 0.0 &gt;

2) determine a turbo code rate 1/2 and a rate 1/3 test puncturing pattern to apply to the output data encoded by the two rate 1/2 configuration encoders;

3) form all possible rate 1/2 and 1/3 turbo codes by combining the test pattern with each rate 1/2 configuration code;

4) evaluate the relative BER performance of all possible rate 1/2 and 1/3 turbo codes with a fixed interleaver length;

5) based on the best overall BER performance, choose from a group of mother pairs, a subgroup of candidate pairs to build an optimal turbo code;

6) Evaluate the different relative BER performance of a turbo code group having a subgroup of candidate pairs punctured in rate 1/2 and rate 1/3 puncturing patterns with a plurality of different interleaver depths.

7) choose from the group of turbo codes, universal codes, with the best overall relative BER relative to the interleaver depth; And

8) Encode the data with rate 1/2 and rate 1/3 turbo codes with the selected universal code pair in the first and second encoders-similar encoders and interleavers supply bits to the second encoder, and Are arranged differently before entering each encoder.

Once generated, the best turbo code of a lower rate, such as 1/4, can also be determined, compatible with the rate 1/2 and 1/3 turbo codes determined by the step.

Rate 1/2 configuration code

The following description describes how the rate 1/2 configuration code is determined in one embodiment.

First, a list of candidate 8-state, rate 1/2 configuration code polynomials is determined.

Table 1 lists the denominator polynomial d (D) and molecular polynomial n (D) determined by the octal method. There are 12 constituent nosehead candidates being considered for initial testing.

Candidate 8-state configuration encoder with rate 1/2 Denominator polynomial d (D) (octal) Molecular Polynomial n (D) (octal) 11 12 11 15 11 17 12 11 12 15 12 17 15 11 15 12 15 17 17 11 17 12 17 15

Each of the twelve polynomials 12 is represented in octal form in Table 1 and has a corresponding binary and polynomial. For example, the binary equivalent of octal number 13 is binary 1011. Binary 1011 corresponds to the following polynomial:

d (D) = D ⁰ (1) + D ¹ (0) + D ² (1) + d ³ (1) = 1 + D ² + D ³ .

The candidate turbo code is then simulated with an interleaver size of 1000 bits and three decoder iterations. The example checks whose results are shown in FIGS. 5 and 6 evaluate the bit error rate (BER) versus Ebi / No performance of all candidate turbo codes of rate 1/2 and rate 1/3, as described above. The measurement of Ebi / No is equivalent to the relative SNR.

The results of Figures 5 and 6 are used to select six (6) code polynomial pairs. The six (6) candidate universal code pairs d (D) -n (D) are shown in octal representation on the left side of Table 2 below.

Next, Table 2 is created using the corresponding performance of the 8-state turbo code using simulated data having candidate universal codes at each rate and interleaver depth. Sample performance studies or simulations are shown in FIGS. 7 and 8 showing selected turbo codes of 512 bits of interleaver depth for rate 1/2 and rate 1/3.

Table 2 below shows the approximate SNR losses for the simulated data due to using rates 1/2 and 1/3 and interleaver depths of 512, 1024, 2048 and 3072 bits.

Approximate SNR Loss Due to Use of Non-Optimized Code Candidate "Universal" Code d (D) -n (D) Turbo code rate & size (bits) 1/2 & 512 1/2 & 1024 1/2 & 2048 1/2 & 3072 1/3 & 512 1/2 & 1024 1/3 & 2048 1/3 & 3072 15-13 0.005 dB 0.00 dB 0.00 dB 0.05 dB 0.10 dB 0.05 dB 0.05 dB 0.10 dB 13-15 0.00 dB 0.00 dB 0.00 dB 0.00 dB 0.05 dB 0.05 dB 0.05 dB 0.05 dB 15-17 0.05 dB 0.05 dB 0.00 dB 0.05 dB 0.05 dB 0.05 dB 0.00 dB 0.10 dB 17-15 0.40 dB 0.50 dB 0.00 dB 0.00 dB 0.05 dB 0.00 dB 17-13 0.40 dB 0.50 dB 0.00 dB 0.00 dB 0.00 dB 0.00 dB 13-17 0.05 dB 0.05 dB 0.05 dB 0.00 dB 0.00 dB 0.10 dB 0.00 dB 0.10 dB

In a similar simulation using a 16-state code, the pairs referred to as 31-33 and 31-27 also provide a similar complexity comparison with the 8-state code using eight (8) decoder iterations, respectively. Samples using four (4) decoder iterations for status codes are shown in FIGS. 7 and 8. An 8-status code with 8 iterations performs a 16 status code with four iterations.

As a separate simulation, the performance difference among the different interleavers using the six (6) candidate pairs is observed to be within 0.05 dB.

Finally, the results in Table 2 show that the next rate 1/2 configuration code pair provides the best overall performance over the range of rates and interleaver sizes studied.

d (D) = 1 + D ² + D ³ ; n (D) = 1 + D + D ³ .

This represents octal 13 and octal 15, respectively.

In each case listed, the performance of codes 13-15 is within 0.05 dB for the best performance code for rate and interleaver size.

Thus, this configuration code is chosen as the basis for the turbo code design, where higher code rates such as 1/2 and 1/3 are dominant.

Rate 1/3 configuration code

The following describes how the rate 1/3 configuration code is determined. Similar to the rate 1/12 configuration code, the rate 1/3 configuration code candidates are identified in Table 3 below to build an almost optimal 1/4 and 1/5 turbo code rate. In this case, the constituent code candidates for the turbo code should have three (3) polynomials instead of two (2).

Candidate Configuration Codes for Optimal Lower Rate Turbo Codes CC # 1 (octal 13-15 / 17) CC # 2 (octal 15-13 / 17) CC # 3 (octal 17-13 / 15) d (D) = 1 + D ² + D ³ (octal 13) n ₁ (D) = 1 + D + D ³ (octal 15) n ₂ (D) = 1 + D + D ³ (octal 17 ) d (D) = 1 + D + D ³ (15 octal) n ₁ (D) = 1 + D ² + D ³ (13 octal) n ₂ (D) = 1 + D + D ² + D ³ ( Octal number 17) d (D) = 1 + D + D ² + D ³ (17 octal) n ₁ (D) = 1 + D ² + D ³ (octal 13) n ₂ (D) = 1 + D + D ³ ( Octal 15)

Optimum Rate 1/4 Turbo Code

In order to build up the overall rate 1/4 turbo code, various puncturing schemes must be considered in combination with each of the configuration codes in Table 3.

The various puncturing schemes of FIG. 9 are considered first. For rate 1/4 codes, common input information bits or system bits are transmitted by two encoders, one encoder with three (3) of four (4) parity bits generated for that input bit. .

The puncturing patterns of Figure 9, i.e., 910, 920, 930 and 940, are selected based on the previously described design principles to meet the specified code rates.

Next, each of the three (3) code triads of Table 3 is combined with the four (4) puncturing patterns 910, 920, 930 and 940 of Figure 9, for example for a fixed interleaver depth of 512. Generates twelve (12) possible turbo codes to be evaluated with the simulated data shown in FIGS.

The performance of the twelve (12) turbo codes is then used to select the three (3) best turbo code candidates for more detailed evaluation. Based on the simulation results shown in Figures 10-12, three of the twelve (12) best turbo code candidates are as follows:

Turbo code A-configuration code 1 having a puncturing pattern second;

Turbo code B-configuration code 2 having a puncturing pattern first; And

Turbo code C-configuration code third with puncturing pattern first (the puncturing pattern is selected from patterns 910, 920, 930 and 940 in FIG. 9).

Next, one of the turbo codes of codes A through C is selected for secondary evaluation to demonstrate that the puncturing pattern is good at different interleaver depths using simulated data of various secondary interleaver frame sizes.

To identify the basic methodology, the performance of turbo code based on configuration code first (eg) is simulated every frame size of 1024, 2048 and 3072 bits. Sample results for the BER / FER performance of 1023 bits of Code # 1 are shown in FIG. 13, which confirms the basic methodology.

14 shows BER / FER performance of simulated data using three rate 1/4 turbo code candidates A through C with an interleaver depth of 512 bits. Consistent results are also achieved at interleaver sizes 1024, 2048 and 3072 bits.

Next, in the simulations and similar figures resulting from FIG. 14, as described in Appendix A, a rate 1/4 turbo code candidate is selected from candidate turbo codes A through C that provide the overall best performance of all interleaver depths. do. In the case of rate 1/4 turbo code, the optimization based on BER performance gives different results than the optimization based on FER performance. For simulated data, turbo code B has the best overall FER performance, and turbo code C provides the best overall BER performance. 15 shows the performance of turbo code C compared to other puncturing schemes.

As such, the FER optimized turbo code B is chosen as the basis for the design because FER performance is often a more important criterion for data services. Turbo code A, on the other hand, may be punctured to provide the same universal turbo code that has been optimally identified for rate 1/3 (by puncturing all parity bits from the n ₂ (D) polynomial). That is, turbo code A is the preferred choice for forward link rate 1/4 code to have a single universal mother code that implements all different code rates.

Although current third generation CDMA encoding primarily relates to rate 1/4 channel encoding for the reverse link, rate 1/3 and rate 1/2 channel coding may be required for some highest rate data channels. Universal turbo codes for rate 1/4, rate 1/3 and rate 1/2 can be designed, where the underlying configuration code is the same and only the puncturing pattern used is different. The method for generating the higher rate turbo code from the rate 1/3 configuration code is as follows.

Rate 1/3 turbo code optimized to rate 1/4

Using the rate 1/4 optimized turbo code, ie the configuration code derived from turbo code B, rate 1/3 and rate 1/2 turbo codes can be designed to be compatible therewith. Therefore, the configuration code second (from code B) is used as the basis.

16 shows seven (7) basic puncturing patterns that can be used to generate a rate 1/3 turbo code and four (4) basic puncturing patterns to generate a rate 1/2 turbo code. In the block diagram 1600, the seven (7) rate 1/3 patterns (1602 through 1614) represent consecutive information puncturing bit patterns (1620) for two (2) encoder puncturing block patterns (1616 and 1618). 1626 and four (4) corresponding row parity bit puncturing patterns 1622, 1624, 1628 and 1630. As before, the pattern " 1111 " shown in row 1620 always transmits all information bits from encoder1. The pattern " 0000 " of row 1626 punctures the information bits entering by the term encoder second. The reason is that it is not necessary to transmit the information bits twice. The four (4) rate 1/2 puncturing patterns 1 to 4 shown in Fig. 16 as reference numerals 1640,1642,1644 and 1646 follow the same notation.

Next, the BER and FER performances of all possible 1/3 turbo codes simulated with the preferred configuration code second at interleaver depth 512 in FIG. 17 are compared.

Next, the two (2) best patterns are selected for next consideration. Next, the performance of these two (2) patterns is compared at incidental interleaver depths (1024, 2048 and 3078) bits.

For example, in FIG. 17 showing a rate 1/3 puncturing pattern of 512 bits, patterns 2 and 5 are selected based on curves 1710 and 1720 as having the best and next best overall relative FER, respectively.

Pattern 2 is then selected to have the best performance across various interleaver depths from the incidental simulation similar to that of FIG. 17 at the incidental interleaver size for 1024, 2048 and 3072 bits.

Rate 1/2 turbo code optimized to rate 1/4

Rate 1/2 code may also be optimized to lower rate code for similar compatibility as described above. 18 compares the BER and FER simulated performance of all rate 1/2 turbo codes at an interleaver depth of 512 bits. FIG. 18 is generated using the four (4) puncturing patterns and configuration code second shown in FIG. 16 for the rate 1/2 turbo code. Patterns 1 and 4 are determined to be best based on simulated curves 1810 and 1820 for FER performance.

As in the case of rate 1/3 optimized at rate 1/4, similar simulation curves for FIG. 18 are performed for patterns 1 and 4 for interleaver depths of 1024, 2048, and 3072 bits. Based on the resulting performance / curve, pattern 1 is adjusted to be the best pattern for FER performance.

Preferred Universal Turbo Codes Optimized for Rates 1/2 and 1/3

19 is a block diagram of a configuration encoder optimized according to the method previously described for turbo code rates 1/2 and 1/3. 20 shows a block diagram for a corresponding turbo code punctured at rate 1/4.

An information bit stream X (t) 1902 is received at the switch 1922, and several modular adders 1904, 1908, 1920, 1910 hardwired to represent two (2) molecular polynomials and one denominator polynomial. , 1914, 1918, 1919 and some shift registers 1906, 1912 and 1916.

In Fig. 19, the denominator polynomial d (D), represented by octal number 13, is hardwired by a return feedback connection to the modular adders 1920 and 1904. Prior to operation, the three shift registers 1906, 1912 and 1916 are first zeroed.

The first molecular polynomial above the denominator polynomial represented by " 1101 " includes the results of modulator adder 1920 and X (t) 1992 to produce a first bit W (t); W (t) from the modulator total (first bit) and modulator adder 1908 of shift register 1906; Another zero bit (third bit) indicated by the absence of a connection to the register 1912; And combining the result of the modular adder 1908 from the modular adder 1998 with the modular sum (fourth bit) of the other register 1916 is hardwired to return the output Y _o (t). The result is Y _o (t) = W (t) + S _o (t) + S ₂ (t).

In FIG. 19, the second molecular polynomial above the denominator polynomial represented by “1111” combines the result of adder 1920 with X (t) 1902 to produce a first bit W (t); Add the contents of the additional register 1906 to W (t) along with the contents of the modular adder 1910 (second bit); Add the contents of register 1912 to the result of adder 1710 with modular adder 1914 (third bit); It is hardwired to return the output Y ₁ (t) by adding the contents of another register 1916 to the result of the adder 1914 together with the modular adder 1919 (fourth bit). The result is Y ₁ (t) = W (t) + S _o (t) + S ₁ (t) + S ₂ (t).

In FIG. 19, the denominator polynomial connection sums the results of registers 1902 to 1906 at adder 1920 and then adds to X (t) at these adders 1904. Thus, if the modular adder 1904 is the value W (t), the register 1906 holds S ₀ (t), the register 1912 holds S ₁ (t), and the register 1916 holds S Holds ₂ (t), and the adder 1904 has W (t) = X (t) + S ₁ (t) + S ₂ (t); Y ₀ (t) = W (t) + S _o (t) + S ₂ (t); And Y ₁ (t) = W (t) + S ₀ (t) + S ₁ (t) + S ₂ (t). Therefore, the addition is accumulated.

If the two bits are different then the result of the modular adder is "1", and if the two bits are the same then "0". Output Y ₀ (t) represents the output from the molecular polynomial first and the denominator polynomial. Output Y ₁ (t) represents the molecular polynomial second and the denominator polynomial.

Initially, S ₀ = S ₁ = S ₂ = 0, and the values in registers 1906, 1912, 1916 shift from left to right after each clock cycle increases. Thus, S ₀ (t + 1) = W (t); S ₁ (t + 1) = S ₀ (t) and S ₂ (t + 1) = S ₁ (t).

For example, the optimal puncturing matrix shown in FIG. 20 shows "1" for the transmitted bits and "0" for the punctured bits. Exemplary FIG. 20 shows an encoder 2000 with an incident bit X (t), and an encoder 2006 to generate an output bit X ^′ (t), parity bits Y ₀ ¹ (t) and Y ₁ ¹ (t). Shows an interleaver 2002 that carries the interleaved bit X ^' (t) to. None of the interleaved bit X ^' (t) is processed in the rate 1/4 encoder 2004, only in the second rate 1/4 encoder 2006. Block 2010 shows a puncturing pattern matrix.

More complex puncturing patterns can be used to achieve other possible coding rates. For example, rates 2/8 and 4/9 are achieved against turbo codes optimized at rates 1/2 and 1/3, and optimized at rate 1/4 using the preferred turbo codes identified in the present invention. The optimal puncturing pattern can be selected to achieve rates 2/9 and 3/8 for the turbo code.

Similar to FIG. 9, the block diagram for the optimal turbo code rate 3/8 uses the rate 1/3 mother configuration code of FIG. An encoder for the configuration code of FIG. 20 is shown in FIG. 19. The puncturing pattern of the rate 3/8 turbo code shown in FIG. 21 punctures 1 of every 6 bits associated with the first molecular polynomial from two encoders to produce a rate 3/8 turbo code.

The second pattern is an extension of the first pattern that causes both component encoders to have the same rate, i.e. 6/11. The extended pattern copies the same pattern (matrix) for the other three (3) bits, but shifts the position of one transmit bit from one encoder to another. In other words, "1" in one encoder must be flipped while flipping "0" in another encoder at a similar position.

22 shows the performance of these patterns at an interleaver depth of 512 bits. Based on these and similar curves at 1024, 2048 and 3072 interleaver depths, pattern 2 is chosen to implement a rate 3/8 turbo code.

FIG. 23 illustrates the puncturing pann selected for the rate 4/9 turbo code used with the mother of the code of FIG. 20. Similarly, the second pattern is a first extension that causes both component encoders to have the same rate, i.e. 8/13.

24 shows the corresponding performance curve. Pattern 2 is chosen to implement a rate 4/9 turbo code.

As such, one exemplary turbo code design that is optimized for turbo code rates 1/2 and 1/3, and universal for all interleaved depths, provides a preferred generator polynomial d (D) = 1 + D ² + D ³ ,. n ₁ (D) = 1 + D + D ³ , and n ₂ (D) = 1 + D ² + D ³ .

Preferred puncturing patterns for various code rates are:

1) Rate 1/4-alternately punctures parity bits n ₁ from one encoder and n ₂ from the same encoder.

Rate 1/3-puncture parity bits n ₂ from two encoders

3) Rate 1/2 - puncturing parity bits n ₂ and alternately ringham puncture parity bits n ₁ from the two encoders.

4) Rate 3/8-puncture parity bit n ₂ and puncture one of every six parity bits n ₁ from two encoders.

5) Rate 4/9-puncture parity bits n ₂ and puncture three evenly out of every 8 parity bits n ₁ from two encoders.

A simplified version of this code is a universal turbo code design consisting of two constituent encoders with generator polynomials d (D) = 1 + D ² + D ³ and N ₁ (D) = 1 + D + D ³ . (The third polynomial n ₂ (D) is not used, so no corresponding output is generated, and the encoder block diagram is simplified by eliminating the corresponding connection.) This universal turbo code design is 1 / It supports the same minimum code as 3. The corresponding preferred set of puncturing patterns is as follows:

Rate 1/3-no puncturing

2. rate 1/2-alternately puncture parity bits n ₁ from two encoders;

3. rate 3/8-puncture one of every six parity bits n ₁ from two encoders; And

4. Rate 4/9-Uniformly punctures 3 out of every 8 parity bits n ₁ from two encoders.

Preferred Universal Turbo Codes Optimized for Code Rate 1 /

The basic block diagram for the preferred configuration encoder is shown in FIG.

Figure 26 is an encoder block diagram for a preferred rate 1/4 turbo code. In this case, the second parity bits are alternately punctured by two configuration encoders. The preferred puncturing pattern described in the previous section is then applied to generate rate 1/3 and rate 1/2 turbo codes. Other rates may also be supported by identifying incidental puncturing patterns. This is illustrated by considering the rates 2/9 and 3/8.

27 shows a puncturing pattern for the 2/9 reverse link code. Three (3) different patterns are compared by the performance curve of FIG. 28 with similar curves as described, for example, in Appendix A showing the performance of various frame interleaver sizes. From the pattern 2 FER curve 2810 and similar curves, pattern second is selected as the optimal FER pattern for rate 2/9.

Next, FIG. 29 shows six (6) initial check puncturing patterns for optimizing the rate 3/8 reverse link code. The performance of these patterns is simulated with a fixed interleaver length of 512 bits. Based on this simulation, patterns 5 and 6 are selected as optimal puncturing patterns for incidental examination.

Two or more expansion patterns 7 and 8 of the patterns 5 and 6 copy the same pattern for the other three information bits, but shift one position of the transmit bits in the parity sequence from one encoder pattern to another encoder pattern. This extension allows all of the configuration encoders to have the same rate, ie 6/11 at each encoder.

30 shows exemplary performance curves of the four 4 candidate puncturing patterns 5, 6, 7, and 8 for a rate 3/8 turbo code. Based on these results, Pattern 8 FER curve 3010 and similar curves, for example as shown in Appendix A, demonstrate that Pattern 8 is the optimal puncturing pattern for rate 3/8 turbo code. As such, one preferred universal turbo code design optimized for rate 1/4 is the polynomial d (D) = 1 + D + D ³ , n ₁ = 1 + D ² + D ³ , and n ₂ = 1 + D Use two configuration codes with + D ² + D ³ .

The puncturing pattern below is the associated optimal pattern as previously discussed for turbo code rate 1/4, and the FER performance for the most commonly used turbo code rate, where n ₁ is the output associated with the first molecular polynomial. Represents bits, and n ₂ represents the output bits associated with the second molecular polynomial.

1) Rate 1/4-alternately punctures parity bits n ₂ from both constituent encoders.

2) Rate 1/3-punctures parity bit n ₁ from both constituent encoders.

3) Rate 1/2-punctures parity bit n ₂ and every other parity bit n ₁ from both encoders.

4) Rate 2/9-punctures every one of every four parity bits in n ₁ from both encoders.

5) Rate 3/8-puncture one of parity bits n ₁ and every six parity bits n ₂ .

These preferred puncturing patterns are also shifted cyclically without affecting performance. Cyclically shifted patterns are equivalent.

Turbo Coding FEC Scheme for CDMA Data Services

The preferred set of universal turbo codes described herein provide a flexible, high performance channel code that is well suited for advanced data communications systems requiring a variety of low speed and high speed data services. Such a preferred universal turbo code enables different turbo encoding scheme techniques to meet certain conditions of a particular data communication system.

As a first example, one of the following two FEC schemes is suitable and recommended for a synchronous CDMA data communication network (such as a third generation CDMA 2000 system currently under development).

1) the preferred universal turbo code optimized at code rates 1/2 and 1/3 with a subset of the associated preferred puncturing patterns on the forward link, and at a code rate 1/4 with a subset of the associated preferred puncturing patterns on the reverse link Optimized universal turbo code; And

2) Preferred universal turbo codes optimized at code rates 1/2 and 1/3 with a subset of the desired puncturing patterns associated on the forward and reverse links.

As a second example, one of the following two FEC schemes is suitable and recommended for an asynchronous CDMA data communication network (such as a third generation UTRA system currently under development in Europe and Asia).

1) a preferred universal turbo code optimized at code rates 1/2 and 1/3 with a subset of associated puncturing patterns on the forward and reverse links;

2) a preferred universal turbo code optimized at code rate 1/4, as described above, with a subset of the desired puncturing patterns associated on the forward and reverse links; And

3) A simplified version of the universal turbo code, as described above, with a subset of the desired puncturing patterns associated on the forward and reverse links.

The choice of implementation to implement depends on the expected good code rate, minimum code rate, and implementation complexity limitations, as well as other system conditions. Of course, additional puncturing patterns can be designed in accordance with the teachings of the present invention to provide other turbo coding rates.

Other variations

Universal turbo code for high speed data services is particularly suitable for third generation CDMA cellular mobile radio systems, but can be readily applied to other systems.

Known variations, such as frame oriented convolutional coding (FOCTC), may also be used in the preferred universal construction code and universal turbo code of the present invention. The design methodology of selecting universal configuration code and universal turbo code can also be applied to alternative turbo code structures, such as engaging in more than two configuration encoders and engaging in serial abbreviations instead of or in parallel abbreviations.

Exemplary preferred puncturing patterns described in the present invention may be modified or modified in various ways by those skilled in the art. For example, the cyclic shift of the preferred puncturing pattern provides a performance that is substantially equivalent to the preferred puncturing pattern described herein. In addition, certain data communication systems may require different and additional puncturing patterns to support rate matching. These puncturing patterns can be designed in accordance with the teachings of the present invention.

Set of rate-compatible universal turbo codes

According to the present invention, an AWGN channel for various code rates and various interleaver depths can be generated by having a turbo code set of a certain higher rate transmit the same bit position as that transmitted by a turbo code of any other lower rate of the same set. It is possible to provide a set of rate-compatible turbo codes that are uniformly optimal or near optimal.

In particular, one embodiment includes various code rates of 1/5, 1/4, 1/3, and 1/2, and rate-compatible turbo code sets of various interleaver depths of 512 to 3072 bits.

Another preferred embodiment provides multiple turbo code sets that are optimized under different conditions that allow the system designer to trade off performance versus diversity information (and thus complexity) or vice versa. The selection of the rate-compatible turbo code set is based on the universal configuration encoder described below.

The universal configuration encoder of the present invention provides optimal or near optimal performance over a large range of code rates and interleaver depths. Different optimization criteria, such as reverse link or forward link dominance and degree of diversity, result in different rate-compatible turbo code sets.

Rate-compatible code sets are particularly suitable for hybrid ARQ schemes applied to satellite broadcasting and telephony.

Some preferred embodiments have different sets of rate-compatible codes based on different universal configuration codes, and different rates of puncturing patterns optimized according to different design criteria.

In accordance with the overall methodology of the present invention, four (4) different preferred rate-compatible turbo code sets are described herein. The first two (2) sets are optimized for high rate turbo codes with higher rates prevailing. The second two (2) sets are optimized for the code of the lower rate where the lower rate prevails. These sets are referred to as sets A-D below.

The first preferred set is derived from the best universal construction code of rate 1/2.

The second set is derived from the other best configuration code at rate 1/3, which is also compatible with the universal configuration code at rate 1/2.

The first set, "set A" has two generator polynomials, while the second set, "set B" has three generator polynomials, two of which are common with "set A". As such, "set B" is optimally compatible with "set A", thereby reducing the amount of design change for encoding and decoding. As before, a third polynomial is needed for the additional encoder parity bits of the turbo code below rate 1/3.

The second set "Set B" includes "Set A" and also extends the family of turbo codes for rates 1/5 and above.

The third and fourth preferred rate-compatible turbo code sets are optimized for lower rates, in particular rate 1/4. "Set C" and "Set D" each also use three generator polynomials, the same as those in "Set B" but in a different order.

Rate-compatible set derived from universal construction code of rate 1/2: set A (rate 1/3, 1/2)

From Table 2, it is determined that the rate 1/2 configuration code that provides the best overall performance is octal pair 13-15. Thus, this configuration code pair is used as the mother configuration code pair for set A.

The rate-compatible set A has a generator polynomial corresponding to octal pair 13-15, where the denominator polynomial is 1 + D ² + D ³ (13 octal) and the molecular polynomial is 1 + D + D ³ (8 Decimal 15).

The puncturing patterns are designed such that all bits transmitted at a rate of one-half code (or more) of the set are also transmitted by a rate one-third code or a lower rate code set.

Exemplary preferred patterns demonstrated by simulation and design principles are as follows:

1) for rate 1/3, there is no puncturing,

2) For rate 1 /, parity bits are alternately punctured between encoders (note that there is no second molecular polynomial encoding in this case).

Figure 31 shows a block diagram for a set A configuration encoder. In FIG. 31, the modular adders 3104, 3108 (connected to the shift register 3106), and the modular adder 3116 (connected to the shift register 3114) represent a molecular polynomial representing octal 15 or binary 1101. It is provided with an encoding device.

Modular adders 3104, 3108, 3112 and 3116 add the contents of shift registers 3106, 3110 and 3114 and X (t) in a manner similar to FIG.

The simulated performance of rate 1/2 turbo code and rate 1/3 turbo code is based on the best 256-known 8-state convolutional code designed in the present invention (with 8 decoder iterations) known according to the simulation data produced by the applicant. For the state convolutional code, it has a performance gain (BER) of about 1/6 dB at rate 1/2 and about 2.0 dB at rate 1/3.

As such, the turbo code of set A is compared to the performance for the best known 256-state convolutional code when simulated for significant performance parameters.

Rate-compatible set derived from universal configuration code of rate 1/3: set B (rates 1 / 2,1 / 3,1 / 4,1 / 5)

As in the case of determining the universal construction code of rate 1/3, an additional output molecular polynomial is needed for the "set B" rate-compatible generator polynomial derived from the best configuration code of rate 1/3.

Thus, the second best individual rate 1/2 configuration code is selected from Table 2. As before, this method results in two (2) octal pairs overlapping. Octal pairs, octal 13-15 and octal 13-17 all provide uniformly superior performance. By joining two (2) pairs together, three (3) generator polynomials with three-octal octets 13-15 / 17 are provided. The denominator polynomial is 1 + D ² + D ³ (13 octal), the first molecular polynomial is 1 + D ² + D ³ (15 octal), and the second molecular polynomial is 1 + D + D ² + D ³ (8 Decimal 17). The preferred design for set B has these generator polynomials for all interleaver depths, and turbo code rates 1/2, 1/3, 1/4 and 1/5.

In set B, the rate 1/3 and rate 1/2 turbo codes generated from the rate 1/3 configuration encoder are the same 1/3 and 1/2 turbo codes in set A created from the universal rate 1/2 configuration encoder, Preserve compatibility between and set B.

The puncturing patterns are designed such that all bits transmitted at any higher rate turbo code of set B are also transmitted at any lower code rate of set B.

Exemplary preferred patterns and design principles demonstrated by simulation are as follows:

1) rate 1/5-no puncturing;

2) Rate 1/4-alternately punctures second molecular parity bit n ₂

3) Rate 1/3-always punctures second molecular parity n ₂

4) Rate 1/ _2- always puncture the second molecular parity bit n ₂ and always puncture the first molecular parity bit n ₁

In the case of the rate 1/4 pattern, the weaker arms of the two (2) output arms of the constituent encoder are alternately punctured.

In the case of the rate 1/3 pattern, the weak outputs of the two (2) constituent encoder outputs are alternately punctured.

For rate 1/2, the weaker of the two (2) constituent encoder outputs are always punctured for both encoders and the strong output is punctured.

Rate-compatible set optimized for low turbo code rate

If the higher code rate is the dominant mode turbo code, then set B is the preferred design choice when strict rate-compatibility is required for all code rates.

When rate-compatibility between lower rate and higher rate turbo codes is not needed, turbo code set C and set D, both optimized for lower turbo code rate, are useful.

Based on the candidate configuration codes listed in Table 3, which are selected based on the results of Table 2 as described previously, the optimal turbo codes for rates 1/4 and 1/5 are selected.

It is the basis for the configuration code first or octal set A in Table 3. However, when the lower rate is not used with the higher rate, the newly optimized 1/4 turbo code is removed by removing the condition that the rate 1/4 puncturing pattern should be that of the rate 1/2 or 1/3 code. Each of the three (3) mother turbo code triads of Table 3, with each of four (4) different puncturing patterns, is considered.

As mentioned above, turbo codes A, B and C are found to be optimal from the respective performance curves 1010, 1110 and 1210 of FIGS.

As before, these puncturing patterns are also demonstrated in other interleavers by simulating the performance of turbo codes based on mother code triad first for ancillary other interleaver frame sizes of 1024, 2048 and 3072. 13 shows sample results of the simulation and confirms the basic methodology at 1024 bits.

Next, FIG. 14 shows a sample corresponding to the performance of a triad that matches the selected puncturing pattern at 512 bits. From similar results for FIG. 14 and other interleaver sizes, the best overall BER performance of all simulated interleaver depths is used as the final design criterion to determine the best candidate.

Rate-compatible set derived from rate 1/4 turbo code: set C (rates 1/5, 1/4, 1/3)

Turbo code set C implements code first and pattern first (turbo code C) from FIG. 9, in accordance with the performance curve 1310 of FIG. 14 and similar curves for different interleaver sizes.

Turbo code set C is a table comprising denominator polynomial 1 + D + D ² + D ³ , first molecular polynomial n ₁ , 1 + D ² + D ³ , and second molecular polynomial n _2, 1 + D + D ² Generator polynomial from 3. As explained previously, the optimal puncturing pattern from a simulation consistent with the methodology is:

1) For rate 1/5-no puncturing

2) rate 1/4-alternately punctures the second molecular polynomial,

3) For rate 1/3-always puncture the second molecular polynomial.

Rate-compatible set derived from rate 1/4 turbo code: set D (rates 1/5, 1/4)

Turbo code set D has a single configuration code for all interleaver depths and turbo code rates 1/4 and 1/5.

Turbo code set D implements code first with pattern second (turbo code A) from FIG. 9 according to the performance curve 1420 of FIG. 14 and similar curves of different interleaver sizes.

This set includes a generator comprising a denominator polynomial d, 1 + D + D ³ , a first molecular polynomial n ₁ , 1 + D ² + D ³ , and a second molecular polynomial n _2, 1 + D + D ² + D ³ It has a polynomial.

The optimal puncturing pattern from simulation, previously described and consistent with the methodology, is as follows:

1) For rate 1/5-no puncturing

2) For rate 1/4-alternately puncture the output 1/2.

The performance of the rate 1/4 FER optimized turbo code of the selected interleaver depth of 512 to 3072 bits is compared to the convolutional code in sample figure 32 and similar studies.

More complex puncturing patterns can be used for convolutional coding to achieve any code rate above that of the base turbo code in each rate-compatible set.

For example, rates above 1/2 or intermediate rates, such as 5/12, can be achieved. With the proper choice of puncturing pattern, this can often be done without sacrificing error correction performance.

Application of Rate-Compliant Turbo Codes

An example application of the rate-compatible turbo code described in the present invention is for rate matching selected so that the code rate matches the available physical channel. In a rate matching scheme, data services use the same basic encoding, but may use the same physical channel, especially if the quality of service specification is different for different data services.

According to the present invention, different puncturing patterns may be selected to generate code rates compatible with physical channels. If the puncturing patterns are rate-compatible, the selection of code rate need not be completed by a single decision unit at a single appropriate time. Instead, this decision can be distributed throughout the decision unit as well as in time. The turbo encoder first generates a coded output sequence that corresponds to the lowest code rate to be supported by the system. For example, all possible parity bits will be output initially. Next, initial puncturing will be performed by one puncturing unit, for example, in response to a quality-of-service (Qos) consideration for a given data service. In this scenario, the data service, for example, does not require the lowest possible code rate available in the system, but the highest quality within that range requires some intermediate code rate, and the lowest quality code within that range is even higher. It can allow a range of Qos that can tolerate rates. The first puncturing unit removes the bits coded according to the puncturing pattern corresponding to the lowest rate to provide the highest quality within the Qos range of the data service. Unpunctured coded data is output to the rest of the system for additional processing. In subsequent processing, it is determined to adjust the code rate higher for the message based on the dynamic traffic management considerations. For example, to accommodate messages from higher priority data services, physical channels with smaller payloads will be replaced, depending on the potential needs for the physical channels normally associated with that data service. The higher code rate is achieved by performing a second puncturing according to the puncturing pattern associated with the new code rate. Since the puncturing pattern is rate-compatible, there is no need to play the coded bits deleted by the first puncturing unit, and the second puncturing unit is simply a higher rate puncturing not erased by the first puncturing unit. Delete the bit specified by the pattern.

A second exemplary application of the rate-compatible turbo code described in the present invention is an incremental redundancy scheme such as error control based on the ARQ protocol. In these schemes, the turbo encoder first generates a coded output corresponding to the highest code rate available in the system. If the encoded output is sent on a communication channel, the receiver may or may not be able to successfully decode the message. If the message is successfully decoded, the receiver typically sends a negative acknowledgment (NAK) to the transmitter, requesting an additional transmission that aids in decoding the packet. By rate-compatible channel encoding, the excess encoded bits generated by one of the lower rate compatible encodings for that packet may be sent to increase the information available to the decoder of the receiver. This decoder performs decoding using the new information along with the original information received for that packet. The effect is if the original packet was encoded as a lower rate code. This process can be repeated until the packet has been successfully decoded. By sending the redundant coded bits at each retransmission, the traffic load required for retransmission is greatly reduced.

Although the invention has been described in terms of specific embodiments and applications thereof, numerous modifications may be made by those skilled in the art without departing from the scope of the invention as set forth in the claims.

<Appendix>

Claims (17)

Data service using a set of rate-compatible Turbo codes optimized at high code rates and derived from universal constituent code, the turbo codes having compatible puncturing patterns. In the method of processing data in the Encoding a signal at the first and second encoders using a higher code rate and a lower code rate and a universal best rate 1/2 configuration code, wherein each of the first and second encoders is for one data bit. Generate a plurality of parity bits; Puncturing each of the plurality of parity bits at each encoder with a highest puncturing pattern at a higher rate; And Puncturing each of the plurality of parity bits at each encoder with a lower rate best puncturing pattern. How to include. The method of claim 1, wherein the best rate 1/2 configuration code is a combination of polynomial 1 + D ² + D ³ (octal number 13) and polynomial 1 + D + D ³ (octal number 15), where D is the data bit. How to indicate. 3. The method of claim 2, wherein one of the rate-compatible turbo codes in the set comprises a rate 1/2 turbo code and one of the puncturing alternately punctures the parity bits between the first and second encoders. Method comprising the same. 3. The method of claim 2, wherein one of the rate-compatible turbo codes in the set includes a rate 1/3 turbo code, and one of the puncturing transmits all parity bits in the first and second encoders. Method comprising the steps. A method of processing data in a data service using a set of rate-compatible turbo codes derived from an optimal universal rate 1/3 configuration code, the turbo codes having similar configuration codes and compatible puncturing patterns. , Encoding a signal having the best rate 1/3 in the first and second encoders, wherein each encoder generates a respective plurality of parity bits for each data bit; Puncturing the plurality of parity bits with a higher rate puncturing pattern; And Puncturing the plurality of parity bits with a lower rate best puncturing pattern. How to include. 6. The method of claim 5, wherein the best rate 1/3 configuration code is: polynomial 1 + D ² + D ³ , (octal 13), polynomial 1 + D + D ³ (octal 15), and 1 + D + D ^2. + D ³ A combination of octal 17, where D is the data bit. 6. The method of claim 5, wherein the set of turbo codes comprises a rate 1/5 turbo code, wherein at least one of the puncturing steps includes transmitting all parity bits in the first and second encoders. Way. 6. The method of claim 5, wherein the set of turbo codes comprises a rate 1/4 turbo code, wherein at least one puncturing step of the puncturing step comprises a selection group of the plurality of parity bits between the first and second encoders. Alternately comprising puncturing. 6. The method of claim 5, wherein the set of turbo codes comprises a rate 1/3 turbo code, wherein at least one puncturing of the puncturing step comprises selecting groups of the plurality of parity bits in the first and second encoders. A method comprising alternating puncturing. 6. The method of claim 5, wherein the set of turbo codes comprises a rate 1/2 turbo code, wherein at least one puncturing of the puncturing step punctures the select groups of the plurality of parity bits in the encoders. And alternately puncturing another selection group of the plurality of parity bits in the encoders. In a rate-compatible turbo encoding method using a set of rate-compatible turbo codes, the set having turbo codes optimized for code rate 1/4 and having different code rates and rate-compatible puncturing patterns. In Encoding a signal at the first and second encoders using a higher code rate and a lower code rate and a universal best rate 1/4 configuration code, wherein each of the first and second encoders is one data. Generate a respective plurality of parity bits for the bits; Puncturing each of the plurality of parity bits at each encoder with a highest puncturing pattern at a higher rate; And Puncturing each of the plurality of parity bits at each encoder with the lowest puncturing pattern at a lower rate. How to include. The method of claim 11, wherein the set of rate-compatible turbo codes represents a combination of polynomials 1 + D + D ³ , 1 + D ² + D ^3, and 1 + D + D ³ , where D is a data bit; The associated rate-compatible puncturing pattern is Sending all data, Alternately puncturing the parity bits associated with polynomial 1 + D + D ³ ; And Puncturing the parity bits associated with polynomial 1 + D + D ³ for each encoder. 12. The method of claim 11, wherein the set of rate-compatible turbo codes is two or more turbo codes of different rates selected from the group of rates comprising one fifth and one quarter-the turbo codes are polynomial 1 + D + D ³ , a combination of 1 + D ² + D ³ and 1 + D + D ² + D ³ , where D represents a data bit. The associated rate-compatible puncturing pattern is Transmitting all data, and Alternately puncturing the parity bits associated with the polynomial 1 + D + D ² + D ³ . In an encoding system using a set of rate-compatible turbo codes derived from a best universal rate 1/2 configuration code, the set having a compatible puncturing pattern, First and second encoders-each said encoder A plurality of shift registers, and A plurality of adders, each coupled to a selected portion of the adders in a configuration corresponding to the best universal rate 1/2 configuration code; And A puncturer configured such that the first and second encoders puncture a plurality of data outputs from each of the first and second encoders, wherein the puncturing is a predetermined turbo according to the set of compatible puncturing patterns. Determined by the code rate An encoding system having a. In an encoding system using a set of rate-compatible turbo codes derived from an optimal universal rate 1/3 configuration code, wherein the rate-compatible turbo codes have similar configuration codes and compatible puncturing patterns. First and second encoders-each said encoder A plurality of shift registers, and A plurality of adders, each coupled to a selected portion of adders in a configuration corresponding to the rate 1/3 configuration code; And A puncturer configured such that the first and second encoders puncture a plurality of data outputs from the first and second encoders, the puncturing being a predetermined turbo code rate in accordance with the set of compatible puncturing patterns. Determined by An encoding system having a. An encoding system that uses a set of rate-compatible turbo codes including universal constituent code for different code rates and turbo codes having rate-compatible puncturing patterns, wherein: First and second encoders-each said encoder A plurality of shift registers, and A plurality of adders, each coupled to selected portions of a plurality of adders in a configuration corresponding to the universal configuration code; And A puncturer configured such that the first and second encoders puncture a plurality of data outputs from the first and second encoders, the puncturing being a predetermined turbo code rate in accordance with the set of compatible puncturing patterns. Determined by An encoding system having a. Determine a set of rate-compatible turbo codes optimized at a high code rate, wherein the set is derived from a best universal construct code of rate 1/2 compatible with a higher code, the turbo code having a compatible puncturing pattern In the way, Selecting a group of candidate mother constituent code pairs having primitive irreducible polynomials based on code pair checking and diversity, wherein the code pair checking comprises a fixed interleaver length of a fixed interleaver length. Simulating the relative bit error rate (BER) performance of rates 1/2 and 1/3 turbo code; Measuring the relative signal-to-noise ratio loss of the signal after a plurality of encodings for each candidate pair at a plurality of different interleaver depths and two different turbo code rates, each of the plurality of encodings comprising a candidate pair, interleaver depth and rate Having different combinations of; Selecting the best candidate based on the best relative signal to noise ratio loss from the measurement; And For each of the two or more rate-compatible turbo codes of the set, selecting at least one low rate and one high rate best puncturing pattern for the best candidate pair—the at least one high rate pattern Selects transmission of any parity bits selected for transmission by the at least one low rate pattern of the set; How to include.