《伪随机序列m和M的生成算法实现.docx》由会员分享，可在线阅读，更多相关《伪随机序列m和M的生成算法实现.docx（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1相关概念随机序列：可以预先确定又不能重复实现的序列伪随机序列：具有随机特性，貌似随机序列的确定序列。n级线性移位寄存器，能产生的最大可能周期是p = 2 -1的序列，这样的序列称为m序列。n级非线性移位寄存器，能产生的最大周期是2的序列，这样的序列称为M序列。图1线性移位寄存器线性移位寄存器递推公式线性移位寄存器的特征方程式/(x) = Co + qx+ + cnxn = Zqx，ci 取值为 0 或 1z=0定义若一个次多项式/(x)满意下列条件：1 1) /(X)为既约多项式(即不能分解因式的多项式)； f(x)可整除(xP+1), p=2n-l;/(x)除不尽俨+1), qpo则称/(
2、x)为本原多项式。定理 线性反馈移位寄存器能产生m序列的充要条件为：反馈移位寄存器的特征多项式为 本原多项式。2 Gb(2)上本原多项式的实现算法二元域GR2)上的本原多项式由于产生伪随机序列的反馈移位寄存器，其特征多项式系数C的取值为。或1,因此所查找的本原多项式为GFQ)上的多项式。在二元域内不行以分解因式的多项式称为既约多项式，和一般代数一样，对于多项式/(e) = 0,则称。为多项式的根。由抽象代数理论可以证明，若a是n次本原多项式/(x)的根，则集合方=0,1,2*-2可构成一个有限的扩域G/(2)。/中的任一元素都可表示为+qa + 4,这样n个重量的有序序列，4，o)就可表示产中
3、的任一元素。若既约多项式/(x)的根能够形成扩域G/(2)，则该多项式是本原多项式，否则不是本原 多项式。2.1 二元域Gb(2)上的本原多项式算法实现Gb(2)上n次多项式的通式为/(x) = +an_xxnx +an_2xn2 -.ax + a,系数是二元域上的元素(0,1)既约多项式既不能整除X/ + 1,。和1不行能是/(x)的根，即。o=l,/(x)的项数肯定为 奇数。止匕外，一个既约多项式是否能形成G尸(2)，从而推断它是否为本原多项式。N次多项式 的扩域，其中，a肯定在扩域中，需要推断的是优用，/”-2是否也在扩域 中，从而形成全部扩域G/(2)，若在，则该n次既约多项式是本原多
4、项式，否则不是。(1)给定二元多项式一2+ “ 2%+.qx + 4o,一2+ “ 2%+.qx + 4o,“0=1设a是f(x)扩域中的一个元素，且f(Q)=0则有:+a.6r+l (1) 11-1 1(2)从优开头，计算。的连续幕。在计算过程中，当遇到a的累次为n时，将(1)代入, 始终计算到。22 (形成gf(2D),再计算。2匕。若则证明了能被x21+l整 除，而不能整除/+1(42-1),判定为本原多项式。在计算。的连续幕过程中，若(g2-1),则证明/(幻能被7+1整除，判定为非本原多项式，停止计算。在计算机实现时，n个重量的有序序列(凡一，四,4)与a的任一连续累有着一一对应的
5、关系，可以用有序序列(_,%,4)来表示a的任一连续幕。用(4_/，。/,唐)来 表示，。用(氏, 四,%)来表示，则可用(%_八 %7,4/)左移一位来实现， 若移位前最高位%j=1,表示消失了 a,则的有序序列表示为42+%,%油+琮)，加法为模2相加，这样可以得到a的连续累。在计算过程中，若旌=1 (q2-1),则判定为非本原多项式。若4(q2-1)都不 为1,且a?为1,则判定了(%)为本原多项式。图2查找本原多项式总流程图图3推断当前多项式是否为本原多项式流程图m序列实现本原多项式系数可确定反馈规律M序列实现M序列是一种非线性的伪随机序列，是由非线性移位寄存器产生的码长为2的周期序列。其构造方法，只要在m序列适当的位置插入一个0状态，即可完成码长为2；的m序列向码长为2的M序列的转换。其反馈规律/（4程 乙）=力（5， Z）+ Z./一2一 %，即