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

1、線性反饋移位寄存器實(shí)現(xiàn)產(chǎn)生偽隨機(jī)數(shù) M 序列在 CN03 平臺(tái)上，主要體現(xiàn)為 Random 功能的實(shí)現(xiàn)。什么是線性反饋移位寄存器？ 數(shù)學(xué)解釋這里就不作介紹了，這里我們主要理解兩個(gè)詞語就行，一個(gè)是線性，它 是指量與量之間的一種按比例、成直線的關(guān)系。這里面有一點(diǎn)點(diǎn)的數(shù)學(xué)知識(shí)，就 是說在ai (0,1)的存儲(chǔ)單元，ai的個(gè)數(shù)表示為反饋移位寄存器的級(jí)，在某一個(gè)時(shí) 刻，這些寄存器會(huì)有一個(gè)狀態(tài)，共有2An個(gè)狀態(tài)，每個(gè)狀態(tài)對(duì)應(yīng)于域 GF(2)上的一個(gè)N維向量，用(a1,a2,a3,an)表示。作為某一個(gè)時(shí)刻的狀態(tài)，可以用一個(gè)函數(shù)f(a1,a2,a3.an)來表示，從而稱為該反饋寄存器的反饋函數(shù)，因此線性的

2、意思，就是指如果這個(gè)反饋函數(shù)是 a1,a2,a3.an的線性函數(shù)，那么這個(gè)反饋移 位寄存器，就叫做線性反饋移位寄存器，比如f(a1,a2,a3,ar)=kna1kn-1a2. k2an-1 k1an,其中系數(shù) ki 0 , 1i=(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)，之所以把它使用到我

3、們的 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ǔ)。 怎樣產(chǎn)生偽隨機(jī)數(shù) M 序列？M 序列的意思就是最大序列，專業(yè)點(diǎn)來說就是周期，就是這些不同的偽隨機(jī)數(shù)在什么時(shí)候才會(huì)回到初始的輸入狀態(tài)，M序列的最大值為25-1 ,因?yàn)槿?的初始狀態(tài)不起作用，所以不能以全 0 的狀態(tài)作為初始輸入。M 序列就是我們在隨機(jī)功能中獲

4、得的那個(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)如下圖X。X4卄rTap Coun

5、tData Flowg(x) = 1 +X4 + X17（Galois Impleme ntatio n）從圖中我們可以看到Galois方式的一些特征，其中包括數(shù)據(jù)的方向從左至右而反 饋線路則是由右至左的。其中 XA0項(xiàng)（本原多項(xiàng)式里面的”這一項(xiàng)），作為起始 項(xiàng)。按照本原多項(xiàng)式所指示的，確定異或門 （XOR）在移位寄存器電路上的位置。 如上圖中的XA4.因此Galois方式也有人稱它為線內(nèi)或模類型（M-型兒FSR.2、斐波那契方式（External）如下圖ci；EJfrIjI,JTap CountIData FlowX16x14x13X11X°LFSR polynomial: g(x

6、) = X14 + X13 + X11 +1(Fib on acci impleme ntati on) 從圖中我們可以看到 Fibonacci 方式的數(shù)學(xué)流向和反饋形式是恰好跟 Galois 方式 相反的，按照本原多項(xiàng)式，其中的 XA0這一項(xiàng)則作為最后一項(xiàng)，這里只需要一個(gè) XOR 門，將本原多項(xiàng)式中所給出的 taps 來設(shè)定它的異或方式。因此 Fibonacci 方式也被叫做線外或者簡型(S-型)L FSR.代碼是怎么通過這個(gè)原來實(shí)現(xiàn)偽隨機(jī)數(shù) M 序列的產(chǎn)生過程的？ 下面來分析一下 CN03 的隨機(jī)功能代碼實(shí)現(xiàn)的過程： 對(duì)于 Random_mode.c1、Random_Initialise(

7、void)這里并不涉及到LFSR部分，其中最重要的是理解seed,就是隨機(jī)數(shù)的種子，它 是通過 SYS_TICK_VALUE 來獲得的，也就是說，在系統(tǒng)運(yùn)行的到某某時(shí)刻的時(shí) 候，如果接到產(chǎn)生隨機(jī)序列的命令，貝S獲取當(dāng)前的系統(tǒng)時(shí)刻作為seed，這里具有一定的隨機(jī)性。獲得了隨機(jī)的 seed 之后，我們看到它調(diào)用了 InitialiseBitSwap(seed) 。2、InitialiseBitSwap(unsigned int Seed)void InitialiseBitSwap(unsigned int Seed)for()先活動(dòng)一個(gè)初始數(shù)組，簡單的賦值過程 last_bit_swap_arr

