HK1038448B - Interleavers and interleaving method for turbo code - Google Patents

Description

Interleaver and interleaving method for Turbo coding

Technical Field

The present invention relates to electronic communication systems, and in particular to interleavers for performing coded modulation.

Background

Techniques for encoding a communication channel, known as code modulation, have been found to improve the Bit Error Rate (BER) of electronic communication systems, such as modems and wireless communication systems. An example of transmitting encoded information is shown in EP0235477, which discloses a method and apparatus for transmitting encoded information that is anti-mixed, according to the law x_k＝x_o+k_pN interleaving Bn symbols and B codewords encoded with n symbols, where x is given by the order of module B_oIs the starting point in the sequence Bn symbols and p is the first number of Bn, k taking a value between 0 and Bn-1. Consecutive sequences of B.n symbols can be linked in different orders, produced by the same law, but with different starting points x_oAnd different step sizes P.

Turbo (Turbo) coded modulation has proven to be a practical, power-efficient and bandwidth-efficient modulation method for "random error" channels characterized by Additive White Gaussian Noise (AWGN) or fading. These random error channels have been found, for example, in a Code Division Multiple Access (CDMA) environment.

The main novelty of Turbo coding is the interleaver, which permutes the originally received or transmitted data frames before inputting them to the second encoder. The permutation is done by a processor executing a randomization algorithm, the structure of which is well known. Combining the permuted data frames with the original data frames has shown to achieve low error rates in AWGN and fading channels. The interleaving process increases the data diversity in this way so that if the modulated symbols in the transmission are distorted, the error can be recovered in the decoder using an error correction algorithm.

Conventional interleavers aggregate or frame signal points to be transmitted into a matrix, where one row of the matrix is sequentially filled at a time. After a predetermined number of signal points have been framed, the interleaver is emptied by sequentially reading out the columns of the matrix to be transmitted. As a result, those signal points in the same matrix row that are immediately adjacent to each other in the original stream of signal points are separated by a number of signal points equal to the number of rows in the matrix. Ideally, the number of rows and columns is chosen so that after transmission, the correlated signal points are separated by burst errors for the channel that are greater than the expected length. However, this is not practical. As the number of lines increases, the signal delay increases due to the framing of the signal points. As a result, there is a systematic constraint on the interleaver size to keep the signal delay within an acceptable range. On the other hand, limiting the size of the interleaver limits the separation of time-different (time-reverse) correlated signal points, thus limiting the improvement in the error performance obtained by the interleaver.

There are two conventional interleaving methods: uniform interleaving (i.e., a regular interleaving method); and non-uniform interleaving (i.e., pseudo-irregular interleaving method). In the case of uniform interleaving, a higher-weight Finite Codeword (FC) may be constructed from a lower-weight FC. Thus, a certain "repetitive pattern" of low weight FC output sequences can occur in the output stream of a uniformly interleaved turbo encoder. However, uniform interleaving does not effectively decorrelate the outputs of the two encoders, and therefore, the minimum distance of the resulting turbo code cannot be increased as desired.

On the other hand, non-uniform interleaving results in better "maximum dispersion (scattering)" of data and "maximum irregularity" of the output sequence, which means that the redundancy introduced by the two convolutional codes is more uniformly spread in the output sequence of the turbo encoder. The minimum distance is increased to a value greater than that required for uniform interleaving. One permanent problem with non-uniform interleaving is how to obtain an effective "non-uniformity" because the interleaving algorithm can only be based on a pseudo-irregular approach. In addition to these, the means employed to implement this embodiment should be useful in practical applications. Furthermore, the conventional interleaver requires a large amount of memory space in the encoder. Conventional interleaving matrices also require delay compensation, which limits their use in applications with real-time requirements.

Therefore, there is a need for a system and method of interleaving codes that minimizes the required delay compensation.

It is an object of the present invention to provide a system and method for improving non-uniform interleaving coding.

It is another object of the present invention to provide a system and method for interleaving codes that minimizes the required delay compensation.

Summary of The Invention

These and other objects are achieved in accordance with the teachings of the present invention by the present invention of interleaving a data frame, wherein the data frame has a predetermined size and is comprised of portions. Embodiments of the present invention include a memory configured to receive and store a data frame. Once received, the data frame is indexed by a plurality of rows having a predetermined row size and a plurality of columns having a predetermined column size. The product of the predetermined row size and the predetermined column size is equal to the predetermined size of the data frame.

