m序列笔记 - 图文

m序列发生器读书笔记1

一．伪随机序列 1． 研究背景

2．发展历史

3.应用及其意义

m序列发生器读书笔记2

二．m序列

1． 概念

由线性反馈移位寄存器产生的周期最长的序列。它是由带线性反馈的移存器产生的周期最长的一种序列,是多级移位寄存器或其他延迟元件通过线性反馈产生的最长的码序列。 2． 产生原理

一般来说,在一个n级的二进制移位寄存器发生器中，所能产生的最大长度的码序周期为2n?1。以m=4为例,若其初始状态为(a3,a2,a1,a0)?(1,0,0,0),,则在移位一次时,由a3和a0模2相加产生新的输入a4?1?0?1,新的状态变为(a3,a2,a1,a0)?(1,1,0,0),这样移位15次后又回到初始状态,但若初始状态为(0,0,0,0),则移位后得到地全是0状态,这说意味

4着在这种反馈中要避免出现全0的状态.在4级移存器共有2?16种不同状态,除全0状态

n以外还有15种可用.即由任何4级反馈移存器产生的序列的周期最长为15,满足2?1(当n为4时).

m序列发生器读书笔记3

图1:m序列的产生举例：4级m序列产生器及其状态

图2中，ai (i = 0 – n) － 移存器状态。ai = 0或1。 ci －反馈状态。ci = 0表示反馈线断开，ci = 1表示反馈线连通。

如图2中示出的一个一般的纯属反馈移存器的组成,反馈线的连接状态用ci表示,ci?1表示此线接通(参加反馈),ci?0表示断开,反馈线的接线状态不同,就可能以改变此移存器序列的周期.

为了产生m序列, 必须确定其特征多项式, 以此确定线性反馈移位寄存器的反馈结构, n 级线性反馈移位寄存器的特征方程定义为：

其中ci( i= 1, 2, ??, n) 根据m序列周期的不同, 取值为0 或1。此特征多项式又称本原多项式, n≤20 的本原多项式如表1 所示:

此外, 本原多项式f ( x ) 的反多项式也是本原多项式, 反多项式的定义为:

因为ci( i= 1, 2, ??, n) 只取0或1值, 故上式可写成:

其中d i( i= 1, 2, ??, n) 也取0 或1 值, 因此按这两种本原多式构成的线性反馈移位器都可

以产生m 序列。例如要产生周期为7( = 23- 1) 的m 序列, 就可用3 级线性反馈移位寄存器 来实现, 由表1 可知, 当n= 3 时的本原多项式为:

由上式可确定3 级线性反馈移位寄存器的反馈结构, 如图3 所示, 自启动的3 级线性反馈 移位寄存器逻辑图, 第1 个和第3 个寄存器输出参加反馈。

m序列发生器读书笔记4

的Q3 端输出信号, 即为m 序列。假设初始状态为: Q 1Q2Q3= b2b1b0, 则有: V 0 = b0 由图3 可知, 反馈方程为: ，令D1= b3 , 当第一个移位脉冲作用后, 移位寄存器状态为:Q1Q2Q3= b3b2b1 , 此时有: V0 = b1

同理, 第二个移位脉冲作用后, 移位寄存器状态为: Q1Q 2Q3= b4b3b2 , 这样, 随着时钟脉冲的不断输入, 在B 3 输出端Q3 输出序列为b0b1b2??, 这个序列满足递归关系:

bk = bk- 1 bk- 3

假设初始状态为: Q1Q2Q 3= 111 时, 随着时钟脉冲不断输入, 移位寄存器的状态如表2 所示。 输入序列: V0 = 11101001110100??

若初始状态不同, 所得到序列只是初相位不同, 是( 9) 式序列左( 或右) 移若干位所得到 的移位序列, 假如若初始状态为Q1Q 2Q3= 001, 则有: V0 = 10011101001110??

它是( 9) 式序列向左移4 位, 并去掉前4 位所得到的m 序列, 状态如图4 所示。 软件设计流程图

m序列发生器读书笔记5

3． 性质

n

a) 均衡性： 在m序列一个周期N=2-1内“1”和“0”的码元数大致相等,“0”出现

n-1n-1

2-1 次，“1”出现2次 (即“1”比“0”只多一个) 。 b) 游程分布：游程是指序列中取值相同的一段元素。并把这段元素的个数称为游程长

度。例如，

