Convolution - Viterbi Code/Decode

Brief Help edited by Juan Chamero, jach_spain@yahoo.es

Updated as of April 2006

 

References:

1. Viterbi School HomePage: http://viterbi.usc.edu/about/viterbi/viterbi_digital_age.htm, and http://home.netcom.com/%7Echip.f/viterbi/algrthms.html.

2. Steve Gardner and Tom Hardin, “Systems design and implementation of modems and FEC codecs for wireless and wireline systems”. They can be reached at shg@istari-design.com and cth@istari-design.com.

3. Library of Comm issues in C++ SPUC Org: http://spuc.sourceforge.net/ , http://spuc.sourceforge.net/iterbi Class (Full): http://spuc.sourceforge.net/

 

 

 

INDEX

 

Parameters

Interpretatin

Some Convolution/Viterbi Experimentation References

Shortcut for a NO ERROR condition

Examples

Running for K = 5

Other Polynomials set:

Convolution seen as from a States Machine

 

Appendices

i) Going Backward in case of No errors condition

II) Another Sources of Viterbi related soft:

III) Convolution - Viterbi Source Codes

IV) Something about efficiency

 

 

 


Parameters

 

Ratio: 1:2, enter one bit, two bits outcome (a two bits symbol in the Jargon)

K=3, constraint, “reach” of the convolution algorithm

Polynomial pair: (a, b): binary numbers that point to Polynomial Tab Bits to XOR in order to generate output. For instance (3, 5) means (0011), (0101)

 

Sample: [010111001010001] plus three 0 flushing bits, remains:

 

[010111001010001000]

 

We are going then to generate two streams: Upper and Lower

 

Polynomial for Upper Stream 1: 1 + X + X^2

Polynomial for Lower Stream 2: 1 + X

 

K=3 stands for a “shift register” of size K-1=2, or in the GSM jargon the size of the “Convolution States Machine” because the convolution coder could be seen as a “black box” that changes states when triggered by input bits, to generate an output of two bits in this case, one for the Upper stream and another for the Lower stream.

 

Let’s see a states transition scheme, step by step, a transition at a time:

 

 

 

State

Input

B0

B1

output

Us

Ls

0

-

0

0

-

-

-

1

0

0

0

0

0

0

2

1

1

0

0

1

1

3

0

0

1

0

1

0

4

1

1

0

1

0

0

5

1

1

1

0

0

1

6

1

1

1

1

1

0

7

0

0

1

1

0

1

8

0

0

0

1

1

1

9

1

1

0

0

1

1

10

0

0

1

0

1

0

11

1

1

0

1

0

0

12

0

0

1

0

1

0

13

0

0

0

1

1

1

14

0

0

0

0

0

0

15

1

1

0

0

1

1

16

0

0

1

0

1

0

17

0

0

0

1

1

1

18

0

0

0

0

0

0

 

 

Generating the following Us and Ls pairs:

 

00 11 10 00 01 10 01 11 11 10 00 10 11 00 11 10 11 00

 

 

Return

 

 

 

 

 

Interpretation

 

Al possible states of this box are then:

 

B0

B1

0

0

0

1

1

0

1

1

 

Each state “matches” with a bit input to change its state

 

Next State Table

 

States bits

Input bit

B0

B1

0

1

0

0

00

10

0

1

00

10

1

0

01

11

1

1

01

11

 

And for each triad (state, input bit, output bit) we have precisely determined the stream output, both upper and lower stream in this case, throughout a Table Lookup as follows:

 

Output Symbol Table

 

Current State

Input = 0:

Input = 1:

00

00

11

01

11

00

10

10

01

11

01

10

 

Note: observe that the “Hamming distance” between possible

output streams as a function of input bit at any cycle is 2.

 

 

 

Now we may build the output as a function of states change with a third Input Inference Table as a function of states, before and after being triggered by the input bit:

 

 

Input Inference table

 

 

00 = 0

01 = 1

10 = 2

11 = 3

00 = 0

0

X

1

X

01 = 1

0

X

1

X

10 = 2

X

0

X

1

11 = 3

X

0

X

1

 

Warning: With this table we may decode convolution straightforwardly (see below the procedure to follow for a NO ERROR condition).

 

Return

 

 

Some Convolution/Viterbi Experimentation References

Source: http://home.netcom.com/%7Echip.f/viterbi/tutorial.html  , www.netcom.com

 

Description of the Algorithm

The Viterbi decoder itself is the primary focus of this tutorial. Perhaps the single most important concept to aid in understanding the Viterbi algorithm is the Trellis diagram. The figure below shows the trellis diagram for our example rate ½, K = 3 convolution encoder, for a 15-bit message:

trellis diagram for rate 1/2 K = 3 (7, 5) convolutional encoder

The four possible states of the encoder are depicted as four rows of horizontal dots. There is one column of four dots for the initial state of the encoder and one for each time instant during the message. For a 15-bit message with two encoder memory flushing bits, there are 17 time instants in addition to t = 0, which represents the initial condition of the encoder. The solid lines connecting dots in the diagram represent state transitions when the input bit is a one. The dotted lines represent state transitions when the input bit is a zero. Notice the correspondence between the arrows in the trellis diagram and the state transition table discussed above. Also notice that since the initial condition of the encoder is State 002, and the two memory flushing bits are zeroes, the arrows start out at State 002 and end up at the same state.

The following diagram shows the states of the trellis that are actually reached during the encoding of our example 15-bit message:

trellis diagram for example 15-bit message

The encoder input bits and output symbols are shown at the bottom of the diagram. Notice the correspondence between the encoder output symbols and the output table discussed above. Let's look at that in more detail, using the expanded version of the transition between one time instant to the next shown below:

The two-bit numbers labeling the lines are the corresponding convolution encoder channel symbol outputs. Remember that dotted lines represent cases where the encoder input is a zero, and solid lines represent cases where the encoder input is a one. (In the figure above, the two-bit binary numbers labeling dotted lines are on the left, and the two-bit binary numbers labeling solid lines are on the right.)

OK, now let's start looking at how the Viterbi decoding algorithm actually works. For our example, we're going to use hard-decision symbol inputs to keep things simple. (The example source code uses soft-decision inputs to achieve better performance.) Suppose we receive the above encoded message with a couple of bit errors:

trellis diagram for example message with errors

Each time we receive a pair of channel symbols, we're going to compute a metric to measure the "distance" between what we received and all of the possible channel symbol pairs we could have received. Going from t = 0 to t = 1, there are only two possible channel symbol pairs we