Turbo product code decoder

Details Turbo product code decoder Turbo product code decoder

2002-12-19

2004-07-13

Lamarre, Guy J. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S785000, C375S262000

Reexamination Certificate

active

06763494

ABSTRACT:

FIELD OF THE INVENTION
The invention generally relates to the field of linear block codes. More particularly, the invention relates to a soft decision turbo product code decoder for error correction decoding.
BACKGROUND OF THE INVENTION
Recently, error correction decoding techniques for recognizing and correcting errors in digital signal transmission have been used in many fields to improve the reliability of data transmission. One such technique is known as Error Corrective Coding (ECC). The basic concept of ECC is to add redundant bits to a digital message in order to eliminate the need for retransmission of the data. This addition of redundant bits to the message is known as Forward Error Correction (FEC). The addition of these redundancy bits allows a decoder at the receiving end to detect and/or correct errors that might have been caused during transmission.
There are several methods employed in adding redundant bits to a message, and one such method is known as block coding. In block coding, the data or message to be transmitted is broken into smaller blocks and each block is coded separately—i.e. redundant bits are appended to the end of each block of data. On the receiving end, each block of data is decoded separately. Block coding has been used in many practical applications, including magnetic and optical storage systems, as well as mobile communications systems, such as cellular phones. Familiarity with the terminology used in block coding is important in understanding the present invention. In preparation for the description contained herein, the basic principles and terminology behind block coding shall be briefly described.
A block code is often described as an (n,k) code, wherein n is the total number of bits in the encoded transmission block and k is the number of bits in the unencoded message block. Accordingly (n−k) redundancy bits, also known as parity bits, have been added to the message block when it is encoded before transmission. In a block code, every legitimate unencoded message differs from every other legitimate unencoded message by a minimum number of bit positions. We refer to this number of bit positions by which every legitimate unencoded message differs as the Hamming distance d
min
. In order to correct single bit errors, a block code must have a minimum Hamming distance of at least 3.
Binary Hamming codes are a well known family of codes used in the art of error correction which provide FEC by using a “block parity” mechanism, wherein a number of redundancy or parity bits are appended to each block of data before transmission. The number of parity bits required to be appended for a given block is defined as the Hamming rule, and is a function of the total number of bits which may transferred—i.e. the bandwidth. A code obtained by appending an (even) extended parity bit onto a binary Hamming code is called an extended Hamming code.
Product codes arrange two dimensional codes (n,k) into (n×n) size arrays. First, k blocks of data, with each block being a length k, are stored in a (k×k) array. Each row and column is then encoded with redundancy bits or ECC and the (even) extended parity bit is appended to each row and column, thereby creating an Extended Hamming Product code For example, the following diagram shows an (8,4)×(8,4) Extended Hamming Product Code, where “D’ represents original data, “E” represents the ECC or redundancy bits, and “P” represents the extended parity bit.
D
D
D
D
E
E
E
P
D
D
D
D
E
E
E
P
D
D
D
D
E
E
E
P
D
D
D
D
E
E
E
P
E
E
E
E
E
E
E
P
E
E
E
E
E
E
E
P
E
E
E
E
E
E
E
P
P
P
P
P
P
P
P
P
&AutoLeftMatch;
As can be seen, each row and column ends with a parity bit P.
The conventional method for decoding an Extended Product Hamming Code after transmission is to receive incoming data, store it in an array and decode each row or column of the array separately using maximum likelihood decoding. Typically, this is accomplished through the use of a look-up table which includes every legitimate valid message. In the decoding process, the data is compared to each entry in the look-up table—i.e. all of the possible valid messages within the table, after the parity and redundancy bits have been removed. If the Hamming distance d
min
is large, than the likelihood of error in choosing the right message from the table is reduced. However, if the Hamming distance d
min
is small, then the likelihood of error increases. Full correlation decoding of one row or column in a product code requires comparing the data with the full set of possible transmitted codewords. For an (8,4); code, this only requires a comparison with 16 possible transmitted codewords. However, for a (64, 57) code, there are 1.4×10
17
possible transmitted codewords, making a full correlation with the use of a look-up table unfeasible.
Additionally, error correction decoding techniques acquire increased value when they not only accurately estimate the content of the original message; but, also provide confidence measures as to the likelihood that the decoded message is correct. Such information is generally referred to as “soft output information”. As an example, in a soft output decoder, the decoder will receive an incoming block of data and attempt to decode the incoming block of data. After decoding the incoming block of data, the soft output decoder will assign a confidence value or measure to the output, indicating whether the decoder is more or less certain of the results. If the decoder assigns a high confidence value to the output, it is more certain that is has properly decoded the incoming block of data. However, if the decoder assigns a low confidence value to the, output, it is less certain that the incoming block of data has been properly decoded—i.e. there may be more than one possible interpretation of the incoming block of data.
A Soft In/Soft Out (SISO) decoder receives demodulated soft decision input data and produces soft decision output data. For each bit in the block of soft decision input data, the decoder examines the confidence of the other bits in the block, and using the redundancy of the code, generates a new soft decision output for the given bit. If the redundancy of the code indicates that the output for the given bit is correct, the decoder will output a positive confidence value. If the redundancy of the decode indicates that the output for the given bit is incorrect, it will output a negative confidence value. The negative value indicates that the confidence value for that bit should be decreased. This may mean that the bit should be inverted from a “1” to a “0” or vice versa.
Within the last decade, SISO decoders have been applied to a new decoding method called turbo codes. Turbo codes are an iterative decoding scheme which decode incoming data blocks in two or more dimensions (depending on the encoding scheme). Accordingly, by way of example, incoming data may be stored in an array and decoded by row and column. When the iterative decoding is applied to product codes of extended Hamming Codes the resultant code is called a turbo product code. A conventional turbo product decoder feeds demodulated soft decision data into the SISO for the first dimension (i.e. the x-rows). The output is then summed with the original demodulated soft decision data and fed back into the SISO for decoding of the second dimension (i.e. the y-columns). The output from the SISO is again summed with the original demodulated soft decision data and fed back into the SISO for decoding of the first dimension once again (i.e. the x-rows). In order for this iterative decoding process to be effective, the data must have been encoded in at least two different dimensions (i.e. it was stored in an array and the rows and columns of the array were each encoded). Typically, this is done by encoding the data horizontally (rows) and vertically (columns).
Typically, each iteration in the decoding process modifies the confidence or soft decision value assigned to each bit since the data is slightly modified through each horizontal and/or vertical decode

Affiliated with

Also associated with

Rating

Turbo product code decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Turbo product code decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turbo product code decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3259204