3.10 Review for Quiz 1

Why this matters

A quiz asks you to do, quickly and without notes, what the earlier sections taught you to do slowly. This page teaches nothing new. It lists what the first three lectures cover, says which section to reopen for each topic, and gives problems on functions that appear nowhere else in the book, so your practice is on problems you cannot answer from memory.

Learning goals

• Check each topic of Lectures 1 to 3 against the checklist, and name the section to reread for any topic you cannot yet do.
• Recognize the kinds of problem these topics produce and the working each kind needs.
• Solve mixed problems on paper before opening the solution, then compare your working with it line by line.
• Spot the mistakes that the earlier sections flagged as the common ones.

Intuition first

Intuition

Reading a solution feels like understanding it. The test is whether you could have written it, and the only way to find out is to write first. So work each problem below on paper, with a clock running, before you open its hint or solution. 20 minutes^{F (fact ch03/quiz1-length)}, which leaves little time to think about how to start, so the starting moves have to be habits: write down every gate delay, name every internal net, list the rows of the table in order.

What the quiz covers

The course says Quiz 1 covers combinational logic, Karnaugh maps, waveforms and SystemVerilog, the material of Lectures 1 to 3.^{F (fact ch03/quiz1-topics)} The quizzes are closed-book and closed-note, no calculators are allowed, and any arithmetic that is needed is kept small.^{F (fact ch03/quiz-closed-book)} Past quizzes with solutions are posted on the course site.^{F (fact ch03/quiz-past-papers)} Use them after this page, for practice on problems written by the people who set the quiz.

The checklist below follows the three lectures. For each line, ask whether you could do it now, on paper, without looking. If not, the section number says where to go.

Lecture 1: gates and tables (sections 1.1 to 1.4)

• Name the seven gates, draw each one with its bubble if it has one, and write its truth table (1.2).
• Say how many rows a table has for $n$ inputs ($2^n$) and how many different functions of $n$ inputs there are ($2^{2^n}$) (1.2).
• Go from a circuit to an expression to a truth table and back again, with the bar over exactly the right letters and the rows in ascending binary order (1.3).
• Say what makes a circuit combinational, and write a first module with assign and with gate primitives, output first (1.4).

Lecture 2: algebra and SystemVerilog basics (sections 2.1 to 2.7)

• Simplify an expression with the laws of Boolean algebra, naming the law at each step (2.1).
• Write a sum of products from the 1 rows and a product of sums from the 0 rows, with the right polarity in each sum (2.2).
• Add up gate cost, and build any function from NAND gates or from NOR gates (2.3).
• Apply DeMorgan's law, and push bubbles through a circuit to change its gate kinds (2.4).
• Write assign statements with the right operator precedence, and read the signals of a module (2.5).
• Use buses, concatenation, replication and sized literals, and read a signed value (2.6).
• Instantiate a module with named connections, and write a multiplexer with always_comb and case (2.7).

Lecture 3: simulation, timing and Karnaugh maps (sections 3.1 to 3.9)

• Write and read a testbench: no ports, a dut instance, an initial block with delays, a loop over inputs, $stop (3.1).
• Read a waveform in the right radix, and say where an unknown X comes from (3.2).
• Draw a waveform when every gate has its own delay, find the glitch, and say when an output is first known (3.3).
• Split a function into its on set and off set and unite neighbors (3.4).
• Fill a Karnaugh map from a table in the book's standard layout (3.5), group the 1s and read off the terms (3.6), and use don't cares only where they help (3.7).
• Decide from a map whether a sum of products can glitch, and say what the fix costs (3.8).
• Go from a description in words to a table, a map per output and a module (3.9).

Kinds of problem

The topics above turn into a handful of problem shapes. For each one, here is the working that keeps you from making an avoidable mistake.

