CSE140 Exercises, Winter 1998

I. A sequential machine outputs a 1 when the input sequence x(t - 2, t)=101 or 010, otherwise the output is 0.

(1). Draw the state diagram and write the state table.
(2). Design the system with 3 T flip­flops and a minimal number of 4­input multiplexers.
(3). Design the system with 3 J­K flip­flops and a minimal two­level NAND network.

II. Given a state table:

(1). Reduce the state table to a minimum number of states.
(2). Find a minimum length input sequence which will distinguish between states A and B in the original table. Write the corresponding output sequences with respect to an initial state A, and with respect to an initial state B, respectively.

III. Given a modulo­16 counter

(1). Design a 5­to­13 counter with a minimal AND­OR­NOT network.
(2). Design a counter with output sequence 9, 10, 11, 2, 3, 4, 7, 5, 12, 13, 15, 0, 1, with a minimal number of 2­input multiplexers.
(3). Design a modulo­64 counter with a modulo­16 counter, two SR flip­flops and a minimal network of AND, OR, NOT gates.

IV. Adder:

(1). A 2­bit adder inputs (a₁, a₀, b₁, b₀, c_in) and outputs (c_out, s₁, s₀). Describe its truth table.
(2). Design a 2­bit adder with a minimal two­level NAND network.
(3). Design a serial adder with a J­K flip­flop and a minimal network of AND, OR, NOT gates.

V. System Designs:

Implement the following algorithm:

Alg:
{
Input

X<0:7>, Y<0:7> type bit­vector,
s-type boolean;

Local­object

A<0:7>, B<0:7> type bit­vector;

Output

C<0:7> type bit­vector;

}

S1: if s' goto S1 else goto S2;
S2: B<­X || A<­Y;
S3: A<­Add(A,B) || if A<7> goto S4 else goto S5;
S4: A<­Add(A,1) || goto S6;
S5: B<­ Add(B,1);
S6: C<­ Add(A,B) || goto S1;

end Alg

(1). Design a data subsystem that is adequate to execute the algorithm and draw the schematic diagram.
(2). Design a control subsystem and draw the state diagram.
(3). Implement the control subsystem with a one hot encoding design. Draw the logic diagram.