?? convcode.c
字號:
//程序：卷積碼編碼、維特比硬判譯碼器
//作者：Anfysky
//日期：2004-12
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <malloc.h>
#include <windows.h>
//extern("c");
//卷積碼參數結構體
typedef struct
{
int *G; //生成多項式
int **pStateTable; //狀態表
int nOutc; //輸出校驗位個數
int nDelayNum; //延時窗個數
}CONV_PARM;
//二維指針分配函數
void ** malloc2(int r, int l, int typesize)
{
int i=0;
void **p=(void **)malloc(r*typesize);
for(i=0; i<r; i++)
p[i]=(void *)malloc(l*typesize);
return p;
}
//二維指針釋放函數
void free2(void **p, int r, int l)
{
int i=0;
for(i=0; i<r; i++)
{
free(p[i]);
}
free(p);
}
//二維指針內存清零函數
void ** memset2(void **p, char c, int r, int l)
{
int i=0;
for(i=0; i<r; i++)
{
memset(p[i],c,l);
}
return p;
}
//產生隨機數
int randB_vec(double* pOut, int nOut)
{
int i=0;
printf("Source Generating ...");
for(i=0; i<nOut; i++)
{
*(pOut+i)=(rand()>(RAND_MAX/2));
}
printf(" Done\n");
return i;
}
//根據當前狀態和生成多項式，產生下一個狀態
static int Gen_C_Int(int nStates, int nWindow, int G)
{
int i=0;
int nAns=0;
int nAnd=nStates&G;
for(i=0; i<=nWindow; i++)
{
nAns+=nAnd%2;
nAnd>>=1;
}
return nAns%2;
}
//產生狀態轉移表
static double Gen_Conv_Table(CONV_PARM* conv_parm)
{
int nStateNumWI=1<<(conv_parm->nDelayNum+1);
int i=0;
int j=0;
int nOut=0;
for(i=0; i<nStateNumWI; i++)
{
//第一個數紀錄下一狀態
conv_parm->pStateTable[i][0]=i>>1;
//第二個數紀錄輸出
nOut=0;
for(j=0; j<conv_parm->nOutc; j++)
{
nOut<<=1;
nOut+=Gen_C_Int(i,conv_parm->nDelayNum,conv_parm->G[j]);
}
conv_parm->pStateTable[i][1]=nOut;
}
return 0;
}
//編碼器
int Conv_Encode(double *pSrc, int nSrcLen, double *pCoded, CONV_PARM conv_parm)
{
int nWindow=0;
int i=0,j=0;
printf("Conv Encoding ... ");
for(i=0; i<nSrcLen+conv_parm.nDelayNum; i++)
{
if(i<nSrcLen)
nWindow+=(int)(*(pSrc+i))<<conv_parm.nDelayNum;
for(j=0; j<conv_parm.nOutc; j++)
{
*(pCoded+i*conv_parm.nOutc+j)=Gen_C_Int(nWindow,conv_parm.nDelayNum,conv_parm.G[j]);
}
nWindow>>=1;
}
printf("Done\n");
return (nSrcLen+conv_parm.nDelayNum)*conv_parm.nOutc;
}
//比較低8位的不同數字位數
int Get_Distance_Char(int n1, int n2)
{
int nXor=n1^n2;
int ans=0;
int i=0;
for(i=0; i<8; i++)
{
ans+=nXor%2;
nXor>>=1;
}
return ans;
}
//譯碼器
int Conv_Decode(double* pCoded, int nCodedLen, double* pDecoded, CONV_PARM conv_parm)
{
int i=0, j=0;
int nDecodedCounter=0;
int nStateCounterWI=0;
int nStateCounter=0;
int nReceiveC=0;
int nDistance=0;
int nNextState=0;
int nStateNumWI=1<<(conv_parm.nDelayNum+1);
int nStateNum=1<<conv_parm.nDelayNum;
int nDecodedNum=(nCodedLen/conv_parm.nOutc)+conv_parm.nDelayNum*2;
int nRealDecodedNum=0;
int nMinDistanceState=0;
int nMinDistance=0;
int nNewDistance=0;
int nTempAddress=0;
//定義pDecodedPath[信源點數][狀態數×3]，每個點的每個狀態上記錄
//1、距離，2、輸入，3、來自的前一狀態
//經過比較之后選擇最短距離并放到每個點每個狀態的記錄頭部。
//由于8bit狀態已經是非常復雜的狀態機了，所以使用2字節存儲轉移狀態是合理的。
//所以可以這樣按位處理：第1個4字節為距離，第2個4字節的頭部1字節為輸入
//第2個4字節的低3字節為下一個最短路徑狀態。(顯然足夠了)
int** pDecodedPath=(int **)malloc2(nDecodedNum,nStateNum*2,sizeof(int));
//為了節省內存，定義pTempDecodedStates[狀態數×4]，
//存放生成的下一個狀態的兩個路徑。
int* pTempDecodedStates=(int *)malloc(nStateNum*4*sizeof(int));
printf("Conv Decoding .");
memset2(pDecodedPath,-1,nDecodedNum,nStateNum*2*sizeof(int));
//將第一個點的前6個值賦0。這里是循環的起點。
for(i=0; i<2; i++)
pDecodedPath[0][i]=0;
for(i=0; i<nCodedLen; i+=conv_parm.nOutc)
{
nReceiveC=0;
for(j=0; j<conv_parm.nOutc; j++)
{
nReceiveC<<=1;
nReceiveC+=(int)(pCoded[i+j]);
}
memset(pTempDecodedStates,-1,nStateNum*4*sizeof(int));
for(nStateCounterWI=0; nStateCounterWI<nStateNumWI; nStateCounterWI++)
{
nStateCounter=nStateCounterWI%nStateNum;
//如果當前狀態所處的位置上，誤差距離全是負數，就是不可到達當前狀態，
//則不做新的目標誤差距離的生成。
if(pDecodedPath[nDecodedCounter][nStateCounter*2]==-1)
{
continue;
}
else
{
nNextState=nStateCounterWI>>1;
//conv_parm.pStateTable[nStateCounterWI][1]是輸出
//比較接收與conv_parm.pStateTable[nStateCounterWI][1]，得到下一狀態上的距離。
nDistance=Get_Distance_Char(conv_parm.pStateTable[nStateCounterWI][1], nReceiveC);
//寫下一狀態的幾個值：距離，輸入，來自的狀態
//距離寫在2整數倍的位置上。
nNewDistance=pDecodedPath[nDecodedCounter][nStateCounter*2]+nDistance;
pTempDecodedStates[nNextState*4+2*(nStateCounterWI%2)]=nNewDistance;
//輸入和來自的狀態合并之后寫在2n+1的位置上。
pTempDecodedStates[nNextState*4+2*(nStateCounterWI%2)+1]=(nStateCounterWI/nStateNum)<<24;
//來自的狀態
pTempDecodedStates[nNextState*4+2*(nStateCounterWI%2)+1]+=nStateCounter;
}
//判斷最小距離，把最小距離點的參數覆蓋到最短路徑上。
if((pTempDecodedStates[nNextState*4+2]>=0) &&
(pTempDecodedStates[nNextState*4+2]<pTempDecodedStates[nNextState*4]))
{
pDecodedPath[nDecodedCounter+1][nNextState*2]=
pTempDecodedStates[nNextState*4+2];
pDecodedPath[nDecodedCounter+1][nNextState*2+1]=
pTempDecodedStates[nNextState*4+3];
}
else
{
pDecodedPath[nDecodedCounter+1][nNextState*2]=
pTempDecodedStates[nNextState*4];
pDecodedPath[nDecodedCounter+1][nNextState*2+1]=
pTempDecodedStates[nNextState*4+1];
}
}
nDecodedCounter++;
if(nDecodedCounter%20000==0)
printf(".");
}
nRealDecodedNum=nDecodedCounter;
//從最后一個點的狀態開始，選擇最小距離
nMinDistance=pDecodedPath[nDecodedCounter][0];
nMinDistanceState=0;
for(nStateCounter=0; nStateCounter<nStateNum; nStateCounter++)
{
nDistance=pDecodedPath[nDecodedCounter][nStateCounter*2];
if((nDistance>0) && (nMinDistance>nDistance))
{
nMinDistance=nDistance;
nMinDistanceState=nStateCounter;
}
}
//選出最小距離之后，根據路徑，倒推整個輸入
for(i=nRealDecodedNum; i>0; i--)
{
pDecoded[i-1]=(pDecodedPath[i][nMinDistanceState*2+1])>>24;
nMinDistanceState=pDecodedPath[i][nMinDistanceState*2+1]%0x1000000;
}
printf(" Done\n");
free2(pDecodedPath,nDecodedNum,nStateNum*2);
free(pTempDecodedStates);
return nRealDecodedNum;
}
//private
//本私有方法僅用于簡化main函數，不可被外部函數調用
static void Initate_Conv_Parm(CONV_PARM* conv_parm)
{
conv_parm[0].nOutc=2;
conv_parm[0].nDelayNum=8;
conv_parm[0].G=(int*)malloc(conv_parm[0].nOutc*sizeof(double));
conv_parm[0].pStateTable=(int**)malloc2(1<<(conv_parm[0].nDelayNum+1),3,sizeof(double));
conv_parm[0].G[0]=0561;
conv_parm[0].G[1]=0753;
Gen_Conv_Table(conv_parm);
conv_parm[1].nOutc=3;
conv_parm[1].nDelayNum=8;
conv_parm[1].G=(int*)malloc(conv_parm[1].nOutc*sizeof(double));
conv_parm[1].pStateTable=(int**)malloc2(1<<(conv_parm[1].nDelayNum+1),3,sizeof(double));
conv_parm[1].G[0]=0557;
conv_parm[1].G[1]=0663;
conv_parm[1].G[2]=0711;
Gen_Conv_Table(conv_parm+1);
}
void main()
{
int i=0;
int nSrc=15;
CONV_PARM conv_parm[2];
double *pSrc=NULL;
double *pOut=NULL;
double *pDecoded=NULL;
DWORD time=0;
int nOut=0;
int nDecoded=0;
int nBitError=0;
time=GetTickCount();
//內部私有方法:初始化卷積碼編碼器參數
Initate_Conv_Parm(conv_parm);
//目前使用的都是conv_parm[0];
pSrc=(double*)malloc(nSrc*sizeof(double));
pOut=(double*)malloc(((nSrc+20)*conv_parm[0].nOutc)*sizeof(double));
pDecoded=(double*)malloc((nSrc+20)*sizeof(double));
printf("Source Number:\t%d \n",nSrc);
//產生信源
randB_vec(pSrc,nSrc);
//卷積碼編碼
nOut=Conv_Encode(pSrc, nSrc, pOut, conv_parm[0]);
for (i=0; i<nSrc; i++)
{
printf("%d,%d,%d\n",(int)pSrc[i],(int)pOut[i*2+1],(int)pOut[i*2]);//輸出高位在前
}
//卷積碼硬判解碼
nDecoded=Conv_Decode(pOut, nOut, pDecoded, conv_parm[0]);
//錯誤檢查
for(i=0; i<nSrc; i++)
{
if((int)pSrc[i]!=(int)pDecoded[i])
nBitError++;
}
time=GetTickCount()-time;
printf("\nTime Used:\t%.3f s\nErrors:\t\t%d bits\n",time*0.001,nBitError);
free(pSrc);
free(pOut);
free(pDecoded);
free(conv_parm[0].G);
free(conv_parm[1].G);
free2(conv_parm[0].pStateTable,(1<<(conv_parm[0].nDelayNum+1)),3);
free2(conv_parm[1].pStateTable,(1<<(conv_parm[1].nDelayNum+1)),3);
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -