A quick FPGA hack for you pseudo-random lovers out there

Long time ago, a friend showed me an article about cellular automata with chaotic behavior and their alleged randomness. One such CA called “Rule 30” produces pseudo random patterns using a simple compression rule. This is shown in the figure below (stolen from Wolfram Mathworld):

 

(each cell is a CA bit, the rows represent progress over time)

 

There is really nothing special with the randomness of Rule 30, it is completely useless for cryptographic applications. What makes Rule 30 a little interesting however, is the fact that it can be implemented very efficiently in FPGA: you will need 2-3 logical elements (4LUT + DFF) for each automaton.

 

Show us the code!

I found a Verilog implementation on Kryptoblog (a Swedish blog about security and stuff), but since I suffer from a severe case of the NIH syndrome, I decided to write my own in VHDL:

-- rule30.vhd: Cellular Automata DRNG - av/tube42.se, 2010
-- Using the same structure as rule30.v by Joachim Strömbergson at Kryptblog
library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

entity rule30 is
generic ( WIDTH : integer := 32);
port (
  CLK_I : in std_logic;
  RESET_N_I : in std_logic;
  DATA_I : in unsigned(WIDTH-1 downto 0);
  LOAD_I : in std_logic;
  NEXT_I : in std_logic;
  DATA_O : out unsigned(WIDTH-1 downto 0)
);
end entity;

architecture behav of rule30 is
  signal state : unsigned(WIDTH-1 downto 0);
begin
  -- sanity checks (should be in the entity, but I cant remember the syntax)
  assert WIDTH > 2 report "WIDTH must be greater than 2" severity failure;

  -- outputs
  DATA_O <= state;

  -- main logic
  rule30_proc: process(CLK_I, RESET_N_I)
    variable tmp : unsigned(WIDTH-1 downto 0);

    -- next state function for each cell
    function comp_next(d : unsigned( 2 downto 0)) return std_logic is
    begin
      case to_integer(d) is
        -- when 1 | 2 | 3 | 4 => return '1'; -- "correct" bit order
        when 4 | 2 | 6 | 1 => return '1'; -- reverse bit order, works with tb
        when others => return '0';
      end case;
     end function;

  begin
    if RESET_N_I = '0' then
      state <= (others => '0');
    elsif rising_edge(CLK_I) then
      if LOAD_I = '1' then
        state <= DATA_I;
      elsif NEXT_I = '1' then
        tmp := state rol 1; -- we use rotating variable to simplify the code
        for i in 0 to WIDTH-1 loop
          state(i) <= comp_next(tmp(2 downto 0));
          tmp := tmp ror 1;
        end loop;
      end if;
    end if;
  end process;
end behav;

This versions is slightly shorter (the Verilog code was about 1000 lines, mine is 60), uses generics for variable bit lengths and also follows the OpenCores coding standard for better readability. It is otherwise identical to the original Verilog code and even passes the testbench supplied with it – mostly because I was too lazy to write my own testbench

 

Ehh.. VHDL is all greek to us, show us the hardware!

The code above will be “synthesized” to logic gates using special software [In my case, I used Altera Quartus which is by the way free for you to experiment]. For example, the comp_next function in the code is synthesized to this:

 

This is really not rocket science, but may be fun for software engineers who haven’t seen a logic gate since they graduated university . In any case, here are some more screen dumps from Quartus (representing an 8-bit rule30 design):

 

 

How do I know your code really works?

You must always test your code, FPGA development is no different from software development in this regard . And you will put many hours into writing unit tests or you will have to put many more hours into debugging. Actually, testing is even more important when working with FPGAs. Compared to software development, the observability is next to zero and the development cycle is very slow, so you better get it right the first time. This is even worse when designing ASIC as they are very expensive to prototype.

 

The correct way to develop with FPGA or ASIC is to simulate your code against a large set of unit tests before even thinking about synthesizers and real hardware. In this particular case, I settled with the testbench from Kryptoblog. Using the (inhumanly expensive) simulator tool Aldec Riviera, I ran the testbench against my code and the original code to prove that everything works as intended:

 

 

(VHDL version on top, Verilog in middle and VHDL test results at the bottom)

 

As you can see in the waveform above, this simple constructs produces chaotic data which can be used as random numbers – if your standards are really low…

 

 

That’s all folks!