Method and coding means for error-correction utilizing concatenated parity and turbo codes

• US 20020147954A1
• Filed: 03/20/2002
• Published: 10/10/2002
• Est. Priority Date: 03/22/2001
• Status: Active Grant

• Current Assignee: University of Florida (State University System of Florida)
• Original Assignee: University of Florida (State University System of Florida)
• Inventors: Shea, John M.
• Granted Patent: US 7,093,179 B2
• Time in Patent Office: Days
• US Class Current: 714/755
• CPC Class Codes: H03M 13/098 using single parity bit
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/2721 the interleaver involves a diagonal direction, e.g. by using an interleaving matrix with read-out in a diagonal direction
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/2966 Turbo codes concatenated with another code, e.g. an outer block code
• CPC Class Codes: H03M 13/2975 Judging correct decoding, e.g. iteration stopping criteria
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• CPC Class Codes: H03M 13/6362 by puncturing
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0065 Serial concatenated codes
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes

Abstract

A method and apparatus for encoding and decoding data using an overall code comprising an outer parity-check and an inner parallel concatenated convolutional, or turbo code. The overall code provides error probabilities that are significantly lower than can be achieved by using turbo codes alone. The output of the inner code can be punctured to maintain the same turbo code rate as the turbo code encoding without the outer code. Multiple parity-check codes can be concatanated either serially or in parallel as outer codes. Decoding can be performed with iterative a posteriori probability (APP) decoders or with other decoders, depending on the requirements of the system. The parity-check code can be applied to a subset of the bits to achieve unequal error protection. Moreover, the techniques presented can be mapped to higher order modulation schemes to achieve improved power and bandwidth efficiency.

Claims

1. A method of error-correction for encoding a block of digital data by serially concatenating at least two error correcting codes, comprising:

a. encoding a block of digital information bits using a concatenated parity-check code as an outer code to generate parity bits;

b. multiplexing the parity bits with the information bits to create a product code;

c. encoding the product code using a turbo code encoder as an inner code; and

d. outputting a serially concatenated encoded data block.

2. The method of claim 1, wherein encoding a block of digital information bits using concatenated parity-check code further comprises encoding the block of digital data using a plurality of parity-check encoders operating in parallel, wherein each input to the parity-check encoder is separated from every other input of each parity-check encoder by a parity-check permuter.

3. The method of claim 2, wherein said parity-check permuter is pseudorandom.

4. The method of claim 2, wherein said parity-check permuter is deterministic.

5. The method of claim 1, wherein encoding a block of digital information bits using a concatenated parity-check code further comprises encoding the block of digital data using a plurality of parity-check encoders operating in series.

6. The method of claim 1, wherein the parity-check code is a rectangular parity-check code.

7. The method of claim 1, wherein the parity-check code is a multidimensional parity-check code.

8. The method of claim 1, wherein the product code is further permuted before being encoding by the turbo code.

9. The method of claim 1, wherein outputting a serially concatenated encoded data block further comprises permuting the encoded data block.

10. The method of claim 1, wherein outputting a serially concatenated encoded date block further comprises puncturing the encoded data block.

11. A method of permuting data between an outer rectangular parity-check code and an inner code for error correction to enhance the performance of an error correcting code by preventing entries in a permuted first rectangular array from ending up in the same row or column of a second array after permutation comprising:

a. placing information bits from a block of digital data into a first rectangular array;

b. creating a second rectangular array having the same number of rows and columns as said first array;

c. reading information bits from said first rectangular array along a diagonal and placing the information bits in a row or column of said second rectangular array;

d. selecting a new diagonal in said first rectangular array and a new starting position in said second rectangular array so that no information bits that are in the same row or column of said first rectangular array are placed in the same row or column of said second rectangular array;

e. if it is not possible to ensure that no information bits from said first rectangular array can be placed in a different row or column of said second rectangular array, then selecting a new diagonal in said first rectangular array and a new starting position in said second rectangular array so that the distance between the bit positions in said second rectangular array is maximized for bits that were in the same row or column in said first rectangular array; and

f. repeating steps c. through e. until all of the information bits from said first rectangular array are placed in said second rectangular array.

