Integer Cube Root in Verilog

 3r33555. 3r3-31.

Introduction

3r33542.  3r33555. We have created a number for the binary algorithm. This code had been tested on the Cyclone IV FPGA board. How you works. 3r33542.  3r33555. 3r33542.  3r33555. Github link: Cube root 3r33542.  3r33555. 3r314. 3r3305. 3r33542.  3r33555.

What is a cube root?

3r33542.  3r33555. Cube root of a number y is a number x such that
$$ display $$ x ^ 3 = y $$ display $$
3r3365. 3r33542.  3r33555. 3r33542.  3r33555. Examples: 3r33542.  3r33555. 3r362.
$$ display $$ sqrt[3]{8} = 2 sqrt[3]{27} = 3 sqrt[3]{64} = 4 $$ display $$
3r3365. 3r33542.  3r33555. So, in our implementation we use an integer cube root . 3r33542.  3r33555. It means that a number of x is an another integer number a such that: 3r34235.  3r33555. 3r362.
$$ display $$ a ^ 3 leqslant x, (a + 1) ^ 3 geqslant x $$ display $$
3r3365. 3r33542.  3r33555. Examples: 3r33542.  3r33555. 3r362.
$$ display $$ sqrt[3]{26} = 2 sqrt[3]{28} = 3 sqrt[3]{63} = 3 sqrt[3]{65} = 4 $$ display $$
3r3365. 3r33542.  3r33555.

Main Logic

3r33542.  3r33555. Integer Cube Root in Verilog 3r33542.  3r33555. 3r33542.  3r33555. The main module is the number during input. 3r33542.  3r33555. It has 4 possible actions:
 3r33555. 3r33542.  3r33555.
 3r33555. 3r3394. multiply increment by 10
 3r33555. 3r3394. divide increment by 10 (increment is not less than 1)
 3r33555. 3r3394. increase number 3r395.  3r33555. 3r3394. decrease number
 3r33555.
3r33542.  3r33555.
Main module [/b] 3r33399. 3r33400. 3r3013. module cube_root (3r3–3555. input inc, 3r3–3555. input sub, 3r3–3555. input next, 3r3–3555. input prev, 3r3–3555. input enter, 3r3–3555. input ckk, 3r3–3555. output ckk, 3r3–3555. ); 3r33555. 3r33555. reg signed[31:0]exit; 3r33555. wire ready; 3r33555. wire[31:0]res; 3r33555. reg zero = 0; 3r33555. 3r33555. //input //3r33555. 3r33555. reg inc1 = 0; 3r33555. reg next1 = 0; 3r33555. reg prev1 = 0; 3r33555. reg sub1 = 0; 3r33555. reg enter1 = 0; 3r33555. reg[31:0]decimal = 1; 3r33555. 3r33555. //////////
3r33555. reg[31:0]to_display; 3r33555. 3r33555. display_bcd display (
.clk (clk),
.value (ready == 0? exit: res),
.control (control), 3r33555. .leds (leds) 3r33555.); 3r33555. 3r33555. calculate calc (
.clk (clk),
.ready_to_calc (~ enter), 3r33555. .num (exit),
.ready (ready),
.res (res)
); 3r33555. 3r33555. always @ (posedge clk)
begin
if (enter == 1) begin 3r335555. if ((inc1 == 1'b0) && (~ inc == 1'b1)) begin 3r35555. exit = exit + decimal; 3r33555. end
inc1 = ~ inc; 3r33555. 3r33555. if ((sub1 == 1'b0) && (~ sub == 1'b1)) begin 3r35555. if (exit> 0) begin
exit = exit - decimal; 3r33555. end
end
sub1 = ~ sub; 3r33555. 3r33555. if ((next1 == 1'b0) && (~ next == 1'b1)) begin 3r35555. decimal = decimal * 10; 3r33555. end
next1 = ~ next; 3r33555. 3r33555. if ((prev1 == 1'b0) && (~ prev == 1'b1)) begin
if (decimal> = 1 && decimal <= 9) begin
decimal = 1; 3r33555. end else begin == 1'b1) begin 3r33555. Exit = 0; 3r33555. Decimal = 1; 3r33555. End 3r33555. End 3r33555. End 3r33555. 3r3555. Endmodule 3r33636. 3r33537. 3r33535.  3r33555. 3r? 3551. 3r? 3551. 3r33542.  3r33555. In the main module cube_root there are also two other modules: calculate and display_bcd . During the program execution. 3r33542.  3r33555. 3r33542.  3r33555. Now, let's understand how they work. 3r33542.  3r33555. 3r33542.  3r33555.

Calculate module

