HK1095673B - Method and system for turbo code - Google Patents

Description

Method and system for turbo encoding

The present application is a divisional application of an invention patent application entitled "block interleaving for turbo coding" filed on 11/1/2000 by the applicant under the application number "00804027.3".

Technical Field

The present invention relates generally to communication systems, and more particularly to interleavers that perform coded modulation.

Background

It has been found that encoding techniques for communication channels, referred to as coded modulation, can improve the bit error rate of electronic communication systems, such as modems, wireless communication systems, and the like. Turbo (Turbo) coded modulation has proven to be a practical, efficient and band-efficient modulation method for "random-error" channels characterized by white gaussian noise (AWGN) or fading. These randomly erroneous channels may be found, for example, in a Code Division Multiple Access (CDMA) environment. The capacity of a CDMA environment depends on the operating signal/noise ratio and thus improving performance, i.e., increasing capacity.

One aspect of such an efficient Turbo encoder (Turbo coder) is an interleaver that permutes the originally received or transmitted data frames before entering the 2 nd encoder. The permutation is done by randomizing portions according to one or more randomization algorithms. Combining the permuted data frames with the original data frames shows that low BERs in AWGN and fading channels can be obtained. The interleaving process increases the diversity in the data so that when the modulation symbols are distorted during transmission, an error correction algorithm can be used in the decoder for recovery.

Conventional interleavers collect and frame signal points to be transmitted into an array, essentially filling the array row by row. After a predetermined number of signal points have been framed, the interleaver is essentially emptied by reading out the columns of the array for transmission. As a result, signal points in the same row of the array that are adjacent to each other in the original signal point stream are separated by a number of signal points equal to the number of rows in the array. Ideally, the number of columns and rows is chosen such that interdependent signal points are spaced longer after transmission than the expected channel error burst.

Non-uniform interleaving may achieve "maximum spreading" of data and "maximum disorder" of the output sequence. Thus, the redundancy introduced by the two convolutional encoders is more equally spread in the output sequence of the Turbo encoder. The minimum distance is increased to a value greater than that of the uniform interleaving. An inherent problem with non-uniform interleaving is how to actually implement interleaving while achieving sufficient "non-uniformity" and minimizing delay compensation, which limits the application of real-time requirements.

Finding a valid interleaver is a popular topic in 3 rd generation CDMA standard activities. It has been determined and generally accepted that the most efficient interleaver is a random interleaver when the frame size approaches infinity. However, for limited frame sizes, the determination of the most efficient interleaver is still under discussion.

Therefore, there is a need for a system and method of interleaving codes that improves non-uniformity for limited frame sizes.

There is also a need for a system and method of interleaving codes that is relatively simple to implement.

It is therefore an object of the present invention to provide a system and method for interleaving codes that improves non-uniformity for limited frame sizes.

It is a further object of this invention to provide such a system and method of interleaving codes that is relatively simple to implement.

The above and other objects will be apparent to those skilled in the art from the following description.

Disclosure of Invention

The above and other objects are accomplished by the present invention, wherein a data frame is interleaved, the data frame having a predetermined size and being composed of a plurality of parts. One embodiment of the present invention includes storing a data frame and utilizing N₁×N₂The method for indexing the data frame by the index array I, wherein N₁And N₂The product of (d) is at least equal to N. The elements in the index array indicate elements in the data frameThe position of the element. The data frame elements may be stored in any conventional manner without being organized into an array. The method further comprises obtaining a signal according to I (j, k) ═ I (j, (α)_jk+β_j) modP) permutes the array of indices where I is an array of indices, as described above, j and k are indices of rows and columns in the array of indices, respectively, α and β are constant sets selected according to the current row, and P and each α_jAre relatively prime numbers. The data frame, indexed by the permuted exponent array I, is effectively permuted.

Yet another embodiment of the present invention encompasses an interleaver that includes storing a data frame and storing N₁×N₂Storage means for an index array I, wherein N₁And N₂The product of (d) is at least equal to N. The elements in the index array indicate the location of the elements in the data frame. The data frame elements may be stored in any conventional manner without being organized into an array. The interleaver further comprises a plurality of interleaver units arranged according to I (j, k) ═ I (j, (o)_jk+β_j) modP) where I is an index array, j and k are indices of rows and columns in the index array, respectively, as described above, α and β are constant sets selected according to the current row, and P and each α are constant sets_jAre relatively prime numbers. The data frame, indexed by the permuted exponent array I, is effectively permuted.