1. Gates and tables. Label every net between gates with its expression before you combine anything. Write the table with the first-listed input as the most significant bit.
2. DeMorgan and bubbles. Push one bar at a time. A bar over a sum becomes a product of bars, and a bar over a product becomes a sum of bars. Then check one row of the table.
3. A map with don't cares. Fill the map from the table, not from your memory of the expression. Group the largest rectangles of 1s, use an X only when it makes a group bigger, and give the terms from the variables that stay fixed. Say "a minimal form" if another exists.
4. A waveform with gate delays. Write each gate's delay first. Each net moves one delay after the input that caused the change. Every net is unknown until a delay has passed, and an output with a controlling input can be known before the slowest path finishes.
5. A testbench. To read one, find which inputs it drives, when, and whether it ends. To write one, declare a signal for every port, instantiate dut, and loop over all input combinations with a delay in each step.
6. A module and its block diagram. Draw each instance as a box with the port names on its edges, connect by name, and check that the widths agree.

How CSE 369 writes this

These conventions come up in every one of the shapes above, so have them ready. NOT is an overbar, and the bar covers exactly what the circuit's gate covers. Truth-table rows ascend in binary with the first-listed input as the most significant bit. A four-variable map has columns AB and rows CD, both in the order 00, 01, 11, 10. A delay waveform states the delay of every gate. A product of sums is read from the 0 rows, and each sum is 0 exactly where its row says.

In SystemVerilog

Before the quiz, make sure you can write these idioms without looking, because they are what a short problem on SystemVerilog tends to ask for.

• A module header with ANSI ports and no trailing comma, and gate primitives written in lowercase with the output first.
• assign with ~, &, ^ and |, remembering that ~ binds tightest and | loosest.
• always_comb with blocking =, and a case with a default so that every input has a value.
• A concatenation on either side of an assignment, with the leftmost item in the top bits.
• A testbench: a module with no ports, a signal for every port, an instance named dut, and an initial block that sets every input at time 0.

Pitfalls

Common pitfall

• Studying by reading solutions. A solution you read always looks obvious; work the problem first.
• Drawing a delay waveform before writing down the delay of every gate, including any gate whose delay is zero.
• Reading a map group's term from the variables that change. The term keeps the variables that stay fixed.
• Writing a product of sums from a 0 row with the literals as they appear in the row. A sum is 0 only when each of its literals is 0, so a variable that is 1 in the row appears complemented.
• Treating the X of a map and the X of a waveform as one thing. The first is a choice you make, the second is a wire with no known value.
• Calling a circuit hazard-free because its zero-delay simulation is clean.

Check your understanding

Take the quiz (4 questions)

A NAND gate takes the two sums $A + \overline{B}$ and $\overline{C} + D$, and its output is Z. Which expression equals Z?

$\overline{A}B + C\overline{D}$$A\overline{B} + \overline{C}D$$A\overline{B}\,\overline{C}D$

A decimal digit arrives in four bits A B C D, with A the high bit, and F is 1 when the digit is 0, 4 or 8. The codes 1010 to 1111 never occur. Which is a minimal sum of products for F?

$\overline{C}\,\overline{D}$$\overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}B\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}\,\overline{D}$$\overline{C}\,\overline{D} + AB$

The function $\overline{B}\,\overline{D} + BC$ is built as two AND gates and an OR gate. When B changes with A = 0, C = 1 and D = 0, the output should stay at 1, but it can dip. Which product term is the group that holds the four cells where C is 1 and D is 0, whatever A and B are?

$C\overline{D}$$BC$$\overline{B}\,\overline{D}$

The circuit $\overline{AB} + \overline{C}$ has three inputs. For how many of its eight input rows is the output 1?

741

Exercises

Exercise 3.10.1

Four gates are connected as in the figure: a NAND gate on P and Q, an inverter on R, an OR gate that takes Q and the inverter's output, and an AND gate that takes the NAND output and the OR output. The output is Y.

A logic schematic with inputs P, Q and R and output Y.

NOT gate g_not: input R; output n2.

NAND gate g_nand: inputs P and Q; output n1.

OR gate g_or: inputs Q and n2; output n3.

AND gate g_and: inputs n1 and n3; output Y.

It agrees with the function logic:ch03/s10-read#Y.

