一種乘同余偽隨機(jī)序列快速實(shí)現(xiàn)的FPGA設(shè)計(jì)

陳 帥

(淮南師范學(xué)院 計(jì)算機(jī)與信息工程系，安徽 淮南232001)

在擴(kuò)頻通信、信息加密和系統(tǒng)測試等實(shí)際應(yīng)用領(lǐng)域中采用了與隨機(jī)序列特性類似的偽隨機(jī)序列[1]。常用的偽隨機(jī)序列是基于線性反饋移位寄存器的m序列與同余序列(乘同余和線性同余)。

乘同余的隨機(jī)數(shù)發(fā)生器[2-3]：y(n+1)=(16807×y(n))mod(231-1)已被廣泛應(yīng)用，其周期為素?cái)?shù)231－1＝2 147 483 647=2.147 483 647×109,直接進(jìn)行該式的乘同余計(jì)算需要64位的整數(shù)除法運(yùn)算。最簡單的方法是采用循環(huán)減法實(shí)現(xiàn)該同余序列運(yùn)算中的整數(shù)除法，即采用將積循環(huán)減去模數(shù) 231-1，直到被減數(shù)小于模數(shù)231-1，則最后的被減數(shù)即為求得的同余數(shù)。采用循環(huán)相減的方法，若循環(huán)的次數(shù)多，必然會(huì)影響速度。為此，Montgomery[4]提出了一種求兩個(gè)大整數(shù)乘積的模的快速算法，算法不需要除法，只采用乘法、加法和右移位，即采用邊乘邊移位，其結(jié)果還需要進(jìn)一步處理。如果參加乘積的數(shù)很大，則移位很多，必然降低運(yùn)算速度。參考文獻(xiàn)[5]采用改變初始值設(shè)定，兩次調(diào)用該Montgomery算法實(shí)現(xiàn)形如 S=(x×y)mod N運(yùn)算，即兩個(gè)大整數(shù)乘積的模的計(jì)算，但運(yùn)算速度必然又大大降低。

現(xiàn)場可編程門陣列FPGA(Field Programmable Gate Array)編程靈活、修改方便，特別適用于流水線方式與并行方式的數(shù)據(jù)處理。在很多高速設(shè)計(jì)和高速測試的場合[6],能夠在FPGA中直接實(shí)現(xiàn)上述偽隨機(jī)序列發(fā)生器。傳統(tǒng)的實(shí)現(xiàn)乘同余產(chǎn)生偽隨機(jī)數(shù)的軟件方法時(shí)鐘頻率很低，而采用FPGA硬件實(shí)現(xiàn)則可以達(dá)到更高的速度。本文對該乘同余偽隨機(jī)序列提出了一種快速方法，該算法特別適合FPGA快速實(shí)現(xiàn)。

1 乘同余操作快速算法設(shè)計(jì)

快速算法流程圖如圖1所示。算法使用3個(gè)32位存儲(chǔ)單元，1個(gè)32位存儲(chǔ)器用于存儲(chǔ)常數(shù) 16 807，2個(gè)32位存儲(chǔ)器依次用于存儲(chǔ)乘法結(jié)果、移位結(jié)果、加法結(jié)果。此外采用了1個(gè)32位的乘法器、2個(gè)32位的加法器、少量移位操作和1個(gè)最高位分離器。算法步驟如下：

(1)將輸入值 y(n)與常數(shù)16807分別存入2個(gè) 32位存儲(chǔ)單元中。

(2)將步驟(1)中數(shù)據(jù)進(jìn)行 32位乘法運(yùn)算,乘積分別存入低32位存儲(chǔ)單元和高32位存儲(chǔ)單元中。

(3)將乘積的高32位存儲(chǔ)單元整體向高位移動(dòng)1位(將乘積的最高位丟棄)，然后，將乘積的低 32位存儲(chǔ)單元的最高位移入乘積高32位存儲(chǔ)單元的最低位。

(4)將乘積的低32位存儲(chǔ)單元的最高位置為零值；

(5)將步驟(3)、(4)所得的 2個(gè) 32位存儲(chǔ)單元進(jìn)行32位的加法運(yùn)算得到32位的和值。

(6)將步驟(5)所得和值的高位（1或 0值）取出，存入另一32位存儲(chǔ)單元，將步驟(5)和值的最高位置為零值(最高位分離)。

(7)將步驟(6)所得 2個(gè) 32位存儲(chǔ)單元值相加，得到32位的和值，即為乘同余迭代操作計(jì)算值 y(n+1)=(16 807×y(n))mod(231-1)。

2 乘同余快速運(yùn)算的驗(yàn)證

采用FPGA功能仿真驗(yàn)證乘同余的快速算法模型如圖2所示。在輸入時(shí)鐘信號clk的上升沿完成對輸入信號in[31..0]的一次乘同余計(jì)算，產(chǎn)生輸出信號out[31..0]， 輸出信號為：out[31..0]=(16 807×in[31..0])mod(231-1)，采用Verilog HDL硬件描述語言描述為：

