bma.cpp

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

#include <stdafx.h>
#include <stdlib.h>
#include <crtdbg.h>

#include "BMA.h"

//BM迭代算法,用伴随式求错误位置多项式
int BMIteration(GFE* d, const GFE* s, BMARegs& bm) {
	Using_Pow2Vec_Vec2Pow_NG(bm.gf);
	GFE* b=bm.B;
	int t_RS=bm.t, N_RS=bm.N, D_RS=bm.D;

    int L=0, l=0, j, k;
	GFE discrep; //每次迭代步的差值
	for (int i=1; i<=2*t_RS; i++) {d[i]=0;}
	d[0]=1;
    for (i=1; i<=2*t_RS; i++) {b[i]=0;}
	b[0]=1;

	for (int r=0; r<2*t_RS; r++) {
        discrep=0;
		l++;
		for (j=0; j<=L; j++) {
			discrep^= GFMPY_V2V(d[j] , s[r-j], NG);
		    _ASSERT((j<=2*t_RS) && (r-j+1>=0) && (r-j+1<=D_RS-1));//调试时检查指针越界之用
		}
        if (discrep!=0) {
			for (k=l; k<=2*t_RS; k++) {
				d[k]^=GFMPY_V2V(b[k-l] , discrep, NG);
                _ASSERT((k<=2*t_RS) && (k-l>=0) && (k-l<=2*t_RS));
			}
			if (2*L<=r) {
				//for (int k=0; k<=t_RS; k++) b[k]=GFDIV_V2V(d[k] , discrep);
				for (k=2*t_RS; k>=0; k--) {
					b[k]=GFDIV_V2V(d[k] , discrep, NG);
					if (k>=l) {
						b[k]^=b[k-l];
					    _ASSERT(k-l<=2*t_RS);
					}
				}
				//_ASSERT((r<2*t_RS-1 && r+1-L==L+1) || r==2*t_RS-1);
				L=r+1-L;
				l=0;
			}
		}
	}

#ifdef _LOGOUT
	fputc(1, bm.fLog);
	for (j=0; j<2*t_RS; j++) fputc((byte)s[j], bm.fLog);
	for (j=1; j<=2*t_RS; j++) fputc((byte)d[j], bm.fLog);
#endif
	for (j=2*t_RS; j>=0; j--) {if (d[j]!=0) break;}
	_ASSERT(j>-1);
	if (j==L && j<=t_RS) return L; else return -1;//-1表示发生了不可纠(多于t个)的错误
}

//钱-搜索算法,求错误位置多项式的根		
bool ChienSearch(int* errloc, GFE* d, int errcnt, const BMARegs& bm) {
	Using_Pow2Vec_Vec2Pow_NG(bm.gf);
	int N_RS=bm.N,  t_RS=bm.t;
    GFE errsum;
	int rootexp, ierr;
    ierr=0;
	for (int l=0; l<N_RS; l++) {
		errsum=0;
		rootexp=l;
		for (int k=1; k<=errcnt; k++) {
            if (d[k]!=0) errsum^=Pow2Vec[MODQ(rootexp+Vec2Pow[d[k]] , NG)];
			_ASSERT(k>=0 && k<=2*t_RS);
			rootexp+=l;
		}
		if (errsum==1) {
			errloc[ierr++]=((l==0)? 0 : N_RS-l);
			_ASSERT(ierr-1<t_RS);
		}
	}
#ifdef _LOGOUT
	fputc(2, bm.fLog);
	for (int j=0; j<2*t_RS; j++) fputc((byte)d[j], bm.fLog);
	fputc((byte)errcnt, bm.fLog);
	fputc((byte)ierr, bm.fLog);
	for (j=0; j<ierr; j++) fputc((byte)errloc[j], bm.fLog);
#endif
	if (ierr!=errcnt) return false; else return true;
	//根的数量不等于错误位置多项式的次数,表明译码失败
}

//计算收到的码字的伴随式
void SyndromCompute(GFE* s, const GFE* r, const BMARegs& bm) {
	Using_Pow2Vec_Vec2Pow_NG(bm.gf);
	int m0_RS=bm.m0, t_RS=bm.t, D_RS=bm.D, N_RS=bm.N;
    int rootexp, j;
	for (int i=m0_RS; i<2*t_RS+m0_RS; i++) {
        s[i-m0_RS]=0;
		_ASSERT((i-m0_RS+1>=0) && (i-m0_RS+1<D_RS));
		rootexp=0;
		for (j=0; j<N_RS; j++) {
            if (r[N_RS-1-j]!=0) {
				s[i-m0_RS]^=Pow2Vec[MODQ(rootexp+Vec2Pow[r[N_RS-1-j]] , NG)];
                _ASSERT(N_RS-1-j>=0 && N_RS-1-j<N_RS);
			}
			rootexp+=i;
		}
	}
#ifdef _LOGOUT
	fputc(0, bm.fLog);
	for (i=0; i<N_RS; i++) fputc((byte)r[i], bm.fLog);
	for (i=0; i<2*t_RS; i++) fputc((byte)s[i], bm.fLog);
#endif
}

