Turbo product code decoder

• US 6,526,538 B1
• Filed: 09/27/1999
• Issued: 02/25/2003
• Est. Priority Date: 09/28/1998
• Status: Expired due to Term

• Current Assignee: Comtech Telecommunications Corporation
• Original Assignee: Comtech Telecommunications Corporation
• Inventors: Hewitt, Eric
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): LAMARRE, GUY J
• Application Number:
  US09/406,252
• Time in Patent Office: 1,247 Days
• Field of Search: 714/752, 714/755, 714/780, 714/783, 714/774, 714/777, 714/782, 714/793, 370/203, 375/346, 375/262, 375/265, 375/263, 375/376, 375/377, 375/332, 375/340, 704/222, 704/242
• US Class Current: 714/780
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2963 Turbo-block codes, i.e. turbo codes based on block codes, e.g. turbo decoding of product codes
• CPC Class Codes: H03M 13/45 Soft decoding, i.e. using symbol reliability information H03M13/41 takes precedence
• CPC Class Codes: H03M 13/618 Shortening and extension of codes
• CPC Class Codes: H03M 13/6586 Modulo/modular normalization, e.g. 2's complement modulo implementations

Abstract

The present invention is a turbo product code decoder capable of decoding multi-dimensional coding schemes. The decoder may be implemented in any digital communication system capable of receiving an encoded stream of data. The decoder is configured for receiving soft decision values. The decoder iteratively decodes the data by generating new soft difference values for each axis-iteration of decoding. These soft difference values represent the change in soft decision values after each axis-iteration. The soft difference values from each axis-iteration are then summed with the original soft decision values in decoding each of the other axis. After any full iteration—i.e. after all axis dimensions have been decoded one full time, the previous difference values for any axis are discarded when that axis is decoded in subsequent iterations. Accordingly, the same information is not continuously fed into the decoder during each subsequent iteration, thereby decreasing the likelihood of error and offering an improvement over prior decoders. Moreover, using unique nearest neighbor computation logic, the decoder of the present invention is able to generate valid nearest neighbors more efficiently without requiring the use of a look-up table, thereby reducing the amount of time required to decode. Finally, the decoder of the present invention utilizes four decoders arranged in parallel along with a unique memory array accessing scheme such that multiple rows or columns may be decoded at the same time, thereby increasing the data throughput time of the decoder over prior turbo product code decoders.

Claims

1. A turbo product code decoder comprising:

a. means for storing a plurality of initial soft decision values, wherein the means for storing includes a predetermined number of memory cells each storing a plurality of initial soft decision values arranged as an array having x-rows and y-columns;

b. means for retrieving and decoding the plurality of initial soft decision values stored in the x-rows, thereby generating a plurality of x-axis iteration values and outputting a plurality of x-axis results, wherein a single x-axis result within the plurality of x-axis results represents a numerical difference between a single initial soft decision value in the plurality of soft decision values and a single x-axis iteration value in the plurality of x-axis iteration values;

c. means for summing the plurality of x-axis results with the plurality of initial soft decision values stored in the y-columns, thereby generating a plurality of y-axis input values; and

d. means for decoding the plurality of y-axis input values, thereby generating a plurality of y-axis iteration values and outputting a plurality of y-axis results, wherein a single y-axis result within the plurality of y-axis results represents a numerical difference between a single y-axis input value in the plurality of y-axis input values and a single y-axis iteration value within the plurality of y-axis iteration values.

2. The turbo product code decoder as claimed in claim 1, further comprising a first means for saving the x-axis results and a second means for saving the y-axis results.

3. The turbo product code decoder as claimed in claim 1, further comprising a means for multiplying each x-axis result within the plurality of x-axis results by an x-axis coefficient before summing the plurality of x-axis results with the plurality of initial soft decision values which are stored in the y-columns.

4. The turbo product code decoder as claimed in claim 1, wherein the predetermined number of memory cells arranged in the x-rows and y-columns are further comprises memory cells arranged into z-columns, and further wherein the plurality of initial soft decision values are stored in the x-rows, the y-columns and the z-columns.

5. The turbo product code decoder as claimed in claim 4, further comprising:

a. means for summing the plurality of x-axis results with the plurality of y-axis results and the plurality of initial soft decision values stored in the z-columns, thereby generating a plurality of z-axis input values; and

b. means for decoding the plurality of z-axis input values, thereby generating a plurality of z-axis iteration values and outputting a plurality of z-axis results, wherein a single z-axis result within the plurality of z-axis results represents a numerical difference between a single z-axis input value within the plurality of z-axis input values and a single z-axis iteration value within the plurality of z-axis iteration values.

6. The turbo product code decoder as claimed in claim 5 further comprising:

a. means for summing the plurality of x-axis results with the plurality of y-axis results, the plurality of z-axis results and the plurality of initial soft decision values stored in the x-rows, y-columns and z-columns, thereby generating a plurality of final decision values; and

b. means for generating a plurality of hard decision bit values, wherein a single bit value within the plurality of hard decision values is represented by a binary “

1”

or a binary “

0”

depending upon a corresponding final decision value within the plurality of final decision values.

7. The turbo product code decoder as claimed in claim 1 further comprising means for terminating iterations of a decoding process upon reaching a predetermined number of iteration cycles.

8. The turbo product code decoder as claimed in claim 1 further comprising means for automatically terminating iterations of a decoding process upon sensing a predetermined condition in the turbo product code decoder.

9. The turbo product code decoder as claimed in claim 8 wherein the predetermined condition is no further modifications to data will occur.

10. The turbo product code decoder as claimed in claim 1 further comprising a transformer for receiving a plurality of x-row values and converting it to a plurality of y-column values and vice versa, wherein the turbo product decoder can selectively operate on rows and columns.

11. The turbo product code decoder as claimed in claim 1 further comprising a transformer for receiving one of row data, column data and z-column data and selectively converting it to a selected one of another data type, wherein the turbo product decoder can selectively operate on rows, columns and z-columns.

12. A turbo block code decoder for receiving an encoded message having a plurality of bits, and outputting a decoded codeword, the turbo block code decoder comprising:

a. means for receiving the encoded message, wherein each bit in the plurality of bits in the encoded message is represented by an initial soft decision value in a plurality of initial soft decision values, the initial soft decision values arranged in a first array and in a second array;

b. means for storing each initial soft decision value in the plurality of initial soft decision values coupled to the means for receiving; and

c. means for iteratively decoding the encoded message coupled to the means for storing, wherein said means for iteratively decoding the encoded message retrieves the plurality of initial soft decision values in the first array and calculates a new soft decision value for each bit in the first array, thereby creating a plurality of new soft decision values, and further wherein the means for iteratively decoding generates a soft difference value for each bit in the first array, thereby creating a plurality of soft difference values, wherein each soft difference value is equal to a numerical difference between the new soft decision value for the bit in the first array and the initial soft decision value for the same bit in the first array, wherein the plurality of soft difference values is combined with the plurality of initial soft decision values in the second array to generate a subsequent soft difference value for each bit in the second array.

13. The turbo block decoder of claim 12, further comprising:

means for multiplying each soft difference value in the plurality of soft difference values in the first array by an x-axis feedback constant.

14. The turbo block decoder of claim 12, wherein the initial soft decision value for each bit in the encoded message is stored in the means for storing in a signed 2'"'"'s complement notation with the absolute value of the 2'"'"'s complement notation representing a confidence value for the bit and the sign of the 2'"'"'s complement notation representing a hard decision bit value for the bit.

15. The turbo block decoder of claim 12, wherein the means for iteratively decoding the encoded message includes:

a. a soft-in/soft-out group having a plurality of soft-in/soft-out decoders arranged in parallel; and

b. a difference memory array for storing the plurality of soft difference values.

16. The turbo block decoder of claim 15, wherein each soft-in/soft-out decoder in the plurality of soft-in/soft-out decoders includes a nearest neighbor computation logic module for generating a plurality of nearest neighbor codewords in the event the soft-in/soft-out decoder generates a hard decision corrected vector, and further wherein each nearest neighbor codeword in the plurality of nearest neighbor codewords has a same number of bits as the plurality of bits in the encoded message and differs from the hard decision corrected vector by a predetermined number of bit positions.

