Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
2000-02-14
2003-06-17
Bocure, Tesfaldet (Department: 2631)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
Reexamination Certificate
active
06580769
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to convolutional decoders and more particularly to convolutional decoders with forward and backward recursion, such as soft decision output decoders and methods.
BACKGROUND OF THE INVENTION
Soft decision output decoders, such as maximum a posteriori (MAP) decoders are known for use with convolutional codes to decode symbols that represent transmitted information, such as voice, video, data or other information communicated over wireless communication link. Convolutional decoders with forward and backward recursion are known and sometimes used to decode the constituent recursive convolutional codes used in turbo codes. Such decoders perform recursive decoding which uses soft decision information from one pass of a MAP algorithm as input to a next pass of a MAP algorithm to obtain a best estimate of transmitted information data as determined from decoded symbols. As known in the art, in the MAP algorithm, the forward recursion evaluates the joint probability of the state at time t and the received data through time t. The backward recursion computes the probability of the received data from time t to the end of the frame given the state at time. Hence, the computation of this probability for backward recursion decoders typically starts from an end of a frame. The MAP decoder is described, for example, in an article entitled “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate” by L. R. Bahl et al., published IEEE Transactions on Information Theory, March 1974. One application of this MAP decoder can be found in “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes”,: by C. Berrou et al., Proceedings of ICC '93, Geneva, Switzerland, pp. 1064-1070, May, 1993, incorporated herein by reference.
For decoding of turbo codes, for example, such as in code division multiple access (CDMA) wireless communication systems, decoding of recursive convolutionally coded information bits requires the determination of the following state in a trellis given a present state, and the input bit, such as a hypothetical information bit. Some decoding algorithms, such as the MAP algorithm, update the trellis in a backward as well as in a forward direction so that it is necessary to determine the next state of the coder (encoder) (the state at time n+1 for forward recursion, and the state at time n−1 for backward recursion) given the present state (at n) and the input bit. This operation is typically performed for every state in the trellis and it is therefore important that this process be done in an efficient manner.
Given the current state &sgr;
n
of the M element shift register, defined as
&sgr;
n
=(&sgr;
n
0
,&sgr;
n
1
, . . . ,&sgr;
n
M−1
)
and input bit u
n
, the next state of the forward recursion can easily be calculated by clocking the shift register to give
&sgr;
n+1
=(u
n
⊕f
n
,&sgr;
n
0
, . . . ,&sgr;
n
M−2
)
where the feedback bit f
n
is defined as the modulo-2 addition of those shift register elements specified in the feedback polynomial g
f
. A more difficult problem is finding &sgr;
n−1
, the next state of the backward recursion given &sgr;
n
and u
n
where,
&sgr;
n−1
=(&sgr;
n−1
0
,&sgr;
n−1
1
, . . . ,&sgr;
n−1
M−1
)
One solution is to use a lookup table that provides the next state for each state and input bit. This requires a precomputed
2
M+1
by M bit look up table. However, such look up tables utilize scarce memory and require additional complexity to generate the look up tables.
Accordingly, a need exists for a more efficient recursive convolutional decoder that can avoid the use of such a look up table.
REFERENCES:
patent: 4972475 (1990-11-01), Sant'Anselmo
patent: 6028899 (2000-02-01), Petersen
patent: 6161209 (2000-12-01), Moher
Brown Tyler
Wang Michael M.
Bocure Tesfaldet
Burd Kevin M
Haas Kenneth A.
May Steven A.
Motorola Inc.
LandOfFree
Method and apparatus for backward recursion next state... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for backward recursion next state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for backward recursion next state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3107262