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

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 ray;
• 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.

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.

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.

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.

A 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.

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;
• and
• 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.

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.

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.

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 permutacion 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.

An apparatus for error correction decoding of serially coficatenated 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.

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 pennuting 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.

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 patty 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.

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 block of digital information bits by the parity-check encoder in response to the negative acknowledgement signal.