3r33542.  3r33555. Calculation module uses a binary search algorithm. ready variable to 1. it is a signal to display the answer. 3r33542.  3r33555. 3r33542.  3r33555.
Calculate module [/b] 3r33399. 3r33400. 3r3013. 3r33555. module calculate (3r33555. input clk, 3r33555. input ready_to_calc, 3r33555. input[31:0]num, 3r33555. output reg ready, 3r33555. output[31:0]res
); 3r33555. 3r33555. integer mid; 3r33555. integer start; 3r33555. integer final; 3r33555. integer counter; 3r33555. 3r33555. assign res = mid; 3r33555. 3r33555. always @ (posedge clk)
begin
if (ready_to_calc == 1) begin
if (ready == 0) begin 3r33555. mid = (start + final) /2; 3r33555. 3r33555. if ((mid * mid * mid)> num) begin
final = mid; 3r33555. end else begin
start = mid; 3r33555. end
3r33555. if (counter == 27) begin
ready = 1; 3r33555. counter = 0; 3r33555. end else begin
counter = counter + 1; 3r33555. end
end
end else begin
final = 465; 3r33555. start = 0; 3r33555. ready = 0; 3r33555. counter = 0; 3r33555. end
end
3r33555. endmodule 3r33555. 3r33636. 3r33537. 3r33542.  3r33555. 3r? 3551. 3r? 3551. 3r33542.  3r33555. 3r3302. Why this module does not exactly 27 iterations? [/b] 3r33542.  3r33555. - Maximum input number is 99999999. So, the maximum possible number of iterations is
$ inline $ log_??? = ??? approx 27 $ inline $
3r33542.  3r33555. 3r3302. Why is upper bound of binary search is initialized by 465? [/b] 3r33542.  3r33555. - Because it can be a result.
$ inline $ sqrt[3]{99999999} approx $ 464 inline $
3r33542.  3r33555. 3r33542.  3r33555.

Display module

