Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-04-25
2003-08-12
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S780000, C714S794000
Reexamination Certificate
active
06606725
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to error-correcting decoding for digital signals received via noisy channels and, more particularly, to a maximum a posteriori (MAP) decoding method for turbo codes based on parallel matrix processing.
BACKGROUND OF THE INVENTION
In mobile wireless communications, multipath fading, intersymbol interference and thermal noise induced by electronic devices lead to an abundance of transmission errors. Channel coding is a common method for obtaining a sufficient quality signal at a receiver. An overview of the most widespread methods for channel coding is presented by Proakis in “
Digital Communications
,” McGraw-Hill International Editions, 1989.
Recently, a novel class of binary parallel concatenated recursive systematic convolutional codes, termed turbo codes, originally described by Berrou et al. in “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes”,
Proceedings of IEEE International Conference on Communications
, 1993, pp. 1064-1070, have received a great deal of attention, see also U.S. Pat. No. 5,406,570, “Method for a maximum likelihood decoding of a convolutional code with decision weighting, and corresponding decoder” issued to Berrou on Apr. 11, 1995. Turbo codes can provide excellent error correcting capability and are, therefore, very attractive for mobile wireless applications to combat channel degradation.
One of the key strategies of turbo codes is an iterative (turbo) decoding mode with soft constituent decoder information exchange, see Andersen, “The TURBO Coding Scheme,” Report IT-146 ISSN 0105-854, Institute of Telecommunication, Technical University of Denmark, December 1994, and Robertson, “Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes,”
Proceedings of IEEE GLOBECOM Conference
, 1994, pp. 1298-1303. Maximum a posteriori (MAP) based methods have proven to be the best for implementing iterative decoding of turbo codes.
A MAP method is based on the BCJR method, see Bahl et al. in “Optimal Decoding of Linear Codes for Minimizing Symbol error Rate,”
IEEE Transactions on Information Theory
, Mar. 1974, pp. 284-287). The MAP method makes optimum symbol-by-symbol decisions, and also provides soft reliability information that is necessary in iterative decoding. There is an increasing demand for practical MAP decoders so that turbo codes can be used in a wide range of applications, such as third generation wideband DS-CDMA mobile communication systems.
However, the conventional MAP method suffers serious drawbacks that make it difficult to achieve low-cost VLSI implementations. Most notably, the complex operations for forward-backward recursions required by the MAP method incur decoding delays and a substantial amount of storage. Most prior art MAP decoders require a significant complexity, compared with the convolutional-code decoders, for example, see Comatlas, Chateaubourg, France, “CAS 5093 Turbo-Code Codec, data Sheet,” August 1994, Efficient Channel Coding, Inc., Eastlake Ohio, USA, “ECC Turbo product code technology,” March 1998, and Small World Communications, Adelaide, Australia, “MAP04 and MAP04A 16 State MAP Decoders,” April 1998.
Therefore, it is desired to provide an efficient low-complexity MAP decoder circuit and method which makes possible a practical VLSI implementation without suffering a substantial performance penalty.
SUMMARY OF THE INVENTION
The present invention provides a matrix transform method and apparatus for MAP decoding of turbo codes. In this invention, the successive decoding procedures are performed in parallel and well formulated into a set of simple and regular matrix operations. These operations substantially accelerate decoding and reduce the computational complexity, and are particularly suited for implementation in special-purpose parallel processing VLSI hardware architectures.
Using shift registers, the implementation schemes for the invented matrix MAP decoding effectively reduce the memory requirement and simplify complicated data accesses and transfers, compared with what is known in the prior art.
More particularly, the invention provides a method and apparatus for fast implementation of MAP decoding a noise corrupted turbo-encoded sequence R
1
N
={R
1
, R
2
, . . . , R
N
}. In general, the method begins with initializing forward and backward recursion probability function vectors &agr;
0
and &bgr;
N
by setting &agr;
0
=[1, 0, 0, . . . , 0] and &bgr;
N
=[1, 1, . . . , 1], respectively. Then, the method determines transition probability matrices &Ggr;(R
k
) and &Ggr;
i
(R
k
) for each received sequence R
k
. Then, values of the vector &agr;
k
are determined according to &Ggr;(R
k
). As &agr;
k
is determined, the method does multiplications on &Ggr;(R
k
) s and &Ggr;
1
(R
k
).
After receiving the complete sequence R
1
N
, an embodiment of the matrix MAP decoding method determines all values of the vector &bgr;
k
T
, k=1, 2, . . . N−1 in parallel by making use of the results of the above matrix multiplication on &Ggr;(R
k
), finally the method determines the log likelihood ratios for all of decoded bits, i.e., &Lgr;(d
k
), k=1, 2, . . . N, in parallel.
An alternative embodiment directly determines the final log likelihood ratios for all of decoded bits, i.e., &Lgr;(d
k
), k=1, 2, . . . N, in parallel, by making direct use of the results of the multiplications on &Ggr;(R
k
)s and &Ggr;
1
(R
k
).
REFERENCES:
patent: 5446747 (1995-08-01), Berrou
patent: 5721745 (1998-02-01), Hladik et al.
patent: 5734962 (1998-03-01), Hladik 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: 6226773 (2001-05-01), Sadjadpour
patent: 6343368 (2002-01-01), Lerzer
patent: 6400290 (2002-06-01), Langhammer et al.
patent: 6477679 (2002-11-01), Such et al.
patent: 6516437 (2003-02-01), Van Stralen et al.
patent: 6516444 (2003-02-01), Tsuguo
patent: 6526539 (2003-02-01), Yano et al.
Valenti et al., “Performance of Turbo Codes in Interleaved Flat Fading Channels with Estimated channel State Information”.
Hall et al., “Turbo Codes for Noncoherent Channels”.
Bahl et al., “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”; IEEE Transactions on Information Theory, Mar., 1974, pp. 284-287.
Berrou et al.; “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”; IEEE Transactions on Communications, vol. 44, No. 10, Oct. 1996, pp. 1261-1271.
CAS 5093 Turbo-Code CODEC; comatlas.
Turbo Code Project Page; www.ie.cuhk.edu.hk.
MAP04T Very High Speed MAP Decoder; Product Specification; Small World Communications, Oct. 25, 1999 (Version 1.0).
AHA4501 Astro Turbo product Code Evaluation Module, Product Summary; Efficient Channel Coding, Inc., 1999.
Technical Description of Turbo Product Codes, Version 4.0; Efficient Channel Coding, Inc., Jun. 1999.
Bao Jay
Kobayashi Hisashi
Wang Duanyi
Baker Stephen M.
Brinkman Dirk
Curtin Andrew J.
Mitsubishi Electric Research Laboratories Inc.
LandOfFree
MAP decoding for turbo codes by parallel matrix processing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with MAP decoding for turbo codes by parallel matrix processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and MAP decoding for turbo codes by parallel matrix processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3122409