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);
}