FPGA設(shè)計(jì)實(shí)現(xiàn)的乘同余快速計(jì)算的仿真功能如圖3所示,T1時(shí)刻,輸入為0x00000002,在clk的上升沿進(jìn)行計(jì)算：(16 807×2)mode(231-1)=0x834e;T2時(shí)刻,輸入為0x6fffffff,在 clk的上升沿進(jìn)行計(jì)算：(16 807×0x6fffffff)mode(231-1)=0x0ffff7cb;T3時(shí)刻,輸入為 0x003fffff,在 clk的上升沿進(jìn)行計(jì)算：(16 807×0x003fffff)mode(231-1)=0x69bfbe79;T4時(shí)刻,輸入為 0,在 clk的上升沿進(jìn)行計(jì)算：(16 807×0)mode(231-1)=0;T5時(shí)刻,輸入為 0x00000006,在clk的上升沿進(jìn)行計(jì)算:(16 807×6)mode(231-1)=0x000189ea?？梢姡現(xiàn)PGA仿真結(jié)果與人工計(jì)算一致，從而證明了乘同余快速算法的正確性。

2.2 乘同余序列的產(chǎn)生

為了連續(xù)產(chǎn)生乘同余序列，需要將上次產(chǎn)生的結(jié)果反饋輸入作為下次進(jìn)行乘同余計(jì)算的輸入值。為此需要對乘同余算法添加選擇控制電路，F(xiàn)PGA才能實(shí)現(xiàn)序列發(fā)生器。設(shè)計(jì)的電路如圖4所示,其中選擇控制為快速乘同余計(jì)算選擇輸入的數(shù)據(jù)，在set=1時(shí)完成初始值預(yù)置輸入，在set=0時(shí)進(jìn)行反饋輸入。

圖5為設(shè)計(jì)的FPGA電路功能仿真圖，F(xiàn)PGA采用EPF10K30ATC144-1。在T1時(shí)刻以前的set=1預(yù)置了初始值0x00000001，從而在T1時(shí)刻的時(shí)鐘clk的上升沿進(jìn)行乘同余運(yùn)算得到0x000041A7；在T2時(shí)刻的時(shí)鐘clk的上升沿，由于set=0,將0x000041A7代入進(jìn)行乘同余運(yùn)算得到0x10D63AF1；在T3時(shí)刻的時(shí)鐘clk的上升沿，由于set=0,將0x10D63AF1代入進(jìn)行乘同余運(yùn)算得到0x60B7ACD9;在T4時(shí)刻的時(shí)鐘clk的上升沿，由于set=0，將0x60B7ACD9代入進(jìn)行乘同余運(yùn)算得到0x3AB50C2A；在T5時(shí)刻的時(shí)鐘clk的上升沿,由于set=0,將0x3AB50C2A代入進(jìn)行乘同余運(yùn)算得到0x4431B782；在T6時(shí)刻開始set=1,故又重新預(yù)置初始值0x00000001，然后在T7時(shí)刻的時(shí)鐘clk的上升沿,將0x00000001代入進(jìn)行乘同余運(yùn)算得到0x000041A7；在T8時(shí)刻的時(shí)鐘 clk的上升沿，由于 set=0，將0x000041A7代入進(jìn)行乘同余運(yùn)算得到0x10D63AF1。

對計(jì)算乘同余序列：y(n+1)=(16 807×y(n))mod(231-1)的運(yùn)算，提出了一種新的快速算法，算法包括1個(gè)32位乘法、2個(gè)32位加法、少量移位操作和1次最高位分離，不需要除法，只需乘法、加法、移位和最高位分離操作即可。在FPGA上設(shè)計(jì)了快速同余算法，功能仿真驗(yàn)證了該算法的正確性。

[1]李飛飛,劉偉寧,王艷華.改進(jìn)的中值濾波算法及其 FPGA快速實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2009,35(14):175-177.

[2]楊波.網(wǎng)絡(luò)安全理論與應(yīng)用[M].北京:電子工業(yè)出版社,2002.

[3]張傳林,林立東.偽-隨機(jī)數(shù)發(fā)生器及其應(yīng)用[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用,2002,23(3):188-208.

[4]PETER L.Modular multiplication without trial division.Mathematics of Computation,1985,44(170):519-521.

[5]陳政彣.于8051單芯片上實(shí)作RSA密碼系統(tǒng)之能量擊及防御措施[D].臺(tái)灣：資訊工程研究所,1993.

[6]束禮寶,宋克柱,王硯方.偽隨機(jī)數(shù)發(fā)生器的FPGA實(shí)現(xiàn)與研究[J].電路與系統(tǒng)學(xué)報(bào),2003,8(3):121-124.