Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1997-11-26
2001-07-03
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S786000, C714S792000, C714S794000
Reexamination Certificate
active
06256764
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for error correcting codes in general, and in particular to a method and system for decoding convolutional codes. Still more particularly, the present invention relates to a method and system for decoding tailbiting convolutional codes.
2. Description of the Prior Art
Information signals communicated between a transmitter and a receiver via a communication channel can be corrupted by various noises associated with the channel. Thus, a technique known as error correction coding is typically employed to mitigate the effects of channel noises within a communication channel. By introducing redundancy in the information signals to be communicated, channel coding can reduce the likelihood of channel noise corrupting the information signals. In most cases, the technique of channel coding has been proven to be quite successful, even for long distance communications such as between a base station on Earth to a spacecraft approaching a distant planet.
Convolutional codes are a class of error correcting codes that are well-known in the art for mitigating the effects of channel noise. One example of such convolutional codes, which has been adopted as a standard for North American digital cellular radio communications, is known as IS-130 by the International Telecommunication Union. IS-130 employs a type of convolutional code that is also known in the art as a tailbiting convolutional code, in which a frame or block of information is encoded and communicated in a blockwise manner. The term tailbiting refers to the fact that the convolutional encoder begins and ends in the same encoding state. Although the decoder is aware that the encoder begins and ends in the same encoding state, the decoder is unaware of the value of that state. In other words, the initial encoding state of the encoder is unknown to the decoder; and in fact, for arbitrary data, the encoder may have started in any of the possible states with approximately the same probability. Hence, the fundamental difficulty encountered in designing a decoder for tailbiting convolutional codes is that the decoder must be capable of determining the initial encoding state of the encoder in a very short time.
In the prior art, a maximum-likelihood decoder, better known as a Viterbi decoder, may be utilized for decoding tailbiting convolutional codes. A Viterbi decoder decodes an actual corrupted sequence of received signals by finding the most likely sequence of uncorrupted signals. Similar to other types of decoders, a Viterbi decoder is also unaware of an encoder's starting state, hence the Viterbi decoder must perform Viterbi decoding exhaustively for all possible starting states. Although the outcome is always correct, this method is unacceptably slow for many applications. For example, if the number of the storage elements in the encoder is K, the time to decode is always 2
K
longer than that of the encoder's non-tailbiting counterpart. As a result, a Viterbi decoder places great demands on computational resources. Needless to say, it would be desirable to provide an improved technique for decoding tailbiting convolutional codes, which yields good levels of error protection with less computational burden.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore an object of the present invention to provide an improved method and system for decoding error correcting codes.
It is another object of the present invention to provide an improved method and system for decoding convolutional codes.
It is yet another object of the present invention to provide an improved method and system for decoding tailbiting convolutional codes.
In accordance with the method and system of the present invention, a tailbiting convolutional code is encoded by a convolutional encoder having multiple encoding states. A first starting score is assigned to each of the encoding states. A Viterbi algorithm is then performed once on the tailbiting convolutional code to associate an ending score with each of the encoding states. A subset of these encoding states is subsequently selected, within which the ending score of each encoding state meets a certain criterion. The Viterbi algorithm is again performed on the tailbiting convolutional code for each encoding state within the subset to determine the best encoding state as the most likely initial encoding state for the tailbiting convolutional code. A Trellis path of this most likely initial encoding state is utilized to decode the tailbiting convolutional code.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5159610 (1992-10-01), Eyuboglu et al.
patent: 5208816 (1993-05-01), Seshardi et al.
patent: 5287374 (1994-02-01), Parr
patent: 5349589 (1994-09-01), Chennakeshu et al.
patent: 5355376 (1994-10-01), Cox et al.
patent: 5475388 (1995-12-01), Gormish et al.
patent: 5615286 (1997-03-01), Patel
patent: 5721745 (1998-02-01), Hladik et al.
patent: 5721746 (1998-02-01), Hladik et al.
patent: 5935270 (1999-08-01), Lin
Howard H. Ma et al., “On Tail Biting Convolutional Codes,” IEEE Transactions on Communications, vol. 34, No. 2, Feb. 1986, pp. 104-110.
Richard Cox et al., “An Efficient Adaptive Circular Viterbi Algorithm for Decoding Generalized Tailbiting Convolutional Codes,” IEEE Transactions on Vehicular Technology, vol. 43, No. 1, Feb. 1994, pp. 57-68.
Qiang Wang et al., “An Efficient Maximum Likelihood Decoding Algorithm for Generalized Tail Biting Convolutional Codes Including Quasicyclic Codes,” IEEE Transactions on Communications, vol. 37, No. 8, Aug. 1989, pp. 875-879.
IEEE Transactions On Communications, vol. 32, No. 3, Mar. 1984, pp. 315-319.
IEEE Transactions On Information Theory, vol. 25, No. 1, Jan. 1979, pp. 97-100.
Bracewell & Patterson L.L.P.
Crane John D.
De'cady Albert
Nortel Networks Limited
Ton David
LandOfFree
Method and system for decoding tailbiting convolution codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for decoding tailbiting convolution codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for decoding tailbiting convolution codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2500382