在上面的一个周期中，共有8个游程，其中长度为4的游程有1个，即“1111”；长度为3的游程有1个，即“000”；长度为2的游程有两个，即“11”和“00”；长度为1的游程有4个，即两个“1”和两个“0”。一般说来，一个周期P=2n-1内,共有2n-1个游程,其中长度为1(单“1”,或单“0”,)的游程占总游程的1/2,长度为2(“11”或“00”)的游程占总游程的1/4,长度为3(“111”或“000”)的游程占总游程的1/8,长度为k的游程占总游程的1/2k，只有一个包含(n一l)个“0”的游程,也只有一个包含n个“1”的游程。

c) 移位相加特性: 一个m序列Mp与其经任意次迟延移位产生的另一个不同序列

Mr模2相加,得到的仍是Mp的某次迟延移位序列Ms,即满足Mp?Mr?Ms. 现以一个m=7的m序列为例子,设Mp的一个周期为1110010,另一个序列Mr是Mp向右移位一次的结果,即Mr的一介相应周期为0111001,这两个序列的模2和为：1110010 ? 0111001 = 1001011上式得出的为Ms的一个相应周期,它与Mp向右移位5次的结果相同

d) 自相关特性: 自相关性和互相关性：m序列和其移位后的序列逐位模2加,所得的

序列还是m序列,只是相位不同。m序列发生器中的对于2个不同相位的m序列,当周期P很大并且τ模P≠0时,这2个序列几乎是正交的。

m序列发生器读书笔记6

e) 周期性

由于m序列有周期性,它的自相关函数也的周期性,周期也是m,即R(j)?R(j?km),当

j?km,k?1,2,?

m序列的最大长度决定于移位寄存器的级数，而码的结构决定于反馈抽头的位置和数量。不同的抽头组合可以产生不同长度和不同结构的码序列。有的抽头组合并不能产生最长周期的序列。对于何种抽头能产生何种长度和结构的码序列，已经进行了大量的研究工作。现在已经得到3 --- 100级m序列发生器的连接图和所产生的m序列的结构。 f) 功率谱密度:功率谱密度和自相关系数构成一对傅里叶变换。求出如下：

由于当m大时，m序列的均衡性、游程分布、自相关特性和功率谱密度等都近似白噪声的特性，但是它又有规律，可以重复产生，所以m序列属于一种伪噪声序列。

4． 应用

伪随机信号在雷达、遥控、遥测、通信加密和无线电测量系统领域有着广泛的应用。利用VHDL语言进行软件编程，通过EDA设计软件对程序编译、优化、综合、仿真、适配，最后将生成的网表文件配置于制定的目标芯片中，可以实现不同序列长度的伪随机信号发生器。 作为最大长度线性移位寄存器序列（简称ｍ序列）是一类重要的伪随机序列， 它最早用于扩频通信，也是目前研究最多的伪随机序列。近几十年来，研究者们又 提出了许多扩频序列。１９６７年R·Gold提出了Gold序列，它具有良好的相关特性，序列数远远多于ｍ序列，便于扩频多址通信。近年来，利用非线性动态系统混沌现象产生的类似随机特性产生了混沌扩频序列，正交序列在同步码分多 址系统中得到了应用。例如：目前IS95标准中使用的PN序列就是m序列，同时m序列还是构成其他序列码的基础，如在WCDMA中采用的GOLD码就是由2个m序列相加而成的。此外m序列又有较好的密码学性质，用在密码学和保密通信中，即用来产生序列密码。3 G及3 G移动通信技术的特征之一是码分多址即CDMA，码是CDMA码分的基础。这里的码就是伪随机码，简称PN码。这是因为伪随机序列（Pseudonoise Sequenec）具有类似于随机信号的一些统计特性，但又是有规律的，容易产生和复制。也正是源于系统中一般都采用伪随机序列，在扩频通信系统中也把扩频序列叫作伪随机序列（即PN码）。PN码的选择作为3 G移动通信的关键技术之一直接影响CDMA系统

m序列发生器读书笔记7

的质量、抗干扰能力等。目前IS95标准中使用的PN序列就是m序列。 三．芯片介绍

1． 移位寄存器的原理

移位寄存器可分为单向移位寄存器（单向左移，单向右移）双位移位存寄器寄存器。 a.4位右移寄存器

1． 原理：单向移位寄存器由4个维持阻塞的D触发器组成。4个D触发器共用一个时钟脉