Description: A circuit with inputs P, Q and R and output Y. A NAND gate takes P and Q. An inverter takes R. An OR gate takes Q and the inverter output. An AND gate takes the NAND output and the OR output and drives Y.

Figure 3.10.1. The circuit of the first exercise.

1. Write the expression for Y.
2. Fill in the truth table.

Hint

Name the output of each gate first, starting from the inputs. The inverter gives the complement of R, and the OR gate takes that and Q. Then write the table with P as the most significant bit.

Solution

The NAND gate gives $\overline{PQ}$, the inverter gives $\overline{R}$, and the OR gate gives $Q + \overline{R}$. The AND gate combines them, so $\overline{PQ} \cdot (Q + \overline{R})$. The bar of the NAND covers the product P and Q and nothing else.

Truth table with 3 inputs (P, Q, R) and output Y; 8 rows in ascending binary order, P most significant

P	Q	R	Y
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Description: A truth table with inputs P, Q and R and output Y, eight rows in binary order.

Figure 3.10.2. The truth table of Y.

Tags: Warm-upGates and schematicsTruth tables

Exercise 3.10.2

A NAND gate takes two sums, $\overline{A} + B$ and $C + \overline{D}$, so its output is $\overline{(\overline{A} + B) \cdot (C + \overline{D})}$. Use DeMorgan's law to rewrite Z as a sum of products in which each bar sits over a single letter. Name the law at each step.

Hint

Push the bar over the product first, which gives a sum of two barred sums. Then push each of those two bars through its sum.

Solution

The outer bar covers a product, so the first step turns it into a sum of two barred sums. Each barred sum then becomes a product of barred letters, one sum at a time, and each bar over a barred letter cancels by double negation.

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$\overline{(\overline{A} + B) \cdot (C + \overline{D})}$
$= \overline{\overline{A} + B} + \overline{C + \overline{D}}$	DeMorgan
$= \overline{\overline{A}} \cdot \overline{B} +$ $\overline{C + \overline{D}}$	DeMorgan
$= \overline{\overline{A}} \cdot \overline{B} +$ $\overline{C} \cdot \overline{\overline{D}}$	DeMorgan
$= A\overline{B} + \overline{C} \cdot \overline{\overline{D}}$	Double negation
$= A\overline{B} + \overline{C}D$	Double negation

The result says that Z is 1 when A is 1 and B is 0, or when C is 0 and D is 1. All the lines are equal on all sixteen rows.

Tags: StandardBoolean algebra

Exercise 3.10.3

The circuit in the figure is an AND-OR circuit: two AND gates feed an OR gate. Use bubble pushing to redraw it with NAND gates only, and say what you did to each gate.

A logic schematic with inputs A, B, C and D and output Y.

AND gate g_ab: inputs A and B; output n1.

AND gate g_cd: inputs C and D; output n2.

OR gate g_or: inputs n1 and n2; output Y.

It computes Y = A and B or C and D.

Description: A circuit with inputs A, B, C and D and output Y. One AND gate takes A and B, another takes C and D, and an OR gate combines their outputs into Y.

Figure 3.10.3. An AND-OR circuit for Y.

Hint

Put a bubble on the output of each AND gate and a bubble on each input of the OR gate. That adds two bubbles to every wire between them. What does a gate with a bubbled input and output look like?

Solution

A bubble on an AND gate's output makes it a NAND gate. An OR gate with a bubble on each input is a NAND gate, by DeMorgan's law: the bar over a product of two barred signals is the sum of the two signals. Each wire between an AND gate and the OR gate now carries two bubbles, which cancel, so the function has not changed. The result is three NAND gates, and the expression is $\overline{\overline{AB} \cdot \overline{CD}}$.

Only NAND gates (3 NAND). 3 gates in all.

A logic schematic with inputs A, B, C and D and output Y.

NAND gate g_ab: inputs A and B; output n1.

NAND gate g_cd: inputs C and D; output n2.

NAND gate g_or: inputs n1 and n2; output Y.

