Generate random number in range using LFSR

neanton28

Junior Member level 1
Joined
Jul 21, 2024
Messages
16
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Activity points
192
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:
Code:
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:
Code:
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;
 

I can think of several methods:
1) Use the number generated by the LFSR as an index into your constant array
2) Multiply the output of your LFSR by 4
 


I suggest you use 9 bit LFSR. This will generate 1~511
then scale each value down to 359/511.
The scaling can be done as multiplication e.g.
359/511 = 0.7025 so pre-scale up by 2^10 to become round(0.7025*2^10) ~= 719
Now multiply each LSFR data by 719 and discard 10 LSBs.
Finally add two zeros as extra LSBs (this means x4)
 

Wow. You couldn't come up with a more complex, resource intensive method?
--- Updated ---

Wow. You couldn't come up with a more complex, resource intensive method?
--- Updated ---

Wow. You couldn't come up with a more complex, resource intensive method?
 

You got absolute zero idea about this resource:
9 registers for LFSR
9 x 9 multiplier (for 719 scale value. )
The rest is bit discard, insert zeros.

no memory, no logic to reset LFSR if value exceeds limits
May be you misunderstood my calculations, it is meant precalculate for FPGA as scale factor 719


Read carefully the post and my suggestion. You need to be respectful to people not an arrogant dictator.
 

If you take the output of an LFSR and add two trailing zeroes, you’ll get what the OP needs. No need to multiply by 719. Maybe you should read what the OP actually asked for.
 

If you take the output of an LFSR and add two trailing zeroes, you’ll get what the OP needs. No need to multiply by 719. Maybe you should read what the OP actually asked for.
but he wants constrain the range to 1436, not more...
 

Some attempt to implement it
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');

    --type t_int_array is array(natural range 0 to 4) of natural range 0 to 1436;
    --constant possible_values : t_int_array :=(4,8,12,16,1436);
    
    signal s_lfsr : STD_LOGIC_VECTOR(8 downto 0) := (others => '1');   
    signal linear_feedback :std_logic;
    signal s_temp : unsigned(17 downto 0);
begin
    result <= s_result;
    
    linear_feedback <= s_lfsr(8) xor s_lfsr(3);
    
    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;
                
                s_temp <= unsigned(s_lfsr) * 719;
            end if;
        end if;
    end process;   
end offset_generator;

Here is quick simulation:



So let's take third output for example.

s_LFSR has value 0x1F8 (504)
s_temp is 0x19AC4 (105156)

It outputs some wrong numbers. In this case 504*719=362376 (0x58788)
 

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

Hi,

the problem with multiplication is that some numbers are preferred. In other words: you don´t get equal distribution.

Klaus

Added: and the random numbers are only "pseudo random". This means the order is always the same. It repeats.

Thus: you need to answer (yourself):
* is non equal distribution OK for your application
* is it OK if the order of the numbers repeat (equally)

In numbers: KAZ´s solution gives an equal row of 511 results (it repeats every 511 ticks)
Within these 511 results .. there are 359 different values. Thus 152 values with double occurance and 207 values with single occurance.

Klaus
 
Last edited:

That is true. LFSR of 9 bits generates pseudo numbers repeating every 511 values.
scaling down to 359 will lead to further bias of distribution.
The seed may be changed every 511runs or if indeed the task requires better randomness then the designer can produce look-up-table from say Matlab, store it.
 
Last edited:

Hi, it's ok if it will repeat since it's based on seed. Here is some information what I want to do:

There are two fpga boards: Board_1 and Board_2.
Board_1 is used for data permutation, and Board_2 is used for reverse permutation (Scramble/Descramble)
Each data package consist of 288 lines for each of which we have to apply one number from array[360] (4,8,12,n+4,...1436)

For each Board_1 and Board_2 I'll set same seed during programming. Then based on this seed both boards will be able to produce same sequence of 288 permutation numbers, like: (18, 4, 1432,...22)

So we only need 288 random numbers from that array[360](4,8,12,n+4,...1436)


And yes, I understand that some numbers will have not equal distribution. Prior to these LFSR topic, I was generating array of permutated values in Java and writing it into RAM of FPGA. And now thinking how to make this pseudo-random generation on FPGA itself based on some user-seed
 
Last edited:

Hi, it's ok if it will repeat since it's based on seed.
The seed just modifies the starting point ... but it does not modify the order.

Board_1 is used for data permutation, and Board_2 is used for reverse permutation (Scramble/Descramble)
if it is for "decrypting" for security reasons ... the given algorithm is not that secure. It is nthong better than having an 511 array with 359 different numbers. (some are double occurance)
Especially the double occurance makes it much harder to descramble, because you can´t know what the origin of this number is.