8、ayBitSwapCounter = bit_swap_arrayBitSwapCounter;while(!LFSR_BitSwap) if(Seed) / 在確保 LFSR 的初始輸入是隨機(jī)數(shù)的同時(shí)，也要確保它不為 0 / 初始狀態(tài)為 0 的時(shí)候，整個(gè)線性反饋移位的過程無論怎么操作都只有全 0 的狀態(tài)LFSR_BitSwap = Seed & 0x1F;Seed = Seed >> 1;elseLFSR_BitSwap = 1;for(.) doif(LFSR_BitSwap & BIT_0)/ 這個(gè)條件是加速處理過程，對(duì)奇、偶數(shù)分開處 /理，也能夠增加序列的隨

9、機(jī)性 LFSR_BitSwap = (LFSR_BitSwap >> 1)八FIVE_STATE_NEXT_LFSR_FEEDBACK_TAPS;/這句代碼是整個(gè)程序里面最為重要的已經(jīng)代碼，它體現(xiàn)了Galois 方式的代碼實(shí)現(xiàn)過程，跟進(jìn)所提供的taps，我們可以把這句代碼理解為in-line的處理過程， /先移位，然后跟進(jìn)給出的 taps 對(duì)相應(yīng)的為進(jìn)行異或運(yùn)算，從而實(shí)現(xiàn)了線性反饋 /移位的功能。通過對(duì)照上圖，能夠較好地理解這個(gè)過程。else LFSR_BitSwap = (LFSR_BitSwap >> 1);while(LFSR_BitSwap > NUMBE

10、R_OF_LFSR_BITS);/ 確保這個(gè)隨機(jī)數(shù)不能 夠大于確定的數(shù)組的個(gè)數(shù)值bit_swap_arraylast_bit_swap_arrayBitSwapCounter = (LFSR_BitSwap-1); /獲得這個(gè)隨機(jī)數(shù)后，將它存到相應(yīng)的數(shù)組里面4 、 BitSwap(unsigned int InputValue) 還沒有很好地理解這個(gè)函數(shù)的用意，但是我嘗試去屏蔽關(guān)于這個(gè)函數(shù)的調(diào)用，并 沒有影響整個(gè)的隨機(jī)功能。所以，我認(rèn)為它應(yīng)該也是一個(gè)增加隨機(jī)性的過程。不 過還好進(jìn)一步理解，有新的進(jìn)展，會(huì)更新到這里。5 、 Random_PreviousTrack 和 Random_NextTr

11、ack 這兩個(gè)函數(shù)就是產(chǎn)生最后的隨機(jī)播放曲目的應(yīng)用。里面的核心代碼在第二點(diǎn)里面 已經(jīng)基本上解釋完畢，可以參考第二個(gè)函數(shù)的解釋。至于上一曲下一曲的區(qū)別， 這里要重點(diǎn)說明一下，就是利用了反饋抽頭數(shù)在 M 序列上面的應(yīng)用，在 M 序列 解釋的第一個(gè)特點(diǎn)中有提及。我們可以看看在頭文件 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 ) 抽頭數(shù)的定義有一定的規(guī)律，參照這個(gè)規(guī)律，可以實(shí)現(xiàn)對(duì)其他級(jí)的選擇。小結(jié)小結(jié)一下這個(gè)學(xué)習(xí)的過程，里面還有兩點(diǎn)沒有深入地理解:1、 抽頭數(shù)