Low complexity convolutional decoder

Details Low complexity convolutional decoder Low complexity convolutional decoder

2001-05-30

2004-05-25

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S781000

Reexamination Certificate

active

06742158

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of convolutional coding; and, more particularly, to a method and apparatus for decoding convolutionally encoded data.
2. Description of the Prior Art
Convolutional codes are used to correct bit errors that occur when digital bits are communicated between a transmitter and a receiver. The transmitter and receiver may be physically connected, or they may interact wirelessly; for example, in a wireless digital communications system.
A typical convolutional encoder introduces dependency and adds redundancy to the encoded sequence. The amount of redundancy introduced by the encoder is measured as n/k, where k is the length of the sequence input to the encoder and n is the length of the sequence output from the encoder in a given encoder cycle. The code rate C is defined as c=k
, and is usually in the range of 0<c≦1.
FIG. 1
illustrates a convolutional encoder
10
with a code rate c=½ provided in a transmitter
11
. More specifically,
FIG. 1
illustrates a G7G4-encoder used in a GSM (Global System for Mobile Communication) system with generator polynomial (1+D+D
2
+D
3
+D
6
1+D
2
+D
3
+D
5
+D
6
). As shown in
FIG. 1
, and as known to those skilled in the art; the encoder
10
is typically implemented as a shift register together with associated combinatorial logic. The shift register is composed of a chain of six delay elements (i.e., flip-flops)
12
; and the combinatorial logic is composed of a plurality of suitably positioned modulo-2 adders
14
, typically implemented as exclusive-or gates. The number of delay elements in the encoder that feed the combinatorial logic that produces the output sequence is defined as the “constraint length” of the code. A sequence input to the encoder at input
16
is encoded by the encoder to produce encoded output sequences at
18
.
In order to add some extra redundancy, so-called “terminating codes” are often used. These start and end in predefined states, often the all zero state. This is accomplished by starting the encoding in the all zero state and adding zeros at the end of the sequence that is input to the encoder, as many as the size of the constraint length of the code.
EDGE (Enhanced Data rates for Global Evolution) is an interface mode which has recently been developed for GSM, as well as for CPRS (General Packet Radio Service) systems. GPRS is a packet switched system that uses the same physical carrier structure as the GSM cellular communications system. EDGE's principal features include new modulation and coding schemes which increase data capacity and speed in the air interface. The packet switched data mode with EDGE modulation is called EGPRS (Enhanced GPRS).
In EDGE/EGPRS systems, convolutional codes having different code rates are used as compared to those used in GSM. Among these is a code with a code rate c=1.
FIG. 2
illustrates a convolutional encoder
20
in a transmitter
21
that is used in EDGE/EGPRS systems. More particularly,
FIG. 2
illustrates a G4-encoder with generator polynomial (1+D
2
+D
3
+D
5
+D
6
), code rate c=1. As shown, the encoder
20
is implemented as a shift register with six delay elements
22
, and combinatorial logic comprised of a plurality of modulo-two adders
24
. A sequence input to the encoder at
26
is encoded by the encoder to produce an encoded output sequence at
28
.
At the receiver, a convolutional decoder attempts to reconstruct the original sequence that was input to the convolutional encoder at the transmitter (e.g., the sequence input at
26
in
FIG. 2
) by utilizing knowledge of the code used by the encoder at the transmitter, and the redundancy in the sequence received by the receiver. To every bit in the received, estimated sequence, there are so-called soft values attached. These soft values are calculated earlier in the receiver, for example, in the equalizer; and are used during the decoding to provide a measure of how good the estimation of the bit is.
Using a code with a code rate c=1 reduces the possibilities to correct bit errors, because there is no redundancy in the received bit sequence except for the starting and ending state.
The common way to decode a convolutionally encoded sequence is to use a Viterbi decoder (see R. Johannesson and K. S. Zigangirov, “Fundamentals of convolutional coding”, IEEE Press series on Digital & Mobile Communication, IEEE Press, 1999). The Viterbi decoder investigates all possible sent sequences and compares them with the received sequence. The most probable sequence is calculated, with respect to the soft values.
The Viterbi decoder uses a large amount of memory and requires that many calculations be carried out. In order to reduce the size of the memory, a Viterbi decoder with back-search limit is often used. A Viterbi decoder with back-search limit investigates only a part of all possible sent sequences when making a bit decision.
The current procedures for decoding a convolutionally encoded sequence suffer from a variety of shortcomings. Initially, as indicated above, the Viterbi decoder uses a large amount of memory and requires that a great many calculations be carried out. This results in an increase in power consumption such that in a mobile telephone, for example, the talk and stand-by time of the telephone is decreased.
Using a Viterbi decoder with back-search limit will reduce memory requirements; however, it will not reduce the number of calculations that are required to be carried out. Furthermore, performance is negatively affected by introducing the back-search limit, especially when convolutional codes with code rate 1 are used, since the starting and ending states are not connected in the investigated trellis.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for decoding convolutionally encoded data which enables simplification of the overall decoding process as compared with conventional decoding procedures. More particularly, a method for decoding a convolutionally encoded sequence of bits encoded by an encoder with given generator polynomial according to the present invention comprises the step of using an inverted given generator polynomial as a decoder.
According to a presently preferred embodiment, the decoding method of the present invention decodes a convolutionally encoded sequence of bits encoded by an encoder with generator polynomial (1+D
2
+D
3
+D
5
+D
6
), code rate 1, and uses a decoder with inverted generator polynomial 1/(1+D
2
+D
3
+D
5
+D
6
). Preferably, the decoder is implemented as a shift register with feedback, together with appropriate combinatorial logic.
The convolutional decoder of the present invention provides substantially the same results as a Viterbi decoder with back-search limit, except for the last n bits, if n is the back-search limit of the Viterbi decoder; inasmuch as there will be no redundancy in the encoded frame except for the start and end state. The frame error rate can be reduced, however, by checking the end state of the shift register. Specifically, when a terminating code is used, the encoder will send tailbits; and the shift register of the decoder should end up in a predefined state. If it does not, the frame has been erroneously decoded; and according to a preferred embodiment of the invention, a redecoding procedure is performed until the end state of the shift register is in the predefined state or until a predefined number of decodings are carried out.
The decoding method and apparatus of the present invention provides several advantages as compared with a Viterbi decoder, including a Viterbi decoder with back-search limit. Among such advantages include a lower complexity (since only a few of all possible paths in the trelllis are calculated), and a smaller memory size and higher performance than a Viterbi decoder with back-search limit. The method according to the present inv

Affiliated with

Also associated with

Rating

Low complexity convolutional decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Low complexity convolutional decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low complexity convolutional decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3222976