Pulse or digital communications – Systems using alternating or pulsating current – Plural channels for transmission of a single pulse train
Reexamination Certificate
1999-09-03
2002-01-29
Chin, Stephen (Department: 2634)
Pulse or digital communications
Systems using alternating or pulsating current
Plural channels for transmission of a single pulse train
C375S262000, C375S264000, C375S265000, C375S341000, C714S792000, C714S795000, C714S796000
Reexamination Certificate
active
06343103
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to communication systems and, more particularly, to decoding techniques for use in such systems.
BACKGROUND OF THE INVENTION
Convolutional codes and bandwidth efficient Trellis Coded Modulation (TCM) are widely used in many different types of communication systems, including voice-band modems, Asymmetric Digital Subscriber Line (ADSL) systems, audio broadcasting systems, Fast or Gigabit Ethernet systems, cellular systems and wireless local loop systems. Convolutional codes are described in, e.g., G. C. Clark, Jr. and J. B. Cain, “Error Control Coding for Digital Communications,” New York: Plenum, 1981, and TCM is described in, e.g., G. Ungerboeck, “Trellis-coded modulation with redundant signal sets part I,” IEEE Communications Magazine, Vol. 25, February 1987, and G. Ungerboeck, “Trellis-coded modulation with redundant signal sets part II,” IEEE Communications Magazine, Vol. 25, February 1987.
The Viterbi algorithm is an efficient maximum-likelihood sequence detection method for decoding convolutional and trellis codes transmitted over Additive White Gaussian Noise (AWGN) channels. The Viterbi algorithm is described in, e.g., A. J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Trans. on Information Theory, Vol. IT-13, April 1967, G. D. Forney, Jr., “Maximum-likelihood sequence detection in the presence of intersymbol interference,” IEEE Trans. on Information Theory, Vol. IT-18, pp. 363-378, May 1972, and G. D. Forney, Jr., “The Viterbi algorithm,” IEEE Proceedings, Vol. 61, pp. 268-278, March 1973. The Viterbi algorithm is currently used, almost exclusively, for decoding these codes in all practical applications. It is also known that for Rayleigh fading channels, if the Channel State Information (CSI) is known, the Viterbi Algorithm can still be the optimum detection method for detecting these codes, with minor modifications, as described in, e.g., E. Biglieri, D. Divsalar, P. J. McLane and M. K. Simon, “Introduction to Trellis-Coded Modulation with Applications,” New York, N.Y.: Macmillan Publishing Company, 1991.
The Viterbi algorithm finds the most-likely codeword sequence in a code, as described by a trellis diagram, given a particular sequence of noisy symbols at the channel output. It is an application of dynamic programming and the search for the optimum path is done recursively. In the Viterbi algorithm for decoding convolutional and trellis codes, square Euclidean distance is the optimum branch metric for decoding sequences transmitted in AWGN channels and in Rayleigh fading channels when CSI is appropriately included.
Multiplications are generally required in the Viterbi algorithm only to compute the square Euclidean distances to obtain branch metrics associated with branches of the trellis. Look-up tables may also be used to obtain the square Euclidean distances. Depending on the trellis to be implemented, a typical look-up table can have a size of at least 2
9
×9~4 k bits. For high bit-rate applications, parallel branch metric computations may be required. Duplications of multipliers or look-up tables to implement parallel branch metric computation can increase the decoder complexity tremendously, making such arrangements prohibitive for high bit-rate applications. Furthermore, the multipliers and the delay associated with accessing large look-up tables can become a processing bottleneck for a fully pipelined Viterbi decoder in high bit-rate applications.
As an alternative, absolute distances have been proposed for use as branch metrics. However, the use of absolute distances as branch metrics has the undesirable effect of reducing the performance of the Viterbi decoder. See H. Lou, “Implementing the Viterbi algorithm. Fundamentals and real-time issues for processor designers,” IEEE Signal Processing Magazine, Vol. 12, pp. 42-52, September 1995.
A need therefore exists for a more efficient branch metric representation, which simplifies the decoder without compromising its performance.
SUMMARY OF THE INVENTION
The present invention provides an improved branch metric representation, based on linear distances, that overcomes the above-described decoder complexity problems of the prior art, while simultaneously avoiding any significant degradation in decoder performance.
An illustrative embodiment of the invention for decoding a sequence of received symbols includes a branch metric calculation unit, an add-compare-select unit, and a traceback unit. The branch metric unit computes branch metrics associated with transitions between states of a multi-stage trellis representation of a state machine. In accordance with the invention, each of the branch metrics correspond to a linear distance between a given one of the received symbols and its nearest codeword in a given stage of the trellis. The add-compare-select unit utilizes the branch metrics of a current stage, along with a previously-generated path metric, for comparison purposes in determining a survivor path and corresponding updated path metric for a current stage of the multi-stage trellis. The traceback unit utilizes the updated path metric to generate a corresponding decoded output.
Advantageously, the decoder is configured such that it achieves a level of performance using the linear distance branch metrics which is equivalent to that achieved using squared distance branch metrics, while the decoder complexity is reduced through the elimination of multiplication operations. More particularly, the invention allows adders rather than multipliers or large look-up tables to be used to obtain the branch metrics, thereby considerably simplifying the decoder. The techniques of the invention are suitable for use with convolutional and trellis codes for a variety of different modulation constellations, such as, e.g., QPSK (Quadrature Phase Shift Keying), 8-PSK (Phase-Shift-Keying), 16-QAM (Quadrature Amplitude Modulation), 32-QAM and larger constellations.
REFERENCES:
patent: 5727029 (1998-03-01), Jeon et al.
patent: 5881075 (1999-03-01), Kong et al.
patent: 5933462 (1999-08-01), Viterbi et al.
patent: 6141384 (2000-10-01), Wittig et al.
G. Ungerboeck, “Trellis-Coded Modulation with Redundant Signal Sets, Part I: Introduction,” IEEE Communications Magazine, vol. 25, No. 2, pp. 5-11, Feb. 1987.
G. Ungerboeck, “Trellis-Coded Modulation with Redundant Signal Sets, Part II: State of the Art,” IEEE Communications Magazine, vol. 25, No. 2, pp. 12-21, Feb. 1987.
A.J. Viterbi, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,” IEEE Trans. on Information Theory, vol. IT-13, No. 2, pp. 260-269, Apr. 1967.
G.D. Forney, Jr., “Maximum-Likelihood Sequence Detection in the Presence of Intersymbol Interference, ” IEEE Trans. on Information Theory, vol. IT-18,No. 3, pp. 363-378, May 1972.
G.D. Forney, Jr., “The Viterbi Algorithm,” IEEE Proceedings, vol. 61, No. 3, pp. 268-277, Mar. 1973.
H. Lou, “Implementing the Viterbi Algorithm. Fundamentals and real-time issues for processor designers,” IEEE Signal Processing Magazine, vol. 12, pp. 42-52, Sep. 1995.
A.J. Viterbi, “A Pragmatic Approach to Trellis-Coded Modulation,” IEEE Communications Magazine, pp. 11-19, Jul. 1989.
Lou Hui-Ling
Urbanke Rudiger L.
Agere Systems Guardian Corp.
Ha Dac V.
Ryan & Mason & Lewis, LLP
LandOfFree
Methods and apparatus for representation of branch metrics... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for representation of branch metrics..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for representation of branch metrics... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2843990