CN1165131C - Linear feedback shift register - Google Patents

Abstract

The present invention relates to a shift register which is used for a system for providing enciphering codes and decoding codes. Coefficients of the shift register are provided by a polynomial of an n-order linear feedback shift register. The shift register comprises a memory which is used for storing the coefficients of the polynomial of the linear feedback shift register and results after calculation of received input samples. The memory has an input end which is used for receiving the input samples and output conforming to the polynomial of the linear feedback shift register.

Description

The encrypted code and the deciphering method of linear feedback shift register and electing property

Technical field

A kind of device of encrypted code (encryption) with deciphering (decryption) that provide is provided, particularly be directed to use and look for the table (look-up table) or (sub-table) linear feedback shift register of inferior table, the present invention has complete detailed explanation.

Background technology

In the communication and computer system in modern times, safety measure is a very important factor.In order to increase the safety measure of system, must be engaged in the encrypted code and the deciphering of information.Before transmission information, data transmitter must transmit encrypted code information (can be called cryptogram) to receiver more earlier with data (can be called plain text) encrypted code.This receiver must be with the cryptogram deciphering before this original plain text information is restored and understood.

Normally used element is linear feedback shift register (linearfeedback shift register is hereinafter to be referred as LFSR) in the safety measure system, and it is to use in encrypted code and two kinds of systems of deciphering.Each LFSR can be represented by LFSR multinomial (also can be called the input multinomial).Fig. 1 is the LFSR functional block diagram, and can or import polynomial repressentation by following LFSR:

x ³¹+x ⁷+x ⁵+x ³+x ²+x+1 (1)

In this example, LFSR will import the 32nd, the 8th, the 6th, the 4th, the 3rd, the 2nd and the 1st bit of sample (input pattern) and do the XOR computing, produce an output bit.Then, this input sample bit that moves to left, and the least significant bit (LSB) unit of this original input sample produces a new revised input sample with regard to exporting bit thus and replacing.LFSR continues revised input sample is done identical computing and produces next new output bit.This computing is last with whole plain text information encryption sign indicating numbers or with till whole cipher text information decipherings.Clearly, known LFSR computing is the output (that is being that a LFSR displacement produces 1 output bit) that produces 1 bit with the form of serial at an execution cycle.

And known LFSR has following shortcoming.At first, the LFSR of known serial output form is under High Speed System, and its transmission rate can not satisfy these systems.As discussed previously, because LFSR is a series form, its transmission rate is the output that an execution cycle produces 1 bit, and these known LFSR can not satisfy many High Speed System one execution cycles or essential generation of time 8 or the more output of multidigit unit.In order to increase the output speed of these LFSR, just produced known parallel output (that is each bit or 16 bits) cycle times 8.Yet, and line output has increased the complexity of circuit and design and the manufacturing cost of increase LFSR.Usually, being used for the circuit of parallel running can be too big and be difficult to be implemented in the consideration of economic benefit.

The second, in order to increase the safety measure system, it is desired periodically changing the LFSR multinomial.Unfortunate, if do not spend cost and resource designs again, known LFSR can not adapt to modifiable LFSR multinomial.For instance, the logical circuit (random logic) of known LFSR utilization combination.Yet the hardware logic electric circuit of script just must design again could adapt to the polynomial change of LFSR when the LFSR multinomial changes.This cost and resource that designs cost again is quite high.

So, must have a comparatively flexible mode to realize that LFSR is to overcome the above-mentioned shortcoming that is manifested.

Summary of the invention

The purpose of this invention is to provide a suitable linear feedback register, it can be in one-period or once produce to surpass the output (parallel output is provided) of 1 bit.

Another object of the present invention provides a suitable linear feedback register, and it can adapt to the polynomial change of LFSR, and need not redesign logical circuit.

Another object of the present invention provides a suitable linear feedback register, and it can be carried out cost-efficient considering down.

And the present invention is divided into multistage calculating with linear shift register, and the calculating of each grade all realizes with memory, and upper level result calculated (promptly going up the output of a level memory) will be as the addressing address of the memory of next level.The memory of afterbody then is that the XOR calculated result is made in its output of all memories that is used for obtaining its previous stage, the bit number output that output simultaneously needs, and the plain text encrypted code can be become cryptogram or the cryptogram deciphering is become plain text, to realize the present invention.

The invention provides a kind of linear feedback shift register and be used for encrypted code and deciphering system.The output of this linear feedback shift register in order to produce the k bit, this linear feedback shift register in each in cycle provide the n rank a LFSR multinomial its a plurality of coefficients are arranged, this linear feedback shift register comprises:

One memory cell is in order to storing coefficient and the result of input sample after as calculated in the described LFSR multinomial, and this memory has an input in order to receiving the input sample, and an output that is consistent with this LFSR multinomial.According to the input sample and be stored in content in the memory, this shift register can produce desirable and the line output result.

The invention provides a kind of with the data method of encrypted code and deciphering optionally, comprising step:

The polynomial a plurality of coefficients of a LFSR that the n rank are provided are to a linear feedback shift register;

Provide linear feedback shift register one memory cell, in order to store a polynomial coefficient of LFSR and an input sample through the result after calculating, memory cell has an input in order to receive the input sample; And

According to the input sample, provide to meet the polynomial output of LFSR.

Be preferably in technical scheme of the present invention, this memory cell can comprise a plurality of memory blocks, and each memory block produces a parallel bit and forms the output of k bit.Described a plurality of memory block is made of k memory.Wherein memory cell size is 2 ⁽ⁿ⁺¹⁾* 1.Wherein a plurality of memory blocks can comprise the memory block of secondary at least.

Be preferably, when this LFSR multinomial is split into m order polynomial, this linear feedback shift register comprises one the 1st grade of memory block and one the 2nd grade of memory block, the 1st grade of memory block comprises m memory, wherein m is split into the number of order polynomial for this LFSR multinomial, the 2nd grade of memory block comprises k memory, and wherein k is the each bit number that produces of this linear feedback shift register.

Be preferably, each memory of the 1st grade of memory block in the linear feedback shift register receives an input sample and is used as an Input Address.Each memory of the 2nd grade of memory block of linear feedback shift register receive the 1st grade of memory block memory output and carry out an XOR (XOR) computing.Linear feedback shift register comprises that also an input is in order to receive the output of k bit from this memory cell in each cycle.Each cycle of linear feedback shift register, wherein k was greater than 1 to high bit place's displacement k bit, and k is the number of the memory of the 2nd grade of memory block of expression.

And, in above-mentioned method, be preferably the k bit is provided output in order to input as linear feedback shift register.And memory cell wherein comprises a plurality of memory blocks, and each memory block produces a parallel bit and forms the output of k bit.Memory block is made of k memory.Memory cell size can be 2 ⁽ⁿ⁺¹⁾* 1.A plurality of memories comprise the memory block of secondary at least.