冲信号，因此为同步时序逻辑电路。数码由最左边的FF0的DI端串行输入

由于D触发器的驱动方程为：Q=D

故 D0=DI，D1=Q0，D2=Q1，D3=Q2 时钟方程：CP0=CP1=CP2=CP3=CP

每一个触发器的输出→其右边触发器的输入，则对应每一个CP上升沿，数据右移一位。

n

n

n

n+1

图1-1 移位寄存器的右移

图 1-2 右移寄存器的时序图

图1-3 移位寄存器的左移

m序列发生器读书笔记8

b.4位左移寄存器 161514131211109VDDQ0Q1Q2Q3CPFF3S1S0原理：数码由最右边的的 端串行输入。每一个触发器的输出→其左边触发器的输入，则对应每一个CP上升沿，数据左移一位。

CC40194(74LS194) 时钟方程：CP0=CP1=CP2=CP3=CP

c. 典型的移位寄存器D3 CR SR D0 D1 D2 1 2 3 4 5 6 (1)74LS194的概述 SL VSS 7 8 74LS194是一种典型的中规模集成移位寄存器。它

有4个RS触发器和一些门电路所构成。图2-1为它的管脚图。74LS194（4位双向移位寄存器）是一种功能很强的通用寄存器，它的具体逻辑功能由管脚9和管脚10的S0，S1来确定。它具有并行输入、并行输出、左移和右移及保持等五个功能。

74LS194共有16个管脚，其中D0、D1、D2、D3为并行数据输入端；Q0、Q1、Q2、Q3为4个触发器输出端；SR为右移串行输入端；SL为左移串行输入端；S0、S1为操作模式控制端；CR为直接无条件清零端；CP为时钟脉冲输入端。

当S0S1=00，为状态保持；S0S1=01为数据右移；S0S1=10为数据左移；S0S1=11为并行送数。此外， 清除功能共5个功能。这些功能的实现是由逻辑图中的门电路来保证的。

m序列发生器读书笔记9

表 2-1 74LS194 功能表

(2)74LS194移位寄存器的应用

移位寄存器应用很广，可构成移位寄存器型计数器：顺序脉冲发生器；可用数据转换，即把串行数据转换为并行数据，或把并行数据转换为串行数据等。

(1) 在数据传送体系转换中的应用。数字系统中的数据传送体系有两种，包括串行传送

体系和并行传送体系。 串行传送体系：即每一节拍只传送一位信息，N位数据需要N个节拍才能传送出去； 并行传送体系：一个节拍同时传送N位数据

在数字系统中，两种传送体系均存在，如计算机主机对信息的处理和加工是并行传送数据的，而信息的传播是串行传送数据的，因此存在两种数据传送体系的转换

? 串行∕并行转换器 ：

在数字系统中，信息的传播通常是串行的，而处理和加工往往是并行的，因此经常要进行输入、输出的串、并转换。

串行∕并行转换器是指串行输入的数码，经转换电路之后变换成并行输出，用二片74LS194四位双向移位句寄存器组成的七位串行∕并行数据转。转换电路如图2-2所示，其转换过程的状态变化如表2-2所示。

具体的转换过程是：串行数据D6…D 0从SR端输入（低位D0先入），并行数据从Q1~Q7输出，表示转换结束的标志码0加在第一片的D0端，其他并行输入端接1。清0启动后，Q8=0，因此S1S0=01，第一个CP是74LS194完成预置操作。

例如，并行输入数据0111111送入Q1~Q8，由于此时Q8=1，S1S0=01，故以后的CP均实现右移操作，经过七次右移后，七位串行码全部移入移存器。此时Q1~Q7 =D6~D 0，且转换结束标志码已到达Q8，表示转换结束，此刻可读出并行数据。由于Q8=0，S1S0再次等于11，因此第9个CP使移位寄存器再次预置数，并重复上述过程。

m序列发生器读书笔记10

图2-2 七位串入-并处转换电路图

表2-2 七位串入-并处状态表

? 七位并入—串出转换电路

图2-3为它的转换电路图，其转换过程的状态变化如表2-3所示 具体的转换过程是： 工作时ST = 0首先使启动信号，则两片74LS194的S1S0=11，第一个CP来到后执行送数操作，Q1~Q7=0d1d2d3d4d5d6d7，且2门输出位1。启动ST =1，1门输出为0，S1S0=01，移存器执行右移操作，经过七次右移后Q0Q1Q2~Q7=11111110,七位并入代码d1~d7全部从Q7串行输出。此时由于Q1~Q6全为1，1门输出为0（表示转换结束），使S1S0=11，第九个CP后，移存器又重新置数，并重复上述过程。

