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;

 

[Quirinus]

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...

In that case you might select the range for the random number generation and filter the output by minimum, maximum value and modulo/division (4 or 2). For 360 numbers the range is (modulo/division) 4 * 360 = 1440 which is covered by an 11-bit Galois LFSR noise generator or the range is (modulo/division) 2 * 360 = 720 which is covered by a 10-bit Galois LFSR noise generator. Filter output for values between 0 and 1439 (modulo/division 4) or 0 and 719 (modulo/division 2) and apply modulo/division by 4 or 2.

 

[neanton28]

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)

Wanted to thank for good explanation. FInally was able to get my hands to this in real fpga. Using now iCE40Up5K and syntesizer automatically inserts hardware multiplier. I ended up using 14 bit LFSR to get more entrophy and amount of required unique numbers went from 360 to 326. So minimal value is 68 and maximum 1372
[68, 72, 76, 80...1364, 1368, 1372]

It compiles well and runs on ice40. Here is code, just in case.

Spoiler: Code

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


entity offset_calculator is
    port(
        clk : in STD_LOGIC;
        valid : out STD_LOGIC;
        encode : in STD_LOGIC;
        decode : in STD_LOGIC;
        lfsr : in STD_LOGIC_VECTOR(13 downto 0);
        offset : out STD_LOGIC_VECTOR(10 downto 0)
        );
end offset_calculator;


architecture offset_calculator of offset_calculator is
    
    -- So minimal value is 68 and maximum 1372
    -- [68, 72, 76, 80...1364, 1368, 1372]
    
    -- let's have 14 bit lfsr. Max value = 16383
    -- Now scale value down 325/32767 = 0,01983
    -- Prescale to get round 0.01983* (2^14) = 325
    
    -- Let's say LFSR generated value 8200. Now multiply it on 325 = 2 665 000
    -- Now discard 14 LSBs
    -- 0010 1000 10___10 1010 0010 1000 = 2 665 000
    -- 10100010 = 162
    -- Now 162 * 4 + 68 = 716
    -- Seems middle of array 
    
    --0101 0001 00___11 1110 1011 1011
    
    constant MULTIPLY_CONST: natural  := 325;
    constant MULTIPLY_CONST_VECTOR: unsigned(15 DOWNTO 0)  := b"0000_0001_0100_0101"; --325
    
    constant GROUP_MULTIPLY_CONST: natural  := 4;
    constant GROUP_MULTIPLY_CONST_VECTOR: unsigned(15 DOWNTO 0)  := b"0000_0000_0000_0100"; --4
    
    constant ACTIVE_VIDEO_BYTES_IN_ROW: natural  := 1440;
    
    attribute syn_noprune : boolean;
    attribute syn_preserve : boolean;
    attribute syn_enum_encoding : string;
    attribute syn_encoding : string;
    
    type t_state is (INITIAL_STATE, STATE_CHECK, STATE_0, STATE_1, STATE_2, STATE_3, STATE_4, OTHERS_CASE);
    attribute syn_enum_encoding of t_state : type is "sequential";
    signal s_state : t_state;
    attribute syn_encoding of s_state : signal is "sequential";
    attribute syn_preserve of s_state : signal is true;   
    
    signal s_VALID : STD_LOGIC;
    signal s_TEMP_OFFSET : unsigned(10 downto 0);
    signal s_OFFSET : unsigned(10 downto 0);
    
    signal s_previous_lfsr : STD_LOGIC_VECTOR(13 downto 0);
    
    SIGNAL a_reg : unsigned(15 DOWNTO 0);
    attribute syn_preserve of a_reg : signal is true;
    SIGNAL b_reg : unsigned(15 DOWNTO 0);
    attribute syn_preserve of b_reg : signal is true;
    
    SIGNAL mult_out : unsigned(31 DOWNTO 0);
    
    
begin

    valid <= s_VALID;
    offset <= std_logic_vector (s_OFFSET);
    
    mult_out <= (a_reg * b_reg);
    
    process( clk )
    begin
        if (rising_edge(clk)) then
            case s_state is
                
                when INITIAL_STATE =>
                    s_state <= STATE_CHECK;
                    s_VALID <= '0';
                    s_OFFSET <= (others => '0');
                    s_previous_lfsr <= (others => '0');
                
                when OTHERS_CASE =>
                    s_DEBUG_1 <= not s_DEBUG_1;
                
                when STATE_CHECK =>
                    if (s_previous_lfsr /= lfsr ) then
                        s_state <= STATE_0;
                        s_VALID <= '0';
                    end if;

                when STATE_0 =>
                    s_previous_lfsr <= lfsr;
                    a_reg <= b"00" & unsigned(lfsr);
                    b_reg <= MULTIPLY_CONST_VECTOR;

                    s_state <= STATE_1;
                when STATE_1 =>
                    a_reg <= b"000_0000" & mult_out(22 downto 14);
                    b_reg <= GROUP_MULTIPLY_CONST_VECTOR;
                    s_state <= STATE_2;
                when STATE_2 =>
                    s_TEMP_OFFSET <= mult_out(10 downto 0) + 68;
                    s_state <= STATE_3;
                when STATE_3 =>
                    if (decode = '1') then
                        s_OFFSET <= ACTIVE_VIDEO_BYTES_IN_ROW - s_TEMP_OFFSET;
                    else
                        s_OFFSET <= s_TEMP_OFFSET;
                    end if;
                    s_VALID <= '1';
                    s_state <= STATE_4;
                    
                when OTHERS =>
                s_state <= OTHERS_CASE;
            end case;
            
        end if;
    end process;
    
end offset_calculator;