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
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; endcase
Any bits compared with
x are ignored. For example if
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
Imaging we're trying to divide a fixed-point number by
3.25 using Newton-Raphson.
In fixed-point format
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.