图2-3 七位并入-串出转换电路

m序列发生器读书笔记11

表2-3 七位并入-串出状态表

(2) 组成移位型计数器。

所谓移位型计数器，就是以移位寄存器为主体构成的同步计数器，它的状态迁移关系除第一级外必须具有移位功能，而第一即可根据需要移进“0”或者“1”。所以，这类计数器的设计，只需对第一级进行设计，而其他各级维持移位功能。 （3）74LS164

如下图

m序列发生器读书笔记12

四．FPGA及VHDL的介绍 1、 FPGA

FPGA（Field－Programmable Gate Array），即现场可编程门阵列，它是在PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。 (1)FPGA工作原理

FPGA采用了逻辑单元阵列LCA（Logic Cell Array）这样一个概念，内部包括可配置逻辑模块CLB（Configurable Logic Block）、输出输入模块IOB（Input Output Block）和内部连线（Interconnect）三个部分。 现场可编程门阵列（FPGA）是可编程器件。与传统逻辑电路和门阵列（如PAL，GAL及CPLD器件）相比，FPGA具有不同的结构，FPGA利用小型查找表（16×1RAM）来实现组合逻辑，每个查找表连接到一个D触发器的输入端，触发器再来驱动其他逻辑电路或驱动I/O，由此构成了即可实现组合逻辑功能又可实现时序逻辑功能的基本逻辑单元模块，这些模块间利用金属连线互相连接或连接到I/O模块。FPGA的逻辑是通过向内部静态存储单元加载编程数据来实现的，存储在存储器单元中的值决定了逻辑单元的逻辑功能以及各模块之间或模块与I/O间的联接方式,并最终决定了FPGA所能实现的功能, FPGA允许无限次的编程. （2）FPGA的基本特点

1）采用FPGA设计ASIC电路(专用集成电路)，用户不需要投片生产，就能得到合用的芯片。

2）FPGA可做其它全定制或半定制ASIC电路的中试样片。 3）FPGA内部有丰富的触发器和I/O引脚。

4）FPGA是ASIC电路中设计周期最短、开发费用最低、风险最小的器件之一。 5) FPGA采用高速CMOS工艺，功耗低，可以与CMOS、TTL电平兼容。

可以说，FPGA芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。 FPGA是由存放在片内RAM中的程序来设置其工作状态的，因此，工作时需要对片内的RAM进行编程。用户可以根据不同的配置模式，采用不同的编程方式。

加电时，FPGA芯片将EPROM中数据读入片内编程RAM中，配置完成后，FPGA进入工作状态。掉电后，FPGA恢复成白片，内部逻辑关系消失，因此，FPGA能够反复

m序列发生器读书笔记13

使用。FPGA的编程无须专用的FPGA编程器，只须用通用的EPROM、PROM编程器即可。当需要修改FPGA功能时，只需换一片EPROM即可。这样，同一片FPGA，不同的编程数据，可以产生不同的电路功能。因此，FPGA的使用非常灵活。 2、 VHDL

（1）VHDL简介

VHDL语言是一种用于电路设计的高级语言。它在80年代的后期出现。最初是由美国国防部开发出来供美军用来提高设计的可靠性和缩减开发周期的一种使用范围较小的设计语言 。

VHDL翻译成中文就是超高速集成电路硬件描述语言，主要是应用在数字电路的设计中。目前，它在中国的应用多数是用在FPGA/CPLD/EPLD的设计中。当然在一些实力较为雄厚的单位，它也被用来设计ASIC。

VHDL主要用于描述数字系统的结构，行为，功能和接口。除了含有许多具有硬件特征的语句外，VHDL的语言形式、描述风格以及语法是十分类似于一般的计算机高级语言。VHDL的程序结构特点是将一项工程设计，或称设计实体（可以是一个元件，一个电路模块或一个系统）分成外部（或称可视部分,及端口)和内部（或称不可视部分），既涉及实体的内部功能和算法完成部分。在对一个设计实体定义了外部界面后，一旦其内部开发完成后，其他的设计就可以直接调用这个实体。这种将设计实体分成内外部分的概念是VHDL系统设计的基本点。 （2）特点

功能强大、设计灵活