Said method also comprises: each cycle, wherein k was greater than 1 to high bit place's displacement k bit, and k is the number of the memory of the 2nd grade of memory block of expression.

Adopt technical scheme of the present invention, can under the situation that does not increase circuit cost, improve the transmission rate of system, need not drop into new cost and carry out under the situation of new design simultaneously, just can be fit to the polynomial change of LFSR, have the advantages that range of application is wider, system speed is higher, be more convenient for using.

Description of drawings

For above-mentioned purpose of the present invention, feature and advantage can be become apparent, will lift preferred embodiment below, and conjunction with figs., be described in detail below:

Fig. 1 is the diagrammatic sketch of the linear feedback shift register of prior art;

Fig. 2 can carry out the calcspar of encrypted code/deciphering system for the present invention;

Fig. 3 is the more detailed schematic diagram of the crypto engine among Fig. 2;

Fig. 4 is the more detailed schematic diagram of the decryption engine among Fig. 2;

Fig. 5 is the more detailed shift register sterogram of the present invention in Fig. 3 or Fig. 4;

Fig. 6 A is the calcspar that the LFSR of Fig. 5 is an example with a LFSR multinomial;

Fig. 6 B and 6C are the computing example of the LFSR of Fig. 6 A; And

Fig. 7 and Fig. 8 are multistage LFSR.

Embodiment

Below given description, detailed details be in order to provide to better understanding of the present invention, its purpose is not for explaining but in order to restriction the present invention.Yet be familiar with the personage of this skill, can reach detailed details of the present invention with other examples.Details as you know or prior art data processing technique, hardware unit and circuit then will be omitted, and can't make description of the invention unclear.

Encrypted code and deciphering system 10

Fig. 2 can carry out the calcspar of encrypted code/deciphering system 10 for the present invention.Encrypted code/deciphering system 10 comprises crypto engine 12 and decryption engine 11.Crypto engine 12 receives plain text 16, and according to encryption key 18 plain text 16 encrypted codes and defined cryptographic algorithm is produced cryptogram 20.Decryption engine 11 receives cryptograms 20, and according to decruption key 22 cryptogram 20 decipherings and defined deciphering algorithm is restored and to be plain text 16.Be used for encrypted code encryption key 18 be used for the decruption key 22 of deciphering can be identical also can be inequality.LFSR of the present invention can carry out any crypto engine 12 or decryption engine 11, and its Fig. 2 and Fig. 3 are more detailed view.

Fig. 3 illustrates figure in more detail for the crypto engine 12 in Fig. 2.Crypto engine 12 comprises shift register 40 and replacement circuit 44 (can be called S-box (S-BOX)).Shift register 40 comprises the input that receives encryption key 18 and produces the output (that is k bit) that has defined output signal bit number.Shift register 40 can make up in guidance according to the present invention.

Replacement circuit 44 comprises the first input end of the output that receives shift register 40, the output that receives second input of k bit plain text 16 and produce k bit cryptogram 20.All be that output bit number according to shift register 40 decides by the bit number of the cryptogram 20 that produced of replacement circuit 44 each time.In fact the bit number of cryptogram 20 can be greater than k, and the bit number of LFSR output in the present embodiment then is the k bit.Replacing the operation of circuit 44 is well known technology, and it is made of the map list (mapping table) that produces by the basis with the cryptographic algorithm.

Aspect action, shift register 40 produces the output of k bit according to original input, and the encrypted code text that an instead input of circuit 44 is used for producing k bit is incited somebody to action in the output of this k bit, and the output bit of this k shift register also will feed back to shift register 40 simultaneously.Like this, k the bit that will be moved to left of the original inputs in the shift register 40, back k low bit (LSB) just is shifted k the bit that register 40 exports and replaces simultaneously.Use the input of new shift register (also to be about to original input k the bit that move to left, simultaneously back k low bit is that output by shift register 40 is replaced), the output that shift register 40 produces other k bit, and S box 44 produces new k bit cryptogram 20.Repeat this step till all encrypted sign indicating number of all plain texts 16 is for cryptogram 20.

Fig. 4 is the more detailed view of the decryption engine 11 in Fig. 2.Decryption engine 11 comprises shift register 40A and replacement circuit 44A (can be called S-box (S-BOX)).Shift register 40A comprises the input of receiving and deciphering key 22 and produces and defined bit and count the output of output signal (that is k bit).Shift register 40A can make up in guidance according to the present invention.

Replacement circuit 44A comprises the first input end of the output that receives shift register 40A, second input of the cryptogram 20 of reception k bit and the output that produces the plain text 16 of k bit.The bit number of the plain text 16 that is produced by replacement circuit 44A all is that output bit number according to shift register 40A decides each time.Replacing the execution of circuit 44A is well known skill, and it is formed under by the basis in cryptographic algorithm by the map list that has defined.

Aspect action, shift register 40A produces the output of k bit according to original input, the output of this k bit is used for producing k bit deciphering text with the instead input of circuit 44A, and this k of shift register 40A output bit will feed back to shift register 40A simultaneously.Like this, k the bit that will be moved to left of the original input in the shift register 40A, the individual low bit (LSB) of the back k output that just is shifted register 40A simultaneously replaces.Use new shift register input (that is original input k the bit that moved to left, simultaneously back k low bit is that output by shift register 40A is replaced), shift register 40A produces the output of other k bit, and S box 44A produces new k bit plain text 16.Repeat this step till all decrypted sign indicating number of all cryptograms 20 is for plain text 16.

Derive general expression or n output equation

General expression (general expression) or n output multinomial will be derived.Herein, the symbol of "+" is the computing of representing XOR (XOR) in fact.Suppose that the LFSR multinomial is:

$f\left(x\right)=\underset{i=0}{\overset{n}{\mathrm{\Σ}}}{a}_i{x}^i------\left(2\right)$

The input sample is { b _n, b _N-1, b _N-2... ... ..b ₂, b ₁, b ₀And when the input sample when feeding back to LFSR its output order for dk, dk-1, dk-2 ... ... d2, d1, d0}, { a _n, a _N-1, a _N-2... ... ..a ₂, a ₁, a ₀It then is the coefficient of LFSR.Can derive following result then:

$\mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}0=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{a}_i{b}_i------\left(3\right)$

