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.
The recursive case
For an encoder which is 2n-bits wide, we could join two 2n-1 bit wide priority encoders together like this.
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.
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?
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.
Thanks. This resolved the problem.
Verilog-2005 has the system task $clog2.
Pingback: Setting Recursion Limit in XST | You, Myself and Community
Pingback: Computing the Logarithm Base 2 | Beyond Circuits