|
BCH_RS编码
一、内容二、功能模块三、结果展示1 手动测试2 自动测试
四、C++实现五、结果分析1 对比相同码长不同纠错能力时的误码率。2、对比相同纠错能力不同码长的误码率3、对比RS码和BCH码的误码率
六、完整代码
一、内容
1、BCH码编码 2、BCH码译码 3、RS码编码 4、RS码译码 5、手动测试 6、自动测试
二、功能模块
实现了码长可变、纠错能力可变、BSC信道、BCH译码用快速迭代译码、钱搜索算法寻找错误位置、RS译码用迭代译码、钱搜索算法、福尼算法实现。 1、构造多项式到向量及向量到多项式的对照表 2、生成极小多项式 3、求多项式的次数模块 4、多项式加法 5、向量乘法 6、多项式乘法 7、求BCH码生成多项式 8、求RS码生成多项式 9、BCH码、RS码编码 10、求f(x)，代表已知多项式求f(x),x为向量 11、BCH迭代译码、钱搜索算法 12、RS迭代译码、钱搜索算法、福尼算法 13、手动测试 14、自动测试 15、BSC信道
三、结果展示
1 手动测试
  
2 自动测试
  
四、C++实现
本实验是基于Dev C++环境进行的。由于功能模块的数量太多，在实验报告中展示会显得杂乱繁琐，故只在实验报告中简述C语言编程的实现思想，详见提交的实验源码。 用一个int数组来存储本原多项式表，每个本原多项式用int型数表示；用一个int数组表示多项式，如果是BCH里面存储的是0或1，RS码存储的是多进制数的向量形式；生成两个表格分别为向量到方幂以及方幂到向量表；迭代译码的过程中每一步的结果用一个结构体来存储，所有的迭代步骤就构成了一个结构体数组。BSC信道是用一个与编码发送比特流相同的数组实现的，错误设为1，不错设为0，再与发送比特流进行异或运算得到接收比特流。 1、求极小多项式模块 使用共轭根系法求极小多项式，得到一个数组为对每一个GF（2m）的向量存存储着其共轭根系。 2、多项式乘法模块，输入两个表示多项式的数组，输出相乘后的数组，相乘时每个向量依次相乘在根据次数移位。 3、BCH码生成多项式模块，由输入的t确定出一组向量，在找到每个向量的共轭根系，求各个共轭根系的并集，在依次乘以一次多项式得到生成多项式。 4、编码模块，信息多项式同样用一个数组表示作为输入，生成多项式数组也作为输入，根据v(x)=〖x^r m(x) +(x^r m(x))〗_g(x) 得到编码后的多项式数组。具体就是移位和进行异或运算。 5、译码模块，用迭代译码算法，RS和BCH的译码分别写了一个模块，迭代译码的过程中每一步的结果用一个结构体来存储，所有的迭代步骤就构成了一个结构体数组，同时为了提高效率加入了快速译码、钱搜索算法和福尼算法。 6、BSC信道，BSC信道是用一个与编码发送比特流相同的数组实现的，错误设为1，不错设为0，其中1以信道转移概率出现，再与发送比特流进行异或运算得到接收比特流。
五、结果分析
1 对比相同码长不同纠错能力时的误码率。
可以看出，当相同码长时纠错能力增大，误码率减小，原因是冗余位增加，但码率减小。
2、对比相同纠错能力不同码长的误码率
可以看出，相同纠错能力下，码长越长冗余位越多，误码率越小。 
3、对比RS码和BCH码的误码率
由于RS码是纠突发错误的纠错码，BCH码纠随机错误，而BSC信道是随错误信道，故RS码的误码率比BCH码高。
六、完整代码
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
# include
using namespace std;
const int N=10000;//设计的最长码长
struct die{//迭代过程表
int u;
int deta[N];
int D;
int u_d;//u-D
int du;
};
vector a_v,v_a;
void excel(int n, vector &a_v, vector &v_a){
//int n;//码长
//vector a_v;//多项式到向量
//vector v_a;//向量到多项式
int m=int(log(double(n+1))/log(2.0));
int benyuan[26]={0};
//============本原多项式表===============//
benyuan[ 2]=1 + (1false};
int first_no=0;//是否迭代完
while(first_no
if((first_no*(1
if(!hash[i]){
first_no=i;
break;
}
}
}
}
int alpha(int* g){
//===============求多项式g的次数===========
int sum=accumulate(g,g+N,0);
int n=0;
int temp;
while(true){
temp=accumulate(g,g+n+1,0);
if(temp==sum) break;
n++;
}
return n;
}
int max_two(int a,int b){
//===============求两数最大值================
if(a>b) return a;
else return b;
}
void sum(int* a,int* b,int* out){
//================码多项式加法===================
//a,b输入码字,存储向量表示
//out 输出码字
fill(out,out+N,0);
for(int i=0;i
//===================向量乘法=====================
// int a,int b,输入两向量
// int n;输入码长
//输出out向量表示
int m=int(log(double(n+1))/log(2.0));
if(a==0 || b==0) return 0;
int out;
out=a_v[(v_a[a]+v_a[b])%((1
fill(temp,temp+N,0);
for(int j=0;j
//===============求BCH生成多项式==================
//输入：n,t;
//输出：g
fill(g,g+N,0);
int m=int(log(double(n+1))/log(2.0));
g[0]=1;//生成多项式
set s;//方幂集合
vector mina;//极小多项式
min_a(n,mina);
for(int i=1;i
s.insert(mina[i][j]);
}
}
set:: iterator it=s.begin();
int temp[N];
int tq[N];
for(it=s.begin();it!=s.end();it++){
fill(temp,temp+N,0);
temp[1]=1;
temp[0]=a_v[*it];
memcpy(tq,g,4*N);
mul(tq,temp,n,g);
}
}
void rs_born(int n,int t,int* g){
//================RS码生成多项式===============
fill(g,g+N,0);
g[0]=1;
int temp[N]={0};
int tq[N];
for(int i=1;i
//=================编码===================
//int n,码长，输入
//words m,信息位,输入
//words g;生成多项式，输入
fill(v,v+N,0);
int q=int(log(double(n+1))/log(2.0));
int r=alpha(g);
int k=n-r;//信息元个数
int low[N]={0};
int high[N]={0};
for(int i=alpha(m);i>=0;i--) high[r+i]=m[i];
memcpy(low,high,4*N);
int cha;
int move[N];
int tg[N];
int tlow[N];
while(alpha(low)>=r){
cha=alpha(low)-r;
fill(move,move+N,0);
fill(tg,tg+N,0);
fill(tlow,tlow+N,0);
move[cha]=low[alpha(low)];
mul(g,move,n,tg);
sum(low,tg,tlow);
memcpy(low,tlow,4*N);
}
sum(high,low,v);
}
int f_x(int* f,int n,int x){
//================求f(x)===============
//f 函数，输入
//x 向量，输入
//n 码长，输入
//out 向量，输出
int out;
out=f[0];
if(!x) return out;
int m=int(log(double(n+1))/log(2.0));
int e=alpha(f);
int temp;
for(int i=1;i
//================BCH译码======================
//int r[N]={0};//接收码字，输入
//int n=15;//码长，输入
//int t=3;//纠错能力，输入
//int g[N];//生成多项式,输入
//int m[N]，信息多项式，输出
int qm=int(log(double(n+1))/log(2.0));
int R=alpha(g);//生成多项式次数
int K=n-R;//信息元个数
fill(m,m+N,0);
for(int i=0;i
int temp=s[i/2-1];
if(temp){
temp=(v_a[temp]*2)%((10};//中间变量
int tdeta[N];
int ttdeta[N];
int rho=0;//记录ρ;
int td;
//==================判断是否只有一位错==============
bool judge=true;
int div=(v_a[s[1]]-v_a[s[0]]+((1judge=false;break;}
}
//====================只有一位错时==================
if(judge){
div=(v_a[s[1]]-v_a[s[0]]+((1
if(tq.u%2){
//========u是奇数=========
tq.du=0;
Q.push_back(tq);
lq=tq;//*****************************************************************
tq.u=tq.u+1;
tq.u_d=tq.u_d+1;
tq.du=0;
}
else{
//=========偶数时==========
for(int i=0;i
if(Q[i].du!=0 && Q[i].u_d>Q[rho].u_d)
rho=i;
}
td=a_v[(((1
money[j]=money[j]+(money[j]>0)*j;
}
flag=0;
for(int k=0;k
//================RS译码======================
//int r[N]={0};//接收码字，输入
//int n=15;//码长，输入
//int t=3;//纠错能力，输入
//int g[N];//生成多项式,输入
//int m[N],信息多项式，输出
int qm=int(log(double(n+1))/log(2.0));
int R=alpha(g);//生成多项式次数
int K=n-R;//信息元个数
fill(m,m+N,0);
for(int i=0;i0};//中间变量
int tdeta[N];
int ttdeta[N];
int rho=0;//记录ρ;
int td;
memset(&tq,0,sizeof(struct die));
tq.u=-1;tq.deta[0]=1;tq.D=0;tq.u_d=-1;tq.du=1;
Q.push_back(tq);
memset(&tq,0,sizeof(struct die));
tq.u=0;tq.deta[0]=1;tq.D=0;tq.u_d=0;tq.du=s[0];
Q.push_back(tq);
tq.u=tq.u+1;
tq.deta[1]=tq.du;
tq.D=alpha(tq.deta);
tq.u_d=tq.u-tq.D;
tq.du=0;
while(true){
for(int i=0;i
if(Q[i].du!=0 && Q[i].u_d>Q[rho].u_d)
rho=i;
}
td=a_v[(((1
money[j]=money[j]+(money[j]>0)*j;
}
flag=0;
for(int k=0;k
error.push_back((10};
for(int i=0;i0};
for(int i=1;i0};//错误多项式
int ty;
for(int i=0;i0};//译码多项式
sum(ex,r,v);
for(int i=0;i0};//信息多多项式
int dem[N]={0};//解码恢复信息多项式
int v[N]={0};//编码码字
int g[N]={0};//生成多项式
int r[N]={0};
coutkind;
if(!kind){//BCH码
//cout
//==============自动测试======================
//输入：
//length 随机生成的比特流长度
//p 信道转移概率
//type 编码方式BCH[0] or RS[1]
//n 码长
//t 纠错能力
// 输出 re 误码率
double re=0;
srand(time(NULL));//随机数种子时变
int m=int(log(double(n+1))/log(2.0));
int K;
int v[N]={0};//编码多项式
int g[N]={0};//生成多项式
int r[N]={0};//接收多项式
int mx[N]={0};//信息多项式
int demx[N]={0};//接收恢复多项式
vector b;//随机生成比特流
vector vb;//编码后比特/数据流
vector eb;//错误比特/数据流
vector rb;//接收比特/数据流
vector deb;//接收译码后数据流
int temp_p1=int(p*10000);//1的个数
int temp_p0=10000-temp_p1;//0的个数
vector lp;//生成转移概率
while(temp_p1--){lp.push_back(1);}
while(temp_p0--){lp.push_back(0);}
if(!type) {
//-----------------BCH码---------------------
bch_born(n,t,g);
int R=alpha(g);//生成多项式次数
K=n-R;
if(length%K!=0){
length=length+K-length%K;
}
int len=length;
while(length--) b.push_back(rand()%2);//生成比特流
length=len;//末尾补齐后长度
//================编码=======================
for(int i=0;i*K
//memcpy(r,&rb[0]+i*n,sizeof(int)*n);
for(int j=0;j
length=length+K*m-length%(K*m);
}
int len=length;
while(length--) b.push_back(rand()%2);//生成比特/数据流
length=len;//末尾补齐后长度
vector rsb;//RS码数据流
int temp=0;
for(int i=0;i*m
//memcpy(mx,&b[0]+i*K,sizeof(int)*K);
for(int j=0;j
//memcpy(r,&rb[0]+i*n,sizeof(int)*n);
for(int j=0;j
int a;
int length;//length长度
float p;//p转移概率
double bit_ratio;//自动测试误比特率
int type;//编码类型
int n;//码长
int t;//纠错能力
//=================生成数据文件====================
/*n=63;
excel(n,a_v,v_a);
vector plt;//画图数据
for(int i=0;i
fout
cout |