Assignment 0: Average Two 8-Bit Unsigned Binary Integers

Average two unsigned binary integers? How hard can that be? Well, harder than you probably think. You see, you've no doubt learned that to average two numbers you add them and then divide by 2. Hopefully, by now you've also heard that you can divide by two by shifting one bit position to the right. So, the average of A and B is just ((A+B)>>1), right? Well, not quite. Suppose A=127 and B=129. If the addition (A+B) is done using only 8 bits, (127+129)=0, not 256, so the shifted result is 0 instead of 128. Here is a clever way to get around that in software. It suggests computing the average as ((A^B)+((A&B)<<1)), which is a great way to avoid overflow errors while averaging using fixed-size machine words.

In hardware, it's a lot easier to do this differently. Build an adder that takes two 8-bit inputs to create a 9-bit result and simply return the top 8 bits of the sum. Here's a little Verilog program to compute the averages of all possible pairs of 8-bit unsigned binary integers:

module demoaverage;
reg unsigned [7:0] a, b, avg;
reg unsigned [8:0] t;
initial begin
  a=0;
  repeat (256) begin
    b=0;
    repeat (256) begin
      t = a + b; // 9-bit result
      avg = t >> 1;
      $display("%d\t%d\t%d", a, b, avg);
      b=b+1;
    end
    a=a+1;
  end
end
endmodule

Well, that was easy! Yeah, too easy. So, I'm going to throw one minor twist into that: I want your average to round up. In other words, the average of 12 and 11 is really 11.5, and I want your design to round that up to 12. Of course, 12 averaged with 10 is still 11. Still, just modifying the above Verilog code isn't hard enough....

I want you to design a synthesizable, combinatorial logic, 8-bit unsigned average (rounding up) circuit without using the Verilog + operator -- or anything else that automatically builds the adder for you. In fact, to be even more annoying, I also forbid you from using the >> or divide operators. That said, I don't care what algorithm your circuit implements; feel free to build a carry select, ripple carry, or whatever type of adder seems easiest.

Your Project

Your project is about writing a Verilog module called average, 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 refaverage(s, a, b); and implements an unsigned average, rounding up, of 8-bit values a and b to give the 8-bit result s. This module should be derived from the code for demoaverage above. It MUST use Verilog's + and >> operators and doesn't need to be synthesizable. This is to be 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 average(s, a, b); and implements an unsigned average, rounding up, 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 full adder module and instantiate copies of it within the definition of average. However, this module MUST be synthesizable, purely combinatorial, logic and it is not permitted to use the Verilog +, >>, nor divide operators in itself nor in anything it instantiates.
3. The definition of a non-synthesizable module that starts with module testbench; and instantiates an average which it exhaustively tests for correctness. Note that it is not sufficient to just print what happens for all 65,536 possible combinations of inputs; I don't want just a stimulus module. Who would want to manually check 65,536 lines of output? Your testbench must not only try each possible input combination, but also must check that the answer from your average matches the answer from refaverage in each case. Your testbench should only output the combinations of inputs for which the answer from average 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 average.v. That's the file you need to submit.

Naturally, I also expect you to run that file through a Verilog compiler:

iverilog -o average average.v

And to run the simulation to test it:

vvp average

Which will hopefully result in it printing just:

All cases tested; 65536 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 average module. That can be done as text. I am not requiring you to provide a schematic of your average 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 average. 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, Friday, September 16, 2016. This submission window will close when class begins on Monday, September 19, 2016. You may submit as many times as you wish, but only the last submission that you make before class begins on Monday, September 19, 2016 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 average.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).