Reciprocal
Hard · Sequential · SystemVerilog · VHDL
A premium problem. Subscribe to open it in the editor, run the testbench and see where your design lands.
Design a fixed-point reciprocal unit that computes 1/d by Newton-Raphson iteration.
Newton-Raphson finds a reciprocal without dividing: from an estimate x of 1/d, the step x ← x (2 - d x) roughly doubles the number of correct bits, so a good starting estimate reaches full precision in a few steps of multiplies and a subtraction.
d and recip_out are unsigned fixed-point values whose low FRAC_BITS bits are the fraction; with the defaults, 16'h4000 is 1.0 and 16'h2000 is 0.5.
A cycle with start high starts a computation on that cycle's d, abandoning any computation in progress. valid is low from the next cycle and high ITERATIONS cycles after that, when recip_out holds the result; both then hold until the next start. The result is 1/d to within two units in the last place: read as integers, recip_out is within ± 2 of ⌊ 2^2F / d ⌋, where F is FRAC_BITS.
The reciprocal fits in WIDTH bits only when, read as an integer, d is greater than 2^2F - W, where W is WIDTH; with the defaults, d above 16'h1000 (0.25). For any other d, including 0, overflow is high from the cycle after start until the next start, recip_out is not checked, and valid still rises on time.
resetn is a synchronous, active-low reset that clears recip_out, valid and overflow and abandons any computation.
- Arithmetic