|
Convolution - Viterbi Code/Decode Brief Help edited by Juan Chamero, jach_spain@yahoo.es Updated as of April 2006 References: 1. 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 Some Convolution/Viterbi Experimentation
References Shortcut for a NO ERROR condition Convolution seen as from a States Machine 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 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:
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 Interpretation Al possible
states of this box are then:
Each state
“matches” with a bit input to change its state
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
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
Warning:
With this table we may decode convolution straightforwardly (see below the
procedure to follow for a NO ERROR condition). 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:
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:
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:
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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
