基于FFT的RS码优化译码方法

本发明涉及一种通信领域的技术，具体是一种在突发错误场景下利用快速傅里叶变换(fft)进行reed-solomon(rs)译码的实现方法。

背景技术：

1、现有reed-solomon(rs)码的编码采用多变量多点赋值(mpe)方法，将信息视为有限域上的多项式，通过对多项式在不同位置采样生成冗余符号。然而，现有的rs码译码大多基于随机错误模型或对抗错误模型，在突发错误模型下的研究相对较少。此外，已有的wu方法仅能在循环群赋值点集的条件下进行译码，对更一般情况的处理能力有限。

技术实现思路

1、本发明针对rs码中的突发错误，提出一种基于快速傅立叶变换对rs码字进行折叠变换的唯一译码方法，通过该方法可以将rs码译码问题转化为交织rs码(简称irs)译码问题，使得转化后的irs码具有常数大小的码长并且可以快速译码。该方法达到准线性时间复杂度，且纠错能力可以渐进的达到singleton界。

2、本发明是通过如下技术方法实现的：

3、本发明涉及一种基于fft的rs码优化译码方法，利用基于伽罗瓦群的快速傅立叶变换处理，将rs码转化为交织rs码(irs)，将rs码的突发错误译码问题转化为irs的突发错误译码问题，通过对irs快速唯一译码得到正确的码字后，经快速傅里叶逆变换处理，完成译码，具体包括：

4、步骤1、针对给定码字进行参数初始化与判定，具体包括：

5、1.1根据码字r及给定码字有限域大小q，对q进行因数分解为则有设域扩展

6、1.2根据rs码参数码长n及原始信息位数k且k

7、的形式，其中：

8、1.3对n进行判定：当n＝t∣q-1，则执行步骤4，否则当且w≥1时执行步骤2。

9、步骤2、针对码字转换操作进行辅助参数预计算，具体包括：

10、2.1根据参数t,w，构造一个阶为的乘法子群一个维度为w的子空间后，构造半直积为的仿射线性子群，阶为且满足n≤q。

11、2.2对0≤i≤w，计算其中：wi≤w是w的i维子空间。对1≤k≤

12、u，计算其中：tk≤t是t的循环子群，其阶为令r＝w+μ，对1≤i≤t令pw+i＝qi，则计算为由gi确定的f的子域，满足并计算与gi相对应的次数为|gi|的x的多项式

13、2.3计算riemann-roch空间的基，具体为：

14、2.4设fg＝fq(xr)，计算l(x)＝∏a∈w(x+α)，选取满足l(γ)≠0并以此计算xr-l(γ)t的大小为n的零点集即在此赋值点集定义基础上

15、步骤3、将原始rs码与齐次irs码转换，具体包括：

16、3.1设长度为n的[n,k]编码携带的突发错误位数长度满足其中：∈是与编码冗余率或容错率相关的小正数参数，满足0＜∈＜＜1；e表示突发错误的分块数，将参数n素因数拆分为的形式，对任意1≤s≤r，令为n的一个因子，相应的定义设gs≤g是一个阶为ms的子群，计算由gs固定的子域并计算为多点集合在fs上的限制。对于j＝1,2,…,ns，计算则有当集合中的赋值点位按照的方式排布，通过{xw-αi-1l(γ)}在fs中的零点集计算，其中：α为大小为ns的乘法群的任一生成元；考虑域扩展同样在f中完全分裂，则rs[n,k]可以被映射到齐次irs码，如下式所示，其中：xu为步骤2.3计算的riemann-roch空间的基，则

17、3.2选取ns＝t。将原始码字r按照长度ms进行折叠得到矩阵所述的折叠是指，基于的排列假设将码字cf中与βj对应的ms个赋值点转置，从而将长度为n的码字向量转换为ms×ns的矩阵，其中：与对应的项为βj＝αj-1l(γ)，

18、

19、3.3对整数j∈[1,ns]，重复如下操作：对矩阵每一列rj执行g-ifft变换以获得多项式

20、所述的g-ifft变换，即通过将有理函数域和伽罗瓦理论中的自同构群应用于fft而构造的广义逆快速傅里叶变换，其实现对于上的次数不高于n的多项式f(x)在n个不同位置上的赋值与该多项式的n个系数之间的相互转换，具体为：

21、

22、3.4对整数i∈[0,ms-1]，重复如下操作：以作为输入运行步骤4的唯一译码方法，获取输出为

23、3.5对c(i)执行g-ifft变换以获得多项式

24、3.6计算

25、3.7计算并输出译码结果

26、步骤4、对赋值点集为循环群或其陪集的rs[n,k]进行突发错误唯一译码，具体包括：

27、4.1对于所述的赋值点集为循环群或其陪集的rs[n,k]，当参数如下：赋值点集是一个循环群的陪集，寻找生成元α及群元素ξ使得其为其中：的阶为n。则rs[n,k]可以定义为当rs码字长度为n，其携带的突发错误位数满足

28、4.2预计算所述的λ(i)(x)通过如下方式定义：令r＝n-k，对于一个突发错误间隔[i,i+r-2]，总可以通过如下方式将其视作[1,n]的子集则对应于[i,i+r-2]的互反错误定位子

29、4.3计算r*的校验子多项式s(x)＝s0+s1x+…+sn-k-1xn-k-1，其中：设r*由正确码字c和突发错误e构成，e是一个错误长度满足的突发错误。则r*的校验子多项式δj＝∏k≠j(ξαj-1-ξαk-1)-1；

30、4.4计算

31、4.5在集合{1,α,…,αn-1}中计算γ(x)的根。根据前文s(x)和γ(x)的定义，当时γ(x)拥有个连续根序列。找到最长的连续根序列后记录起始位置i和序列长度

32、4.6使用记录的擦除位置对r*进行擦除译码，具体包括：

33、i)计算及其导数λ′(c)。

34、ii)使用快速傅里叶逆变换计算f(x)∈fq[x]＜n，使得f(x)满足以下条件：

35、当则有f(ξαj-1)＝λ(ξαj-1)rj；当则f(ξαj-1)＝0。然后计算f(x)的导数f′(x)。

36、iii)对于j∈[i,i+i-1]，计算码字cj＝f′(ξαj-1)λ(ξαj-1)-1；对于计算码字cj＝rj。

37、4.7输出经过纠错的码字为(c1,c2,…,cn)。

38、本发明涉及一种实现上述方法的系统，包括：变换单元和译码单元，其中：变换单元通过计算赋值点集和构造相关多项式，将原始码字映射到赋值点集为循环群或循环群陪集的齐次交织rs码的表示形式；译码单元对循环群及其陪集赋值点上的唯一译码操作。

39、技术效果

40、本发明通过对赋值点集的推广实现对赋值点集为循环群或其陪集时的rs[n,k]进行突发错误唯一译码方法，从而将吴氏算法推广到赋值点为循环群陪集的情况；通过针对rs码中的突发错误设计准线性时间的唯一译码方法，本方法能够实现渐进达到singleton界的纠错能力；与现有技术相比，本发明实现对任意实数∈>0及任意整数e≥1，能对长度小于n-k-n∈(e+2)的rs[n,k]在突发错误模型下以不高于∈/qe-1的误纠概率进行唯一译码，特别地，当n为一个o(1)-平滑整数时，rs[n,k]的唯一译码可以通过本译码方法在的准线性复杂度时间内完成。