Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-05-15
2003-06-17
Tu, Christine T. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S780000, C375S262000, C375S341000
Reexamination Certificate
active
06581182
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to communication systems that encode and decode with concatenated codes, and, more particularly, to iterative decoding of data detected from a communication medium.
2. Description of the Related Art
Concatenated code systems for encoding and decoding data use two or more component codes that are concatenated during the process of encoding the data. Although the component codes may be of any type, the component codes are typically relatively simple codes such as the convolutional codes. The two or more component codes are concatenated either in serial or in parallel. For example, in serial concatenation of two component codes, data is first encoded by a first encoding module with a first component code. This encoded data is, in turn, passed through an interleaver and then applied to a second encoding module for encoding with a second component code. This process operates on only a single, serial data stream, and the first and second component codes may be the same code. In the parallel concatenation, in one processing path data is encoded with the first component code and in the other processing path data is interleaved and then is encoded with a second component code. The two encoded streams are combined in parallel by, for example, interleaving to provide a single encoded data stream.
For either serial or parallel concatenation, the encoded data is then used to modulate a signal that is passed through a communication (transmission) channel to a receiver, which processes the transmitted signal from the transmission channel. Such transmission channel may correspond to recording on and playback from a magnetic medium, or may correspond to transmission between users through a cellular/wireless/wired channel. The transmission channel has a corresponding frequency response that possibly includes memory (e.g., a partial response channel). The signal modulated by the encoded data has an added noise component and added signal distortion caused by the channel's frequency response as the signal passes through the transmission channel.
The term “output channel sample” refers to the samples of the channel output (signal modulated by encoded data) from the transmission channel that is generated through the sampling process of the receiver. The receiver typically includes a detector to detect the sequence of symbol bits representing the encoded data from the output channel samples. A decoder receives the detected symbol sequence from the detector and decodes the sequence of symbol bits o reconstruct the data. The decoder may be a simple decoder reversing the encoding process, or it may be an iterative decoder that repetitively decodes the data for a predefined number of iterations or until a predetermined decoding metric, such as maintaining the bit-error rate (BER), is less than a specified threshold.
The detector and the decoder may each typically employ a partial-response, maximum-likelihood (PRML) algorithm (e.g., a Viterbi algorithm (VA)), a maximum a posteriori (MAP) algorithm, or a soft-output Viterbi algorithm (SOVA). SOVA algorithms are known in the art and is described in, for example, J. Hagenauer and P. Hoeher, “A Viterbi Algorithm With Soft Decision Outputs and Its Applications,”
Proc. of IEEE Globecom '
89, pp. 1680-1686, November, 1989, the teachings of which are incorporated herein by reference.
Concatenated code systems may employ iterative decoding of encoded data using either serial or parallel iterative decoding methods. When employing iterative decoding of data encoded with a concatenated code, a block of data is input to the iterative decoder. The block boundaries desirably conform to symbol boundaries of the concatenated code. The iterative decoder may comprise N component code decoders for decoding in accordance with each of the N component codes originally used to encode the data. The particular implementation of the iterative decoder is dependent on whether the encoding process was based on serial or parallel concatenation.
In an iterative decoding method, the complete decoding process during each iteration subjects a block of encoded data to decoding by each of the N component code decoders. The complete decoding process repeats for each iteration until a predetermined number (I) of decoding iterations are complete. Each iteration performs a complete, “soft” decoding of the data encoded with a concatenated code (i.e., a decoding with each component code of the concatenated code). Each iteration allows for higher confidence in the decisions for bits in the decoded data that are made based on the soft-output values provided from the detector.
The following definitions may be of use to understanding the encoding and decoding methods. A set of binary values U is defined in the Galois field-2 (GF(2)) with elements {+1, −1} where −1 is the “null” element under ⊕ addition. The reliability value L(u) is the log-likelihood ratio of the binary random values in U and is defined as the natural log of the ratio of the probability that the random variable U takes on the value u=+1 to the probability that the random variable U takes on the value u=−1. The sign of L(u) is used as a hard decision by a detector, and the magnitude of L(u) is used as a reliability statistic for the hard decision.
In an iterative decoding scheme, the reliability values for decoded user bits are updated at each iteration, utilizing the information extracted from the previous iteration, termed “soft-in, soft-out” decoding. Iterative decoding of concatenated codes using “soft-in, soft-out” information is well known in the art and is described in, for example, J. Hagenauer, E. Offer, and L. Papke, “Iterative Decoding of Block and Convolutional Codes”,
IEEE Transactions on Information Theory
, Vol. 42, No. 2, March 1996, whose teachings are incorporated herein by reference.
To decode a block of output channel samples to provide a block of decoded data, the soft-in, soft-out decoder receives the output channel sample values from a transmission channel as well as a priori reliability values L′(u) for the information bits u. The a priori reliability values L′(u) may be 0 for the first iteration, and, after the first iteration, the soft decision (a posteriori) reliability values L(u) for the information bits from the previous iteration. Also provided are “extrinsic” values L
e
(u) for the decoded information bits. The “extrinsic” values L
e
(u) may be values based on indirect information not available from a previous iteration (e.g., other parity bits added to the information bits or the values from decoding with one component code that are subsequently used to make a hard decision for an information bit when decoding with another component code. For each decoding iteration in the 2-dimensional case, the decoder completes a decoding operation for each component code. In this case, the extrinsic values L
e
(u) may be employed sequentially as a priori reliability values L′(u) for soft-in, soft-out decoding of each component code.
When concatenated codes are used to encode data that is then passed through a transmission channel with memory, additional decoding (performance) gain is achieved when each iteration of decoding also includes full demodulation of the received data. Full demodulation refers to complete detection of a block of symbols from the output channel samples before subjecting the block of symbols to an iteration of decoding. This is commonly termed a “full-iteration” decoding scheme because, in effect, iterative detection also takes place in the receiver. The full iterative decoder may be implemented as a serial iterative decoder that operates sequentially with I iterations. While MAP detectors achieve optimum performance, they are complex to implement, adding considerably to the complexity of iterative decoders. Consequently, for each iteration, detectors of the prior art typically employ a soft output Viterbi algorithm (SOVA)
Agere Systems Inc.
Hughes Ian M.
Mendelsohn Steve
Tu Christine T.
LandOfFree
Iterative decoding with post-processing of detected encoded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Iterative decoding with post-processing of detected encoded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterative decoding with post-processing of detected encoded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3099211