文章快速检索    
  深空探测学报  2017, Vol. 4 Issue (4): 385-389  DOI: 10.15982/j.issn.2095-7777.2017.04.012
0

引用本文 

詹亚锋, 解得准. BCH(63,56)性能分析及仿真[J]. 深空探测学报, 2017, 4(4): 385-389. DOI: 10.15982/j.issn.2095-7777.2017.04.012.
ZHAN Yafeng, XIE Dezhun. Performance Analysis and Simulation of BCH(63,56)[J]. Journal of Deep Space Exploration, 2017, 4(4): 385-389. DOI: 10.15982/j.issn.2095-7777.2017.04.012.

基金项目

国家自然科学基金资助项目(61671263,61271265);清华大学自主科研项目(20161080057,20131089244)

作者简介

詹亚锋(1976– ),男,副研究员,博士生导师,主要研究方向:深空通信、通信信号处理。通信地址:清华大学中央主楼12层(100084)电话:(010)62773218 E-mail:zhanyf@tsinghua.edu.cn

文章历史

收稿日期:2016-11-03
修回日期:2017-07-09
BCH(63,56)性能分析及仿真
詹亚锋, 解得准    
清华大学 宇航技术研究中心,北京 100084
摘要: 作为一种实现复杂度低的信道编码方式,BCH(63,56)码被广泛应用在空间遥控链路中,具有检测2 bit错误及纠正1 bit错误的性能。从理论分析和计算机仿真两个方面研究了BCH(63,56)码的编码性能。在介绍BCH(63,56)码编译码原理的基础上,对其误码率性能进行了理论计算和蒙特卡洛仿真。结果表明:当译码后的误码率为1 × 10–5时,BCH(63,56)码的编码增益可达2.1 dB。
关键词: BCH(63,56)    空间通信    蒙特卡洛仿真    
Performance Analysis and Simulation of BCH(63,56)
ZHAN Yafeng, XIE Dezhun     
Space Center of Tsinghua University,Beijing 100084,China
Abstract: BCH(63, 56)is widely used in uplink channel of deep space communication for low-complexity implementing, which can check 2 bits error and correct 1 bit error. The performance of BCH(63, 56)is studied by theoretical analysis and computer simulation in this paper. On the basis of introducing the basic principle of BCH(63, 56), the performance of bits error rate is calculated and the Monte Carlo simulation is carried out. The results show that the coding gain of BCH(63, 56)can be up to 2.1 dB when the bit error rate is 1e–5.
Key words: BCH(63, 56)    deep space communication    Monte Carlo simulation    
0 引 言

在卫星测控通信中,可靠的测控信息传输至关重要。通常在地面站发射功率足够的情况下,为了降低航天器实现的复杂度,上行遥控链路不采用信道编码。但是在特殊场景,如深空通信中,超远的传输距离使得上行链路增加信道编码变得十分必要。

空间数据系统咨询委员会(Consultative Committee for Space Data Systems,CCSDS)在其发布的建议书[1-2]中对上述问题进行了说明,建议在空间通信遥控链路中采用BCH(63,56)作为信道编码。该编码可以纠正1 bit的错误,辨识2 bit的错误。

多篇文献对BCH(63,56)的在轨实现方式进行了研究[3, 6-7],但是尚未发现有文献对BCH(63,56)的编码增益进行讨论,这给工程设计人员带来了困惑。为此,本文通过理论分析和计算机仿真两个方面,对BCH(63,56)的编码性能进行分析和讨论。论文结构如下:第1节对BCH的编码原理进行介绍;第2节基于BCH(63,56)的纠错能力,对其编码增益进行理论分析;第3节对其编码增益进行蒙特卡洛仿真,并和理论性能进行对比;第4节对全文进行小结。

1 BCH编码原理简介 1.1 BCH码编码原理

BCH码是循环码的一种,循环码是被广泛使用的线性分组码[8-9]。它是汉明码的一种推广形式,可以纠正多个错误。在给定纠错能力的前提下,可以设计不同码长的BCH码来实现要求的纠错功能[10]

不失一般性,假设研究的BCH码为BCH(nk),其中:n为编码之后数据帧的长度(单位是bit);k为要传送的消息长度(单位是bit)。设要传送的消息矢量为

$\mathit{\boldsymbol{m}} = \left[ {{m_0},{m_1}, \cdots ,{m_{k - 1}}} \right]$ (1)

编码之后的数据帧为

$\mathit{\boldsymbol{c}} = \left[ {{c_0},{c_1}, \cdots ,{c_{n - 1}}} \right]$ (2)

