基于GFFT的LFSR序列生成多项式估计方法

doi:10.11959/j.issn.1000-0801.2018025

摘要/Abstract

摘要：

针对线性反馈移位寄存器（LFSR）序列生成多项式的估计问题，提出了一种基于LFSR序列有限域傅里叶变换（GFFT）的估计方法。首先证明了LFSR序列GFFT的非零点与LFSR序列生成多项式的零点之间的对应关系，进而利用该性质实现 LFSR 序列生成多项式的快速估计，并给出了算法在误码环境下的改进方法。仿真实验验证了算法的有效性，并对算法的计算复杂度进行了理论分析。和已有算法相比较，本文提出的算法具有更高的计算效率。

关键词: 信号处理, 线性反馈移位寄存器, 有限域傅里叶变换, 生成多项式

Abstract:

The problem addressed here is generator polynomial estimation of linear feedback shift register (LFSR) sequence.An algorithm based on the Galois field Fourier transform (GFFT) was proposed.The relationship between non-zero points in GFFT of LFSR sequence and zero points in generator polynomial of LFSR sequence was illustrated firstly.Then the generator polynomial of LFSR sequence was fast estimated based on that property,and the improved method in noisy environment was proposed at last.Validity of the algorithm is verified by the simulation results,and the computational load is illustrated.The computational efficiency of the proposed algorithm is higher than that of the existing algorithms.

Key words: signal processing, linear feedback shift register, Galois field Fourier transform, generator polynomial

中图分类号:

TN911.22

沈利华. 基于GFFT的LFSR序列生成多项式估计方法[J]. 电信科学, 2018, 34(2): 58-64.

Lihua SHEN. Generator polynomial estimation of LFSR sequence based on GFFT[J]. Telecommunications Science, 2018, 34(2): 58-64.

图/表 5

参考文献 23

[1]	刘洋 . TD-SCDMA 同频组网中扰码性能分析及同频干扰的解决方法[J]. 电信科学, 2007,23(12): 48-53.
	LIU Y . An improved coverage solution for TD-SCDMA multi-frequency cellular network[J]. Telecommunications Science, 2007,23(12): 48-53.
[2]	任啸天, 徐晖, 王翔 ,等. 一种针对短码、周期长码直扩信号扩频序列盲估计方法[J]. 宇航学报, 2011,32(12): 2596-2600.
	REN X T , XU H , WANG X ,et al. A method for blind estimation of PN sequence of short-code and periodic long-code DSSS signal[J]. Journal of Astronautics, 2011,32(12): 2596-2600.
[3]	张志成, 黄小娜, 熊丽 . 一种适合多载波码分多址系统的扩频序列[J]. 电信科学, 2015,31(11): 47-51.
	ZHANG Z C , HUANG X N , XIONG L . A spread spectrum sequence for MC-CDMA system[J]. Telecommunications Science, 2015,31(11): 47-51.
[4]	YUAN C , ZHONG Y Z , YANG S Q . Composite chaotic pseudorandom sequence encryption algorithm for compressedvideo[J]. Tsinghua Science and Technology, 2004,9(2): 234-241.
[5]	HE W J . Reconstructing the feedback polynomial of a linear scrambler with the method of hypothesis testing[J]. IET Communications, 2015,9(8): 1044-1047.
[6]	柴先明, 彭耿, 师栋锋 ,等. 基于匹配搜索的伪随机序列生成多项式估计[J]. 光学精密工程, 2011,19(9): 2222-2227.
	CHAI X M , PENG G , SHI D F ,et al. Generator polynomial estimation of pseudo-random sequence based on match-searching[J]. Optics and Precision Engineering, 2011,19(9): 2222-2227.
[7]	黄开枝, 陈松 . 基于加权 WHT 的软判决序列快速估计算法[J]. 电子与信息学报, 2013,35(1): 74-79.
	HUANG K Z , CHEN S . A soft fast estimation method of PN sequence based on weighting Walsh Hadamard Transform (WHT)[J]. Journal of Electronics ＆ Information Technology, 2013,35(1): 74-79.
[8]	陈松, 黄开枝, 赵华 . 基于可信度累积的伪随机序列多项式估计算法[J]. 通信学报, 2012,33(9): 125-131.
	CHEN S , HUANG K Z , ZHAO H . Polynomial estimation method for PN sequence based on reliability accumulation[J]. Journal on Communications, 2012,33(9): 125-131.