14. The method of claim 13, wherein the soft decision turbo decoder is an a posteriori probability (APP), Maximum a posteriori (MAP), Bahl-Cocke-Jelinek-Raviv (BCJR), log-MAP, log-max, or Viterbi soft decision turbo decoder.

15. The method of claim 13, wherein the soft decision parity-check decoder is an APP, MAP, BCJR, log-MAP, log-max, or Viterbi soft decision parity-check decoder.

16. The method of claim 13, wherein the soft decision parity-check decoder is a sub-optimal decoder comprising the use of minimums and second minimums.

17. The method of claim 13, wherein the iterative decoding of the serially concatenated parity-check and turbo code is stopped by making a hard decision in the parity-check decoder when no parity errors are detected.

19. The method of claim 18, wherein the soft decision turbo decoder is an APP, MAP, BCJR, log-MAP, log-max, or Viterbi soft decision turbo decoder.

20. The method of claim 18, wherein the soft decision parity-check decoder is an APP, MAP, BCJR, log-MAP, log-max, or Viterbi soft decision parity-check decoder.

21. The method of claim 18, wherein the soft decision parity-check decoder is a sub-optimal decoder comprising the use of minimums and second minimums.

12. A method of permuting data between an outer rectangular parity-check code and an inner code for error correction to enhance the performance of the error correcting code by preventing entries in a permuted first square array from ending up in the same row or column of a second square array after permutation comprising:

a. placing information bits from a block of digital data into a first square array;

b. creating a second square array having the same number of rows and columns as said first array;

c. establishing a first variable for storing a row position of an element in an array, establishing a second variable for storing a column position of an element in an array, establishing a first counter for storing values used in performing iterations, setting the first counter to a first initial value, establishing a first terminal counter value equal to the dimension of the first square array, and if the first counter value is not equal to said first terminal value, then iteratively performing the following steps c1 through c4;

(c-1) establishing a second counter for storing values used in performing iterations, setting the second counter to a second initial value, establishing a second terminal counter value equal to the dimension of the first square array, and if the second counter value is not equal to said second terminal value, then iteratively performing the following steps c1a through c1d;

(c-1-a) putting the current first array element into the current second array element location;

(c-1-b) computing a new first variable by incrementing the current first variable by 1, modulus dimension of the first square array;

(c-1-c) computing a new second variable by incrementing the current second variable by 1, modulus dimension of the first square array;

(c-1 -d) incrementing the second counter;

(c-2) computing a new first variable by incrementing the current first variable by 2, modulus dimension of the first square array;

(c-3) computing a new second variable by incrementing the current second variable by 1, modulus dimension of the first square array;

(c-4) incrementing the first counter; and

d. outputting a second array of shuffled elements.

13. A method of error correction decoding of serially concatenated error correcting codes using an overall iterative decoding process wherein a parity-check decoder and a turbo code decoder iteratively exchange soft decision information using soft decision feedback, comprising:

a. receiving soft inputs for the serially concatenated error correcting encoded data bits at a turbo-code decoder and outputting, using soft decision techniques, turbo decoded extrinsic information to a turbo-decoded extrinsic-information permuter and an adder;

b. permuting the turbo decoded extrinsic information and forwarding the permuted turbo decoded extrinsic information to a parity-check decoder;

c. permuting the soft inputs for the systematic bits and forwarding the soft inputs for the systematic bits to a parity-check decoder;

d. receiving the permuted turbo decoded extrinsic information and permuted soft inputs for the systematic bits at the parity-check decoder;

e. generating parity-check decoder extrinsic information using soft-decision techniques for iterative feedback to the turbo code decoder;

f. inverse permuting the parity-check decoder extrinsic information and sending the inverse permuted parity-check decoder extrinsic information to the turbo code decoder and the adder;

g. receiving and adding the soft inputs for the systematic bits, the turbo decoded extrinsic information, and the parity-check decoder extrinsic information at the adder and generating a set of decoder soft outputs;

h. receiving the adder decoder bits at a hard decision decoder and generating decoded data bits.

18. A method of error correction decoding of serially concatenated error-correcting codes using a non-iterative decoding process between an internally iterating turbo code decoder and a parity-check decoder comprising:

