Digital Logic and Computer Organization
- Final exam is scheduled to take place from 9am to noon, December 13th,
Wednesday, in Building 315/Room 216
- Topics:
- Number Systems and Codes
- Error Detecting Code (parity bit) and Hamming Error Code
- Boolean Algebra, Huntington Postulates and its derived
Theorems
- Boolean functions/expressions and their minimization
- Logic Operators, Logic Gates and Combinational Logic Circuits
- Standard Combinational Circuit Applications
- Standard types of Memory elements (Flip flops)
- Sequential circuit analysis
- Sequential circuit design using finite state machine model
and/or algorithmic state machine model
- Standard sequential circuit applications
- Concepts of design and realization of CPU and Memory
- Practice Questions (for topics after the midterm):
- (From Peter's previous exams)
(a) Draw the logic schematic for a SR latch using (1) NOR gates;
(2) NAND gates.
(b) Derive the characteristic equation for the gated SR latch.
(c) SR latch inputs S=1 and R=1 are not allowed. Why?
(d) JK latches are not useful. Why?
- Question 1 to 3 from Peter's past final exam:
Final exam 2007
- Question 1 to 4 from Peter's past final exam:
Final exam 2015
- (From Optional Textbook 1 with modification)
The gated D latch in our lecture notes is constructed with 2 NOR, 2 AND
and 1 NOT gates. Consider the alternative way for obtaining a D latch
with 4 NAND gates only.
Draw the logic diagram and verify the circuit operation.
- (From Optional Textbook 1)
A sequential circuit has two JK flip-flops A and B
(whose output are denoted as A and B respectively), and one input x.
The circuit is described by the following flip-flop input equations:
J_A = x; K_A = B'; J_B = x; K_B = A
- Derive the state equations for the next state of A and B.
- Draw the state table and state diagram of the circuit.
- (From Optional Textbook 1 with modification)
For the following state table:
| Present State |
Next State |
Output |
| x = 0 |
x = 1 |
x = 0 |
x = 1 |
| a |
e |
a |
0 |
0 |
| b |
c |
d |
0 |
0 |
| c |
e |
f |
0 |
0 |
| d |
h |
b |
1 |
0 |
| e |
c |
d |
0 |
0 |
| f |
e |
a |
1 |
1 |
| g |
h |
g |
0 |
1 |
| h |
h |
b |
1 |
0 |
- Draw the corresponding state diagram;
- Perform the state reduction using implication table;
- Draw the state diagram corresponding to the reduced state table;
- Starting from state a and the input sequence 01001010001,
determine the output sequence;
- Using binary state assignment, construct the sequential circuit
with JK flip flops to realize the corresponding state diagram;
- Using binary state assignment, construct the sequential circuit
with SR flip flops to realize the corresponding state diagram;
- Using binary state assignment, construct the sequential circuit
with D flip flops to realize the corresponding state diagram;
- Using binary state assignment, construct the sequential circuit
with T flip flops to realize the corresponding state diagram;
- Using One-hot state assignment, construct the sequential circuit
with JK flip flops to realize the corresponding state diagram;
- Using One-hot state assignment, construct the sequential circuit
with SR flip flops to realize the corresponding state diagram;
- Using One-hot state assignment, construct the sequential circuit
with D flip flops to realize the corresponding state diagram;
- Using One-hot state assignment, construct the sequential circuit
with T flip flops to realize the corresponding state diagram;
Midterm : Midterm is tentatively scheduled to take place
in class on 18 October 2023, Wednesday.
- Topics:
- Number Systems and Codes
- Error Detecting Code (parity bit) and Hamming Error Code
- Boolean Algebra, Huntington Postulates and its derived
Theorems
- Boolean functions/expressions and their minimization
- Logic Operators, Logic Gates and Combinational Logic Circuits
- Standard Combinational Circuit Applications
- Practice Questions:
- (From Peter's previous midterm) Consider the construction of
a 4 data-bits (d1,d2,d3,d4) and 4 check-bits (p1,p2,p3,p4)
Extended Hamming code. Let the Hamming encoded word have
the form (p1,p2,d1,p3,d2,d3,d4,p4). Also, let the received
parity bits be the syndrome (c1,c2,c3) and c4.
(a) If the data bits (d1,d2,d3,d4) are (1,0,1,0),
what is the Hamming encoded word?
(b) What can you infer if the the syndrome is (0,0,0)
and c4 is (1).
- (From Peter's previous midterm) Consider the function
F(a,b,c,d,e) = ab + cd'e + a'de + abcde
(a) Draw a NOR-NOR realization of F based on its structural
description.
(b) Draw a NAND-NAND realization of F based on its structural
description.
(c) Express F in canonical POS form using Pi M notation.
(d) Express F in canonical SOP form using Sigma m notation.
(e) Implement F' (complement of F) using a NOR-NOR PLA.
- Using Huntington's Postulates and the derived Theorems we discussed
in the lecture only, prove the DeMorgan's theorem for three variables:
(x + y + z)' = x'y'z'. Justify each step of the transformation.
- Given the Boolean function F = a'b'c' + ab'c + a'bc' + abc',
(a) list its truth table first;
(b) using K-Map to find its minimum sum-of-product expression;
(c) draw a logic schematic that implements this function
using only 2-input NAND gate(s).
Only the true form of the variables are available.
- (From Optional Textbook 1)
Simplify the following Boolean functions, using four-variable
K-maps:
(a) F(w,x,y,z) = Sigma m(4,5,6,7,12,13,14,15)
(b) F(w,x,y,z) = Sigma m(0,3,8,11,12,13,15)
(c) F(w,x,y,z) = Sigma m(3,7,11,13,14,15)
(d) F(w,x,y,z) = Sigma m(2,3,6,10,12,13,14,15)
- (From Optional Textbook 1)
Find all the prime implicants for the following Boolean
functions, and determine which are essential:
(a) F(w,x,y,z) = Sigma m(0,2,4,5,6,7,8,10,13,15)
(b) F(w,x,y,z) = Sigma m(0,2,3,5,7,8,10,11,14,15)
(c) F(w,x,y,z) = Sigma m(2,3,4,5,6,7,9,11,12,13)
(d) F(w,x,y,z) = Sigma m(0,1,2,5,7,8,10,15)
- (From Optional Textbook 1)
Simplify the following expressions to (1) sum-of-products
and (2) product-of-sums:
(a) x'z' + y'z' + yz' + xy
(b) wxy' + wx'z + xyz
(c) w'yz + wxz + wx'z + wx'y
(d) wy'z' + y'z + wx' + wxyz
- (From Optional Textbook 1)
Simplify the following Boolean function F, together with
the don't-care conditions d, and then express the simplified
function in sum-of-products form:
(a) F(x,y,z) = Sigma m(2,3,4,6,7)
d(x,y,z) = Sigma m(0,1,5)
(b) F(w,x,y,z) = Sigma m(0,3,5,7,11,15)
d(w,x,y,z) = Sigma m(1,2,4,6,12)
(c) F(w,x,y,z) = Sigma m(0,3,7,8,9,11,12,13)
d(w,x,y,z) = Sigma m(1,4,14,15)
(d) F(w,x,y,z) = Sigma m(4,5,6,7,12,13,14)
d(w,x,y,z) = Sigma m(1,9,11,15)
- (Combination from Optional Textbook 1 and Peter's previous midterm)
Draw a logic schematic using only two-input NAND gates
to implement the function
F(A,B,C,D) = (A XOR B) XOR C
where only the true form of the variables are available.
Hint: dreive a SOP expression first, then convert to
a nand-nand realization (assume that variables are available
in their true and complemented form). Then, use nand gate
to replace an inverter gate to complete a 3 level
nand only realization.