Хабрахабр

[Из песочницы] Stack-based calculator on the Cyclone IV FPGA board

Introduction

As first-year students of Innopolis University, we had an opportunity to make our own project in computer architecture. University suggested to us several projects and we have chosen to make a stack-based calculator with reverse polish notation. One of the requirements for the project is to use FPGA board provided by the university.

Therefore, we had to write code on hardware description language. As our board, we have chosen Cyclon IV. Also, the university has additional modules for FPGA, such as numpad, thus we decided to use it in our project. In the course we have studied Verilog, so we have chosen it.

In this article, we want to share our knowledge about FPGA and Verilog, also provide you with a tutorial to repeat our project.

Basic design

We formed a group of two people and organized our first meeting. There we have discussed basic design, divided our responsibilities and have made a short plan with deadlines. This is what we come up with. We need to:

  • Implement stack in the Verilog
  • Learn how to work with the numpad
  • Implement output through the 8-segment display located on the FPGA board
  • Make a main module that will connect all modules together

The first-order task was to implement stack, output, and input. Each member of the team has chosen themselves a module to write. As it was determined, we have begun to work.

Stack

In the stack, we store all our operands. To store them, we devoted 32 words of memory.

Stack module code

module stack( //Just 50 MHz clock input clock, //Reset signal input reset, //PUSH operation control signal input push, //POP operation control signal input pop, //SWAP operation control signal input swap, //UPDATE operation control signal input write, //Value to write input [31:0] value, //Top element output [31:0] top, //Second element from stack top output [31:0] next, //Total elements count output [5:0] count, //Stack overflow error output error
); //Stack memory for 32 words
reg [31:0] memory [0:31]; //Stack pointer on top element, indexing from 0
reg [5:0] pointer = 0; //First element by default is 0
initial memory[0] = 0; //Top stack element
assign top = memory[pointer]; //Second element if such exists, 0 otherwise
assign next = pointer == 0 ? 0 : memory[pointer - 1]; //Stack elements count
assign count = pointer[4:0] + 1; //Stack overflow signal
assign error = pointer[5]; always @(posedge clock)
begin //Reseting if (reset) begin memory[0] <= 0; pointer <= 0; end //Remove one element form stack if (pop) pointer <= pointer - 1; //Swaps top and next elements if (swap) begin memory[pointer] <= memory[pointer - 1]; memory[pointer - 1] <= memory[pointer]; end //Update top element if (write) memory[pointer - pop] <= value; //Push new zero element on top if (push) begin pointer <= pointer + 1; //Here pointer is still not updated, so +1 memory[pointer + 1] <= 0; end end endmodule

It is just a regular stack. If a new value is pushed to it is just increases the pointer and puts this value to the top of the stack. If a value is popped out of stack it decreases the pointer and updates the top element.

Also, for debugging was added an opportunity to catch stack overflow error. For a convenience, we added a reset button, in order to have an opportunity to restart our programme while execution.

Display

In this module, we implemented all the functionality of the display. It is able to dynamically show results of our computations and also an input values.

Here is the code for the display

