Error detection/correction and fault detection/recovery – Pulse or data error handling – Data formatting to improve error detection correction...
Reexamination Certificate
2000-05-11
2003-08-12
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Data formatting to improve error detection correction...
C714S804000
Reexamination Certificate
active
06606718
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to encoding, detection, and decoding of data in communication systems, and, more particularly, to a product code with interleaving for error detection and correction by a receiver.
2. Description of the Related Art
Many digital transmission systems commonly employ techniques for detection of digital data represented by a sequence of symbols. The symbol bits are transferred as a signal through a transmission (i.e., communication) channel in which noise is typically added to the transmitted signal. For example, magnetic recording systems first encode data into symbol bits that are recorded on a magnetic medium. Writing data to, storing data in, and reading data from the magnetic medium may be considered to take place via a transmission channel that has an associated frequency response. Similarly, wired, optical, wireless, and cellular communication systems also transfer encoded data through a channel that is then detected and decoded by a receiver. The signal may be read from the channel as a sampled signal (i.e., a sequence of sample values) representing the transmitted encoded data. For processing convenience, the encoding and decoding process is applied to blocks of data, each block representing a portion of the original data sequence.
Encoding data with two-dimensional or higher block codes and subsequent decoding of the encoded data are employed in many systems due to the relatively high coding gain and simple structure of the decoder. Product codes may be employed for encoding of data in which two or more simple codes (known as component codes) are combined to create more powerful encoding schemes. The dimension of the code may be related to the number of component codes.
For example, a product code may employ a parity-bit check code that, for the two-dimensional case, encodes N information bits as two-dimensional data words (e.g., n
1
words having n
2
information bits, or n
2
words having n
1
information bits). Each data word represents a vector in a corresponding dimension, and n
1
and n
2
are integers greater than 0. The product code encoding of the data (i.e., the N information bits) are ordered in a rectangular matrix u, and the encoding may be a row vector (e.g., n
1
information bits) by column vector (e.g., n
2
information bits) combination to form the rectangular matrix u. The combination may be GF(2) addition, multiplication, or linear operation of the binary values. For example, a sequence of N information bits (e.g., a block of data) may be formed as an (n
1
×n
2
) matrix of information bits, with N=n
1
n
2
. The product code encoding of the data also includes row- and column-wise parity bits p
r
and p
c
, respectively, as error detection and correction information. Horizontal rows are formed from n
2
code words of an (n
1
, k
1
) block code C
r
having rate R
1
=(n
1
/k
1
) (here, k
1
is the total length of a row, and the length of the parity bit information for each row is k
1
−n
1
). Vertical columns are formed from n
1
code words of an (n
2
, k
2
) block code C
c
having rate R
2
=(n
2
/k
2
) (here, k
2
is the total length of a column, and the length of the parity bit information for each column is k
2
−n
2
).
The block of data encoded with the product code is typically transmitted as a serial block of encoded data. Product codes typically exhibit optimum performance with respect to coding gain when correcting for single one-bit errors when single-bit parity check codes are employed per dimension. Only single, one-bit errors may be detected and corrected because of parity-check cancellation arising from an even number of errors occurring in a row or in a column and parity-check positional ambiguities associated with multiple one-bit errors. For an example of this positional ambiguity in a square, product code matrix with single bit parity check codes, let the first element of the first row be in error, and the second element of the second row be in error (errors along the forward diagonal). Both the first and second row-wise and first and second column-wise parity bits will indicate an error, but they will also indicate an error if the second element of the first row and the first element of the second row is in error (errors in the reverse diagonal). Detection and correction of higher numbers of errors, especially higher numbers of consecutive errors, may add excessive overhead in terms of error detection information (e.g., parity bits), reducing overall system throughput. Errors in data at the receiver may be caused by incorrect decisions of the detection and/or decoding process because of signal degradation. Signal degradation occurs from added random and/or burst noise as the signal passes through the communication channel.
A characteristic of some communication channels is the addition of “bursty” noise. Such noise may corrupt a transmitted signal for a period of time equivalent to the period of several transmitted symbols (either data or encoded data). Bursty noise may cause burst errors in the received data. To minimize the effect of burst errors, many communication systems include an interleaver in the transmitter and a corresponding de-interleaver in the receiver. Interleaving is a mappingƒ(*) that generally comprises receiving a block of data having BLK values (i.e., BLK is the block length and BLK is an integer greater than one), and rearranging the order of the BLK values in the block. Interleaving may also be employed, for example, to remove non-random sequences of values in a data stream. By interleaving the symbols in a block of data prior to transmission through the channel, the de-interleaving process distributes the burst errors throughout the de-interleaved block.
The term “output channel sample” refers to a sample of encoded data from the transmission channel generated through the sampling process of the receiver. A 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 to reconstruct the data. The decoder may be a simple decoder reversing the encoding process, or an iterative decoder that repetitively decodes the data until a predetermined decoding metric, such as a maximum bit-error rate (BER) threshold, is satisfied. The detector and the decoder may each typically employ a partial response, maximum-likelihood (PRML) algorithm (e.g., Viterbi algorithm (VA)), a maximum a posteriori (MAP) algorithm, or a soft-output Viterbi algorithm (SOVA).
These algorithms used by detectors and/or decoders typically determine a maximum-likelihood path through a trellis of states. The path represents a sequence of decisions for symbols corresponding to the received output channel samples. However, in situations where the received signal has low signal-to-noise ratio (SNR), the algorithm may determine an incorrect path through the trellis, thereby generating an incorrect sequence of decisions for a corresponding sequence of output channel samples. Such sequence of errors is commonly termed an “error event” of the detection algorithm. For some error events, the decision for the sequence of received bits may generate a long sequence of errors, which are thus inserted into the detected encoded data prior to decoding. Consequently, the detection algorithms used in a particular implementation are optimized based on channel memory, SNR, and impulse response, and indirectly with respect to dominant error events.
SUMMARY OF THE INVENTION
The present invention relates to encoding a block of data with a product code and interleaving of the values of the encoded block to enhance error detection and correction of the product code. The error correction capability of the product code detects and corrects M-bit errors in an encoded block, M a positive integer. The encoded block is interleaved by applying a mapping to the encoded block based on
Agere Systems Inc.
Hughes Ian M.
Mendelsohn Steve
Tu Christine T.
LandOfFree
Product code with interleaving to enhance error detection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Product code with interleaving to enhance error detection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Product code with interleaving to enhance error detection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3095022