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

Controlling Virtuoso schematic inputs with Digital Vector File

The utilization of a Vector File makes controlling multiple input and output signals independently possible. Its implementation is important for a variety of circuits which need different pulses at specific times, relieving the effort to manage PWL voltage sources at schematic.

Note: comments begins with “;” character

radix 1 1 4 4
; radix specifies the number of ports and number of bits for each port,
; the base number is also specified ( from binary '1' to hexadecimal '4' )

io i i i i

; io defines the state of each port, as input "i", output "o"
; or bidirectional "b"
vname Primeiro_Sinal Segundo_Sinal Terceiro_Sinal[0:3] Quarto_Sinal,Quinto_Sinal,Sexto_Sinal,Setimo_Sinal

; vname sets the name of each port

tunit 1ns

; tunit configures the time unit of simulation

trise 1ps
; trise defines the rise time of each vector

tfall 1ps
; tfall defines fall time of each vector

vih 5.0
; vih defines logical '1' voltage

vil 0.0
; vil defines logical '0' voltage
period 10.0

; period determines the time interval between each vector step, the
; number is multiplied by the previously time unit set

idelay 5 0 1 1 0

; idelay inserts a delay at the selected ports multiplied by the time unit

; The next lines will define the states of each port as the
; transient simulation happens, each line represents a time step

; The binary number can be represented with 0 or 1, and the
; hexadecimals with 0-F

0 0 0 0 ; All signals initially set to 0
1 0 F F ; First signal with a logical '1', second with a logical '0' , the other ones set to a logical '1'
0 1 C C ; And goes on
1 0 A A
1 1 3 3

The ports declaration and manipulation are indented by its position from left to right.

To the visualization of the developed signals, it is necessary to open a schematic on Virtuoso and open: “Analog Environment->Setup->Simulation Files”, inserting the file path on the “Vector File” field.

After the simulation, the signals can be seen on results browser

primeiros_sinais

quarto_sinal

After the simulation, the signals can be seen on results browser
radix 1 1

io i i

vname A B ; schematic input ports 

tunit 1ns

trise 1ps

tfall 1ps

vih 5.0

vil 0.0

period 10.0

0 0
0 1
1 0
1 1
1 0
0 1
0 0 ; 70ns in total

 

and_2_schem

and_2_out

Reference: http://www.bioee.ee.columbia.edu/courses/cad/html/vector_file.pdf