A Viterbi Decoder python implementation

A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that was generated by a convolutional encoder, finding the most-likely sequence of hidden states from a sequence of observed events, in the context of hidden Markov models. In other words, in a communication system, for example, the transceiver encodes the desired bits to be transferred, encrypting and at the same time preparing the encoded bitstream for an unfortunate data change caused by the channel noise. The receiver decoder knows the state machine created by the encoder hardware, which can find the most-likely transmitted bits based on the most-likely path.

A convolutional encoder is built the same as presented in the video: https://www.youtube.com/watch?v=oI0MwwXJ8dE&t=640s

viterbi_encoder

The input bits shifts at different times (clocks) on the three registers shown in the figure above. Depending on the bits available inside those registers, the system will deliver a pair of bits produced (in this case) by two xor gates connected like so. The constraint length (k) is the number of registers an input bit can influence on the encoded bits, in the presented case k=3. The code rate (R) is a relation upon the number of bits that enter the system and the number of bits leaving, leading to R=1/2.

A state machine can be built to describe the encoding system. The red boxes represent the states; a state transition happens when an input bit shifts on the registers. When a bit is shifted, not only the state changes but also another encoded bits are outputted.

st_machine

The above state machine represents the snapshots of the described system. Each arrow has a pair of numbers “x/yy” where x is the bit inserted, and yy is the encoded bits.

inputs = ("1","0","0","1","1")
def v_xor(bit0,bit1):
    if(bit0==bit1):
        return "0"
    else:
        return "1"
def viterbi_encoder(inputs):
    #shift register encoder
    s_reg = ["0","0","0"]
    obs = []
    for t in range (0,len(inputs)):
        #shifting the bits to right
        s_reg[2]=s_reg[1]
        s_reg[1]=s_reg[0]
        #inserting input
        s_reg[0]= inputs[t]
        state = s_reg[0]+ s_reg[1]
        obs.append([])
        #encoded bits
        obs[t] = v_xor(v_xor(s_reg[0],s_reg[1]),s_reg[2])+\
            v_xor(s_reg[0],s_reg[2])
        print s_reg,state
    print obs

viterbi_encoder(inputs)

The above code represents the implementation of a convolutional encoder following the previous logic. The system receives input bits with:

inputs = ("1","0","0","1","1")
viterbi_encoder(inputs)

Shift inserted bit for each time step:

for t in range (0,len(inputs)):
    #shifting the bits to right
    s_reg[2]=s_reg[1]
    s_reg[1]=s_reg[0]
    #inserting input
    s_reg[0]= inputs[t]

At the same time step, calculate encoded bits with a representation of xor gate:

def v_xor(bit0,bit1):
    if(bit0==bit1):
        return "0"
    else:
        return "1"

And their interconnection at the shift registers outputs:

obs[t] = v_xor(v_xor(s_reg[0],s_reg[1]),s_reg[2])+\
    v_xor(s_reg[0],s_reg[2])

Code output:

# shift_register / current state
[‘1’, ‘0’, ‘0’] 10
[‘0’, ‘1’, ‘0’] 01
[‘0’, ‘0’, ‘1’] 00
[‘1’, ‘0’, ‘0’] 10
[‘1’, ‘1’, ‘0’] 11

# encoded bits
[’11’, ’10’, ’11’, ’11’, ’01’]

The Viterbi algorithm is applied to decode the generated vector of bits. The bits transmitted are decoded based on the state machine analysis. Each machine state is expected to have a direction represented by arrows in the second figure, for example, the state “00” can’t jump to state “11”, as states “10” or “01” are not able to stay for two time steps. A Trellis diagram can be used to represent the possible paths between each state for each time step. This representation helps to visualize the code better.

The Trellis diagram below is based in: https://www.youtube.com/watch?v=iPh-HKZyWN4

trellis

Its structure consists of nodes referring to our machine states, each node interconnects with two possible branches representing possible state machine transitions, for each time step a calculation is performed based on the number of different bits between the observed encoded bits and branch expected bits. The result is a branch metric that points which is the most-likely path to follow.

trellis_ex.png

The above example shows the decoding operation for the pairs “11” and “10”. The blue number represents each node metric, at t=0 they are all set to 0. When t=1, each node verifies upcoming branches and their metrics, branches with bigger metric between two possibilities are eliminated. The remaining branch metric is incorporated to the node for further calculations. A branch is chosen randomly If two have the same metric. For t=2, same calculations are performed.

Since there are only two observations, the Viterbi algorithm trace-back begins. Firstly choosing the node with smaller metric, circled by yellow. Then, following the branches that aren’t eliminated and retrieving their input bit attribute also circled by yellow. For these two observations, the most-likely input bits are “10”. This approach brings an issue related to the trace-back mechanism because reading backward will deliver the input bits with inverted indexes. In this case, for example, the first output got is “01”. Also, all metrics need to be calculated before having an output bitstream.

obs = ("11","10","11","11","01","01","11")
start_metric = {'zero':0,'one': 0, 'two': 0,'three':0}
state_machine = {
    #current state, possible branches, branch information
    'zero': {'b1': {'out_b':"11",'prev_st': 'one','input_b':0},
             'b2': {'out_b':"00",'prev_st': 'zero','input_b':0}},
    'one': {'b1': {'out_b': "01", 'prev_st': 'three', 'input_b': 0},
             'b2': {'out_b': "10", 'prev_st': 'two', 'input_b': 0}},
    'two': {'b1': {'out_b': "11", 'prev_st': 'zero', 'input_b': 1},
             'b2': {'out_b': "00", 'prev_st': 'one', 'input_b': 1}},
    'three': {'b1': {'out_b': "10", 'prev_st': 'three', 'input_b': 1},
             'b2': {'out_b': "01", 'prev_st': 'two', 'input_b': 1}},

}

