包 昕，陆佩忠，游 凌(. 西南电子电信技术研究所 成都 6004；. 复旦大学计算机科学与工程系 上海 杨浦区 00433)



基于伽罗华域傅里叶变换的RS码识别方法

包 昕1，陆佩忠2，游 凌1
(1. 西南电子电信技术研究所 成都 610041；2. 复旦大学计算机科学与工程系 上海 杨浦区 200433)

【摘要】针对RS码识别问题，研究并提出了基于伽罗华域傅里叶变换(GFFT)的统计识别算法。在分析GFFT谱向量的统计特性后，引入一种用于衡量谱分量概率分布差异性的平方欧几里德距离测度，成功实现了对RS码本原多项式、生成多项式的识别。仿真结果验证了理论分析的正确性。与同类算法相比，该算法的检测性能明显提高，且更适用于闭集集合大于1的实际应用场合。

关 键 词信道编码识别; 欧氏距离; 域上傅里叶变换; RS

Recognition of RS Coding Based on Galois Field Fourier Transform

BAO Xin1, LU Pei-zhong2, and YOU Ling1
(1. Southwest Electronic and Telecommunication Technology Research Institute Chengdu 610041; 2. Department of Computer Science and Engineering, Fudan University Yangpu Shanghai 200433)

Abstract To recognize reed-solomon (RS) coding, a statistical arithmetic based on galois field Fourier transform (GFFT) is presented and studied. The statistical characteristics of spectral vectors generated by GFFT are analyzed, and the squared Euclid distance is introduced to measure the statistical difference between spectral vectors. Finally the primitive polynomial and general polynomial are obtained successfully. The simulation results verify the theory analysis and demonstrate that the recognition accuracy of the proposed algorithm is superior to other similar algorithms; moreover, the proposed algorithm can still work when the number of elements in a finite set is larger than one.

Key words channel coding recognition; Euclid distance; galois field Fourier transform; RS

信道编码识别问题，即是根据解调后的比特流序列，辨识出所采用的纠错编码类型及相应参数，广义上还包括对交织和扰码的识别。它的主要应用场合为：1) ACM和协作通信中增加系统鲁棒性；2) 在非合作条件下进行通信侦察及电子对抗。

RS码是一种多进制线性分组码。自1961年问世以来，已在卫星、深空、无线等通信领域大量使用，并被CCSDS、IESS、DVB等纳入国际标准。因此，针对RS码的识别研究显得极为必要。文献[1]揭示了RS码在GF(2)与GF(q )上的对应关系，提出了域上辗转相除法。文献[2-4]以此为基础，分别提出了基于域上欧几里德运算，中国剩余定理和域上高斯消元法的RS码识别策略。以上策略均基于线性变换，故对误码尤为敏感。针对该问题，文献[5-6]分别利用形如VALEMBOIS[7]的对偶码组发现模型，提出了具备一定抗误码能力的统计识别方案。

文献[8]最早将域上伽罗华域变换(GFFT)[9]引入RS码识别问题，但该方法需事先设定多种先验参数，抗误码能力较弱。文献[10]在此基础上，利用信息差熵和码根统计，实现了RS码相关参数的容错辨识，由于缺乏相应的理论推导，该算法的判决门限仍需事先人为设定。文献[11]提出了在GFFT后进行频谱累积量统计的检测方法，并给出了较明确的判决门限和统计量参数计算式。文献[12]进一步拓展了前述思想，使用非线性变换和中值滤波，增大了GFFT谱分量的区分度，明显提高了求取本原多项式时的容错性能。但时，由于缺乏明确的码根判定策略，使得生成多项式的重建仍存在不确定性。由于低阶本原多项式个数有限，RS码识别问题在工程实现时常采用闭集识别策略，且闭集集合大小大于1。以上几种算法在此时的虚警概率明显偏高，并不适用于实际应用场景。

本文通过分析RS码特有的谱向量统计特征，提出基于欧氏距离测度的统计识别思想，设计并实现了针对本原多项式和生成多项式的识别算法。相比于前述同类算法，本文算法容错性能较高，并完全适用于闭集集合大于1的实际应用场合。