VHDL具有功能强大的语言结构，可以用简洁明确的源代码来描述复杂的逻辑控制。它具有多层次的设计描述功能，层层细化，最后可直接生成电路级描述。VHDL支持同步电路、异步电路和随机电路的设计，这是其他硬件描述语言所不能比拟的。VHDL还支持各种设计方法，既支持自底向上的设计，又支持自顶向下的设计；既支持模块化设计，又支持层次化设计。 支持广泛、易于修改

由于VHDL已经成为IEEE标准所规范的硬件描述语言，目前大多数EDA工具几乎都支持VHDL，这为VHDL的进一步推广和广泛应用奠定了基础。在硬件电路设计过程中，主要的设计文件是用VHDL编写的源代码，因为VHDL易读和结构化，所以易于修改设计。

强大的系统硬件描述能力

VHDL具有多层次的设计描述功能，既可以描述系统级电路，又可以描述门级电路。而描述既可以采用行为描述、寄存器传输描述或结构描述，也可以采用三者混合的混合级描述。另外，VHDL支持惯性延迟和传输延迟，还可以准确地建立硬件电路模型。VHDL支持预定义的和自定义的数据类型，给硬件描述带来较大的自由度，使设计人员能够方便地创建高层次的系统模型。 很强的移植能力

VHDL是一种标准化的硬件描述语言，同一个设计描述可以被不同的工具所支持，使得设计描述的移植成为可能。 易于共享和复用

VHDL采用基于库（Library）的设计方法，可以建立各种可再次利用的模块。这些模块可以预先设计或使用以前设计中的存档模块，将这些模块存放到库中，就可以在以后的设计中进行复用，可以使设计成果在设计人员之间进行交流和共享，减少硬件电路设计。

m序列发生器读书笔记14

（3）优势

I 与其他的硬件描述语言相比，VHDL具有更强的行为描述能力，从而决定了他成为系统设计领域最佳的硬件描述语言。强大的行为描述能力是避开具体的器件结构，从逻辑行为上描述和设计大规模电子系统的重要保证。

II VHDL丰富的仿真语句和库函数，使得在任何大系统的设计早期就能查验设计系统的功能可行性，随时可对设计进行仿真模拟。

III VHDL语句的行为描述能力和程序结构决定了他具有支持大规模设计的分解和已有设计的再利用功能。符合市场需求的大规模系统高效，高速的完成必须有多人甚至多个代发组共同并行工作才能实现。

IV 对于用VHDL完成的一个确定的设计，可以利用EDA工具进行逻辑综合和优化，并自动的把VHDL描述设计转变成门级网表。

V VHDL对设计的描述具有相对独立性，设计者可以不懂硬件的结构，也不必管理最终设计实现的目标器件是什么，而进行独立的设计。

m序列发生器读书笔记15

A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

Mostly used linear function of single bits is XOR, thus normally it is a shift register whose input bit is driven by the exclusive-or (XOR) of some bits of the overall shift register value. The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the stream of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle. However, an LFSR with a well-chosen feedback function can produce a sequence of bits which appears random and which has a very long cycle.

Applications of LFSRs include generating pseudo-random numbers, pseudo-noise

sequences, fast digital counters, and whitening sequences. Both hardware and software implementations of LFSRs are common.

The mathematics of a cyclic redundancy check, used to provide a quick check against transmission errors, are closely related to those of an LFSR.

m序列发生器读书笔记16

The bit positions that affect the next state are called the taps. In the diagram the taps are [16,14,13,11]. The rightmost bit of the LFSR is called the output bit. The taps are XOR'd sequentially with the output bit and then fed back into the leftmost bit. The sequence of bits in the rightmost position is called the output stream.

? ?

?

The bits in the LFSR state which influence the input are called taps (white in the diagram).

A maximum-length LFSR produces an m-sequence (i.e. it cycles through all

possible 2n ? 1 states within the shift register except the state where all bits are zero), unless it contains all zeros, in which case it will never change.

As an alternative to the XOR based feedback in an LFSR, one can also use XNOR.[1] This function is an affine map, not strictly a linear map, but it results in an equivalent polynomial counter whose state of this counter is the complement of the state of an LFSR. A state with all ones is illegal when using an XNOR feedback, in the same way as a state with all zeroes is illegal when using XOR. This state is considered illegal because the counter would remain \

The sequence of numbers generated by an LFSR or its XNOR counterpart can be

considered a binary numeral system just as valid as Gray code or the natural binary code. The arrangement of taps for feedback in an LFSR can be expressed in finite field

