main.cpp

编码、通信中移位寄存器综合

/*****************线性序列寄存器综合内核函数************************/
/**************北京邮电大学信息安全中心***************/
/*****李武军([e-mail],hotmail.com;QQ11604612)***/
/*算法基本原理：
	参考资料：代数和编码（修订版），万哲先编或讲课笔记
表示方法：对于多项式fx，只保存其系数cn于p_cn,保存序列a于sequence中
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
#include<math.h>
char sequence[]="00100011101";
				//"000100110101111";
int n,dn,N,ln,m;
int *p_cn,*p_cm;
int Getdn(int n);
void FindMinNumRegister();
void PrintRegisterFunc();
void main()
{
	int i;
	N=strlen(sequence);
	ln=0;
	p_cm=new int[N+1];
	p_cn=new int[N+1];
	p_cn[0]=p_cm[0]=1;
	for(i=1;i<=N;i++)
		p_cn[i]=p_cm[i]=0;
	printf("a=%s\n",sequence);
	printf("n\tdn-1\tln\tfn(x)\n");
	FindMinNumRegister();
	//PrintRegisterFunc();

	delete []p_cn,p_cm;
}
void FindMinNumRegister()
{
	int i,temp;
	int *p_c_temp=new int[N+1];
	p_c_temp[0]=1;
	for(i=1;i<=N;i++)
		p_c_temp[i]=0;
	for(n=0,m=-1;n<N;n++,PrintRegisterFunc())
	{
		if(!(dn=Getdn(n)))//dn=0
			continue;
		else//dn!=0
		{	
			temp=__max(ln,n+1-ln);
			if(ln!=temp)//ln与当前的最大ln不等，应该保存作为lm
				memcpy(p_c_temp,p_cn,(n+1)*sizeof(int));//先暂存原来的fn
			if(m==-1)//第一次，即m等于初始值
				p_cn[n+1]=1;//fn+1=1+x^(n+1)
			else
			{
				for(i=n-m;i<=n;i++)
					p_cn[i]=p_cn[i]^p_cm[i-(n-m)];//fn+1=fn+（fm右移n-m)
			}
			if(ln!=temp)
			{
				ln=temp;//保存出当前的寄存器长度
				m=n;	//得到当前的最小的n作为lm中的m
				memcpy(p_cm,p_c_temp,(n+1)*sizeof(int));//保存fm
			}
		}
		
	}

}
int Getdn(int n)
{
	int i, result=0;
	for(i=0;i<=ln;i++)
		if(p_cn[i])
			result^=sequence[n-i]&1;
	return result;
}
void PrintRegisterFunc()
{
	char buffer[1024]="";
	char buff_num[10];
	_itoa(n,buff_num,10);
	printf("%s\t",buff_num);
	_itoa(dn,buff_num,10);
	printf("%s\t",buff_num);
	_itoa(ln,buff_num,10);
	printf("%s\t",buff_num);
	for(int i=0;i<=ln;i++)
	{
		if(p_cn[i])
			sprintf(&buffer[strlen(buffer)],"x^%d+",i);
	}
	if(buffer[2]=='0')//将x^0替换为1
	{
		buffer[2]='1';
		strcpy(buffer,&buffer[2]);
	}
	if(buffer[strlen(buffer)-1]=='+')// 去掉最后一个+;
		buffer[strlen(buffer)-1]='\0';	
	printf("%s\n",buffer);
}