1 问题描述

设某RS码码组c(x )的码元符号取自mp阶本原多项式p( x )所构成的扩域纠错性能为2t。经信道传输，添加噪声向量e(x )后形成接收向量，其中误码率记为pe，有：

RS码识别问题即是研究如何从接收向量r(x )中恢复出RS码相关参数的问题，具体包括本原多项式p( x )、所采用的码根生成多项式g( x )。在实际通信中，RS码的码组起点和长度往往能够通过帧同步或卷积交织参数确定，为简化问题，本文假设其已知。

2 域上傅里叶变换及欧式测度

2.1 域上傅里叶变换及谱向量统计特性

类似实数域和复数域上的离散傅里叶变换，在有限域上也可以定义傅里叶变换，简称GFFT[9]。

定义 1 令GF(q )上的多项式：

在GF(qm)上的傅里叶变换多项式为：

其中，

称为V( X )的第j个谱分量。使用矩阵可表示为：

定理 1 多项式v( x )以ja为根的充要条件是谱向量的第j个谱分量Vj为0。

因此，若给定一最小距离为d=2 t +1的RS码，将生成多项式定义为：

式中，m0≥ 1；α是本原多项式p( x )的本原元。

定理 2 生成多项式g( x )的谱多项式G( Z )存在2t个0系数，即：

由于循环码是xn1−剩余系中以g( x )为生成元的理想，每一个码多项式c( x )必满足因此，存在以下定理。

定理 3 码字多项式c( x )的谱多项式C( Z )，至少存在2t个连0，即：

又设M关于N的比值：

称为比值向量q。显然，当统计次数N足够大时，q应满足定理4。

2.2 平方欧几里德距离测度

如果能设计一种有效的不平衡准则，从形如图1的有限组统计结果中，确认具有最大差异性的一组比值向量则等价于实现了对本原多项式的闭集识别。

图1　(15,11)RS码在不同扩域下GFFT

区分向量间的差异性，需要通过设计某种差异性测度来实现。为此，本文引入平方欧几里德距离d，用以刻画q与均匀分布的差异性：

可证明，测度d满足如下定理：

式中，事件H0和H1分别表示为：

例2 如图2所示，先后给定若干RS码，分别统计在H0条件下比值向量q的欧氏距离d-Sta，同时标记理论值

例2与例3充分验证了前述定理的正确性。在一定误码率范围内，欧氏距离d对事件H0和H1具备明显的区分度。

图2　欧式距离d的统计值与理论值

图3　不同扩域下GFFT欧式距离d统计值

3 RS码识别算法描述

RS码识别问题可分解为辨识本原多项式p( x )和恢复生成多项式g( x )两部分。尽管RS码在码率、纠错能力、生成多项式的构造上可以不同，但均依赖于为数不多的若干本原多项式。基于这一事实，本文可对任意RS码采用闭集识别策略，通过事先构造本原多项式集合设计RS码的分步识别方法。

1) 辨识本原多项式p( x )。

首先使用集合Q中的本原多项式，分别对接收向量r(x )做GFFT，获得各自的谱向量；接着通过测度d刻画谱向量；最后选取差异度最大的d对应的本原多项式p( x )作为识别结果。算法描述如下：

输出：本原多项式p( x )

④ 利用式(12)计算欧式距离测度d

已知本原多项式p( x )及欧几里得测度d，依据定理5，可通过纠错性能t，计算出对应的误码率：

依据定理4，可获得在此误码率下谱分量为0概率的理论值。显然，比值向量q应与该理论值吻合。如果存在某个集合使得：

反之，若无法找到这样的集合，则说明假设的纠错性能t错误，需重新进行假设，直到找到正确的t值。算法描述如下：

平方欧几里德测度d

输出：码根集合U

生成多项式g( x )

① For ti∈ T

利用式(15)计算当前误码率

利用式(9)计算谱分量为0的理论概率值

