[發(fā)明專利]一種構(gòu)造隨機(jī)序列的最短線性移位寄存器的方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201310112404.5
• 申請(qǐng)日: 2013-04-02
• 公開(kāi)（公告）號(hào): CN103235714A
• 公開(kāi)（公告）日: 2013-08-07
• 發(fā)明（設(shè)計(jì)）人: 康紅娟
• 申請(qǐng)（專利權(quán)）人: 四川長(zhǎng)虹電器股份有限公司
• 主分類號(hào): G06F7/58
• 分類號(hào): G06F7/58
• 代理公司: 成都九鼎天元知識(shí)產(chǎn)權(quán)代理有限公司 51214
• 代理人: 詹永斌

所屬技術(shù)領(lǐng)域

本發(fā)明是針對(duì)目前應(yīng)用廣泛的隨機(jī)序列，解決構(gòu)造生成任一隨機(jī)序列的線性移位寄存器的問(wèn)題，具體涉及一種構(gòu)造隨機(jī)序列的最短線性移位寄存器的方法。

背景技術(shù)

隨機(jī)序列可以作為一種信號(hào)形式，也可以作為一個(gè)隨機(jī)數(shù)。是一類有著廣泛應(yīng)用的碼。例如，在連續(xù)波雷達(dá)中可用作測(cè)距信號(hào)，在遙控系統(tǒng)中可用作群同步信號(hào)，還可用作噪聲源及在保密通信中起加密作用等等。它還可以產(chǎn)生偽隨機(jī)數(shù)適于及孫繼的系統(tǒng)模擬和在數(shù)字系統(tǒng)中作為誤碼測(cè)試信號(hào)等。隨機(jī)序列還可用于擴(kuò)頻，在多址系統(tǒng)中作為地址信號(hào)等。隨機(jī)序列有著多方面的應(yīng)用，因此它的地位非常重要，對(duì)它的而研究也日益廣泛和深入。

線性移位寄存器是一類隨機(jī)位序列生成器，在硬件序列發(fā)生器以及密碼學(xué)中都有廣泛應(yīng)用，也能滿足低功耗或高速度的要求。對(duì)于一個(gè)周期為N的隨機(jī)序列，通常需要占用具有N個(gè)存儲(chǔ)單元的移位寄存器，這樣在一些周期較大的隨機(jī)序列就需要占用很多的硬件資源。這這種情況下，找到一種能產(chǎn)生周期為N的隨機(jī)序列的最短的性移位寄存器就顯得尤為重要。

發(fā)明內(nèi)容

為了實(shí)現(xiàn)上述目的，本發(fā)明提供了一種構(gòu)造隨機(jī)序列的最短線性移位寄存器的方法，分為以下幾步：

第一步：給定一個(gè)周期為N的有限序列a_i(0≤i≤N)，尋找最小的整數(shù)尋找非負(fù)整數(shù)n₀，序列中小于n₀的項(xiàng)數(shù)為0。

第二步.將第一步所述序列中小于等于n₀的項(xiàng)數(shù)賦值給一個(gè)新子序列d_i(0≤i≤N)的對(duì)應(yīng)項(xiàng)數(shù)，其中f_n0(x)為d_n0對(duì)應(yīng)的多項(xiàng)式。

第三步.約定n₀+1個(gè)值為1的聯(lián)接多項(xiàng)式，與第二步所述新子序列中d_i(0≤i≤n₀)相對(duì)應(yīng)，每個(gè)多項(xiàng)式對(duì)應(yīng)的級(jí)數(shù)為0。

第四步.由第二步所述新子序列構(gòu)造n₀+1階線性移位寄存器<f_n0+1(x)，L_n0+1>的多項(xiàng)式，作為周期為n₀+1的隨機(jī)序列生成多項(xiàng)式f_n0+1(x)以及級(jí)數(shù)L_n0+1；

第五步.循環(huán)第四步，進(jìn)行遞歸運(yùn)算，計(jì)算位于n₀與N之間的任意的周期序列的生成線性移位寄存器，最終得到周期為N的序列的線性移位寄存器<f_N(x)，L_N>。

采用本發(fā)明，得到產(chǎn)生周期為N的隨機(jī)序列的最短線性移位寄存器，盡量少的占用了存儲(chǔ)單元，節(jié)約硬件資源。

具體實(shí)施方式

結(jié)合本發(fā)明的需要，先介紹如下術(shù)語(yǔ)：

1、q元有限域

假定一個(gè)集合F是非空的，F(xiàn)中的成員可以叫做元素。進(jìn)一步在F中規(guī)定加法和乘法這兩種運(yùn)算，即對(duì)于F中的任意兩個(gè)元素a和b，可以對(duì)它們進(jìn)行加法運(yùn)算和乘法運(yùn)算。加法運(yùn)算的結(jié)果記作a+b，叫做它們的和。乘法運(yùn)算的結(jié)果記作a*b，叫做它們的積。同時(shí)要求F中任意兩個(gè)元素經(jīng)過(guò)加法運(yùn)算和乘法運(yùn)算的結(jié)果仍是F中的元素。也就是F對(duì)于所規(guī)定的加法運(yùn)算和乘法運(yùn)算是自封的。同時(shí)，F(xiàn)中的加法運(yùn)算和乘法運(yùn)算滿足如下規(guī)則：

（1）對(duì)于F中任意元素a，b，c，有

a+b=b+a

(a+b)+c=a+(b+c)

a*b=b*a

(a*b)*c=a*(b*c)

a*(b+c)=a*b+a*c

（2）F中存在一個(gè)元素0，具有性質(zhì)

a+0=a

（3）F中存在一個(gè)元素-a，具有性質(zhì)

a+(-a)=0

（4）F中存在一個(gè)非0元素e，具有性質(zhì)

a*e=a

(5)對(duì)任意F中非0元素a，存在元素a^-1，具有性質(zhì)

a*a^-1=e

那么F對(duì)于所規(guī)定的加法運(yùn)算和乘法運(yùn)算是一個(gè)域。進(jìn)一步，若F中的元素個(gè)數(shù)是有限的q個(gè)，F(xiàn)就稱作q元有限域。

2、n級(jí)線性反饋移位寄存器