$\mathrm{<figure-callout\; id="1"\; label="d"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">d</figure-callout>}1=\underset{i=0}{\overset{n-1}{\mathrm{\&Sigma;}}}{a}_{i+1}{b}_i+a_0{\mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}}_0$

$=\underset{i=0}{\overset{n-1}{\mathrm{\&Sigma;}}}{a}_{i+1}{b}_i+{\mathrm{<figure-callout\; id="0"\; label="a"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">a</figure-callout>}}_0\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{a}_i{b}_i$

$=\underset{i=0}{\overset{n-1}{\mathrm{\&Sigma;}}}(a_{i+1}+a_0{a}_i)b_i+a_0{a}_n{b}_n$

$=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}d{1}_i{b}_i------\left(4\right)$

Wherein under i≤n-1

d1 _i＝(a _i+1+a ₀a _i)

d1 _n＝a ₀a _n

$\mathrm{<figure-callout\; id="2"\; label="d"\; filenames="C0111025000271.png"\; state="\{\{state\}\}">d</figure-callout>}2=\underset{i=0}{\overset{n-2}{\mathrm{\&Sigma;}}}{a}_{i+2}{b}_i+a_1{\mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}}_0+a_0{\mathrm{<figure-callout\; id="1"\; label="d"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">d</figure-callout>}}_1$

$=\underset{i=0}{\overset{n-2}{\mathrm{\&Sigma;}}}{a}_{i+2}{b}_i+{\mathrm{<figure-callout\; id="1"\; label="a"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">a</figure-callout>}}_1\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{a}_i{b}_i+{\mathrm{<figure-callout\; id="0"\; label="a"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">a</figure-callout>}}_0\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}d{1}_i{b}_i$

$=\underset{i=0}{\overset{n-2}{\mathrm{\&Sigma;}}}(a_{i+2}+a_1{a}_i+a_0{d1}_i)b_i+a_1(a_{n-1}{b}_{n-1}+a_n{b}_n)+a_0{d1}_n{b}_n+a_{0}d{1}_{n-1}{b}_{n-1}$

$=\underset{i=0}{\overset{n-2}{\mathrm{\&Sigma;}}}(a_{i+2}+a_1{a}_i+a_0{d1}_i)b_i+(a_1{a}_{n-1}+a_0{d1}_{n-1})b_{n-1}+(a_1{a}_n+a_0{d1}_n)b_n$

$=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{d2}_i{b}_i------\left(5\right)$

Wherein under i≤n-2

d2 _i＝(a _i+2+a ₁a _i+a ₀d1 _i)

d2 _n-1＝a ₁a _n-1+a ₀d1 _n-1

d2 _n＝(a ₁a _n+a ₀d1 _n)

$d3=\underset{i=0}{\overset{n-3}{\mathrm{\&Sigma;}}}{a}_{i+3}{b}_i+a_2{\mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}}_0+a_1{\mathrm{<figure-callout\; id="1"\; label="d"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">d</figure-callout>}}_1+a_0{\mathrm{<figure-callout\; id="2"\; label="d"\; filenames="C0111025000271.png"\; state="\{\{state\}\}">d</figure-callout>}}_2$

$=\underset{i=0}{\overset{n-3}{\mathrm{\&Sigma;}}}{a}_{i+3}{b}_i+a_2\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{a}_i{b}_i+a_1\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{d1}_i{b}_i+a_0\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{d2}_i{b}_i$

$=\underset{i=0}{\overset{n-3}{\mathrm{\&Sigma;}}}(a_{i+3}+a_2{a}_i+a_1{d1}_i+a_0{d2}_i)b_i+a_2(a_{n-2}{b}_{n-2}+a_{n-1}{b}_{n-1}+a_n{b}_n)$

$+a_1({d1}_n{b}_n+{d1}_{n-1}{b}_{n-1}+{d1}_{n-2}{b}_{n-2})+a_0({d2}_n{b}_n+d{2}_{n-1}{b}_{n-1}+{d2}_{n-2}{b}_{n-2})$

$=\underset{i=0}{\overset{n-3}{\mathrm{\&Sigma;}}}(a_{i+3}+a_2{a}_i+a_1{d1}_i+a_0{d2}_i)b_i+(a_2{a}_{n-2}+a_1{d1}_{n-2}+a_0{d2}_{n-2})b_{n-2}$

$+(a_2{a}_{n-1}+a_1{d1}_{n-1}+a_0{d2}_{n-1})b_{n-1}+(a_2{a}_n+a_1{d1}_n+a_0{d2}_n)$

$=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}d{3}_i{b}_i---\left(6\right)$

Wherein under i≤n-3

d3 _i＝(a _i+3+a ₂a _i+a ₁d1 _i+a ₀d2 _i)，

d3 _n-2＝a ₂a _n-2+a ₁d1 _n-2+a ₀d2 _n-2

d3 _n-1＝a ₂a _n-1+a ₁d1 _n-1+a ₀d2 _n-1

d3 _n＝a ₂a _n+a ₁d1 _n+a ₀d2 _n

From above derivation, m is output as

$\mathrm{dm}=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}d{m}_i{b}_i=\left[\begin{array}{ccc}d{m}_n{\mathrm{dm}}_{n-1}& ......& {\mathrm{dm}}_{1}d{m}_0\end{array}\right]\left[\begin{array}{c}{b}_n\\ b_{n-1}\\ .\\ .\\ b_1\\ b_0\end{array}\right]------\left(7\right)$

Wherein m the Lose of dm:LFSR goes out

Dm _i: the Lose of m the output bit of LFSR goes out i coefficient of many Entries formula, and this coefficient is

Knot closes a ₀, a ₁... ..a _nDe Knot fruit

b _i: Lose goes into sample

Describe by top, output order dk, dk-1, dk-2 ... ... d2, d1, each bit among the d0} can be represented that this multinomial is called the output multinomial of this bit by a multinomial, and this to export polynomial coefficient be the polynomial coefficient { a of LFSR _n, a _N-1, a _N-2... ... ..a ₂, a ₁, a ₀Via the result after the different linear combination.After the polynomial coefficient of LFSR has been known, carry out the equation of (7), just can obtain the polynomial coefficient of output of all output bits.Acquisition at m bit of output order is by the input sample { b that will be provided _n, b _N-1, b _N-2... ... ..b ₂, b ₁, b ₀Bring into meet m output bit the output multinomial.So if need export in the LFSR system of k bit and can show that (7) derive k and export multinomial according to above-mentioned grade at an execution cycle, when receiving any input sample, only need in this k output of this input sample substitution multinomial, just can be in an execution cycle, obtain the output of k bit, for as how state the LFSR of notion on memory is realized meeting, following paragraph is illustrated.

Adaptability

The present invention uses one or more memories to replace logical circuit to carry out LFSR, makes the present invention can adapt to the polynomial adjustment of LFSR and changes.The present invention can use memory cell to carry out above-mentioned equation (7), makes the designer to adapt to polynomial change via the content that changes memory cell.The size of memory cell is 2 ⁽ⁿ⁺¹⁾* 1, wherein (n+1) represents address-bus width, and 1 representative data highway width, n are represented the polynomial exponent number of LFSR.

An input sample similarly is { b _n, b _N-1, b _N-2... ... ..b ₂, b ₁, b ₀, be the addressing that is used for memory cell.For instance, the input sample 0,0,0 .., 0} are taken as the address of memory cell, and be stored in 0,0,0 .., the data in the 0} position are then by access.Illustrate further, when the input sample 0,0,0 .., 1} are taken as the address of memory cell, and be stored in 0,0,0 .., the data in the 1} position are then by access.With similar form, 2 ⁽ⁿ⁺¹⁾The position can come access with the address that is fit to.In example, the designer can use above-mentioned equation (7) to calculate all dm values, according to following correspondence these values are stored then, when receiving any input sample, just can export its pairing m output bit according to following correspondence:

Dm (0,0,0 ..., 0) be stored in address (0,0,0 ..., 0)

Dm (0,0,0 ..., 1) be stored in address (0,0,0 ..., 1)

................

Dm (1,1,1 ..., 1) be stored in address (1,1,1 ..., 1)

Wherein dm (0,0,0..., 0) refers to that when importing sample be (0,0,0..., 0) time m output bit value, dm (0,0,0..., 1) refer to that when importing sample be (0,0,0..., 1) time m output bit value, by that analogy, dm (1,1,1..., 1) refer to that when importing sample be (1,1,1..., 1) time m output bit value.

Just after the output equation formula of m bit is derived, promptly after all coefficients of equation (7) are derived:

Dm (0,0,0..., 0) expression is with (0,0,0..., 0) the back value that is calculated of this input sample substitution equation (7), dm (0,0,0..., 1) represent (0,0,0..., 1) and the back value that is calculated of this input sample substitution equation (7), analogize in this, dm (1,1,1..., 1) represent (1,1,1..., 1) this imports the value that sample substitution equation (7) back is calculated.

And,, one relative output equation formula is all arranged for each output bit according to the description of front for a LFSR that must in one-period, export k bit, and always total k output equation formula, suppose that this k output equation formula is:

d ₀(x), d ₁(x) ... .d _k(x), wherein x refers to import sample (b _n, b _N-1... b ₁, b ₀), according to the description of the preceding paragraph, all available one 2 of each output equation formula ^N+1* 1 memory is realized, so for a LFSR that will export k bit at one-period, need k individual 2 altogether ^N+1* 1 memory, and each memory is used for realizing a corresponding output equation formula.

How to solve the problem of N when very big

The address-bus width of supposing memory cell is (n+1), and the dateout width is k.Suppose that the input sample provides { b _n, b _N-1, b _N-2... ... ..b ₂, b ₁, b ₀To memory cell.In general, when the multinomial exponent number (n) of LFSR increased, memory cell became more difficult and more consumes into original execution.For instance, its design of some circuit n equals 16 may be too big and unaccommodated, yet for other circuit design, n is greater than or equal to 16 and is fit to.

Problem when the present invention is cut apart original LFSR multinomial and become order polynomial and come addressing n very big.The inventor confirms to export multinomial dm following feature:

$\mathrm{dm}=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}d{m}_i{b}_i=\underset{j=0}{\overset{t-1}{\mathrm{\&Sigma;}}}d{m}_j{b}_j+\underset{l=t}{\overset{t+p-1}{\mathrm{\&Sigma;}}}{\mathrm{dm}}_l{b}_l+.....+\underset{r=n-p+1}{\overset{n}{\mathrm{\&Sigma;}}}{\mathrm{dm}}_r{b}_r$

$=\underset{i=0}{\overset{z}{\mathrm{\&Sigma;}}}{g}_i$

