CS270 Homework 1: Combinational Logic and Transistors

See Progress page for due date.

Goals

1. To practice designing combinational logic circuits.
2. To learn about series-parallel transistor circuits.
3. To design word-level combinational circuits.

The Assignment

*** READ THIS SECTION CAREFULLY ***

You are going to design various circuits involving logic gates and transistors.

Note: Logisim provides a number of libraries that may implement some of what we ask, but for this assignment, you are not allowed to use any elements from the Plexers or Arithmetic libraries. Rather, you should design every circuit with elements only from the Gates and Wiring libraries. You are expected to use combinational logic only (no latches, flip flops, or state machines).

Start from the following skeleton file: H1.circ

When finished, submit your H1.circ file to the H1 box in the Checkin tab. Preliminary testing will perform some sanity tests, but it will not check that you got the right answers.

This assignment will be auto-graded. Don't change the name of the sub-circuits and don't create or remove sub-circuits. Pay attention to the notes inside the input, output, and reserved sections. If you don't pass preliminary testing, the auto-grader will be unable to grade your work and you won't get credit.

Problem 1: Decoder (15 points)

1. Start with the skeleton in the P1 sub-circuit.
2. Design a 3-input decoder whose outputs are labeled A through H and whose inputs are labeled I2, I1, and I0 where I2 is the most significant bit in an input combination. Think about which input combinations should be associated with each output, hint: the input 000 should be associated with output A and increasing input values should select increasing output letters. If you don't follow this ordering, you will lose points.

Problem 2: Programmable Logic Array (25 points)

1. Start with the skeleton in the P2 sub-circuit.
2. Design a combinational circuit for the truth table below. The inputs are A, B, and C, and the outputs are X and Y. Use the methodology described in Section 3.3.4 of the textbook (pg. 63) and the lecture slides, which employs a programmable logic array (PLA). You may only use AND, OR, and NOT gates.

   A	B	C	X	Y
   0	0	0	1	1
   0	0	1	0	0
   0	1	0	0	0
   0	1	1	1	0
   1	0	0	0	0
   1	0	1	1	0
   1	1	0	1	0
   1	1	1	0	1

Problem 3: Series-Parallel Circuits of Transistors (20 points) **Extra Credit**

1. Start with the skeleton in the P3 sub-circuit.
2. We're providing you with the pull-up portion of a series-parallel circuit. Complete the circuit with the pull-down portion by obtaining the complement of the pull-up circuit using the recursive rules explained in lecture. At the end, the completed circuit should produce the truth table shown below. Do not use logic gates.

   A	B	C	X
   0	0	0	1
   0	0	1	1
   0	1	0	1
   0	1	1	0
   1	0	0	1
   1	0	1	0
   1	1	0	1
   1	1	1	0

Problem 4: 12-bit Incrementer (30 points)

You will design a circuit that takes a 12-bit 2's complement number A as input, and produces A + 1. You need to do a stepwise design.

1. First understand the algorithm that your circuit is to implement.

   To add 1 to any (2's complement or unsigned) binary integer, we use the grade school algorithm: work our way from the least significant bit (LSB) to the left towards the most significant bit (MSB). Work out three examples on paper.

2. Decompose the algorithm into a set of functions for each bit and write their truth tables.

   The input at any bit position is an input bit A and a carry bit Cin, and the result of the addition at that position is an output bit S, and a carry bit Cout. So, our first step is to write a truth table that specifies these two outputs as a function of the two inputs. Since there are two inputs and two outputs, your truth table should have 4 rows and 4 columns.

3. Now implement and test it in Logisim:
   • First, build the P4_IncrOneBit sub-circuit that deals with a single bit position as explained above.
   • In the P4_Main sub-circuit, build your logic by making 12 copies of the P4_IncrOneBit sub-circuit and connecting them appropriately. The input to your circuit should come from the splitter in the input section. The output of your circuit should go to the splitter in the output section. Don't add any additional input or output pins in the main circuit. If you need a constant 0 or 1, use the Constant element under the Wiring library.
   • Finally, note that the bit-0 sub-circuit can be simplified so that it doesn't need a Cin input. Build the P4_IncrBit0 sub-circuit and use that in the P4_Main sub-circuit for the LSB instead of P4_IncrOneBit.

Problem 5: 11-bit Normalizer (30 points)

You will design a circuit that takes an 11-bit 2's complement number A and shifts it to the left until the leftmost 1 in A becomes the MSB.

1. Build the P5_LSH1 sub-circuit that takes an 11-bit input X and shifts it left by 1 bit. The least significant bit of the output is 0. The output Y is 11 bits wide.

   [Hint: it does not need any gates, just splitters from the Wiring library]

2. Next, build the P5_Mux11 sub-circuit. It's a multiplexer that takes two 11-bit inputs A and B and a single select bit S. If S is 0, its 11-bit output X will be A. Otherwise, it will be B.

   [Hint: experiment with the splitters and the Data Bits property of the AND/OR gates. If you use them correctly, your multiplexer design will be very compact]

3. Next build the P5_CLSH1 sub-circuit (for Conditional LSH1). It has a single 11-bit input X and an 11-bit output Y. The output depends on the MSB of X:
   • If MSB(X) is 1, the output will be X unchanged.
   • If MSB(X) is 0, the output will be LSH1(X).

   [Hint: you will only need splitters and one copy of each of the previous sub-circuits]

4. Finally, build the normalizer in the P5_Main sub-circuit. It will take the 11-bit input that comes from the splitter in the input section, and it will produce an 11-bit output that goes to the splitter in the output section.

   The output should be the result of left-shifting the input until the leftmost 1 becomes the MSB. If the input is all zeroes (no leftmost 1), the output should be 0. You should use only the previous P5_* sub-circuits, and possibly other elements from the Gates and Wiring libraries.