Random numbers are hard to generate. Well, they're a lot easier to generate if you don't mind them not being too random. A well-known, easy to implement, and rather low quality, method for generating random numbers is a linear congruential generator (LCG). Let's try that.
The basic idea is that to get the next value in a sequence of random numbers in the range 0..M-1, you simply multiply the previous random value by a carefully-selected constant (let's call it a), add another constant (let's call it c), and then take the result modulus M. Of course, if M is a power of 2, it is a lot easier to compute that modulus because you get to simply bitwise AND with the constant M-1. Actually, modulus is even easier than that in Verilog: just take the bottom log2(M) bits. In any case, it is fairly easy to pick the constants such that you get a fairly random-looking sequence in which no value is repeated until all M values have occurred.
The unfortunate thing is that the bottom bits in the random numbers generated often don't look very random -- in fact, for the most popular choices of a, c, and M the bottom bits simply count: increment by 1 each time. This is why smart people often ignore the bottom few bits of each random number. So, you're probably wondering why anybody would use such a terrible random number generator, and you should wonder, because this was the standard method used for rand() on unix systems for decades... and Windows was still using it the last time I checked. People are lazy? However, there is actually an excellent technical reason to use this on a parallel computer: you can ensure each of N processors will get a different random sequence by picking c=0, initializing the random number on each processor number p to the initial seed times ap, and then using aN instead of a as the multiplier to get the next random value. That basically gives the processors interleaved sequences within the original random sequence. (Although you have to be careful not to have a seed of 0, because with c=0, all the randoms generated would then be 0... which isn't very random.) Of course, you don't need to know any of this stuff for this project, but this wouldn't be a Dietz course if I didn't tell you about it. ;-)
For generating 8-bit random numbers, M=256 and the classic choices are a=13 and c=1. Sounds easy enough. Let's write a little Verilog program to compute and print the sequence of all 256 values (no need to do more because the sequence just repeats):
module demorand8;
reg [15:0] seed;
initial begin
seed = 0;
repeat (256) begin
seed = ((13 * seed) + 1) % 256;
$display("%d", seed);
end
end
endmodule
Well, that was easy! Yeah, too easy: you need to do this computation WITHOUT using the Verilog operator *, +, %, nor even <<. Do it at the gate level.
I want you to design a synthesizable Verilog module that, given a seed value as the argument, returns the next value in the random sequence. That module must be purely combinatorial logic implementing the same 8-bit random number generator formula described above. Obviously, that will require building your own adder from simple gates. Why? Well, 13 is 8+4+1. That means 13*seed is really (8*seed)+(4*seed)+(1*seed). So, (13*seed)+1 is really (seed<<3)+(seed<<2)+seed+1. Get it? You can build this circuit using three instances of an 8-bit adder that you design. That said, I don't care what algorithm your adder implements; feel free to build a carry select, ripple carry, or whatever type of adder seems easiest.
Your project is about writing a Verilog module called rand8, 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:
$display("All cases tested; %d correct, %d failed", correct, failed);
Place all your verilog code for the above in one file called rand.v. That's the file you need to submit.
Naturally, I also expect you to run that file through a Verilog compiler. The one I really expect your code to work with is Icarus Verilog using my CGI Interface, but you can use it or whatever Verilog system you wish. For example, Icarus Verilog can be installed and run on just about any computer; simulation with it is simply and compile:
iverilog -o rand rand.v
And then a separate command to run the simulation:
vvp rand
Which would hopefully result in it printing just:
All cases tested; 256 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. ;-)
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 rand8 module. That can be done as text. I am not requiring you to provide a schematic of your rand8 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 rand8. If you do find it useful, you may include a screen grab from gtkwave in your implementor's notes.
The recommended due date for this assignment is 11:59PM Sunday, January 29, 2017. That's a bit early, but it's as late as you can have things together and still have time to run things by Prof. Dietz before he leaves for Electronic Imaging early Monday afternoon... if you want to do that. The actual submission will not close until class begins on Friday, February 3, 2017. You may submit as many times as you wish, but only the last submission that you make before class begins on Friday, February 3, 2017 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!)
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 rand.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).
Advanced Computer Architecture.