Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reissue Patent
1999-05-04
2003-02-25
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S786000, C375S308000
Reissue Patent
active
RE038010
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to data communications. More particularly, the present invention relates to a novel and improved method and apparatus for encoding and decoding trellis modulated data based upon punctured convolutional codes.
II. Description of the Related Art
The field of data communications is concerned with raising the data throughput of a transmission system with a limited signal to noise ratio (SNR). The use of error correcting circuitry such as the Viterbi decoder allows system tradeoffs to be made with smaller SNRs or higher data rates to be used with the same bit error rate (BER). The decrease in the SNR needed is generally referred to as coding gain. Coding gain may be determined from bit error performance curves. In a graph of bit error performance curves, the BER of uncoded and various coded data is charted against E
b
/N
o
, where E
b
is the energy per bit and N
o
is the one sided Gaussian White Noise power spectral density. The coding gain at any point along a bit error performance curve for a particular BER level is determined by subtracting the coded E
b
/N
o
from the uncoded E
b
/N
o
. In the paper “Viterbi Decoding for Satellite and Space Communication”, by J. A. Heller and I. M. Jacobs, IEEE Transactions on Communication Technology, Vol. COM-19, pgs. 835-848, October 1971, extensive results of simulations on various decoder apparatus were reported.
The coding rate and constraint length are used to define the Viterbi decoder. The coding rate (m
) corresponds to the number of coding symbols produced (n) for a given number of input bit (m). The coding rate of ½ has become one of the most popular rates, although other code rates are also generally used. One class of codes with m≠1 are called punctured codes and are produced by discarding or erasing symbols from the rate 1
code. The constraint length (K) is related to the length of the conventional encoder used in the encoding of the data. A constraint length of K=7 is typical in convolutional coding schemes. The convolutional encoder can be thought of as a Finite Impulse Response (FIR) filter with binary coefficients and length K−1. This filter produces a symbol stream with 2
K−1
possible states.
The basic principal of the Viterbi algorithm is to take a convolutionally encoded data stream that has been transmitted over a noisy channel and use the properties of the convolutional code to determine the transmitted bit stream. The Viterbi algorithm is a computationally efficient method of updating the conditional probabilities of all 2
K−1
states and finding the most probable bit sequence transmitted. In order to compute this probability, all the conditional probabilities of 2
K−1
states for each bit must be computed. For a rate ½ code, the resulting decision from each of these computations is stored as a single bit in a path memory.
A chainback operation, an inverse of the encoding operation, is performed in which the p·2
K−1
decision bits are used to select an output bit, where p is the path memory depth. After many states the most probable path will be selected with a high degree of certainty. The path memory depth must be sufficiently long to allow this probability to approach 1. For a rate ½ code, an exemplary path memory depth is about (5·K), or 35 states. For a rate ⅞ punctured code the optimal depth increases to 96 states.
Constraint lengths of K less than 5 are too small to provide any substantial coding gain, while systems with K greater than 7 are typically too complex to implement as a parallel architecture on a single VLSI device. As the constraint length increases, the number of interconnections in a fully parallel computation section increases as a function of (2
K−1
·L), where L is the number of bits of precision in the state metric computations. Therefore, where K is greater than 7, serial computation devices are generally used which employ large external random access memories (RAMs).
In the paper “Channel Coding with Multilevel/Phase Signal” by G. Ungerboeck, IEEE Transactions on Information Theory, Vol. IT-28, pgs. 55-67, January 1982, a trellis coded modulation (TCM) was described. In Ungerboeck it was shown that within a given spectral bandwidth, it is possible to achieve an Asymptotic Coding Gain of up to 6 dB by employing a rate (n−1)
convolutional code and doubling the signal set. Unfortunately, for each modulation technique and for each bit rate, the maximal coding again is achieved by a different convolutional code. Further disclosed were the results of a search for all convolutional codes for several rates and modulation techniques, and the best codes presented.
In the paper “A Pragmatic Approach to Trellis-Coded Modulation” by A. J. Viterbi, J. K. Wolf, E. Zehavi and R. Padovani, IEEE Communications Magazine, pgs. 11-19, July 1989, a pragmatic approach to trellis coded modulation (PTCM) was disclosed. The underlying concept therein is that a somewhat lower coding gain is achievable by a PTCM based on the “industry standard” rate ½, K=7 convolutional code. Although a lower coding gain is realized, it is very close to the coding gain of Ungerboeck at BERs of interest.
Trellis coding is an attractive coding technique since it possesses an aspect which other coding techniques lack. The power of trellis coding lies in the fact that even though no apparent coding operation is performed on some of the bit(s) of the input data, the decoder is able to provide error correction on all bits. Generally the use of TCM techniques to achieve efficient use of power-bandwidth resources has been limited to low speed applications in digital signal processor implementations. The use of PTCM techniques enable VLSI implementations of an encoder/decoder capable of operating at high rates. A decoder using PTCM techniques is capable of handling different modulation techniques, such as M-ary phase-shift keying (M-ary PSK) including Binary PSK (BPSK), Quadrature PSK (QPSK), 8-PSK, and 16-PSK.
In the paper, “Development of Variable-Rate Viterbi Decoder and Its Performance Characteristics,” Sixth International Conference on Digital Satellite Communications, Phoenix Ariz., September 1983, Y. Yasuda, Y. Hirata, K. Nakamura and S. Otani discuss a method whereby a class of high rate binary convolutional codes can be constructed from a single lower rate binary convolutional code. The advantage of punctured codes for binary transmission is that the encoders and decoders for the entire class of codes can be constructed easily by modifying the single encoder and decoder for the rate ½ binary convolutional code from which the high rate punctured code was derived. The current invention will be concerned primarily with rate (m−1)/m binary convolutional codes (m a positive integer greater than or equal to 3) formed from puncturing a particular rate ½ convolutional code which has become a de-facto standard of the communications industry. This code has constraint length
7
and generator polynomials G
1
((D)=1+D
2
+D
3
+D
5
+D
6
and G
2
(D)=1+D+D
2
+D
3
+D
6
. Indeed, many commercial VLSI convolutional encoder and decoder chips (including a device marketed under Part No. Q1875 by QUALCOMM Incorporated of San Diego, Calif.) contain encoders and decoders for punctured binary codes using this de-facto standard rate ½ code.
It is therefore an object of the present invention to provide a novel method and circuitry for encoding and decoding trellis data using punctured rate ½ convolutional encoders.
SUMMARY OF THE INVENTION
The present invention is a novel and improved method and apparatus for encoding and decoding trellis modulated data based upon punctured rate ½ convolutional codes. In accordance with the present invention, a trellis encoder and decoder are disclosed in which a circuit is provided that encodes and decodes based upon punctured rate ½ convolutional
Wolf Jack K.
Zehavi Ephraim
Brown Charles D.
Pappas George C.
Qualcomm Incorporated
Ton David
Wadsworth Philip R.
LandOfFree
Trellis encoder and decoder based upon punctured rate... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Trellis encoder and decoder based upon punctured rate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trellis encoder and decoder based upon punctured rate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3146167