③ If 式(16)成立

U= M，利用式(17)构造生成多项式，识别成功。

4 仿真及性能分析

4.1 算法仿真

1) 分别计算数据在不同扩域下作GFFT后的欧式距离d，如图4所示，横轴分别对应集合Q中不同本原多项式q( x )所生成的扩域集合Q依次为及

图4　不同扩域下的d值

图5　?下GFFT的谱向量

综上，本文成功地识别了该(31,27)RS码的生成多项式。

4.2 对比测试

文献[8,12]同样提出了基于GFFT的RS码识别算法。文献[8]关注谱向量的连零特征，若1个接收码组r的谱向量中，码根位置U处存在连零，则称为一次记录，若记录次数大于0.51N⎡⎤⎢⎥，即判定文献[12]则通过非线性变换和中值滤波，扩大了谱向量间的差异度，在此基础上，只要即判定其中，现将本文算法与这两种算法进行对比测试。

例5 给定(31,27)RS码，统计量N =50，3种算法的识别成功率曲线如图6所示。

图6　闭集集合大小为1时，3种算法识别成功曲线

可见，本文算法在高误码时劣于文献[12]算法，但明显优于文献[8]算法。现实中码根集合U未知，文献[8,12]的算法回避了该问题，而本文利用式(16)可实现集合U的检测和重建。为便于仿真比对，例5中为文献[8,12]的算法事先设定了此集合。

图7　集合大小大于1时，3种算法识别成功曲线

例5考察了3种算法在闭集集合大小为1时的RS码闭集识别性能。闭集识别即是给定备选集合后，判定给定目标是否为某一备选项的模式匹配问题。由于低阶本原多项式p( x )个数非常有限，在实际工程应用中RS码识别问题常采用闭集识别策略。因此，有必要考察3种算法在闭集集合大小大于1时的识别能力。

例6 给定包含(15,11)、(31,27)、(63,57)、(127, 119)、(255,239)共5种RS码的闭集集合。采用3种算法对(31,27) RS码进行识别，码组个数N =50。测试结果如图7所示，文献[12]算法的检测性能明显下降。

综上，本文算法比同类识别方法更为稳健，适合于实际工程应用场景。

4.3 统计量N对识别成功率的影响

基于GFFT的统计识别算法取决于能否获得足够多的正确码组，本节重点讨论统计量N与识别成功率的关系。

对于一个符号取自GF(2m)上的(n , k ) RS码，出现一个正确码字的概率为：

式中，pe表示当前误码率。在N个码组中至少出现一个正确码组的概率为：

设peu为误码率上限。显然，peu随着统计量N的增加而提高。任何以获取正确码组作为前提的识别算法，性能都不可能超越此误码率上限。结合式(13)可知，若希望正确识别本原多项式，应满足：

式中，m、m′分别代表本原多项式的真实阶数和试探阶数；N′为由真实统计量N换算为试探本原多项式后的统计量。两者关系为：

因此，只要N与误码率pe满足：

即可保证算法1的有效进行。

例7 给定包含(15,11)、(31,27)、(63,57)、(127,119)、(255,239)共5种RS码的闭集集合。采用本文算法对(31,27)RS码进行识别，N依次设为25、50、100、200。

测试结果如图8所示。由图可见，随着统计量N的增加，算法的识别准确率明显提高。因此，足够的统计量N是算法保证有效性、提高容错性的充分条件之一。

图8　不同统计量N的识别准确率

5 结 束 语

本文使用伽罗华域傅里叶变换(GFFT)，设计和实现了针对RS码的统计识别算法。通过对欧几里得测度统计特性的详细推导和证明，借助测度间的差异性实现了对本原多项式的辨识，并在此基础上完整恢复出生成多项式。同时本文还与两种同类算法进行比对，仿真结果显示，本文算法的识别稳健性更高，且完全适用于闭集集合大于1的实际应用场景。最后还讨论了识别成功率与统计量的关系，为该算法的使用提供了理论参考。

参 考 文 献

