%viterbi.m
%viterbi解碼程序
function[decoder_output,survivor_state,cumulated_metric]=viterbi(G,k,channel_output)
%[decoder_output,survivor_state,cumulated_metric]=viterbi(G,k,channel_output)
%其中G是一個(gè)n行L*k列矩陣，它的每一行決定了從移位寄存器到輸入碼字的連接方式.
%survivor_state是一個(gè)矩陣，它顯示了通過(guò)網(wǎng)格的最優(yōu)路徑，這個(gè)矩陣通過(guò)一個(gè)單獨(dú)
%的函數(shù)metric(x,y)給出。

n=size(G,1);
%檢驗(yàn)G的維數(shù)
if rem(size(G,2),k)~=0
   error('Size of G and k do not agree')
end
if rem(size(channel_output,2),n)~=0
error('channle output not of the right size')
end
L=size(G,2)/k;
number_of_states=2^((L-1)*k);

%產(chǎn)生狀態(tài)轉(zhuǎn)移矩陣，輸出矩陣和輸入矩陣
for j=0:number_of_states-1
for t=0:2^k-1
[next_state,memory_contents]=nxt_stat(j,t,L,k);
input(j+1,next_state+1)=t;
branch_output=rem(memory_contents*G',2);
nextstate(j+1,t+1)=next_state;
output(j+1,t+1)=bin2deci(branch_output);
end
end
input;
state_metric=zeros(number_of_states,2);
depth_of_trellis=length(channel_output)/n;
channel_output_matrix=reshape(channel_output,n,depth_of_trellis);
survivor_state=zeros(number_of_states,depth_of_trellis+1);
[row_survivor col_survivor]=size(survivor_state);
%開(kāi)始非尾信道輸出的解碼
%i為段，j為每一階段的狀態(tài)，t為輸入
for i=1:depth_of_trellis-L+1
flag=zeros(1,number_of_states);
if i<=L
step=2^((L-i)*k);
else
step=1;
end
for j=0:step:number_of_states-1
for t=0:2^k-1
branch_metric=0;
binary_output=deci2bin(output(j+1,t+1),n);
for tt=1:n
    branch_metric=branch_metric+metric(channel_output_matrix(tt,i),binary_output(tt));
end

if((state_metric(nextstate(j+1,t+1)+1,2)>state_metric(j+1,1)+branch_metric)|flag(nextstate(j+1,t+1)+1)==0)
    state_metric(nextstate(j+1,t+1)+1,2)=state_metric(j+1,1)+branch_metric;
survivor_state(nextstate(j+1,t+1)+1,i+1)=j;
flag(nextstate(j+1,t+1)+1)=1;
end
end
end
state_metric=state_metric(:,2:-1:1);
end

%開(kāi)始尾信道輸出的解碼
for i=depth_of_trellis-L+2:depth_of_trellis
flag=zeros(1,number_of_states);
last_stop=number_of_states/(2^((i-depth_of_trellis+L-2)*k));
for j=0:last_stop-1
branch_metric=0;
binary_output=deci2bin(output(j+1,1),n);
for tt=1:n
branch_metric=branch_metric+metric(channel_output_matrix(tt,i),binary_output(tt));
end

if((state_metric(nextstate(j+1,1)+1,2)>state_metric(j+1,1)+branch_metric)|flag(nextstate(j+1,1)+1)==0)
    state_metric(nextstate(j+1,1)+1,2)=state_metric(j+1,1)+branch_metric;
    survivor_state(nextstate(j+1,1)+1,i+1)=j;
    flag(nextstate(j+1,1)+1)=1;
end
end
state_metric=state_metric(:,2:-1:1);
end

%從最優(yōu)路徑產(chǎn)生解碼輸出
%由段得到狀態(tài)序列，再由狀序列從input矩陣中得到該段的輸出
state_sequence=zeros(1,depth_of_trellis+1);
size(state_sequence);
state_sequence(1,depth_of_trellis)=survivor_state(1,depth_of_trellis+1);
for i=1:depth_of_trellis
        state_sequence(1,depth_of_trellis-i+1)=survivor_state((state_sequence(1,depth_of_trellis+2-i)+1),depth_of_trellis-i+2);
    end
state_sequence;

decoder_output_matrix=zeros(k,depth_of_trellis-L+1);
for i=1:depth_of_trellis-L+1
dec_output_deci=input(state_sequence(1,i)+1,state_sequence(1,i+1)+1);
dec_output_bin=deci2bin(dec_output_deci,k);
decoder_output_matrix(:,i)=dec_output_bin(k:-1:1)';
end
decoder_output=reshape(decoder_output_matrix,1,k*(depth_of_trellis-L+1));
cumulated_metric=state_metric(1,1);
%************************end of file***********************************