a. receiving serially concatenated error correcting encoded data bits at a turbo code decoder,

b. iteratively decoding the serially concatenated error correcting encoded data bit using soft decision techniques,

c. outputting the turbo decoded soft decision information to a permuter;

d. permuting the turbo decoded soft decision information and forwarding the permuted turbo decoded soft decision information to a parity-check decoder;

e. receiving and decoding the permuted turbo decoded soft decision information at a parity-check decoder; and

f. generating decoded information bits.

22. The method for decoding concatenated parity-check code and an internally iterating turbo codes passing soft decision information to the parity-check code, wherein the parity-check decoder is a simple decoder comprising:

a. receiving hard-decision values for information bits from a turbo code decoder;

b. receiving soft-decision values for information bits from a turbo code decoder;

c. receiving a first horizontal parity bit vector and a first vertical parity bit vector from the turbo code decoder;

d. placing the hard decision values for the received information bits into a rectangular parity-check array;

e. calculating a second horizontal parity bit vector and a second vertical parity bit vector based on the hard decision values in the first rectangular array;

f. adding, using modulo two arithmetic, the calculated second horizontal parity bit vector and the second vertical parity bit vector with the first horizontal hard decision value vector and first vertical hard decision value vector and placing the results in a third horizontal parity bit vector and a third vertical parity bit vector;

wherein the resulting parity bits are binary value 1 for any row or column in the first array containing an odd number of errors, and the resulting parity bits are binary value 0 for any row or column in the first array containing no errors or an even number of errors;

g. computing the number of binary value 1'"'"'s in the third vertical parity bit vector, and computing the number of binary value 1'"'"'s in the third horizontal parity vector;

h. estimating the positions of symbols output from the turbo code decoder that are in error by examining the soft-decision values in the rows and columns of the rectangular parity-check array according to the parity bits computed in the third vertical parity bit vector and the third horizontal parity bit;

i. correcting the positions of symbols output from the turbo code decoder that are in error; and

j. generating decoded information bits.

23. The method according to claim 22, wherein the step of estimating the positions of symbols output from the turbo code decoder that are in error further comprises:

a. comparing the number of binary value 1'"'"'s in the vertical column vector computed for all the rows of the with the number of binary value 1'"'"'s computed in the horizontal row vector for all the columns in the second array;

b. if the number of binary value 1'"'"'s computed for all the rows of the rectangular parity-check array is equal to the number of binary value 1'"'"'s computed for all the columns in the rectangular parity-check array, establishing a first counter for storing values used in performing iterations, setting the first counter to an initial value, establishing a first terminal counter value equal to the number of rows in the rectangular parity-check array, and if the first counter value is not equal to said terminal value, then iteratively performing the following steps b1 through b3;

(b-1) if the current row has a parity error indicated in the third vertical parity bit vector, finding the minimum soft-decision value from all of the columns of the rectangular parity-check array that have a parity error indicated by a binary 1 in the associated horizontal parity bit vector;

(b-2) changing the hard decision value for the minimum soft decision value to the opposite value;

(b-3) incrementing the counter;

c. else if the number of binary value 1'"'"'s computed for all the rows of the rectangular parity-check array is greater than the number of binary value 1'"'"'s computed for all the columns in the rectangular parity-check array, establishing a second counter for storing values used in performing iterations, setting the second counter to an initial value, establishing second terminal counter value equal to the number of rows in the rectangular parity-check array, and if the second counter value is not equal to said terminal value, then iteratively performing the following steps c1 through c3;

(c-1) if the current row has a parity error indicated in the third vertical parity bit vector, finding the minimum soft decision value from all of the rows of the rectangular parity-check array that have a parity error indicated by a binary 1 in the associated vertical parity bit vector;

(c-2) changing the hard decision value for the minimum soft decision value to the opposite value;

(c-3) incrementing the counter;

d. else establishing a third counter for storing values used in performing iterations, setting the third counter to an initial value, establishing third terminal counter value equal to the number of columns in the rectangular parity-check array, and if the third counter value is not equal to said terminal value, then iteratively performing the following steps d1 through d3;

