Computer Science 150 Homework Assignment 2
Spring 1997

Due: Thursday, February 13, 5:00 pm

The numbers in brackets [ ] denote the relative marks assigned for each question.

1. A multiplexer is a combinational logic circuit. The basic function of a multiplexer is choosing one of the inputs and using it as the output. Here's a picture of a multiplexer (digital nerds call it a mux):

   

   This is a 2 input mux. The S line selects whether to have the output be IN1 or IN0. All muxes have basically the same set up. They have a certain number of inputs, select lines to choose between them, and an output. Note that the select signals ``don't count'' as inputs here; when we talk about an n-input mux, it is implied that there are log(n) (base 2 logarithm) select inputs as well.

   Your job is to:

   1. Implement a 4-input-1-output multiplexer using 6 tristate buffers and 3 inverters. [10]
   2. Using a single 4-input-1-output multiplexer for each, implement two-input AND, OR, XOR, NAND, and NOR functions. [10]
   3. Implement the sum function for an adder using a 4-input-1-output multiplexer and an inverter. Remember that the inputs for that function are A, B, and CI and the output is simply S. [15]

   Show the schematics for each of the above.

2. BCD (or binary coded decimal) is a method of representing the ten decimal digits in terms of binary numbers. BCD uses four bits in order to encode the digits zero through nine. This scheme was popular in the past because it is more accurate for certain calculations.
1. Implement a BCD counter (using D flip-flops and logic gates) that counts continously. Each time the counter goes up to 9, there should be an additional signal (TC, or terminal count) that goes high for one cycle (similar to a carry out signal). The output sequence should look something like this:

   Output  TC       ; Comment
   
   0000     0       ; 0
   0001     0       ; 1
   0010     0       ; 2
   0011     0       ; 3
   0100     0       ; 4
   0101     0       ; 5
   0110     0       ; 6
   0111     0       ; 7
   1000     0       ; 8
   1001     1       ; 9  Notice TC is high
   0000     0       ; 0  It loops back to zero here
   0001     0       ; 1  And so on...
   

   Note that there is no input. The counter does require a clock signal, however. Give a schematic for the circuit. [20]

2. Just like toggle flip-flops can be used to make a counter by feeding the output of the first toggle flip-flop into the clock input of the next, you should be able to make a BCD counter with multiple bits. Show the schematic for a BCD counter that counts from 0 to 999. [5]

3. Your boss at SETI was so impressed by your first homework assignment solution that she asked you to build another alien intelligence detector.

   Implement an FSM that outputs a 1 if the sum of the last three bits seen in a serial bitstream is greater than 1. For example, if you had

   input:  0100110010001110010100
   output: 0000011000000111000100
   

   Use no more than four states for your design. Submit a state transition diagram and the state transition table with your schematics. Be sure to show the state assignment that you used.

   1. Implement this FSM using D flip-flops and a ROM. Give the truth table for the ROM along with your design. [20]
   2. Implement this FSM using J-K flip-flops and logic gates. Try to minimize the number of gates you use; that is, do not use the J-K flip-flops to build a D register. [20]

4. (Bonus)

   1. One criticism of Flash EPROM devices is that they eventually fail after being written to so many times. Suppose a computer hard drive were made with Flash devices, and any particular bit in the drive is expected to fail after being written 30000 times. Assume a person overwrites every single bit in the hard drive 5 times a day, every day. Approximately how many years will the hard drive last? (Sidenote: most modern Flash devices can actually withstand at least 100000 writes.) [1]
   2. Prove the Consensus theorem: X Y + Y Z + X' Z = X Y + X' Z [2]
   3. Kenny Keener comes to you with an idea for a new type of digital circuit, a Super PLA Technoid (SPLAT). Kenny's idea is to take the outputs of a standard PLA (Katz, Figure 4.3) and feed them into the inputs of another programmable OR-plane, so that any number of outputs from the original PLA could be ORed together. He suggests that you could implement some functions on his SPLAT that you wouldn't be able to on a regular PLA. Kenny asks for a $100 investment from you. Should you invest in his idea? Why (not)? [3]
   4. Your boss at SETI (again) wants you to implement the following function using logic gates. The SETI budget is completely in ruins, so she expects you to implement the function using the absolute minimum number of two-input gates (AND/OR only); inversion is free, however. If she can find a better solution, she'll probably fire you or something. (Warning: this is a difficult problem. SETI doesn't have the computer resources to spare, so two (2) marks will be deducted if you use a logic minimization program (e.g. Espresso). Show your work. No marks for solutions which use more than eight gates. It is a bonus question, after all.)
      fg + (c'+b')ad(e+g) + ade'g' + f(b'+c') + abcd + bcf [4]