It computes Y = A and B or C and D.

Description: A circuit with inputs A, B, C and D and output Y made of three NAND gates: one takes A and B, one takes C and D, and a third takes their outputs and drives Y.

Figure 3.10.4. The same function from three NAND gates.

Tags: StandardGates and schematicsBoolean algebra

Exercise 3.10.4

A decimal digit arrives in four bits A B C D, with A the high bit. The output F is 1 when the digit is 3, 6 or 9. The codes 1010 to 1111 never occur. Draw the map of F and find a minimal sum of products.

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care

	AB=00	AB=01	AB=11	AB=10
CD=00	0	0	X	0
CD=01	0	0	X	1
CD=11	1	0	X	X
CD=10	0	1	X	X

Description: A four-variable Karnaugh map of F with three 1s, seven 0s and six X cells.

Figure 3.10.5. The map of F with no groups drawn. X marks the codes that never occur.

Hint

Take each 1 in turn and ask which X cells it can join. The 1 for the digit 9 can form a square of four with three X cells.

Solution

The digit 9 is the cell where A and D are 1 and B and C are 0. It has X cells for the codes 1011, 1101 and 1111 around it, which makes a square of four with A and D fixed at 1, and its term is $AD$. The digit 3 can pair with the X for 1011. A changes in that pair, and B is 0 while C and D are 1, so its term is $\overline{B}CD$. The digit 6 pairs with the X for 1110. A changes in that pair, and B and C are 1 while D is 0, so its term is $BC\overline{D}$. Every group of four that holds 3 also holds a 0 (the digit 1, 2 or 7), and so does every group of four that holds 6 (the digit 2, 4 or 7), so these pairs are the best groups.

F = $AD + \overline{B}CD + BC\overline{D}$

• $AD$2-by-2 square: rows 01 and 11, columns 11 and 10; 3 of the cells are don't care
• $\overline{B}CD$horizontal pair, wraps left and right: row 11, columns 10 and 00 (2 cells); 1 of the cells is a don't care
• $BC\overline{D}$horizontal pair: row 10, columns 01 and 11 (2 cells); 1 of the cells is a don't care

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care

	AB=00	AB=01	AB=11	AB=10
CD=00	0	0	X	0
CD=01	0	0	X	1
CD=11	1	0	X	X
CD=10	0	1	X	X

Groups drawn:

1. A and D: 2-by-2 square in rows CD=01 and 11, columns AB=11 and 10; 4 cells, 3 of them don't care.
2. not B and C and D: horizontal pair wrapping around the left and right edges in row CD=11, columns AB=10 and 00; 2 cells, 1 of them don't care.
3. B and C and not D: horizontal pair in row CD=10, columns AB=01 and 11; 2 cells, 1 of them don't care.

Description: The same map with three groups, a square of four around the digit 9 and two pairs, each reaching an X cell.

Figure 3.10.6. The three groups of F. Each X that a group uses is chosen as 1.

The sum is $AD + \overline{B}CD + BC\overline{D}$. The X cells that no group uses stay unused, which is allowed.

Tags: StandardKarnaugh maps

Exercise 3.10.5

A circuit has a NAND gate that takes A and B and drives the net nand_ab, an inverter that takes C and drives c_n, and an OR gate that takes both nets and drives Y. The NAND gate takes 20 time units, the inverter 10 and the OR gate 20. A, B and C are all 1 from the start of the run. C falls at time 50 and rises again at time 80.

1. Complete the lanes nand_ab, c_n and Y.
2. How long after the start of the run does Y first have a known value?
3. Can Y glitch in this run? Say why or why not.

Time in ps; one column is 10 ps.

Timing diagram from simulation, ch03/lamp-trace: time in ps from 0 to 120, 12 columns of 10 ps.

A: 1 at 0, no changes.

B: 1 at 0, no changes.

C: 1 at 0, then 0 at 50, 1 at 80.

Empty lanes for the reader to complete: dut.nand_ab, dut.c_n, Y.

Description: A timing diagram of A, B and C with three empty lanes below them. A and B stay at 1, and C falls once and rises again later.

Figure 3.10.7. The inputs of the circuit. The lanes for the three gate outputs are left empty.

Hint

No gate output is known at the start. Each is known one gate delay after its inputs are, so find the time of each first value, then follow the change in C through the inverter and the OR gate.

Solution

Here is the model of the circuit that the figure comes from. The delays are the numbers after the #.

lamp_delay.sv

// Gate-level model of lamp, for simulation only: the NAND takes 20 time units, the NOT 10, the OR 20.
module lamp_delay(input logic A, B, C, output logic Y);
  logic nand_ab, c_n;

  nand #20 g_nand(nand_ab, A, B);
  not  #10 g_not(c_n, C);
  or   #20 g_or(Y, nand_ab, c_n);
endmodule

The inputs are known at time 0. The inverter is the fastest gate, so c_n is known first, at time 10, and its value is 0. The NAND gate takes 20, so nand_ab is known at time 20, and its value is 0 because A and B are both 1. The OR gate needs both of its inputs, and neither is a 1 that could settle it early, so Y is known 20 after the later input, at time 40, with the value 0.

At time 50 C falls. The inverter answers 10 later, so c_n rises at 60. The OR gate has a 1 on an input, and answers 20 after that, so Y rises at 80. At time 80 C rises, c_n falls at 90, and with both OR inputs at 0, Y falls at 110. nand_ab never moves again, because A and B do not.

Time in ps; one column is 10 ps.

Timing diagram from simulation, ch03/lamp-trace: time in ps from 0 to 120, 12 columns of 10 ps.

A: 1 at 0, no changes.

B: 1 at 0, no changes.

C: 1 at 0, then 0 at 50, 1 at 80.

dut.nand_ab: unknown at 0, then 0 at 20.

dut.c_n: unknown at 0, then 0 at 10, 1 at 60, 0 at 90.

Y: unknown at 0, then 0 at 40, 1 at 80, 0 at 110.

Description: The full timing diagram. nand_ab and c_n start unknown. Y is unknown until time 40, is 0, rises at 80 and falls at 110.

Figure 3.10.8. The answer: every signal, from the simulation.

Y does not glitch. Only C changes, and C reaches Y by one route, through the inverter and the OR gate. When only one input changes, a glitch needs that input to reach the output by two routes of different length, so that two changes can arrive at different times and leave a gap. In this circuit nothing races.

Tags: StandardWaveformsHazards

Exercise 3.10.6

The module gray3 turns a 3-bit number into its Gray code.

gray3.sv

// Binary to Gray code for a 3-bit number: each output bit compares two neighbouring input bits.
module gray3(input logic B2, B1, B0, output logic G2, G1, G0);
  assign G2 = B2;
  assign G1 = B2 ^ B1;
  assign G0 = B1 ^ B0;
endmodule

This testbench was meant to try every input combination.

gray3_short_tb.sv

// A testbench for gray3 that was meant to try every input combination.
module gray3_short_tb();
  logic B2, B1, B0, G2, G1, G0;

  gray3 dut(.*);

  initial begin
    for (int i = 0; i < 6; i++) begin
      {B2, B1, B0} = i[2:0]; #10;
    end
    $stop;
  end
endmodule

Its waveform is below.

Time in ps; one column is 10 ps.

Timing diagram from simulation, ch03/gray3-short-trace: time in ps from 0 to 60, 6 columns of 10 ps.

B2: 0 at 0, then 1 at 40.

B1: 0 at 0, then 1 at 20, 0 at 40.

B0: 0 at 0, then 1 at 10, 0 at 20, 1 at 30, 0 at 40, 1 at 50.

G2: 0 at 0, then 1 at 40.

G1: 0 at 0, then 1 at 20.

G0: 0 at 0, then 1 at 10, 0 at 30, 1 at 50.

Description: A timing diagram of B2, B1, B0, G2, G1 and G0 over six steps, as the input counts up from 000.

Figure 3.10.9. The waveform from the testbench.

