CS 270 Programming Assignment #2

Due Tuesday September 16th (by 11:59pm)

Introduction:

Programming assignments and the associated homework questions are to be done individually. The homework questions listed in this assignment description should be answered in the README file.

For this assignment you will be writing digital logic simulators for a 4-bit adder and for a D-latch. The goals for this assignment are as follows:

Learn how to simulate digital logic with functions.
Learn how to unit test with asserts in C.
Increase your understanding of adders and D-latches, which are fundamental to the implementation of the arithmetic and logic unit (ALU) and memory respectively.

For example, you will be simulating the AND gate as shown below.

The inputs to the AND gate are labeled A and B. The output is labeled C. In this assignment, the AND gate will be simulated with a function. The inputs to the gate will be passed as parameters to the function and the output will be the return value.

    C = and_gate(A,B);

The simulated digital gates will operate on the BIT enumerated type (see declaration in pa2.h).

The Assignment

You will be given the implementation for the following functions and their corresponding unit tests:

    BIT and_gate( BIT A, BIT B )
    
    BIT not_gate( BIT A )
    
    BIT rs_latch(BIT S, BIT R)

Implement the following functions, each in a separate file named based on the function (e.g. or_gate.c).

    BIT or_gate( BIT A, BIT B )
        Returns the output of an "or" digital logic gate given the 
        inputs A and B.
   
    BIT2 adder_full(BIT a, BIT b, BIT carry_i)
        Returns the carry_(i+1) bit and sum bit based on the input bits a, b,
        and carry_i.  Implement the full adder as diagrammed in Figure 3.15
        int the book
        using only the and_gate(), not_gate(), and or_gate() functions.
        See pa2.h for the definition of the BIT2 type.
    
    BIT4 adder_4bit(BIT4 A, BIT4 B)
        Assume that the final carry bit is dropped, just as would happen in a real machine.
        
    BIT d_latch(BIT WE, BIT D)
        Truth table for the d_latch:
                WE  D       return          side effect
        ---------------------------------------
        0   0       stored bit
        0   1       stored bit
        1   0       0               stored bit = 0
        1   1       1               stored bit = 1
        
        The stored bit is the static variable in the rs_latch function.

The prototypes for all of the functions are in a pa2.h file.

For the function addr_full() keep in mind that functions that simulate 2-bit input digital gates are sufficient for simulating gates with more than two inputs. See Section 3.2.5 in the book for some hints.

Each of the four functions you are implementing will require a unit test. Within each unit test, test all possible inputs as is done in the test_and_gate and test_not_gate unit tests unless you can make a convincing argument that such testing would be unwieldy (e.g. less than ten test cases is not a big deal, but more than one hundred is unwieldy). For the functions where full testing is unwieldy, implement at least four test cases IN ADDITION to the ones provided.

Since the functions in this assignment all return a value, your unit tests can check that the return value is the one expected and otherwise stop execution through the use of the C assert() function (see test_and_gate.c for examples).

README and Homework Questions

For this assignment the README file should contain your name, userid, a high-level description of what the functions in the assignment do, how to compile and run the unit tests, an overview of how the functions were tested, and answers to the the following questions. COPY the question into the file and then type in the answer directly after the copied question. Questions marked as DRAWING should be done on paper and turned in Thursday, September 18th at the BEGINNING of class (BEFORE 12:30pm).

How many test cases are necessary to test each of the below functions fully? How did you determine your answer?

       
    BIT and_gate( BIT A, BIT B )
    
    BIT not_gate( BIT A )
    
    BIT rs_latch(BIT S, BIT R)
    
    BIT or_gate( BIT A, BIT B )
   
    BIT2 adder_full(BIT a, BIT b, BIT carry_i)
    
    BIT4 adder_4bit(BIT4 A, BIT4 B)
        
    BIT d_latch(BIT WE, BIT D)

Powers of two. Fill in the missing information in the following chart:

    Power of two        Abbreviation    Term
    -----------------------------------------
    2^10                1 K             1 kilo
    2^20                1 M             1 mega
    2^30                1 G             1 giga
    2^40                1 T             1 tera
    2^50                1 P             1 peta
    2^60                1 E             1 exa
    2^70                1 Z             1 zetta
    2^80                1 Y             1 yotta   
    2^11                2 K             2 kilo
    2^32                
                        128 M           128 mega
    2^17    
    -----------------------------------------

(DRAWING) Question 3.16 in the book.

(DRAWING) Draw a diagram similar to the one in Figure 3.21 but for a 2^3-by-2 bit memory.

How many bits does a 2^3-by-2 bit memory contain?

Given a 2^n-by-m-bit memory how many and what size decoders and muxes are needed?

Write an equation to describe the number of bits that a 2^n-by-m-bit memory contains.

