Verilog Implementation of Linear Feedback Shift Register (LFSR) – Nonlinear Feedback Shift Register (Producing Pseudo-random Numbers)

Linear feedback shift register (LFSR)

In practice, the selection of random seeds determines the difference of pseudo-random sequences, which means the selection of random seeds is very important.

The most common way to generate pseudo-random numbers is to use a linear feedback shift register (LFSR).nA D trigger and several XOR gatesThe following pictures are made:

Where GN is the feedback coefficient, the value can only be 0 or 1, take 0 to show that there is no feedback path, take 1 to show that there is a feedback path; where the feedback coefficient determines the different algorithms for generating random numbers. The feedback function is expressed as y=a0x^0+a1x+a2x^2…The feedback function is linear, called the linear shift feedback sequence, otherwise it is called the nonlinear feedback shift sequence.

Which bits should be selected to carry out XOR in order to guarantee the longest cycle?，This is a very important question. A sequence of selected bits is called a tapped sequence. Theory shows that for LFSR to have the longest period, the polynomial plus 1 of the tapped sequence must be a primitive polynomial, which means that the polynomial is irreducible, such as。

nA D flip-flop can provide up to 2 ^ n – 1 states (excluding all zero states). In order to ensure that these states do not repeat, the choice of GN must satisfy certain conditions. The following is n=3, G₀=1，g₁=1,g₂=0,g₃=1As an example, we illustrate the characteristics of LFSR, which has the LFSR structure of the parameter.

　　Suppose that at the beginning, D₂D₁D₀=111(seed)，Then, when the clock arrived, there were:

　　D₂=D1_OUT=1；

　　D₁=D_{0_}OUT^D₂_OUT=0；

　　D0=D_{2_}OUT=1；

That is, D₂D₁D₀=101；Similarly, when another clock comes, you can get D.₂D₁D₀=001. ………………

Draw the state transition diagram as follows:

　　As can be seen from the graph, there are exactly 2^3-1=7 States, excluding all 0.

　　If you understand the above picture, you can get at least three conclusions:

　　1)The initial state is provided by SEED.

　　2)When the feedback coefficient is different, the state transition diagram obtained is also different; G must be guaranteed._n===1,Where else is the feedback?

　　3)DThe more the trigger, the more the state it generates, the more random it is.

 verilogRealization:

module RanGen(
    input               rst_n,    /*rst_n is necessary to prevet locking up*/
    input               clk,      /*clock signal*/
    input               load,     /*load seed to rand_num,active high */
    input      [7:0]    seed,     
    output reg [7:0]    rand_num  /*random number output*/
);


always@(posedge clk or negedge rst_n)
begin
    if(!rst_n)
        rand_num    <=8'b0;
    else if(load)
        rand_num <=seed;    /*load the initial value when load is active*/
    else
        begin
            rand_num[0] <= rand_num[7];
            rand_num[1] <= rand_num[0];
            rand_num[2] <= rand_num[1];
            rand_num[3] <= rand_num[2];
            rand_num[4] <= rand_num[3]^rand_num[7];
            rand_num[5] <= rand_num[4]^rand_num[7];
            rand_num[6] <= rand_num[5]^rand_num[7];
            rand_num[7] <= rand_num[6];
        end
            
end
endmodule

LFSR is used to guarantee the cycle length and balance of the key stream in the secret key analysis of communication system. The cryptographic properties of the key stream are determined by the nonlinear combination function to prevent it from being attacked.

Two, nonlinear feedback shift register

As shown below, there is not much to do now, so there are only a few simple concepts.