Normalization implementation for a logmap decoder

Details Normalization implementation for a logmap decoder Normalization implementation for a logmap decoder

2000-02-23

2002-06-04

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

With error detection or correction

C714S796000, C714S795000, C714S788000

Reexamination Certificate

active

06400290

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to a hardware implementation of the log Maximum A Posteriori (MAP) probability algorithm. More specifically, this invention relates to a programmable logic device that can be programmed to configure its logic elements to approximate the normalization of probability values used in the operation of logMAP decoders.
Programmable logic devices (“PLDs”) typically include (1) many regions of programmable logic, and (2) programmable interconnection resources for selectively conveying signals to, from, and/or between those logic region's. Each logic region is programmable to perform any of several different, relatively simple logic functions. The interconnection resources are programmable to allow the logic regions to work together to perform much more complex logic functions than can be performed by any individual logic region. Examples of known PLDs are shown in U.S. Pat. Nos. 3,473,160, Re. 34,363, 5,689,195 and 5,909,126, and U.S. patent application Ser. No. 09/266,235, all of which are hereby incorporated by reference herein in their entireties.
One of the functions that can be implemented in a PLD is a log Maximum a Posteriori (logMAP) decoder, as used in turbo decoding. Turbo codes are a relatively recent coding and decoding technique that makes use of an iterative decoding scheme. Developed in,the early 1990s, turbo coding allows highly reliable data communication at signal-to-noise ratios very near the Shannon limit, which is defined as the minimum signal-to-noise ratio needed to communicate reliably over a given communication medium at a given spectral (bandwidth) efficiency. Turbo codes are described in a paper by C. Berrou entitled, “Near Shannon Limit Error Correcting Coding and Decoding: Turbo Codes,” Proceedings of ICC '93, Geneva, Switzerland, pp. 1064-1070, May 1993, and the iterative decoding scheme is described in J. Hagenauer's “Iterative (Turbo) Decoding of Systematic Concatenated Codes with MAP and SOVA Algorithms,” Proceedings of the ITG Conference on Source and Channel Coding, Frankfurt Germany, pp. 1-9, October 1994.
The fundamental concept of a logMAP decoder is that it is a machine that determines the state (path) metrics and branch metrics of a given encoder. State metrics are defined as the probability that any state in the trellis is reached at any given time, while the branch metric is defined as the probability that any particular branch was traversed at any given time in the trellis. A trellis is a term which describes a tree in which a branch not only bifurcates into two or more branches but also in which two or more branches can merge into one. A trellis diagram is an infinite replication of the state diagram for an encoder. The nodes (states) at one level in the trellis are reached from the node states of the previous level by transitioning through one branch, as determined by the state diagram.
In the present invention, the state and branch metrics are represented by &agr;, &bgr;, and &ggr;. Alpha (&agr;) represents the forward state metric and is defined as the probability that any state will be reached during the forward path through the MAP decoder. Its counterpart, &bgr;, is the backward state metric and is defined as the probability that any state will be reached in a backward recursion through the MAP decoder. Gamma (&ggr;) is the branch metric and is defined as the probability that any given branch of the trellis will be traversed at any given time. For practical implementation, the calculation can be calculated in the logarithmic domain. This means that all multiplication becomes addition and division becomes subtraction. The normalization of &agr; values, normally a division operation in the MAP decoder, thus becomes a subtraction operation in the logMAP decoder.
Fixed point hardware implementation requires that the &agr; and &bgr; probabilities must be normalized to prevent overflow. One known method suggests that &agr; values are normalized by deducting the largest &agr; value from all &agr; values generated in the trellis at any time. Typically, this is a multi-logic level operation, with the number of logic levels dependent on the constraint length of the logMAP decoder. In the first level of the comparison operation, pairs of &agr; values are fed into a maximum value selection circuit where they are inputted into a comparator and a multiplexer (MUX). The MUX utilizes the output of the comparator to output the larger of the two &agr;s. These values are in turn paired and fed into another level of maximum value selection circuits which each outputs the larger of the two input values. This continues until the largest &agr; has been isolated. The maximum &agr; is then deducted from all the &agr; values generated in the trellis. This means that the largest normalized value will be “0”. Because the &agr; values represent the probabilities of any state in the trellis being reached, this normalization also ensures that the sum of the probabilities of all states in the trellis being reached must approximate unity, where unity (or 1.0) is the ideal sum of all states after normalization. A floor is normally used to prevent underflow.
The primary drawback of this method, however, is that N
s
−1 comparisons have to be made in order to isolate the largest &agr;, where N
s
=2
(L−1)
and is defined as the number of states in the trellis of the logMAP decoder, and L, the constraint length, is defined as the number of memory elements used during the coding. Even when implemented as a tree, log
2
(N
s
) levels of comparison are required in determining the largest &agr;. In programmable logic, each level of compare requires two levels of logic: one for the comparator, and one for the 2:1 multiplexer which selects the larger value. Thus the determination of the largest &agr; often comprises the largest logic requirement in the logMAP decoder, as well as the largest component of the propagation delay in the critical path of the decoder.
It would be desirable to provide a method of normalization utilizing programmable logic devices in which the logic requirements are greatly reduced without degrading the performance of the logMAP decoder.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a programmable logic device that can be programmed to configure its logic elements to approximate the normalization of probability values used in the operation of logMAP decoders, thereby significantly reducing the number of logic levels required in the normalization operation. Such reduction is projected to increase decoder speeds of three times over known processes, without significantly degrading accuracy. Indeed, the increased decoder speeds may allow for an increased number of iterations within the turbo decoder utilizing the logMAP decoder that may result in greater accuracy than known systems. Thus, this invention takes advantage of the fact that the logMAP and MAP decoders are found to work even if the state metrics are not precisely normalized after every calculation. Instead, an approximate normalization is used which greatly reduces the level of logic resources.
In a preferred embodiment, the &agr; probabilities are approximately normalized by calculating an approximate normalization value which is then deducted from all &agr; values in the trellis at any time. Because the approximate normalization value can only be positive, all negative &agr; values are necessarily excluded from the comparison by logically ANDing the most significant bit (MSB) of each &agr; with the NOT of its own MSB. The resulting bits are then all bitwise ORed together, thus approximating a single normalization value. This approximate normalization value is then fed into a subtraction circuitry which subtracts the approximate normalization value from all &agr; values and outputs the desired normalized &agr; values.
In the case of programmable logic devices, one logic level is what will fit into a four-input look-up table, or a new level of logic starts after a carry. Examples of functio

Affiliated with

Also associated with

Rating

Normalization implementation for a logmap 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 Normalization implementation for a logmap decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Normalization implementation for a logmap decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2952784