% viterbi decode
% 07.10.31

function deconvolution_sequence = deconvolution(convolution_sequence)

% route = zeros(4,20);


t_output = convolution_sequence;
a = size(convolution_sequence);
number_inputdata = a(2)/2 - 6;

s = [0];
number_trip = 1;
trip_old = zeros(10,100000);
trip_new = zeros(10,100000);
haming_distance = zeros(1,100000);
delay_6_to_0 = zeros(1,7);
bit_number = 1;
t_output_1 = 0;
t_output_2 = 0;

n = 1;
r0 = t_output(1);
r1 = t_output(2);
trip_new(1,1) = 0; 
trip_new(2,1) = 1;
number_trip = 2;
for k = 1:2
   delay_6_to_0 = zeros(1,7);
   for m = 1:n
      delay_6_to_0 = circshift(delay_6_to_0,[0,1]);
      delay_6_to_0(1) = trip_new(k,m);
      t_output_1(m) = delay_6_to_0(1) + delay_6_to_0(3) + delay_6_to_0(4) + delay_6_to_0(6) + delay_6_to_0(7);
      generator0 = mod(t_output_1(m),2);
      t_output_2(m) = delay_6_to_0(1) + delay_6_to_0(2) + delay_6_to_0(3) + delay_6_to_0(4) + delay_6_to_0(7);
      generator1 = mod(t_output_2(m),2);
   end

   if r0 ~= generator0
      haming_distance(k) = haming_distance(k)+1;
   end
   if r1 ~= generator1
      haming_distance(k) = haming_distance(k)+1;
   end%caculate the haming distance of one trip
end%Add

for n = 2:number_inputdata
    r0 = t_output(2*(n-1)+1);
    r1 = t_output(2*n);
    
    trip_old = trip_new;
    haming_distance_old = haming_distance;
    for m = 1:number_trip
        trip_new(2*(m-1)+1,:) = trip_old(m,:);
        trip_new(2*(m-1)+1,n) = 0;
        trip_new(2*(m-1)+2,:) = trip_old(m,:);
        trip_new(2*(m-1)+2,n) = 1;
        haming_distance(2*(m-1)+1) = haming_distance_old(m);
        haming_distance(2*(m-1)+2) = haming_distance_old(m);
    end
    number_trip = number_trip*2;
    for k = 1:number_trip
        delay_6_to_0 = zeros(1,7);
       for m = 1:n
          delay_6_to_0 = circshift(delay_6_to_0,[0,1]);
          delay_6_to_0(1) = trip_new(k,m);
          t_output_1(m) = delay_6_to_0(1) + delay_6_to_0(3) + delay_6_to_0(4) + delay_6_to_0(6) + delay_6_to_0(7);
          generator0 = mod(t_output_1(m),2);
          t_output_2(m) = delay_6_to_0(1) + delay_6_to_0(2) + delay_6_to_0(3) + delay_6_to_0(4) + delay_6_to_0(7);
          generator1 = mod(t_output_2(m),2);
       end
    
       if r0 ~= generator0
          haming_distance(k) = haming_distance(k)+1;
       end
       if r1 ~= generator1
          haming_distance(k) = haming_distance(k)+1;
       end
    end%Add
    
    min_number = 1;
    trip_min_4 = zeros(4,100000);
    haming_distance_min = zeros(1,4);
    for m = 1:4
        min = haming_distance(1);
        for l = 1:number_trip
            if haming_distance(l) < min
                min = haming_distance(l);
                min_number = l;
            end
        end%Compare
        trip_min_4(m,:) = trip_new(min_number,:);
        haming_distance_min(m) = haming_distance(min_number);
%         haming_distance(min_number) = 100;
    end
    
    for m = 1:4
        trip_new(m,:) = trip_min_4(m,:);
        haming_distance(m) = haming_distance_min(m);
    end
    number_trip = 4;
    
end
deconvolution_sequence = trip_new(min_number,1:36);