|
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 could have received: 002, and
112. That's because we know the convolution encoder was initialized
to the all-zeroes state, and given one input bit = one or zero, there are only
two states we could transition to and two possible outputs of the encoder.
These possible outputs of the encoder are 00 2 and 112.
The metric we're going to use for now is the Hamming distance between the
received channel symbol pair and the possible channel symbol pairs. The Hamming
distance is computed by simply counting how many bits are different between the
received channel symbol pair and the possible channel symbol pairs. The results
can only be zero, one, or two. The Hamming distance (or other metric) values we
compute at each time instant for the paths between the states at the previous
time instant and the states at the current time instant are called branch
metrics. For the first time instant, we're going to save these results as
"accumulated error metric" values, associated with states. For the
second time instant on, the accumulated error metrics will be computed by
adding the previous accumulated error metrics to the current branch metrics. At t = 1, we received 002.
The only possible channel symbol pairs we could have received are 002
and 112. The Hamming distance between 002 and 002
is zero. The Hamming distance between 002 and 112 is two.
Therefore, the branch metric value for the branch from State 002 to
State 002 is zero, and for the branch from State 002 to
State 102 it's two. Since the previous accumulated error metric
values are equal to zero, the accumulated metric values for State 002
and for State 102 are equal to the branch metric values. The
accumulated error metric values for the other two states are undefined. The
figure below illustrates the results at t = 1:
Note that the solid lines
between states at t = 1 and the state at t = 0 illustrate the
predecessor-successor relationship between the states at t = 1 and the state at
t = 0 respectively. This information is shown graphically in the figure, but is
stored numerically in the actual implementation. To be more specific, or maybe
clear is a better word, at each time instant t, we will store the number of the
predecessor state that led to each of the current states at t. Now let's look what happens
at t = 2. We received a 112 channel symbol pair. The possible
channel symbol pairs we could have received in going from t = 1 to t = 2 are 002
going from State 002 to State 002, 112 going
from State 002 to State 102, 102 going from
State 102 to State 01 2, and 012 going from
State 102 to State 11 2. The Hamming distance between 002
and 112 is two, between 112 and 112 is zero,
and between 10 2 or 012 and 112 is one. We add
these branch metric values to the previous accumulated error metric values
associated with each state that we came from to get to the current states. At t
= 1, we could only be at State 002 or State 102. The
accumulated error metric values associated with those states were 0 and 2
respectively. The figure below shows the calculation of the accumulated error
metric associated with each state, at t = 2.
That's all the computation
for t = 2. What we carry forward to t = 3 will be the accumulated error metrics
for each state, and the predecessor states for each of the four states at t = 2,
corresponding to the state relationships shown by the solid lines in the
illustration of the trellis. Now look at the figure for
t = 3. Things get a bit more complicated here, since there are now two
different ways that we could get from each of the four states that were valid
at t = 2 to the four states that are valid at t = 3. So how do we handle that?
The answer is, we compare the accumulated error metrics associated with each
branch, and discard the larger one of each pair of branches leading into a
given state. If the members of a pair of accumulated error metrics going into a
particular state are equal, we just save that value. The other thing that's
affected is the predecessor-successor history we're keeping. For each state,
the predecessor that survives is the one with the lower branch metric. If the
two accumulated error metrics are equal, some people use a fair coin toss to
choose the surviving predecessor state. Others simply pick one of them
consistently, i.e. the upper branch or the lower branch. It probably doesn't
matter which method you use. The operation of adding the previous accumulated
error metrics to the new branch metrics, comparing the results, and selecting
the smaller (smallest) accumulated error metric to be retained for the next
time instant is called the add-compare-select operation. The figure below shows
the results of processing t = 3:
Note that the third channel
symbol pair we received had a one-symbol error. The smallest accumulated error
metric is a one, and there are two of these. Let's see what happens now
at t = 4. The processing is the same as it was for t = 3. The results are shown
in the figure:
Notice that at t = 4, the
path through the trellis of the actual transmitted message, shown in bold, is
again associated with the smallest accumulated error metric. Let's look at t =
5:
At t = 5, the path through
the trellis corresponding to the actual message, shown in bold, is still
associated with the smallest accumulated error metric. This is the thing that
the Viterbi decoder exploits to recover the original message. Perhaps you're getting
tired of stepping through the trellis. I know I am. Let's skip to the end. At t
= 17, the trellis looks like this, with the clutter of the intermediate state
history removed:
The decoding process begins
with building the accumulated error metric for some number of received channel
symbol pairs, and the history of what states preceded the states at each time
instant t with the smallest accumulated error metric. Once this information is
built up, the Viterbi decoder is ready to recreate the sequence of bits that
were input to the convolution encoder when the message was encoded for
transmission. This is accomplished by the following steps:
The
following table shows the accumulated metric for the full 15-bit (plus two
flushing bits) example message at each time t:
It is interesting to note that for this hard-decision-input
Viterbi decoder example, the smallest accumulated error metric in the final
state indicates how many channel symbol errors occurred. The following state history table shows the surviving
predecessor states for each state at each time t:
The following table shows the states selected when tracing
the path back through the survivor state table shown above:
Using a table that maps state transitions to the inputs that
caused them, we can now recreate the original message. Here is what this table
looks like for our example rate ½ K = 3 convolution code:
Note: In the above
table, x denotes an impossible transition from one state to another state. So now we have all the tools required to recreate the
original message from the message we received:
The two flushing bits are
discarded. Shortcut for a NO ERROR condition We have to take into
account that in summary the convolution is a injective transformation F,
meaning that given an initial state S(0) and an input
stream I of length h bits a convolution with (in this case) a couple of
functions f and g (corresponding to two polynomials) generates via a sort of
Shift Register F applied to (S(0), I) gives the stream II formed by h pairs ob
bits that are named “symbols”, namely: F(S(0), I) = II Existing then the inverse
function F´ such that F´(II) = I Let´s see how this inverse behaves. We
may now use the Input Inference Table defined above. Knowing the output symbols
stream, for example: 00 11 10 00 01 10 01 11 11 10 00
10 11 00 11 10 11 00 Input
Inference table
First step: given S(t), current state at time t, and II(t), output symbol at
time t, from Output Symbol Table we “infer” Input (I(t) at time t. Second step: Once inferred
Input we compute the next state S(t+1) from Next State
Table Here's an insight into how
the traceback algorithm eventually finds its way onto the right path even if it
started out choosing the wrong initial state. This could happen if more than
one state had the smallest accumulated error metric, for example. I'll use the
figure for the trellis at t = 3 again to illustrate this point:
See how at t = 3, both
States 012 and 112 had an accumulated error metric of 1.
The correct path goes to State 012 -notice that the bold line
showing the actual message path goes into this state. But suppose we choose
State 112 to start our traceback. The predecessor state for State 112 , which is State 102 , is the same
as the predecessor state for State 012! This is because at t = 2,
State 102 had the smallest accumulated error metric. So after a
false start, we are almost immediately back on the
correct path. For the example 15-bit
message, we built the trellis up for the entire message before starting
traceback. For longer messages, or continuous data, this is neither practical nor
desirable, due to memory constraints and decoder delay. Research has shown that
a traceback depth of K x 5 is sufficient for Viterbi decoding with the type of
codes we have been discussing. Any deeper traceback increases decoding delay
and decoder memory requirements, while not significantly improving the
performance of the decoder. The exception is punctured codes, which I'll
describe later. They require deeper traceback to reach their final performance
limits. To implement a Viterbi
decoder in software, the first step is to build some data structures around
which the decoder algorithm will be implemented. These data structures are best
implemented as arrays. The primary six arrays that we need for the Viterbi
decoder are as follows:
Before
getting into the example source code, for purposes of completeness, I want to
talk briefly about other rates of convolution codes that can be decoded with
Viterbi decoders. Earlier, I mentioned punctured codes, which are a common way
of achieving higher code rates, i.e. larger ratios of k to n. Punctured codes
are created by first encoding data using a rate 1/n encoder such as the example
encoder described in this tutorial, and then deleting some of the channel
symbols at the output of the encoder. The process of deleting some of the
channel output symbols is called puncturing. For example, to create a rate 3/4
code from the rate 1/2 code described in this tutorial, one would simply delete
channel symbols in accordance with the following puncturing pattern:
Where a one indicates that
a channel symbol is to be transmitted, and a zero indicates that a channel
symbol is to be deleted. To see how this make the rate be 3/4, think of each
column of the above table as corresponding to a bit input to the encoder, and
each one in the table as corresponding to an output channel symbol. There are
three columns in the table, and four ones. You can even create a rate 2/3 code
using a rate 1/2 encoder with the following puncturing pattern:
which has two columns and three ones. To decode a punctured code,
one must substitute null symbols for the deleted symbols at the input to the
Viterbi decoder. Null symbols can be symbols quantized to levels corresponding
to weak ones or weak zeroes, or better, can be special flag symbols that when
processed by the ACS circuits in the decoder, result in no change to the
accumulated error metric from the previous state. Of course, n does not have to
be equal to two. For example, a rate 1/3, K = 3, (7, 7, 5)
code can be encoded using the encoder shown below:
This encoder has three
modulo-two adders, so for each input bit, it can produce three channel symbol
outputs. Of course, with suitable puncturing patterns, you can create
higher-rate codes using this encoder as well. I don't have good data to
share with you right now about the traceback depth requirements for Viterbi
decoders for punctured codes. I have been told that instead of K x 5, depths of
K x 7, K x 9, or even more are required to reach the point of diminishing
returns. This would be a good topic around which to design some experiments
using a modified version of the example simulation code I provide. Polynomials:
(35, 23) in Octal Upper
Stream: (1 1 1 0 1); =>
Tab bits: 1101 Lower
Stream: (1 0 0 1 1); =>
Tab bits: 0011
Shift
registers define the “state” of the virtual Viterbi machine. At each clock step
they shift leaving a vacant place that is occupied by the “input bit”, the bit
to be coded as a two bits symbol. Bits of the symbols must satisfy at each step
the following relations: Input bit + Tab bits
Upper Polynomial = Upper bit Input bit + Tab bits
Lower Polynomial = Lower bit Where the
operator + stands for XOR. This is the procedure for a 1:2 Convolution, and in
general for a 1:m Convolution we will have m bits
symbols, each one staysfuing a similar relation,
namely Input bit + Tab bits
j-Polynomial Tab bits = j-bit Note:
only changes Upper Stream Polynomial, (11001)
=> (31 in octal), (10011)
=> (23 in octal) Warning:
as used in our Prototype (programmed in DSP board)
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
