基于星载数传系统的一种BCH码的译码方案_李璜宁.pdf

4 集成电路应用 第 40 卷 第 1 期（总第 352 期）2023 年 1 月 Research and Design 研究与设计0 引言 随着空间探测技术的发展，对于空间探测器存储功能的需求也越来越高。但由于可能出现的数据存储错误，需要对数据内可能出现的随机错误进行纠错。1 研究背景对此本次将以基于FPGA的星载数传数据存储系统为对象，对外部已编码过的输入数据进行BCH译码，最终有效实现星载数传数据的检测并纠错过程。实现工具。本次采用libero 11.9sp进行程序编译并通过modelsim进行相关功能仿真。2 BCH译码 假设发送的码字为v(x)v0+v1x+v2x2+v(n-1)x(n-1)，在传输过程中，受到错误信息e(x)干扰后最后接收到的码字为式（1）。r(x)r0+r1x+r2x2+r(n-1)x(n-1)（1）译码步骤如下：（1）利用接收码字r(x)计算伴随式S。（2）利用伴随式S求解错误多项式(x)。（3）求出(x)的根，进而通过求解得出的根来确定错误位置数，并在此基础上纠正发生错误的数据位，一般情况下对应位取反即可。2.1 计算伴随式S由于纠错能力为t的BCH码的伴随式S是一个2t维向量，即式（2）。S（S1，S2，S3，S2t）rHT （2）其中,H为一致校验矩阵，展开可以得到式（3）。Sir（i）r0+r1i+r22i+rn-1(n-1)i（1i2t）（3）若i的最小多项式为i(x)，则有式（4）。r(x)ai(x)i(x)+bi(x)（4）其中，bi(x)为次数小于i(x)的余式，而i（i）0，故如式（5）。Sir（i）bi（i）（5）联立式（1）与式（5），得到式（6）。Sie（i）（6）从式（6）可以看出，伴随式S仅仅与错误图样e(x)有关。2.2 计算错误位置多项式假设错误图样e(x)有v个错误，并且错误位置分布在xj1，xj2，xjv，其中0j1j2jvn，即式（7）。作者简介：李璜宁，上海航天电子有限公司，硕士；研究方向：信息与通信工程。收稿日期：2022-12-05；修回日期：2022-12-23。摘要：阐述太空中的恶劣环境影响，数据在存储传输过程中因为诸如单粒子效应而产生的错误，需要对于数据接收端接收到的可能存在错误数据进行检查以及纠错，用以保证数据结构的完整性与可靠性。在诸多检纠错码中，BCH码无疑是一种较为成熟的方案，探讨一种较为新型的BCH码译码方案，完成对于给定长度的数据进行译码，从而完成检错、纠错过程。关键词：信息通信，FPGA，BCH，译码。中图分类号：TN975，TN792 文章编号：1674-2583(2023)01-0004-04DOI：10.19339/j.issn.1674-2583.2023.01.002文献引用格式：李璜宁，刘小荣.基于星载数传系统的一种BCH码的译码方案J.集成电路应用,2023,40(01):4-7.基于星载数传系统的一种BCH码的译码方案李璜宁，刘小荣（上海航天电子有限公司，上海 201821）Abstract Due to the influence of the harsh environment in space,various errors occur during the storage and transmission of data due to effects such as the single-particle effect.At this time,it is necessary to check and correct the possible error data received by the data receiver to ensure the integrity and reliability of the data structure.Among the many error detection and correction codes,BCH code is undoubtedly a more mature scheme,the following will study a relatively new BCH code decoding scheme and complete the decoding of data of a given length,and finally complete the error detection and correction process.Index Terms information communication,FPGA,BCH,decoding.A BCH Code Decoding Scheme Based on Spaceborne Data Transmission SystemLI Huangning,LIU Xiaorong(Shanghai Aerospace Electronics Co.,Ltd.,Shanghai 201821,China.)集成电路应用 第 40 卷 第 1 期（总第 352 期）2023 年 1 月 5Research and Design 研究与设计e(x)xj1+xj2+xjv （7）得到方程组如式（8）。S1j1+j2+jvS2(j1)2+(j2)2+(jv)2S3(j1)3+j2)3+(jv)3S2t(j1)2t+(j2)2t+(jv)2t （8）从中可以看出，只需要用伴随式求出上述方程组的根j1，j2，jv，即可求得错误位置j1，j2，jv。将上述方程组改写为式（9）。S11+2+vS212+22+v2S313+23+v3S2t12t+22t+v2t （9）其中，kjk（1kv）称为错误位置数，同时对错误位置多项式(x)做出如下定义，如式（10）。(x)（1+1x）（1+2x）（1+v x）1+1x+2x2+vxv （10）通过数学计算，错误位置多项式系数i和伴随式S之前满足如下的恒等关系式，如式（11）。S1+10S2+1 S1+220S3+1 S2+2S1+330Sv+1Sv-1+v-1S1+vSv0 （11）2.3 求解错误位置多项式的根，得出错误位置求解上述方程组式（11）可以使用BM算法。BM算法实际上运用的是迭代的基本思想，对于式（11)，首先需要求出（1）(x)，使得带入后满足式（11）中的第一个等式。接着第二步是先检验（1）(x)（2）(x)是否成立，如若不成立，则对首次得出的（1）(x)添加一个修正项得出（2）(x)，同时使其次数最低，且满足式（11）中的前两个恒等式。接下来不断进行迭代，本文为进行到第v步的错误位置多项式，如式（12）。（v）(x)1+1（v）x+2（v）x2+hv（v）xhv （12）式（12）中，hv表示（v）(x)的最高次项系数。下一步需要判断第v+1步（v+1）(x)（v）(x)成立与否时需要计算第v次的迭代值式（13）。d(v)S(v+1)+1（v）S(v)+1（v）S(v-1)+hv（v）Sv+1-hv （13）此时若计算得到迭代值d(v)0，则表明等式成立。若不为0，则通过添加修正项来获得（v+1）(x)。具体计算方式为：首先返回至第v步之前的各个步骤，直至得出某一个多项式（t）(x)，使其满足第t步的迭代差值dt不为0，且t-hv具有最大值，此时，如式（14）。（v+1）(x)1（v）(x)+d(v)dt-1x（v-t）（t）(x)（14）3 BCH译码软件设计 3.1 错误位置多项式获取前面理论部分已提及，在BCH译码过程中，多余错误位置多项式的求解无疑是最为关键的一个步骤。这里通过对于流程图的理论完成固件设计。将式（13）与式（14）完成对于逻辑的编写算法。考虑到每次迭代后都有一个返回求解的过程，本次设计采用双重状态机迭代嵌套的方式，第一层为所进行的迭代次数，第二层则为在第一次所处的迭代次数中对于式（15）与式（16）的实现。据此所设计的状态转换图如图1所示。d(v)S(v+1)+1（v）S(v)+1（v）S(v-1)+hv（v）S(v+1-hv)（15）（v+1）(x)1（v）(x)+d(v)dt-1xv-t（t）(x)（16）本文对错误位置多项式的状态转换图进行相关说明：其中Num_v表示已经迭代到了第v次，这是第一层迭代。同时在每个第一层的迭代下都有一个下位状态机，这个下位状态机的主要作用是用于完成差值dv的计算以及对错误位置多项式的更新，即Elp_update状态。接下来在Desc状态下完成对式（15）的乘法部分计算，也就是将更新后得到的本原元的幂与Sj进行加法运算，而最后的Desc_update则是完成式（15）的最后一步加法运算，并计算出差值dv+2。至于为何是计算dv+2而非dv+1，在二进制BCH码情形下，BM算法有以下结论，即每次迭代后计数值加2与每次迭代后逐次加1等效。在第v+2迭代次数时，Elp1与Elp2分别计算式（16）中的第二项，得到（）(x)的系数与dv的本原元幂次，接着将各幂次相加并实现了伽罗华域中的乘法运算；接着Elp_update状态下实现式（16）中的加法，同时进行(v+2)(x)中迭代各个不同幂次的系数计算。并保证在进行到第v次迭代时对差值dv是否为0进行判断。若为0则进入状态Elp_update状态，即此时满足条件(v)(x)（v+2）(x)；若不为0，则返回上一步重新计算差值dv，直至其满足为0的条件。3.2 钱氏搜索硬件设计在获取相应的错误多项式后，需要求解其根，从而得到接收端错误数据发生的位置并进行相应的纠错。在众多求解根的算法中，比较常用的是采用钱氏搜索算法。其基本思想为将上述的各次幂，即6 集成电路应用 第 40 卷 第 1 期（总第 352 期）2023 年 1 月 Research and Design 研究与设计1，2，n-1带入上个步骤所得到的错误位置多项式(x)，并判断带入后是否满足(x)0。若不断进行带入，在k处使得(x)0成立，则代入的那个根k即为(x)0的一个根，同时可以得出错误数据发生的位置就在n-k处。由于考虑的是二进制BCH码，各个数据位仅存在0、1值，故得出错误位置后将对应位置的数据取反即可完成纠错。钱氏搜索的电路原理结构如图2所示。从电路结构可以看出，校验是从高位到低位逐级的一个过程，所以一共需要进行n次校验。采用钱氏搜索译码的一个显著的优点也就在于其为逐级译码过程，故可以在边进行校验的时候边解码，相当于并行操作的一次简易流水线，大大节省了译码所消耗的时间。钱氏搜索的具体过程为：首先在寄存器中输入并存储相应的错误位置多项式的系数，接着逐次按顺序输入k，2k，tk(1kn)。然后进行求和可以还原得出错误位置多项式：k(k)1+1k+22k+ttk。通过迭代法，若错误位置多项式k(k)0，则说明错误位置是n-k，错误个数为k。取反操作可以通过外接一个反相器进行对应功能的实现。4 功能仿真结果为了便于分析与观察，本次拟采用BCH（31，16，3）进行仿真结果分析，此时阶数m5，纠错能力t3当接收信号为data_in31b100_0111_1000_0100_1100_0000_0000_0000时，仿真图像如图3。通过仿真图可以看出，在译码过程结束后data_outdata_in，此时n_err0，即不存在接收信号错误，count0表明错误个数为0。综合上述可以得图2 钱氏电路硬件设计结构图1 错误位置多项式状态转换图 集成电路应用 第 40 卷 第 1 期（总第 352 期）2023 年 1 月 7Research and Design 研究与设计出接受信号正确，且并未收到错误信号干扰。此时随机加入3位错误，如图4所示。同理，通过将data_in与data_out进行数据位的对比可以看出，纠正后输出的data_out相较于data_in的第30位、第27位与第24位数据发生翻转，即错误发生在第30、27、24位，n_err由1变为0表明开始检测出错误，并且纠