编码器实现的功能为将长度为k bit的消息矢量线性映射为长度为n bit的码字,这两者之间的关系为

$\mathit{\boldsymbol{c}} = {m_0}{g_0} + {m_1}{g_1} + \cdots + {m_{k - 1}}{g_{k - 1}} = \mathit{\boldsymbol{m}} \cdot \mathit{\boldsymbol{G}}$ (3)

其中:G为生成矩阵,可以表示为

$\mathit{\boldsymbol{G}} = \left[ {\begin{array}{*{20}{c}}{{g_0}}\\[5pt]{{g_1}}\\[5pt] \vdots \\[5pt]{{g_{k - 1}}}\end{array}} \right]$ (4)

其中:每一行都是一个n维的行向量。

编码的过程也可以写成多项式的形式,已知消息矢量,可以得到消息多项式

${m}(x) = {m_0} + {m_1}x + \cdots + {m_{k - 1}}{x^{k - 1}}$ (5)

为了将该消息多项式生成码字多项式,需要在该消息多项式的基础上乘以(nk)次生成多项式。

${c}(x) = {m}(x) \cdot {g}(x)$ (6)

如果按照式(6)生成码字矩阵,则有用的信息并不是集中在已编码矩阵的右侧,因此,需要首先对消息矩阵进行移位

${x^{n - k}}{m}(x) = {m_0}{x^{n - k}} + {m_1}{x^{n - k + 1}} + \cdots + {m_{k - 1}}{x^{n - 1}}$ (7)

将移位之后的消息多项式除以生成多项式

${x^{n - k}}{m}(x) = a(x){g}(x) + b(x)$ (8)

其中:a(x)和b(x)分别为商式和余式。其中余式为

$b(x) = {b_0} + {b_1}x + {b_2}{x^2} + \cdots + {b_{n - k + 1}}{x^{n - k + 1}}$ (9)

实际用来发送的码字多项式为消息多项式和余式的和

$\begin{array}{l}c(x) = {x^{n - k}}m(x) + b(x) = a(x)g(x)\\\;\;\;\;\;\;\; = {m_0}{x^{n - k}} + {m_1}{x^{n - k + 1}} + \cdots + {m_{k - 1}}{x^{n - 1}}\\\;\;\;\;\;\;\;\;\;\; + {b_0} + {b_1}x + {b_2}{x^2} + \cdots + {b_{n - k + 1}}{x^{n - k + 1}}\end{array}$ (10)

因此,BCH(63,56)编码的步骤可以概括为[3]

1)用xnk乘以消息多项式m(x);

2)用相乘之后得到的多项式除以生成多项式g(x),得到余式为b(x)(余式即为校验多项式);

3)码字多项式为消息多项式和校验位多项式之和c(x)= xnkm(x)+ b(x)。

对于BCH(63,56)码来说,已知其生成码多项式为g(x)= 1 + x2 + x6 + x7。因此,具体的编码过程为[11]

1)将56位消息序列转化成消息多项式;

2)在消息多项式的基础上乘以x7

3)将得到的多项式除以生成多项式,得到余式,最后与得到的余式相加,得到码字多项式;

4)将生成的码字多项式转化为矢量的形式。

1.2 BCH码编译码原理

采用伴随式译码[5]的方法对BCH(nk)码进行译码。伴随式译码的主要思想是:为了判断接收到的信息有没有发生错误,需要根据生成多项式判断该序列对应的伴随式。如果伴随式为零,则说明接收到的序列没有发生错误或者发生了错误但是变成了另外一个有效码字(这种错误不可检测),如果伴随式不为零,需要根据错误图样和伴随式的关系判断发生错误的位置并进行力所能及的纠错。错误图样实际上是一个和码字有相同长度的矩阵。对于只能纠正1位错误的BCH(63,56)码来说,其对应的错误图样矩阵中只有1个“1”,其他元素全部为“0”。如果对接收到的码字求解伴随式,该伴随式和某一个错误图样恰好匹配,则该错误图样矩阵中的“1”的位置即为接收码字中发生错误的位置。对该位置上的码元取反(码字“1”纠正为“0”,码字“0”纠正为“1”),即可对该码字进行纠正。同理,如果研究的BCH(n,k)码具有纠正多位错误的能力,则其对应的错误图样矩阵中的非零元素应为多个(数目和纠正错误的位数相等)。纠正接收码字的过程实际上是将接收码字矩阵与相匹配的错误图样矩阵求异或运算的过程。