(d-1) if the current column has a parity error indicated in the third vertical parity bit vector, finding the minimum soft decision value from all of the columns of the rectangular parity-check array that have a parity error indicated by a binary 1 in the associated horizontal parity bit vector;

(d-2) changing the hard decision value for the minimum soft-decision value to the opposite value; and

(d-3) incrementing the counter.

24. The method of claim 22, wherein the rectangular array is square.

26. The method of claim 25, wherein a subset of the information bits are repeated at the input to the parity-check encoder or turbo encoder and a subset of the information bits outputted by the turbo encoder are punctured.

29. The apparatus of claim 28, wherein the parity-check encoder for encoding the block of digital data further comprises a plurality of parity-check encoders operating in parallel, wherein each input to the parity-check encoder is separated from every other input of each parity-check encoder by a parity-check permuter.

30. The apparatus of claim 28 wherein said parity-check permuter is pseudorandom.

31. The apparatus of claim 28, wherein said parity-check permuter is deterministic.

32. The apparatus of claim 28, wherein the parity-check encoder for encoding a block of digital information bits further comprises a plurality of parity-check encoders operating in series.

33. The apparatus of claim 28, wherein the parity-check code is a rectangular parity-check code.

34. The apparatus of claim 28, wherein the parity-check code is a multidimensional parity-check code.

35. The apparatus of claim 28, further comprising a permuter to permute the product code before the product code is encoded by the turbo encoder.

36. The apparatus of claim 28, further comprising a permuter to interleave the serially concatenated encoded data block before the encoded data block is transmitted over a communication channel.

37. The apparatus of claim 28, further comprising a puncturer to puncture a serially concatenated encoded date block before the encoded data block is transmitted over a communication channel.

25. A method of error correction encoding using a concatenated turbo coder and parity-check coder, wherein the parity-check encoder encodes a subset of the information bits encoded by the corresponding turbo code encoder.

27. A method of error correction for encoding a block of digital data using at least two error correcting codes operating in parallel comprising:

a. encoding a block of digital information bits and generating parity bits using a parity-check encoder;

b. encoding the block of digital information bits in parallel with the parity-check encoder using a turbo encoder;

c. outputting a turbo code encoded data block;

d. detecting errors in the outputted turbo code encoded data block;

e. if errors are detected in the outputted turbo code encoded data block;

i. generating a negative acknowledgement signal to the parity-check encoder; and

ii. outputting the parity bits generated for the block of digital information bits by the parity-check encoder in response to the negative acknowledgement signal.

28. An apparatus for error correction encoding a block of digital data by serially concatenating at least two error correcting codes, comprising:

a. an outer-code parity-check encoder for encoding a block of digital information bits to generate parity bits;

b. a multiplexer for multiplexing the parity bits output from the parity-check encoder with the information bits to create a product code; and

c. an inner code turbo code encoder for encoding the product code and outputting a serially concatenated encoded data block.

38. An apparatus for permuting data between an outer rectangular parity-check code and an inner code for error correction to enhance the performance of an error correcting code by preventing entries in a permuted first rectangular array from ending up in the same row or column of a second array after permutation comprising:

a. means for placing information bits from a block of digital data into a first rectangular array;

b. means for creating a second rectangular array having the same number of rows and columns as said first array;

c. means for reading information bits from said first rectangular array along a diagonal and placing the information bits in a row or column of said second rectangular array;

d. means for selecting a new diagonal in said first rectangular array and a new starting position in said second rectangular array so that no information bits that are in the same row or column of said first rectangular array are placed in the same row or column of said second rectangular array;

e. means for determining if it is not possible to ensure that no information bits from said first rectangular array can be placed in a different row or column of said second rectangular array, then selecting a new diagonal in said first rectangular array and a new starting position in said second rectangular array so that the distance between the bit positions in said second rectangular array is maximized for bits that were in the same row or column in said first rectangular array; and

f. an iteration element capable of repeating steps c. through e. until all of the information bits from said first rectangular array are placed in said second rectangular array.

39. An apparatus for permuting data between an outer rectangular parity-check code and an inner code for error correction to enhance the performance of the error correcting code by preventing entries in a permuted first square array from ending up in the same row or column of a second square array after permutation comprising:

a. means for placing information bits from a block of digital data into a first square array;

b. means for creating a second square array having the same number of rows and columns as said first array;

c. means for establishing a first variable for storing a row position of an element in an array, establishing a second variable for storing a column position of an element in an array, establishing a first counter for storing values used in performing iterations, setting the first counter to a first initial value, establishing a first terminal counter value equal to the dimension of the first square array, and if the first counter value is not equal to said first terminal value, then iteratively performing the following steps c1 through c4

(c-1) establishing a second counter for storing values used in performing iterations, setting the second counter to a second initial value, establishing a second terminal counter value equal to the dimension of the first square array, and if the second counter value is not equal to said second terminal value, then iteratively performing the following steps c1a through c1d;

(c-1-a) putting the current first array element into the current second array element location;

(c-1-b) computing a new first variable by incrementing the current first variable by 1, modulus dimension of the first square array;

(c-1-c) computing a new second variable by incrementing the current second variable by 1, modulus dimension of the first square array;

(c-1-d) incrementing the second counter;

(c-2) computing a new first variable by incrementing the current first variable by 2, modulus dimension of the first square array;

(c-3) computing a new second variable by incrementing the current second variable by 1, modulus dimension of the first square array;

(c-4) incrementing the first counter; and

d. means for outputting a second array of shuffled elements.

40. An apparatus for error correction decoding of serially concatenated error correcting codes using an overall iterative decoding process wherein a parity-check decoder and a turbo code decoder iteratively exchange soft decision information using soft decision feedback, comprising:

a. means for receiving soft inputs for the serially concatenated error-correcting encoded data and inverse permuted parity-check extrinsic information at a turbo code decoder and outputting, using soft decision techniques, turbo decoded extrinsic information to a turbo decoded extrinsic information permuter and an adder;

b. means for permuting the turbo decoded extrinsic information and forwarding the permuted turbo decoded extrinsic information to a parity-check decoder;

c. means for permuting the soft inputs for the systematic bits and forwarding the permuted soft inputs for the systematic bits to a parity-check decoder;

d. means for receiving the permuted turbo decoded extrinsic information bits and permuted soft inputs for the systematic bits at the parity-check decoder;

e. means for generating parity-check extrinsic information using soft decision techniques for iterative feedback to the turbo code decoder;

f. means for inverse permuting the parity-check extrinsic information and sending the inverse permuted parity-check extrinsic information to the turbo code decoder and the adder;

g. means for receiving and adding the soft inputs for the systematic bits, the turbo decoded extrinsic information, and the inverse-permuted parity-check decoder extrinsic information at the adder and generating decoder soft outputs;

h. means for receiving the decoder soft outputs at a hard decision decoder and generating decoded data bits.

41. An apparatus for error correction decoding of serially concatenated error-correcting codes using a non-iterative decoding process between an internally iterating turbo code decoder and a parity-check decoder comprising:

a. means for receiving soft inputs for serially concatenated error-correcting encoded data bits at a turbo code decoder,

b. means for iteratively decoding the soft inputs for the serially concatenated error correcting encoded data bit using soft-decision techniques,

c. means for outputting the turbo decoded soft-decision outputs to a permuter;

d. means for permuting the turbo-decoded soft-decision outputs and forwarding the permuted turbo-decoded soft-decision outputs to a parity-check decoder;

e. means for receiving and decoding the permuted turbo-decoded soft-decision outputs at a parity-check decoder; and

f. means for generating decoded information bits.

42. An apparatus for decoding concatenated parity-check code and an internally iterating turbo code passing soft decision information to the parity-check code, wherein the parity-check decoder is a simple decoder comprising:

a. means for receiving hard-decision values for information bits from a turbo-code decoder;

b. means for receiving soft-decision values for information bits from a turbo-code decoder;

c. means for receiving a first horizontal parity bit vector and a first vertical parity bit vector from the turbo code decoder;

d. means for placing the hard decision values for the received information bits into a rectangular parity-check array;

e. means for calculating a second horizontal parity bit vector and a second vertical parity bit vector based on the hard decision values in the first rectangular array;