//Forney算法计算错误值
void ErrEvaluate(GFE* errvalue, Polynom* d, const Polynom* s,
				 const int* errloc, int errcnt, BMARegs& bm) {
	Using_Pow2Vec_Vec2Pow_NG(bm.gf);
	GFE* SR=bm.SR;
	Polynom* w=&bm.w;
	int t_RS=bm.t, m0_RS=bm.m0;

	d->D=errcnt;
	PolyMPY(w, s, d, SR);
	GFE md, mn;
	int lexp, k;
	for (int i=0; i<errcnt; i++) {
        lexp=0;
		md=0;
		for (k=0; k<2*t_RS; k++) {
            if (w->coef[k]!=0) md^=Pow2Vec[MODQ(Vec2Pow[w->coef[k]]-lexp , NG)];
            lexp+=errloc[i];
		}
		lexp=0;
		mn=0;
		for (k=1; k<=errcnt; k+=2) {
            if (d->coef[k]!=0) mn^=Pow2Vec[MODQ(Vec2Pow[d->coef[k]]-lexp , NG)];
            lexp+= (2*errloc[i]);
		}
		errvalue[i]= (md==0)? 0 : Pow2Vec[MODQ(Vec2Pow[md]-Vec2Pow[mn]+(2-m0_RS)*errloc[i] , NG)];
	}
#ifdef _LOGOUT
	//NOT DONE
	fputc(3, bm.fLog);
	fputc((byte)errcnt, bm.fLog);
	for (int j=1; j<=2*t_RS; j++) fputc((byte)d->coef[j], bm.fLog);
	for (j=1; j<=2*t_RS; j++) fputc((byte)s->coef[j], bm.fLog);
	for (j=1; j<=2*t_RS; j++) fputc((byte)w->coef[j], bm.fLog);
	for (j=0; j<errcnt; j++) fputc((byte)errloc[j], bm.fLog);
	for (j=0; j<errcnt; j++) fputc((byte)errvalue[j], bm.fLog);
#endif
}

/*
struct DecAlgInterface {
	void* DecAlgRegs;
	CloseAlgFunc CloseDecAlg;
	HDecFunc DecodeOneWord_Hard;
	SDecFunc DecodeOneWord_Soft;
	bool isHardDecoder;
	int AlgStructSize;
};
*/

DecAlgInterface InitBMA(const RSCodeParam& rsp) {
	BMARegs& bm=*((BMARegs*)malloc(sizeof(BMARegs)));
	bm.m0=rsp.m0;
	bm.N=rsp.N;
	bm.K=rsp.K;
	bm.t=rsp.t;
	bm.D=rsp.D;
	bm.gf=rsp.gf;

	//BM迭代法用到的各寄存器初始化
    InitPolynom(&bm.S, bm.gf, bm.D-1);
//	bm.S.D=2*bm.t-1;
	bm.S.coef[0]=1;
    InitPolynom(&bm.delta, bm.gf, 2*bm.t);
    bm.B=(GFE*)malloc(sizeof(GFE)*(2*bm.t+1));
    bm.Y=(GFE*)malloc(sizeof(GFE)*bm.t);
    bm.lx=(int*)malloc(sizeof(int)*bm.t);
    bm.SR=(GFE*)malloc(sizeof(GFE)*bm.t);
    InitPolynom(&bm.w, bm.gf, 3*bm.t);

	DecAlgInterface decalg;
	decalg.AlgStructSize=sizeof(BMARegs);
	decalg.CloseDecAlg=CloseBMA;
	decalg.DecAlgRegs=&bm;
	decalg.DecodeOneWord_Hard=DecodeOneWord_BMA;
	decalg.DecodeOneWord_Soft=NULL;
	decalg.isHardDecoder=true;
#ifdef _LOGOUT
	bm.fLog=fopen("BMALog.dat", "wb");
	fputc((byte)bm.m0, bm.fLog);
	fputc((byte)bm.N, bm.fLog);
	fputc((byte)bm.K, bm.fLog);
	fputc((byte)bm.D, bm.fLog);
	fputc((byte)bm.t, bm.fLog);
#endif
	return decalg;
}

void CloseBMA(void* A) {
	BMARegs& bm=*((BMARegs*)A);
	FreePolynom(&bm.S);
	FreePolynom(&bm.delta);
	FreePolynom(&bm.w);
	free(bm.B);
	free(bm.Y);
	free(bm.lx);
	free(bm.SR);
#ifdef _LOGOUT
	fclose(bm.fLog);
#endif
}

/*译解一个码字*/
bool DecodeOneWord_BMA(GFE* c, const GFE* r,  const RSCodeParam& rsp, void* A) {
	BMARegs& bm=*((BMARegs*)A);
	for (int i=0; i<bm.N; i++) c[i]=r[i];
    SyndromCompute(&bm.S.coef[1], r, bm);
	int errcount=BMIteration(bm.delta.coef, &bm.S.coef[1], bm);
	if (errcount==-1) return false;//发生了多于t个错误
	if (!ChienSearch(bm.lx, bm.delta.coef, errcount, bm)) return false;//译码失败
	ErrEvaluate(bm.Y, &bm.delta, &bm.S, bm.lx, errcount, bm);
	for (i=0; i<errcount; i++) {
		c[bm.N-1-bm.lx[i]]^=bm.Y[i];
		_ASSERT(bm.lx[i]>=0 && bm.lx[i]<bm.N);
	}
	return true;
}