对于BCH(nk)码来说,每一个接收信号的伴随式都是一个r = nk位的矢量,若接收信号矢量定义为v,则伴随式矢量为

$\mathit{\boldsymbol{s}} = \mathit{\boldsymbol{v}} \cdot {H^{\rm{T}}}$ (11)

其中:H表示校验矩阵。校验矩阵可以由生成矩阵得到[5],若生成矩阵可以写成

$\mathit{\boldsymbol{G}} = \left[ {{{\bf{I}}_{k \times k}}\left| {{\mathit{\boldsymbol{P}}_{k \times r}}} \right.} \right]$ (12)

则校验矩阵可以写成

$\mathit{\boldsymbol{H}} = \left[ {{\mathit{\boldsymbol{P}}_{k \times r}}\left| {{{\bf{I}}_{r \times r}}} \right.} \right]$ (13)

两者之间的关系为

$\mathit{\boldsymbol{G}} \cdot {\mathit{\boldsymbol{H}}^{\rm{T}}} = {{\bf{0}}_{k \times r}}$ (14)

伴随式矢量s的性质为:当v是一个有效的码字时,生成的伴随式矢量s为零,伴随式为零意味着接收的序列对应的多项式能够被生成多项式整除。因此,伴随式为零不能保证没有错误的出现,接收的序列可能是另外一个有效的码字。假设错误图样为e,则接收矢量可以表示为:v = c + e,则伴随式和错误图样的关系为

$\mathit{\boldsymbol{s}} = \mathit{\boldsymbol{v}} \cdot {\mathit{\boldsymbol{H}}^{\rm{T}}} = \mathit{\boldsymbol{e}} \cdot {\mathit{\boldsymbol{H}}^{\rm{T}}}$ (15)

从式(15)可以看出,只要知道错误图样和伴随式的对应关系,就可以根据接收信号矢量生成的伴随式求出错误的位置并且进行纠正。对于BCH(63,56)码来说,其纠错能力为1 bit,因此,只要求出每一位出错时对应的错误图样,并且根据所有可能的错误图样得到所有可能的伴随式,就可以根据接收信号矢量的伴随式得到发生错误的位置并且进行纠正。图 1是BCH(63,56)码的译码器原理框图[4,12]

图 1 BCH(63,56)译码器原理框图 Fig. 1 Flowchart of decoding of BCH(63,56)

按照图 1,BCH(63,56)码的译码步骤可以概括为:

1)利用伴随式计算电路计算[6-7]接收信号序列的伴随式;

2)因为BCH(63,56)码只能纠正1 bit错误,生成所有发生1 bit错误的错误图样。由所有错误图样生成所有可能的伴随式;

3)将接收信号序列生成的伴随式与所有错误图样对应的伴随式进行比对,发现错误的位置并且对错误进行纠正。

2 BCH码性能估算

本节对BCH(63,56)的编码性能进行估算。因为BCH(63,56)码是纠错码,其可以纠正编码后数据在信道传输的过程中发生的1 bit错误。因此,在相同的Eb/N0水平下,经过BCH(63,56)编码后再传输的方案势必比直接传输有用数据的方案得到的误码率小。为精确计算误码率,需要首先知道在给定Eb/N0条件下每一帧发生不同数量比特错误的概率。这里主要考虑如下4种错误类型:没有错误、有1 bit错误、有2 bit错误以及有3 bit及以上错误。设其发生的概率分别为P(0)、P(1)、P(2)及P(3)。

Eb/N0 = 6.8 dB为例,未编码的BPSK信号对应的误码率为PBPSK = 1 × 10–3,则可以计算P(0)、P(1)、P(2)及P(3)为

$P(0) = {(1 - {P_{{\rm{BPSK}}}})^{63}} = 93.9\% $ (16)
$P(1) = C_{63}^1{P_{{\rm{BPSK}}}}{(1 - {P_{{\rm{BPSK}}}})^{62}} = 5.9\% $ (17)
$P(2) = C_{63}^2P_{{\rm{BPSK}}}^2{(1 - {P_{{\rm{BPSK}}}})^{61}} = 0.18\% $ (18)
$P(3) = C_{63}^3P_{{\rm{BPSK}}}^3{(1 - {P_{{\rm{BPSK}}}})^{60}} = 3.7 \times {10^{ - 5}}$ (19)

其中: $C_{63}^1$ $C_{63}^2$ $C_{63}^3$ 均为组合数, $C_m^n = \displaystyle\frac{{m!}}{{n!(m - n)!}}$

