Lab 7 Exercises

exercises
lab
computer-systems
digital-logic
sequential-logic
NoteProvided task

Pre-Lab Preparation

You should complete a circuit schematic diagram as described below before your Lab 7 session in week 4 (Thu-Fri). You should consult the device pinout information on Blackboard (captured in device-pinouts; the drawing rules it has to satisfy are in circuit-schematics). You will be testing this circuit (or a similar circuit) during the prac session.

Design Requirements

Design and draw a circuit schematic diagram for a 3-bit synchronous counter which counts through your allocated sequence (see table below).

Hardware Specifications:

  • Clock: You must use a push button for the clock signal.
  • Preset: Use a single switch to allow your counter to be preset (i.e., to 111).
  • Clear: Use a single switch to allow your counter to be cleared (i.e., to 000).
  • Outputs: Your count output should be shown on three LEDs.
    • \(Q_2\): Most Significant Bit (MSB)
    • \(Q_1\): Middle bit
    • \(Q_0\): Least Significant Bit (LSB)

Note: Your allocated sequence has seven binary numbers; you may choose to do whatever you like with the missing number – i.e., if the counter ever has this value then we don’t care what the next count value is.

It is recommended that you simulate your circuit using Logisim to ensure it counts through the expected sequence.

Count Sequences

Find the sequence corresponding to the last digit of your 8-digit UQ student number:

Table 1: Count sequence by last digit of student ID
Last digit of UQ ID Count Sequence
0 111 -> 011 -> 101 -> 110 -> 001 -> 000 -> 010 -> 111 -> …
1 111 -> 010 -> 101 -> 110 -> 100 -> 000 -> 001 -> 111 -> …
2 000 -> 011 -> 010 -> 110 -> 100 -> 001 -> 111 -> 000 -> …
3 111 -> 100 -> 101 -> 000 -> 110 -> 001 -> 011 -> 111 -> …
4 000 -> 101 -> 011 -> 010 -> 001 -> 110 -> 100 -> 000 -> …
5 000 -> 110 -> 001 -> 100 -> 111 -> 011 -> 010 -> 000 -> …
6 111 -> 010 -> 000 -> 110 -> 001 -> 101 -> 100 -> 111 -> …
7 111 -> 001 -> 110 -> 101 -> 100 -> 000 -> 010 -> 111 -> …
8 111 -> 000 -> 001 -> 101 -> 011 -> 110 -> 100 -> 111 -> …
9 000 -> 100 -> 001 -> 110 -> 101 -> 011 -> 010 -> 000 -> …

In the lab session

The prep task above is only step one. The whole exercise is a seven-step procedure, modelled on the worked examples in lecture 7:

  1. Pick the counting sequence based on your student number.
  2. Draw the state table — present state and next state.
  3. Obtain Boolean expressions for the \(D\)’s in terms of the \(Q\)’s.
  4. Simplify the expressions if necessary.
  5. Obtain a logic diagram — and optionally simulate it.
  6. Convert the logic diagram to a schematic diagram.
  7. Build and test the circuit for correct operation.

Steps 1–4 are Table 2 through Equation 7 below, step 5 is Figure 1, step 6 is Figure 2, and step 7 is the bench work. The session runs as review of preparation task → design → build and test.

Don’t forget the preset/clear inputs on the flip-flops. The design requirements need both a preset (to 111) and a clear (to 000), and only a flip-flop with both asynchronous inputs can give you that — the 74HCT74 has a SET and a CLR on each half, so it can; the 74HCT175 used in task 2 has a single shared CLR and no set at all, so it cannot. See device-pinouts.

Working

My student number is ——6, so I will be sequencing: 111 -> 010 -> 000 -> 110 -> 001 -> 101 -> 100 -> 111 -> …

Let’s map the current and next states:

Table 2: Current and next state
Current State (\(Q_2 Q_1 Q_0\)) Next State (\(D_2 D_1 D_0\)) Comment
0 0 0 1 1 0 \(000 \to 110\)
0 0 1 1 0 1 \(001 \to 101\)
0 1 0 0 0 0 \(010 \to 000\)
0 1 1 X X X unused state
1 0 0 1 1 1 \(100 \to 111\)
1 0 1 1 0 0 \(101 \to 100\)
1 1 0 0 0 1 \(110 \to 001\)
1 1 1 0 1 0 \(111 \to 010\)

