Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-05-25
2004-04-06
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S777000
Reexamination Certificate
active
06718508
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods of data encoding. In particular, the present invention relates to a method of encoding data for error correction and decoding error encoded data.
BACKGROUND OF THE INVENTION
The communication of data intensive information has increased with the advent of wireless and internet technologies, and consequently, consumers and businesses are demanding increased speed and accuracy in their data communication systems.
Wireless mediums such as digital cellular and satellite communications channels are inherently noisy, resulting in transmissions having a large number of errors. Re-transmission of the data is typically required, reducing system performance and efficient use of available bandwidth.
A solution that has been used for several years to enable efficient, high quality data communication over noisy channels is forward error correction codes (FEC). FEC technology adds redundant information to a data stream, to enable a receiver to identify and correct errors without the need for re-transmission of data. The correcting process is called forward error correction because the receiving decoder only uses the information received and never requests a re-transmission, hence the flow of data is always moving forward. FEC coding of data is typically performed in the modulator of a communication system, and decoding of the encoded data is typically performed in the demodulator of the system.
Included among the types of FEC codes are low-density parity-check (LDPC) codes and turbo-codes, for example. Specific classes of LDPC codes have been investigated by R. G. Gallager in the paper titled “Low-density parity-check codes”, in IRE Transactions on Information Theory, pp. 21-28, January 1962, J. Lodge et al. in the paper titled “The decoding of multi-dimensional codes using separable MAP ‘filters’” in Proc. 16
th
Biennial Symp. On Commun., Kingston, Canada, pp. 343-346, May 1992, A. Hunt et al. in the paper titled “Hyper-codes: High-performance low-complexity error-correcting codes” in Proc. 19
th
Biennial Symp. On Commun., Kingston, Canada, pp. 263-267, May 1998, and D. Rankin et al. in the paper titled “Randomly interleaved single parity check codes” in Proc. IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Victoria, pp. 420-423, Aug. 1999. Many LDPC codes are well suited to high code-rate applications, as compared to turbo codes, as presented by C. Berrou et al. in the paper titled “Near optimum error-correcting coding and decoding: Turbo codes” IEEE Trans. On Commun., vol. 44, no. 10, pp. 1261-1271, October 1996. Turbo codes excel at low to moderate code rates when the signal-to-noise ratio (SNR) is also low to moderate, but can experience a flattening, or flaring of the bit-error rate (BER) curve at SNRs that limit the ultimate power efficiency for very low packet-error rate applications. This flaring is due to the existence of low-weight code words.
Fundamentally, FEC technology is a type of error-correction code. An error-correction code is a method of coding information messages in a manner that incorporates redundancy. By exploiting this redundancy, a decoder for an error-correcting code is able to provide error-correcting and/or detecting functionality. However, redundancy as incorporated within error-correction codes does not necessarily imply an exact duplication of data.
Herein, the term error-correction code, referred to as a code from this point forward, is defined as a mapping of information messages to code words, each code word being an ordered collection of symbols from some finite symbol set. Each code word of a code has the same code word length. A symbol set is a collection of distinct identifiers, such as {0 1} or {1 &bgr; &bgr;
2
&bgr;
3
}. The code words of a code form a proper subset of all possible ordered collection of symbols from the symbol set, and the collections of a size are equal to the code word length. Some ordered collections of symbols from the symbol set are code words of the code, and others are not, and this is what provides the required redundancy.
The symbol set of the code has an associated operator, called addition, defined over the elements of the symbol set, with one of the symbols in the symbol set being the identity element for the addition operator. Further, each element must have an inverse and the addition operator must be commutative, in other words, the operator is insensitive to the ordering of the operands. For example, a+b=b+a. In mathematical terms, the symbol set together with the addition operator form an abelian group.
Typically, a set of constraints determines which ordered collections of symbols are code words of a code and which are not. The constraints are expressed in terms of one or more operators that are associated with the symbol set. Highly structured constraints are usually desirable to enable simple encoding and decoding of a code. The constraints are usually defined over groups or fields, which have well-known mathematical properties.
A code where the information message is part of the code word itself is called a systematic code. That is, with a systematic code, the information messages are expressed in terms of the same symbol set used for the code words themselves, and the symbols of the information message appear within the associated code word, in some arbitrary but fixed placement pattern.
Block codes are codes having a finite code word length. Linear codes are identified when the sum of every pair of code words is a code word. Binary codes have symbols that are bits, such as 0 and 1. A product code is a code constructed from two or more codes, called component codes of the product code, which are combined in an orthogonal manner. Specifically, an N-dimensional product code is a code composed of N component codes, where each code word of the product code can be represented as an N-dimensional array of symbols. For any selected dimension and any set of valid indices for other dimensions, the ordered collection of symbols determined by moving along the selected dimension while keeping the indices of the other dimensions fixed, is a code word of the component code associated with the selected dimension. It is noted that a component code of a product code may itself be a product code.
Parity is a well-known method of applying constraints for coding. Using even-parity with bits, a constraint exists that a set of symbols sums modulo-2 to 0. For example, a set of message information bits {1 0} are encoded as the code word {1 0 1 }, and a set of message information bits {1 1 } are encoded as the code word {1 1 0}. Even-parity with bits, in the binary case, is a special case of sum-to-identity parity for general symbol sets.
Error correcting capability can be improved by creating larger, more powerful codes. A method of creating a larger and more powerful code from one or two linear component codes is to arrange the message information symbols in a rectangular array, or matrix, and then form a product code by applying parity equations along the rows and columns of the array. More specifically, one set of parity equations, called row parity equations, corresponding to the row component code is applied along the rows and a second set of parity equations, called column parity equations, corresponding to the column component code is applied along the columns resulting from the application of the first set of parity equations. The resulting two-dimensional product codes have a minimum distance equal to the product of the minimum distances of the row and column component codes, and the arithmetic difference patterns between two product code words are linear combinations of simple rectangular (i.e., weight 4) patterns. Additional dimensions could be added by stacking the product code words of the message information array to form a 3-dimensional array. Then, a third set of parity equations could be applied straight through the third dimension to form a 3-
Guinand Paul
Hunt Andrew
Lodge John
Borden Ladner Gervais LLP
Her Majesty the Queen in right of Canada as represented by the
Kinsman Anne
Ton David
LandOfFree
High-performance error-correcting codes with skew mapping does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-performance error-correcting codes with skew mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-performance error-correcting codes with skew mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3187421