A further embodiment of the present invention provides an interleaver for interleaving elements of a data frame, the interleaver comprising: an input memory storing a data frame comprising a plurality of elements as an array D having a plurality of data elements as 0, 1₁-1 of N₁A row; and as 0, 1.. cndot.N₂-1 of N₂Column (i) wherein N₁And N₂Is a positive integer greater than 1; coupled to said input memory and replacing array D by array D according to the following equation₁Processor D of₁(j，k)＝D(j，(α_jk+β_j) modP) where j is through arrays D and D₁An index of the row; k is through the arrays D and D₁The indices of the columns; alpha is alpha_jAnd beta_jIs an integer predetermined for each row j; p is at least equal to N₂An integer of (d); and eachα_jIs a relative prime number with respect to P, and is coupled to the processor and configured to store the permutation array D₁The working memory of (2).

Yet a further embodiment of the present invention provides an interleaver that interleaves elements in a data frame, the interleaver comprising: a memory storing an index array I having a value of 0, 1.. N₁N of-1₁A row; and as 0, 1.. cndot.N₂N of-1₂Column (i) wherein N₁And N₂Is a positive integer greater than 1, and the memory is further configured to store received data frame elements in respective ones of a plurality of memory locations; a processor coupled to the memory for storing values indicative of respective memory locations of frame elements at successive positions row by row in array I; and the processor further replaces the I array with I according to the following equation₁Array: i (j, k) is I (j, (α)_jk+β_j) modP) where j is through arrays I and I₁The index of the row(s); k is through arrays I and I₁The index of the column (c); alpha is alpha_jAnd beta_jIs a predetermined integer for each row j; p is at least equal to N₂An integer of (d); and each alpha_jIs a relative prime number with respect to P, thus, according to array I₁The indexed data frames can be effectively permuted.

The invention will now be described in connection with certain illustrated embodiments and practices. It will be apparent to those skilled in the art that various modifications, additions and deletions can be made therein without departing from the spirit of the invention or the scope of the appended claims.

Drawings

The invention will be clearly understood from the following detailed description of an embodiment thereof, taken in conjunction with the accompanying drawings, in which:

FIG. 1 shows an illustrative diagram of a conventional Turbo encoder;

FIG. 2 shows a block diagram of the interleaver shown in FIG. 1;

FIG. 3 illustrates an array containing data frames and permutations of the array;

FIG. 4 illustrates data frames stored in successive storage units;

fig. 5 shows an index array and a permutation of the index array that indexes the data frame shown in fig. 4.

Detailed Description

Fig. 1 illustrates a conventional Turbo encoder. As shown, the conventional Turbo encoder includes two encoders 20 and one interleaver 100. The interleaver 100 of the present invention receives an incoming data frame 110, the size of the frame 110 being N, where N is the number of bits, bytes, or other portions into which the frame may be partitioned, referred to as frame elements. The interleaver 100 divides the N frame elements into groups of data like rows. The interleaver then rearranges the data in the groups in a pseudo-random manner. The interleaver 100 may rearrange the data groups of different groups using different methods. However, those skilled in the art will recognize that one or more of the methods may be reused for one or more data sets without departing from the scope of the present invention. After permuting the data in each group, the interleaver outputs the data in a different order than it was received.

Interleaver 100 may be at N₁×N₂Storing frames of data in arrays of a size such that N₁×N₂N. The example shown in FIG. 3 shows a row having 3 (N)₁3)6 columns (N)₂6) is used to store a data frame 110 having 18 elements, denoted as frame elements 00(FE00) through FE17 (N18). Although this is the preferred method, the array can be designed to be N₁×N₂Is part of N such that one or more smaller arrays operate in accordance with the invention and the results of each smaller array are combined later.

The permutation of array 350 according to the present invention is performed separately for each row j of array 350, and the column k in each row is permuted according to the following equation.

D(j，k)＝D(j，(α_jk+β_j)modP)

Wherein:

j and k are indices of rows and columns, respectively, in array 350;

p is greater than or equal to N₂The number of (1);

α_jand P is a relative prime number (1 or both may be non-prime, but their common divisor is only 1);