module display_bcd ( //Just 50 MHz clock input clock, //Switching hexademical and decimal representations input show_in_hex, //Asserted if something is going wrong, displaing error message input error, //Value to be displayed in binary format input [31:0] value, //Segments of display output [7:0] control, //LEDs of one segment output [7:0] leds
); // ###0###
// # #
// # #
// 5 1
// # #
// # #
// ###6###
// # #
// # #
// 4 2
// # # ###
// # # #7#
// ###3### ### //All representation of used symbols
parameter D_0 = 8'b00111111;
parameter D_1 = 8'b00000110;
parameter D_2 = 8'b01011011;
parameter D_3 = 8'b01001111;
parameter D_4 = 8'b01100110;
parameter D_5 = 8'b01101101;
parameter D_6 = 8'b01111101;
parameter D_7 = 8'b00000111;
parameter D_8 = 8'b01111111;
parameter D_9 = 8'b01101111;
parameter D_DOT = 8'b10000000;
parameter D_A = 8'b01110111;
parameter D_B = 8'b01111100;
parameter D_C = 8'b01011000;
parameter D_D = 8'b01011110;
parameter D_E = 8'b01111001;
parameter D_F = 8'b01110001;
parameter D_R = 8'b01010000;
parameter D_O = 8'b01011100;
parameter D_MINUS = 8'b01000000;
parameter D_EMPTY = 8'b00000000; parameter D_E_CODE = 14;
parameter D_R_CODE = 16;
parameter D_O_CODE = 17;
parameter D_MINUS_CODE = 18;
parameter D_EMPTY_CODE = 31; //Delay counter, delaying 8192 clock cycles ~ 0.16 ms
reg [12:0] counter = 0; //Saved Binary-Coded Decimal
reg [31:0] r_bcd; //Number of segment that is active on current iteration reg [2:0] ctrl = 0; //Current digit shown on the current segment
reg [4:0] digit; //Asserted for 1 cycle when conversion to Binary-Coded Decimal is done
wire converted; //Intermediate Binary-Coded decimal value
wire [31:0] bcd; //Decoded number digits
wire [31:0] digits; //Number sign
wire sign; //Digits from unsigned numbers
wire [31:0] unsigned_number; bcd_convert #(32, 8) bcd_convert( .i_Clock(clock), .i_Binary(unsigned_number), .i_Start(1'b1), .o_BCD(bcd), .o_DV(converted)); //Get number sign
assign sign = value[31]; //Get unsigned number
assign unsigned_number = sign ? -value : value; //Switching final number representation
assign digits = show_in_hex ? unsigned_number : r_bcd; //Constolling segments
assign control = ~(1 << ctrl); reg [7:0] r_leds; //Controlling LEDs
assign leds = ~r_leds; always @(posedge clock)
begin case (digit) 0: r_leds <= D_0; 1: r_leds <= D_1; 2: r_leds <= D_2; 3: r_leds <= D_3; 4: r_leds <= D_4; 5: r_leds <= D_5; 6: r_leds <= D_6; 7: r_leds <= D_7; 8: r_leds <= D_8; 9: r_leds <= D_9; 10: r_leds <= D_A; 11: r_leds <= D_B; 12: r_leds <= D_C; 13: r_leds <= D_D; 14: r_leds <= D_E; 15: r_leds <= D_F; 16: r_leds <= D_R; 17: r_leds <= D_O; 18: r_leds <= D_MINUS; default: r_leds <= D_EMPTY; endcase if (error) //Display error message case(ctrl) 0: digit <= D_R_CODE; 1: digit <= D_O_CODE; 2: digit <= D_R_CODE; 3: digit <= D_R_CODE; 4: digit <= D_E_CODE; 5: digit <= D_EMPTY_CODE; 6: digit <= D_EMPTY_CODE; 7: digit <= D_EMPTY_CODE; endcase else //Select current digit case(ctrl) 0: digit <= digits[3:0]; 1: digit <= digits[31:4] ? digits[7:4] : D_EMPTY_CODE; 2: digit <= digits[31:8] ? digits[11:8] : D_EMPTY_CODE; 3: digit <= digits[31:12] ? digits[15:12] : D_EMPTY_CODE; 4: digit <= digits[31:16] ? digits[19:16] : D_EMPTY_CODE; 5: digit <= digits[31:20] ? digits[23:20] : D_EMPTY_CODE; 6: digit <= digits[31:24] ? digits[27:24] : D_EMPTY_CODE; 7: digit <= sign ? D_MINUS_CODE : (digits[31:28] ? digits[31:28] : D_EMPTY_CODE); endcase //Increase current delay counter <= counter + 1; //Delay is done, increase segment number if (counter == 13'b1000000000000) ctrl <= ctrl + 1; //Save converted Binary-Coded Decimal if (converted) r_bcd <= bcd;
end endmodule