arithmetic as a polynomial mod 2. This means that the coefficients of the polynomial must be 1's or 0's. This is called the feedback polynomial or characteristic polynomial. For example, if the taps are at the 16th, 14th, 13th and 11th bits (as shown), the feedback polynomial is

The 'one' in the polynomial does not correspond to a tap — it corresponds to the input to the first bit (i.e. x0, which is equivalent to 1). The powers of the terms represent the tapped

m序列发生器读书笔记17

bits, counting from the left. The first and last bits are always connected as an input and output tap respectively.

Tables of primitive polynomials from which maximum-length LFSRs can be constructed are given below and in the references.

? ? ? ?

The LFSR will only be maximum-length if the number of taps is even; just 2 or 4 taps can suffice even for extremely long sequences.

The set of taps — taken all together, not pairwise (i.e. as pairs of elements) — must be relatively prime. In other words, there must be no common divisor to all taps.

There can be more than one maximum-length tap sequence for a given LFSR length

Once one maximum-length tap sequence has been found, another automatically follows. If the tap sequence, in an n-bit LFSR, is [n, A, B, C, 0], where the 0 corresponds to the x0 = 1 term, then the corresponding 'mirror' sequence is [n, n ? C, n ? B, n ? A, 0]. So the tap sequence [32, 7, 3, 2, 0] has as its counterpart [32, 30, 29, 25, 0]. Both give a maximum-length sequence.

Some example C code is below: #include

uint16_t lfsr = 0xACE1u; unsigned bit;

unsigned period = 0; do {

/* taps: 16 14 13 11; characteristic polynomial: x^16 + x^14 + x^13 + x^11 + 1 */ bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1; lfsr = (lfsr >> 1) | (bit << 15); ++period;

} while(lfsr != 0xACE1u);

The above code assumes the most significant bit of lfsr is bit 1, and the least significant bit is bit 16.

As well as Fibonacci, this LFSR configuration is also known as standard, many-to-one or external XOR gates. LFSR has an alternative configuration.

Named after the French mathematician évariste Galois, an LFSR in Galois configuration, which is also known as modular, internal XORs as well as one-to-many LFSR, is an alternate structure that can generate the same output stream as a conventional LFSR.[2]

m序列发生器读书笔记18

In the Galois configuration, when the system is clocked, bits that are not taps are shifted one position to the right unchanged. The taps, on the other hand, are XOR'd with the output bit before they are stored in the next position. The new output bit is the next input bit. The effect of this is that when the output bit is zero all the bits in the register shift to the right unchanged, and the input bit becomes zero. When the output bit is one, the bits in the tap positions all flip (if they are 0, they become 1, and if they are 1, they become 0), and then the entire register is shifted to the right and the input bit becomes 1.

A 16-bit Galois LFSR. The register numbers in white correspond to the same primitive polynomial as the Fibonacci example but are counted in reverse to the shifting direction. This register also cycles through the maximal number of 65535 states excluding the all-zeroes state. The state ACE1 hex shown will be followed by E270 hex.

To generate the same output stream, the order of the taps is the counterpart (see above) of the order for the conventional LFSR, otherwise the stream will be in reverse. Note that the internal state of the LFSR is not necessarily the same. The Galois register shown has the same output stream as the Fibonacci register in the first section.

?

?

Galois LFSRs do not concatenate every tap to produce the new input (the

XOR'ing is done within the LFSR and no XOR gates are run in serial, therefore the propagation times are reduced to that of one XOR rather than a whole chain), thus it is possible for each tap to be computed in parallel, increasing the speed of execution.

In a software implementation of an LFSR, the Galois form is more efficient as the XOR operations can be implemented a word at a time: only the output bit must be examined individually.

Below is a code example of a 32-bit maximal period Galois LFSR that is valid in C: #include uint32_t lfsr = 1; unsigned period = 0; do {

/* taps: 32 31 29 1; characteristic polynomial: x^32 + x^31 + x^29 + x + 1 */ lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xD0000001u); ++period;

} while(lfsr != 1u);

And here is the code for the 16 bit example in the figure #include

uint16_t lfsr = 0xACE1u; unsigned period = 0;

m序列发生器读书笔记19

do {

/* taps: 16 14 13 11; characteristic polynomial: x^16 + x^14 + x^13 + x^11 + 1 */ lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xB400u); ++period;

} while(lfsr != 0xACE1u);