f. means for adding, using modulo two arithmetic, the calculated second horizontal parity bit vector and the second vertical parity bit vector with the first horizontal hard decision value vector and first vertical hard decision value vector and placing the results in a third horizontal parity bit vector and a third vertical parity bit vector;

wherein the resulting parity bits are binary value 1 for any row or column in the first array containing an odd number of errors, and the resulting parity bits are binary value 0 for any row or column in the first array containing no errors or an even number of errors;

g. means for computing the number of binary value 1'"'"'s in the third vertical parity bit vector, and computing the number of binary value 1'"'"'s in the third horizontal parity vector;

h. means for estimating the positions of symbols output from the turbo code decoder that are in error by examining the soft decision values in the rows and columns of the rectangular parity-check array according to the parity bits computed in the third vertical parity bit vector and the third horizontal parity bit;

i. means for correcting the positions of symbols output from the turbo code decoder that are in error; and

j. means for generating decoded information bits.

43. An apparatus according to claim 42, wherein the element for estimating the positions of symbols output from the turbo code decoder that are in error further comprises:

a. means for comparing the number of binary value 1'"'"'s in the vertical column vector computed for all the rows of the with the number of binary value 1'"'"'s computed in the horizontal row vector for all the columns in the second array;

b. means for determining if the number of binary value 1'"'"'s computed for all the rows of the rectangular parity-check array is equal to the number of binary value 1'"'"'s computed for all the columns in the rectangular parity-check array, establishing a first counter for storing values used in performing iterations, setting the first counter to an initial value, establishing a first terminal counter value equal to the number of rows in the rectangular parity-check array, and if the first counter value is not equal to said terminal value, then iteratively performing the following steps b1 through b3;

(b-1) if the current row has a parity error indicated in the third vertical parity bit vector, finding the minimum soft decision value from all of the columns of the rectangular parity-check array that have a parity error indicated by a binary 1 in the associated horizontal parity bit vector;

(b-2) changing the hard decision value for the minimum soft decision value to the opposite value;

(b-3) incrementing the counter;

c. means for determining if the number of binary value 1'"'"'s computed for all the rows of the rectangular parity-check array is greater than the number of binary value 1'"'"'s computed for all the columns in the rectangular parity-check array, establishing a second counter for storing values used in performing iterations, setting the second counter to an initial value, establishing second terminal counter value equal to the number of rows in the rectangular parity-check array, and if the second counter value is not equal to said terminal value, then iteratively performing the following steps c1 through c3;

(c-1) if the current row has a parity error indicated in the third vertical parity bit vector, finding the minimum soft decision value from all of the rows of the rectangular parity-check array that have a parity error indicated by a binary 1 in the associated vertical parity bit vector;

(c-2) changing the hard decision value for the minimum soft decision value to the opposite value;

(c-3) incrementing the counter;

d. means for establishing a third counter for storing values used in performing iterations, setting the third counter to an initial value, establishing third terminal counter value equal to the number of columns in the rectangular parity-check array, and if the third counter value is not equal to said terminal value, then iteratively performing the following steps d1 through d3;

(d-1) if the current column has a parity error indicated in the third vertical parity bit vector, finding the minimum soft decision value from all of the columns of the rectangular parity-check array that have a parity error indicated by a binary 1 in the associated horizontal parity bit vector;

(d-2) changing the hard decision value for the minimum soft decision value to the opposite value; and

(d-3) incrementing the counter.

44. An apparatus for error correction encoding using a concatenated turbo coder and parity-check coder, wherein the parity-check encoder encodes a subset of the information bits encoded by the corresponding turbo code encoder.

45. An apparatus for error correction encoding a block of digital data using at least two error correcting codes operating in parallel comprising:

a. means for encoding a block of digital information bits and generating parity bits using a parity-check encoder;

b. means for encoding the block of digital information bits in parallel with the parity-check encoder using a turbo encoder;

c. means for outputting a turbo code encoded data block;

d. means for detecting errors in the outputted turbo code encoded data block;

e. means for determining if errors are detected in the outputted turbo code encoded data block and performing the following steps e1 through e2;

(e-1) generating a negative acknowledgement signal to the parity-check encoder; and

(e-2) outputting the parity bits generated for the for the block of digital information bits by the parity-check encoder in response to the negative acknowledgement signal.