Assignment 0: NaN-preserving 1's Complement Subtraction

An 8-bit 2's complement number can have any value from -128 to 127. In contrast, an 8-bit 1's complement number can hold any integer value from -127 to 127. The most significant bit is the sign and the other bits hold the value, which is complemented if the sign is negative. There's a simple trade-off: in 2's complement, the negative of -128 is not representable, so 2's complement arithmetic isn't closed on negation. In 1's complement, negation is closed, and it's cheap to compute because all one needs to do is to flip all the bits, but there are two values for 0: +0 and -0. Normally, the two values for 0 are considered a disadvantage, but we can turn it into an advantage by treating -0 as NaN (Not a Number). Thus, if an operand of an operation is -0 (NaN), we'll force the result to be -0 (NaN); similarly, if the ordinary 1's complement result would be -0, we must force it to be +0.

Unfortunately, the better properties of 1's complement do come at a cost: 1's complement addition and subtraction are not the same circuits used for unsigned binary or 2's complement. Here's a little Verilog program to compute 1's complement subtraction for all possible pairs of 8-bit values. Note that values going out of range wrap around, then don't become NaN.

`define SIGN(v) (v[7]?"-":"+")
`define MAG(v)  (v[7]?~v[7:0]:v[7:0])
`define NaN     8'b11111111

module demoonesub;
reg [7:0] r, a, b;
reg [8:0] t;
initial begin
  a=0;
  repeat (256) begin
    b=0;
    repeat (256) begin
      if ((a == `NaN) || (b == `NaN)) begin
        // preserve NaNs
        r = `NaN;
      end else begin
        // add 1's complement
        t = a + (b ^ `NaN);
        // add 1 if overflow
        r = (t[8] ? (t[7:0] + 1) : t);
        // don't let -0 happen
        if (r == `NaN) r = 0;
      end
      $display("%s%-d - %s%-d = %s%-d",
               `SIGN(a), `MAG(a),
               `SIGN(b), `MAG(b),
               `SIGN(r), `MAG(r));
      b=b+1;
    end
    a=a+1;
  end
end
endmodule

Well, that was easy enough. Yeah, but that's not what I want you to do. I want you to design a synthesizable, combinatorial logic, 8-bit 1's complement NaN-preserving 1's complement subtractor without using the Verilg + or - operators. To be precise, the constraint is basically that you cannot use any word-level Verilog operators that do not function on each bit independently: for example, copying a value, bitwise AND, shift by a constant, and even the ?: operator are allowed. Of course, you don't need to write any Verilog assignments; the whole thing could be implemented by instantiating gates. Speed and gate-count of your design is not an issue; feel free to use whatever algorithm you wish -- or whatever seems easiest. Incidentally, you don't have to use the same algorithm I used in demo1sub above.

Your Project

Your project is about writing a Verilog module called onesub, 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 refonesub(r, a, b); and makes r the result of Nan-preserving 1's complement subtraction of b from a. This module MUST use at least one of Verilog's word-level operators that you're not allowed to use in your synthesizable design (e.g., demoonesub uses +). Use as straightforward an implementation as possible, perhaps derived from the algorithm used in demoonesub above. This refonesub module will serve as your oracle to deliver known correct answers.
2. The definition of a module that starts with module onesub(r, a, b); and makes r the result of Nan-preserving 1's complement subtraction of b from a, but is fully synthesizable and uses only bitwise or gate-level operations. Of course, it may instantiate other combinatorial logic modules to implement its functionality, e.g., you might start with defining an 8-bit NaN-preserving 1's complement adder circuit and then instantiate that in your onesub... or maybe you'll build and use an ordinary 8-bit adder? You might even begin by building a one-bit full adder and then build whatever 8-bit stuff you need from that (e.g., instantiating 8 copies to build a ripple carry adder). You have a free choice of algorithm for how you implement onesub. 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 onesub which it exhaustively tests for correctness. Note that it is not sufficient to just print what happens for all 65,536 possible input values; 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 value, but also must check that the answer from your onesub matches the answer from refonesub in each case. Your testbench should only output the combinations of inputs for which the answer from onesub 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 onesub.v. That's the file you need to submit.

Naturally, I also expect you to run that file through a Verilog compiler. You can use either the WWW form version made for this course or Icarus Verilog directly:

iverilog -o onesub onesub.v

And to run the simulation to test it:

vvp onesub

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 onesub module. That can be done as text. I am not requiring you to provide a schematic of your onesub module... but practice creating schematics is certainly a good thing (i.e., a skill that is useful in this course) and it wouldn't hurt to include a schematic.

Although you could generate a VCD file and using gtkwave to visualize it, I don't think there's much point in doing that for onesub. 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, September 9, 2020. This submission window will close when class begins on Monday, September 14, 2020 (bumped from Friday, September 11, 2020). You may submit as many times as you wish, and all submissions are archived (although the only confirmation you'll get is a response WWW page), but only the last submission that you make before class begins on September 14, 2020 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 onesub.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).