Simplified block sliding window implementation of a map decoder

Details Simplified block sliding window implementation of a map decoder Simplified block sliding window implementation of a map decoder

1999-03-31

2003-05-13

Liu, Shuwang (Department: 2734)

Pulse or digital communications

Pulse code modulation

C375S262000, C375S265000, C375S340000, C375S341000, C714S792000, C714S794000, C714S795000, C714S796000

Reexamination Certificate

active

06563877

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to digital transmission systems and, in particular, to Maximum Posteriori Probability (MAP) and similar decoders that use a sliding window technique.
BACKGROUND OF THE INVENTION
Of most interest to this invention are digital transmission systems where a received signal from a channel is a sequence of wave forms whose correlation extends well beyond T, the signaling period. There can be many reasons for this correlation, such as coding, intersymbol interference, or correlated fading. It is known that an optimum receiver in such situations cannot perform its decisions on a symbol-by-symbol basis, so that deciding on a particular information symbol U
k
involves processing a portion of the received signal T
d
seconds long, with T
d
>T. The decision rule can be either optimum with respect to a sequence of symbols, or with respect to the individual symbol, U
k
.
Reference can be had to a journal article entitled “Soft-Output Decoding Algorithms in Iterative Decoding of Turbo Codes”, S. Benedetto et al., TDA Progress Report 42-124, pp. 63-87, Feb. 15, 1996 (incorporated by reference herein), wherein the authors report that the most widely applied algorithm for the first kind of decision rule is known as the Viterbi algorithm. In an optimum formulation of the Viterbi algorithm it is required to wait for decisions until an entire sequence has been received. In practical implementations, this drawback is overcome by anticipating decisions (single or in batches) on a regular basis with a fixed delay, D. A choice of D five to six times the memory of the received data is widely recognized as presenting a good compromise between performance, complexity, and decision delay.
Optimum symbol decision algorithms base their decisions on the maximum a posteriori probability (MAP). This class of algorithms has been known for several decades, although they are generally much less popular than the Viterbi algorithm, and are not commonly applied in practical systems. One reason for this is that the MAP algorithms typically yield performance in terms of symbol error probability that is only slightly superior to the Viterbi algorithm, yet they present a much higher complexity. Recently, however, interest in these algorithms has increased in connection with the problem of decoding concatenated coding schemes.
Concatenated coding schemes (a class which may include product codes, multilevel codes, generalized concatenated codes, and serial and parallel concatenated codes) were first proposed by Forney (G. D. Forney, Jr., “Concatenated Codes”, Cambridge, Mass., MIT, 1966) as a means of achieving large coding gains by combining two or more relatively simply “constituent” codes. The resulting concatenated coding scheme is a powerful code endowed with a structure that facilitates decoding, such as by using so-called stage decoding or iterated stage decoding.
In order to function properly these decoding algorithms cannot limit themselves to simply passing the symbols decoded by an inner decoder to an outer decoder. Instead they need to exchange some kind of soft information. As was proved by Forney, an optimum output of the inner decoder should be in the form of the sequence of the probability distributions over the inner code alphabet conditioned on the received signal, the a posteriori probability (APP) distribution. There have been several attempts to achieve, or at least approach, this goal. Some of these approaches are based on modifications of the Viterbi algorithm so as to obtain at the decoder output some reliability information, in addition to the “hard”-decoded symbols. This has led to the concept of an “augmented-output,” or the list-decoding Viterbi algorithm, and to the soft-output Viterbi algorithm (SOVA). However, these approaches can be suboptimal, as they are unable to supply the required APP. A different approach employs the original symbol MAP decoding algorithms with the aim of simplifying them to a form suitable for implementation. Of particular interest are soft-decoding algorithms as a main building block of an iterative stage decoding of parallel concatenated codes. These algorithms are particularly interesting since the advent of the so-called turbo codes (C. Berrou et al., Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes”, Proceedings of ICC'93, Geneva, pp. 1064-1070, May 1993). These codes are parallel concatenated convolutional codes (PCCC) whose encoder is formed by two (or more) constituent systematic encoders joined through an interleaver. In this approach the input information bits feed the first encoder and, after having been interleaved by the interleaver, enter the second encoder. The codeword of the parallel concatenated code includes the input bits to the first encoder followed by the parity check bits of both encoders. Generalizations to more than one interleaver and two parallel concatenated convolutional codes are possible.
The suboptimal iterative decoder is modular and contains a number of equal component blocks formed by concatenating soft decoders of the constituent codes (CC), separated by the interleavers used at the encoder side. By increasing the number of decoding modules and, thus, the number of decoding iterations, bit-error probabilities as low as 10
−5
at E
b
/N
o
=0.0 dB for rate 1/4 PCCC have been shown by simulation. A version of turbo codes employing two eight-state convolutional codes as constituent codes, an interleaver of 32×32 bits, and an iterative decoder performing two and one-half iterations with a complexity of the order of five times the maximum-likelihood (ML) Viterbi decoding of each constituent code is presently available on a chip, yielding a measured bit-error probability of 0.9×10
−6
at E
b
/N
o
=3 dB. Upper bounds to the ML bit-error probability of PCCCs have been proposed. As a by-product, it has been shown by simulation that iterative decoding can approach quite closely the ML performance. The iterative decoding algorithm is a simplification whose regular steps and limited complexity seem quite suitable to very large-scale integration (VLSI) implementation. Simplified versions of the algorithm have been proposed and analyzed in the context of a block decoding strategy that requires trellis termination after each block of bits. A similar simplification has been used for a hardware implementation of the MAP algorithm.
In an article entitled “Multiple Output Sliding Window Decoding Algorithm for Turbo Codes”, Proc. CISS 1996, Baltimore Md., pp. 515-520 (incorporated by reference herein), J. Yuan et al. report on a previous sliding window MAP decoding algorithm (SW-BCJR, where BCJR indicates the original authors), in which the decoder operates on a fixed memory span and APP outputs are forced with a given delay. This approach is said, however, to dramatically increase the required computation relative to the non-windowed MAP algorithm.
More particularly, these authors show that the non-windowed MAP algorithm requires that the entire sequence must be received before starting the decoding process. In order to avoid this delay, and to reduce memory requirements, the sliding window approach operates with a fixed memory span D, which is small compared to the frame or block size. While saving both memory and delay, it is also shown that the sliding window MAP algorithm must, at every time index k, in order to obtain the probability of the state of the encoder at state S
i
, conditioned on future received symbols (B
k
(S
i
)), recursively backwards compute for the entire sliding window length, as opposed to once for the entire frame length for the non-windowed MAP algorithm. In this regard a term á
k
(S
i
) is the probability of the state S
i
of the encoder at time k conditioned on the past and current received symbols, &agr;
k
(S
i
,u
k
) is the a posterior transition probability from state S
i
at time k and encoder data input u
k
, and &Ggr;
k
(x) is the joint probability of the channel input symbol x
k
and channel ou

Affiliated with

Also associated with

Rating

Simplified block sliding window implementation of a map decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Simplified block sliding window implementation of a map decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simplified block sliding window implementation of a map decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3012476