$=\left[\begin{array}{cccc}{\mathrm{dm}}_n& {\mathrm{dm}}_{n-1}& ...& {\mathrm{dm}}_{n-p+1}\end{array}\right]\left[\begin{array}{c}{b}_n\\ b_{n-1}\\ .\\ .\\ b_{n-\mathrm{<figure-callout\; id="1"\; label="p\; +"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">p</figure-callout>}+1}\end{array}\right]+..+\left[\begin{array}{cccc}{\mathrm{dm}}_{t-1}& {\mathrm{dm}}_{t-2}& ...& {\mathrm{dm}}_0\end{array}\right]\left[\begin{array}{c}{b}_{t-1}\\ b_{t-2}\\ .\\ .\\ b_0\end{array}\right]---\left(9\right)$

Wherein: gi represents the result of each order polynomial;

The original multinomial of z representative is partitioned into the number of order polynomial.Wherein the relational expression of z and n is as follows:

(n+1)＝z*p+q q＜z

Wherein p represents (n+1) merchant divided by z, and q represents (n+1) remainder divided by z.

According to equation (9), must determine that at first original LFSR will be partitioned into the how many times multinomial, that is to say that the z value must be determined by the designer earlier, after the decision of z value, each order polynomial just can be derived, and according to equation (9), its content of the memory of the first order is the result of each order polynomial, and its content of partial memory is to be stored in each order polynomial result of the first order to make XOR result afterwards, and detailed implementation will explain in the following description.

A shift register embodiment

Figure 5 shows that according to the shift register 40 of Fig. 3 of the embodiment of the invention or the calcspar of the shift register 40A of Fig. 4.At first import sample { b _n, b _N-1, b _N-2... ... ..b ₂, b ₁, b ₀Being divided into the z section, every section width is p, supposes that its q is 0.Otherwise the width of its front (z-1) section is all p, and final stage is t.Wherein the relational expression of p, q, t, z and n is as follows:

(n+1)＝z*p+q

If q=0 then t=0, if q ≠ 0 then t=(n+1)-(z-1) * P.The width of each section is the address-bus width of the 1st grade of memory 74 of Fig. 5.For instance, suppose that the z section is as follows:

B ₀＝(b _n，b _n-1，...，b _n-p+1)

B ₁＝(b _n-p，...，b _n-2p+1)

.......

B _z-1＝(b _x-1，b _x-1，...，b ₀)

B wherein ₀, B ₁... .B _Z-2Its width is p, and B _Z-1Width be x.Work as q=0, x equals p, otherwise x equals t, output equation formula by each the output bit that obtains in the equation (9) can be divided into z order polynomial, (the z formula is determined by the designer), if and a line output k bit, then this k the relative output equation formula of exporting bit can be expressed as following equation:

$\mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}0=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}{d0}_i{b}_i=\underset{j=0}{\overset{t-1}{\mathrm{\&Sigma;}}}{d10}_j{b}_j+\underset{l=t}{\overset{t+p-1}{\mathrm{\&Sigma;}}}{d20}_l{b}_l+....\underset{r=n-p+1}{\overset{n}{\mathrm{\&Sigma;}}}{\mathrm{dz}0}_r{b}_r=\underset{x=0}{\overset{z-1}{\mathrm{\&Sigma;}}}{g0}_x$

$\mathrm{<figure-callout\; id="1"\; label="d"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">d</figure-callout>}1=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}d{1}_i{b}_i=\underset{j=0}{\overset{t-1}{\mathrm{\&Sigma;}}}{d11}_j{b}_j+\underset{l=t}{\overset{t+p-1}{\mathrm{\&Sigma;}}}d{21}_l{b}_l+...\underset{r=n-p+1}{\overset{n}{\mathrm{\&Sigma;}}}{\mathrm{dz}1}_r{b}_r=\underset{x=0}{\overset{z-1}{\mathrm{\&Sigma;}}}{g1}_x$

.......

$\mathrm{dk}-1=\underset{i=0}{\overset{n}{\mathrm{\&Sigma;}}}\mathrm{dk}-1_i{b}_i=\underset{j=0}{\overset{t-1}{\mathrm{\&Sigma;}}}d1k-1_j{b}_j+\underset{l=t}{\overset{t+p-1}{\mathrm{\&Sigma;}}}d2k-1_l{b}_l+....\underset{r=n-p+1}{\overset{n}{\mathrm{\&Sigma;}}}\mathrm{dzk}-1_r{b}_r=\underset{x=0}{\overset{z-1}{\mathrm{\&Sigma;}}}\mathrm{gk}-1_x$

$\left[\begin{array}{c}\mathrm{dk}-1\\ \mathrm{dk}-2\\ .\\ .\\ d1\\ \mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}0\end{array}\right]=\left[\begin{array}{ccccc}\mathrm{dk}-1_m& \mathrm{dk}-1_{m-1}& ....& \mathrm{dk}-1_1& \mathrm{dk}-1_{m-\mathrm{<figure-callout\; id="1"\; label="p\; +"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">p</figure-callout>}+1}\\ & & .& & \\ & & .& & \\ d{0}_m& {d0}_{m-1}& ....& \mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}{0}_1& {d0}_{m-p+1}\end{array}\right]\left[\begin{array}{c}{b}_m\\ b_{m-1}\\ .\\ .\\ .\\ b_{m-\mathrm{<figure-callout\; id="1"\; label="p\; +"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">p</figure-callout>}+1}\end{array}\right]+...+\left[\begin{array}{cccc}\mathrm{dk}{-1}_{t-1}& \mathrm{dk}-1_{t-2}& ....& \mathrm{dk}-1_0\\ & .& & \\ & .& & \\ {d0}_{t-1}& {d0}_{t-2}& ....& {\mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}0}_0\end{array}\right]\left[\begin{array}{c}{b}_{t-1}\\ b_{t-2}\\ .\\ .\\ .\\ {\mathrm{<figure-callout\; id="0"\; label="b"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">b</figure-callout>}}_0\end{array}\right]$

$=\left[\begin{array}{c}{s}_{0.0}\\ s_{1.0}\\ .\\ .\\ .\\ s_{k-t.0}\end{array}\right]+\left[\begin{array}{c}{s}_{0.1}\\ s_{1.1}\\ .\\ .\\ .\\ s_{k-1.1}\end{array}\right]+.....+\left[\begin{array}{c}{\mathrm{<figure-callout\; id="0"\; label="s"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">s</figure-callout>}}_{0.z-1}\\ s_{t.z-1}\\ .\\ .\\ .\\ s_{k-1.z-1}\end{array}\right]------\left(10\right)$

Wherein gmn is meant if the result of its n order polynomial when m the output multinomial of exporting bit be divided into the z section.The relation of p, t, z and n is as follows:

(n+1) if=z*p+q q＜z and q be not equal to 0, t=(n+1)-(z-1) * p, otherwise t equals 0.

Shift register 40 or 40A comprise the 1st grade of memory block 70 and the 2nd grade of memory block 80.The 1st grade of memory block 70 comprise many memories or table 74 (promptly be memory 10, memory 1 ₁..., memory 1 _Z-1).The number of memory 74 (z) decides according to the number that original multinomial is cut apart order polynomial fully.Each memory 74 its content in the memory block 70 of the first order are according to (10) result calculated:

Memory 10 is used for realizing arithmetic expression

$\left[\begin{array}{cccc}\mathrm{dk}{-1}_n& {\mathrm{dk}-1}_{n-1}& ....& {\mathrm{dk}-1}_{n-\mathrm{<figure-callout\; id="1"\; label="p\; +"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">p</figure-callout>}+1}\\ & .& & \\ & .& & \\ {d0}_n& {d0}_{n-1}& ....& {d0}_{n-p+1}\end{array}\right]\left[\begin{array}{c}{b}_n\\ b_{n-1}\\ .\\ .\\ .\\ b_{n-p+1}\end{array}\right],$

Memory 11 is used for realizing arithmetic expression

$\left[\begin{array}{cccc}{\mathrm{dk}-1}_{n-p}& {\mathrm{dk}-1}_{n-p-1}& ....& \mathrm{dk}-1_{n-2p+1}\\ & .& & \\ & .& & \\ {d0}_{n-p}& {d0}_{n-p-1}& ....& {d0}_{n-2p+1}\end{array}\right]\left[\begin{array}{c}{b}_n\\ b_{n-1}\\ .\\ .\\ .\\ b_{n-p+1}\end{array}\right],$

Analogize in this,

Memory 1 _Z-1Be used for realizing arithmetic expression $\left[\begin{array}{cccc}{\mathrm{dk}-1}_{t-1}& {\mathrm{dk}-1}_{t-2}& ....& {\mathrm{dk}-1}_0\\ & .& & \\ & .& & \\ {d0}_{t-1}& {d0}_{t-2}& ....& {\mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}0}_0\end{array}\right]\left[\begin{array}{c}{b}_{t-1}\\ .\\ .\\ .\\ .\\ {\mathrm{<figure-callout\; id="0"\; label="b"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">b</figure-callout>}}_0\end{array}\right],$

And detailed content is, supposes with memory 1 ₀Be example, memory 1 ₀Address width be p and the output bus width is k, then (0,0,0, contained content is for (b in ..0) in its address _n, b _N-1... b _N-p+1)=(0,0,0, the result (s of the above-listed arithmetic expression gained of substitution in the time of ..0) _0,0, s _1,0... s _K-1,0).And (0,0,0, contained content is for (b in ..1) in the address _n, b _N-1..b _N-p+1)=(0,0,0, the result (s of the above-listed arithmetic expression gained of substitution in the time of ..1) _0,0, s _1,0... s _K-1,0).Remaining address contents also is to obtain in a like fashion.And (1,1,1, contained content is for (b in ..1) in the address _n, b _N-1..b _N-p+1)=(1,1,1, the result (s of the above-listed arithmetic expression gained of substitution in the time of ..1) _0,0, s _1,0... s _K-1,0).And as for other each memories in memory 70, its content also is to derive in the same way.Relation between z and the n (original polynomial exponent number) is:

(n+1)＝z*p+q q＜z

As discussed previously, p is (n+1) quotient divided by z, and q is (n+1) remainder divided by z.Each order polynomial at first will be determined.If q is not equal to 0, the individual memory size in front (z-1) is all (2 ^p* K), last memory size of the 1st grade of memory block 70 is (2 ^t* K), t=(n+1)-(z-1) * p wherein.If q is 0, then all z the 1st grade of memory block 70 memories 74 sizes are (2 ^p* K), K represents the also bit number of line output.

Input sample 60 be divided into the z section and each section to correspond to the memory 74 of the 1st grade of memory block 70 that meets all be an Input Address.

B ₀Expression memory 1 ₀Input Address, B _Z-1Expression memory 1 _Z-1Input Address.

The 2nd grade of memory block 80 comprises that many memories 84 (that is are memories 2 ₀..., memory 2 _Z-1) each data-bus width that the number of address-bus width z bit is all arranged and export a bit, z is the number of the 1st grade of memory block 70 memories 74.For instance, its stored content of k memory of the 2nd grade 80 is for making XOR computing value afterwards with memory 74 outputs of the 1st grade of memory block 70.Each memory 84 all has address-bus width z, and exports the data-bus width of a bit.Each memory 84 size is (2 ^z* 1).The 2nd grade of memory block 80 allows to produce at the same time k bit (parallel processing).

For instance, memory 2 ₀Comprise that an input is in order to receiver address bit S ₀₀..., S _0z-1, and via basic principle generation output bit d0.Memory 2 _K-1Comprise that an input is in order to receiver address bit S _K-10..., S _K-1z-1, and via basic principle generation output bit dk-1.

According to equation (10), each di output is the execution through a memory.Memory can comprise one the 1st grade and one the 2nd grade, and each level can have one or more external memory (sub-memory).

Each output di needs a z memory 74 of the 1st grade of memory block 70 and a memory 84 in the second level memory block 80.

If have k output bit to produce at the same time, when q=0, need z individual (2 at the 1st grade of memory block ^p* k) memory.Be not equal to the individual memory of 0, the 1 grade of needs (z-1) at q, each memory size is (2 ^p* k) and its size of memory be (2 ^t* k).

The calcspar that it is example with a LFSR multinomial that Fig. 6 A is depicted as the shift register of Fig. 5.LFSR112 comprises the 1st a grade of memory block 118 and the 2nd a grade of memory block 124.The 1st grade of memory block 118 comprises a first memory 134 and a second memory 138.The 2nd grade of memory block 124 comprises a first memory 144 and a second memory 148.One the 3rd memory 154.

Suppose that input sample 114 is { b ₄, b ₃, b ₂, b ₁, b ₀, and its LFSR multinomial is f (x)=x ⁴+ x ²+ x+1, LFSR multinomial are 4 rank (that is n=4), and LFSR112 is the output of (that is once-through operation, cycle or displacement) generation 3 bits once.The bit number (k) of each cycle output is 3.The output multinomial of d2, d1 and d0 can be expressed as follows (using equation (2)-(7)):

d0＝x ⁴+x ²+x+1

d1＝x ⁴+x ³+x ²

d2＝x ³+x ²+x

Each exports polynomial coefficient:

{d0 ₄，d0 ₃，d0 ₂，d0 ₁，d0 ₀}＝{1，0，1，1，1}

{d1 ₄，d1 ₃，d1 ₂，d1 ₁，d1 ₀}＝{1，1，1，0，0}

{d2 ₄，d2 ₃，d2 ₂，d2 ₁，d2 ₀}＝{0，1，1，1，0}

Suppose that each output multinomial is divided into two order polynomials (that is z=2), because (4+1)=2*2+1, according to equation (10), p=2, q=1, because q is not equal to 0, t=(n+1)-(z-1) * p=(4+1)-(2-1) * 2=3.The output order can be expressed as:

$\left[\begin{array}{c}d2\\ d1\\ \mathrm{<figure-callout\; id="0"\; label="d"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">d</figure-callout>}0\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 0& 1\end{array}\right]\left[\begin{array}{c}{b}_4\\ b_3\end{array}\right]+\left[\begin{array}{ccc}1& 1& 1\\ 1& 0& 0\\ 1& 1& 0\end{array}\right]\left[\begin{array}{c}{b}_2\\ b_1\\ b_0\end{array}\right]={\mathrm{<figure-callout\; id="0"\; label="m"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">m</figure-callout>}}_0+{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">m</figure-callout>}}_1$

Wherein ${\mathrm{<figure-callout\; id="0"\; label="m"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">m</figure-callout>}}_0=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 0& 1\end{array}\right]\left[\begin{array}{c}{b}_4\\ b_3\end{array}\right]=\left[\begin{array}{c}{\mathrm{<figure-callout\; id="2"\; label="s"\; filenames="C0111025000271.png"\; state="\{\{state\}\}">s</figure-callout>}}_{\mathrm{2,0}}\\ {\mathrm{<figure-callout\; id="1"\; label="s"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">s</figure-callout>}}_{\mathrm{1,0}}\\ {\mathrm{<figure-callout\; id="0"\; label="s"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">\; <figure-callout\; id="0"\; label="s"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">s</figure-callout>\; </figure-callout>}}_{\mathrm{0,0}}\end{array}\right],{\mathrm{<figure-callout\; id="1"\; label="m"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">m</figure-callout>}}_1=\left[\begin{array}{ccc}1& 1& 1\\ 1& 0& 0\\ 1& 1& 0\end{array}\right]\left[\begin{array}{c}{b}_2\\ b_1\\ b_0\end{array}\right]=\left[\begin{array}{c}{\mathrm{<figure-callout\; id="2"\; label="s"\; filenames="C0111025000271.png"\; state="\{\{state\}\}">s</figure-callout>}}_{\mathrm{2,1}}\\ {\mathrm{<figure-callout\; id="1"\; label="s"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">s</figure-callout>}}_{\mathrm{1,1}}\\ {\mathrm{<figure-callout\; id="0"\; label="s"\; filenames="C0111025000281.png,C0111025000291.png"\; state="\{\{state\}\}">\; <figure-callout\; id="1"\; label="s"\; filenames="C0111025000271.png,C0111025000281.png"\; state="\{\{state\}\}">s</figure-callout>\; </figure-callout>}}_{\mathrm{0,1}}\end{array}\right]$

When second-level storage block (118,124) is utilized, by above-mentioned equation (9), the 1st grade of memory block 118 comprises one (2 ^p* k)=2 ²The first memory 134 of * 3 sizes (being memory 10) with one (2 ^t* k)=2 ³The second memory 138 of * 3 sizes (being memory 11).

Moreover input sample 114 is divided into two sections B0={b ₄, b ₃And B1={b ₂, b ₁, b ₀.B0 section and B1 section distinctly are memory 134 (memory 1 ₀) and memory 138 (memory 1 ₁) Input Address.First memory 134 receives b ₄With b ₃Be Input Address, produce output bit S according to basic principle ₀₀, S ₁₀With S ₂₀Second memory 138 receives b ₂, b ₁With b ₀Be Input Address, produce output bit S according to basic principle ₀₁, S ₁₁With S ₂₁

Table 1 for first memory 134 the including of array m0 (matrix m0), it includes to { b ₄, b ₃Variously may make up the resulting result of substitution array operation formula m0.Table 2 for second memory 138 the including of array m1, it includes to { b ₂, b ₁, b ₀Variously may make up the resulting result of substitution array operation formula m1:

Table 1 memory 1 ₀Including of array m0

Address { b 4，b 3}	Include { s 2，0，s 1，0，s 0，0}
		00	{0，0，0}
01	{0，1，1}
		10	{1，1，0}
11	{1，0，1}

Table 2 memory 1 ₁Including of array m1

Address { b 2，b 1，b 0}	Include { s 2，1，s 1，1，s 0，1}
		000	{0，0，0}
001	{1，0，0}
		010	{1，0，1}
011	{0，0，1}
		100	{1，1，1}
101	{0，1，1}
		110	{0，1，0}
111	{1，1，0}

The 2nd grade of memory block 124, because k=3 and z=2 need three memories (144,148,154), the size that each memory needs is 2 ²* 1.Memory (144,148,154) is to be used for carrying out XOR, and its input is that the result by the memory (134,138) of the 1st grade of memory block 118 is provided.Each memory (144,148,154) includes all identical, as shown in table 3 (that is, memory 2 _i, i=2,1,0):

Table 3 memory 2 _iInclude i=2,1,0

The address	Include
		00	0
01	1
		10	1
11	0

Yet memory (144,148,154) receives different Input Address.First memory 144 receives S ₀₀With S ₀₁Input Address produces output bit d0.Second memory 148 receives S ₁₀With S ₁₁Input Address produces output bit d1.The 3rd memory 1 54 receives S ₂₀With S ₂₁Input Address produces output bit d2.

Fig. 6 B and 6C are depicted as Fig. 6 A and are used as b with 11 1 00 ₄₄..., b ₀Example as a result at each grade.Fig. 6 B is first execution cycle.At first an AND (logical) computing is performed between following:

b ₄, b ₃With d0 ₄, d0 ₃

b ₄, b ₃With d1 ₄, d1 ₃And

b ₄, b ₃With d2 ₄, d2 ₃

Then, each AND computing is carried out the XOR computing again and is produced S ₀₀, S ₁₀, S ₂₀Output.

The second, one AND computing is performed between following:

b ₂, b ₁, b ₀With d0 ₂, d0 ₁, d0 ₀

b ₂, b ₁, b ₀With d1 ₂, d1 ₁, d1 ₀And

b ₂, b ₁, b ₀With d2 ₂, d2 ₁, d2 ₀

Then, each AND computing is carried out the XOR computing again and is produced S ₀₁, S ₁₁, S ₂₁Output.

Be performed between the 3rd XOR computing is following:

S ₀₀, S ₀₁Produce d0;

S ₁₀, S ₁₁Produce d1; And

S ₂₀, S ₂₁Produce d2.

New bit d0-d2 moves to left to b ₄... b ₀New sample bit b ₄... b ₀Produce next new bit d0-d2 via above-mentioned AND and XOR computing again and become new sample again.Fig. 6 C then is next execution cycle.

Another one entity example again, its LFSR multinomial is:

x ¹⁵+ x ¹⁴+ x ¹¹+ x ¹⁰+ x ⁷+ x ⁶+ x ³+ x ²+ 1, and output k parallel output bit, the LFSR multinomial can be split into two order polynomials (P1 and P2) according to above-mentioned equation (9), and P1 is x ¹⁵+ x ¹⁴+ x ¹¹+ x ¹⁰, P2 is x ⁷+ x ⁶+ x ³+ x ²+ 1.According to the derivation of P1 and P2 and previous examples, can derive the content of each memory in the first order and the second level.

According to aforementioned, the 1st grade of memory block needs two (2 ⁸* k) memory, the 2nd grade of memory block need k (2 ²* 1) memory.

In special application, if still can not satisfy the demands too greatly at the 1st grade of its memory of memory block, there are following two kinds of methods can solve this problem, first method is divided into more order polynomial by describing according to (9) equation with the LFSR multinomial, just can adjust the size that the z value changes required memory.For instance, original multinomial may be partitioned into five order polynomials (P1, P2, P3, P4 and P5):

P1 is x ¹⁵+ x ¹⁴

P2 is x ¹¹+ x ¹⁰

P3 is x ⁷

P4 is x ⁶

P5 is x ³+ x ²+ 1

At this moment, the 1st grade of memory block needs four (2 ³* k) memory and one (2 ⁴* k) memory, the 2nd grade of memory block need k (2 ⁵* 1) memory.

Another solve the excessive method of first order built-in storage then be order polynomial P1 and P2 be divided into again inferior order polynomial (P11, P12, P21, P22).The structure of third level storage block is provided at this moment.Fig. 7 and Fig. 8 illustrate this example.

Suppose identical LFSR multinomial:

x ¹⁵+x ¹⁴+x ¹¹+x ¹⁰+x ⁷+x ⁶+x ³+x ²+1

Instruct according to the present invention, if it is divided into two order polynomials, then these two order polynomial P1 and P2 are respectively:

P1 is x ¹⁵+ x ¹⁴+ x ¹¹+ x ¹⁰And

P2 is x ⁷+ x ⁶+ x ³+ x ²+ 1

It is according to following parameter z that original multinomial is divided into two order polynomials, p and q (as above describing):

Original multinomial x ¹⁵+ x ¹⁴+ x ¹¹+ x ¹⁰+ x ⁷+ x ⁶+ x ³+ x ²+ 1 has 16 (the 13rd, 12,9,8,5,4,1 power item is 0).So because multinomial is divided into two order polynomial z=2, its p (n+1 is divided by the quotient of z) equals (15+1)/2=8, its q (n+1 is divided by the remainder of z) equals 0.Because q=0, each order polynomial has the p=8 item.The general rule that produces two order polynomial P1 and P2 is:

Promptly be that original polynomial f (x) is calculated the item of lowest-order from the item of high-order, per 8 form one group or order polynomial.Be noted that P1 is that the highest 8 and the P2 are minimum 8.

According to above-mentioned, the first order needs 2 (2 ⁸* k) memory, the second level need k (2 ²* 1) memory.This structure is shown in Figure 7, and memory 1 ₀Handle multinomial P1, memory 11 is handled multinomial P2.

If (2 ⁸* k) still too big on purposes, then circuit designers can instruct according to the present invention, and (P1 P2) is more a plurality of order polynomials (sub-sub-polynomial) with three grades segmentation of structures order polynomials

How explanation carries out three grades structure in the following example.Suppose P1, P2 can be expressed as:

P1 is x ¹⁵+ x ¹⁴+ 0x ¹³+ 0x ¹²+ x ¹¹+ x ¹⁰+ 0x ⁹+ 0x ⁸And

P2 is x ⁷+ x ⁶+ 0x ⁵+ 0x ⁴+ x ³+ x ²+ 0x+1

In multistage execution, (P1 P2) can be regarded as other multinomial to each order polynomial.For instance, (P11 P12) is cut apart in the above-mentioned identical mode of original multinomial of cutting apart when P1 is divided into two order polynomials.P11 and P12 are expressed as follows:

P11 is x ¹⁵+ x ¹⁴+ 0x ¹³+ 0x ¹²And

P12 is x ¹¹+ x ¹⁰+ 0x ⁹+ 0x ⁸

Fig. 8 is with memory 1 ₀Memory as secondary.Subtract one because each polynomial exponent number is polynomial item number, the item number of P1 is 8, and the exponent number of P1 is 7 (being n=7).P1 is divided into two order polynomials (that is z=2) and uses previously described principle, (7+1)=and 2*4+0.So p=4, q=0.If with memory 1 ₀Memory with a secondary replaces, since z=2,2 memories of the 11st grade of needs.Because 3 memories of the 12 grade of needs of k=3.Since p=4, q=0, k=3.The 11st grade of each memory needs (2 ^p* k)=(2 ⁴* 3) size, the 12nd grade of each memory needs (2 ^z* 1)=(2 ²* 1) size.

Explanation according to above-mentioned example, after number that original multinomial is divided into order polynomial is determined, the number of level, the needed amount of memory of each grade, and the size of memory, and these parameters all can guidance according to the present invention be derived out, can do best use by suitable modification and with resource on special purposes.Circuit designers can be analyzed the multinomial of being given, according to above-mentioned equation (9), and be evaluated at the number of its grade on each special purposes, the memory of each grade, and the size of memory (each possible partitioning scheme of original multinomial can produce different order polynomials).If it is inappropriate in cost-efficient design for special purposes, narrates above can repeating, and original multinomial is divided into different order polynomials.So, the tool cost efficiency, quick and suitable shift register can instruct according to the present invention and be understood.And the employed memory of LFSR allows the designer to change the LFSR multinomial.

In sum; though the present invention is disclosed in the preferred embodiment form; right its is not in order to limit the present invention; anyly have the knack of this operator; without departing from the spirit and scope of the present invention; should make various changes and modification, so protection scope of the present invention should be as the criterion with appended patent claimed range.

Claims (19)

1. linear feedback shift register, in order to the output that produces the k bit in each cycle, this linear feedback shift register provides a LFSR multinomial on n rank, and it has a plurality of coefficients, and this linear feedback shift register comprises:

One memory cell is in order to storing described coefficient and the result of input sample after as calculated in the described LFSR multinomial, and this memory has an input in order to receiving described input sample, and an output that is consistent with this LFSR multinomial; Wherein, k is greater than 1.

2. linear feedback shift register as claimed in claim 1 is characterized in that this memory cell comprises a plurality of memory blocks, and each described memory block produces a parallel bit and forms the k bit, and by described memory cell output.

3. linear feedback shift register as claimed in claim 2 is characterized in that it being to constitute described a plurality of memory block by k memory.

4. linear feedback shift register as claimed in claim 1 is characterized in that described memory cell size is 2 ⁽ⁿ⁺¹⁾* 1.

5. linear feedback shift register as claimed in claim 2 is characterized in that described a plurality of memory block is made up of the memory block of two levels at least.

6. linear feedback shift register as claimed in claim 1, it is characterized in that when this LFSR multinomial is split into m order polynomial, this linear feedback shift register comprises one the 1st grade of memory block and one the 2nd grade of memory block, the 1st grade of memory block comprises m memory, wherein m is split into the number of order polynomial for this LFSR multinomial, the 2nd grade of memory block comprises k memory, and wherein k is the each bit number that produces of this linear feedback shift register.

7. linear feedback shift register as claimed in claim 6 is characterized in that each described memory reception one input sample of described the 1st grade of memory block is used as an Input Address.

8. linear feedback shift register as claimed in claim 6 is characterized in that each described memory of described the 2nd grade of memory block, be receive described the 1st grade of memory block described memory output and carry out an XOR computing.

9. linear feedback shift register as claimed in claim 6 is characterized in that described linear feedback shift register comprises that more an input is in order to receive the output of k bit from this memory cell in each cycle.

10. linear feedback shift register as claimed in claim 9, it is characterized in that each cycle of described linear feedback shift register is to high bit place's displacement k bit, wherein k is greater than 1, and k is the number of the described memory of described the 2nd grade of memory block of expression.

11. the method with the encrypted code and the deciphering of an electing property of data is characterized in that:

The polynomial a plurality of coefficients of a LFSR that the n rank are provided are to a linear feedback shift register;

Described linear feedback shift register one memory cell is provided, and in order to store a polynomial described coefficient of described LFSR and an input sample through the result after calculating, described memory cell has an input in order to receive described input sample; And

According to described input sample, provide to meet the polynomial output of described LFSR.

12. method as claimed in claim 11 is characterized in that also comprising: the output that the k bit is provided is in order to the input as described linear feedback shift register, and wherein k is greater than 1.

13. method as claimed in claim 11 is characterized in that also comprising: described memory cell comprises a plurality of memory blocks, each described memory block produces a parallel bit and forms the output of k bit, and wherein k is greater than 1.

14. method as claimed in claim 13 is characterized in that described memory block is made of k memory.

15. method as claimed in claim 11 is characterized in that described memory cell size is 2 ⁽ⁿ⁺¹⁾* 1.

16. method as claimed in claim 13 is characterized in that described a plurality of memory is made up of the memory block of two levels at least.

17. method as claimed in claim 11 is characterized in that also comprising: described LFSR multinomial is split into m order polynomial.

18. method as claimed in claim 17, it is characterized in that also comprising: the 1st grade of memory block of described linear feedback shift register 1 and one the 2nd grade of memory block are provided, described the 1st grade of memory block comprises m memory, wherein m is the number that described LFSR multinomial is split into order polynomial, described the 2nd grade of memory block comprises k memory, and wherein k is the each bit number that produces of described linear feedback shift register.

19. method as claimed in claim 18 is characterized in that also comprising: each cycle, wherein k was greater than 1 to high bit place's displacement k bit, and k is the number of the described memory of described the 2nd grade of memory block of expression.

Images