1. Which input combinations does the run never try?
2. Fix the testbench.
3. Read G2, G1 and G0 from the waveform for the input 101.

Hint

Count how many times the loop body runs, and compare it with the number of combinations of three inputs.

Solution

The loop runs for i from 0 to 5, which is six steps, and three inputs have eight combinations. The run stops after trying 101, so 110 and 111 are never tried. The waveform shows the same thing: it ends with the input at 101.

The fix is to run the loop while i is below 8. With that change the testbench counts through all eight combinations, in binary order.

gray3_tb.sv

// Testbench for gray3: all eight input combinations, counting up in binary.
module gray3_tb();
  logic B2, B1, B0, G2, G1, G0;

  gray3 dut(.*);

  initial begin
    for (int i = 0; i < 8; i++) begin
      {B2, B1, B0} = i[2:0]; #10;
    end
    $stop;
  end
endmodule

For the input 101 the last step of the waveform shows G2, G1 and G0 all at 1. That agrees with the module: G2 is B2, which is 1, G1 is B2 xor B1, which is 1 xor 0, and G0 is B1 xor B0, which is 0 xor 1.

Tags: StandardTest benches and simulationWaveforms

Exercise 3.10.7

The module masked_pick uses two instances of a small module, bit_and, and a case.

bit_and.sv

// Bitwise AND of two 3-bit values, one gate per bit.
module bit_and(input logic [2:0] p, q, output logic [2:0] r);
  assign r = p & q;
endmodule

masked_pick.sv

// Choose one of four 3-bit values: a under the mask m, b under the same mask, a unchanged, or all zeros.
module masked_pick(input logic [2:0] a, b, m, input logic [1:0] sel, output logic [2:0] y);
  logic [2:0] a_masked, b_masked;

  bit_and u_a(.p(a), .q(m), .r(a_masked));
  bit_and u_b(.p(b), .q(m), .r(b_masked));

  always_comb begin
    case (sel)
      2'd0: y = a_masked;
      2'd1: y = b_masked;
      2'd2: y = a;
      default: y = 3'd0;
    endcase
  end
endmodule

Draw the block diagram of masked_pick: a box for each instance with its port names on the edges, a multiplexer for the case, a wire for every connection, and the width written on every wire that is wider than one bit. Which wire goes to which data input of the multiplexer?

Hint

Start with the two instances and say, for each of their ports, which signal of masked_pick is connected to it. Then treat the case as a 4:1 multiplexer whose data inputs are numbered by the value of sel, and ask what each arm sends to y.

Solution

Both instances connect their port q to m, so m splits into two branches. The instance u_a takes a on p, and u_b takes b on p. Each instance has a 3-bit output r, and these become the signals a_masked and b_masked. The case is a multiplexer with its data inputs numbered by sel: a_masked goes to input 00, b_masked to input 01, a itself to input 10, and the constant 0 to input 11, which is what the default arm gives. The select sel is the only 2-bit wire. Every data wire is 3 bits wide, including the constant and the output y, and that agreement is what you check at the end.

Illustration a block diagram that explains an idea; its behavior is not checked

A block diagram with inputs a (3 bits), m (3 bits), b (3 bits) and sel (2 bits) and output y (3 bits).

Block "bit_and" u_a: p is a, q is m, r is n1.

Block "bit_and" u_b: p is b, q is m, r is n2.

Constant 0 drives n3.

4-to-1 multiplexer pick: selects among n1 as input 0, n2 as input 1, a as input 2 and n3 as input 3 using sel; output y.

This diagram is illustrative: its behavior is not checked.

Description: A block diagram. Inputs a, m and b are three bits wide. Input a goes to the p port of a bit_and box named u_a and also, by a branch, to input 10 of a four-input multiplexer. Input m goes to the q ports of both boxes. Input b goes to the p port of a bit_and box named u_b. The output of u_a goes to multiplexer input 00 and the output of u_b to input 01. A 3-bit constant 0 is on input 11. The 2-bit input sel enters the select side of the multiplexer, and the multiplexer output is the 3-bit y.

