# 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;
endcase``````

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.