Recursive Modules

Many designers think that recursive techniques cannot be applied to hardware design. I’m not really sure where this misconception comes from. While it is true that in Verilog ‘95 you could not use recursion because the language did not support it, with Verilog 2001, recursion is possible. Recursion is really useful for describing hardware that has a tree structure. Let’s use a priority encoder as an example.

A priority encoder takes as input a bit vector and produces the bit number of the highest (or lowest) bit set and also an indication that some input bit was set. For example with an 8-bit encoder and an input of ‘b00101110, the output would be 5 because bit number 5 is the highest bit set.

The base case

For a 2-bit input, a priority encoder is pretty simple. The valid output is just the OR of the two input bits. The bit number output is just the higher input bit. In schematics it looks something like this.

Base implementation of a 2-bit priority encoder

A 2-bit priority encoder

The recursive case

For an encoder which is 2n-bits wide, we could join two 2n-1 bit wide priority encoders together like this.

Recursive implementation of a priority encoder

Recursive implementation of a priority encoder

Verilog code

So what does the code for this look like? It’s pretty simple. If the input vector is two bits wide, then we just implement the base case. Otherwise, if the width is not a power of two, then we pad out the input with zero bits to the next power of two width and then instantiate a power of two width encoder. If the width is a power of two, then we build the encoder out of two encoders half the size.


module priencr #(parameter width = 64)
  (
   input [width-1:0] decode,
   output [log2(width)-1:0] encode,
   output valid
   );

  function [31:0] log2;
    input reg [31:0] value;
    begin
      value = value-1;
      for (log2=0; value>0; log2=log2+1)
	value = value>>1;
    end
  endfunction

  generate
    if (width == 2)
      begin
	assign valid = |decode;
	assign encode = decode[1];
      end
    else if (width & (width-1))
      priencr #(1<<log2(width)) priencr ({1<<log2(width) {1'b0}} | decode,
                                         encode,valid);
    else
      begin
	wire [log2(width)-2:0] encode_low;
	wire [log2(width)-2:0] encode_high;
	wire valid_low, valid_high;
	priencr #(width>>1) low(decode[(width>>1)-1:0],encode_low,valid_low);
	priencr #(width>>1) high(decode[width-1:width>>1],encode_high,valid_high);
	assign valid = valid_low | valid_high;
	assign encode = valid_high ? {1'b1,encode_high} : {1'b0,encode_low};
      end
  endgenerate
endmodule

Wrap up

The only gotchas with recursion are vendor support. I have come across vendors who don’t think recursion is possible in Verilog 2001 because the standard doesn’t say it is specifically supported. The Verilog 2005 standard is very clear that recursion is allowed to help with this problem.

Recursion can be a very powerful way to express tree-like structures in hardware.

January 10, 2009 • Posted in: HDL, Verilog

5 Responses to “Recursive Modules”

  1. Igor Podolsky - November 10th, 2010

    Hello,

    I compiled your example in NCVerilog (version IUS82-s006) and receive the following error:
    ncvlog: *F,NOTOPL: no top-level unit found, must have recursive instances.
    ncverilog: *E,VLGERR: An error occurred during parsing.
    When I comment priencr instantiations in genearte block the compilation passes.

    Can you comment?

  2. admin - November 10th, 2010

    This is because you have priencr as a top-level module. The algorithm that NCVerilog uses to find the top level gets confused if the top-level module is recursive. If you instantiate priencr from another module and compile that as the top level everything should work.

  3. Igor Podolsky - November 14th, 2010

    Thanks. This resolved the problem.

  4. Janus - May 8th, 2013

    Verilog-2005 has the system task $clog2.

  5. Setting Recursion Limit in XST | You, Myself and Community - August 10th, 2013

    [...] http://www.beyond-circuits.com/wordpress/2009/01/recursive-modules/ [...]

Leave a Reply