Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-06-02
2003-01-21
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S790000
Reexamination Certificate
active
06510538
ABSTRACT:
TECHNICAL FIELD
The invention relates to the decoding of encoded data. In particular, the invention concerns apparatus and a method for decoding received data which has been convolution encoded and punctured prior to transmission.
BACKGROUND
Convolutional coding is a process by which code is generated from a source signal. The code which is generated consists of bits of data which are derived from the source signal in accordance with the particular convolutional coding scheme in use.
The code generated in a given time period depends on both the data values of the source signal in that time period and the data values of the source signal in preceding time periods. The code is typically generated for transmission in a communication system.
Convolutional coding is used in communication systems to provide signal encryption and to reduce the susceptibility of the system to received bit errors. For example, the Groupe Speciale Mobile (GSM) cellular communication system uses convolutional coding.
A further development of convolutional coding is punctured convolutional coding. Puncturing is an additional process step which is applied to convolutional codes. Puncturing consists of omitting some of the bits from the block of data generated by the convolutional coding. The output data stream resulting from punctured convolutional coding therefore has a lower bit rate than the data stream which would result from mere convolutional coding of the same source signal.
In order to retrieve the source data, the data blocks which result from convolutional coding need at some stage to be decoded. This decoding typically happens after receipt of the data by the receiver to which the data has been transmitted, and is performed by the receiver. A type of decoder called a ‘Viterbi’ decoder can be used to perform the decoding.
Punctured convolution codes can best be decoded by a Viterbi decoder. However, different puncturing schemes require different decoders. This means that for fast implementation in a device such as a digital signal processor (DSP), the decoder must be specifically designed for the particular puncturing scheme.
This leads to problems in the decoding step. In systems where many different puncturing schemes are used, handcrafting a Viterbi decoder to each puncturing scheme can involve significant effort and hence resources. The multiple decoders may also take up too much code space.
Published patent application GB-A-2 308 044 discloses convolutional encoding of data for transmission in a GSM cellular communication system. The encoded data may be punctured prior to transmission.
The present invention seeks to optimise the decoding of punctured codes.
SUMMARY OF THE INVENTION
A method in accordance with the invention allows the decoding of data which has been convolution encoded, the data consisting of consecutive groups of bits, each group Gt comprising n bits whose values depend on the particular state change St of the data encoder which occurs at a particular time t, the particular state change St being one of a set of possible state changes Sj which the data encoder could have undergone at that particular time t.
The method of decoding data comprises, for the group Gt of n bits received at the particular time t:
a) making comparisons between the n bits of the group Gt and each possible permutation Pi of n bits, and for each comparison, calculating a numerical value for the error metric Mti between the group Gt and the permutation Pi; and
b) consulting a pre-calculated look-up table Tt which contains the set of possible state changes Sj, and which indicates for each of these state changes Sj a particular one of the said permutations Pi associated with that state change Sj, and assigning to each state change Sj in the look-up table Tt the metric Mti calculated in step a) for the permutation Pi associated with that state change Sj; and
c) using the metric values assigned to the set of possible state changes Sj to update the cumulative metric used to decode the convolution encoded data.
In a preferred embodiment of the method of the invention, the look-up table Tt used at the particular time t may be one of a set of pre-calculated look-up tables, the selection of the particular look-up table Tt for use at a particular time being made in dependence on the puncturing scheme being used by the encoder at that particular time t. Also, the permutation Pi associated with a particular state change Sj in the look-up table Tt may be the group of n bits which the encoder would produce for that particular state change Sj using the puncturing scheme in use at that particular time t. Finally the number of bits n in the particular group Gt may depend on the puncturing scheme being used by the encoder at that particular time t.
In an embodiment of the invention for data transmission, the encoded data may be transmitted after encoding and then received by a receiver prior to decoding.
The invention further comprises a data decoder for decoding data which has been convolution encoded, the data consisting of consecutive groups of bits, each group Gt comprising n bits whose values depend on the particular state change St of the data encoder which occurs at a particular time t, the particular state change St being one of a set of possible state changes Sj which the data encoder could have undergone at that time t.
The data decoder comprises, for the group Gt of n bits received at the particular time t:
a) means MT for making comparisons between the n bits of the group Gt and each possible permutation Pi of n bits, and for each comparison, calculating a numerical value for the error metric Mti between the group Gt and the permutation Pi; and
b) means TG for consulting a pre-calculated look-up table Tt which contains the set of possible state changes Sj, and which indicates for each of these state changes Sj a particular one of the said permutations Pi associated with that state change Sj, and for assigning to each state change Sj in the look-up table Tt the metric Mti calculated in step a) for the permutation Pi associated with that state change Sj; and
c) means BMC for using the metric values assigned to the set of possible state changes Sj to update the cumulative metric used to decode the convolution encoded data.
In a preferred embodiment of the data decoder of the invention, the look-up table Tt used at the particular time t may be one of a set of pre-calculated look-up tables and the means TG for consulting a pre-calculated look-up table Tt selects the particular look-up table Tt for use at a particular time t in dependence on the puncturing scheme being used by the encoder at that particular time t. The permutation Pi associated with a particular state change Sj in the look-up table may be the group of n bits which the encoder would produce for that particular state change Sj using the puncturing scheme in use at that particular time t. The number of bits n in the particular group Gt may depend on the puncturing scheme being used by the encoder at that particular time t.
In an embodiment of the invention for data transmission, a receiver for receiving encoded, punctured data, may comprise a data decoder in accordance with the invention or any of the preferred embodiments detailed above.
REFERENCES:
patent: 5151904 (1992-09-01), Reiner et al.
patent: 5220570 (1993-06-01), Lou et al.
patent: 5331665 (1994-07-01), Busschaert et al.
patent: 5396518 (1995-03-01), How
patent: 5432803 (1995-07-01), Liu et al.
patent: 5436918 (1995-07-01), Kato et al.
patent: 5469452 (1995-11-01), Zehavi
patent: 5497401 (1996-03-01), Ramaswamy et al.
patent: 5566189 (1996-10-01), Laskowski
patent: 5710784 (1998-01-01), Kindred et al.
patent: 5931966 (1999-08-01), Carley
patent: 5970104 (1999-10-01), Zhong et al.
patent: 6205187 (2001-03-01), Westfall
patent: 6289487 (2001-09-01), Hessel et al.
patent: 6374387 (2002-04-01), van den Berghe
patent: 6381727 (2002-04-01), Ikeda
patent: 2308044 (1997-06-01), None
patent: WO 93 06550 (1993-04-01), None
patent: WO 96 23360 (1996-08-01), None
Baker Stephen M.
Lukasik Susan L.
Motorola. Inc.
Santema Steven R.
LandOfFree
Method and apparatus for Viterbi decoding of punctured 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 apparatus for Viterbi decoding of punctured codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for Viterbi decoding of punctured codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3002500