Shifting Verilog Values for CORDIC and Division

Welcome to the FPGA Cookbook.

This is part of a series of handy recipes to solve common FPGA development problems. Look out for more FPGA cookbook posts soon.

Efficiently shift a Verilog value into a specified range

Newton-Raphson division and CORDIC methods only work in a small domain. For example, Newton-Raphson division implementations usually expect the divisor to be in the range 0.5 to 1.0. For a large number of bits this requires many single shifts and comparisons. Instead we can create a priority encoder with casex to determine the most significant bit (MSB) and then apply a single shift as required.

Feedback to @WillFlux is most welcome.

The Case for Priority Encoding

The Verilog casex statement compares a value, ignoring x values.

Consider the following casex statement for determining the most significant bit of an 8-bit number:

casex (num)
    8'b1xxxxxxx:    bit = 7;
    8'b01xxxxxx:    bit = 6;
    8'b001xxxxx:    bit = 5;
    8'b0001xxxx:    bit = 4;
    8'b00001xxx:    bit = 3;
    8'b000001xx:    bit = 2;
    8'b0000001x:    bit = 1;
    8'b0000000x:    bit = 0;

Any bits compared with x are ignored. For example if num is:

  • 01010001 - the first case doesn't match, but the second does: setting bit = 6.
  • 00001111 - the first four cases don't match, but the fifth does: setting bit = 3.

Note also that the bit value is integer part of the logarithm of num: log2(num).

Shift It

Imaging we're trying to divide a fixed-point number by 3.25 using Newton-Raphson.

In fixed-point format 3.25 is 2 + 1 + 0.25:

bit     7 6 5 4 . 3 2 1 0
value   0 0 1 1 . 0 1 0 0

We test the divisor with our casex statement, getting the result 5: the most significant bit is at position 5. We subtract 3 from this because the binary point is after position 3. Thus we need to shift our binary point to the left by 2 bits:

bit     7 6 . 5 4 3 2 1 0
value   0 0 . 1 1 0 1 0 0

The bits are exactly the same, but our value now represents 1/2 + 1/4 + 1/16 or 0.8125, which is in the correct range of 0.5 to 1.0.

We need to left shift the other values involved in the calculation by 2 bits too. You'll be able to see this in action soon, when I publish the division recipe. Follow @WillFlux to hear when it's published.

In the meantime, check our my guide to using fixed-point numbers in Verilog. It demonstrates addition, subtraction, multiplication, and division by constant.