%卷積碼的譯碼
function decoder_output=viterbi(G,k,channel_output)
%VITERBI		卷積碼的維特比解碼器
%[decoder_ouput,survivor_state,cumulated_metric]=viterbi(G,k,channel_output)
%				G是一個(gè)n*Lk矩陣，該矩陣的每一行確定了從移位記錯(cuò)器到第n個(gè)輸出間的連接，
%				是碼速率。
%				survivor_state是表示通過(guò)網(wǎng)絡(luò)的最佳路徑的矩陣。
%				量度在另一個(gè)函數(shù)metric（x,y）中給出，而且可根據(jù)
%				硬判決和軟判決來(lái)指定。
%				該算法最小化了量度而不是最大化似然

n=size(G,1);	%取出矩陣G的一維大小，即得出輸出端口
	%	檢查大小
if rem(size(G,2),k)~=0		%當(dāng)G列數(shù)不是k的整數(shù)倍時(shí)
   error('Size of G and k do not agree')		%發(fā)出出錯(cuò)信息
end
if rem(size(channel_output,2),n)~=0			%當(dāng)輸出量元素個(gè)數(shù)不是輸出端口的整數(shù)倍時(shí)
   error('Channel output not of the right size')		%發(fā)出出錯(cuò)信息
end

L=size(G,2)/k;			%得出移位數(shù)，即寄存器組的個(gè)數(shù)

	%		由于L-1個(gè)寄存器組的狀態(tài)即可表示出輸出狀態(tài)，
	%		所以總的狀態(tài)數(shù)number_of_states可由前L-1個(gè)
	%		寄存器的狀態(tài)組合來(lái)確定
number_of_states=2^((L-1)*k);

	%	產(chǎn)生狀態(tài)轉(zhuǎn)移矩陣、輸出矩陣和輸入矩陣
for j=0:number_of_states-1		%j表示當(dāng)前寄存器組的狀態(tài)因?yàn)闋顟B(tài)是從零
   									%開(kāi)始的,所以循環(huán)從0到number_of_states-1
                              
      for l=0:2^k-1				%l為從k個(gè)輸入端的信號(hào)組成的狀態(tài)，總的狀
                                 	%態(tài)數(shù)為2^k，所以循環(huán)從0到2^k-1
                                    
      %	nxt_stat完成從當(dāng)前的狀態(tài)和輸入的矢量得出下寄存器組的一個(gè)狀態(tài)
      [next_state,memory_contents]=nxt_stat(j,l,L,k);
      
      %	input數(shù)組值是用于記錄當(dāng)前狀態(tài)到下一個(gè)狀態(tài)所要的輸入信號(hào)矢量
      %  input數(shù)組的維數(shù)：	一維坐標(biāo)x=j+1指當(dāng)前狀態(tài)的值
      %					  	二維坐標(biāo)y=next_state+1指下一個(gè)狀態(tài)的值
      %	由于Matlab中數(shù)組的下標(biāo)是從1開(kāi)始的，而狀態(tài)值
      %	是從0開(kāi)始的，所以以上坐標(biāo)值為:狀態(tài)值+1
      input(j+1,next_state+1)=l;	
      %	branch_output用于記錄在狀態(tài)j下輸入l時(shí)的輸出
      branch_output=rem(memory_contents*G',2);
      %	nextstate數(shù)組記錄了當(dāng)前狀態(tài)j下輸入l時(shí)的下一個(gè)狀態(tài)
      nextstate(j+1,l+1)=next_state;
      %	output數(shù)組記錄了當(dāng)前狀態(tài)j下輸入l時(shí)的輸出（十進(jìn)制）
      output(j+1,l+1)=bin2deci(branch_output);
   end
end

%		state_metric數(shù)組用于記錄譯碼過(guò)程在每狀態(tài)時(shí)的漢明距離
%		state_metric大小為number_of_states×2，（:,1）當(dāng)前
%		狀態(tài)位置的漢明距離，為確定值，而（:,2）為當(dāng)前狀態(tài)加輸入
%		得到的下一個(gè)狀態(tài)漢明距離，為臨時(shí)值
state_metric=zeros(number_of_states,2);
%		depth_of_trellis用于記錄網(wǎng)格圖的深度
depth_of_trellis=length(channel_output)/n;
%		輸出矩陣，每一列為一個(gè)輸出狀態(tài)
channel_output_matrix=reshape(channel_output,n,depth_of_trellis);
%		survivor_state描述譯碼過(guò)程中在網(wǎng)格圖中的路徑
survivor_state=zeros(number_of_states,depth_of_trellis+1);
%開(kāi)始無(wú)尾信道輸出的解碼
for i=1:depth_of_trellis-L+1	%i指示網(wǎng)格圖的深度
   %		flag矩陣用于記錄網(wǎng)格圖中的某一列是否被訪問(wèn)過(guò)
   flag=zeros(1,number_of_states);
   if i<=L
      step=2^((L-i)*k);		%在網(wǎng)格圖的開(kāi)始處，并不是所有的狀態(tài)都取
   else							%用step來(lái)說(shuō)明這個(gè)變化
      step=1;					%狀態(tài)數(shù)從1→2→4→...→number_of_states
   end
   for j=0:step:number_of_states-1		%j表示寄存器的當(dāng)前狀態(tài)
      for l=0:2^k-1					%l為當(dāng)前的輸入
         branch_metric=0;			%用于記錄碼間距離
         %		將當(dāng)前狀態(tài)下輸入狀態(tài)l時(shí)的輸出output轉(zhuǎn)為n位二進(jìn)制，以便
         %		計(jì)算碼間距離（說(shuō)明：數(shù)組坐標(biāo)大小變化同上）。
         binary_output=deci2bin(output(j+1,l+1),n);
         %		計(jì)算實(shí)際的輸出碼同網(wǎng)格圖中此格某種輸出的碼間距離
         for ll=1:n
            branch_metric=branch_metric+metric(channel_output_matrix(ll,i),binary_output(ll));
         end
         %		選擇碼間距離較小的那條路徑
         %		選擇方法：
         %				當(dāng)下一個(gè)狀態(tài)沒(méi)有被訪問(wèn)時(shí)就直接賦值，否則，用比它小的將其覆蓋
         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) %或的關(guān)系
            %	下一個(gè)狀態(tài)的漢明距離（臨時(shí)值）=當(dāng)前狀態(tài)的漢明距離（確定值）+ 碼間距離
            state_metric(nextstate(j+1,l+1)+1,2)=state_metric(j+1,1)+branch_metric;
            %	survivor_state數(shù)組的一維坐標(biāo)為下一個(gè)狀態(tài)值，二維坐標(biāo)為此狀態(tài)
            %	在網(wǎng)格圖中的列位置，記錄的數(shù)值為當(dāng)前狀態(tài)，這樣就可以從網(wǎng)格圖中
            %	某位置的某個(gè)狀態(tài)得出其對(duì)應(yīng)上一個(gè)列位置的狀態(tài)，從而能很方便的完
            %	成譯碼過(guò)程。
            survivor_state(nextstate(j+1,l+1)+1,i+1)=j;
            flag(nextstate(j+1,l+1)+1)=1;		%指示該狀態(tài)已被訪問(wèn)過(guò)
         end
      end
   end
   state_metric=state_metric(:,2:-1:1);		%移動(dòng)state_metric，將臨時(shí)值移為確定值