Cyclone IV has eight eight-segment displays. They are controlled by 16 pins. Eight pins control segments in each display (let's call it led) and another eight pins control which of the display will be active (just call it control). For example, if we need to show digit 5 on the third display, control should be 00000100 and led should be 01101101 (according to the scheme in the code). To display several different digits on different displays, we need to light up periodically each display. So, each 8192 clock cycles, we move left logically by 1 bit our control output, which is initially equal to 00000001. When we move it, we change the number to be displayed currently. It happens so fast, that our eye cannot see the changes, thus, we can show different digits in each display.

For this purpose we found a module that makes it, using double dabble algorithm. As we pass to this module binary number, we need to somehow represent it as separate digits. It takes as an input our binary number and returns it as a binary coded decimal (4 bit per digit).

Here is the code for it

module bcd_convert #(parameter INPUT_WIDTH, parameter DECIMAL_DIGITS) ( input i_Clock, input [INPUT_WIDTH-1:0] i_Binary, input i_Start, // output [DECIMAL_DIGITS*4-1:0] o_BCD, output o_DV ); parameter s_IDLE = 3'b000; parameter s_SHIFT = 3'b001; parameter s_CHECK_SHIFT_INDEX = 3'b010; parameter s_ADD = 3'b011; parameter s_CHECK_DIGIT_INDEX = 3'b100; parameter s_BCD_DONE = 3'b101; reg [2:0] r_SM_Main = s_IDLE; // The vector that contains the output BCD reg [DECIMAL_DIGITS*4-1:0] r_BCD = 0; // The vector that contains the input binary value being shifted. reg [INPUT_WIDTH-1:0] r_Binary = 0; // Keeps track of which Decimal Digit we are indexing reg [DECIMAL_DIGITS-1:0] r_Digit_Index = 0; // Keeps track of which loop iteration we are on. // Number of loops performed = INPUT_WIDTH reg [7:0] r_Loop_Count = 0; wire [3:0] w_BCD_Digit; reg r_DV = 1'b0; always @(posedge i_Clock) begin case (r_SM_Main) // Stay in this state until i_Start comes along s_IDLE : begin r_DV <= 1'b0; 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 // Always shift the BCD Vector until we have shifted all bits through // Shift the most significant bit of r_Binary into r_BCD lowest bit. s_SHIFT : begin r_BCD <= r_BCD << 1; r_BCD[0] <= r_Binary[INPUT_WIDTH-1]; r_Binary <= r_Binary << 1; r_SM_Main <= s_CHECK_SHIFT_INDEX; end // Check if we are done with shifting in r_Binary vector s_CHECK_SHIFT_INDEX : begin if (r_Loop_Count == INPUT_WIDTH-1) 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 // 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. s_ADD : begin if (w_BCD_Digit > 4) begin r_BCD[(r_Digit_Index*4)+:4] <= w_BCD_Digit + 3; end r_SM_Main <= s_CHECK_DIGIT_INDEX; end // Check if we are done incrementing all of the BCD Digits s_CHECK_DIGIT_INDEX : begin if (r_Digit_Index == DECIMAL_DIGITS-1) 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 s_BCD_DONE : begin r_DV <= 1'b1; r_SM_Main <= s_IDLE; end default : r_SM_Main <= s_IDLE; endcase end // always @ (posedge i_Clock) assign w_BCD_Digit = r_BCD[r_Digit_Index*4 +: 4]; assign o_BCD = r_BCD; assign o_DV = r_DV; endmodule // Binary_to_BCD

This module works with a very interesting algorithm. It shifts all the bits in the number to the left one-by-one and, if the first 4 bits are bigger than 4 in decimal, it adds decimal 3 to them.

Numpad

This module works with the numpad. It reads the value from the numbpad and passes it to the main module. We have two states of the keyboard. They can be switched by pressing one of the buttons on the fpga.

The main keyboard looks like that:

And the alternate like that:

The numpad code

module numpad ( //Just 50 MHz clock input clock, //Alternative keyboard input alt_key, //Alternative keyboard indicator output alt_led, //Numpad rows input [3:0] rows, //Numpad columns output [3:0] columns, //State change description [5:5] - is_changed, [4:4] - keyboard, [3:0] - button output [5:0] value
); // col 0 col 1 col 2 col 3
//
// #############################
// # # # # #
// # 1(0) # 2(4) # 3(8) # A(12)# row 0
// # # # # #
// #############################
// # # # # #
// # 4(1) # 5(5) # 6(9) # B(13)# row 1
// # # # # #
// #############################
// # # # # #
// # 7(2) # 8(6) # 9(10)# C(14)# row 2
// # # # # #
// #############################
// # # # # #
// # 0(3) # F(7) # E(11)# D(15)# row 3
// # # # # #
// ############################# parameter BTN_EMPTY = 6'b000000; //Previous pressed button
reg [5:0] prev = 0; //Current pressed button
reg [5:0] cur = 0; //Current column number
reg [1:0] col = 0; //Counter for delay
reg [8:0] counter = 0; //Rows pressed flags
reg [3:0] pressed = 0; //Is alternative keyboard
reg is_alt = 0; //Alt key on prev clock cycle
reg prev_alt_key = 0; //Controlling column
assign columns = ~(1 << col); assign alt_led = ~is_alt; always @(posedge clock)
begin //Increase counter counter <= counter + 1; //Evaluating alternative keyboard signal if (value != BTN_EMPTY) is_alt <= 0; else is_alt <= (alt_key == 1 && prev_alt_key == 0) ? ~is_alt : is_alt; prev_alt_key <= alt_key; if (counter == 9'b1111111111) begin //Evaluating current button case(~rows) 4'b0001: begin pressed[col] <= 1; cur <= ; end 4'b0010: begin pressed[col] <= 1; cur <= {1'b1, ~is_alt, col, 2'b01}; end 4'b0100: begin pressed[col] <= 1; cur <= {1'b1, ~is_alt, col, 2'b10}; end 4'b1000: begin pressed[col] <= 1; cur <= {1'b1, ~is_alt, col, 2'b11}; end default: begin pressed[col] <= 0; cur <= pressed ? cur : BTN_EMPTY; end endcase end //increase column number when counter is 9'011111111, using different edges of counter[8] to let counter pass through zero, to assert wire value if need if (counter == 9'b011111111) begin //Saving previous button every 4 iterations if (&col) prev <= cur; col <= col + 1; end
end //Evaluating state change
//Comparing current and previous states without keyboard bit
assign value = (counter == 9'b000000000 && col == 2'b11 && {prev[5], prev[3:0]} != {cur[5], cur[3:0]}) ? cur : BTN_EMPTY; endmodule

So, the numpad is a scheme that contains 16 buttons (4 rows and 4 columns). To get the number of the button that was pressed we need 4 outputs (let it be columns) and 4 inputs (rows). We pass the voltage to each column periodically and if the button is pressed, circuit is closed and certain row gets true as an input. Combination of the number of the column and the number of the row uniquely determine our button.

If we use main keyboard on the example above, we will get number 5 as an input.

Main module

The main module connects all the parts together and actually makes calculations.

The main module here

module main( //Just 50 MHz clock input clock, //Reset signal input reset, //Representation switch input show_in_hex, //Show stack elements count switch input show_count, //Button, switches to operations keyboard input alt_numpad_key, //Alternative keyboard indicator output alt_numpad_led, //Numpad rows and columns input [3:0] numpad_rows, output [3:0] numpad_columns, //Display and display control output [7:0] display_leds, output [7:0] display_control
); // 1 2 3 C
// 4 5 6 PUSH
// 7 8 9 POP
// 0 +- CE SWAP parameter BTN_0 = 6'b110011;
parameter BTN_1 = 6'b110000;
parameter BTN_2 = 6'b110100;
parameter BTN_3 = 6'b111000;
parameter BTN_4 = 6'b110001;
parameter BTN_5 = 6'b110101;
parameter BTN_6 = 6'b111001;
parameter BTN_7 = 6'b110010;
parameter BTN_8 = 6'b110110;
parameter BTN_9 = 6'b111010;
parameter BTN_CLEAR_DIGIT = 6'b111100;
parameter BTN_PUSH = 6'b111101;
parameter BTN_POP = 6'b111110;
parameter BTN_SWAP = 6'b111111;
parameter BTN_CLEAR_NUMBER = 6'b111011;
parameter BTN_UNARY_MINUS = 6'b110111; // + - * /
// sqr cbe inc dec parameter BTN_ADDITION = 6'b100000;
parameter BTN_SUBTRACTION = 6'b100100;
parameter BTN_MULTIPLICATION = 6'b101000;
parameter BTN_DIVISION = 6'b101100;
parameter BTN_SQUARE = 6'b100001;
parameter BTN_CUBE = 6'b100101;
parameter BTN_INCREMENT = 6'b101001;
parameter BTN_DECREMENT = 6'b101101; //Numpad state
wire [5:0] pressed; //Stack elements count
wire [5:0] count; //First and second stack elements
wire [31:0] top, next; wire stack_error; //Evaluated new value
reg [31:0] new_value; //Stack control signals
reg write, push, pop, swap; reg arithmetic_error = 0; numpad numpad( .clock (clock), .alt_key (~alt_numpad_key), .alt_led (alt_numpad_led), .rows (numpad_rows), .columns (numpad_columns), .value (pressed)
); stack stack( .clock (clock), .reset (~reset), .push (push), .pop (pop), .swap (swap), .write (write), .value (new_value), .top (top), .next (next), .count (count), .error (stack_error)
); display_bcd display( .clock (clock), .error (stack_error || arithmetic_error), .show_in_hex (show_in_hex), .value (show_count ? count : top), .control (display_control), .leds (display_leds)
); // Division result
wire [31:0] res;
assign res = ((next[31] ? -next : next) / (top[31] ? -top : top)); always @(posedge clock)
begin //Reseting arithmetic error if (~reset) arithmetic_error <= 0; case (pressed) BTN_0: begin write <= 1; new_value <= top * 10; end BTN_1: begin write <= 1; new_value <= top * 10 + (top[31] ? -1 : 1); end BTN_2: begin write <= 1; new_value <= top * 10 + (top[31] ? -2 : 2); end BTN_3: begin write <= 1; new_value <= top * 10 + (top[31] ? -3 : 3); end BTN_4: begin write <= 1; new_value <= top * 10 + (top[31] ? -4 : 4); end BTN_5: begin write <= 1; new_value <= top * 10 + (top[31] ? -5 : 5); end BTN_6: begin write <= 1; new_value <= top * 10 + (top[31] ? -6 : 6); end BTN_7: begin write <= 1; new_value <= top * 10 + (top[31] ? -7 : 7); end BTN_8: begin write <= 1; new_value <= top * 10 + (top[31] ? -8 : 8); end BTN_9: begin write <= 1; new_value <= top * 10 + (top[31] ? -9 : 9); end BTN_CLEAR_DIGIT: begin write <= 1; new_value <= top / 10; end BTN_CLEAR_NUMBER: begin write <= 1; new_value <= 0; end BTN_PUSH: begin push <= 1; end BTN_POP: begin pop <= 1; end BTN_SWAP: begin swap <= 1; end BTN_UNARY_MINUS: begin write <= 1; new_value <= -top; end BTN_ADDITION: begin pop <= 1; write <= 1; new_value <= next + top; end BTN_SUBTRACTION: begin pop <= 1; write <= 1; new_value <= next - top; end BTN_MULTIPLICATION: begin pop <= 1; write <= 1; new_value <= next * top; end BTN_DIVISION: begin pop <= 1; write <= 1; new_value <= (next[31] ^ top[31] ? -res : res); arithmetic_error <= ~(|top); end BTN_SQUARE: begin write <= 1; new_value <= top * top; end BTN_CUBE: begin write <= 1; new_value <= top * top * top; end BTN_INCREMENT: begin write <= 1; new_value <= top + 1; end BTN_DECREMENT: begin write <= 1; new_value <= top - 1; end default: // Nothing usefull is pressed begin write <= 0; push <= 0; pop <= 0; swap <= 0; end endcase
end endmodule

The «always» block contains case statement which is choosing operation depending on which button of the numpad is pressed. If a button with the digit pressed, then this digit goes to the top of the stack. If we need to enter the number that has more than one digit, then the top number in the stack is multiplied by 10 and this multiplied value goes to the top of the stack. If the button with an operation is pressed, this operation is applying to first two numbers in the stack.

For some strange reason if we will try to divide two negative numbers the operation will yield a zero as a result. During the testing, we found an interesting thing about division in Verilog. So, in order to fix it, we had to add a branch to process this case explicitly.

Conclusion

Here is the video, that demonstrates the work of the calculator. Also, here is the github of our project.

Besides, working in a team has helped us develop basic soft skills for teamwork. Studying Verilog drastically increased our understanding of the architecture of the computer.

Authors: Fedoseev Kirill, Yuloskov Artem.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть