Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-08-20
2001-02-20
Baker, Stephen M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S755000, C714S792000, C714S794000
Reexamination Certificate
active
06192501
ABSTRACT:
BACKGROUND OF THE INVENTION
The maximum a posteriori (MAP) decoding algorithm introduced by Bahl, Cocke, Jelinick, and Raviv in “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”,
IEEE Transactions on Information Theory,
March 1974, pp. 284-287, also known as the BCJR algorithm, is an optimum symbol-by-symbol decoder for trellis codes. It is particularly useful as a component decoder in decoding parallel concatenated convolutional codes, i.e. turbo codes, because of its excellent performance. It is advantageous for decoding turbo codes because it accepts soft-decision information as an input and produces soft-decision output information. However, one problem with this type of decoder is that it requires a relatively large amount of memory. For example, the entire received code word must be stored during decoding due to the nature of the algorithm. Furthermore, in order to obtain high-speed decoding, it is necessary to store a large number of intermediate results which represent various event probabilities of interest so that they can be combined with other results later in the decoding process, which decoding process comprises forward and backward (from the end to the beginning of a received code word) recursive calculations. The MAP algorithm as described by Bahl et al. requires that at least half of the results from the two recursive calculations be stored in memory for fast decoding.
Memory size is a particular problem in turbo coding systems since bit-error rate is inversely proportional to the number of information bits in the code word. (The term “block size” as used herein refers to the number of information bits in a code word.) In a turbo coding system, therefore, it would be desirable to utilize the largest block size possible in order to obtain the greatest coding gain. Unfortunately, an efficient and practical system utilizing such a large block size has not emerged heretofore.
Therefore, it is desirable to provide a method and system for encoding and decoding large trellis codes, which method and system require a significantly reduced memory without compromising coding gain and without additional overhead. It is furthermore desirable that such a method and system be applicable to turbo coding such that an efficient and practical turbo coding system is realizable.
SUMMARY OF THE INVENTION
In a communications system, a trellis code word is segmented by both the encoder and a segmented symbol-by-symbol MAP decoder, advantageously reducing required memory size with insignificant loss in coding gain and little or no additional overhead. The encoder periodically returns to a known state by the insertion of “tail” or “merge” bits into the sequence of information bits from the source. The segmented MAP decoder operates on code word segments as if they were individual code words and takes advantage of knowing the state of the encoder at specified times to reduce decoding latency and required memory. This is applicable to a turbo coding system, for example, wherein the coding gain is maintained by interleaving the information bits across the segments of a component code word. The result is an efficient and practical turbo decoder.
REFERENCES:
patent: 5406570 (1995-04-01), Berrou et al.
patent: 5446747 (1995-08-01), Berrou
patent: 5511073 (1996-04-01), Padovani et al.
patent: 5663957 (1997-09-01), Dent
patent: 5721745 (1998-02-01), Hladik et al.
patent: 5721746 (1998-02-01), Hladik et al.
patent: 5734962 (1998-03-01), Hladik et al.
patent: 5862132 (1999-01-01), Blanchard et al.
Benedetto et al., “Performance of Continuous and Blockwise Decoded Turbo Codes”, IEEE Communications Letters, vol. 1, No. 3, May 1997, pp. 77-79.
“Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes,” Patrick Robertson, IEEE, 1994, pp. 1298-1303.
“Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” LR Bahl, J Cocke, F. Jelinek; J. Raviv, IEEE Transactions on Information Theory, Mar. 1974, pp. 284-287.
“Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes (1),” Claude Berrou, Alain Glavieux; Punya Thitimajshima, IEEE, 1993, pp. 1064-1070.
Fergus Ross John Anderson
Hladik Stephen Michael
Van Stralen Nick Andrew
Baker Stephen M.
Breedlove Jill M.
General Electric Company
Stoner Douglas E.
LandOfFree
High data rate maximum a posteriori decoder for segmented... 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 data rate maximum a posteriori decoder for segmented..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High data rate maximum a posteriori decoder for segmented... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598541