Berlekamp-Massey算法.pptx_第1页
Berlekamp-Massey算法.pptx_第2页
Berlekamp-Massey算法.pptx_第3页
Berlekamp-Massey算法.pptx_第4页
Berlekamp-Massey算法.pptx_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、给定有限域（二元域）上的一条长度为N的序列，能够产生该序列的最短的LFSR的级数是多少？其反馈多项式又是什么？,Berlekamp-Massey算法,一、BM算法的理论基础,定义：设 +1 0 1 是一个二元序列，f(x)= =0 是二元域上次数L的多项式，则定义是一个以f(x)为反馈多项式的L级线性反馈移存器，并定义“下一步离差” 是 与上述LFSR生成的二元序列的第n+1项之间的差： = =0 ,定理：设 = 0 1 1 是一个长度为N的二元序列，其线性复杂度为L=L( ),并设也可生成序列 +1 = 0 1 当且仅当下一步离差 = (2)如果 =，则有L( +1 )=L (3)如果 =，

2、记m是长度为 L( ) 且可以生成 的LFSR，则线性反馈移存器就是可以生成 且具有最短级数的LFSR。其中： L=maxN+1-L,L= , 若/2 +1,若/2 并且f(x)=f(x)B(x) 。,二、BM算法的计算步骤,输入：长度为N的二元序列 = 0 1 1 。 输出： （1）序列 的线性复杂度L()且0( )N。 （2）生成序列 的L（ ）级LFSR的反馈多项式f(x)。,Step 1 初始化： 0 ()1, 0 0Step 2 当n, ,(0) 均已求得，且 0 1 记： ()= 0 () + 1 () + () , 0 () =1,再计算： = 0 () + 1 () 1 + (

3、) (1)若 =0，则令： +1 ()= ()， +1 ()= ()(2)若 =1，当 0 = 1 = =0时， 取 +1 ()=1+ +1 , +1 =+1 当有m(0),使得 +1 = +2 = 同时： +1 ()= ()+ (), +1 =max ,+1 Step 3 输出最短线性移存器的反馈多项式f(x)。,求产生周期为7的m序列一个周期：0011101的最短线性移存器。 解：设 0 1 2 3 4 5 6 =0011101,首先取初值 0 =1, 0 =0,则由 0 =0得 0 =1 0 =0从而 1 =1, 1 =0；同理由 1 =0得 0 =1 1 =0，从而 2 =1, 2 =0。 由 2 =1得 2 =1 2 =1，从而根据 0 = 1 = 2 =0知 2 =1+ 2+1 =1+ 3 , 3 =3,实例,第1步,计算 : 3 =1 3 +0 2 +0 1 +1* 0 =1 因为 2 3 ,故m=2，据此 4 = 3 + 32 2 =1+ 3 4 = max 3,3+13 =3 第2步,计算 : 4 =1 4 +1 3 +0 2 +1* 1 =0 5 = 4 =1+ 3 5 = 4 =3,实例,第3步,计算 5 : 5 =1 5 +1 4 +0 3 +1* 2 =0 6 = 5 =1+ 3 6 = 5 =3 第4步,计算

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论