17. The turbo block decoder of claim 16, wherein the predetermined number of bit positions is four and two of the bit positions remain fixed, while the other two bit positions may vary.

18. A turbo block code decoder for receiving an encoded message having a plurality of bits and outputting a decoded codeword comprising:

a. an input module for receiving the encoded message, wherein each bit in the encoded message is represented by an initial soft decision value;

b. an original memory array coupled to the input module for storing the initial soft decision values;

c. a soft-in/soft-out group coupled to the original memory array for receiving the initial soft decision values in a first predetermined axis and decoding the encoded message, wherein the soft-in/soft-out group calculates a new soft decision value for each bit in the first predetermined axis and generates a soft difference value for each bit in the first predetermined axis, and further wherein the soft difference value is equal to a numerical difference between the new soft decision value and the initial soft decision value in the first predetermined axis; and

d. a difference memory array coupled to the soft-in/soft out group for storing the soft difference values, wherein each soft difference value in the difference memory array is combined with the initial soft decision values in a second predetermined axis to generate a new soft difference value for each bit in the second predetermined axis.

19. The turbo block decoder of claim 18, wherein the initial soft decision values are stored in the original memory array in a signed 2'"'"'s complement notation with an absolute value of the 2'"'"'s complement notation representing a confidence value and a sign of the 2'"'"'s complement notation representing a hard decision bit value.

20. The turbo block decoder of claim 18, wherein the soft-in/soft-out group includes a plurality of soft-in/soft-out decoders arranged in parallel, and further wherein the initial soft decision values are arranged into a plurality of blocks with each block being decoded by one of the plurality of soft-in/soft-out decoders in order to generate the soft difference value for each bit in the plurality of blocks.

21. The turbo block decoder of claim 20, wherein each of the plurality of soft-in/soft-out decoders in the soft-in/soft-out group includes a computation logic module for generating a plurality of nearest neighbor codewords, wherein each nearest neighbor codeword in the plurality of nearest neighbor codewords differs from the block being decoded by a predetermined number of bit positions.

22. A method of iteratively decoding a received block of data having a plurality of bits represented by a plurality of initial soft decision values, the method comprising the steps of:

a. storing the plurality of initial soft decision values in a memory array having x-rows and y-columns;

b. decoding the plurality of initial soft decision values stored in the x-rows, thereby creating a plurality of new x-axis soft decision values;

c. generating a plurality of x-axis difference values, wherein said plurality of x-axis difference values represent a numerical difference between the plurality of new x-axis soft decision values and the plurality of initial soft decision values stored in the x-rows;

d. multiplying the plurality of x-axis difference values by an x-axis feedback constant, thereby generating a plurality of x-axis iteration output values, wherein the x-axis feedback constant remains constant for the decoding of the plurality of initial soft decision values stored in the x-rows;

e. summing the plurality of x-axis iteration output values with the plurality of initial soft decision values stored in the y-columns, thereby generating a plurality of y-axis input values;

f. decoding the plurality of y-axis input values, thereby creating a plurality of new y-axis soft decision values;

g. generating a plurality of y-axis difference values, wherein said plurality of y-axis difference values represent a numerical difference between the plurality of new y-axis soft decision values and the plurality of y-axis input values; and

h. multiplying the plurality of y-axis difference values by a y-axis feedback constant, thereby generating a plurality of y-axis iteration output values, wherein the y-axis feedback constant remains constant for the decoding of the plurality of y-axis input values.

23. The method of iteratively decoding as claimed in claim 22, further comprising the additional steps of:

a. summing the plurality of y-axis iteration output values with the plurality of x-axis iteration output values and the plurality of initial soft decision values stored in the x-rows and the y-columns, thereby generating a plurality of final output values; and

b. performing a hard decision operation on the plurality of final output values in order to generate an output codeword having a plurality of bits, wherein each bit is assigned as a binary “

1”

or a binary “

0”

, and further wherein the assignment of each bit as a binary “

1”

or the binary “

0”

is based upon the plurality of final output values.

24. A method of iteratively decoding a received block of data having a plurality of bits represented by a plurality of initial soft decision values, the method comprising the steps of:

a. storing the plurality of initial soft decision values in a memory having x-rows, y-columns and z-columns;

b. decoding the plurality of initial soft decision values stored in the x-rows, thereby creating a plurality of new x-axis soft decision values;

c. generating a plurality of x-axis difference values, wherein said plurality of x-axis difference values represent a numerical difference between the plurality of new x-axis soft decision values and the plurality of initial soft decision values stored in the x-rows;

d. multiplying the plurality of x-axis difference values by an x-axis feedback constant, thereby generating a plurality of x-axis iteration output values;

e. summing the plurality of x-axis iteration output values with the plurality of initial soft decision values stored in the y-columns, thereby generating a plurality of y-axis input values;

f. decoding the plurality of y-axis input values, thereby creating a plurality of new y-axis soft decision values;

g. generating a plurality of y-axis difference values, wherein said plurality of y-axis difference values represent a numerical difference between the plurality of new y-axis soft decision values and the plurality of y-axis input values;

h. multiplying the plurality of y-axis difference values by a y-axis feedback constant, thereby generating a plurality of y-axis iteration output values;

i. summing the plurality of y-axis iteration output values with the plurality of x-axis iteration output values and plurality of initial soft decision values stored in the z-columns, thereby generating a plurality of z-axis input values;

j. decoding the plurality of z-axis input values, thereby creating a plurality of new z-axis soft decision values;

k. generating a plurality of z-axis difference values, wherein said plurality of z-axis difference values represent a numerical difference between the plurality of new z-axis soft decision values and the plurality of z-axis input values; and

l. multiplying the plurality of z-axis difference values by a z-axis feedback constant, thereby generating a plurality of z-axis iteration output values.

25. The method of iteratively decoding as claimed in claim 24, which includes the further steps of:

a. summing the plurality of z-axis iteration output values with the plurality of y-axis iteration output values, and the plurality of x-axis iteration output values thereby generating a plurality of final output values; and

b. performing a hard decision operation on the plurality of final output values in order to generate an output codeword having a plurality of bits, wherein each bit is assigned as a binary “

1”

or a binary “

0”

, and further wherein the assignment of each bit as a binary “

1”

or the binary “

0”

is based upon the plurality of final output values.

26. The method of iteratively decoding a received block of data as in claim 24, wherein the step of decoding the initial x-axis soft decision values is accomplished by:

a. receiving the plurality of initial x-axis soft decision values and generating an x-axis soft decision vector having a number of x-axis confidence elements and an x-axis hard decision vector having a corresponding number of x-axis hard decision elements, wherein the number of x-axis confidence elements and the corresponding number of x-axis hard decision elements is equal to a total number of x-axis soft decision values in the plurality of soft decision values;

b. comparing the x-axis hard decision elements within the x-axis hard decision vector to each nearest neighbor codeword in a group of nearest neighbor codewords; and

c. adjusting the x-axis confidence elements in the x-axis soft decision vector in relation to the results of the comparison.

27. The method of iteratively decoding a received block of data as in claim 26, wherein each nearest neighbor codeword differs from the received block of data by a predetermined number of bits.

28. The method of iteratively decoding a received block of data as in claim 26, wherein the step of comparing the x-axis hard elements within the x-axis hard decision vector includes the further steps of:

a. assigning a difference metric to each nearest neighbor codeword in the group of nearest neighbor codewords based upon the comparison with the x-axis hard decision vector;

b. storing the nearest neighbor codeword having a minimum difference metric;

c. performing an exclusive-or operation between each bit in a center codeword and the corresponding bit in the nearest neighbor codeword with the minimum difference metric, in order to generate a new output codeword;

d. assigning each bit in the new output codeword a soft confidence value based upon a difference between a first difference metric value for the new output codeword as a second difference metric value for the new output codeword with a bit in the mth position inverted; and

e. generating a soft difference value for each bit in the new output codeword by calculating a difference between the soft confidence value assigned to each bit in the new output codeword and the soft decision value assigned to each bit in the same bit position within the block being decoded.

29. A method for decoding a linear block encoded string of information bits comprising the steps of:

a. receiving the linear block encoded string of information bits and converting the string into codewords of length N;

b. performing hard and soft decisions on each codeword in order to generate a hard decision vector h of length N and a soft decision vector c of length N, wherein the soft decision vector represents the reliability of the information in the hard decision vector;

c. computing the syndrome of the hard decision vector h;

d. computing the 1 bit parity of the hard decision vector h;

e. if the syndrome calculation indicates that there is an error in the hard decision vector, correcting the error by inverting the appropriate hard decision bit value in the hard decision vector and 2'"'"'s complementing the soft decision value in the same bit position in the soft decision vector;

f. if the parity was correct and step e. required the hard decision bit value to be inverted, or if the parity was incorrect and step e did not require the hard decision bit value to be inverted, inverting the appropriate hard decision bit value in the hard decision vector and 2'"'"'s complementing the soft decision value for the last bit position in the soft decision vector;

g. finding the location of the two minimum values in the soft decision vector and designating these locations as LOW1 and LOW2, then replacing the soft decision value at location LOW1 with the 2'"'"'s complement of the soft decision value at location LOW2 and replacing the soft decision value at location LOW2 with the 2'"'"'s complement of the soft decision value at location LOW1;

h. finding the sum of the new soft decision values at locations LOW1 and LOW2 in the soft decision vector for later use;

i. computing the set of nearby valid codewords with Hamming weight 4 which have 1'"'"'s in locations LOW1 and LOW2;

for (n, k) codes, this will yield a set of (n/2−

1) codewords with each of these nearby valid codewords having a 1 in locations LOW1 and LOW2 and two other locations which are designated Nc1 and Nc2;

j. finding the sum of the soft decision values in locations Nc1 and Nc2 in the soft decision vector;

k. swapping the soft decision value at location Nc1 with the soft decision value at location Nc2 and repeat steps j and k for each of the nearby valid codewords which were computed in step i;

l. from the sums computed in steps h and j, determining which soft decision value sum is the lowest and designate this as Min1;

m. determining which two bit locations created Min1, and designate these two bit locations as MinA and MinB;

additionally, determine the next lowest soft value sum from steps i and k, and designate this as Min2;

n. replacing the value at bit location MinA in the soft decision vector with the value of Min2 minus the current value at bit location MinA, and replacing the value at bit location MinB in the soft decision vector with the value of Min2 minus the current value at bit location MinB;

o. subtracting the value of Min1 from the values in all other bit locations in the soft decision vector in order to generate an output codeword—

if the locations of Min1 and Min2 are the same as the locations of LOW1 and LOW2 (independent of order), then the output codeword is the center codeword and if the locations Min1 and Min2 are not the same as the locations of LOW1 and LOW2 (independent of order) then invert the hard decision bits in the hard decision vector at locations MinA, MinB, LOW1 and LOW2; and

p. for each bit in the output codeword generating a new signed soft value vector, this accomplished by 2'"'"'s complementing all soft values in the output codeword at bit locations which correspond with bit locations in the hard decision vector having a 0 in their location and creating the new signed soft value vector.

30. The method for decoding a linear block encoded string of information bits as claimed in claim 29, wherein the step of computing the set of nearby valid codewords with Hamming weight 4 which have 1'"'"'s in locations LOW1 and LOW2 includes the steps of:

a. creating a first used location vector U of length N which initially contains all zeros in each bit position;

b. selecting a first fixed bit position and a second fixed bit position and setting each of these bit positions within the first used location vector U to a binary one;

the first used location vector U is then passed into the priority encoder;

c. starting with the bit location U₀ and moving toward the bit location U_N, searching the first used location vector U for a first zero bit location having a binary 0;

d. generating a second used location vector V of length N, with binary ones in the first fixed bit position, the second fixed bit position and the first zero bit location, and binary zeros in every other bit location;

e. performing a Hamming code syndrome computation on the second used location vector V and computing an error bit location of the Hamming code syndrome computation; and

f. generating a nearest neighbor with different bit values from the center codeword in the first fixed bit position, the second fixed bit position, the first zero bit location and the error bit location and the same bit values as the center codeword in all other bit locations.