Figure 3.10.10. The block diagram of masked_pick. The wire from a has a branch that goes to input 10 of the multiplexer.

The book's tools ran this module on all 2048 settings of its inputs and compared y with the rule the four arms state. The block diagram is a sketch: its boxes have no behavior that a program can check, so read it against the module yourself.

Tags: StandardSystemVerilogGates and schematics

Exercise 3.10.8

A motion passes when at least two of the three voters A, B and C say yes, unless the veto V has been used. The output is Pass.

1. Write the truth table, with V as the most significant input.
2. Draw the map and find a minimal sum of products.
3. Write the module.
4. Does the sum of products have a static-1 hazard for any single-input change?

Hint

When V is 1 the output is 0 whatever the voters say. With V at 0 the function is the majority of the three voters, which you have grouped before.

Solution

Here is the table.

Truth table with 4 inputs (V, A, B, C) and output Pass; 16 rows in ascending binary order, V most significant

V	A	B	C	$\mathrm{Pass}$
0	0	0	0	0
0	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	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	0

Description: A truth table with inputs V, A, B and C and output Pass, sixteen rows in binary order.

Figure 3.10.11. The truth table of Pass.

All eight rows with V at 1 are 0. With V at 0 the output is 1 on the four rows that have at least two voters at 1. The map covers those four 1s with three groups of two cells: each fixes V at 0 and fixes two of the voters at 1.

Pass = $\overline{V}AB + \overline{V}AC + \overline{V}BC$

Hazard-free for single input changes: every pair of adjacent 1 cells is held by one drawn group.

• $\overline{V}AB$vertical pair: rows 11 and 10, column 01 (2 cells)
• $\overline{V}AC$vertical pair: rows 01 and 11, column 01 (2 cells)
• $\overline{V}BC$horizontal pair: row 11, columns 00 and 01 (2 cells)

Karnaugh map of Pass: columns VA, rows BC; cell values are 0, 1 or X for don't care

	VA=00	VA=01	VA=11	VA=10
BC=00	0	0	0	0
BC=01	0	1	0	0
BC=11	1	1	0	0
BC=10	0	1	0	0

Groups drawn:

1. not V and A and B: vertical pair in rows BC=11 and 10, column VA=01; 2 cells.
2. not V and A and C: vertical pair in rows BC=01 and 11, column VA=01; 2 cells.
3. not V and B and C: horizontal pair in row BC=11, columns VA=00 and 01; 2 cells.

Description: A four-variable Karnaugh map with columns V and A and rows B and C, with four 1s covered by three groups of two cells.

Figure 3.10.12. The map of Pass with its three groups.

Each group has V fixed at 0 and two of the voters fixed at 1, so the terms are $\overline{V}AB$, $\overline{V}AC$ and $\overline{V}BC$. The module writes them as one expression, with the common $\overline{V}$ factored out.

veto_vote.sv

// A motion passes when at least two of the three voters say yes and the veto V is not used.
module veto_vote(input logic V, A, B, C, output logic Pass);
  assign Pass = ~V & ((A & B) | (A & C) | (B & C));
endmodule

For the hazard, look at every pair of neighboring 1s. They are the cells where V is 0 and the voters are 011 and 111, 101 and 111, or 110 and 111. In the first pair A changes while V, B and C stay at 0, 1 and 1, and the group with term $\overline{V}BC$ holds both. In the second B changes while V, A and C are 0, 1 and 1, and the group with term $\overline{V}AC$ holds both. In the third C changes while V, A and B are 0, 1 and 1, and the group with term $\overline{V}AB$ holds both. Every pair is inside one group, so there is no static-1 hazard for a single input change, and this minimal cover needs no extra group. The module factors out $\overline{V}$, so it is three levels rather than two. The conclusion still holds for it: V is 0 and does not change in any of the three moves, so the factored gate stays at 1 and the voters' OR behaves like the two-level cover.

Tags: ChallengeKarnaugh mapsSystemVerilogHazards