--> I recommend to use paper and pencil or excel or something else to verify whether your idea does work or not.

Klaus
 

For first implementation it's ok to not have perfect distribution. And such low amount of possible values (360) is the limitation of algorithm for analog television (CVBS). There increasing steps for more complex permutation makes picture quality worse during descrambling.
We can make LFSR longer than 9 bit, let's say 18 bits. And so seed will also consist of 18 bits (524287)
--- Updated ---

I recommend to use paper and pencil or excel or something else to verify whether your idea does work or not.
Right now I generate two arrays[360] in java and then use them in fpga's. One array is for scrambling, other for descrambling. Idea itself works, image is scrambled and then descrambled with appropriate quality loose.
 

Right now I generate two arrays[360] in java and then use them in fpga's. One array is for scrambling, other for descrambling. Idea itself works, image is scrambled and then descrambled with appropriate quality loose.
My concern is the "double occurance". Did you focus on this ... with your test?

Let´s say your genereated tabel looks like: {14, 22, 129, 8, 76, 14, 111, ...}
Mind the double occurance of {14}!

I don´t understand the term "quality lose" here. On a digial system there should be no quality loss at all.

Klaus
 

Have not yet tested double occurrence, but it should not have great impact I suppose.

And that's the point of not using AES encryption or other. Data is transmitted over analog channel (analog television/CVBS/yellow RCA connector on TV/DVD).

Scheme is next:
1) ADC decodes analog signal from camera into digital BT.656 packets
2) They are stored in line buffer inside FPGA's RAM
3) FPGA outputs data from this line buffer in mixed way to DAC. And numbers from array[360] are indexes for way how to permutate bytes in line
4) This permutated BT.656 data flows to DAC which transforms it to analog signal (CVBS)
5) On other end there is Board_2 which will do reverse operation to restore original image

And since it's analog signal, it does not have any redundancy like we have in digital interfaces: usb/ethernet/hdmi...

And this ADC/DAC conversions both with that BT.656 has format YCbCr 4:2:2 lead to loosing quality



 
Last edited:

strictly speaking, what you are achieving with your encryption is only a symbol substitution. this is hardly secure. there is a reason why we use standards in cryptography and not reinvent the wheel. Consider using a stream cipher, they can be lightweight.
 

Yes, you are right. It's scrambling/descrambling and not proper encryption. But this is limitation of analog video. Stream cipher will require that transmitted data is the same on receiving end. But with analog it can not be guaranteed, since it will be also transmitted over air.

There are digital video transmitter systems which have all this redundancy and error recovery. For that there is no need to invent anything, encryption is already built-in
 

And this ADC/DAC conversions both with that BT.656 has format YCbCr 4:2:2 lead to loosing quality
your thread topic was generating random numbers ... using digital techniques, FPGA ... in so far the "loss of quality" is not related to the topic, and we don´t need to discuss ... we don´t even need to know about. (Still it might be another problem of your application). Correct me if I´m wrong.

****
Back to the scrambling descrambling.

I understand the concept (at least in parts) .... but this is a pure digital part. The problem with your descrambler is, that you don´t get the same digital numbers than you scrambled. The signal flow is something like this.

input_data --> scrambled_data_Tx --> analog --> digital --> scrambled_data_Rx --> descrambler --> picture

If so, then you need to be aware that the scrambled_data_tx ... are not the same as scrambled_data_Rx
Mind: not because of loss of quality, but because of timing, phase shift, filtering, offset, noise, gain, nonlinearity.
So how is your concept to descramble the data stream on the Rx side?

Lets say you get unscrambled 123 ... then scramble it to 14 .. then transmit DA -> AD to 17 .... how do you get back the 123?
There will be small differences in the scrambled on the Rx side. Maybe +/- a couple of LSBs. .. because 17 now may be descrambled to 3 (rather far from 123)

***
I´m asking because I´m curious and have no idea how you solve it.
But if you are sure your concept can handle the problem ... then we don´t need to waste time to discuss it in detail.

Klaus
 

Yes, generating numbers was original topic, but seems in discussion I had to provide more information about it.

Now why it works.
LFSR will be reset with seed after 288 values on both boards. BT.656 format of video has special markers that allow to find what frame is currently being sent (odd/even). And on this change odd/even I am resetting internal counter now which points to array[360] with permutation indexes
 

Cookies are required to use this site. You must accept them to continue using the site. Learn more…