A processor is coupled to the memory and is configured to divide the frame of data into a plurality of portions. The processor is further configured to generate a permuted sequence that the plurality of portions have, wherein i is based on₁(n₁)＝α₁^(n₁)mod(P₁) Indexing multiple parts by multiple rows, where P₁Is a prime number greater than a predetermined row size, n₁Is an exampleEnclose from 1 to P₁-1 (including P)₁-1) integer, and a₁Is P₁The root of (2). The algorithm is such that i₁(n₁) Is a unique number between 1 and a predetermined line size.

The processor is further configured to generate a plurality of partial permutation sequences, wherein i is based on₂(n₂)＝α₂^(n₂)mod(P₂) Indexing multiple parts by multiple columns, where P₂Is a prime number, n, of days in a predetermined column size₂Is in the range of 1 to P₂-1 (including P)₂-1) integer, and a₂Is P₂The root of (2). The algorithm is such that i₂(n₂) Is a unique number between 1 and a predetermined column size. The result is an interleaved portion of the data frame.

Brief Description of Drawings

The present invention will be more clearly understood from the detailed description of exemplary embodiments taken in conjunction with the accompanying drawings, in which:

fig. 1 is a diagram of a typical turbo encoder.

Fig. 2a and 2b are flowcharts illustrating the operation of an improved turbo code interleaver according to the present invention.

Fig. 3 is a flow chart illustrating another embodiment of an improved turbo code interleaver according to the present invention.

Detailed description of the invention

The present invention is an apparatus and method for interleaving codes. The interleaver takes input data frames of every N data bits and rearranges them in a pseudo-random manner before encoding by the second encoder. The present invention may be used in satellite communication systems, wireless telephone systems, modems, computers, and the like.

The interleaver orders the bits in a way that lacks any apparent ordering. The present invention may perform better than a conventional interleaver even in the case where the data frame is small (i.e., where N is on the order of thousands). This is done by obtaining a more diverse "dispersion" than a conventional interleaver. Figure 1 shows a standard turbo encoder. It comprises two encoders 10 and 20 and an interleaver 30. The encoders 10 and 20 are connected in parallel such that the interleaver 30 is concatenated before the second encoder 20. The output of the first encoder 10 is a low weight encoding 50 and the output of the second encoder 20 is a high weight encoding 60. These outputs may be to a device such as an encoding shortening mechanism (not shown) to periodically delete selected bits to reduce encoding overhead. Further, the output of the interleaver 70 may also be sent directly to the shortening mechanism, although this is not required. Furthermore, the present invention may also be used with other non-turbo coding systems that require code interleaving.

The present invention discloses two embodiments of an interleaver that can improve the performance of conventional turbo coding. The first embodiment is referred to as Galya interleaver and the second embodiment is referred to as Frequency Hopping (FH) interleaver. Both embodiments are based on the principles of number theory and both embodiments may be implemented in software or hardware (i.e., Application Specific Integrated Circuits (ASICs), Programmable Logic Arrays (PLAs), or any other suitable logic devices, the structure of which is known).

In a first embodiment, the Galya interleaver, the matrix of information bits has N₁Row and N₂Column, thereby N₁*N₂N. In addition, prime numbers P are also present₁And P₂Each of which is greater than N₁And N₂(i.e., P)₁＞N₁And P₂＞N₂). Preferably, the prime numbers should be greater than N, respectively₁And N₂The lowest prime number of (a) is not required. Initial root (initial root) alpha can be determined for these prime numbers using conventional methods₁And alpha₂. With the above parameters, the bit sequence for the Galya interleaver is defined by the following equation:

i₁(n₁)＝α₁^(n₁)mod(P₁) Wherein n is₁＝1，2，…，P₁-1; and i₁(n₁)≤N₁(ii) a And

i₂(n₂)＝α₂^(n₂)mod(P₂) Wherein n is₂＝1，2，…，P₂-1; and i₂(n₂)≤N2。

For N256, N₁＝N₂＝16，P₁＝P₂＝17，α₁＝α₂＝3。