则若未进行BCH编码,系统误码率可以近似为

$BE{R_{{\rm{normal}}}} = \frac{{NP(1) + NP(2) \times 2 + NP(3) \times 3}}{{N \times 63}}$ (20)

其中:N为总的帧数目。因为发生3 bit以上错误的帧较少,所以错误3 bit及以上的帧均按照错误3 bit来计算。

若进行BCH(63,56)编码,则译码后系统的误码率为

$BE{R_{{\rm{BCH}}}} = \frac{{NP(2) \times 2 + NP(3) \times 3}}{{N \times 63}}$ (21)

因为BCH(63,56)码可以纠正1 bit的错误,所以不再计算错误1 bit导致的误码率。按照上面的方法,对BCH(63,56)码的误码率性能进行估算,结果如表 1所示。

表1中给出的结果是用概率方法估计的BCH(63,56)码在不同的Eb/N0水平下,误码率的理论计算结果。从前面的计算过程中可以看出,BCH(63,56)码对于误率的减小主要是因为其可以对信道传输过程中发生的1 bit错误进行纠正。从而在相同的Eb/N0水平下,比未经过BCH(63,56)码编码的方案在误码率上有所减小。为了验证理论计算的正确性,在第3节中,将会利用MATLAB软件实际仿真得到BCH(63,56)码的性能。同时为了直观比较经过BCH(63,56)码编码后的方案和未经编码方案的误码率,将会在同一坐标尺度下进行比较。

表 1 理论计算得到的采用BCH编码的系统的误码率 Table 1 Error rate of BCH coded system by theoretical calculation
3 BCH(63,56)码性能仿真

本节用MATLAB软件对BCH(63,56)码的编译码过程进行蒙特卡洛仿真,以得到在不同的Eb/N0条件下BCH(63,56)码的误码率性能。仿真程序的流程图如图 2所示。

图2所示,对BCH(63,56)码仿真的步骤[13-14]主要为:首先在MATLAB中产生随机信源,即要发送的有用码字信息。然后根据第1节介绍的编码方法,把每56位信息码字在生成多项式已知的条件下映射成为63位码字。仿真中,采用的调制方式为二进制相移键控(Binary Phase Shift Keying,BPSK)。生成的码字经过BPSK调制之后成为基带调制信号,根据不同的Eb/N0可对基带调制信号添加不同大小的高斯白噪声,从而模拟信号在信道中传输的过程[15]。对于接收端,首先对经过信道传输的信号进行基带BPSK解调,恢复出63位码字。随后,利用伴随式计算该63位码字的伴随式并与本地存储的错误图样进行对比,从而可纠正信道传输过程中引起的错误。

根据仿真框图,通过在MATLAB中进行仿真,可以得到BCH(63, 56)码在不同Eb/N0下的性能。

图 2 计算机仿真流程图 Fig. 2 Flowchart of computer simulation

图 3为仿真得到的BCH(63,56)码的误码率和误帧率,同时,也画出了理论计算得到的BCH(63,56)码的性能以及BPSK未编码系统的误码率性能。

图 3 BCH(63,56)误码率性能和未编码系统性能比较 Fig. 3 The comparison of BCH(63,56)and un-coded system

图 3中可以看出,当信噪比较小时,经过BCH(63,56)码编码与未编码系统的误码率性能相仿,而比理论计算部分得到的误码率性能要差。这是因为,在低信噪比的情况下,消息在传输过程中可能会发生多位的错误,而BCH(63,56)码只能纠正1 bit的错误,并且只能检测出2 bit的错误。如果接收端发生了2 bit错误,则接收端能够检测出该码字发生了错误,但是不能对其进行纠正。当接收端发生了3 bit或者大于3 bit的错误时,接收端不能检测出该码字发生的3 bit错误,更严重的是,因为多比特错误图样对应的所有可能的伴随式,与1 bit错误图样对应的伴随式有交集,因此此时接收端可能会对接收序列按照发生了1 bit错误进行“纠错”,当然这个“纠错”的过程势必会导致接收序列在错误的基础上再多错一位。而对误码率进行理论计算的过程中,并没有考虑BCH(63,56)帧错3 bit以上情况导致的负作用。从而导致在信噪比很低的情况下仿真误码率劣于理论计算的误码率性能。

