Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-08-03
2004-06-29
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06757701
ABSTRACT:
FIELD OF THE INVENTION
Apparatus and method for implementing a linearly approximated Log MAP algorithm and especially an apparatus and method for implementing a linearly approximated Log MAP algorithm for turbo decoding and turbo equalization.
BACKGROUND OF THE INVENTION
Turbo Coding (i.e.—TC) is used for error control coding in digital communications and signal processing. The following references give some examples of various implementations of the TC: “Near Shannon limit error correcting coding and decoding: turbo-codes”, by Berrou, Glavieux, Thitimajshima, IEEE International Conference of Communication. Geneva Switzerland, pp. 1064-1070, May 1993; “Implementation and Performance of a Turbo/MAP Decoder”, Pietrobon, International Journal of Satellite Communication; “Turbo Coding”, Heegard and Wicker, Kluwer Academic Publishers 1999.
MAP algorithm and soft output Viterbi algorithm (SOVA) are Soft Input Soft Output (i.e.—SISO) decoding algorithms that have gained wide acceptance in the area of communications. Both algorithms are mentioned in U.S. Pat. No. 5,933,462 of Viterbi et al.
The TC has gained wide acceptance in the area of communications, such as in cellular networks, modems, and satellite communications. Some turbo encoders consists of two parallel-concatenated systematic convolutional encoders separated by a random interleaver. A turbo decoder has two soft-in soft-out (SISO) decoders. The output of the first SISO is coupled to the input of the second SISO via a first interleaver, while the output of the second SISO is coupled to an input of the first SISO via a feedback loop that includes a deinterleaver.
A common SISO decoder uses either a maximum a posteriori (i.e.—MAP) decoding algorithm or a Log MAP decoding algorithm. The latter algorithm is analogues to the former algorithm but is performed in the logarithmic domain. Another common decoding algorithm is the max log MAP algorithm. The max log MAP is analogues to the log MAP but the implementation of the former involves an addition of correction factor. Briefly, the MAP finds the most likely information bit to have been transmitted in a coded sequence.
The output signals of a convolutional encoder are transmitted via a channel and are received by a receiver that has a turbo decoder. The channel usually adds noise to the transmitted signal.
During the decoding process a trellis of the possible states of the coding is defined. The trellis includes a plurality of nodes (states), organized in T stages, each stage has N=2sup(K−1) nodes, whereas T being the number of received samples taken into account for evaluating which bit was transmitted from a transmitter having the convolutional encoder and K is the constraint length of the code used for encoding. Each stage is comprised of states that represent a given time. Each state is characterized by a forward state metric, commonly referred to as alpha (&agr; or a) and by a backward state metric, commonly referred to as beta (&bgr; or b). Each transition from a state to another state is characterized by a branch metric, commonly referred to as gamma (&ggr;).
Alphas, betas and gammas are used to evaluate a probability factor that indicates which signal was transmitted. This probability factor is commonly known as lambda (A). A transition from a stage to an adjacent stage is represented by a single lambda.
A function MAX*(a(n),b(n)) is frequently used when alphas, betas and gammas are calculated. Conveniently, said calculation involves in a comparison of a(n) and b(n). Said elements a(n) and b(n) usually have real values. MAX*(a(n), b(n)) equals MAX(a(n), b(n))+Log(1+EXP{−|a(n)−b(n)|}). The first portion of said equation is usually calculated. The calculation of the second portion is relatively complicated and time consuming. Usually an approximation of said second portion is calculated. Said approximation is either a linear approximation, a step approximation or a multi step approximation. A linear approximation method is described in “Linearity Approximated for Log-MAP Algorithms for Turbo Decoding”, by Jung-Fu Cheng and Tony Ottoson. Said method suggests to approximate the second portion by a the following functions: MAX{0, (C−|a(n)−b(n)|/4} and by: MAX{0, (C−|a(n)−b(n)|/8}. Both estimations provide relatively poor performances when |a(n)−b(n)| is relatively small, and their implementation is relatively time consuming.
There is a need for providing a fast and high performance apparatus and method for implementing a linearly approximated Log MAP algorithm.
REFERENCES:
patent: 4748577 (1988-05-01), Marchant
patent: 5801974 (1998-09-01), Park
patent: 5933462 (1999-08-01), Viterbi et al.
patent: 5935200 (1999-08-01), Whittaker
patent: 5951629 (1999-09-01), Wertheim et al.
patent: 2003/0053566 (2003-03-01), He et al.
Yung-Fu Cheg, Tony Ottosson: “Linearly approximated log-map algorithms for turbo decoding”, 51stIEEE Vehicular technology conference proceedings, vol. 3, May 15-18 2000, pp. 2252-2256.
“Simplified log-map algorithm” research disclosure, Industrial opportunities Ltd. Havant, GB No. 421, May 1999, p. 612.
Robertson et al. “A comparision of optimal and sub-optimal map decoding algorithms operating in the log domain” proceedings of the conference on communications (ICC), US, New York, IEEE Jun. 18 1995 , pp. 1009-1013.
Aidan Fabrice
Leshin Gregory
Sivan Noam
LandOfFree
Apparatus and method for implementing a linearly... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for implementing a linearly..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for implementing a linearly... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3311355