Fig. 2a and 2b show the implementation of the above embodiments in software or hardware. The above equations may be implemented in a parallel or serial approach. In FIG. 2a, step 200 defines the representation block length N₁The parameter (c) of (c). Array i to be used for storing a bit sequence₁(n₁) Is defined as a dimension N₁And initialized (step 210). Next, define prime number P₁Greater than N₁(step 220). Step 230 defines N₁Is called alpha₁. Defining a counter n₁And initializes it to 1 (step 240) and increments each pass through the loop (step 270). As shown in step 260, the counter determines when to break (break out of) a loop (step 250) for the bit sequence, i, of each symbol in the data frame₁(n₁) And counting. The loop is conditionally broken when the entire data frame has been replaced. The loop may also be adjusted to interleave portions of received or transmitted data frames.

In step 2b, step 400 defines the representation block length N₂The parameter (c) of (c). Defining an array storing a sequence of bits to be of size N₂And initializes it (step 410). Next, define prime number P₂Greater than N₂(step 420). Step 430 defines N₂Initial root of, a₂. Defining a counter n₂And it is initialized to 1 (step 440) and incremented each pass through the loop (step 470). The counter determines when to break the loop for the bit sequence, i, of each symbol in the data frame, as shown in step 460₂(n₂) And counted (step 450). The loop is conditionally broken when the entire data frame has been replaced. The loop may also be adjusted to interleave portions of received or transmitted data frames.

In a second embodiment, the FH interleaver assumes a block length (or data frame size) of N. Furthermore, there is a prime number P greater than N. Preferably, the prime number should be the lowest prime number greater than N, but this is not required. For a given prime number, the initial root α can be found using conventional methods. Thus, for example, if N is 256, then P is 257 and α is 3. With the above parameters, the bit sequence for the FH interleaver is defined by the following equation:

i (N) ═ α (N) mod (P), where N ═ 1, 2, …, P-1, i (N) ≦ N.

Fig. 3 shows a method for implementing the above-described embodiments in software or hardware. Step 300 defines a parameter representing the block length N. The array for storing the bit sequence is defined to size N and initialized (step 310). Next, a prime number P is defined to be greater than N (step 320). Step 330 defines the initial root of N, α. A counter n is defined and initialized to 1 (step 340) and is incremented each time a loop is passed (step 370). The counter determines when to break the loop, shown as step 360, which counts the bit sequence i (n) for each symbol in the data frame (step 350). The loop is conditionally broken when the entire data frame is permuted. The loop may be adjusted to interleave portions of received or transmitted data frames.

One skilled in the art recognizes that any initial value i for array i (n) may be used₁(n₁) Or i₂(n₂) And are within the scope of the present invention. For example, the initial values may include 0, 1, 2, etc., or a template may be generated with different initialization data. Furthermore, it is common to use indices of different starting values during programming. Thus, n₁And n₂Can be any integer and the cycle off condition n ≦ N, n can be adjusted accordingly₁≤N₁、n₂≤N₂And fall within the scope of the present invention.

The disclosed interleaver is compatible with existing turbo coding structures and is compatible with current decoding algorithms. These interleavers provide superior performance without increasing system complexity.

In addition, those skilled in the art will recognize that a deinterleaver may be used to decode the interleaved data frame. The structure of a deinterleaver for decoding turbo codes is known in the art. They are not further described here. Therefore, the deinterleaver corresponding to the first embodiment can be constructed using the following permutation sequence for deinterleaving:

i₁(n₁)＝α₁^(n₁)mod(P₁) Wherein n is₁＝1，2，…，P₁-1; and i₁(n₁)≤N₁(ii) a And

i₂(n₂)＝α₂^(n₂)mod(P₂) Wherein n is₂＝1，2，…，P₂-1; and i₂(n₂)≤N₂。

Then, the deinterleaver corresponding to the second embodiment can also be constructed with the following permutation sequence for deinterleaving:

(n) α ^ (n) mod (P), where n is 1, 2, …, P-1; and i is less than or equal to N (N).

It will thus be seen that the invention effectively achieves the objects set forth above, among those made apparent from the preceding description. In particular, the present invention provides a system and method of interleaving codes.

It is to be understood that variations may be made in the above constructions and in the sequence of operations described above without departing from the scope of the invention. Accordingly, the foregoing description and drawings are by way of example only, and not limitation.

