Generate random number in range using LFSR

[neanton28]

Greetings! I am trying to find best way for random generator in specific range and was wondering what are the best practices for now.
I have array of 360 numbers each of one is +4 of previous:

constant possible_values : t_int_array :=(4,8,12, n+4...1432,1436);

And I'd like to have some function that accepts seed/code and output numbers from this array in random way. Numbers may also be not initially stored in array, but also generated in some function during execution. This will save some on-chip RAM.

For now I am still looking for proper way of such limitation pure LFSR, since it will just generate me random numbers, and not what I need. Maybe there is some graceful way to do it, to not add conditions like (if result > 1436 then generate again)

That's some example vhdl block I created for demonstration:

library IEEE;
use IEEE.std_logic_1164.all;

entity offset_generator is
     port(
         clk : in STD_LOGIC;
         reset : in STD_LOGIC;
         seed : in STD_LOGIC_VECTOR(32 downto 0);
         result : out STD_LOGIC_VECTOR(10 downto 0)
         );
end offset_generator;



architecture offset_generator of offset_generator is
signal s_result : STD_LOGIC_VECTOR(10 downto 0) := (others => '0');

    type t_int_array is array(natural range 0 to 360) of natural range 0 to 1436;
    constant possible_values : t_int_array :=(4,8,12,16,....,1432,1436);
    
    signal s_seed : STD_LOGIC_VECTOR(32 downto 0) := (others => '0');
    
          
    function GET_RANDOM (seed : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
    begin
        return INSERT_IMPLEMENTATION_HERE;
    end;
    
begin
    result <= s_result;
    
    process( clk )
    begin
        if (rising_edge(clk)) then
            if (reset = '1') then
                s_seed <= seed;
            else
                s_result <= GET_RANDOM(s_seed);
            end if;
        end if;
    end process;   
end offset_generator;

 

[KlausST]

Hi,

I understand this all is done on the Tx side.
But I have no clue how it can be done on the Rx side.
Scrambled BT.656 .. especially when processed A->D->A .. you lost the markers ... in my opinion.
Even the markers are scrambled.

But again: I don´t need to understand you whole process ....

Klaus

 

[neanton28]

504 * 719 = 362376
Divide by 1024 (discard 10 LSBs)= 353 (or 354 if rounded)
Now output adding two zero LSBs
353 * 4= 1412

Spoiler: Code

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

entity offset_generator is
     port(
         clk : in STD_LOGIC;
         reset : in STD_LOGIC;
         seed : in STD_LOGIC_VECTOR(8 downto 0);
         result : out STD_LOGIC_VECTOR(10 downto 0)
         );
end offset_generator;

architecture offset_generator of offset_generator is
    signal s_result : STD_LOGIC_VECTOR(10 downto 0) := (others => '0');
    signal s_lfsr : STD_LOGIC_VECTOR(8 downto 0) := (others => '1');  
    signal linear_feedback :std_logic;
    --signal s_temp : unsigned(18 downto 0);
   
    signal s_stub_lfsr : STD_LOGIC_VECTOR(8 downto 0) := b"1_1111_1000"; --504
   
    signal s_temp_lfsr : unsigned(8 downto 0);
    signal s_x719_lfsr : unsigned(18 downto 0);
    signal s_divided_lfsr : unsigned(8 downto 0);
    signal s_x4_lfsr : unsigned(10 downto 0);
begin
    result <= s_result;
    linear_feedback <= s_lfsr(8) xor s_lfsr(3);
    --s_temp <= to_unsigned( ((to_integer( unsigned(s_lfsr) ) * 719) / 1024) * 4, 19);

    s_temp_lfsr <= unsigned(s_stub_lfsr);
   
    s_x719_lfsr <= s_temp_lfsr * 719; --"101_1000_0111_1000_1000"  504*719=362376
   
    s_divided_lfsr <= s_x719_lfsr(18 downto 10); --"1_0110_0001" division 362376/1024=353
   
    s_x4_lfsr <= s_divided_lfsr & b"00"; -- 353*4=1412 multiply by 4
   
    process( clk )
    begin
        if (rising_edge(clk)) then
            if (reset = '1') then
                s_lfsr <= seed;
            else
                s_lfsr(8 downto 0) <= s_lfsr(7 downto 0) & linear_feedback;
            end if;
        end if;
    end process;  
end offset_generator;

When I define multiplications in one line, in simulation it works:

s_temp <= to_unsigned( ((to_integer( unsigned(s_lfsr) ) * 719) / 1024) * 4, 19);

But when I split it in several operations for clarity, I get error on compilation and simulation at line:

s_x719_lfsr <= s_temp_lfsr * 719; --"101_1000_0111_1000_1000"  504*719=362376

Message: Warning: COMP96_0367: offset_generator.vhd : (33, 17): Improper array length (18). Expected length is 19.

This look weird because all dimensions match

--- Updated Oct 29, 2024 ---

Hi,

I understand this all is done on the Tx side.
But I have no clue how it can be done on the Rx side.
Scrambled BT.656 .. especially when processed A->D->A .. you lost the markers ... in my opinion.
Even the markers are scrambled.

But again: I don´t need to understand you whole process ....

Klaus

Ah, no worries. I scramble not whole line, but only active video part. This way all markers stay in their position.
Format of BT.656 is like this: EAV|80|10|80|10...|SAV|01|02|03|04|...

EAV - is start marker of line
80|10| - is sequence of blanking bytes
SAV - is start of active video bytes
01|02|03|04 - is sequence of 1440 bytes of actual video data. I scramble only this part, making it like |200|201|202|....|1436|1440|01|02|03|04|...|197|198|199|

--- Updated Oct 29, 2024 ---

Hm, I changed decimal 719 to binary format b"10_1100_1111" and error went away.
Here is result of simulation. All numbers in decimal format:

Works well, thanks! Now will try to add such code to fpga project and to synthesize. Curious how many LUTs it will take on fpga without hardware multiplier.

So for current 9-bit LFSR it requires 9x10 bit multiplier. Since 719 takes 10 bits

--- Updated Oct 29, 2024 ---

I am curious if there are some universal rules or tips of how to create such number generators for different scales/values. I bet I am not the first who tries to implement this pseudo-random generator among fixed set of values

 

[kaz1]

I am curious if there are some universal rules or tips of how to create such number generators for different scales/values. I bet I am not the first who tries to implement this pseudo-random generator among fixed set of values

I haven't heard of constrained LFSR. The scaling rule can be simplified as:
In your case you might just apply 359/511 as 359/512 if resolution is enough. Thus 359 is the scale factor and discard 9 lsbs (LFSR length)

 

[std_match]

Instead of an LFSR, you can use a block RAM with initialized data (a ROM). It is easy to constrain the data to any range.

 

[kaz1]

Instead of an LFSR, you can use a block RAM with initialized data (a ROM). It is easy to constrain the data to any range.

The OP does not want use ram. Moreover, rams have to be populated per each seed, yet the requirement is changing the seed. True, rams can allow control of randomness through using pre-computed LUTs populated from software tools.

 

[KlausST]

rams have to be populated per each seed

I don´t think so.
The seed in your solution is nothing but a "offset" for a array with fixed values.
The numbers and the order is not altered by the seed, just the whole array gets shifted.
So the array even could be in ROM.

Klaus

 

[kaz1]

I don´t think so.
The seed in your solution is nothing but a "offset" for a array with fixed values.
The numbers and the order is not altered by the seed, just the whole array gets shifted.
So the array even could be in ROM.

Klaus

I don't have seed... the original code has seed input. Given 511 ticks and changing start location of sequence in runtime could imply different values relative to start of reset and this will change randomness. The OP may try to verify that.

 

[KlausST]

Hi,

correct me if I´m wrong. But I think most (all?) LFSR need a seed. It may be fixed, it may be variable, but most LFSR don´t work with a start of all 0s.

I agree, the seed changes the start location ... it will not change the "randomness" of the LFSR since the order stats the same.
I could agree that it changes the randomness of the whole system ... but not really in the meaning of increasing a security level.

As an example:
with one seed: the ouput of the LSFR my be {167, 13, 1, 88, 43, 112, 69, 17, 99, 201,...)
with a different seed the output may be: [43, 112, 69, 17, 99, 201,..}

Klaus

 

[neanton28]

Instead of an LFSR, you can use a block RAM with initialized data (a ROM). It is easy to constrain the data to any range.

Right now I use block RAM that shores this random numbers. But numbers itself are generated on PC in Java sample program. And I would like to make such interface in FPGA , let's say UART where user will write seed/code and FPGA will generate all this numbers. It's needed to make easy and reproducible configuration for multiple boards. Think of it as a PIN code or password.

RAM is not issue, my FPGA have enough of it. But generation of numbers...

 

[kaz1]

Hi,

correct me if I´m wrong. But I think most (all?) LFSR need a seed. It may be fixed, it may be variable, but most LFSR don´t work with a start of all 0s.

I agree, the seed changes the start location ... it will not change the "randomness" of the LFSR since the order stats the same.
I could agree that it changes the randomness of the whole system ... but not really in the meaning of increasing a security level.

As an example:
with one seed: the ouput of the LSFR my be {167, 13, 1, 88, 43, 112, 69, 17, 99, 201,...)
with a different seed the output may be: [43, 112, 69, 17, 99, 201,..}

Klaus

That is true, same sequence but different start. If I time it relative to some data block it will be different for some section. Not that efficient.

--- Updated Oct 30, 2024 ---

Right now I use block RAM that shores this random numbers. But numbers itself are generated on PC in Java sample program. And I would like to make such interface in FPGA , let's say UART where user will write seed/code and FPGA will generate all this numbers. It's needed to make easy and reproducible configuration for multiple boards. Think of it as a PIN code or password.

RAM is not issue, my FPGA have enough of it. But generation of numbers...

That is a U-turn.
So you want
A fixed rom containing nicely randomised table and
then randomise the address from somewhere.

You may also have more ROM tables and address them randomly or invert data content or change endianness.
So much to play with. It all depends on the purpose and you are best to research.

 

[neanton28]

Hi,

correct me if I´m wrong. But I think most (all?) LFSR need a seed. It may be fixed, it may be variable, but most LFSR don´t work with a start of all 0s.

I agree, the seed changes the start location ... it will not change the "randomness" of the LFSR since the order stats the same.
I could agree that it changes the randomness of the whole system ... but not really in the meaning of increasing a security level.

As an example:
with one seed: the ouput of the LSFR my be {167, 13, 1, 88, 43, 112, 69, 17, 99, 201,...)
with a different seed the output may be: [43, 112, 69, 17, 99, 201,..}

Klaus

And are there any known approaches how randomness can be increased? But same way it to be reproducible based on seed.

--- Updated Oct 30, 2024 ---

That is true, same sequence but different start. If I time it relative to some data block it will be different for some section. Not that efficient.

--- Updated Oct 30, 2024 ---

That is a U-turn.
So you want
A fixed rom containing nicely randomised table and
then randomise the address from somewhere.

You may also have more ROM tables and address them randomly or invert data content or change endianness.
So much to play with. It all depends on the purpose and you are best to research.

I would not say a U-turn. It's same as first message in topic. Main goal is to get random sequence of numbers from array based on seed, so on other board with same seed it would produce same result

 

[kaz1]

And are there any known approaches how randomness can be increased? But same way it to be reproducible based on seed.

--- Updated Oct 30, 2024 ---

I would not say a U-turn. It's same as first message in topic. Main goal is to get random sequence of numbers from array based on seed, so on other board with same seed it would produce same result

The satellite TV (DVB-s) uses PRBS generator at Tx and also same at Rx. It is meant for energy dispersal (not security issues). They use fixed seed by standards but you can modify seed protocol.
In principle the randomness is limited by shift register of 9 bits + 2 zeros, the best way to efficiently randomise is configure different LUTS at start up for Tx and Rx. The LUTs will be prepared in files say some 16 tables and choose one. At system reset you can change the LUT file and download if run-time update is supported.

 

[neanton28]

The satellite TV (DVB-s) uses PRBS generator at Tx and also same at Rx. It is meant for energy dispersal (not security issues). They use fixed seed by standards but you can modify seed protocol.
In principle the randomness is limited by shift register of 9 bits + 2 zeros, the best way to efficiently randomise is configure different LUTS at start up for Tx and Rx. The LUTs will be prepared in files say some 16 tables and choose one. At system reset you can change the LUT file and download if run-time update is supported.

In this example then we'll have 16 tables of 360 numbers, so it will lead only to possible 16 combinations/codes if I understand right.

And if I'll increase shift register to let's say 16 bits or even more. Suppose it should increase randomness based on seed, or it will not have such impact?

 

[KlausST]

And are there any known approaches how randomness can be increased? But same way it to be reproducible based on seed.

for me the simplest approach would be to increase the LFSR bit width.

Now it is 9 bits. usable numbers 1...511
You can just make it 24 bits wide (ant the seed also 24 bits) ... and use any 9 bits you like to.
Then you have 15 redundant bits making 32768 different orders of the random numbers.

There are other approaches (with god and bad) ... it is just an example how to improve the existing system on randomness.

And these 15 additional bits really don´t cost much of an FPGA´s resources.

Klaus

 

[neanton28]

for me the simplest approach would be to increase the LFSR bit width.

Now it is 9 bits. usable numbers 1...511
You can just make it 24 bits wide (ant the seed also 24 bits) ... and use any 9 bits you like to.
Then you have 15 redundant bits making 32768 different orders of the random numbers.

There are other approaches (with god and bad) ... it is just an example how to improve the existing system on randomness.

And these 15 additional bits really don´t cost much of an FPGA´s resources.

Klaus

So even not adjust scale of whole 24 bits lfsr, but only take some static 9 bits from it, like this?

signal : LFSR unsigned(23 downto 0);
signal: LFSR_to_use_in_computation(8 downto 0);

LFSR_to_use_in_computation <= LFSR(17 downto 9);

 

[kaz1]

So even not adjust scale of whole 24 bits lfsr, but only take some static 9 bits from it, like this?

signal : LFSR unsigned(23 downto 0);
signal: LFSR_to_use_in_computation(8 downto 0);

LFSR_to_use_in_computation <= LFSR(17 downto 9);

Your purpose is some sort of security that no one can easily detect the pattern yet the Rx should be able to know the pattern. There are very specialised algorithms for encryption.
If you want a basic yet good algorithm the yes use 24 bits or so then select 9 bits also based on agreed randomiser. According to your range you still need to scale down as before.

 

[std_match]

I don't think it works to have a long LFSR and use a subset of the bits for this application.
The same number can appear twice before other numbers have appeared.

 

[KlausST]

So even not adjust scale of whole 24 bits lfsr, but only take some static 9 bits from it, like this?

Again: this is just an example to expand the existing 9 bit LFSR solution for more random order. Quick and dirty.

There might be other even better solutions.

--- Updated Oct 30, 2024 ---

I don't think it works to have a long LFSR and use a subset of the bits for this application.
The same number can appear twice before other numbers have appeared.

This is true ....
But this is what I claimed to be the problem with the existing 9 bit solution, too. Some numbers come once, some come twice.
OP said this is not a problem.
I don´t have the knowledge to say whether the solution fits the application or not. I already have claimed my doubts.

Klaus

 

[Quirinus]

An example of a configurable periodic noise generator - randomizer.v - (pseudo random) can be found at https://github.com/krynentechnology/soneo.

 

[neanton28]

An example of a configurable periodic noise generator - randomizer.v - (pseudo random) can be found at https://github.com/krynentechnology/soneo.

If I understand right, it generates whole set of random numbers, while I am looking for numbers among array. In my case: 4,8,12,16... And also way how to change it in case I need some other values, like : 12,14,16...