[1] 刘玉君. 有限域上RS码特征的研究[J]. 信息工程大学学报, 2007, 8(1): 64-67. LIU Yu-jun. Studies on the features of RS codes over finite fields[J]. Journal of Information Engineering University, 2007, 8(1): 64-67.

[2] 戚林. 一种RS码快速盲识别方法[J]. 电路与系统学报, 2011, 16(2): 71-76. QI Lin. A fast blind recognition method of RS codes[J]. Journal of Circuits and Systems, 2011, 16(2): 71-76.

[3] 甘露, 周攀. 基于中国剩余定理分解的RS码快速盲识别算法[J]. 电子与信息学报. 2012, 34(12): 2837-2842. GAN Lu, ZHOU Pan. Fast blind recognition method of RS codes based on Chinese remainder theorem decomposition [J]. Journal of Electronics& Information Technology, 2012, 34(12): 2837-2842.

[4] 李灿, 张天骐. 基于伽罗华域高斯列消元的RS码盲识别[J]. 电讯技术, 2014, 54(7): 926-931. LI Can, ZHANG Tian-qi. Blind recognition of RS codes based on Galois field columns Gaussian elimination[J]. Telecommunication Engineering, 2014, 54(7): 926-931.

[5] 彭淼, 高勇. RS码参数的盲估计[J]. 电子信息对抗技术, 2013, 28(1): 5-9. PENG Miao, GAO Yong. Blind parameter estimation of RS encoder[J]. Electronic Information Warfare Technology, 2013, 28(1): 5-9.

[6] 阔永红, 曾伟涛, 陈健. 基于概率逼近的本原BCH码编码参数的盲识别方法[J]. 电子与信息学报, 2014, 36(2): 332-339. KUO Yong-hong, ZENG Wei-tao, CHEN Jian. Blind identification of primitive BCH codes parameters based on probability approximation[J]. Journal of Electronics & Information Technology, 2014, 36(2): 332-339.

[7] VALEMBOIS A. Detection and recognition of a binary linear code[J]. Discrete Applied Mathematics, 2001, 111(1): 199-218.

[8] 刘健, 谢锘. RS码的盲识别方法[J]. 电子科技大学学报, 2009, 38(3): 363-367. LIU Jian, XIE Ruo. Blind recognition method of RS coding[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(3): 363-367.

[9] 王新梅, 肖国镇. 纠错码——原理与方法[M]. 西安: 西安电子科技大学出版社, 2006. WANG Xin-mei, XIAO Guo-zhen. Error correction code: principles and methods[M]. Xi’an: Xi’an University of Electronic Science and Technology Press, 2006.

[10] 闻年成, 杨晓静. RS码的盲参数识别[J]. 计算机工程与应用, 2011, 47(19): 136-139. WEN Nian-chen, YANG Xiao-jing. Blind recognition of RS codes parameters[J]. Computer Engineering and Application, 2011, 47(19): 136-139.

[11] 王丰华, 解辉, 黄知涛, 等. 基于频谱累积量的线性分组码检测识别方法[J]. 系统工程与电子技术, 2013, 35(12): 2595-2599. WANG Feng-hua, XIE Hui, HUANG Zhi-tao, et al. Blind recognition of linear block code based on spectral cumulants[J]. Systems Engineering and Electronics, 2013, 35(12): 2595-2599.

[12] 解辉, 王丰华. 基于频谱预处理的RS码盲检测识别方法[J]. 宇航学报, 2013, 34(1): 128-132. XIE Hui, WANG Feng-hua. Blind detection and recognition of RS code based on spectral preprocessing[J]. Journal of Astronautic, 2013, 34(1): 128-132.

编 辑 税 红

作者简介：包昕(1986 − )，男，博士生，主要从事盲信号处理、信道编码分析等方面的研究.

基金项目：国家自然科学基金(61172140)

收稿日期：2014 − 09 − 10; 修回日期：2015 − 06 − 29

中图分类号TN911.22

文献标志码A

doi:10.3969/j.issn.1001-0548.2016.01.004