3r33542.  3r33555. This module is responsible for the performance. It uses eight eight-segment displays and has been manipulated by 16 pins. Where 8 pins are in charge and they are distinct digits. 3r33542.  3r33555. 3r33542.  3r33555. So, we want to display this module. Then, it passes this value to the Binary_to_BCD module which converts binary number to the binary coded decimal using Double Dabble algorithm . After that, converted value becomes easy to display. 3r33542.  3r33555. 3r33542.  3r33555.
Display module [/b] 3r33399. 3r33400. 3r3013. module display_bcd (
input clk,
input[31:0]value,
output[7:0]control,
output[7:0]leds
); 3r33555. 3r33555. 3r33555. bcd_convert # (3? 8) bcd_convert (3r33555. .i_Clock (clk), 3r355555. 3r33555.); 3r33555. 3r33555. integer delay = 0; 3r33555. integer final_bcd; 3r33555. 3r33555. reg[2:0]ctrl = 0; 3r33555. reg[4:0]digit; 3r33555. 3r33555. wire bcd_ready; 3r33555. wire[31:0]bcd_number; 3r33555. 3r33555. wire[31:0]digits; 3r33555. assign digits = final_bcd; 3r33555. 3r33555. wire[31:0]value_temp; 3r33555. assign value_temp = value; 3r33555. 3r33555. 3r33555. assign control = ~ (1 ctrl); 3r33555. 3r33555. assign leds = ~
(digit == 0? 8'b00111111:
(digit == 1? 8'b00000110:
(digit == 2? 8'b01011011:
(digit == 3? 8'b01001111:
(digit == 4? 8'b01100110: 3r33555. (Digit == 5? 8'b01101101:
(Digit == 6? 8'b01111101:
(Digit == 7? 8'b00000111:
(Digit == 8? 8'b01111111: 3r3-3555. (Digit == 9? 8'b01101111: 3r3-3555. 8'b00000000)))))))))); 3r33555. 3r33555. 3r33555. always @ (posedge clk)
begin
3r33555. if (bcd_ready)
final_bcd = bcd_number; 3r33555. 3r33555. case (ctrl) 3r33555. 0: digit = digits[3:0]; 3r33555. 1: digit = digits[31:4]? digits[7:4]: ten; 3r33555. 2: digit = digits[31:8]? digits[11:8]: ten; 3r33555. 3: digit = digits[31:12]? digits[15:12]: ten; 3r33555. 4: digit = digits[31:16]? digits[19:16]: ten; 3r33555. 5: digit = digits[31:20]? digits[23:20]: ten; 3r33555. 6: digit = digits[31:24]? digits[27:24]: ten; 3r33555. 7: digit = digits[31:28]? digits[31:28]: ten; 3r33555. endcase 3r33555. 3r33555. delay = delay + 1; 3r33555. 3r33555. if (delay == 10000) 3r33555. ctrl = ctrl + 1; 3r33555. 3r33555. end
3r33555. endmodule 3r33536. 3r33537. 3r33542.  3r33555. 3r? 3551.
3r???.  3r33555.
BCD convert [/b] 3r33399. 3r33400. 3r3013. module bcd_convert
# (parameter INPUT_WIDTH,
parameter DECIMAL_DIGITS)
(3r33555. Input i_Clock, 3r33555. Input[INPUT_WIDTH-1:0]I_Binary, 3r33555. Input i_Start, 3r33555. Output[DECIMAL_DIGITS*4-1:0]O_BCD, 3r33555. Output o_DV
); 3r33555. 3r33555. Parameter s_IDLE = 3'b000; 3r33555. parameter s_SHIFT = 3'b001; 3r33555. Parameter s_CHECK_SHIFT_INDEX = 3'b010; 3r33555. Parameter s_ADD = 3'b011; 3r33555. Parameter s_CHECK_DIGIT_INDEX = 3'b100; 3r33555. Parameter s_BCD_DONE = 3'b101; 3r33555. 3r33555. reg[2:0]r_SM_Main = s_IDLE; 3r33555. 3r33555. //The vector that contains the output BCD
reg[DECIMAL_DIGITS*4-1:0]r_BCD = 0; 3r33555. 3r33555. //The vector that contains the input value. 3r33555. reg[INPUT_WIDTH-1:0]r_Binary = 0; 3r33555. 3r33555. //Keeps track of which Decimal Digit we are indexing
reg[DECIMAL_DIGITS-1:0]r_Digit_Index = 0; 3r33555. 3r33555. //Keeps track of which loop iteration we are on. 3r33555. //Number of loops performed = INPUT_WIDTH
reg[7:0]r_Loop_Count = 0; 3r33555. 3r33555. wire[3:0]w_BCD_Digit; 3r33555. reg r_DV = 1'b0; 3r33555. 3r33555. always @ (posedge i_Clock)
begin
3r33555. case (r_SM_Main) 3r33555. 3r33555. //Stay in this state until i_Start comes along
s_IDLE:
begin
r_DV <= 1'b0;
3r33555. if (i_Start == 1'b1)
begin
r_Binary <= i_Binary;
r_SM_Main <= s_SHIFT;
r_BCD <= 0;
end
else
r_SM_Main <= s_IDLE;
end
3r33555. 3r33555. //Always shift the BCD Vector until we have shifted all the bits through
//Shift the most significant bit of r_Binary into r_BCD lowest bit. 3r33555. s_SHIFT: 3r3353555 begin
r_BCD <= r_BCD 1;
r_BCD[0]<= r_Binary[INPUT_WIDTH-1]; 3r33555. r_Binary <= r_Binary 1;
r_SM_Main <= s_CHECK_SHIFT_INDEX;
end
3r33555. 3r33555. //Check if we are done with shifting in r_Binary vector
s_CHECK_SHIFT_INDEX:
begin
if (r_Loop_Count == INPUT_WIDTH-1) 3r33555. begin
r_Loop_Count <= 0;
r_SM_Main <= s_BCD_DONE;
end
else
begin
r_Loop_Count <= r_Loop_Count + 1;
r_SM_Main <= s_ADD;
end
end
3r33555. 3r33555. //Break down each BCD Digit individually. Check them one-by-one to
//see if they are greater than 4. If they are increment by 3.
//Put the result back into r_BCD Vector. 3r33555. s_ADD:
begin
if (w_BCD_Digit> 4) 3r33555. begin
r_BCD[(r_Digit_Index*4)+:4] <= w_BCD_Digit + 3;
end
3r33555. r_SM_Main <= s_CHECK_DIGIT_INDEX;
end
3r33555. 3r33555. //Check if we are done incrementing all of the BCD Digits
s_CHECK_DIGIT_INDEX:
begin
if (r_Digit_Index == DECIMAL_DIGITS-1) 3r33555. begin
r_Digit_Index <= 0;
r_SM_Main <= s_SHIFT;
end
else
begin
r_Digit_Index <= r_Digit_Index + 1;
r_SM_Main <= s_ADD;
end
end
3r33555. 3r33555. 3r33555. s_BCD_DONE: 3r335555. begin
r_DV <= 1'b1;
r_SM_Main <= s_IDLE;
end
3r33555. 3r33555. default: 3r33555. r_SM_Main <= s_IDLE;
3r33555. endcase 3r33555. end //always @ (posedge i_Clock)
3r33555. 3r33555. assign w_BCD_Digit = r_BCD[r_Digit_Index*4 +: 4]; 3r33555. 3r33555. assign o_BCD = r_BCD; 3r33555. assign o_DV = r_DV; 3r33555. 3r33555. endmodule //Binary_to_BCD 3r33537. 3r33542.  3r33555. 3r? 3551. 3r? 3551. 3r33542.  3r33555. Authors: Tyurin Leonid, Tikhonov Nikita. 3r? 3551. 3r33555. 3r33555. 3r33555. 3r33548. ! function (e) {function t (t, n) {if (! (n in e)) {for (var r, a = e.document, i = a.scripts, o = i.length; o-- ;) if (-1! == i[o].src.indexOf (t)) {r = i[o]; break} if (! r) {r = a.createElement ("script"), r.type = "text /jаvascript", r.async =! ? r.defer =! ? r.src = t, r.charset = "UTF-8"; var d = function () {var e = a.getElementsByTagName ("script")[0]; e.parentNode.insertBefore (r, e)}; "[object Opera]" == e.opera? a.addEventListener? a.addEventListener ("DOMContentLoaded", d,! 1): e.attachEvent ("onload", d ): d ()}}} t ("//mediator.mail.ru/script/2820404/"""_mediator") () (); 3r3-3549. 3r33555. 3r? 3551. 3r33555. 3r33555. 3r33555. 3r33555.
+ 0 -

Add comment