It is to be understood that the appended claims are intended to cover all of the generic and specific features of the invention herein described and all statements of the scope of the invention which, as a matter of language, might be said to fall therebetween.

Claims (34)

1. An apparatus for interleaving a plurality of portions of a data frame having a predetermined size, comprising:

means for receiving and storing the data frame;

means for dividing the data frame into the plurality of portions; and

for according to i (n) ═ αⁿmod (P) means for permuting said portions, wherein P is a prime number greater than said predetermined size of said data frame, n is an integer in the range 1 to P-1 and including P-1, and α is the root of P, such that i (n) becomes1 and said predetermined size.

2. The apparatus of claim 1, wherein the plurality of portions have a predetermined size, wherein the predetermined size is at least 1 bit.

3. The apparatus of claim 1, wherein the means for permuting is implemented with an Application Specific Integrated Circuit (ASIC).

4. The apparatus of claim 1, wherein said means for permuting is implemented for a microprocessor.

5. The apparatus of claim 1, wherein the permutation is implemented in software.

6. The apparatus of claim 1, further comprising means for column interleaving the plurality of portions according to a permutation sequence.

7. The apparatus of claim 1, wherein:

the apparatus for receiving and storing the data frame includes a memory configured to receive and store the data frame indexed by a plurality of rows having a predetermined row size and a plurality of columns having a predetermined column size, wherein a product of the predetermined row size and the predetermined column size is equal to the predetermined size of the data frame;

the apparatus for separating the data frames includes a processor coupled to the memory for separating the plurality of portions and according to i₁(n₁)＝α₁^(n₁)mod(P₁) Generating a permutated sequence of the plurality of portions indexed by rows, where P₁Is a prime number, n, greater than the predetermined row size₁Is from 1 to P₁-1 and comprising P₁-1 and alpha₁Is P₁Root of (a) which is₁(n₁) Becomes a unique number between 1 and the predetermined row size; and

the processor is configured to operate according to i₂(n₂)＝α₂^(n₂)mod(P₂) Generating a permutated sequence of the plurality of portions indexed by the plurality of columns, wherein P₂Is a prime number, n, greater than the predetermined column size₂Is in the range of 1 to P₂-1 and comprising P₂Integer in the range of-1 and a₂Is P₂Of which is such that i₂(n₂) Becomes a unique number between 1 and the predetermined column size, thereby interleaving the data frame portion.

8. The apparatus of claim 7, wherein the plurality of portions have a predetermined size, wherein the predetermined size is at least 1 bit.

9. The apparatus of claim 7, wherein the processor is an Application Specific Integrated Circuit (ASIC).

10. The apparatus of claim 7, further comprising a deinterleaver, wherein the deinterleaver is based on the permutated sequence i₁(n₁)＝α₁^(n₁)mod(P₁) Deinterleaving the plurality of portions indexed by the plurality of rows.

11. The apparatus of claim 7, further comprising a deinterleaver, wherein the deinterleaver is based on the permutation sequence i₂(n₂)＝α₂^(n₂)mod(P₂) Deinterleaving the plurality of portions indexed by the plurality of columns.

12. The apparatus of claim 1, wherein the means for receiving and storing the data frame comprises a memory configured to receive and store the data frame; and

the means for dividing the data frame includes a processor coupled to the memory for dividing the data frame into the plurality of portions and based on i (n) - αⁿmod (P) generating said permutated sequences of said portions, wherein P is a prime number greater than said predetermined size of said data frame, n is an integer ranging from 1 to P-1 inclusive P-1, and α is the root of P, such that i (n) becomes a unique number between 1 and said predetermined size of said data frame, thereby interleaving said data frame portions.

13. The apparatus of claim 12, wherein the plurality of portions have a predetermined size, the predetermined size being at least one bit.

14. The apparatus of claim 12, wherein the processor is an Application Specific Integrated Circuit (ASIC).

15. The apparatus of claim 12, further comprising a deinterleaver, wherein the deinterleaver deinterleaves the plurality of portions according to the permute sequence.

16. The apparatus of claim 1, further comprising:

means for indexing said data frame with a plurality of rows having a predetermined row size and a plurality of columns having a predetermined column size, wherein the product of said predetermined row size and said predetermined column size is equal to said predetermined size of said data frame;