Deriving \(D_2\)

Rows where \(D_2 = 1\):

\(Q_2 Q_1 Q_0\) \(D_2\)
0 0 0 1
0 0 1 1
1 0 0 1
1 0 1 1

Each row gives one product term (1 for that row, 0 elsewhere):

\[ \begin{aligned} D_2 &= \bar{Q_2} \cdot \bar{Q_1} \cdot \bar{Q_0} + \bar{Q_2} \cdot \bar{Q_1} \cdot Q_0 + Q_2 \cdot \bar{Q_1} \cdot \bar{Q_0} + Q_2 \cdot \bar{Q_1} \cdot Q_0 \\ &= \bar{Q_2} \cdot \bar{Q_1} \left(\bar{Q_0} + Q_0\right) + Q_2 \cdot \bar{Q_1} \left(\bar{Q_0} + Q_0\right) & \text{(Distributive law)} \\ &= \bar{Q_2} \cdot \bar{Q_1} \cdot \mathbf{t} + Q_2 \cdot \bar{Q_1} \cdot \mathbf{t} & \text{(Negation law)} \\ &= \bar{Q_2} \cdot \bar{Q_1} + Q_2 \cdot \bar{Q_1} & \text{(Identity law)} \\ &= \bar{Q_1} \left(\bar{Q_2} + Q_2\right) & \text{(Distributive law)} \\ &= \bar{Q_1} \cdot \mathbf{t} & \text{(Negation law)} \\ &= \bar{Q_1} & \text{(Identity law)} \end{aligned} \tag{1}\]

\(D_2\) is just \(\bar{Q_1}\), so it needs no gate at all. FF1’s \(\overline{Q}\) output wires straight to FF2’s \(D\) input.

Deriving \(D_1\)

Sum of products where \(D_1 = 1\) (000, 100, 111):

\[ \begin{aligned} D_1 &= \bar{Q_2} \cdot \bar{Q_1} \cdot \bar{Q_0} + Q_2 \cdot \bar{Q_1} \cdot \bar{Q_0} + Q_2 \cdot Q_1 \cdot Q_0 & \\ &= \bar{Q_1} \cdot \bar{Q_0} \left(\bar{Q_2} + Q_2\right) + Q_2 \cdot Q_1 \cdot Q_0 & \text{(Distributive law)} \\ &= \bar{Q_1} \cdot \bar{Q_0} \cdot \mathbf{t} + Q_2 \cdot Q_1 \cdot Q_0 & \text{(Negation law)} \\ &= \bar{Q_1} \cdot \bar{Q_0} + Q_2 \cdot Q_1 \cdot Q_0 & \text{(Identity law)} \end{aligned} \tag{2}\]

Deriving \(D_0\)

Sum of products where \(D_0 = 1\) (001, 100, 110), plus the unused state 011 — its next state is a don’t care, so I am free to take \(D_0 = 1\) there, which lets \(Q_1\) cancel:

\[ \begin{aligned} D_0 &= \bar{Q_2} \cdot \bar{Q_1} \cdot Q_0 + \bar{Q_2} \cdot Q_1 \cdot Q_0 + Q_2 \cdot \bar{Q_1} \cdot \bar{Q_0} + Q_2 \cdot Q_1 \cdot \bar{Q_0} & \\ &= \bar{Q_2} \cdot Q_0 \left(\bar{Q_1} + Q_1\right) + Q_2 \cdot \bar{Q_0} \left(\bar{Q_1} + Q_1\right) & \text{(Distributive law)} \\ &= \bar{Q_2} \cdot Q_0 \cdot \mathbf{t} + Q_2 \cdot \bar{Q_0} \cdot \mathbf{t} & \text{(Negation law)} \\ &= \bar{Q_2} \cdot Q_0 + Q_2 \cdot \bar{Q_0} & \text{(Identity law)} \\ &= Q_2 \oplus Q_0 & \text{(definition of XOR)} \end{aligned} \tag{3}\]

\(\bar{Q_2} \cdot Q_0 + Q_2 \cdot \bar{Q_0}\) is exclusive-or, so \(D_0\) is a single XOR gate.

Checking Robustness

