基于伽罗华域傅里叶变换的rs码识别方法-包昕.pdf

《基于伽罗华域傅里叶变换的rs码识别方法-包昕.pdf》由会员分享，可在线阅读，更多相关《基于伽罗华域傅里叶变换的rs码识别方法-包昕.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第 45 卷 第 1 期 电 子 科 技 大 学 学 报 Vol.45 No.1 2016年 1月 Journal of University of Electronic Science and Technology of China Jan. 2016 基于伽罗华域傅里叶变换的 RS码识别方法 包 昕1，陆佩忠2，游 凌1(1. 西南电子电信技术研究所 成都 610041； 2. 复旦大学计算机科学与工程系 上海 杨浦区 200433) 【 摘要 】 针对 RS码识别问题，研究并提出了基于伽罗华域傅里叶变换 (GFFT)的统计识别算法。在分析 GFFT谱向量的统计特性后，引入一种用于衡量谱

2、分量概率分布差异性的平方欧几里德距离测度，成功实现了对 RS码本原多项式、生成多项式的识别。仿真结果验证了理论分析的正确性。与同类算法相比，该算法的检测性能明显提高，且更适用于闭集集合大于 1的实际应用场合。 关 键 词 信道编码识别 ; 欧氏距离 ; 域上傅里叶变换 ; RS 中图分类号 TN911.22 文献标志码 A doi:10.3969/j.issn.1001-0548.2016.01.004 Recognition of RS Coding Based on Galois Field Fourier Transform BAO Xin1, LU Pei-zhong2, and YO

3、U 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 trans

4、form (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

5、 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

6、channel coding recognition; Euclid distance; galois field Fourier transform; RS 收稿日期： 2014 09 10; 修回日期： 2015 06 29 基金项目：国家自然科学基金 (61172140) 作者简介：包昕 (1986 )，男，博士生，主要从事盲信号处理、信道编码分析等方面的研究 . 信道编码识别问题，即是根据解调后的比特流序列，辨识出所采用的纠错编码类型及相应参数，广义上还包括对交织和扰码的识别。它的主要应用场合为： 1) ACM和协作通信中增加系统鲁棒性； 2) 在非合作条件下进行通信侦察及电子对抗。

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

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

9、合大小大于 1。以上几种算法在此时的虚警概率明显偏高，并不适用于实际应用场景。 第 1期 包昕，等 : 基于伽罗华域傅里叶变换的 RS码识别方法 31 本文通过分析 RS码特有的谱向量统计特征，提出基于欧氏距离测度的统计识别思想，设计并实现了针对本原多项式和生成多项式的识别算法。相比于前述同类算法，本文算法容错性能较高，并完全适用于闭集集合大于 1的实际应用场合。 1 问题描述 设某 RS码码组 ()xc 的码元符号取自pm 阶本原多项式 ()px所构成的扩域2GF(2 ) / ( )pmFx px= ，纠 错性能为 2t 。经信道传输，添加噪声向量 ()xe 后形成接收向量，其中误码率记为e

10、p ，有： () () ()x xx=+rce(1) RS码识别问题即是研究如何从接收向量 ()xr中恢复出 RS码相关参数的问题，具体包括本原多 项式 ()px、所采用的码根00 0121,mm mt +null 、生 成多项式 ()g x 。在实际通信中， RS码的码组起点和 长度往往能够通过帧同步或卷积交织参数确定，为简化问题，本文假设其已知。 2 域上傅里叶变换及欧式测度 2.1 域上傅里叶变换及谱向量统计特性 类似实数域和复数域上的离散傅里叶变换，在有限域上也可以定义傅里叶变换，简称 GFFT9。 定义 1 令 GF( )q 上的多项式： 12() , GF()nnn-1 n-2 1

11、 0 ivx v x v x vx v v q=+ (2) 在 GF( )mq 上的傅里叶变换多项式为： 1212 10() , GF( )nn mnn jVZ V Z V Z VZ V V q=+null (3) 其中， 10( ) ( ) 0 1n-jjijiiVv v jn= (4) 称为 ()VX的第 j 个谱分量。使用矩阵可表示为： 0 011 12 111 121 2 2 212 211 12 111 11() () () 1() () ()1() () ()1nnnn nn nn nnn nn nn nVv = nullnullnullnullnullnullnullnullnu

12、llnullnull(5) 其中，向量01 1, , nVV V=V null 为 ()vx在 GF( )mq 上的谱向量。 定理 1 多项式 ()vx以ja 为根的充要条件是谱向量 01 1, ,nVV V= nullV 的第 j 个谱分量jV 为 0。 因此，若给定一最小距离为 2+1dt= 的 RS码，将生成多项式定义为： 00 0121() ( )( ) ( )mm mtgx x x x += null(6) 式中，01m ； 是本原多项式 ()px的本原元。 定理 2 生成多项式 ()g x 的谱多项式 ()GZ 存在 2t 个 0系数，即： 000 2 1jGmjmt= () ()

