北斗卫星导航纠错码BCH(15,11)快速译码算法及实现结构 ①
2021-04-09江宝安
江 宝 安
(重庆邮电大学移通学院，重庆 401520 )
0 引言
北斗卫星导航系统(BDS)是中国独立自主研制的全球卫星导航系统，可在全球范围内全天候、全天时地提供各类高精度、高可靠定位、导航、授时服务，并具短报文通信能力。目前，我国正在实施北斗三号系统建设，2020年将完成30颗卫星发射组网，全面建成北斗三号系统。
对卫星导航接收机而言,导航电文的准确性至关重要，其含有的卫星导航基本信息直接决定了接收机的定位精度[1]。为了增强导航电文的准确性，北斗系统采用了循环码BCH(15,11)作为导航电文的前向纠错码[2]。因此，设计该BCH码的高效译码方案具有重要的意义。 BCH一般译码算法主要分为两类：硬判决译码算法[3]和软判决译码算法[4，5]。 硬判决译码算法具有简单、易于实现的优点，也是北斗系统接口控制文件中推荐的译码算法，但是其译码性能相对较差。软判决译码算法的性能虽然得到一定的提高,但是在实际应用中由于复杂度的增加，会增大软硬件实现成本，译码延迟等的不利影响。基于实际应用，硬判决译码算法得到优先考虑。本文提出了一种基于长除法 的北斗系统BCH(15,11)码的高效硬判决译码算法及实现结构。本算法不需要存储错误图样，也不需要解BM方程，只需要循环移位和模2相加，软硬件实现简单易行，适合接收机工程化实现和应用。
1 北斗导航电文数据码纠错编码方式[2]
导航电文采取BCH(15,11)码加交织方式进行纠错。BCH(15,11)码长为15比特，信息位为11比特，纠错能力为1比特，生成多项式为g(x)=x4+x+1。
BCH(15,11)码是循环码，可以通过线性移位寄存器电路有效实现其编码[8]
编码框图如图1所示，文献[2]有详细论述。
文献[2]中给出了BCH(15,11)硬判决译码算法，译码框图见图2，主要步骤如下：
(1)用接收码r(x)除以生成多项式g(x)得余式，此余式即为校正子。
(2)由校正子查错误图样表1，得错误码e(x)。
(3)由接收码r(x)模2相加e(x)得原码。
综上所述，译码算法采用的是错误图样查表法，需要预先存储错误图样，译码时，查找，匹配费时，效率不高。
图1 BCH(15,11,1)编码框图
图2 BCH(15,11,1)译码框图
表1 纠错信号的 ROM 表
2 本文提出的基于长除法的BCH(15,11)译码算法
BCH(15,11)生成多项式为g(x)=x4+x+1。
信息多项式为：m(x)=m10x10+m9x9+…+m1x+m0，(mi取0或1,i=0,1,…,10)
则，BCH(15,11)编码多项式为：c(x)=m(x)·g(x)。
此译码算法分为以下 2 步：
(1)由接收到的含有错误的r(x)=c(x)+e(x)循环长除g(x)得余式，若余式项数小于等于 1，即为错误多项式。
(2)错误多项式模2相加r(x)得原码。
证明：r(x)=m(x)g(x)+e(x)⟹e(x)≡r(x)mod(g(x))，故只要r(x)mod(g(x))余式相数小于等于1必为错误多项式。证毕。
例1：设发送码是：c(x)=m(x)·g(x)=(x10+x9+x7+x)·(x4+x+1)=x14+x13+x9+x8+x7+x5+x2+x
假设接收码是：r(x)=m(x)·g(x)=x14+x13+x9+x8+x7+x5+x4+x2+x，有 1位错误e(x)=x4，当然接收端是不知道有这 1位错误的。由循环长除法得错误多项式如 图 3 所示，得错误多项式e(x)=x4，纠错得原码。
图3 例1长除法得e(x)
例2：实际应用中通常采用系统码形式，编码方程为
c(x)=xn-km(x)+xn-km(x))mod(g(x))
设发送信息为：m(x)=x10+x8+x7+x+1
则，发送码是：
c(x)=x15-11m(x)+(xn-km(x))mod(g(x))
=x14+x12+x11+x5+x4+x3+x2+1
假设接收码是：
r(x)=c(x)+e(x)=x14+x11+x5+
x4+x3+x2+1
错误位e(x)=x12，当然接收端是不知道有这 1位错误的。由循环长除法得错误多项式如 图 4 所示，得错误多项式e(x)=x-3=x12，纠错得原码。
图4 例2长除法得e(x)
3 新算法软硬件实现结构
循环长除法软硬件实现如图5所示，主要包括循环移位，模2相加，判断r(x)不为0的个数。
①先寄存接收码r(x)，e(x)←r(x)。
②判断e(x)不为0的个数s，若s<2，则c=e+r结束。
③若当前e(x)第一位为1，则g(x)和e(x)分别对应的5位数据模2相加，g(x)逆时针移动一位；若当前e(x)第一位为0，则g(x)直接逆时针移动直到e(x)第一位对应位为1，g(x)和e(x)分别对应的5位数据模2相加，g(x)逆时针移动一位；转②。(g(x)最多逆时针移动25位)
由以上算法结构说明可得如下结论：本算法结构简单，只需要15位移位寄存器存储接收码，由生成多项式循环模2相加接收码，当错误位数小于等于1时，即得错误位，类似打地鼠游戏。相对文献[2]中给出了BCH(15,11)错误图样查表法，不需要预先存储错误图样；译码时，不需要查找，匹配，速度快，资源占用少，效率较高。
4 MATLAB仿真
仿真程序如下：
%BCH(15,11,1)
msg=gf(randint(1,11),1):%information code
c=bchenc(msg,15,11);%encode
n=gf([010000000000000],1);%1bit error
r=c+n;%receive code
e=r;
g=gf([1 0 0 1 1]);%generator polynomial
m=sum(e～=0);k=0;
while m>1 & k<2
k=k+1；
for j=1:11
if e(j)==1
e(j)=0;e(j+3)= e(j+3)+1; e(j+4)= e(j+4)+1;
end
if sum(e～=0)<2
disp('OK r(x)=e(x) mod(g(x))');e,
return
end
end
for j=12:15
if e(j)==1
e(j)=0; j1=mod(j+3,15); j2=mod(j+4,15);
e(j1)=e(j1)+1; e(j2)=e(j2)+1;
end
if sum(e～=0)<2
disp('OK r(x)=e(x) mod(g(x))');e,
return
end
end
end
disp('OK c=r+e');c=r+e;
图5 BCH(15,11)循环长除法实现结构图
仿真分析：运用本仿真程序对所有211=1024个原码，及211·15=15360个含有1个错误位的接收码进行仿真验算，均能正确纠错，由此可证明本算法有效可行。
5 结束语
随着北斗导航系统的逐步完善和全面提供各种应用服务,设计体积小，功耗低的接收机芯片至关重要，而BCH(15,11)译码算法在研制接收机中具有重要作用。本文提出的基于循环长除法的BCH(15,11)译码算法操作简单，易于软硬件实现，非常适合在北斗系统导航接收机中工程化应用。
