Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
2000-10-25
2004-07-06
Chin, Stephen (Department: 2634)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C375S262000
Reexamination Certificate
active
06760390
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a novel operator for decoding block and convolutional codes in digital communications systems and particularly for simplifying log-MAP decoding of block and convolutional codes. The operator, the avg* representation of a kernel operation, may allow log-MAP decoding of many information services. The invention also relates to a low-complexity implementation of generating an optimal log-likelihood ratio (LLR) for use in decoders such as block and convolutional decoders.
BACKGROUND OF THE INVENTION
Block and convolutional codes, which have been advantageous in digital communications systems, are among some techniques used to transport information reliably. A variety of methods can be used to decode block and convolutional codes and to recover the information. For example, one method is a Viterbi algorithm, which is a maximum-likelihood decoding method that minimizes the probability of word error. Since a word is comprised of a sequence of symbols (or bits), the Viterbi algorithm is often called a sequence estimator. The Viterbi algorithm however does not minimize the probability of symbol (or bit) error. Another method for decoding block and convolutional codes uses a maximum aposterio (MAP) principle. MAP decoders make optimum symbol-by-symbol decisions, as well as providing “soft” reliability information which, for example, is desired in concatenated decoding systems such as turbo decoders. A possible algorithm for MAP decoding is the Bahl, Cocke, Jelink, and Rajiv (BCJR) algorithm. While the BCJR algorithm is the most commonly used MAP algorithm, the BCJR algorithm however suffers several shortcomings that make it difficult for hardware and software implementations, e.g., the requirement for multiplications and exponentiations.
In general, a MAP decoder requires forward and backward generalized Viterbi recursions on the code trellis, requiring sums of products of probabilities. A MAP decoder also computes likelihood ratios that are based on the results of the forward and backward recursions. The log-MAP algorithm couches the MAP decoder in the logarithmic domain, eliminating exponentiations and turning the products into sums, but also turning the sums into operations of a complicated function (i.e., log-add). This complicated function is the kernel operation of the log-MAP decoder that dominates the overall decoder complexity, similar to the add-compare-select (ACS) operation in a conventional Viterbi decoder. In the art, the complicated function has been represented as the max* function, a maximization (max) operation plus a correction term. One common implementation method for the max* function computes the max and adds a correction term which is accessed from a lookup table. Although this method appears to be efficient, the table lookup may be too complex to implement in both software and hardware. For example, table lookups may cause pipeline stalls within processors. One sub-optimal implementation, known as a max-log-MAP function, omits the correction term (i.e., max instead of max*).
One class of block and convolutional codes is a turbo code, which is, for example, being proposed for third generation (3G) cellular services. The decoders for turbo codes (turbo decoders) can be difficult to implement because they are complex and because the decoder is iterative. For instance, complexity estimates for turbo decoding 3G services can prohibit optimal (MAP or log-MAP) decoding of the constituent codes that comprise a turbo code. Although a sub-optimal algorithm such as the max-log-MAP or Soft Output Viterbi Algorithm (SOVA) may be used to meet the complexity constraints, either the decoder performance suffers from not using the optimal algorithm or number of iterations required to meet a specified performance increases. Therefore, there is a need for an algorithm that allows computationally efficient log-MAP decoding.
Many current (EDGE, iDEN) and most future (1XTREME, HDR, 4G) communication systems are employing higher-order modulations (8PSK, 16QAM, 64QAM, etc) in order to improve system spectral efficiency. Soft-decision decoding in these systems is complicated by the need for soft values for each encoded bit, rather than each symbol. Soft-decision decoding is necessary because of improved reliability to voice and data (up to 2 dB) and it facilitates advanced decoding techniques such as turbo codes and hybrid ARQ. The optimal soft value for bit k of a received symbol y, for any set of possible modulated (transmitted) symbols X, is:
ln
(
p
(
y
|
x
,
x
∈
X
0
)
p
(
y
|
x
,
x
∈
X
1
)
)
=
ln
(
∑
X
0
p
(
y
|
x
)
∑
X
1
p
(
y
|
x
)
)
,
(
1
)
where x is a modulated symbol, X
i={x|x
k
=i}, and x
k
is the corresponding k
th
bit of the modulated symbol index for x, and all symbols are equally probable. Because equation (1) is complex to implement, sub-optimal methods of generating soft values are employed. The current method of generating soft values is the dual-min,
K
(
min
X
1
d
1
2
-
min
X
0
d
0
2
)
,
where K is a scale factor proportional to the signal-to-noise ratio (SNR), X
1
is the set of constellation points with a “1” in the desired bit position, and X
0
is the set of constellation points with a “0” in the desired bit position. The term d
1
2
(d
0
2
) is the squared Euclidean distance from the received symbol to the constellation symbol with a 1 (0) in the desired position. The dual-min essentially compares the received symbol to all possible transmitted symbols, and assigns a soft value based only on the closest symbol with a 0 and the closest symbol with a 1 in that bit position. The dual-min is much easier to implement than the optimal method, but it unfortunately suffers a performance degradation from the optimal method.
Thus, there is also a need for a low-complexity, high-performance method of generating bit soft values from higher-order modulation symbols.
REFERENCES:
patent: 5442627 (1995-08-01), Viterbi et al.
patent: 6304996 (2001-10-01), Van Stralen et al.
patent: 6381728 (2002-04-01), Kang
patent: 6526539 (2003-02-01), Yano et al.
patent: 6625778 (2003-09-01), Nakamura et al.
patent: 2002/0034269 (2002-03-01), Demjanenko et al.
L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inform. Theory, vol. IT-20, pp. 284-287, Mar. 1974.
P. Robertson, E. Villebrun, and P. Hoeher, “A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain,” International Conference on Communications, pp. 1009-1013, Jun. 1995.
W. Gross and P. Gulak, “Simplified MAP algorithm suitable for implementation of turbo decoders,” Electronics Letters, vol. 34, No. 16, pp. 1577-1578, Aug. 1998.
S. Le Goff, A. Glavieux, and C. Berrou, “Turbo-codes and high spectral efficiency modulation,” International Conference on Communications, Jun. 1994.
V. Kuhn, “Evaluating the performance of turbo codes and turbo-coded modulation in a DS-CDMA environment,” IEEE Journal on Selected Areas of Communications, vol. 17, pp. 2138-2147, Dec. 1999.
Blankenship Thomas Keith
Classon Brian Keith
Desai Vipul Anil
Haas Kenneth A.
Motorola Inc.
LandOfFree
Log-map metric calculation using the avg* kernel does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Log-map metric calculation using the avg* kernel, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Log-map metric calculation using the avg* kernel will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3211142