线性移位寄存器实现产生伪随机数M序列.doc

线性反馈移位寄存器实现产生伪随机数M序列-在CN03平台上，主要体现为Random功能的实现。什么是线性反馈移位寄存器？数学解释这里就不作介绍了，这里我们主要理解两个词语就行，一个是线性，它是指量与量之间的一种按比例、成直线的关系。这里面有一点点的数学知识，就是说在ai(0,1)的存储单元，ai的个数表示为反馈移位寄存器的级，在某一个时刻，这些寄存器会有一个状态，共有2n个状态，每个状态对应于域GF(2)上的一个N维向量,用(a1,a2,a3,an)表示。作为某一个时刻的状态，可以用一个函数f(a1,a2,a3.an)来表示，从而称为该反馈寄存器的反馈函数，因此线性的意思，就是指如果这个反馈函数是a1,a2,a3.an的线性函数，那么这个反馈移位寄存器，就叫做线性反馈移位寄存器，比如f(a1,a2,a3,an)=kna1kn-1a2.k2an-1k1an,其中系数ki0，1i=(1,2,3,n)。另外一个词，就是反馈，这个词在我理解，就是说需要获得下一个状态就需要通过获得一个反馈值来实现。这个反馈的值可以在接下来的两种实现LFSR的方式的解释过程中得到更深刻的理解。为什么要使用线性反馈移位寄存器？使用线性反馈移位寄存器的作用：在很多领域上都有使用到LFSR，譬如说密码学、白噪声，还有我们这里的随机功能实现，之所以把它使用到我们的radio的随机功能里面，除了它可以产生伪随机数序列实现随机播放功能之外，更重要的是我们利用了它的两个特点。其一，只需要在代码中开辟几个byte的位置，就能够实现随机序列的产生，需要的空间很少。其二，是它的记忆功能，我们在随机的功能里面，选择了下一曲，则上一曲可以通过调整抽头数的序列来从新获得，而不需要开辟空间进行存储。怎样产生伪随机数M序列？M序列的意思就是最大序列，专业点来说就是周期，就是这些不同的伪随机数在什么时候才会回到初始的输入状态，M序列的最大值为2n-1，因为全0的初始状态不起作用，所以不能以全0的状态作为初始输入。M序列就是我们在随机功能中获得的那个随机播放的序列。它有些很好的特性：1、 通过反馈抽头数可以获得与之前输出的值的输入值，这也是我们所说的记忆功能。2、 这些给定的反馈抽头数永远都是偶数的，而且只包括最高位，不包括最低位。3、 还有另外一些特征，这里就不一一列出(这些规律的东西，我们只需要理解我们用到的)。两种LFSR的产生形式这里有两种LFSR的实现方式，伽罗瓦(Galois)和斐波那契(Fibonacci)两种形式，也有人称为外部(External)执行方式和内部(Internal)执行方式。所以这两种方式也是有着本质的区别的。1、伽罗瓦方式(Internal)如下图 (Galois Implementation)从图中我们可以看到Galois方式的一些特征，其中包括数据的方向从左至右而反馈线路则是由右至左的。其中X0项(本原多项式里面的”1”这一项)，作为起始项。按照本原多项式所指示的，确定异或门(XOR)在移位寄存器电路上的位置。如上图中的X4.因此Galois方式也有人称它为线内或模类型(M-型)LFSR.2、斐波那契方式(External)如下图(Fibonacci implementation)从图中我们可以看到Fibonacci方式的数学流向和反馈形式是恰好跟Galois方式相反的，按照本原多项式，其中的X0这一项则作为最后一项，这里只需要一个XOR门，将本原多项式中所给出的taps来设定它的异或方式。因此Fibonacci方式也被叫做线外或者简型(S-型)LFSR.代码是怎么通过这个原来实现伪随机数M序列的产生过程的？下面来分析一下CN03的随机功能代码实现的过程：对于Random_mode.c 1、Random_Initialise(void)这里并不涉及到LFSR部分，其中最重要的是理解seed,就是随机数的种子，它是通过SYS_TICK_VALUE来获得的，也就是说，在系统运行的到某某时刻的时候，如果接到产生随机序列的命令，则获取当前的系统时刻作为seed，这里具有一定的随机性。获得了随机的seed之后，我们看到它调用了InitialiseBitSwap(seed)。2、InitialiseBitSwap(unsigned int Seed)void InitialiseBitSwap(unsigned int Seed) . for()/先活动一个初始数组，简单的赋值过程 last_bit_swap_arrayBitSwapCounter = bit_swap_arrayBitSwapCounter;. while(!LFSR_BitSwap) if(Seed) /在确保LFSR的初始输入是随机数的同时，也要确保它不为0 /初始状态为0的时候，整个线性反馈移位的过程无论怎么操作都只有全0的状态 LFSR_BitSwap = Seed & 0x1F; Seed = Seed 1; else LFSR_BitSwap = 1; for(.) do if(LFSR_BitSwap & BIT_0)/这个条件是加速处理过程，对奇、偶数分开处/理，也能够增加序列的随机性 LFSR_BitSwap = (LFSR_BitSwap 1) FIVE_STATE_NEXT_LFSR_FEEDBACK_TAPS;/这句代码是整个程序里面最为重要的已经代码，它体现了Galois方式的代码实/现过程，跟进所提供的taps，我们可以把这句代码理解为in-line的处理过程，/先移位，然后跟进给出的taps对相应的为进行异或运算，从而实现了线性反馈/移位的功能。通过对照上图，能够较好地理解这个过程。 else LFSR_BitSwap = (LFSR_BitSwap 1); while(LFSR_BitSwap NUMBER_OF_LFSR_BITS);/确保这个随机数不能够大于确定的数组的个数值 bit_swap_arraylast_bit_swap_arrayBitSwapCounter = (LFSR_BitSwap-1);/获得这个随机数后，将它存到相应的数组里面 4、 BitSwap(unsigned int InputValue)还没有很好地理解这个函数的用意，但是我尝试去屏蔽关于这个函数的调用，并没有影响整个的随机功能。所以，我认为它应该也是一个增加随机性的过程。不过还好进一步理解，有新的进展，会更新到这里。5、 Random_PreviousTrack和Random_NextTrack这两个函数就是产生最后的随机播放曲目的应用。里面的核心代码在第二点里面已经基本上解释完毕，可以参考第二个函数的解释。至于上一曲下一曲的区别，这里要重点说明一下，就是利用了反馈抽头数在M序列上面的应用，在M序列解释的第一个特点中有提及。我们可以看看在头文件random.h里面的定义：#define SIXTEEN_STAGE_NEXT_LFSR_FEEDBACK_TAPS (BIT_15 | BIT_13 | BIT_12 | BIT_10 ) #define SIXTEEN_STAGE_PREV_LFSR_FEEDBACK_TAPS (BIT_0 | BIT_14 | BIT_13 | BIT_11 )抽头数的定义有一定的规律，参照这个规律，可以实现对其他级的选择。小结小结一下这个学习的过程，里面还有两点没有深入地理解：1、 抽头数是怎么来的，通常已经算好了，网上有相关的资源。参考网站：/res