?? viterbi.cpp
字號:
//****************************************************************
//(2,1,2)卷積碼編碼器與viterbi譯碼算法的實現
//該碼的生成電路見課本P393，圖10-9，G（D）=[1，1+D+D^2]；
//****************************************************************
//通信與信息系統專業 詹銳鑫 07212439 2008年1月24日
//****************************************************************
#include <iostream.h>
#include <stdlib.h>
const int length=20; //表示卷積碼的輸出長度；顯然，輸出長度為輸入長度的2倍；
int m[length/2]={1,0,1,1,1,0,0,0,1,1}; //輸入序列，其長度為輸出碼字的一半；
int code[length]={0}; //編碼器的輸出序列，其長度為輸入的2倍；
int rs[length]={1,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,1,0,0};
//經過信道后，譯碼器的輸入信息；可能有若干位出錯；
int ds[length/2]={0}; //譯碼器的輸出，可糾正若干錯誤位；
//****************************************
void coding(int *in_m,int * out_d); //編碼器函數；
void viterbi(int *rs,int *ds); //veterbi譯碼器函數；
//****************************************
void main()
{
int i=0;
//對于給定的輸入信息，輸出其編碼；
coding(m,code); //若想改變測試數據，可修改前面的m和length值；
//可以得到不同的測試數據；
for(i=0;i<length/2;i++)
cout<<m[i];
cout<<" 輸入信息元（未編碼）"<<endl;
for(i=0;i<length;i++)
cout<<code[i];
cout<<" 輸出編碼碼字（編碼器輸出）"<<endl;
//對于給定的譯碼器輸入，輸出其譯碼值；
viterbi(rs,ds); //可由上面的編碼器輸出，隨機修改N位，測試其譯碼器的輸出；
//也可以采用rand()函數，隨機改變N位數據
//作為信道傳輸錯誤的仿真；
for(i=0;i<length;i++)
cout<<rs[i];
cout<<" 譯碼器的輸入序列，含有N位隨機或突發錯誤；"<<endl;
for(i=0;i<length/2;i++)
cout<<ds[i];
cout<<" 譯碼器的輸出,可能修改出現的錯誤,也可能譯碼失敗,但仍輸出誤差最小的譯碼"<<endl;
}
//(2,1,2)卷積碼編碼器；
//采用狀態機編程思想；劃分為四個狀態，并按輸入，進行狀態轉移；
void coding(int * in_m,int * out_d)
{
int state=0; //當前狀態；
int next_state=0; //下一狀態值；
for(int i=0;i<(length)/2;i++) //有length/2個輸入，就有length/2次狀態轉移；
{
if(state==0) //狀態0；
{
if(in_m[i]==0) //輸入0，仍處于狀態0，輸出：00；
{
next_state=0;
out_d[2*i]=0;
out_d[2*i+1]=0;
}
else if(in_m[i]==1) //輸入1，跳到狀態1，輸出：11；
{
next_state=1;
out_d[2*i]=1;
out_d[2*i+1]=1;
}
}
else if(state==1) //狀態1
{
if(in_m[i]==0) //輸入0，跳到狀態2，輸出：10；
{
next_state=2;
out_d[2*i]=1;
out_d[2*i+1]=0;
}
else if(in_m[i]==1) //輸入1，跑到狀態3，輸出：01；
{
next_state=3;
out_d[2*i]=0;
out_d[2*i+1]=1;
}
}
else if(state==2) //狀態2
{
if(in_m[i]==0) //輸入0，跳到狀態0，輸出：11；
{
next_state=0;
out_d[2*i]=1;
out_d[2*i+1]=1;
}
else if(in_m[i]==1) //輸入1，跳到狀態1，輸出：00；
{
next_state=1;
out_d[2*i]=0;
out_d[2*i+1]=0;
}
}
else if(state==3) //狀態3
{
if(in_m[i]==0) //輸入0，跳到狀態2，輸出：01；
{
next_state=2;
out_d[2*i]=0;
out_d[2*i+1]=1;
}
else if(in_m[i]==1) //輸入法1，跳到狀態3，輸出：10；
{
next_state=3;
out_d[2*i]=1;
out_d[2*i+1]=0;
}
}
state=next_state; //跳到下一狀態；
}
return; //編碼結束；
}
//viterbi譯碼算法實現；
void viterbi(int *rs,int *ds)
{
struct unit //各時刻各狀態記錄
{
unsigned last_point; //本狀態的上一最優狀態
unsigned weight; //到本狀態的總重量
unsigned over; //本狀態是否走過
}; //（length/2）+1個時刻,4個狀態
unit point[(length/2)+1][4];
int i,j;
for(i=0;i<(length/2)+1;i++)
for (j=0;j<4;j++)
{ //初始化清零所有時刻狀態
point[i][j].last_point=0;
point[i][j].weight=0;
point[i][j].over=0;
}
point[0][0].over=1; //從零時刻零狀態開始
//上一時刻此狀態到本時刻此狀態，其重量的改變，采用^按位異或
//t=1時刻：
point[1][0].weight=point[0][0].weight+(rs[0]^0)+(rs[1]^0);
point[1][1].weight=point[0][0].weight+(rs[0]^1)+(rs[1]^1);
point[1][0].last_point=0;
point[1][1].last_point=0;
//如果只有兩輸入，則結束譯碼過程：
if(length==2)
{
if(point[1][0].weight<point[1][1].weight)
{
ds[0]=0;
}
else ds[0]=1;
return;
}
//t=2時刻：
//有多于兩個輸入，繼續譯碼過程：
point[2][0].weight=point[1][0].weight+(rs[2]^0)+(rs[3]^0);
point[2][1].weight=point[1][0].weight+(rs[2]^1)+(rs[3]^1);
point[2][0].last_point=0;
point[2][1].last_point=0;
point[2][2].weight=point[1][1].weight+(rs[2]^1)+(rs[3]^0);
point[2][3].weight=point[1][1].weight+(rs[2]^0)+(rs[3]^1);
point[2][2].last_point=1;
point[2][3].last_point=1;
point[1][0].over=1;
point[1][1].over=1;
//有多于6個輸入，則繼續譯碼，否則結束譯碼過程：
unsigned p1,p2; //到達本時刻本狀態的兩條路徑的各自重量；
if(length>=6)
{
//t=3,4,5,6……時刻：
for (i=3;i<=length/2;i++)
{
p1=point[i-1][0].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^0); //處于狀態0
p2=point[i-1][2].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^1); //兩條輸入路徑各自重量；
//總距離p1,p2,取最短者
if (p1>p2)
{
point[i][0].last_point=2;
point[i][0].weight=p2;
point[i-1][2].over=1;
}
else
{
point[i][0].last_point=0;
point[i][0].weight=p1;
point[i-1][0].over=1;
}
p1=point[i-1][0].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^1); //state=1
p2=point[i-1][2].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^0);
if (p1>p2)
{
point[i][1].last_point=2;
point[i][1].weight=p2;
point[i-1][2].over=1;
}
else
{
point[i][1].last_point=0;
point[i][1].weight=p1;
point[i-1][0].over=1;
}
p1=point[i-1][1].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^0); //state=2
p2=point[i-1][3].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^1);
if (p1>p2)
{
point[i][2].last_point=3;
point[i][2].weight=p2;
point[i-1][3].over=1;
}
else
{
point[i][2].last_point=1;
point[i][2].weight=p1;
point[i-1][1].over=1;
}
p1=point[i-1][1].weight+(rs[2*(i-1)]^0)+(rs[2*(i-1)+1]^1); //state=3
p2=point[i-1][3].weight+(rs[2*(i-1)]^1)+(rs[2*(i-1)+1]^0);
if (p1>p2)
{
point[i][3].last_point=3;
point[i][3].weight=p2;
point[i-1][3].over=1;
}
else
{
point[i][3].last_point=1;
point[i][3].weight=p1;
point[i-1][1].over=1;
}
}//t=3,4,5,6……
}
unsigned path[(length/2)+1]={0}; //記錄狀態轉移路徑
unsigned result[length/2]={0}; //記錄解碼信息位輸出
unsigned last; //最近的狀態，遞推回去的變量；
//判斷最后一個節點的總重量最低者，作為譯碼的最后一個狀態；作為遞推回去的出發點；
last=point[length/2][0].weight;
path[length/2]=0;
for(i=1;i<=3;i++)
{
if(point[length/2][i].weight<last)
{
last=point[length/2][i].weight;
path[length/2]=i;
}
}
//遞推回到出發點，最佳路徑的每個節點狀態；
for(i=(length/2)-1;i>=0;i--)
{
last=point[i+1][path[i+1]].last_point;
path[i]=last;
}
//根據每個點的最佳狀態，推出其輸入碼位，主要根據狀態轉移圖判斷；
for (i=1;i<=length/2;i++)
{
if ((path[i]==0) || (path[i]==2))
result[i-1]=0;
else if ((path[i]==1) || (path[i]==3))
result[i-1]=1;
}
for(i=0;i<=(length/2)-1;i++)
ds[i]=result[i]; //結果作為譯碼輸出；
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -