gf.cpp

包括RS码的编码,硬(BM)/软(KV)译码,AWGN信道调制解调仿真. 具体采用何种编译码方案和调制解调方式可在Profile.txt文件中指定(内有详细说明). 且扩展性极好,容易向其中加入新的调

#include <stdafx.h>
#include <stdlib.h>
#include "GF.h"

/*返回一个GF(2^m)元素的m数*/
int GFEDeg(GFE p) {
	if (p==0) return -1;
	GFE t=p;
	for (int i=0; (t>>=1)!=0; i++);
	return i;
}

/*GF(2^m)中的组合数计算*/
GFE CombMod2(GFE n1, GFE n2) {
	if ((n1 & n2)==n2) {
		return 1;
	}
	else {
		return 0;
	}
}

/*生成Galoias Field*/
void InitGF(GF* gf, int m) {
    gf->M=m;
	gf->N=1;
	GFE mask=1;
	int deg=GFEDeg(primepolynom[m]);
	for (int i=0; i<deg; i++, gf->N*=2, mask<<=1);
	gf->N--;

    gf->Vec2Pow=(int*)malloc(sizeof(int)*(gf->N+1));
	gf->Pow2Vec=(GFE*)malloc(sizeof(GFE)*(gf->N+1));
    GFE p=1;
	for (i=0; i<gf->N; i++) {
        gf->Pow2Vec[i]=p;
        gf->Vec2Pow[p]=i;
        if (((p<<=1) & mask)!=0) p^=primepolynom[m];
	}
    //gf->Vec2Pow[0]=gf->N;
	gf->Vec2Pow[0]=-1;
	gf->Pow2Vec[gf->N]=0;
}

GF NewGF(int m) {
    GF g;
	InitGF(&g, m);
	return g;
}

void FreeGF(GF* g) {
	free(g->Pow2Vec);
	free(g->Vec2Pow);
	free(g);
}

/*
static int* Vec2Pow;
static Polynom* Pow2Vec;
int NG;

void genGF(int m) {
    NG=1;
	Polynom mask=1;
	int deg=PolynomDeg(primepolynom[m]);
	for (int i=0; i<deg; i++, NG*=2, mask<<=1);
	NG--;

    Vec2Pow=(int*)malloc(sizeof(int)*NG);
	Pow2Vec=(Polynom*)malloc(sizeof(Polynom)*NG);
    Polynom p=1;
	for (i=0; i<NG; i++) {
        Pow2Vec[i]=p;
		Vec2Pow[p]=i;
		//p=PolynomMOD(PolynomMPY(p,alpha),primpoly);
        if (((p<<=1) & mask)!=0) p^=primepolynom[m];
	}
	Vec2Pow[0]=-1;
}

//以GF元素为系数的多项式之乘除法(系数以本原元素幂次表示)
int GFPolyMPY(const int* a,int k, const int* b,int r, int** m) {
	//Big Endian, 低次项之下标在后
    //注意:k,r分别是多项式a,b的阶数,即其系数数组长度-1!
	//以GF中元素为系数的多项式相乘,系数数组中存放的是alpha之幂次
	//0元素以幂次-1表示(ONLY IN THIS FUNCTION)
	int* SR=(int*)malloc(sizeof(int)*r);
	int i,j;
	for (i=0; i<r; i++) SR[i]=-1;
	int* c=(int*)malloc(sizeof(int)*(k+r+1));
    
	for (i=0; i<k+r+1; i++) {
	     c[i]=-1;
		 for (j=r; j>0; j--) {
			 if (b[j]>=0 && SR[j-1]>=0) {
				 if (c[i]>=0) c[i]=GFADD_P2P(c[i],MODQ(b[j]+SR[j-1],NG));
				 else c[i]=MODQ(b[j]+SR[j-1],NG);
			 }
		 }
		 for (j=r-1; j>0; j--) SR[j]=SR[j-1];
		 if (i<k+1) {
			SR[0]=a[i];
			if (b[0]>=0 && a[i]>=0) {
				if (c[i]>=0) c[i]=GFADD_P2P(c[i],MODQ(b[0]+a[i],NG));
                else c[i]=MODQ(b[0]+a[i],NG);
			}
		 } else if (i==k+1) SR[0]=-1;
	}
	*m=c;
	free(SR);
	return k+r;
}

int GFPolyMOD(const int* a,int k, const int* b,int r, int** rx) {
	for (int i=0; b[i]==-1 && i<r+2; i++);
	int r0=r-i;  if (r0<0) return -1;//表示除式为零
    int* SR=(int*)malloc(sizeof(int)*r0);
    int q;
    for (i=0; i<r0; i++) SR[i]=a[i];
	for (i=0; i<k-r0+1; i++) {
		q=(SR[0]<0)? -1 : MODQ(SR[0]-b[r-r0],NG);
		for (int j=0; j<r0-1; j++) {
			if (b[r-r0+1+j]<0 || q<0) SR[j]=SR[j+1];
			else if (SR[j+1]<0) SR[j]=MODQ(b[r-r0+1+j]+q,NG);
			else SR[j]=GFADD_P2P(SR[j+1],MODQ(b[r-r0+1+j]+q,NG));
		}
		if (b[r]<0 || q<0) SR[r0-1]=a[r0+i];
		else if (a[r0+i]<0) SR[r0-1]=MODQ(b[r]+q,NG);
		else SR[r0-1]=GFADD_P2P(a[r0+i],MODQ(b[r]+q,NG));
    }
    *rx=SR;
	return k-r0;//返回商式之次数
}

int GFPolyDIV(const int* a,int k, const int* b,int r, int** qx) {
	for (int i=0; b[i]==-1 && i<r+2; i++);
	int r0=r-i;  if (r0<0) return -1;//表示除式为零
    int* SR=(int*)malloc(sizeof(int)*r0);
    int* q=(int*)malloc(sizeof(int)*(k-r0+1));
    for (i=0; i<r0; i++) SR[i]=a[i];
	for (i=0; i<k-r0+1; i++) {
		q[i]=(SR[0]<0)? -1 : MODQ(SR[0]-b[r-r0],NG);
		for (int j=0; j<r0-1; j++) {
			if (b[r-r0+1+j]<0 || q[i]<0) SR[j]=SR[j+1];
			else if (SR[j+1]<0) SR[j]=MODQ(b[r-r0+1+j]+q[i],NG);
			else SR[j]=GFADD_P2P(SR[j+1],MODQ(b[r-r0+1+j]+q[i],NG));
		}
		if (b[r]<0 || q[i]<0) SR[r0-1]=a[r0+i];
		else if (a[r0+i]<0) SR[r0-1]=MODQ(b[r]+q[i],NG);
		else SR[r0-1]=GFADD_P2P(a[r0+i],MODQ(b[r]+q[i],NG));
    }
    *qx=q;
	free(SR);
	return k-r0;//返回商式之次数
}

/*以GF元素为系数的多项式之乘法(系数以矢量形式表示):移存器与积式数组由调用者提供的版本
调用者需保证移存器SR[0..r-1]与积式m[0..k+r]已分配好
*/
/*
int GFPolyMPY(const Polynom* a,int k, const Polynom* b,int r, Polynom* SR, Polynom* m) {
	//Big Endian, 低次项之下标在后
    //注意:k,r分别是多项式a,b的阶数,即其系数数组长度-1!
	//以GF中元素为系数的多项式相乘,系数数组中存放的是其m重表示
	int i,j;
	for (i=0; i<r; i++) SR[i]=0;
	
	for (i=0; i<k+r+1; i++) {
	     m[i]=0;
		 for (j=r; j>0; j--) m[i]^=GFMPY_V2V(b[j], SR[j-1]);
		 for (j=r-1; j>0; j--) SR[j]=SR[j-1];
		 if (i<k+1) {
			SR[0]=a[i];
			m[i]^=GFMPY_V2V(b[0],a[i]);
		 } else if (i==k+1) SR[0]=0;
	}
	return k+r;
}

/*以GF元素为系数的多项式之乘法(系数以矢量形式表示):移存器与积式数组在局部临时分配的版本
因而适用于调用次数不多的场合
*/
/*
int GFPolyMPY(const Polynom* a,int k, const Polynom* b,int r, Polynom** m) {
	//Big Endian, 低次项之下标在后
    //注意:k,r分别是多项式a,b的阶数,即其系数数组长度-1!
	//以GF中元素为系数的多项式相乘,系数数组中存放的是其m重表示
	Polynom* SR=(Polynom*)malloc(sizeof(Polynom)*r);
	Polynom* c=(Polynom*)malloc(sizeof(Polynom)*(k+r+1));    
	GFPolyMPY(a,k, b,r, SR,c);
	*m=c;
	free(SR);
	return k+r;
}

int GFPolyMOD(const Polynom* a,int k, const Polynom* b,int r, Polynom** rx) {
	for (int i=0; b[i]==0 && i<r+2; i++);
	int r0=r-i;  if (r0<0) return -1;//表示除式为零
    Polynom* SR=(Polynom*)malloc(sizeof(Polynom)*r0);
    Polynom q;
    for (i=0; i<r0; i++) SR[i]=a[i];
	for (i=0; i<k-r0+1; i++) {
		q=GFDIV_V2V(SR[0],b[r-r0]);
		for (int j=0; j<r0-1; j++) SR[j]=SR[j+1]^GFMPY_V2V(b[r-r0+1+j],q);
		SR[r0-1]=a[r0+i]^GFMPY_V2V(b[r],q);
    }
    *rx=SR;
	return k-r0;//返回商式之次数
}

int GFPolyDIV(const Polynom* a,int k, const Polynom* b,int r, Polynom** qx) {
	for (int i=0; b[i]==0 && i<r+2; i++);
	int r0=r-i;  if (r0<0) return -1;//表示除式为零
    Polynom* SR=(Polynom*)malloc(sizeof(Polynom)*r0);
    Polynom* q=(Polynom*)malloc(sizeof(Polynom)*(k-r0+1));
    for (i=0; i<r0; i++) SR[i]=a[i];
	for (i=0; i<k-r0+1; i++) {
		q[i]=GFDIV_V2V(SR[0],b[r-r0]);
		for (int j=0; j<r0-1; j++) SR[j]=SR[j+1]^GFMPY_V2V(b[r-r0+1+j],q[i]);
		SR[r0-1]=a[r0+i]^GFMPY_V2V(b[r],q[i]);
    }
    *qx=q;
	free(SR);
	return k-r0;//返回商式之次数
}
*/