β_jis a constant with 1 value associated with each row.

Once the data for all rows is replaced, the new array is read out column by column. Also, once the rows have been permuted, the data grouped by columns can be permuted before outputting the data. Where both rows and columns are permuted, the rows, columns, or both may be permuted in accordance with the invention. For example, a row in the array may also be transposed by transposing bits that represent the row index j in binary. (e.g., in a 4-row array, rows 2 and 3 would be transposed according to this scheme.) rows or columns may also be permuted according to a different permutation method, but not both. Those skilled in the art will appreciate that the system may be rearranged to store data column by column, permute the sets of data column by column, and read the results row by row without departing from the scope of the invention.

These interleaving methods are based on number theory and may be implemented in software and/or hardware (i.e., Application Specific Integrated Circuits (ASICs), Programmable Logic Arrays (PLAs), or any other suitable logic devices). Also, a single pseudo-random sequence generator (i.e., M-sequence, Gold sequence, Kasami sequence, etc.) may be used as the interleaver.

In the example shown in fig. 3, P is selected to be 6, the alpha value is 5 for all 3 rows, and the beta value is 1, 2, and 3 for 3 rows, respectively. (these are merely examples. other numbers are chosen to obtain different permutation results.) the values of α (5), each relative prime to P (6) as specified above.

Replacing Row 0 in array D350 by array D by computing a prescribed equation with a prescribed value₁The process for row 0 in 360 is as follows:

D₁(0，0)＝D(0，(5*0+1)mod6)＝D(0，(1)mod6)＝D(0，1)＝FE01

D₁(0，1)＝D(0，(5*1+1)mod6)＝D(0，(6)mod6)＝D(0，0)＝FE00

D₁(0，2)＝D(0，(5*2+1)mod6)＝D(0，(11)mod6)＝D(0，5)＝FE05

D₁(0，3)＝D(0，(5*3+1)mod6)＝D(0，(16)mod6)＝D(0，4)＝FE

D₁(0，4)＝D(0，(5*4+1)mod6)＝D(0，(21)mod6)＝D(0，3)＝FE03

D₁(0，5)＝D(0，(5*5+1)mod6)＝D(0，(26)mod6)＝D(0，2)＝FE02

then row 0 becomes: FE01 FE00 FE05 FE04 FE03 FE02

For row 1, the equation becomes:

D₁(1，0)＝D(1，(5*0+2)mod6)＝D(1，(2)mod6)＝D(1，2)＝FE08

D₁(1，1)＝D(1，(5*1+2)mod6)＝D(1，(7)mod6)＝D(1，1)＝FE07

D₁(1，2)＝D(1，(5*2+2)mod6)＝D(1，(12)mod6)＝D(1，0)＝FE06

D₁(1，3)＝D(1，(5*3+2)mod6)＝D(1，(17)mod6)＝D(1，5)＝FE11

D₁(1，4)＝D(1，(5*4+2)mod6)＝D(1，(22)mod6)＝D(1，4)＝FE10

D₁(1，5)＝D(1，(5*5+2)mod6)＝D(1，(27)mod6)＝D(0，3)＝FE09

row 1 then becomes: FE08 FE06 FE11 FE10 FE09

For row 2, the equation becomes:

D₁(2，0)＝D(2，(5*0+3)mod6)＝D(2，(3)mod6)＝D(2，3)＝FE15

D₁(2，1)＝D(2，(5*1+3)mod6)＝D(2，(8)mod6)＝D(2，2)＝FE14

D₁(2，2)＝D(2，(5*2+3)mod6)＝D(2，(13)mod6)＝D(2，1)＝FE13

D₁(2，3)＝D(2，(5*3+3)mod6)＝D(2，(18)mod6)＝D(2，0)＝FE12

D₁(2，4)＝D(2，(5*4+3)mod6)＝D(2，(23)mod6)＝D(2，5)＝FE17

D₁(2，5)＝D(2，(5*5+3)mod6)＝D(2，(28)mod6)＝D(0，4)＝FE16

row 2 then becomes: FE15 FE14 FE13 FE12 FE17 FE16

And the permuted data frame is contained in the array D of fig. 3₁360. A column-by-column output array will output the frame elements in the following order:

1，8，15，0，7，14，5，6，13，4，11，12，3，10，17，2，9，16。

in an alternative embodiment of the invention, the data frame 110 is stored not in an array or matrix but in a contiguous memory location and a separate index array is stored for indexing the elements of the data frame, the index array is permuted according to the equations of the invention, and the data frame is output after being indexed by the permuted index array.

Fig. 4 illustrates a block diagram storing 32 elements in length (thus having offsets 0 to 31 from the starting memory location). Data frame 110, which in this example is taken to be 22 elements long and thus contains elements FE00 through FE21, occupies offset storage locations 00 through 21 in block 400. The offset storage locations 22 through 31 in block 400 contain unknown content. The 22 element frame length is only an example and other lengths may be chosen. Storing the frame elements in contiguous memory locations is an example, and non-contiguous memory locations may also be used.

FIG. 5 illustrates an exponent array I550 for indexing the memory block 400. 4 rows (N) each having 8 columns₁＝4，N₂＝8，N＝N₁×N₂32). Next, as shown in FIG. 5, the original content is filled into array I550. This initialization produces the same effect as reading in the data frame 110 row by row.

The array of indices is permuted according to the following equation:

I₁(j，k)＝I(j，(α_jk+β_j)modP)

wherein α is 1, 3, 5, 7

β＝0，0，0，0

P＝8

These numbers are examples, and other numbers may be selected as long as the specification is satisfied: p is at least equal to N₂And each value of alpha is a relative prime number with respect to the selected P value.

For example, if the equation is applied to the column of row 2, then:

I₁(2，0)＝I(2，(5*0)mod8)＝I(2，(0)mod8)＝I(2，0)＝16

I₁(2，1)＝I(2，(5*1)mod8)＝I(2，(5)mod8)＝I(2，5)＝21

I₁(2，2)＝I(2，(5*2)mod8)＝I(2，(10)mod8)＝I(2，2)＝18

I₁(2，3)＝I(2，(5*3)mod8)＝I(2，(15)mod8)＝I(2，7)＝23

I₁(2，4)＝I(2，(5*4)mod8)＝I(2，(20)mod8)＝I(2，4)＝20

I₁(2，5)＝I(2，(5*5)mod8)＝I(2，(25)mod8)＝I(2，1)＝17

I₁(2，6)＝I(2，(5*6)mod8)＝I(2，(30)mod8)＝I(2，6)＝22

I₁(2，7)＝I(2，(5*7)mod8)＝I(2，(35)mod8)＝I(2，3)＝19

applying the equations identically to rows 0, 1 and 3 results in the permuted index array I shown in FIG. 5₁560。

The data frame 110 is read from the memory frame 400 and the permuted index array I is fetched column by column₁The memory cell is output in the order specified in (1), thereby outputting the memory cells in the following offset order:

0，8，16，24，1，11，21，31，2，14，18，30，3，9，23，29，4，12，20，28，5，15，17，27，6，10，22，26，7，13，19，25。

however, this example assumes that the frame length is 22 elements of the offset storage locations 22-31 in the box 400, and not part of the data frame. Thus, when a data frame is output, it is punctured or clipped to length 22; i.e., offset memory cells greater than 21 are ignored. The data frame is then output in the following order of elements:

0，8，16，1，11，21，2，14，18，3，9，4，12，20，5，15，17，6，10，7，13，19。

in one aspect of the invention, the rows of the array are transposed, e.g., by inverting the bits of the binary representation row index j and prior to output.

The interleaver 100 of the present invention can be implemented in a number of different ways. Fig. 2 shows an embodiment of the invention in which the interleaver 100 comprises an input memory 300 for receiving and storing the data frame 110. The memory 300 may include a shift register, a RAM, and the like. The interleaver 100 may also include a working memory 310, and the memory 310 may also include a RAM, a shift register, and the like. The interleaver includes a processor 320 (e.g., microprocessor, ASIC, etc.) configured to process I (J, K) in real time according to the above equation or access a table containing the I (J, K) results pre-stored therein. Those skilled in the art will appreciate that memories 300 and 310 may be the same or separate memories.

To determine I (j, k) in real time, line 1 in the permutation index array and store the byte corresponding to the permutation index in the working memory. The next row is then permuted and stored, and so on, until all rows have been permuted and stored. This row permutation may be done sequentially or in parallel.

