Viterbi decoder

Details Viterbi decoder Viterbi decoder

2000-11-16

2001-11-27

Bocure, Tesfaldet (Department: 2631)

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

C714S796000

Reexamination Certificate

active

06324226

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a Viterbi decoder used for maximum likelihood decoding of convolutional codes.
2. Related Background Art
A Viterbi decoder is used for maximum likelihood decoding of convolutional codes, wherein from a plurality of known code sequences of possible input code sequences, a code sequence closest in code distance to that generated by a convolutional encoder is selected as a maximum likelihood code sequence (maximum likelihood path), and based on the information thus selected, decoded data are obtained. The Viterbi decoding has a high capability for correcting random errors occurring in a communication channel and allows a particularly high encoding gain to be obtained in combination with a soft decision decoding system. For instance, in a mobile communication system, in which bit errors affect communication quality considerably and which tends to be affected by interference waves easily, convolutional codes are used as error collecting codes and the Viterbi decoding is employed for decoding them.
This Viterbi decoding algorithm is described briefly. For instance, suppose a convolutional code, with a code rate R=½ and a constraint length K=3, whose generating polynomials are given by the following formulae.
G0(D)=1+D
2
G1(D)=1+D+D
2
FIG. 9
shows a structural example of a convolutional encoder for generating such a code. In
FIG. 9
, information bits as input data are delayed sequentially by two delay elements
901
and
902
such as flip-flops or the like. The input data and data from the delay element
902
are added by an adder
903
, which is output as an output G0. The input data and data from the delay element
901
are added by an adder
904
and then data from the adder
904
and the data from the delay element
902
are added by an adder
905
, which is output as an output G1.
When the contents of the respective delay elements
901
and
902
in such an encoder are indicated as S[1] and S[0], the states S[1:0] of the encoder can include four states of (00), (01), (10), and (11). There are always two possible transition states with respect to an input.
In other words, in the case of an input “0”, when a current state is (00) or (01), it is subjected to the transition to the state (00), and when the current state is (10) or (11), it is subjected to the transition to the state (01). In the case of an input “1”, when the current state is (00) or (01), it is subjected to the transition to the state (10), and when the current state is (10) or (11), it is subjected to the transition to the state (11).
As a method of illustrating such state transitions, a trellis diagram is used, and such state transitions are illustrated by a trellis diagram shown in FIG.
10
. In
FIG. 10
, solid-line arrows (branches) indicate transitions in the case of an input “0” and broken-line branches indicate transitions in the case of an input “1”. The numerals provided along the respective branches are codes (G0, G1) output upon the transitions of the respective branches.
As is apparent from
FIG. 10
, two branches become confluent in transition to the respective states without fail. In the Viterbi decoding algorithm, a combination (a path) of maximum likelihood (most likely) branches out of the two respective branches reaching the respective states is selected and information (a path selection signal) of the path (a surviving path) thus selected is stored in a memory. The path selection is executed until a predetermined path length is obtained and then a maximum likelihood surviving path is searched (traced back) based on contents of the path selection signal memory. Based on the change of the respective maximum likelihood states obtained by the trace-back, information input to the convolutional encoder is decoded.
The Viterbi decoder for decoding convolutional codes based on such a Viterbi algorithm basically includes a branch metric calculation means, an ACS (add-compare-select) operation means, a path metric memory, a path selection signal memory, and a trace-back means. The branch metric calculation means calculates code distances (branch metrics) between input code sequences and code sequences predicted in respective branches. The ACS operation means calculates accumulated values (path metrics) of branch metrics reaching respective states and selects surviving paths. The path metric memory stores the path metrics of the respective states, and the path selection signal memory stores information of the selected paths. The trace-back means searches maximum likelihood surviving paths based on the contents of the path selection signal memory.
In the above-mentioned ACS operation means, the surviving paths in respective states are selected according to a so-called path metric transition diagram, and the path metrics of the surviving paths are calculated. This path metric transition diagram is prepared based on the trellis diagram as shown in FIG.
10
.
FIGS. 11A and 11B
show path metric transition diagrams when codes indicated by the trellis diagram shown in
FIG. 10
are used. That is to say, in the trellis diagram shown in
FIG. 10
, there are two paths that become confluent in the state (00), one of which is generated by an output of a code (00) from the state (00) and the other of which generates a code (11) from the state (01). Therefore, the path metric PM00(new) in the current state (00) is expressed by one of the following two formulae:
PM00(new)a=PM00(old)+BM00
PM00(new)b=PM01(old)+BM11
where PM00(old) and PM01(old) indicate path metrics of the preceding states and BM00 and BM11 denote branch metrics.
In other words, a maximum likelihood value of two path metrics PM00(new)a and PM00(new)b during the ACS operation is selected and the path metric thus selected is determined as the path metric PM00(new) of the current state (00).
There are two paths that become confluent in the state (10), one of which is generated by an output of a code (11) from the state (00) and the other of which generates a code (00) from the state (01). Therefore, the path metric PM10(new) in the current state is expressed by one of the following two formulae.
PM10(new)a=PM00(old)+BM11
PM10(new)b=PM01(old)+BM00
Further, there are two paths that become confluent in the state (01), one of which is generated by an output of a code (01) from the state (10) and the other of which generates a code (10) from the state (11). Therefore, the path metric PM01(new) in the current state is expressed by one of the following two formulae.
PM01(new)a=PM10(old)+BM01
PM01(new)b=PM11(old)+BM10
Furthermore, there are two paths that become confluent in the state (11), one of which is generated by an output of a code (10) from the state (10) and the other of which generates a code (01) from the state (11). Therefore, the path metric PM11(new) in the current state is expressed by one of the following two formulae.
PM11(new)a=PM10(old)+BM10
PM11(new)b=PM11(old)+BM01
Based on the above, the path metric transition diagrams as shown in
FIGS. 11A and 11B
can be prepared.
As can be seen from the above formulae and the path metric transition diagrams shown in
FIGS. 11A and 11B
, the difference between PM00(new) and PM10(new) is only the correspondence between PMxx(old) and BMxx when BM11 and BM00 are added to PM00(old) and PM01(old).
Similarly, the difference between PM01(new) and PM11(new) also is only the correspondence between PMxx(old) and BMxx when BM01 and BM10 are added to PM10(old) and PM11(old).
Furthermore, the two PMxx(old) in each case described above have the relationship of continuous even and odd number states and the two PMxx(new) have the relationship of upper and lower order states in which only their most significant bits differ from each other.
These facts indicate that two PMxx(new) with the relationship of the upper and lower order states can be calculated f

Affiliated with

Also associated with

Rating

Viterbi 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 Viterbi decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2594661