Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-06-01
2003-01-21
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S794000, C714S795000
Reexamination Certificate
active
06510536
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to max-log-APP decoding and is particularly concerned with max-log-APP decoder systems and methods suited for Turbo and Turbo-like forward-error-correcting codes, by using iterative processing.
BACKGROUND OF THE INVENTION
Claude Berrou obtained U.S. Pat. No. 4,446,747 entitled: “Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoder”. This patent describes essentially the same Turbo-code presented by Berrou et al in their paper “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes”, published in the Proceedings of ICC'93, Geneva, Switzerland, pp. 1064-1070, May, 1993. The Turbo-code presented, is a rate 1/2 binary code that provided performance within 0.5 dB of the BPSK capacity limit at a BER of 10
−5
, when using an interleaver block size of 65,536. This result is also only 0.7 dB from the more general Shannon capacity limit. The encoder consists of two rate 1/2 recursive systematic convolutional (RSC) encoders operating in parallel with the data binary digits (bits) interleaved between the two encoders as shown in FIG.
1
. Without puncturing, and with rate 1/2 constituent codes, the overall code rate is 1/3. This is because the systematic data bits only need to be sent once. Other code rates can be achieved as required by puncturing the parity bits c
1
i
and c
2
i
. In this configuration, the job of the interleaver is to spread reliability information that occurs in one code throughout the other code so that there is a higher probability of correcting unreliable information.
FIG. 2
shows the RSC encoder, with polynomials (23,35)
8
, used in the prior art TURBO4 codec as discussed in B. Talibart and C. Berrou, “Notice Preliminaire du Circuit Turbo-Codeur/Decodeur TURBO4”, Version 0.0, June, 1995. This RSC encoder has four memory (delay) units.
More recently Berrou, and Glavieux provided more discussion of the coding and decoding of Turbo-codes in their paper “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”, published in the IEEE Trans. on Comm., Vol. 44, No. 10, October 1996.
Soft-in/soft-out a posterior probability (APP) decoding of the systematic component codes is key to the decoding of Turbo-codes. This is also referred to as maximum a posterior (MAP) decoding in the literature. The so-called MAP algorithm was first derived by Bahl et al in their paper “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, published in IEEE Trans. on Inform. Theory, Vol. IT-20, pp. 284-287, March 1974. The APP terminology is more correct in the context of soft-in/soft-out iterative processing, and this is the terminology used here.
An APP decoder finds the probability of each data bit at each bit time given the entire received signal. Thus it also inherently provides the most likely bit value at each bit time given the entire received signal. This is in contrast to the well-known Viterbi algorithm, which performs maximum likelihood sequence estimation (MLSE) as discussed in A. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically optimum Decoding Algorithm”, IEEE Trans. Inform. Theory, Vol. IT-13, pp. 260-269, April 1967; and G. Forney, “The Viterbi Algorithm”, Proc. IEEE, Vol. 61, No. 3, pp. 268-278, March 1973. That is, the Viterbi algorithm finds the entire sequence that was most likely transmitted given the received signal. Both algorithms are optimum for their respective criteria, but the APP decoding approach more naturally provides the soft information required for iterative decoding. The relationship between these two decoding methods will be further explained below.
The following is a brief summary of the relevant background material required for understanding the invention. The APP, log-APP, and max-log-APP decoding algorithms are described. A more detailed description of these prior art algorithms is provided in, for example, L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Trans. on Inform. Theory, Vol. IT-20, pp. 284-287, March 1974; P. Robertson, E. Villebrun, and P. Hoeher, “A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain”, Proceedings of ICC'95, Seattle, pp. 1009-1013, June 1995; P. Robertson, P. Hoeher, and E. Villebrun, “Optimal and Sub-Optimal Maximum a Posteriori Algorithms Suitable for Turbo Decoding”, IEEE Communications Theory, Vol. 8, No. 2, pp. 119-125, March-April 1997. S. Pietrobon, “Implementation and Performance of a Turbo/MAP Decoder”, submitted to the International Journal of Satellite Communications, Feb. 21, 1997; J. Hagenauer, E. Offer, and L. Papke, “Iterative Decoding of Binary Block and Convolutional Codes”, IEEE Trans. on Inform Theory, Vol. 42, No. 2, pp. 429-445, March 1996; J. Erfanian, S. Pasupathy, G. Gulak, “Reduced Complexity Symbol Detectors with Parallel Structures for ISI Channels”, IEEE Trans. on Communications, Vol. 42, No. 2/3/4, pp.1661-1671, February/March/April 1994.
The decoding algorithms are presented in the context of systematic binary convolutional codes and an additive white Gaussian noise (AWGN) channel model. Of course this does not prevent their use in other systems with more complicated signaling constellations and channels. In the case of Turbo-codes, recursive systematic convolutional (RSC) codes are conventionally employed.
The prior art APP decoding algorithm is now described. The data bit at time i is denoted as d
i
and is either 0 or 1. The state of the RSC encoder at time i is determined by the contents of the encoder's shift-register before d
i
enters the encoder. Thus, data bit d
i
causes the state of the encoder to change from S
i
to S
i+1
. The initial state S
1
is usually set to zero. Here it is assumed that after K systematic bits the final state, S
K+1
, is also zero. In the case of RSC codes the last mem systematic bits are often reserved and specifically chosen to flush or terminate the encoder into the zero state, where mem is the memory of the RSC encoder. The number of states is N
s
=2
mem
. The usual approach with Turbo-codes is to terminate the first RSC code, interleave the data and flush bits, and then leave the second RSC code unterminated.
Assuming a rate 1/2 RSC encoder, as shown in
FIG. 2
for example, the outputs at time i are the systematic data bit d
i
and the coded parity bit c
i
. These outputs are typically modulated using an antipodal signaling scheme such as BPSK or QPSK and sent through an additive white Gaussian noise (AWGN) channel. The received sequence is defined as
R=[x
1
y
1
. . . x
i
y
i
. . . x
K
y
K
] (1)
where (x
i
, y
i
) is a pair of received signal samples at time i, and
x
i
=d
i
′+u
i
, d
i
′=1−2
d
i
(2)
y
i
=c
i
′+v
i
, c
i
′=1−2
c
i
(3)
where d′
i
and c′
i
are the corresponding data and parity symbols with ±1 values, and u
i
and v
i
are AWGN samples with variance &sgr;
2
. The likelihood ratio associated with each data bit at time i is given by
λ
i
=
Pr
(
d
i
=
0
❘
R
)
Pr
(
d
i
=
1
❘
R
)
(
4
)
where Pr(d
i
=d|R), d=0, 1 is the a posterior probability (APP) of the data bit d
i
. Once &lgr;
i
is evaluated, decisions can be made as follows
d
^
i
=
{
0
if
λ
i
≥
1
1
if
λ
i
<
1
(
5
)
The efficient method of calculating &lgr;
i
can be summarized as follows:
λ
i
=
∑
m
=
0
N
s
-
1
α
i
m
δ
i
0
,
m
β
i
+
1
f
(
0
,
m
)
∑
m
=
0
N
s
-
1
α
i
m
δ
i
1
,
m
β
i
+
1
f
(
1
,
m
)
(
6
)
where m is the state number and the summations are over all N
s
states. The &agr;'s and &bgr;'s are the forward and backward stat
Crozier Stewart N.
Gracie Ken
Guinand Paul
Hunt Andrew
Lodge John
Baker Stephen M.
Her Majesty the Queen in right of Canada as represented by the
Polster Lieder Woodruff & Lucchesi L.C.
LandOfFree
Reduced-complexity max-log-APP decoders and related turbo... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reduced-complexity max-log-APP decoders and related turbo..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced-complexity max-log-APP decoders and related turbo... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3061037