These code examples create a toggle mask to apply to the shifted value using the XOR operator. The mask is created by first removing all but the least significant bit (the output bit) of the current value. This value is then negated (two's complement negation), which creates a value of either all 0s or all 1s, if the output bit is 0 or 1, respectively. By ANDing the result with the tap-value (e.g., 0xB400 in the second example) before applying it as the toggle mask, it acts functionally as a conditional to either apply or not apply the toggle mask based on the output bit. A more explicit but significantly less efficient code example is shown below.

#include

uint16_t lfsr = 0xACE1u; unsigned period = 0; do {

unsigned lsb = lfsr & 1; /* Get lsb (i.e., the output bit). */ lfsr >>= 1; /* Shift register */

if (lsb == 1) /* Only apply toggle mask if output bit is 1. */

lfsr ^= 0xB400u; /* Apply toggle mask, value has 1 at bits corresponding * to taps, 0 elsewhere. */ ++period;

} while(lfsr != 0xACE1u);

Binary Galois LFSRs like the ones shown above can be generalized to any q-ary alphabet {0, 1, ... , q ? 1} (e.g., for binary, q is equal to two, and the alphabet is simply {0, 1}). In this case, the exclusive-or component is generalized to addition modulo-q (note that XOR is addition modulo 2), and the feedback bit (output bit) is multiplied (modulo-q) by a q-ary value which is constant for each specific tap point. Note that this is also a generalization of the binary case, where the feedback is multiplied by either 0 (no feedback, i.e., no tap) or 1 (feedback is present). Given an appropriate tap configuration, such LFSRs can be used to generate Galois fields for arbitrary values of q.

The following table lists maximal-length polynomials for shift-register lengths up to 19. Note that more than one maximal-length polynomial may exist for any given shift-register length.

m序列发生器读书笔记20

?

? ?

Ones and zeroes occur in 'runs'. The output stream 0110100, for example

consists of five runs of lengths 1,2,1,1,2, in order. In one period of a maximal LFSR, 2n ?1 runs occur (for example, a six bit LFSR will have 32 runs). Exactly half of these runs will be one bit long, a quarter will be two bits long, up to a single run of zeroes n ? 1 bits long, and a single run of ones n bits long. This distribution almost equals the statistical expectation value for a truly random sequence. However, the probability of finding exactly this distribution in a sample of a truly random sequence is rather low.

LFSR output streams are deterministic. If you know the present state, you can predict the next state. This is not possible with truly random events.

The output stream is reversible; an LFSR with mirrored taps will cycle through the output sequence in reverse order.

LFSRs can be implemented in hardware, and this makes them useful in applications that require very fast generation of a pseudo-random sequence, such as direct-sequence spread spectrum radio. LFSRs have also been used for generating an approximation of white noise in various programmable sound generators.

m序列发生器读书笔记21

Uses as counters

The repeating sequence of states of an LFSR allows it to be used as a clock divider, or as a counter when a non-binary sequence is acceptable as is often the case where computer index or framing locations need to be machine-readable.[3] LFSR counters have simpler feedback logic than natural binary counters or Gray code counters, and therefore can operate at higher clock rates. However it is necessary to ensure that the LFSR never enters an all-zeros state, for example by presetting it at start-up to any other state in the sequence. The table of primitive polynomials shows how LFSRs can be arranged in Fibonacci or Galois form to give maximal periods. One can obtain any other period by adding to an LFSR that has a longer period some logic that shortens the sequence by skipping some states. Uses in cryptography

LFSRs have long been used as pseudo-random number generators for use in stream ciphers (especially in military cryptography), due to the ease of construction from simple electromechanical or electronic circuits, long periods, and very uniformly distributed

output streams. However, an LFSR is a linear system, leading to fairly easy cryptanalysis. For example, given a stretch of known plaintext and corresponding ciphertext, an attacker can intercept and recover a stretch of LFSR output stream used in the system described, and from that stretch of the output stream can construct an LFSR of minimal size that simulates the intended receiver by using the Berlekamp-Massey algorithm. This LFSR can then be fed the intercepted stretch of output stream to recover the remaining plaintext. Three general methods are employed to reduce this problem in LFSR-based stream ciphers:

? ? ?

Non-linear combination of several bits from the LFSR state;

Non-linear combination of the output bits of two or more LFSRs (see also: shrinking generator); or

Irregular clocking of the LFSR, as in the alternating step generator.

Important LFSR-based stream ciphers include A5/1 and A5/2, used in GSM cell phones, E0, used in Bluetooth, and the shrinking generator. The A5/2 cipher has been broken and both A5/1 and E0 have serious weaknesses.[4][5] Uses in digital broadcasting and communications Scrambling

To prevent short repeating sequences (e.g., runs of 0's or 1's) from forming spectral lines that may complicate symbol tracking at the receiver or interfere with other transmissions, linear feedback registers are often used to \randomization is removed at the receiver after demodulation. When the LFSR runs at the same rate as the transmitted symbol stream, this technique is referred to as scrambling. When the LFSR runs considerably faster than the symbol stream, expanding the bandwidth of the transmitted signal, this is direct-sequence spread spectrum. Neither scheme should be confused with encryption or encipherment; scrambling and spreading with LFSRs do not protect the information from eavesdropping. They are

m序列发生器读书笔记22

instead used to produce equivalent streams that possess convenient engineering properties to allow for robust and efficient modulation and demodulation. Digital broadcasting systems that use linear feedback registers:

? ? ? ?

ATSC Standards (digital TV transmission system – North America) DAB (Digital Audio Broadcasting system – for radio)

DVB-T (digital TV transmission system – Europe, Australia, parts of Asia) NICAM (digital audio system for television)

Other digital communications systems using LFSRs:

? ? ? ? ? ? ? ? ? ? ?

IBS (INTELSAT business service) IDR (Intermediate Data Rate service) SDI (Serial Digital Interface transmission)

Data transfer over PSTN (according to the ITU-T V-series recommendations) CDMA (Code Division Multiple Access) cellular telephony 100BASE-T2 \

1000BASE-T Ethernet, the most common form of Gigabit Ethernet, scrambles bits using an LFSR

PCI Express 3.0 SATA[6] USB 3.0

IEEE 802.11a scrambles bits using an LFSR

Other uses

The German time signal DCF77, in addition to amplitude keying, employs phase-shift keying driven by a 9-stage LFSR to increase the accuracy of received time and the robustness of the data stream in the presence of noise.[7]

The Global Positioning System uses an LFSR to rapidly transmit a sequence that indicates high-precision relative time offsets. See also

? ? ? ?

Pinwheel

Mersenne twister

Maximum length sequence analog feedback shift register

[edit] References

1. ^ Linear Feedback Shift Registers in Virtex Devices

2. ^ Beker, Henry; Piper, Fred (1982). Cipher Systems: The Protection of Communications. Wiley-Interscience. p. 212.

3. ^ http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf 4. ^ Barkam, Elad; Biham, Eli; Keller, Nathan (2008), Journal of Cryptology 21 (3):

392–429, http://cryptome.org/gsm-crack-bbk.pdf

5. ^ Lu, Yi; Willi Meier; Serge Vaudenay (2005). \

A Practical Attack on Bluetooth Encryption\Crypto 2005 (Santa Barbara,

m序列发生器读书笔记23

California, USA) 3621: 97–117. doi:10.1007/11535218_7.

http://www.terminodes.org/micsPublicationsDetail.php?pubno=1216. 6. ^ Section 9.5 of the SATA Specification, revision 2.6

7. ^ Hetzel, P. (16 March 1988). \

using a pseudo-random phase-shift keying of the carrier\Frequency and Time Forum. Neuchatel. pp. 351–364.

https://www.ptb.de/cms/fileadmin/internet/fachabteilungen/abteilung_4/4.4_zeit_und_frequenz/pdf/5_1988_Hetzel_-_Proc_EFTF_88.pdf. Retrieved 11 October 2011. [edit] External links

?

? ? ? ? ? ? ? ? ? ?

LFSR Reference LFSR theory and implementation, maximal length sequences, and comprehensive feedback tables for lengths from 7 to 16,777,215 (3 to 24 stages), and partial tables for lengths up to 4,294,967,295 (25 to 32 stages).

International Telecommunications Union Recommendation O.151 (August 1992) Maximal Length LFSR table with length from 2 to 67. Pseudo-Random Number Generation Routine

http://www.ece.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html

http://www.quadibloc.com/crypto/co040801.htm Simple explanation of LFSRs for Engineers Feedback terms

General LFSR Theory

An implementation of a cryptographically secure shrinking pseudorandom number generator.

An implementation of LFSR in VHDL.

本文来源：https://www.bwwdw.com/article/85fw.html