[9]	陈松, 黄开枝 . 基于正反向联合 TCF 的序列多项式估计算法[J]. 电路与系统学报, 2013,18(2): 145-151.
	CHEN S , HUANG K Z . A method for generator polynomial estimation of PN sequence based on forward and backward combined TCF[J]. Journal of Circuits and Systems, 2013,18(2): 145-151.
[10]	郝士琦, 戚林, 王勇 . 一种新的伪随机扰码盲识别方法[J]. 电路与系统学报, 2011,16(4): 6-11.
	HAO S Q , QI L , WANG Y . A new blind recognition method of pesudo-randomizer code sequence[J]. Journal of circuits and systems, 2011,16(4): 6-11.
[11]	柴先明, 魏跃敏, 师栋锋 ,等. 一种基于与BCH码等价原理的m序列重构算法[J]. 电子与信息学报, 2011,33(2): 304-308.
	CHAI X M , WEI Y M , SHI D F ,et al. A method for reconstruction of m-sequence based on the equivalence with BCH codes[J]. Journal of Electronics ＆ Information Technology, 2011,33(2): 304-308.
[12]	张吴, 吕全通, 朱宇轩 . 基于线性分组码的自同步扰码盲识别[J]. 应用科学学报, 2015,33(2): 178-186.
	ZHANG W , LV Q T , ZHU Y X . Blind recognition of self-synchronized scrambler based on linear block code[J]. Journal of Applied Sciences, 2015,33(2): 178-186.
[13]	陈泽亮, 彭华, 巩克现 ,等. 基于软信息的扰码盲识别方法[J]. 通信学报, 2017,38(3): 174-182.
	CHEN Z L , PENG H , GONG K X ,et al. Scrambler blind recognition method based on soft information[J]. Journal on Communications, 2017,38(3): 174-182.
[14]	MATHIEU C . Reconstruction of a linear scrambler[J]. IEEE Transactions on Computers, 2007,56(9): 1283-1291.
[15]	LIU X B , SOO N K , WU X W . Reconstructing a linear scrambler with improved detection capability and in the presence of noise[J]. IEEE Transactions on Information Forensics and Security, 2012,7(1): 208-218.
[16]	LIU X B , KOH S N , CHUI C C ,et al. A study on reconstruction of linear scrambler using dual words of channel encoder[J]. IEEE Transactions on Information Forensics and Security, 2013,8(3): 542-552.
[17]	XIE H , WANG F H , HUANG Z T . Blind reconstruction of linear scrambler[J]. Journal of Systems Engineering and Electronics, 2014,25(4): 560-565.
[18]	廖红舒, 袁叶, 甘露 . 自同步扰码的盲识别方法[J]. 通信学报, 2013,34(1): 136-143.
	LIAO H S , YUAN Y , GAN L . Novel blind recognition method for self-synchronized scrambler[J]. Journal on Communications, 2013,34(1): 136-143.
[19]	虞红芳, 吴曼, 刘曼 ,等. 一种快速准确适用性广的伪随机扰码识别方法[J]. 电子科技大学学报, 2015,44(4): 500-504.
	YU H F , WU M , LIU M ,et al. Fast and correct recognition method for pseudo-randomizer code[J]. Journal of University of Electronic Science and Technology of China, 2015,44(4): 500-504.
[20]	黄芝平, 周靖, 苏绍璟 ,等. 基于游程统计的自同步扰码多项式阶数估计[J]. 电子科技大学学报, 2013,42(4): 541-545.
	HUANG Z P , ZHOU J , SU S J ,et al. Order estimation of self-synchronizing scrambling polynomial based on run statistic[J]. Journal of University of Electronic Science and Technology of China, 2013,42(4): 541-545.
[21]	吕全通, 张旻, 朱宇轩 . 基于相关度统计的同步扰码盲识别方法[J]. 数据采集与处理, 2016,31(3): 570-576.
	LV Q T , ZHANG M , ZHU Y X . Blind recognition method for synchronous scrambler based on statistical correlation[J]. Journal of Data Acquisition and Processing, 2016,31(3): 570-576.
[22]	ROBERT J M . 信息论与编码理论[M].李斗,殷悦,罗燕,译. 北京: 电子工业出版社, 2007.
	ROBERT J M . The theory of information and coding[M]. Translated by LI D,YIN Y,LUO Y. Beijing: Publishing House of Electronics Industry, 2007.
[23]	IMAMURA K , YOSHIDA W . A simple derivation of the Berlekamnp-Massey algorithm and some applications[J]. IEEE Transactions on Information Theory, 1987,33(1): 146-150.