end

%開(kāi)始尾部信道輸出解碼
for i=depth_of_trellis-L+2:depth_of_trellis
   flag=zeros(1,number_of_states);
   %  狀態(tài)數(shù)從number_of_states→number_of_states/2→...→2→1
   %	程序說(shuō)明同上，只不過(guò)輸入矢量只為0
   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 ll=1:n
         branch_metric=branch_metric+metric(channel_output_matrix(ll,i),binary_output(ll));
      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
%	從最佳路徑中產(chǎn)生解碼
%	譯碼過(guò)程可從數(shù)組survivor_state的最后一個(gè)位置向前逐級(jí)譯碼
state_sequence=zeros(1,depth_of_trellis+1);
%	survivor_state數(shù)組的最后的輸出狀態(tài)肯定是“0”
state_sequence(1,depth_of_trellis)=survivor_state(1,depth_of_trellis+1);
%	逐級(jí)譯碼過(guò)程
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
decorder_output_matrix=zeros(k,depth_of_trellis-L+1);
for i=1:depth_of_trellis-L%+1
   %		根據(jù)數(shù)組input的定義來(lái)得出從當(dāng)前狀態(tài)到下一個(gè)狀態(tài)的輸入信號(hào)矢量
   dec_output_deci=input(state_sequence(1,i)+1,state_sequence(1,i+1)+1);
   %		轉(zhuǎn)成二進(jìn)制信號(hào)
   dec_output_bin=deci2bin(dec_output_deci,k);
   %		將一次譯碼存入譯碼輸出矩陣decoder_output_matrix相應(yīng)的位置
   decoder_output_matrix(:,i)=dec_output_bin(k:-1:1)';
end
%		按照一維序列形式重新組織輸出
decoder_output=reshape(decoder_output_matrix,1,k*(depth_of_trellis-L));%+1
%		state_metric為網(wǎng)格圖最后一個(gè)列位置中“0”狀態(tài)位置的漢明距
%		離，這個(gè)值就是整個(gè)譯碼過(guò)程中的漢明距離。
cumulated_metric=state_metric(1,1);