CS270 Homework 1: Combinational Logic and Transistors
See Progress page for due date.
- To practice designing combinational logic circuits.
- To learn about series-parallel transistor circuits.
- To design word-level combinational circuits.
*** READ THIS SECTION CAREFULLY ***
You are going to design various circuits involving logic gates and
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 (25 points)
- Start with the skeleton in the P1 sub-circuit.
- 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 (there's a natural ordering). If you don't follow
this ordering, you will lose points.
Problem 2: Programmable Logic Array (30 points)
- Start with the skeleton in the P2 sub-circuit.
- 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), which employs a programmable
logic array (PLA). You may only use AND, OR, and NOT gates.
Problem 3: Series-Parallel Circuits of Transistors (30 points)
- Start with the skeleton in the P3 sub-circuit.
- 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.
Problem 4: 12-bit Incrementer (40 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.
- 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.
- 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
- 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
- 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 (40 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.
- 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
- 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]
- 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
- 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
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
Problem 6: Canvas Assignment (35 points)
Complete the H1 Canvas assignment in Canvas. You have two