function[decoder_output,survivor_state,cumulated_metric]=viterbi_4QAM(G,k,channel_output,q,ro)
% Funcion modificada para modulacion 4QAM usando codificador de Ungerboek
% H=[2,5]
%VITERBI: The Viterbi decoder for convolutional codes
% [decoder_output, survivor_state, cumulated_metric]
% viterbi(G,k,channel_output)
% G is a n x Lk matrix each row of which determines the connections
% from the shift register to the n-th output of the code, k/n is
% the rate of the code. survivor_state is a matrix showing the
% optimal path through the trellis. The metric is given in a
% separate function metric(x,y) and can be specified to
% accommodate hard and soft decision. This algorithm minimizes
% the metric rather than maximizing the likelihood.
% M is obtained from modulation M-PSK of the received signal.
% q is obtained from modulation M-PSK of the convolutional encoder.
n=size(G,1); % numero de salidas
%check the sizes
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('channel output not of the right size')
end
L=size(G,2)/k;
number_of_states=q^((L-1)*k);
% generate state transition matrix, output matrix, and input matrix
input=[0 1 0 0;0 0 0 1;1 0 0 0;0 0 1 0];
output=[0 2;1 3;0 2;1 3];
nextstate=[0 1;2 3;1 0;3 2];
state_metric=zeros(number_of_states,2);
depth_of_trellis=length(channel_output); %profundidad de la trelisa es dada por el numero de simbolos enviados
survivor_state=zeros(number_of_states,depth_of_trellis+1);
% start decoding of non-tail channel outputs
for i=1:depth_of_trellis-L+1
flag=zeros(1,number_of_states);
if i<=1
states=0;
elseif i<=2
states=1;
else
states=number_of_states-1;
end
for j=0:1:states
for l=0:q^k-1
branch_metric=0;
binary_output = deci2bin(output(j+1,l+1),n,q);
simb_output = M_4QAM(binary_output);
metrica = metric(channel_output(1,i),ro(1,i)*simb_output);
branch_metric = branch_metric+metrica;
if((state_metric(nextstate(j+1,l+1)+1,2)>state_metric(j+1,1)+branch_metric)||flag(nextstate(j+1,l+1)+1)==0)
state_metric(nextstate(j+1,l+1)+1,2)=state_metric(j+1,1)+branch_metric;
survivor_state(nextstate(j+1,l+1)+1,i+1)=j;
flag(nextstate(j+1,l+1)+1)=1;
end
end
end
state_metric=state_metric(:,2:-1:1);
end
% start decoding of the tail channel-outputs
for i=depth_of_trellis-L+2:depth_of_trellis
flag=zeros(1,number_of_states);
step=1;
if i~=depth_of_trellis-L+2
step=2;
end
for j=0:step:number_of_states-1
l=0;
if j>1
l=1;
end
branch_metric=0;
binary_output = deci2bin(output(j+1,l+1),n,q);
simb_output = M_4QAM(binary_output);
metrica = metric(channel_output(1,i),ro(1,i)*simb_output);
branch_metric = branch_metric+metrica;
if((state_metric(nextstate(j+1,l+1)+1,2)>state_metric(j+1,1)+branch_metric)||flag(nextstate(j+1,l+1)+1)==0)
state_metric(nextstate(j+1,l+1)+1,2)=state_metric(j+1,1)+branch_metric;
survivor_state(nextstate(j+1,l+1)+1,i+1)=j;
flag(nextstate(j+1,l+1)+1)=1;
end
end
state_metric=state_metric(:,2:-1:1);
end
% generate the decoder output from the optimal path
state_sequence=zeros(1,depth_of_trellis+1);
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
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,q);
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);