当信噪比大于4 dB时,BCH(63,56)码的误码率性能开始明显好于未编码系统的误码率性能,并且随着信噪比增大两者之间的差距越来越大。这是因为在信噪比较大的情况下,每一帧接收信息中发生错误的比特数都在1 bit左右,当发生1 bit的错误时,BCH(63,56)码能够发挥出其纠错的功能。对于所有发生不同比特错误的帧来说,发生1 bit错误的帧在所有发生错误的帧中所占的比例越来越大,因此两者之间误码率性能的差距越来越大。因此,当信噪比逐步提高时,BCH(63,56)码的误码率性能的优越性逐步就显现出来了。

同时,在高信噪比的情况下,仿真性能与理论计算的性能相仿,这是因为此时在系统中出现3 bit错误的帧的概率很小。从图 3还可以看出,在1 × 10–5的误码率条件下,BCH(63,56)的编码增益约为2.1 dB。

4 结 论

BCH(63,56)码可以纠正1 bit错误并且检测出2 bit错误,该种编码方式适合于用在深空通信遥控链路中。通过理论分析和计算机仿真,表明在1 × 10–5的误码率条件下,BCH(63,56)的编码增益约为2.1 dB。上述结论可以为深空通信系统的工程人员进行系统设计时提供参考。

参考文献
[1] CCSDS. TC synchronization and channel coding[Z]. [S. l.]: CCSDS, 2010.
[2] CCSDS. TC synchronization and channel coding – summary of concept and rationale[Z]. [S. l.]: CCSDS, 2006.
[3] Arunkumar S, Kalaivani T. FPGA implementation of CCSDS BCH(63, 56)for satellite communication[C]//IEEE International Conference on Electronics Design. [S. l.]: IEEE, 2013.
[4] 贺鹤云. LDPC码基础与应用[M]. 北京: 人民邮电出版社, 2009.
He H Y.Principle and application of LDPC[M].Beijing:Posts & Telecom Press,2009.
[5] 王育民, 李晖. 信息论与编码理论[M]. 北京: 高等教育出版社, 2013.
Wang Y M,Li H. The theory of information and coding[M].Beijing:Higher Education Press,2013.
[6] Lonescu L M, Anton C, Tutanescu I. Hardware implementation of BCH Error-correcting codes on a FPGA[J]. International Journal of Intelligent Computing Research(IJICR), 2010, 1(3): 148-153.
[7] Kusumawardani S S, Sutopo B. Designing 1 bit error correcting circuit on FPGA using BCH codes[C]//Proceedings of International Conference on Electrical, Communication, and Information, CECI. [S. l.]: CECI, 2001.
[8] 王新梅, 肖国镇.纠错码——原理与方法[M]. 西安: 西安电子科技大学出版社,2001.
Wang X M,Xiao G Z. Principles and methods of error correcting codes[M].Xi’an: Xidian University Press,2001.
[9] 杨晓琳.循环码理论及其译码算法研究——设计距离为11的二元BCH码构造及其B-M迭代译码算法实现[D].成都: 成都理工大学,2008.
Yang X L.Research on cyclic codes and its decoding algorithms—construction of binary BCH codes with design distance 11 and complementation of its B-M iterative decoding algorithm[D].Chengdu: Chengdu University of Technology,2008.
[10] 王永波.BCH译码算法的研究及硬件实现[D].厦门: 厦门大学,2011.
Wang Y B.BCH decoding algorithm and hardware implementation[D].Xiamen: Xiamen University,2011.
[11] 江建国.BCH编译码器的设计及验证[D].上海: 上海交通大学,2010.
Jiang J G.Design and verification of BCH encoder and decoder[D].Shanghai: Shanghai Jiao Tong University,2010.
[12] 张宗橙.纠错码原理和应用[M].电子工业出版社,2003.
Zhang Z C. Principle and application of error correcting codes[M]. Publishing House of Electronics Industry,2003.
[13] 李志国,张伟功.BCH码迭代译码算法及软件实现方法[J].计算机技术及发展,2007,17(4):171-174.
Li Z G,Zhang W G.Binary BCH code BM decoding Algorithm and soft ware realization[J].Computer Technology and Development, 2007,17(4):171-174. http://d.wanfangdata.com.cn/Periodical/wjfz200704047
[14] 王立宁. MATLAB与通信仿真[M]. 人民邮电出版社, 2000.
Wang L N. MATLAB and communication simulation[M].Posts & Telecom Press,2000.
[15] 樊昌信, 曹丽娜. 通信原理[M]. 北京: 国防工业出版社, 2012.
Fan C X,Cao L N.Principles of communications[M]. Beijing: National Defense Industry Press, 2012.