13、ipx q x= ，识别成功。 2) 恢复生成多项式 ()g x ，即辨识码根集合| ( ) 0, 1,2 1qmjUjg j=。 已知本原多项式 ()px及欧几里得测度 d ，依据定理 5，可通过纠错性能 t ，计算出对应的误码率： e211exp ln2(2 1) 2 (1 1/ 2 )mmdpmt=(15) 依据定理 4，可获得在此误码率下谱分量为 0概率的理论值。显然，比值向量 q应与该理论值吻合。如果存在某个集合01 021, tmm m+= null ，使得： 0 | 0 | jjjPR j U jqPR j U j = = (16) 则 UM= ， 该 RS码必以00 0121,

14、mm mt +null 作为其生成多项式的根，生成多项式表示为： () ( )jjUgx x =(17) 反之，若无法找到这样的集合，则说明假设的纠错性能 t 错误， 需重新进行假设， 直到找到正确的 t 值。 算法描述如下： 输入：比值向量 12,nqq q= nullq 平方欧几里德测度 d 纠错性能集合 12,Ttt= null输出：码根集合 U生成多项式 ()g x For itT 利用式 (15)计算当前误码率 利用式 (9)计算谱分量为 0的理论概率值 For 01, 2,m = null 01 021, tmm m+= null If 式 (16)成立 UM= ，利用式 (17)

15、构造生成多项式，识别成功。 4 仿真及性能分析 4.1 算法仿真 例 4 某误码率为e0.01p = 的 (31,27)RS码序列被第三方截获，现对其展开识别。 1) 分别计算数据在不同扩域下作 GFFT后的欧式距离 d ，如图 4所示，横轴分别对应集合 Q 中不同本原多项式 ()qx所生成的扩域2()/ ()Fx qx，集合 Q依次为41x x+ + 、521xx+ + 、61x x+、71x x+ + 及84x x+ +321xx+ + 。 由图 4可得， 以最大值 0.155d = 所对应的本原多项式52() 1px x x= +作为识别结果。 1 2 3 4 500.020.040.0

16、60.080.100.120.140.16GFFT 值 平均欧氏距离图 4 不同扩域下的 d值 2) 做2()/ ()Fx px上 GFFT如图 5所示，图中横轴对应2()/ ()Fx px中元素234 301, , , , , , null ， 纵轴为比值向量 q。 0 5 10 15 20 25 3000.050.100.150.200.25j q在F2(x)/p(x)上做GFFT后的q值图 5 522()/ 1Fx x x+ + 下 GFFT的谱向量 可见， 存在集合3456, , , M = ， 使 j 时，0.219jq ； j 时， 0.031jq 。当 2t = 时，由式(15)

17、可知理论误码率e0.010 4p = 。 依据式 (9)， 0jR =概率满足： jU 时， Pr 0 0.222 1jR = ；当 jU时， Pr 0 0.031 3jR = = 。其中集合 U 大小为 24t = 。由此，本文可认定 UM= ，生成多项式 ()g x 必以3456, , , M = 中元素为根，即： 345642631824 18() ( )( )( )( )gx x x x xxxxx= =+(18)综上，本文成功地识别了该 (31,27)RS码的生成 电 子 科 技 大 学 学 报 第 45 卷 34多项式。 4.2 对比测试 文献 8,12同样提出了基于 GFFT的

18、RS码识别算法。文献 8关注谱向量的连零特征，若 1个接收码 组 r的谱向量12, , nRR R=R null 中，码根位置 U 处存在连零， 则称为一次记录， 若记录次数大于 0.51N ，即判定 () ()px qx= 。 文献 12则通过非线性变换和中值滤波，扩大了谱向量间的差异度，在此基础上，只要12QQ ，即判定 () ()px qx= ，其中，1| jQRjU=，2| jQRjU=。现将本文算法与这两种算法进行对比测试。 例 5 给定 (31,27)RS码，统计量 50N = ， 3种算法的识别成功率曲线如图 6所示。 0 0.005 0.010 0.015 0.0200 0.1

19、 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 误比特率 识别率本文算法 文献 12算法 文献 8算法 图 6 闭集集合大小为 1时， 3种算法识别成功曲线 可见，本文算法在高误码时劣于文献 12算法，但明显优于文献 8算法。现实中码根集合 U 未知，文献 8,12的算法回避了该问题，而本文利用式 (16)可实现集合 U 的检测和重建。为便于仿真比对，例 5中为文献 8,12的算法事先设定了此集合。 0 0.005 0.010 0.015 0.0200 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 误比特率 识别率本文算法 文献 12

20、算法文献 8算法 图 7 集合大小大于 1时， 3种算法识别成功曲线 例 5考察了 3种算法在闭集集合大小为 1时的 RS码闭集识别性能。闭集识别即是给定备选集合后，判定给定目标是否为某一备选项的模式匹配问题。由于低阶本原多项式 ()px个数非常有限，在实际工程应用中 RS码识别问题常采用闭集识别策略。因此，有必要考察 3种算法在闭集集合大小大于 1时的识别能力。 例 6 给定包含 (15,11)、 (31,27)、 (63,57)、 (127, 119)、 (255,239)共 5种 RS码的闭集集合。采用 3种算法对 (31,27) RS码进行识别，码组个数 50N = 。测试结果如图 7

