Sliding window technique for map decoders

Details Sliding window technique for map decoders Sliding window technique for map decoders

2000-07-31

2004-11-02

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C375S341000, C714S755000, C714S786000

Reexamination Certificate

active

06813743

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention generally relates to maximum a posteriori (MAP) decoders, and, more specifically, to efficiently performing decoding of large blocks of coded symbols or bits with a MAP decoder.
2. Background
MAP decoders were proposed over two decades ago in “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” L. R. Bahl et al., IEEE Transactions on Information Theory, March 1974, pp. 27-30 (hereinafter referred to as “the Bahl reference”). More recently, refinements to MAP decoders have been proposed in “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes,” C. Berrou et al., Proc. ICC ’93 Geneva, Switzerland, May 1993, pp. 1064-1070 (hereinafter referred to as “the Berrou reference”). Both the Bahl and Berrou references are hereby fully incorporated by reference herein as though set forth in full.
Because of its increased complexity in relation to Viterbi decoders, the MAP decoder has not been widely adopted. The problem is compounded when long blocks are used, stemming from the use of long interleavers during the encoding process. To simplify the decoding process, a sliding window technique has been proposed in “An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes,” A. Viterbi, IEEE Journal On Selected Areas In Telecommunications, Vol. 16, No. 2, February 1998, pp. 260-264 (hereinafter referred to as “the Viterbi reference”), which is hereby fully incorporated by reference herein as though set forth in full. However, the sliding window technique proposed in the Viterbi reference releases soft decisions in awkward fits and starts in which soft decisions for successive sub-blocks are released in consecutive order, but the soft decisions for each subblock are released in reverse order. Because of this order of data release, the sliding window technique proposed in the Viterbi reference is not efficient in the use of memory. Another problem is that there is a variable delay between the initiation of processing and the release of soft outputs. That makes subsequent processing utilizing the soft outputs more difficult.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, there is provided a MAP decoding system in which one or more forward engines and one or more backward engines operate in unison to calculate the soft outputs for encoded symbols within a sliding window of a larger block. The one or more backward engines calculate backward probabilities over respective sub-blocks within a sliding window. In synchronization with the one or more backward engines, the one or more forward engines recursively calculate forward probabilities over the successive sub-blocks. In synchronization with the calculation of the forward probabilities, the one or more forward engines calculate and release soft outputs for the successive sub-blocks. The sliding window is then moved forward or backward and the calculations performed on a different portion of the block. The process repeats itself until the entire block has been processed.


REFERENCES:
patent: 4291406 (1981-09-01), Bahl et al.
patent: 5329535 (1994-07-01), Coker
patent: 5724106 (1998-03-01), Autry et al.
patent: 5933462 (1999-08-01), Viterbi et al.
patent: 6023783 (2000-02-01), Divsalar et al.
patent: 6128765 (2000-10-01), Ross et al.
patent: 6421804 (2002-07-01), Lee
patent: 6477681 (2002-11-01), Taipale et al.
patent: 6580767 (2003-06-01), Koehler et al.
Bahl, L.R., et al.,Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate; IEEE Transactions on Information Theory; Mar. 1974; pp. 284-287.
Berrou, Claude, et al.,Near Shannon Limit Error—Correcting Coding and Decoding: Turbo-Codes(1), Integrated Circuits for Telecommunication Laboratory et al., 1993, IEEE, pp. 1064-1070.
Viterbi, Andrew J.,An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes; IEEE Journal on Selected Areas in Communications, vol. 16, No. 2, Feb. 1998., pp. 260-264.
Benedetto, S., et al.,A Soft-Input Soft-Output Maximum A Posteriori(MAP)Module to Decode Parallel and Serial Concatenated Codes; TDA Progress Report, 42-127, Nov. 1996, pp. 1-20.
Benedetto, S. and Montorsi, G.,Iterative decoding of serially concatenated convolutional codes; Electronics Letters, vol. 32, No. 13, Jun. 1996, pp. 1186-1188.
Benedetto, S. and Montorsi, G.,Serial concatenation of block and convolutional codes; Electronics Letters, vol. 32, No. 10, May 1996, pp. 887-888.
Divsalar, D. and Pollara, F.,Serial and Hydrid Concatenated Codes with Applications; Jet Propulsion Laboratory, California Institute of Technology, pp. 1-8.
Divsalar, D. and Pollara, F.,Turbo Trellis Coded Modulation with Iterative Decoding for Mobile Satellite Communications; Jet Propulsion Laboratory, California Institute of Technology, pp. 1-7.
Hoeher, Peter and Lodge, John, “Turbo DPSK”: Iterative Differential PSK Demodulation and Channel Decoding; IEEE Transactions on Communications, vol. 47, No. 6, Jun. 1999, pp. 837-843.
Narayanan, Krishna R. and Stüber, Gordon L.,A Serial Concatenation Approach to Iterative Demodulation and Decoding; IEE Transactions on Communications, vol. 47, No. 7, Jul. 1999, pp. 956-961.
Robertson, P., et al.,A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain; IEEE, 1995, pp. 1009-1013.
Pietrobon, S., “Efficient Implementation of Continuous MAP Decoders and a Synchonisation Technique for Turbo Decoders,” pp. 1-4, reprinted from Proc. Int. Symp. Inform. Theory Appl., Victoria, B.C., Canada, 1996, pp. 586-589.

Affiliated with

Also associated with

Rating

Sliding window technique for map decoders does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sliding window technique for map decoders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sliding window technique for map decoders will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3363856