Assignment 0: Binary Coded Decimal Adder

Binary Coded Decimal (BCD) is a representation of numbers that is fairly easy to operate on. It can be a useful notation because each base ten digit is separately encoded, making it easy and lossless to convert back and forth with printed digit sequences.

A decimal digit can have any value from 0 to 9. It takes 4 bits hold one of 10 unique values, so each BCD digit is represented using a 4-bit nybble. Each BCD digit is represented in a nybble as an ordinary binary value. However, a nybble could also represent the values 10 to 15 -- and we'll just skip those. In other words, the BCD representation of the decimal value 12 is actually the binary representation of the decimal value 18 or, much more naturally, the hexadecimal value 0x12. Yes, to print-out a BCD value as a decimal number, just print it as though it was an ordinary hexadecimal value. After all, the nybble values skipped are 0xA to 0xF.

Ok. So, how do we do BCD addition? Well, here's a really simple way to do this in Verilog for all 200 possible pairs of 8-bit BCD values:

module demobcd;
integer a, b, c;
reg [7:0] da, db, dc;
initial begin
  a = 0;
  repeat (100) begin
    da[7:4] = a / 10; // most significant BDC digit
    da[3:0] = a % 10; // least significant BCD digit
    b = 0;
    repeat (100) begin
      db[7:4] = b / 10;
      db[3:0] = b % 10;
      c = a + b;
      dc[7:4] = (c / 10) % 10;
      dc[3:0] = c % 10;
      $display("%x + %x = %x", da, db, dc);
      b = b + 1;
    end
    a = a + 1;
  end
end
endmodule

Well, that was easy! The catch is that it isn't a synthesizable combinatorial circuit, which is what I want you to build. Actually, it doesn't even do the add in BCD; it does the add in binary and then converts the result -- which is not ok for your project. In fact, I'm being even meaner than that: in this project I want you to design a synthesizable, purely combinatorial, circuit for an 8-bit BCD adder without using Verilog word-level operators like + for addition nor < for less than. You also must exhaustively test it..

So, let's talk about BCD add. When you add two 4-bit digit representations, there are two reasons BCD digit addition might not give the same 5-bit result as an ordinary 4-bit binary addition. First, consider adding the two largest BCD digits: 9+9=18, or in BCD, 0x9+0x9=0x18. However, conventional binary addition gives 0x9+0x9=0x12; the sum is 6 less than it should be. In general, whenever the 4-bit binary add generates a carry (a "1" in the 5th bit) so would the BCD add, but the 4-bit result is 6 too small. The other issue is that, for example, adding 0x9+0x1 in binary will give 0xA, not 0x10 -- you can't have a digit "A" in a BCD value. Thus, if the digit sum results in any of the illegal BCD digit values, "A" through "F", the correct answer would be to set the carry and subtract 10 from the 4-bit result so that 0xA becomes 0x0, 0xB becomes 0x1, etc. That sounds complex, doesn't it? Well, it so happens that subtracting 10 from a 4-bit binary value is the same as adding 6! So, basically, all you need to do is add the two 4-bit BCD digits to produce a 5-bit sum and, if the sum is greater than 0x9, add 6 to the bottom 4 bits and set bit 5. If I allowed you to use 4-bit + and 5-bit >=, BCD digit addition could be something like:

module digitadd(carry, s, a, b);
output carry;
output [3:0] s;
input [3:0] a, b;
wire [4:0] t;
assign t = a + b;
assign carry = (t >= 10);
assign s = t[3:0] + (carry ? 6 : 0);
endmodule

For your synthesizable, combinatorial logic, 8-bit BCD addition circuit, I will allow you to operate on a word at a time, but only using assignment (to copy a value) or bitwise operators (such as ^ for XOR, so you can write something like a^b). That said, you are free to use any bit-level algorithm you wish for your synthesizable, purely combinatorial, circuit design.

Your Project

Your project is about writing a Verilog module called bcdadd, but there are actually two other chunks of Verilog code you need in order to test it. The three required modules of Verilog code are:

1. The definition of a module that starts with module refbcdadd(s, a, b); and computes the BCD result of adding the values of a and b to give the 8-bit result s. Notice that there is no carry out of the 8-bit (two digit) BCD add. This module MUST use Verilog's + operator and doesn't need to be synthesizable. For example, to add two 8-bit BCD values you could convert both to ordinary binary, add them, and then convert the result back to BCD. The ordinary binary value, bin of BCD value bcd would be bin=(10*bcd[7:4])+bcd[3:0];. To convert back, bcd[7:4]=(bin/10)%10; bcd[3:0]=bin%10;. Use as straightforward an implementation as possible; it will serve as your oracle to deliver known correct answers.
2. The definition of a module that starts with module bcdadd(s, a, b); and implements BCD addition of 8-bit values a and b to give the 8-bit result s. Of course, it may instantiate other combinatorial logic modules to implement its functionality, e.g., you might start with defining a one-bit full adder, then a BCD digit adder, and then this module. Again, you have a free choice of algorithm. However, this module MUST be Verilog code that you author using synthesizable, purely combinatorial, logic -- it is NOT permitted to use word-level Verilog operators (as noted above) in itself nor in anything it instantiates.
3. The definition of a non-synthesizable module that starts with module testbench; and instantiates a bcdadd which it exhaustively tests for correctness. Note that it is not sufficient to just print what happens for all 10,000 possible combinations of inputs; I don't want just a stimulus module. Who would want to manually check 10,000 lines of output? Incidentally, make sure you test only the 10,000 pairs of valid 8-bit BCD values -- not all 65,536 possible binary bit patterns. Your testbench must not only try each possible input combination, but also must check that the answer from your bcdadd matches the answer from refbcdadd in each case. Your testbench should only output the combinations of inputs for which the answer from bcdadd was wrong. Further, it should count how many input combinations were correct and how many failed. The last line of text output should be generated by Verilog code like:

   $display("All cases tested; %d correct, %d failed", correct, failed);
   

Place all your verilog code for the above in one file called bcd.v. That's the file you need to submit.

Naturally, I also expect you to run that file through a Verilog compiler either using our CGI interface or Icarus Verilog directly:

iverilog -o bcd bcd.v

And to run the simulation to test it:

vvp bcd

Which will hopefully result in it printing just:

All cases tested; 10000 correct, 0 failed

If not, and you can't figure-out how to fix it, as Ricky Ricardo would say, you got some splainin to do. ;-)

Details For The Implementor's Notes

You should be submitting an implementor's notes document with your project. Just a couple of quick comments about that....

Your implementor's notes certainly should describe the logic used to implement your bcd module. That can be done as text. I am not requiring you to provide a schematic of your bcdadd module... but practice creating schematics is certainly a good thing (i.e., a skill you will need in this course) and it wouldn't hurt to include a schematic.

Although I would encourage you to think about generating a VCD file and using gtkwave to visualize it, I don't think there's much point in doing that for a simple combinatorial circuit like bcdadd. If you do find it useful, you may include a screen grab from gtkwave in your implementor's notes.

Due Dates

The recommended due date for this assignment is before class, Wednesday, Spetember 12, 2018. This submission window will close when class begins on Friday, September 14, 2018. You may submit as many times as you wish, but only the last submission that you make before class begins on Friday, September 14, 2018 will be counted toward your course grade.

Note that you can ensure that you get at least half credit for this project by simply submitting a tar of an "implementor's notes" document explaining that your project doesn't work because you have not done it yet. Given that, perhaps you should start by immediately making and submitting your implementor's notes document? (I would!)

Submission Procedure

For each project, you will be submitting a tarball (i.e., a file with the name ending in .tar or .tgz) that contains all things relevant to your work on the project. Minimally, each project tarball includes the source code for the project and a semi-formal "implementors notes" document as a PDF named notes.pdf. It also may include test cases, sample output, a make file, etc., but should not include any files that are built by your Makefile (e.g., no binary executables). For this particular project, name the Verilog source file bcd.v.

Submit your tarball below. The file can be either an ordinary .tar file created using tar cvf file.tar yourprojectfiles or a compressed .tgz file file created using tar zcvf file.tgz yourprojectfiles. Be careful about using * as a shorthand in listing yourprojectfiles on the command line, because if the output tar file is listed in the expansion, the result can be an infinite file (which is not ok).