N is normally reserved for the state of the LFSR, M would be good to use for the number of random bits we wish to generate.
A standard LFSR generates 1 bit of random data, if consecutive bits of the LFSR are used they can be highly correlated, especially if taking a multi-bit value every clock cycle. To remove this correlation we can overclock the lfsr, say 4 times to generate 4 bits. The alternative to the this is to calculate the equations (feedback polynomials) that you would get for each bit. For every clock its internal state (as represented by the N-bits of the LFSR) would move forward 4 steps. Both techniques for over clocking or creating the feedback taps to move the state forward more than 1 step are known as leap-forward.
The code example in the question has been taken from a previous question and answer, this is an example of manually creating the extra feedback for a leap-forward lfsr.
The maths to do this can be done by generating the transition matrix and raising to the power of the number of steps we wish to move forward.
Quick 4-bit LFRS example: with transition matrix a:
a =
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 1
Feedback is XOR of the first and last bit, seen on last row of the matrix. All other rows are just a single shift. The output of this LFSR is good for one bit. Two bits would suffer from a high correlation, unless it was overclocked.
>> a^2
ans =
0 0 1 0
0 0 0 1
1 0 0 1
1 1 0 1
If we want two bits we need to square the transition matrix. It can be seen that the first two rows are a shift of two places and we require feedback for two places, ie we are moving the LFSR forward two states for every clock.
Just for confirmation if we wanted three bits:
a^3
ans =
0 0 0 1
1 0 0 1
1 1 0 1
1 1 1 1
The second code example in the previous question went on to parameterise the code so the leap forward calculations did not have to be manually created, skipping all of that lovely maths! However the approach used meant it could not be fully parameterised. Therefore I would like to revisit the example I gave for that question:
module fibonacci_lfsr(
input clk,
input rst_n,
output [4:0] data
);
wire feedback = data[4] ^ data[1] ;
always @(posedge clk or negedge rst_n)
if (~rst_n)
data <= 4'hf;
else
data <= {data[3:0], feedback} ;
endmodule
Now we want to parameterise it:
module fibonacci_lfsr#(
parameter POLYNOMIAL = 4'h9
)(
input clk,
input rst_n,
output [4:0] data
);
//AND data with POLYNOMIAL this
// selects only the taps in the polynomial to be used.
// ^( ) performs a XOR reduction to 1 bit
always @* begin
feedback = ^( POLYNOMIAL & data);
end
//Reseting to 0 is easier
// Invert feedback, all 1's state is banned instead of all 0's
always @(posedge clk or negedge rst_n)
if (~rst_n)
data <= 'b0;
else
data <= {data[3:0], ~feedback};
endmodule
A small step now, Just bring the shift outside of the synchronous loop to help with the step after.
always @* begin
data_next = data;
feedback = ^( POLYNOMIAL & data);
data_next = {data_next[3:0], ~feedback} ; //<- Shift and feedback
end
always @(posedge clk or negedge rst_n)
if (~rst_n)
data <= 'b0;
else
data <= data_next;
TL;DR
Now to control the leap-forward iterations, let the tools do the heavy lifting of multiplying the transition matrix.
module fibonacci_lfsr#(
parameter POLYNOMIAL = 4'h9,
parameter N = 4,
parameter BITS = 2
)(
input clk,
input rst_n,
output [BITS-1:0] random
);
reg [N-1:0] data;
reg [N-1:0] data_next;
reg feedback;
assign random = data[N-1:N-BITS];
always @* begin
data_next = data;
// Compiler unrolls the loop, calculating the transition matrix
for (int i=0; i<BITS; i++) begin
feedback = ^( POLYNOMIAL & data_next);
data_next = {data_next[N-2:0], ~feedback} ;
end
end
always @(posedge clk or negedge rst_n)
if (~rst_n)
data <= 'b0;
else
data <= data_next;
endmodule
Example on EDA Playground.
i++ is part of SystemVerilog. If you can only synthesis plain (pre-2009) Verilog then you will need to declare i as an integer and use i =i+1 in the for loop.
