# Viterbi Decoding Depends on given State Machine Diagram (trellis)

조회 수: 17(최근 30일)
Jimmy cho 26 Aug 2020
편집: Jimmy cho 26 Aug 2020
Hi guys, before posting here I really searched on forum here about my issue and I found something relevant to viterbi decoder and there's already built functions that simulink provide, but I really didn't understand them, I mean by that I didn't understand how do I use them in my question, so feel free if you'd like to use them it's acceptable for me.
My problem is : (attaching a video of my problem explanation : https://www.youtube.com/watch?v=dKIf6mQUfnY so it's recommended and preferable to understand my problem and waste your time reading my problem below is see the video because it's explained more understandable on the video , the state machine is given for me and there's no need to implement it, so it's as input to my function )
I have a diagram of state machine (on the left side in the photo below) , every dots respectively represent the current state that Im in,
first point represents state : 00
second point below the first point represents state: 10
third point below the second point represents state: 01
fourth point below the third point represents state : 11
So graphically what I explained above is :
00 first point
10 second point
01 third point
11 fourth point
this state machine is given to the function, every Arrow in the state machine (the left side in my photo below) represent:
given input bit (zero or 1) / current state output , so for first point 00 there's two arrows crossing from it, first row if the input is zero then it's 0/00 , this means that the given input bit is zero and output is 00 , the second arrow from state 00 if the input bit is 1 then it will transit to state 10 (it was 00 and if input 1 from left side then it will be 10) and output is 11 ..etc for all state shows in the left side in my attached photo below. so my function that Im trying to implement in matlab is viterbi decode according to hamming distance!
As you see in the photo above, the right side of my photo is what my function is going to do and return according to it the required output, my function is actually what it does is decoding according to given state machine diagram and by hamming distance the input data to figure what are the bits.
for example lets assume my input is : input = [0 0 0 1 0 1 1 0 1 0];
so if we look at left side of attached photo above, we see that over all arrows on state machine output are two bits (00 , 01 , 10 ,11) so we must devide the input to two bits and it will be like this : 00 01 01 10 10
and now we calculate the hamming distance between every two pairs of the given input with out state machine arrows outputs, this means:
input as I said devided it to pairs : 00 01 01 10 10
so now I look to state machine outputs and I start from first point there's two arrows 0/00 , 1/11 so I look at my input first pair 00 , and do comparing by hamming distance (hamming distance is the number of differences between the two compared patterns ) , for first row that cross fro first point of state machine 0/00 the output (second pattern) is 00 I compare to the the first pair of my input which it's also 00 so the hamming distance is 0 because (00 compared to 00 has no differences) ..so you see on the right side of my photo that there's an arrow below 00 has hamming distance 0. I look now for the second arrow that cross from first point 00 of state machine (left side) I see it's 1/11 so here the output as shown is 11 compared to right side at my input pair 00 the hamming distance is 2 (00 compared to 11 => hamming distance is 2 because the differences between 00 and 11 is 2) , so if you look on the right side of my photo you see under 00 there's two arrows one with hamming distance 0, second arrow with hamming distance 2 .
Now I go to the second pair input on the right side which it's 01 , now do the comparing between 01 to the outputs of states of my state machine on the left side, this means we look at first point of my state machine which it's 0/00 for first arrow, second arrow it's 1/11, I compare 00 and 11 (second outputs that's shown on my arrows of my state machine). so I look at 01 at right side of my photo, and take all hamming distance between it to 00 and 11 .
Under 01, for first arrow on the right side , I look at 01 and 00 so I see hamming distance is 1, so the value on that arrow is 1, so the value of that arrow is =1+ (hamming distance on the previous arrow which it's zero in my case ) = 1 . Now I look to second arrow under 01 on the right side the hamming distance between 11 and 01 is 1, so the value of that arrow is 1+( (hamming distance on the previous arrow which it's zero in my case ) =1 .
I complete like this scheme under whole states on right side 00 01 01 10 10 and for each state on the right side I take the hamming distance according to state machine on the left side respectively.
After I finish all states on the right side, I take for every state the minimum distance under of it and if there's two hamming distance with the same value I return one of them(doesn't matter) like min(2,2)=2 ..
so after taking all the minimum distance under each state at the right side (on the photo I circlued by red circules on the path I I take -minimum hamming distances), I retrun respectively the input bits from state machine on the left side for each state corresponded to the minimum hamming distance path that I drew on thew right side, in my case this means the path is: (I mean ny the path what's circuled in red circles)
00 00 11 10 10
so I look at state machine on left side and correspondingly to that path to my left side state machine I take its input values , I mean by input values the left side of the value of my arrow for instance if it was 1/11 the left side of 1/11 is 1 and the right side is 11 ..
So correspondingly to the path that I drew on the right side I look on the left side and take all the input values of my arrows respectively to the path that I drew on the right side.
So the output in my case is array of binary integers which it's :
output=[0 0 1 1 0];
Note once again if two haming distances under any states of the right side having the same values so it doesn't matter which arrow to return because they have the same value.
In addition, the state machine on the left side is given to the function that I want to implement and there's no need to implement it again, it's given as input to my function.
Any assistance please how do I implement that in matlab? thanks alot, I really appreciate your help to me.
Im posting here because I really tried about two weeks struggling my problem and at the end unfortunately Im not getting the required output and my code is too long aside to that my algorithm is too long, here's my code down what I tried:
%implementation of viterbi algorithm
clc;
data=[];
tic;
%generate data of random binary sequence
%take system time(cputime) in nanoseconds
for i=1:1:10
ms=round(toc*1000*60*60*60);
r=mod(ms,2);
if(r==1)
data=[data,r];
else
data=[data,r];
end
end
disp(data);
%call function to encode data
endata=encode_data(data); %here implicitly I have encoded the data by calling other function
disp("Data Encoded");
disp(endata);
p=viterbidec(endata);
data1=p;
disp("Data Decoded.");
disp(data1);
temp=1;
ldata=length(data);
%compare the input data and decoded data is equal or not
for i=1:1:ldata
if data(i)==data1(i)
% disp("equal");
else
temp=temp+1;
end
end
if (temp>1)
disp("Not equal");
else
disp("Equal");
end
function [code]= encode_data(message1)
%As the encoder is 1/2=1/n
%and n is length of generated codeword
for i=1:length(message1)
message(i)= num2str(message1(i));
end
state='00';
next_state='00';
code1=[];
message=[message '00'];
message=[message];
for t=1:length(message)
inp= message(t);
state=next_state;
if(state=='00')
if(inp=='0')
next_state='00';
outp='00';
else
next_state='10';
outp= '11';
end
elseif(state=='10')
if(inp=='0')
next_state='01';
outp='10';
else
next_state='11';
outp= '01';
end
elseif(state=='01')
if(inp=='0')
next_state='00';
outp='11';
else
next_state='10';
outp= '00';
end
elseif(state=='11')
if(inp=='0')
next_state='01';
outp='01';
else
next_state='11';
outp= '10';
end
end
code1= [code1 outp];
end
for i=1:length(code1)
code(i)= str2num(code1(i));
end
end
function [dec_op]=viterbidec(rcvdmsg)
% as our convolutional code is with 2 codeword then to make it simple
%combine 2 bits in 1
input=[];
for j=1:2:length(rcvdmsg)
input=[ input (rcvdmsg(j))* 2 + (rcvdmsg(j+1))];
end
%it produces 0 for 00,1 for 01,2 for 10 and 3 for 11
%initializing all arrays
op_table=[00 00 11; 01 11 00; 10 10 01; 11 01 10]; %OUTPUT array
ns_table=[0 0 2; 1 0 2; 2 1 3; 3 1 3]; %NEXT STATE array
transition_table=[0 1 1 55; 0 0 1 1; 55 0 55 1; 55 0 55 1];
%There are 17 time instants which is made up of our 15-bit message plus 2 memory flush bits.
st_hist(1:4, 1:17)=55; %STATE HISTORY array
aem=zeros(4, 17); %ACCUMULATED ERROR METRIC (AEM) array
ssq=zeros(1, 17); %STATE SEQUENCE array
lim=length(input); %length of input
for (t=0:1:lim) %clock loop
% t 0 represents inital condition of encoder
if(t==0)
st_hist(1,1)=0; %start at state 00
else
temp_state=[];%vector to store possible states at an instant
temp_metric=[];%vector to store metrics of possible states
temp_parent=[];%vector to store parent states of possible states
for (i=1:1:4)
i;
in=input(t);
if(st_hist(i, t)==55) %if invalid state
%do nothing
else
ns_a=ns_table(i, 2)+1; %next state if input is 0
ns_b=ns_table(i, 3)+1; %next state if input is 1
op_a=op_table(i, 2); %next possible output if input is 0
op_b=op_table(i, 3); %next possible output if input is 1
cs=i-1; %current state
%Branch metrics are the Hamming distance values at each time instant for
%the paths between the states at the previous time instant and
%the states at the current time instant.
M_a=hamm_dist(in, op_a); %branch metric for ns_a
M_b=hamm_dist(in, op_b); %branch metric for ns_b
indicator=0; %flag to indicate redundant states
%em_c: error metric of current state
%em_r: error metric of redundant state
for k=1:1:length(temp_state) %check next states
%if next possible redundant
if(temp_state(1,k)==ns_a)
indicator=1;
%We add these branch metric values to
%the previous accumulated error metric values
%associated with each state.
em_c=M_a + aem(i,t);
em_r=temp_metric(1,k) + aem(temp_parent(1, k)+1,t);
%If the members of a pair of accumulated
%error metrics going into a particular state are equal, we just save that value
if( em_c< em_r)%compare the two error metrics
st_hist(ns_a,t+1)=cs;%select state with low AEM
temp_metric(1,k)=M_a;
temp_parent(1,k)=cs;
end
end
%if next possible state
if(temp_state(1,k)==ns_b)
indicator=1;
em_c=M_b + aem(i,t);
em_r=temp_metric(1,k) + aem(temp_parent(1, k)+1,t);
if( em_c < em_r)%compare the two error metrics
st_hist(ns_b,t+1)=cs;%select state with low AEM
temp_metric(1,k)=M_b;
temp_parent(1,k)=cs;
end
end
end
%if none of the 2 possible states are redundant
if(indicator~=1)
%update state history table
st_hist(ns_a,t+1)=cs;
st_hist(ns_b,t+1)=cs;
%update the temp vectors accordingly
temp_parent=[temp_parent cs cs];
temp_state=[temp_state ns_a ns_b];
temp_metric=[temp_metric M_a, M_b];
end
end
end
%update the AEMs (accumulative error metrics) for all states for
%current instant 't'
for h=1:1:length(temp_state)
xx1=temp_state(1, h);
xx2=temp_parent(1, h)+1;
aem(xx1, t+1)=temp_metric(1, h) + aem(xx2, t);
end
end
end
%trace back
%Select the state having the smallest accumulated error metric
%and save the state number of that state.
for(t=0:1:lim)
%take first col of aem
slm=min(aem(:, t+1));
slm_loc=find( aem(:, t+1)==slm );
sseq(t+1)=slm_loc(1)-1;
end
% recreate the sequence of bits that Were input to the convolutional encoder.
dec_op=[];
for p=1:1:length(sseq)-1
p;
dec_op=[dec_op, transition_table((sseq(p)+1), (sseq(p+1)+1))];
end
%Hamming distance is the metric were going to use between the received symbol
%and the possible symbols.
%Returns the hamming distance b/w two 2 bit codes
function [HD]=hamm_dist(A,B)
HD=0;
for i=1:2
a=bitget(A, i);
b=bitget(B, i);
if(a~=b)
HD=HD+1;
end
end
end
end
it would be appreciated if anyone could help to implement my problem solution in matlab !
thanks.

댓글을 달려면 로그인하십시오.

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!