011 was left unused in Table 2, so its next state was treated as a don’t care when deriving Equation 1, Equation 2 and Equation 3. The circuit will still compute something for this state, so I need to check it doesn’t get stuck there. Substituting \(Q_2 Q_1 Q_0 = 011\) into each equation:

\[ \begin{aligned} D_2 &= \bar{Q_1} \\ &= \bar{1} \\ &= 0 \end{aligned} \tag{4}\]

\[ \begin{aligned} D_1 &= \bar{Q_1} \cdot \bar{Q_0} + Q_2 \cdot Q_1 \cdot Q_0 \\ &= \bar{1} \cdot \bar{1} + 0 \cdot 1 \cdot 1 \\ &= 0 \cdot 0 + 0 \\ &= 0 \end{aligned} \tag{5}\]

\[ \begin{aligned} D_0 &= Q_2 \oplus Q_0 \\ &= 0 \oplus 1 \\ &= 1 \end{aligned} \tag{6}\]

So \(D_2 D_1 D_0 = 001\), meaning 011 -> 001. This is not 011 itself, and 001 is already part of my sequence, so the counter does not lock up in the unused state: it self-corrects back into the main count sequence within one clock cycle.

Taking the don’t care as a 1 in \(D_1\) as well would have simplified it to \(\overline{Q_1 \oplus Q_0}\), but then 011 -> 011 and the counter would hang, so I only used it for \(D_0\).

Conclusion

As per Equation 1, Equation 2 and Equation 3, the excitation equations for the counter are:

\[ \begin{aligned} D_2 &= \bar{Q_1} \\ D_1 &= \bar{Q_1} \cdot \bar{Q_0} + Q_2 \cdot Q_1 \cdot Q_0 \\ D_0 &= Q_2 \oplus Q_0 \end{aligned} \tag{7}\]

and the robustness check in Equation 4, Equation 5 and Equation 6 confirms that the one unused state, 011, transitions to 001 rather than to itself. The counter is therefore self-correcting, and these three equations fully and safely implement my allocated count sequence.

That comes to five 2-input gates, which fit into three gate chips. No inverters are needed anywhere: the 74HCT74 gives \(\overline{Q}\) alongside \(Q\), so \(\overline{Q_1}\) and \(\overline{Q_0}\) are free.


Circuit Schematic

Figure 1: The complete counter: the gates of Equation 7 on the left, the three flip-flops on the right, and \(Q\)/\(\overline{Q}\) fed back to the input rails. \(D_2\) has no gate: it is FF1’s \(\overline{Q}\) wired straight across. CLOCK, PRESET and CLEAR come from the push button and the two switches; each \(Q\) drives one of the three LEDs.

Figure 1 is a logic diagram. Figure 2 is the same counter drawn as a circuit schematic (see circuit-schematics), with device IDs, chip types and pin numbers from device-pinouts.

It takes five chips: U1 and U2 are 74HCT74 dual flip-flops, U3 a 74HCT08 (the 3-input product is U3:B and U3:C cascaded, since the kit has no 3-input gate), U4:A a 74HCT32 and U5:A a 74HCT86. On the IO board, CLOCK is button B0, PRESET and CLEAR are switches S0 and S1, and \(Q_2 Q_1 Q_0\) drive LEDs L2, L1 and L0.

Figure 2: The counter as a circuit schematic, ready to build: device IDs and chip types on every gate, pin numbers on every connection, IO board symbols for the inputs and outputs, and the power connections given once for all four chip types. Inputs and outputs are the same right-pointing pentagon, the input’s wire leaving the point and the output’s arriving at the flat back edge, per circuit-schematics. A dot marks a joined connection; crossing wires are not connected.

Peer review of the schematic

Before building, everyone checks a neighbour’s schematic against a fixed list. It is worth running over Figure 2 as a self-check, because it is also the marking list:

  • naming of inputs and outputs;
  • identification of chips (U1, U2, …) and of the gate within a chip where it matters (:A, :B, …);
  • identification of chip types (74HCT00 etc.);
  • numbering of pins, including the IO board pins;
  • power supply connections;
  • circuit functionality — will it do what was asked?

The schematic guide and device pinouts on Blackboard have the detail (circuit-schematics and device-pinouts here). Ask a tutor if that is not enough. My schematic uses five 74-series chips.

Task 2 — a 4-bit up/down counter built from an adder