21、所示， 文献 12算法的检测性能明显下降。 综上，本文算法比同类识别方法更为稳健，适合于实际工程应用场景。 4.3 统计量 N对识别成功率的影响 基于 GFFT的统计识别算法取决于能否获得足够多的正确码组，本节重点讨论统计量 N 与识别成功率的关系。 对于一个符号取自 GF(2 )m上的 (, )nk RS码，出现一个正确码字的概率为： (2 1)1 block no error e(1 )mmpp= (19) 式中，ep 表示当前误码率。在 N 个码组中至少出现一个正确码组的概率为： (2 1)block no error e1(1(1 ) )mmNNpp= (20) 因此，只有当block

22、 no error1/NpN 时，才真正存在至少一个正确码组，此时误码率应满足： 11/ (2 1)e11(11/ ) mN mpN (21) 设eup 为误码率上限。 显然，eup 随着统计量 N 的增加而提高。任何以获取正确码组作为前提的识别算法，性能都不可能超越此误码率上限。结合式 (13)可知，若希望正确识别本原多项式，应满足： 222(2 1)e1111(1)21mmmmptN (22) 式中， m 、 m分别代表本原多项式的真实阶数和试探阶数； N为由真实统计量 N 换算为试探本原多项式后的统计量。两者关系为： 12(2 1)(2 1)mmmNNm=(23) 因此，只要 N 与误码

23、率ep 满足： 13122(2)e12(2 ) (1 ) 22mmmm mmNpt(24) 即可保证算法 1的有效进行。 例 7 给定包含 (15,11)、 (31,27)、 (63,57)、(127,119)、 (255,239)共 5种 RS码的闭集集合。采用本文算法对 (31,27)RS码进行识别， N 依次设为 25、 50、100、 200。 测试结果如图 8所示。由图可见，随着统计量 N 第 1期 包昕，等 : 基于伽罗华域傅里叶变换的 RS码识别方法 35 的增加，算法的识别准确率明显提高。因此，足够的统计量 N 是算法保证有效性、提高容错性的充分条件之一。 0.005 0.01

24、0 0.015 0.0200.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 误比特率 识别率0 0 N = 25N = 50N = 100N = 200图 8 不同统计量 N的识别准确率 5 结 束 语 本文使用伽罗华域傅里叶变换 (GFFT)，设计和实现了针对 RS码的统计识别算法。通过对欧几里得测度统计特性的详细推导和证明，借助测度间的差异性实现了对本原多项式的辨识，并在此基础上完整恢复出生成多项式。同时本文还与两种同类算法进行比对，仿真结果显示，本文算法的识别稳健性更高，且完全适用于闭集集合大于 1的实际应用场景。最后还讨论了识别成功率与统计量的关系，为该算法的使用

25、提供了理论参考。 参 考 文 献 1 刘玉君 . 有限域上 RS码特征的研究 J. 信息工程大学学报 , 2007, 8(1): 64-67. LIU Yu-jun. Studies on the features of RS codes over finite fieldsJ. 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

26、 of RS codesJ. 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,

27、 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 eliminationJ. Telecommunication Engineering, 2014, 54(7): 926-931. 5 彭淼 , 高勇 . RS码参数的盲估计 J. 电子信息对抗技术 , 2013, 28(1): 5-

28、9. PENG Miao, GAO Yong. Blind parameter estimation of RS encoderJ. 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 paramete

29、rs based on probability approximationJ. Journal of Electronics & Information Technology, 2014, 36(2): 332-339. 7 VALEMBOIS A. Detection and recognition of a binary linear codeJ. Discrete Applied Mathematics, 2001, 111(1): 199-218. 8 刘健 , 谢锘 . RS码的盲识别方法 J. 电子科技大学学报 , 2009, 38(3): 363-367. LIU Jian, X

30、IE Ruo. Blind recognition method of RS codingJ. 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 methodsM. Xian: Xian University of Electro

31、nic Science and Technology Press, 2006. 10 闻年成 , 杨晓静 . RS码的盲参数识别 J. 计算机工程与应用 , 2011, 47(19): 136-139. WEN Nian-chen, YANG Xiao-jing. Blind recognition of RS codes parametersJ. Computer Engineering and Application, 2011, 47(19): 136-139. 11 王丰华 , 解辉 , 黄知涛 , 等 . 基于频谱累积量的线性分组码检测识别方法 J. 系统工程与电子技术 , 2013

32、, 35(12): 2595-2599. WANG Feng-hua, XIE Hui, HUANG Zhi-tao, et al. Blind recognition of linear block code based on spectral cumulantsJ. 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 preprocessingJ. Journal of Astronautic, 2013, 34(1): 128-132. 编 辑 税 红