Whether in real time or by looking up a table to determine the displaced I (j, k), the data can be stored in the workpiece memory in a number of different ways. Data may be stored by selecting data from the input memory in the same order as I (j, k) in the permuted exponent array (i.e., the input memory is indexed by the permutation function) and storing them in the working memory in the order in which the memory cells are available. Storage may also be performed by selecting bytes in the order they are stored in the input memory (i.e., FIF0) and storing them directly into the working memory in locations determined by the permuted I (j, k) (i.e., the working memory is indexed by the permutation function). Once this is done, the data can be read out from the working memory column by column according to the permuted index array. As described above, after the data is stored in the working memory according to columns instead of rows, the data may undergo another round of permutation to obtain different results.

If the system is fast enough, one memory may be omitted and the data elements may be received in real time or by table lookup into working memory in an order corresponding to the permuted index array.

The disclosed interleaver is compatible with existing Turbo code structures. These interleavers exhibit superior performance without increasing the complexity of the system.

Further, as will be appreciated by those skilled in the art, a deinterleaver may be used to decode the interleaved frame. The structure of de-interleaver for decoding Turbo code belongs to the prior art. And as such will not be discussed here. However, the deinterleaver of the corresponding embodiment may be configured with the permutated sequence described above.

Although the above-described embodiment is a Turbo encoder as found in a CDMA system, it should be appreciated by those skilled in the art that the present invention is not so limited and can be implemented for any type of interleaving and deinterleaving in any communication system.

The invention thus effectively achieves the objects stated above, including variations which will be apparent from the foregoing description. In effect, the present invention provides an improved apparatus and method for interleaving finite length codes while minimizing the complexity of implementation.

It will be appreciated that various changes can be made in the above constructions and in the foregoing operational sequences without departing from the scope of the invention. Accordingly, it is intended that all matter contained in the above description and shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

It is also to be understood that the following 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 (8)

1. A method for interleaving elements of a signal data communication channel frame, comprising the steps of:

storing a frame of signal data comprising a plurality of elements as an array D having

Is marked as 0, 1₁-1 of N₁A row; and

is marked as 0, 1₂-1 of N₂The columns of the image data are,

wherein N is₁And N₂Is a positive integer greater than 1; and

according to the followingThe equation replaces array D with array D₁

D₁(j，k)＝D(j，(α_jk+β_j)modP)

Where j is the arrays D and D₁The row number of (c);

k is arrays D and D₁The column number of (a);

α_jand beta_jIs an integer predetermined for each row j;

p is greater than or equal to N₂An integer of (d); and

each alpha_jIs a relative prime number with respect to P, where a relative prime number represents a group of numbers without common divisor other than 1.

2. The method of claim 1, wherein the elements of array D are stored in a first order and array D is stored in a second order₁Is output in a second order.

3. The method of claim 2, wherein elements of array D are stored row by row, and array D is stored row by row₁The elements of (a) are output column by column.

4. The method of claim 1, further comprising outputting an array D₁Wherein N is₁And N₂Is greater than the number of elements in the frame, the frame is truncated to the number of elements in the frame during output.

5. An interleaver for interleaving elements of a data frame, comprising:

storage device for storing a data frame comprising a plurality of elements as an array D having

Is marked as 0, 1₁-1 of N₁A row; and

is marked as 0, 1₂-1 of N₂The columns of the image data are,

wherein N is₁And N₂Is a positive integer greater than 1; and

array D is replaced by array D according to the following equation₁Replacement device

D₁(j，k)＝D(j，(α_jk+β_j)modP)

Where j is the arrays D and D₁The row number of (c);

k is arrays D and D₁The column number of (a);

α_jand beta_jIs an integer predetermined for each row j;

p is greater than or equal to N₂An integer of (d); and

each alpha_jIs a relative prime number with respect to P, where a relative prime number represents a group of numbers without common divisor other than 1.

6. The interleaver of claim 5 further comprising means for storing the elements of array D in a first order and outputting array D in a second order₁The device of said element.

7. The interleaver of claim 6 wherein said means for storing said elements of array D are stored row by row, and said output array D is₁The elements of (1) are output column by column.

8. The interleaver of claim 5, further comprising outputting the array D₁And when N is₁And N₂Is greater than the number of elements in the frame₁Means for truncating to the number of elements in the frame.