Many existing computer architectures (including the Pentium) implement technique called branch prediction. See (http://www.x86.org/articles/branch/branchprediction.htm) for some discussion of branch predictors. The main idea of a branch predictor is that when a branch in the code is reached, a prediction is made as to which direction the branch will go to enable faster fetching of the next instruction. For this question and the next, you will be implementing one small piece of a branch predictor, a 2-bit saturation counter. A 2-bit saturation counter starts at the count of 0. If a branch statement jumps, the count goes to 1. If a branch statement falls through, the count stays at 0. When the count is in state 1, a jump causes the count to go to 2, and a fall through causes the count to go to 0. In general, the count saturates at 0 when the count is going down and it also saturates at 3 when the count is going up. The output of the 2-bit saturation counter is to predict jump if the counter value is 2 or 3 and to predict fall through otherwise.

Fill in the missing pieces of the truth table for the combinational circuit that will control the next state and output for the 2-bit saturation counter. (For this question, only copy the partial truth table into your README file and fill in the missing outputs).
```
    States
        A 2-bit counter can represent 4 states (count=0, 1, 2, or 3).  
        The two bits become
        internal inputs to the combinational logic circuit.
        Assume we are using a master-slave flip-flop to store each bit.

    external inputs
        JUMP - input that is true branch instruction jumps and false if not
        
    internal inputs, which encode the current state
        B1
        B0

    internal outputs, next values of B1 and B0

    external outputs
        OUT - true if predict jump, false if predict fall through
        
Fill in the rest of the below truth table.

    Current         Input       Next    
    State           JUMP        State           OUT
    ------------------------------------------------------------
    0   B1=0,B0=0   0           0   B1=0,B0=0   0 (no jump)
    0   B1=0,B0=0   1           1   B1=0,B0=1   0 (no jump)
    1   B1=0,B0=1   0           0   B1=0,B0=0   0 (no jump)
    1   B1=0,B0=1   1           2   B1=1,B0=0   1 (jump)
    2   B1=1,B0=0   0           
    2   B1=1,B0=0   1           
    3   B1=1,B0=1   0           
    3   B1=1,B0=1   1           
```

(DRAWING) Draw three separate combinational circuits that take the current values of B1, B0, and JUMP as input and generate the next values of B1, B0, and OUT respectively. Include the above truth table with your drawing.

Getting Started

The start of a Makefile, a doxygen configuration file (optional, try command make docs), and some of the functions and unit tests have been provided in the public directory (~cs270/public). Let a copy of the PA2-start subdirectory become your initial PA2 subdirectory. To accomplish this do the following at the command prompt:

    % cd ~/CS270
    (Just to make sure you are in your home directory.)
    % cp -r ~cs270/public/PA2-start ~/CS270/PA2
    cp: cannot access `/s/bach/a/class/cs270/public/PA2-start/.svn': Permission denied

The above error about the .svn subdirectory is fine. Do an 'ls' in your PA2 directory and you should now see the following files:

    and_gate.c            not_gate.c     rs_latch.c         test_not_gate.c
    cs270.doxygen.config  pa2.guideline  test_adder_4bit.c  test_rs_latch.c
    Makefile              pa2.h          test_and_gate.c

See SVN Notes for directions for setting up a subversion repository and working directory.

We STRONGLY recommend that you implement one function and its corresponding unit test at a time. Write your file and function headers BEFORE you start implementing the function. Remember that each function and unit test should be in its own file.

Submitting your Assignment

Make sure there are unit tests for all of the functions in the assignment.
Make sure your code follows the code style requirements (see http://www.cs.colostate.edu/~cs270/Programs/code-requirements.html).
Put all of the required information and answer the associated homework questions in the README file.

The subversion.txt file should include output from the following commands:

    % svn log -r HEAD:1     // must be done in subversion working directory
    % svn info              // must be done in subversion working directory
    % svnlook tree REPOSITORY_PATH  // svnlook must be issued on the machine where the repository is stored

We recommend copying the output of the above commands into an editor and saving the result as subversion.txt.

Do a "make clean" in PA2/ before creating the tar ball for the assignment.
Include all the source files, the README file, the Makefile, and a subversion.txt file in a tar file.
```
% cd ~/CS270/
```
```
% tar cvf PA2_userid.tar PA2
```

Submit assignment using checkin utility

% ~cs270/bin/checkin PA2 PA2_username.tar

Sanity Check (procedure we will use to grade your assignment):
```
    % cd ~/CS270/
    % cp PA2_username.tar ~/Temp
    % cd ~/Temp
    % tar xf PA2_username.tar
    % cd PA2
    % make all      // this should compile and run unit tests  
  
```
We will also be copying in our own unit tests for each function, and we will be reading through the code comments for the code style requirements portion of the grade.

Late Policy

Late assignments will be accepted up to 24 hours past the due date and time for a deduction of 20% and will not accepted past this period. One minute late is still late.

mstrout@cs.colostate.edu .... September 15, 2008