The second task drops the derive-the-equations method entirely. Instead of working out \(D_3 \ldots D_0\) by hand, put a 4-bit adder (74HCT283) in front of a 4-bit register (74HCT175) and let the adder compute the next count:

  • the current count — the flip-flop outputs \(Q_3 Q_2 Q_1 Q_0\) — goes back to one adder input, \(A\);
  • the adder’s sum outputs \(S_3 \ldots S_0\) drive the flip-flop inputs \(D_3 \ldots D_0\);
  • an external input \(U\) picks the direction:
    • \(U = 0\): \(0000 \to 0001 \to \ldots \to 1111 \to 0000\) (up);
    • \(U = 1\): \(1111 \to 1110 \to \ldots \to 0000 \to 1111\) (down).

That leaves the other adder input \(B\) and the carry-in \(C_{in}\) to work out for each mode:

Table 3: The table to fill in
Mode Adder B input \(C_{in}\)
Up-count (\(U=0\))
Down-count (\(U=1\))

Working out B and Cin

Note

Hint: \(-1\) in four-bit two’s complement is 1111, and that is exactly the thing task 2 needs.

The adder computes \(A + B + C_{in}\), and \(A\) is already the current count. So the question is only what to add.

Counting up means the next count is one more than this one, so \(B + C_{in}\) has to come to 1. The cheapest way is \(B = 0000\) with \(C_{in} = 1\) — the carry-in is a free +1, which is why it is the input being asked about at all.

Counting down means the next count is one less, i.e. \(Q + (-1)\). In four-bit two’s complement \(-1\) is 1111 (see binary-number-representations), so \(B = 1111\) with \(C_{in} = 0\).

Table 4: The completed table
Mode Adder B input \(C_{in}\)
Up-count (\(U=0\)) 0000 1
Down-count (\(U=1\)) 1111 0

Read Table 4 down the columns and the combinational logic falls out with no algebra at all:

\[B_3 = B_2 = B_1 = B_0 = U \qquad\qquad C_{in} = \overline{U}\]

Every bit of \(B\) is just \(U\) wired straight to it, and \(C_{in}\) is \(U\) through a single inverter. One gate for the whole direction control.

The wrap-around is free, and worth seeing why: the adder’s carry-out \(C_4\) goes nowhere, so the arithmetic is mod 16. Counting up from 1111 gives \(1111 + 0000 + 1 = 1\,0000\), and the discarded carry leaves 0000. Counting down from 0000 gives \(0000 + 1111 + 0 = 1111\) with no carry generated at all.

Figure 3: Task 2’s logic diagram with the two unknowns filled in. \(Q_3 \ldots Q_0\) feed back to the adder’s \(A\) input, the sum drives the register’s \(D\) inputs, and the direction input \(U\) does two jobs: tied to all four bits of \(B\) it supplies 0000 or 1111, and inverted into \(C_{in}\) it supplies the +1 that up-counting needs. The four nested feedback loops are drawn so no two cross. The task gives the two chips, the clock, the \(A\) feedback and the \(S\)-to-\(D\) connections; the \(B\) rail, the inverter and the \(C_{in}\) connection complete it, per the derivation above. The chips are plain rectangles rather than the notched arithmetic-block outline device-pinouts gives the 74HCT283, and the 74HCT175’s clock wedge sits on the bottom edge here rather than on the left edge as in the pinout sheet’s symbol. Either way it is one clock serving all four flip-flops.

Building it

The steps for task 2:

  1. Complete the given logic diagram, connecting \(U\) to the adder’s \(B\) input and \(C_{in}\) with appropriate combinational logic — that is Figure 3.
  2. Simulate the logic diagram in Logisim to check it behaves.
  3. Convert the logic diagram to a schematic diagram (the same treatment Figure 1 got in Figure 2).
  4. Build and test it: clock on a push button, \(U\) on a slide switch, the four counter outputs on four LEDs — see io-board for which pins those are.

Two things to watch on the hardware. The 74HCT175 shares one clock (pin 9) and one clear (pin 1) across all four flip-flops, so unlike the 74HCT74 pairs in Figure 2 there is nothing to fan out — but there is also no preset, so this counter can only be cleared, not loaded. And the register has no clock-enable: every push of the button counts, in whichever direction \(U\) happens to be selecting at that instant.