線性移位寄放器實(shí)現(xiàn)產(chǎn)生偽隨機(jī)數(shù)M序列

本文格式為Word版，下載可任意編輯——線性移位寄放器實(shí)現(xiàn)產(chǎn)生偽隨機(jī)數(shù)M序列線性反饋移位寄放器實(shí)現(xiàn)產(chǎn)生偽隨機(jī)數(shù)M序列

在CN03平臺上，主要表達(dá)為Random功能的實(shí)現(xiàn)。

什么是線性反饋移位寄放器？

數(shù)學(xué)解釋這里就不作介紹了，這里我們主要理解兩個(gè)詞語就行，一個(gè)是線性，它是指量與量之間的一種按比例、成直線的關(guān)系。這里面有一點(diǎn)點(diǎn)的數(shù)學(xué)知識，就是說在ai∈(0,1)的存儲單元，ai的個(gè)數(shù)表示為反饋移位寄放器的級，在某一個(gè)時(shí)刻，這些寄放器會有一個(gè)狀態(tài)，共有2^n個(gè)狀態(tài)，每個(gè)狀態(tài)對應(yīng)于域GF(2)上的一個(gè)N維向量,用(a1,a2,a3,……an)表示。作為某一個(gè)時(shí)刻的狀態(tài)，可以用一個(gè)函數(shù)f(a1,a2,a3…..an)來表示，從而稱為該反饋寄放器的反饋函數(shù)，因此線性的意思，就是指假使這個(gè)反饋函數(shù)是a1,a2,a3….an的線性函數(shù)，那么這個(gè)反饋移位寄放器，就叫做線性反饋移位寄放器，譬如f(a1,a2,a3,…an)=kna1⊕kn-1a2⊕….⊕k2an-1⊕k1an,其中系數(shù)ki∈{0，1}i=(1,2,3,…,n)。

另外一個(gè)詞，就是反饋，這個(gè)詞在我理解，就是說需要獲得下一個(gè)狀態(tài)就需要通過獲得一個(gè)反饋值來實(shí)現(xiàn)。這個(gè)反饋的值可以在接下來的兩種實(shí)現(xiàn)LFSR的方式的解釋過程中得到更深刻的理解。

為什么要使用線性反饋移位寄放器？

使用線性反饋移位寄放器的作用：

在好多領(lǐng)域上都有使用到LFSR，譬如說密碼學(xué)、白噪聲，還有我們這里的隨機(jī)功能實(shí)現(xiàn)，之所以把它使用到我們的radio的隨機(jī)功能里面，除了它可以產(chǎn)生偽隨機(jī)數(shù)序列實(shí)現(xiàn)隨機(jī)播放功能之外，更重要的是我們利用了它的兩個(gè)特點(diǎn)。其

一，只需要在代碼中開拓幾個(gè)byte的位置，就能夠?qū)崿F(xiàn)隨機(jī)序列的產(chǎn)生，需要的空間很少。其二，是它的記憶功能，我們在隨機(jī)的功能里面，選擇了下一曲，則上一曲可以通過調(diào)整抽頭數(shù)的序列來從新獲得，而不需要開拓空間進(jìn)行存儲。

怎樣產(chǎn)生偽隨機(jī)數(shù)M序列？

M序列的意思就是最大序列，專業(yè)點(diǎn)來說就是周期，就是這些不同的偽隨機(jī)數(shù)在什么時(shí)候才會回到初始的輸入狀態(tài)，M序列的最大值為2^n-1，由于全0的初始狀態(tài)不起作用，所以不能以全0的狀態(tài)作為初始輸入。M序列就是我們在隨機(jī)功能中獲得的那個(gè)隨機(jī)播放的序列。它有些很好的特性：

1、通過反饋抽頭數(shù)可以獲得與之前輸出的值的輸入值，這也是我們所說的記

憶功能。

2、這些給定的反饋抽頭數(shù)永遠(yuǎn)都是偶數(shù)的，而且只包括最高位，不包括最低

位。

3、還有另外一些特征，這里就不一一列出(這些規(guī)律的東西，我們只需要理解

我們用到的)。

兩種LFSR的產(chǎn)生形式

這里有兩種LFSR的實(shí)現(xiàn)方式，伽羅瓦(Galois)和斐波那契(Fibonacci)兩種形式，也有人稱為外部(External)執(zhí)行方式和內(nèi)部(Internal)執(zhí)行方式。所以這兩種方式也是有著本質(zhì)的區(qū)別的。1、伽羅瓦方式(Internal)

如下圖

(GaloisImplementation)

從圖中我們可以看到Galois方式的一些特征，其中包括數(shù)據(jù)的方向從左至右而反饋線路則是由右至左的。其中X^0項(xiàng)(本原多項(xiàng)式里面的〞1〞這一項(xiàng))，作為起始項(xiàng)。依照本原多項(xiàng)式所指示的，確定異或門(XOR)在移位寄放器電路上的位置。如上圖中的X^4.因此Galois方式也有人稱它為線內(nèi)或模類型(M-型)LFSR.2、斐波那契方式(External)如下圖

(Fibonacciimplementation)

從圖中我們可以看到Fibonacci方式的數(shù)學(xué)流向和反饋形式是恰好跟Galois方式相反的，依照本原多項(xiàng)式，其中的X^0這一項(xiàng)則作為最終一項(xiàng)，這里只需要一個(gè)XOR門，將本原多項(xiàng)式中所給出的taps來設(shè)定它的異或方式。因此Fibonacci方式也被叫做線外或者簡型(S-型)LFSR.

代碼是怎么通過這個(gè)原來實(shí)現(xiàn)偽隨機(jī)數(shù)M序列的產(chǎn)生過程的？

下面來分析一下CN03的隨機(jī)功能代碼實(shí)現(xiàn)的過程：對于Random_mode.c1、Random_Initialise(void)

這里并不涉及到LFSR部分，其中最重要的是理解seed,就是隨機(jī)數(shù)的種子，它是通過SYS_TICK_VALUE來獲得的，也就是說，在系統(tǒng)運(yùn)行的到某某時(shí)刻的時(shí)候，假使接到產(chǎn)生隨機(jī)序列的命令，則獲取當(dāng)前的系統(tǒng)時(shí)刻作為seed，這里具有一定的隨機(jī)性。

獲得了隨機(jī)的seed之后，我們看到它調(diào)用了InitialiseBitSwap(seed)。2、InitialiseBitSwap(unsignedintSeed)voidInitialiseBitSwap(unsignedintSeed){…….

for(…)//先活動一個(gè)初始數(shù)組，簡單的賦值過程

last_bit_swap_array[BitSwapCounter]=bit_swap_array[BitSwapCounter];…….

while(!LFSR_BitSwap)

{if(Seed)//在確保LFSR的初始輸入是隨機(jī)數(shù)的同時(shí)，也要確保它不為0

{//初始狀態(tài)為0的時(shí)候，整個(gè)線性反饋移位的過程無論怎么操作都只有全0

的狀態(tài)

LFSR_BitSwap=SeedSeed=Seed>>1;}else{

LFSR_BitSwap=1;}}for(….){do{

if(LFSR_BitSwap

//這句代碼是整個(gè)程序里面最為重要的已經(jīng)代碼，它表達(dá)了Galois方式的代碼實(shí)//現(xiàn)過程，跟進(jìn)所提供的taps，我們可以把這句代碼理解為in-line的處理過程，//先移位，然后跟進(jìn)給出的taps對相應(yīng)的