def bits_diff_num(num_1,num_2):
    count=0;
    for i in range(0,len(num_1),1):
        if num_1[i]!=num_2[i]:
            count=count+1
    return count

def viterbi(obs, start_metric, state_machine):
    #Trellis structure
    V = [{}]
    for st in state_machine:
        # Calculating the probability of both initial possibilities for the first observation
        V[0][st] = {"metric": start_metric[st]}
    #for t>0
    for t in range(1, len(obs)+1):
        V.append({})
        for st in state_machine:
            #Check for smallest bit difference from possible previous paths, adding with previous metric
            prev_st = state_machine[st]['b1']['prev_st']
            first_b_metric = V[(t-1)][prev_st]["metric"] + bits_diff_num(state_machine[st]['b1']['out_b'], obs[t - 1])
            prev_st = state_machine[st]['b2']['prev_st']
            second_b_metric = V[(t - 1)][prev_st]["metric"] + bits_diff_num(state_machine[st]['b2']['out_b'], obs[t - 1])
            #print(state_machine[st]['b1']['out_b'],obs[t - 1],t)
            if first_b_metric > second_b_metric:
                V[t][st] = {"metric" : second_b_metric,"branch":'b2'}
            else:
                V[t][st] = {"metric": first_b_metric, "branch": 'b1'}

    #print trellis nodes metric:
    for st in state_machine:
        for t in range(0,len(V)):
            print V[t][st]["metric"],
        print ""
    print ""

    smaller = min(V[t][st]["metric"] for st in state_machine)
    #traceback the path on smaller metric on last trellis column
    for st in state_machine:
        if V[len(obs)-1][st]["metric"] == smaller:
            source_state = st
            for t in range(len(obs),0,-1):
                branch = V[t][source_state]["branch"]
                print(state_machine[source_state][branch]['input_b']),
                source_state = state_machine[source_state][branch]['prev_st']
            print (source_state+"\n")
    print("Finish")

viterbi(obs,
        start_metric,
        state_machine)

The algorithm is implemented with Python as shown above. The Viterbi decoder takes as input the encoder state machine, start metric for t=0 and the observations:

obs = ("11","10","11","11","01","01","11")
start_metric = {'zero':0,'one': 0, 'two': 0,'three':0}
state_machine = {
    #current state, possible branches, branch information
    'zero': {'b1': {'out_b':"11",'prev_st': 'one','input_b':0},
             'b2': {'out_b':"00",'prev_st': 'zero','input_b':0}},
    'one': {'b1': {'out_b': "01", 'prev_st': 'three', 'input_b': 0},
             'b2': {'out_b': "10", 'prev_st': 'two', 'input_b': 0}},
    'two': {'b1': {'out_b': "11", 'prev_st': 'zero', 'input_b': 1},
             'b2': {'out_b': "00", 'prev_st': 'one', 'input_b': 1}},
    'three': {'b1': {'out_b': "10", 'prev_st': 'three', 'input_b': 1},
             'b2': {'out_b': "01", 'prev_st': 'two', 'input_b': 1}},

}

Starting with all metrics = 0  means the system has equal probability to have begun with any of four states. If the application specifies that the first state always starts at zero (“00”) for example, a short approach is raising the other state metrics. By knowing the beginning state, the decoder has less probability of getting a wrong bitstream from the noisy channel.

The vector “V” represents the Trellis graph, which loads primary metrics for t=0:

V = [{}]
for st in state_machine:
    # Calculating the probability of both initial possibilities for the first observation
    V[0][st] = {"metric": start_metric[st]}

After, the Trellis metrics and optimal branches are calculated:

#for t>0
for t in range(1, len(obs)+1):
    V.append({})
    for st in state_machine:
        #Check for smallest bit difference from possible previous paths, adding with previous metric
        prev_st = state_machine[st]['b1']['prev_st']
        first_b_metric = V[(t-1)][prev_st]["metric"] + bits_diff_num(state_machine[st]['b1']['out_b'], obs[t - 1])
        prev_st = state_machine[st]['b2']['prev_st']
        second_b_metric = V[(t - 1)][prev_st]["metric"] + bits_diff_num(state_machine[st]['b2']['out_b'], obs[t - 1])
        #print(state_machine[st]['b1']['out_b'],obs[t - 1],t)
        if first_b_metric > second_b_metric:
            V[t][st] = {"metric" : second_b_metric,"branch":'b2'}
        else:
            V[t][st] = {"metric": first_b_metric, "branch": 'b1'}

With all paths and metric set, the trace-back takes place from the smaller metric node:

smaller = min(V[t][st]["metric"] for st in state_machine)
#traceback the path on smaller metric on last trellis column
for st in state_machine:
    if V[len(obs)-1][st]["metric"] == smaller:
        source_state = st
        for t in range(len(obs),0,-1):
            branch = V[t][source_state]["branch"]
            print(state_machine[source_state][branch]['input_b']),
            source_state = state_machine[source_state][branch]['prev_st']
        print (source_state+"\n")

Code output:

#Trellis nodes metric, t=0, t=1 …
0 0 1 0 2 3 3 0
0 1 1 2 2 0 2 3
0 0 1 1 0 3 3 2
0 1 0 2 2 2 0 3

#Inverted input bits encoded and decoded
0 1 1 1 0 0 1 zero

Finish

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s