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;
      value = value-1;
      for (log2=0; value>0; log2=log2+1)
	value = value>>1;

    if (width == 2)
	assign valid = |decode;
	assign encode = decode[1];
    else if (width & (width-1))
      priencr #(1<<log2(width)) priencr ({1<<log2(width) {1'b0}} | decode,
	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};

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.

5 thoughts on “Recursive Modules

  1. 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. 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. Pingback: Setting Recursion Limit in XST | You, Myself and Community

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>