for according to i₁(n₁)＝α₁^(n₁)mod(P₁) Means for permuting the plurality of portions indexed by the plurality of rows, where P₁Is a prime number larger than the predetermined row size, n₁Is in the range of 1 to P₁-1 and comprising P₁An integer in the range of-1, and a₁Is P₁Of which is such that i₁(n₁) Becomes unique between 1 and the predetermined line sizeCounting; and

according to i₂(n₂)＝α₂^(n₂)mod(P₂) Means for permuting said plurality of portions indexed by said plurality of columns, wherein P₂Is a prime number larger than the predetermined column size, n₂Is in the range of 1 to P₂-1 and comprising P₂Integer in the range of-1 and a₂Is P₂Of which is such that i₂(n₂) Becomes a unique number between 1 and the predetermined column size.

17. The apparatus of claim 16, wherein the plurality of portions have a predetermined size, wherein the predetermined size is at least one bit.

18. The apparatus of claim 16, wherein the means for permuting is implemented using an Application Specific Integrated Circuit (ASIC).

19. The apparatus of claim 16, wherein said means for permuting is implemented using a microprocessor.

20. The apparatus of claim 16, wherein the means for permuting is implemented by using software.

21. The apparatus of claim 16, further comprising means for i according to the permutation sequence₁(n₁)＝α₁^(n₁)mod(P₁) Deinterleaving means for deinterleaving the plurality of portions indexed by the plurality of rows.

22. The apparatus of claim 16, further comprising means for i according to the permutation sequence₂(n₂)＝α₂^(n₂)mod(P₂) Deinterleaving means for deinterleaving the plurality of sections indexed by the plurality of columns.

23. A method for interleaving portions of a data frame having a predetermined size, comprising:

receiving and storing the data frame;

dividing said data frame into said plurality of portions; and

according to i (n) ═ alphaⁿmod (P) permutes the portions, where P is a prime number greater than the predetermined size of the data frame, n is an integer in the range 1 to P-1 and including P-1, and α is the root of P, such that i (n) becomes a unique number between 1 and the predetermined size of the data frame.

24. The method of claim 23, wherein the plurality of portions have a predetermined size, wherein the predetermined size is at least one bit.

25. The method of claim 23, wherein the permuting is accomplished by employing an Application Specific Integrated Circuit (ASIC).

26. The method of claim 23, wherein the permuting is accomplished by using a microprocessor.

27. The method of claim 23, wherein the permuting is accomplished by using software.

28. The method of claim 23, comprising:

indexing the data frame with a plurality of rows having a predetermined row size and a plurality of columns having a predetermined column size, wherein a product of the predetermined row size and the predetermined column size is equal to the predetermined size of the data frame;

according to i₁(n₁)＝α₁^(n₁)mod(P₁) Permuting the plurality of portions indexed by the plurality of rows, whichMiddle P₁Is a prime number greater than a predetermined row size, n₁Is from 1 to P₁-1 and comprising P₁An integer in the range of-1, and a₁Is P₁Of which is such that i₁(n₁) Is a unique number between 1 and the predetermined row size; and

according to i₂(n₂)＝α₂^(n₂)mod(P₂) Permuting the plurality of portions indexed by the plurality of columns, wherein P₂Is a prime number greater than a predetermined row size, n₂Is from 1 to P₂-1 and comprising P₂An integer in the range of-1, and a₂Is P₂Of which is such that i₂(n₂) Is a unique number between 1 and the predetermined column size, thereby interleaving the data frame portion.

29. The method of claim 28, wherein the plurality of portions have a predetermined size, wherein the predetermined size is at least one bit.

30. The method of claim 28, wherein the permuting is implemented by an Application Specific Integrated Circuit (ASIC).

31. The method of claim 28, wherein the permuting is accomplished by a microprocessor.

32. The method of claim 28, wherein the permuting is accomplished by using software.

33. The method of claim 28, further comprising permuting sequence i according to₁(n₁)＝α₁^(n₁)mod(P₁) Deinterleaving the plurality of portions indexed by the plurality of rows.

34. The method of claim 28, wherein the method is performed in a batch processCharacterized in that it further comprises a permutation sequence i₂(n₂)＝α₂^(n₂)mod(P₂) Deinterleaving the plurality of portions indexed by the plurality of columns.