3.9 Design examples

Why this matters

Up to now each map came with its truth table already filled in. A real design starts earlier, with a description in words of what the circuit must do. This section takes three small descriptions all the way: words, then a table, then one K-map per output, then equations, then a module that a program checks against the table. Once you have done it three times, the method is a habit.

Learning goals

• Turn a description in words into a truth table, and mark as don't cares the input patterns that cannot occur.
• Draw one K-map for each output of a circuit and read a minimal sum of products from each.
• Write a decoder with a case statement and say what its default arm does in simulation.
• Check that a module computes the table it was designed from.

Intuition first

Intuition

In software you might specify a function by a list of test cases and then write code that passes them. For a small combinational circuit the list of cases can be complete, because the inputs are a few bits: the truth table is the whole specification. Design is then a series of translations of that table into forms that cost less. The place where the software analogy breaks is the outputs. A function returns one value, but a circuit has all its outputs at once, and each output has its own map.

The steps are the same each time.

1. Name the inputs and the outputs, and say in words what each input pattern means.
2. Fill in the truth table. Mark an output X where it can never be looked at.
3. Draw one K-map per output and group the 1s, using the Xs that help.
4. Read the terms off the groups.
5. Write the module and check it against the table.

Example one: a 2-bit adder

Example 3.9.1(adding two 2-bit numbers).

The first number has bits A (the high bit) and B (the low bit), and the second has bits C (high) and D (low). The largest sum is 3 + 3 = 6, which needs three bits, so the answer is three bits X, Y and Z, with X the most significant. Figure 3.9.1 lists all sixteen input patterns.

Truth table with 4 inputs (A, B, C, D) and outputs X, Y, Z; 16 rows in ascending binary order, A most significant

A	B	C	D	X	Y	Z
0	0	0	0	0	0	0
0	0	0	1	0	0	1
0	0	1	0	0	1	0
0	0	1	1	0	1	1
0	1	0	0	0	0	1
0	1	0	1	0	1	0
0	1	1	0	0	1	1
0	1	1	1	1	0	0
1	0	0	0	0	1	0
1	0	0	1	0	1	1
1	0	1	0	1	0	0
1	0	1	1	1	0	1
1	1	0	0	0	1	1
1	1	0	1	1	0	0
1	1	1	0	1	0	1
1	1	1	1	1	1	0

Description: A truth table with inputs A, B, C and D and outputs X, Y and Z, sixteen rows in binary order.

Figure 3.9.1. The truth table of the 2-bit adder. Each row's output is the sum of the number AB and the number CD, in binary.

There are three outputs, so there are three maps. The first is X, which is 1 when the sum is 4 or more.

X = $AC + BCD + ABD$

• $AC$2-by-2 square: rows 11 and 10, columns 11 and 10
• $BCD$horizontal pair: row 11, columns 01 and 11 (2 cells)
• $ABD$vertical pair: rows 01 and 11, column 11 (2 cells)

Karnaugh map of X: 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	0	0
CD=01	0	0	1	0
CD=11	0	1	1	1
CD=10	0	0	1	1

Groups drawn:

1. A and C: 2-by-2 square in rows CD=11 and 10, columns AB=11 and 10; 4 cells.
2. B and C and D: horizontal pair in row CD=11, columns AB=01 and 11; 2 cells.
3. A and B and D: vertical pair in rows CD=01 and 11, column AB=11; 2 cells.

Description: A four-variable Karnaugh map of X with three groups.

Figure 3.9.2. The map of X, the high bit of the sum.

The 2-by-2 square in rows CD=11 and 10, columns AB=11 and 10 says that when both high bits are 1, both numbers are at least 2, so the sum is at least 4 whatever the low bits are. The term $BCD$ is 1 when the second number is 3 and the first number is odd, which also adds up to at least 4. The term $ABD$ is the mirror image: the first number is 3 and the second is odd.

The second output is Z, the low bit of the sum.

Z = $B\overline{D} + \overline{B}D$

• $B\overline{D}$2-by-2 square, wraps top and bottom: rows 10 and 00, columns 01 and 11
• $\overline{B}D$2-by-2 square, wraps left and right: rows 01 and 11, columns 10 and 00

Karnaugh map of Z: 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	1	1	0
CD=01	1	0	0	1
CD=11	1	0	0	1
CD=10	0	1	1	0

Groups drawn:

1. B and not D: 2-by-2 square wrapping around the top and bottom edges in rows CD=10 and 00, columns AB=01 and 11; 4 cells.
2. not B and D: 2-by-2 square wrapping around the left and right edges in rows CD=01 and 11, columns AB=10 and 00; 4 cells.

Description: A four-variable Karnaugh map of Z with two groups of four cells.

Figure 3.9.3. The map of Z, the low bit of the sum.

The two groups wrap around the map's edges: the 2-by-2 square wrapping around the top and bottom edges in rows CD=10 and 00, columns AB=01 and 11 and the 2-by-2 square wrapping around the left and right edges in rows CD=01 and 11, columns AB=10 and 00. Together they read $B\overline{D} + \overline{B}D$, which is the same as $B \oplus D$: $\overline{B}D + B\overline{D} = B \oplus D$. The low bit of the sum depends only on the low bits of the two numbers, as it does in a one-bit adder.

The third output, Y, is the awkward one.

Y = $\overline{A}C\overline{D} + A\overline{C}\,\overline{D} + \overline{A}\,\overline{B}C + A\overline{B}\,\overline{C} + \overline{A}B\overline{C}D + ABCD$

• $\overline{A}C\overline{D}$horizontal pair: row 10, columns 00 and 01 (2 cells)
• $A\overline{C}\,\overline{D}$horizontal pair: row 00, columns 11 and 10 (2 cells)
• $\overline{A}\,\overline{B}C$vertical pair: rows 11 and 10, column 00 (2 cells)
• $A\overline{B}\,\overline{C}$vertical pair: rows 00 and 01, column 10 (2 cells)
• $\overline{A}B\overline{C}D$single cell: row 01, column 01
• $ABCD$single cell: row 11, column 11

Karnaugh map of Y: 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	1	1
CD=01	0	1	0	1
CD=11	1	0	1	0
CD=10	1	1	0	0

Groups drawn:

1. not A and C and not D: horizontal pair in row CD=10, columns AB=00 and 01; 2 cells.
2. A and not C and not D: horizontal pair in row CD=00, columns AB=11 and 10; 2 cells.
3. not A and not B and C: vertical pair in rows CD=11 and 10, column AB=00; 2 cells.
4. A and not B and not C: vertical pair in rows CD=00 and 01, column AB=10; 2 cells.
5. not A and B and not C and D: single cell in row CD=01, column AB=01; 1 cell.
6. A and B and C and D: single cell in row CD=11, column AB=11; 1 cell.

Description: A four-variable Karnaugh map of Y with six groups: four pairs and two single cells.

Figure 3.9.4. The map of Y, the middle bit of the sum.

Its 1s are scattered, so a minimal sum of products has six terms and twenty literals. A map does not always give a small answer. Here the problem is not the method but the shape of the function: the middle bit of a sum is an XOR of the two high bits and the carry out of the low bits, and an XOR written as a sum of products needs many terms.

$\overline{A}C\overline{D} +$ $A\overline{C}\,\overline{D} +$ $\overline{A}\,\overline{B}C +$ $A\overline{B}\,\overline{C} +$ $\overline{A}B\overline{C}D +$ $ABCD$ $= A \oplus C \oplus BD$

The check above confirms that the six-term sum equals this form with XOR gates, where $BD$ is the carry out of the low bits.

Example two: a seven-segment decoder

A seven-segment display is seven separate lights arranged to draw a digit. Section 3.1 simulated a decoder for it; this section works out the decoder's truth table and maps, and then reads Section 3.1's module as the answer. The segments are named as the lecture names them: L0 is the top segment, L1 the upper right, L2 the lower right, L3 the bottom, L4 the lower left, L5 the upper left and L6 the middle. The decoder's input is a 4-bit number B3 B2 B1 B0 holding a digit, and its seven outputs L0 to L6 say which segments light. Ten of the sixteen input codes are digits; the other six are not.

leds[6:0] = 7'b0111111
active high: a 1 lights a segment

leds[6:0] = 7'b0000110
active high: a 1 lights a segment

leds[6:0] = 7'b1011011
active high: a 1 lights a segment

leds[6:0] = 7'b1001111
active high: a 1 lights a segment

leds[6:0] = 7'b1100110
active high: a 1 lights a segment

leds[6:0] = 7'b1101101
active high: a 1 lights a segment

leds[6:0] = 7'b1111101
active high: a 1 lights a segment

leds[6:0] = 7'b0000111
active high: a 1 lights a segment

leds[6:0] = 7'b1111111
active high: a 1 lights a segment

leds[6:0] = 7'b1101111
active high: a 1 lights a segment

Description: The digits 0 to 9 drawn as seven-segment displays.

Figure 3.9.5. The ten digits as the decoder lights them. A filled segment is lit.

Example 3.9.2(the table and the map of segment L5).

The truth table has seven outputs and sixteen rows. The rows for 10 to 15 are X: no digit has those codes, so nothing looks at the decoder's output there.

Truth table with 4 inputs (B3, B2, B1, B0) and outputs L0, L1, L2, L3, L4, L5, L6; 16 rows in ascending binary order, B3 most significant; X means don't care

$B_3$	$B_2$	$B_1$	$B_0$	$L_{0}$	$L_{1}$	$L_{2}$	$L_{3}$	$L_{4}$	$L_{5}$	$L_{6}$
0	0	0	0	1	1	1	1	1	1	0
0	0	0	1	0	1	1	0	0	0	0
0	0	1	0	1	1	0	1	1	0	1
0	0	1	1	1	1	1	1	0	0	1
0	1	0	0	0	1	1	0	0	1	1
0	1	0	1	1	0	1	1	0	1	1
0	1	1	0	1	0	1	1	1	1	1
0	1	1	1	1	1	1	0	0	0	0
1	0	0	0	1	1	1	1	1	1	1
1	0	0	1	1	1	1	1	0	1	1
1	0	1	0	X	X	X	X	X	X	X
1	0	1	1	X	X	X	X	X	X	X
1	1	0	0	X	X	X	X	X	X	X
1	1	0	1	X	X	X	X	X	X	X
1	1	1	0	X	X	X	X	X	X	X
1	1	1	1	X	X	X	X	X	X	X

Description: A truth table with inputs B3, B2, B1 and B0 and outputs L0 to L6. The rows for 0 to 9 hold 1s and 0s, and the rows for 10 to 15 hold X in every output.

Figure 3.9.6. The seven-segment decoder: a 1 means the segment is lit. The codes above 9 are don't cares.

Each column is a separate function and gets its own map. Take L5, the upper left segment, which is lit for 0, 4, 5, 6, 8 and 9.

L5 = $B_3 + \overline{B_1}\,\overline{B_0} + B_2\overline{B_0} + B_2\overline{B_1}$

• $B_3$group of eight: columns 11 and 10 (8 cells); 6 of the cells are don't care
• $\overline{B_1}\,\overline{B_0}$row of four: row 00 (4 cells); 1 of the cells is a don't care
• $B_2\overline{B_0}$2-by-2 square, wraps top and bottom: rows 10 and 00, columns 01 and 11; 2 of the cells are don't care
• $B_2\overline{B_1}$2-by-2 square: rows 00 and 01, columns 01 and 11; 2 of the cells are don't care

Karnaugh map of L5: columns B3,B2, rows B1,B0; cell values are 0, 1 or X for don't care

	B3B2=00	B3B2=01	B3B2=11	B3B2=10
B1B0=00	1	1	X	1
B1B0=01	0	1	X	1
B1B0=11	0	0	X	X
B1B0=10	0	1	X	X

Groups drawn:

1. B 3: group of eight in columns B3,B2=11 and 10; 8 cells, 6 of them don't care.
2. not B 1 and not B 0: row of four in row B1,B0=00; 4 cells, 1 of them don't care.
3. B 2 and not B 0: 2-by-2 square wrapping around the top and bottom edges in rows B1,B0=10 and 00, columns B3,B2=01 and 11; 4 cells, 2 of them don't care.
4. B 2 and not B 1: 2-by-2 square in rows B1,B0=00 and 01, columns B3,B2=01 and 11; 4 cells, 2 of them don't care.

Description: A four-variable Karnaugh map of L5 with 1s, 0s and X cells and four groups, the largest covering the two columns where B3 is 1.

Figure 3.9.7. The map of L5 with its four groups. Every X is used as a 1.

The group of eight in columns B3,B2=11 and 10 holds the digits 8 and 9 and all six don't care cells, which is how six Xs help: they let a group of two become a group of eight, and its term is just $B_3$. The other groups are $\overline{B_1}\,\overline{B_0}$ (the codes ending in 00), $B_2\overline{B_0}$ and $B_2\overline{B_1}$. Together $B_3 +$ $\overline{B_1}\,\overline{B_0} +$ $B_2\overline{B_0} +$ $B_2\overline{B_1}$ lights the upper left segment, with four terms and seven literals. Each segment has its own map and chooses its own Xs, so the other segments need other groups.

What the module does with the codes above 9

How CSE 369 writes this

The decoder in this book is active high: a 1 lights a segment, the way the lecture's decoder does. The handout for Lab 4 says the DE1 board's displays are active low: a 0 on a segment's wire turns that segment on.^{F (fact ch03/de1-seg7-active-low)} The two conventions differ in which value means lit, and a decoder has to match the display it drives. This section shows only the active-high decoder. The decoder has digits 0 to 9 only, and bit i of its output drives segment Li.

In SystemVerilog

A table with many outputs and many rows is the case where a case statement is the natural code: one line per row. This is the decoder of Section 3.1, which can now be read as the answer to the table above. Its input is called bcd and carries B3 B2 B1 B0.

seg7_digit.sv

// Seven-segment decoder for the digits 0 to 9. leds[i] drives segment Li and 1 means lit.
// The codes 10 to 15 are not digits, so their output is left unknown.
module seg7_digit (
  input  logic [3:0] bcd,
  output logic [6:0] leds
);
  always_comb begin
    case (bcd)
      //          leftmost bit is segment 6
      4'd0: leds = 7'b0111111;
      4'd1: leds = 7'b0000110;
      4'd2: leds = 7'b1011011;
      4'd3: leds = 7'b1001111;
      4'd4: leds = 7'b1100110;
      4'd5: leds = 7'b1101101;
      4'd6: leds = 7'b1111101;
      4'd7: leds = 7'b0000111;
      4'd8: leds = 7'b1111111;
      4'd9: leds = 7'b1101111;
      default: leds = 7'bX;
    endcase
  end
endmodule

The comment over the arms says the leftmost bit is segment 6, which is the order a code is written in. For 0 the lit segments are L0 to L5, and the code is 7'b0111111. The last arm, default, covers every input that no earlier arm names, which here is the six codes from 10 to 15 (A to F in hexadecimal). It gives the output the value 7'bX: unknown.

In simulation the output for those inputs is X, as Figure 3.1.4 in Section 3.1 shows: the leds lane is hatched, the drawing for an unknown value, for the codes A to F. That matches the table, which does not say what the output is there. When a synthesis tool builds the circuit, the X is permission to choose, the same as an X in a K-map.^{? (not machine-checked: A property of synthesis tools in general, not checked by this book's tools: they treat an X assigned in a case arm as permission to choose whatever output is cheapest.)} So the decoder does not promise any output for those inputs, and nothing in a design should depend on one.

Section 3.1 checks this module digit by digit: its check bench lists the lit segments of each of the ten digits by segment name and compares them with leds.

Example three: rock-paper-scissors

Example 3.9.3(a judge for two players).

Two players each choose rock, paper or scissors. Rock beats scissors, scissors beats paper, and paper beats rock. The poses are coded in two bits: rock is 00, paper is 01 and scissors is 10. Player 1's pose is the pair of bits A and B, and player 0's pose is the pair C and D. The circuit has two outputs. Win is 1 when player 1 wins, and Tie is 1 when the two poses are equal.

The don't cares come from two facts about how the outputs are used. First, 11 is not a pose, so when either player's pair is 11, neither output matters. Second, when the poses are equal there is no winner, but that alone does not make Win a don't care: a judge that reports no winner would normally show Win as 0. Win is free on a tie only because we state an interface rule, which is that whoever reads the outputs checks Tie first and ignores Win whenever Tie is 1. When Tie is 0, Win equal to 1 means player 1 wins and Win equal to 0 means player 0 wins. With that rule, the three tie rows are don't cares for Win.

Truth table with 4 inputs (A, B, C, D) and outputs Win, Tie; 16 rows in ascending binary order, A most significant; X means don't care

A	B	C	D	$\mathrm{Win}$	$\mathrm{Tie}$
0	0	0	0	X	1
0	0	0	1	0	0
0	0	1	0	1	0
0	0	1	1	X	X
0	1	0	0	1	0
0	1	0	1	X	1
0	1	1	0	0	0
0	1	1	1	X	X
1	0	0	0	0	0
1	0	0	1	1	0
1	0	1	0	X	1
1	0	1	1	X	X
1	1	0	0	X	X
1	1	0	1	X	X
1	1	1	0	X	X
1	1	1	1	X	X

Description: A truth table with inputs A, B, C and D and outputs Win and Tie. Rows where the two poses are equal have X for Win, and rows where either pair is 11 have X for both outputs.

Figure 3.9.8. The truth table of the judge. X marks the rows where an output does not matter.

Win has three 1s, one for each way that player 1 can win: rock against scissors, paper against rock, scissors against paper. Everything else is a 0 or an X.

Win = $B\overline{C} + AD + \overline{B}C$

• $B\overline{C}$2-by-2 square: rows 00 and 01, columns 01 and 11; 3 of the cells are don't care
• $AD$2-by-2 square: rows 01 and 11, columns 11 and 10; 3 of the cells are don't care
• $\overline{B}C$2-by-2 square, wraps left and right: rows 11 and 10, columns 10 and 00; 3 of the cells are don't care

Karnaugh map of Win: 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	X	1	X	0
CD=01	0	X	X	1
CD=11	X	X	X	X
CD=10	1	0	X	X

Groups drawn:

1. B and not C: 2-by-2 square in rows CD=00 and 01, columns AB=01 and 11; 4 cells, 3 of them don't care.
2. 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.
3. not B and C: 2-by-2 square wrapping around the left and right edges in rows CD=11 and 10, columns AB=10 and 00; 4 cells, 3 of them don't care.

Description: A four-variable Karnaugh map of Win with many X cells and three groups of four cells.

Figure 3.9.9. The map of Win. Each group is one winning match-up made larger with don't cares.

Each of the three groups holds exactly one 1 and three don't cares. The 2-by-2 square in rows CD=00 and 01, columns AB=01 and 11 is the paper-against-rock case, and its term is $B\overline{C}$. The 2-by-2 square in rows CD=01 and 11, columns AB=11 and 10 is scissors against paper, $AD$. The 2-by-2 square wrapping around the left and right edges in rows CD=11 and 10, columns AB=10 and 00 is rock against scissors, $\overline{B}C$. The don't cares are what make each term two literals: without them a single 1 would need a term of four.

Tie is 1 when the two poses are equal.

Tie = $BD + AC + \overline{A}\,\overline{B}\,\overline{C}\,\overline{D}$

• $BD$2-by-2 square: rows 01 and 11, columns 01 and 11; 3 of the cells are don't care
• $AC$2-by-2 square: rows 11 and 10, columns 11 and 10; 3 of the cells are don't care
• $\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}$single cell: row 00, column 00

Karnaugh map of Tie: 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	1	0	X	0
CD=01	0	1	X	0
CD=11	X	X	X	X
CD=10	0	0	X	1

Groups drawn:

1. B and D: 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11; 4 cells, 3 of them don't care.
2. A and C: 2-by-2 square in rows CD=11 and 10, columns AB=11 and 10; 4 cells, 3 of them don't care.
3. not A and not B and not C and not D: single cell in row CD=00, column AB=00; 1 cell.

Description: A four-variable Karnaugh map of Tie with two groups of four cells and one single cell.

Figure 3.9.10. The map of Tie.

Paper against paper and scissors against scissors each join three don't cares in a group of four, giving $BD$ and $AC$. Rock against rock has no don't care neighbor, so it stays a single cell with all four variables, $\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}$.

The module is the two equations, and the shown testbench tries each winning match-up, one loss and the three ties. It does not look at Win in a tie, because under the interface rule a reader ignores Win whenever Tie is 1.

rps_judge.sv

// Rock-paper-scissors judge. {A, B} is player 1's pose and {C, D} is player 0's: rock 00, paper 01, scissors 10.
module rps_judge(input logic A, B, C, D, output logic Win, Tie);
  assign Win = (B & ~C) | (A & D) | (~B & C);
  assign Tie = (B & D) | (A & C) | (~A & ~B & ~C & ~D);
endmodule

rps_judge_tb.sv

// Player 1 wins with rock, paper and scissors, loses once, and ties three ways. Win is not looked at in a tie.
module rps_judge_tb();
  logic A, B, C, D, Win, Tie;

  rps_judge dut(.A, .B, .C, .D, .Win, .Tie);

  initial begin
    {A, B} = 2'b00; {C, D} = 2'b10; #10;   // expect: Win=1, Tie=0
    {A, B} = 2'b01; {C, D} = 2'b00; #10;   // expect: Win=1, Tie=0
    {A, B} = 2'b10; {C, D} = 2'b01; #10;   // expect: Win=1, Tie=0
    {A, B} = 2'b00; {C, D} = 2'b01; #10;   // expect: Win=0, Tie=0
    {A, B} = 2'b00; {C, D} = 2'b00; #10;   // expect: Tie=1
    {A, B} = 2'b01; {C, D} = 2'b01; #10;   // expect: Tie=1
    {A, B} = 2'b10; {C, D} = 2'b10; #10;   // expect: Tie=1
    $stop;
  end
endmodule

A 2-bit adder can be written two ways: from the three equations, or with the + operator and no equations at all. Both modules are checked against the same table, so they compute the same function.

adder2.sv

// A 2-bit adder written from the three K-map equations: (A B) + (C D) = (X Y Z).
module adder2(input logic A, B, C, D, output logic X, Y, Z);
  assign X = (A & C) | (B & C & D) | (A & B & D);
  assign Y = (~A & C & ~D) | (A & ~C & ~D) | (~A & ~B & C) | (A & ~B & ~C) | (~A & B & ~C & D) | (A & B & C & D);
  assign Z = (~B & D) | (B & ~D);
endmodule

adder2_plus.sv

// The same adder with the + operator: the tool picks the gates.
module adder2_plus(input logic A, B, C, D, output logic X, Y, Z);
  assign {X, Y, Z} = {1'b0, A, B} + {1'b0, C, D};
endmodule

Pitfalls

Common pitfall

• Trying to read all the outputs of a circuit from one K-map. A map shows one output, so draw one for each.
• Filling in the rock-paper-scissors table with the two players swapped. Write down which pair is which player, and what Win equal to 1 means, before you fill in the rows.
• Using the same don't-care choices on every output. Each map uses an X as a 1 only where it lets a group grow.
• Reading the bits of the decoder's output backward. Bit i of leds drives segment Li, and a code is written with bit 6 first.
• Treating the X in the default arm as a particular output value. It means unknown, and nothing should depend on it.

Check your understanding

Take the quiz (5 questions)

Which expression is the low bit Z of the 2-bit sum?

$B \oplus D$$BD$$B + D$

How many of the sixteen input rows of the rock-paper-scissors judge are don't cares for Tie?

7610

Which is a minimal sum of products for Win, where Win is 1 when player 1 wins?

$B\overline{C} + AD + \overline{B}C$$\overline{A}D + BC + A\overline{D}$$B\overline{C} + AD + \overline{B}C + BD$

For how many of the ten digits is segment L4, the lower left one, lit?

436

In simulation, what does the decoder's leds show when its input is 12? All seven bits are X All seven bits are 0, so every segment is off The pattern for the digit 2, because 12 minus 10 is 2

Exercises

Exercise 3.9.1

A thermometer code shows the size of a 2-bit number n, whose bits are A (high) and B (low). The output T1 is 1 when n is at least 1, T2 is 1 when n is at least 2, and T3 is 1 when n is 3. Here is the table.

Truth table with 2 inputs (A, B) and outputs T1, T2, T3; 4 rows in ascending binary order, A most significant

A	B	$T_{1}$	$T_{2}$	$T_{3}$
0	0	0	0	0
0	1	1	0	0
1	0	1	1	0
1	1	1	1	1

Description: A truth table with inputs A and B and outputs T1, T2 and T3, four rows.

Figure 3.9.11. The thermometer code.

1. Draw a map for each output and write a minimal sum of products.
2. Write a module that uses a case statement.

Hint

A map of two variables has two rows and two columns. T1 has three 1s, so look for two pairs.

Solution

The maps have two variables, with A on the rows and B on the columns.

T1 = $A + B$

• $A$horizontal pair: row 1 (2 cells)
• $B$vertical pair: column 1 (2 cells)

Karnaugh map of T1: columns B, rows A; cell values are 0, 1 or X for don't care

	B=0	B=1
A=0	0	1
A=1	1	1

Groups drawn:

1. A: horizontal pair in row A=1; 2 cells.
2. B: vertical pair in column B=1; 2 cells.

Description: A two-variable Karnaugh map of T1 with two groups of two cells.

Figure 3.9.12. T1: n is at least 1.

T2 = $A$

• $A$horizontal pair: row 1 (2 cells)

Karnaugh map of T2: columns B, rows A; cell values are 0, 1 or X for don't care

	B=0	B=1
A=0	0	0
A=1	1	1

Groups drawn:

1. A: horizontal pair in row A=1; 2 cells.

Description: A two-variable Karnaugh map of T2 with one group of two cells.

Figure 3.9.13. T2: n is at least 2.

T3 = $AB$

• $AB$single cell: row 1, column 1

Karnaugh map of T3: columns B, rows A; cell values are 0, 1 or X for don't care

	B=0	B=1
A=0	0	0
A=1	0	1

Groups drawn:

1. A and B: single cell in row A=1, column B=1; 1 cell.

Description: A two-variable Karnaugh map of T3 with a single 1.

Figure 3.9.14. T3: n is 3.

So $A + B$ gives T1, $A$ gives T2 and $AB$ gives T3. A module with a case statement writes one line for each row of the table.

thermo_case.sv

// A thermometer code for the 2-bit number {A, B}, written with a case statement.
module thermo_case(input logic A, B, output logic T1, T2, T3);
  always_comb
    case ({A, B})
      2'b00: {T1, T2, T3} = 3'b000;
      2'b01: {T1, T2, T3} = 3'b100;
      2'b10: {T1, T2, T3} = 3'b110;
      default: {T1, T2, T3} = 3'b111;   // the remaining input, 2'b11
    endcase
endmodule

The default arm stands for the one input that no earlier arm names. Every row of this table has a value, so the arm is the fourth row and not a placeholder.

Tags: Warm-upKarnaugh mapsSystemVerilog

Exercise 3.9.2

A comparator takes two 2-bit numbers, the first with bits A (high) and B (low) and the second with bits C (high) and D (low). Its output GT is 1 when the first is greater than the second. Find a minimal sum of products.

Karnaugh map of GT: 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	1	1	1
CD=01	0	0	1	1
CD=11	0	0	0	0
CD=10	0	0	1	0

Description: A four-variable Karnaugh map of GT with six 1s and no groups.

Figure 3.9.15. The map of GT, with no groups drawn.

Hint

Think about the high bits first. When A is 1 and C is 0, the first number is bigger whatever the low bits are.

Solution

The map has six 1s. The 2-by-2 square in rows CD=00 and 01, columns AB=11 and 10 covers the cases where the high bit of the first number is 1 and the high bit of the second is 0. The first number is then at least 2 and the second at most 1, so the low bits do not matter, and the term is $A\overline{C}$. Two 1s are left over. One is the cell where A, B, C and D are 0, 1, 0, 0, whose only neighbor that is a 1 is the cell where they are 1, 1, 0, 0. The high bits are equal there, both 0, and the low bits decide: B is 1 and D is 0. That pair, the horizontal pair in row CD=00, columns AB=01 and 11, reads $B\overline{C}\,\overline{D}$. The other is the cell where they are 1, 1, 1, 0. Its only neighbor that is a 1 is again the cell where they are 1, 1, 0, 0, and the pair is the vertical pair wrapping around the top and bottom edges in rows CD=10 and 00, column AB=11, which reads $AB\overline{D}$: the high bits are both 1 and the low bits decide again.

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

• $A\overline{C}$2-by-2 square: rows 00 and 01, columns 11 and 10
• $B\overline{C}\,\overline{D}$horizontal pair: row 00, columns 01 and 11 (2 cells)
• $AB\overline{D}$vertical pair, wraps top and bottom: rows 10 and 00, column 11 (2 cells)

Karnaugh map of GT: 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	1	1	1
CD=01	0	0	1	1
CD=11	0	0	0	0
CD=10	0	0	1	0

Groups drawn:

1. A and not C: 2-by-2 square in rows CD=00 and 01, columns AB=11 and 10; 4 cells.
2. B and not C and not D: horizontal pair in row CD=00, columns AB=01 and 11; 2 cells.
3. A and B and not D: vertical pair wrapping around the top and bottom edges in rows CD=10 and 00, column AB=11; 2 cells.

Description: The same map with three groups of two or four cells covering all six 1s.

Figure 3.9.16. The three groups of GT.

Tags: StandardKarnaugh maps

Exercise 3.9.3

Draw the map of segment L3, the bottom segment of the decoder, and find a minimal sum of products. Use the don't cares where they help.

Karnaugh map of L3: columns B3,B2, rows B1,B0; cell values are 0, 1 or X for don't care

	B3B2=00	B3B2=01	B3B2=11	B3B2=10
B1B0=00	1	0	X	1
B1B0=01	0	1	X	1
B1B0=11	1	0	X	X
B1B0=10	1	1	X	X

Description: A four-variable Karnaugh map of L3 with 1s, 0s and X cells.

Figure 3.9.17. The map of L3, with no groups drawn.

Hint

Not every X will be useful. Start with the biggest group you can make, and then see what it leaves.

Solution

The codes where B3 is 1 are the digits 8 and 9 and the six don't cares, and all of them fit in one group, so $B_3$ is a term. The 1s that remain are the digits 0, 2, 3, 5 and 6. The digit 5 is the hardest to cover. Its neighbors are the codes 4, 7 and 1, which are all 0 for L3, and the code 13, which is a don't care, so the only way to give 5 a group is to pair it with 13. That is the horizontal pair in row B1,B0=01, columns B3,B2=01 and 11, and it reads $B_2\overline{B_1}B_0$. Three groups of four cover the other digits. The term $B_1\overline{B_0}$ holds the codes 2, 6, 10 and 14, and $\overline{B_2}\,\overline{B_0}$ holds 0, 2, 8 and 10. The term $\overline{B_2}B_1$ holds 2, 3, 10 and 11, which is where the digit 3 is covered.

L3 = $B_3 + B_1\overline{B_0} + \overline{B_2}\,\overline{B_0} + \overline{B_2}B_1 + B_2\overline{B_1}B_0$

• $B_3$group of eight: columns 11 and 10 (8 cells); 6 of the cells are don't care
• $B_1\overline{B_0}$row of four: row 10 (4 cells); 2 of the cells are don't care
• $\overline{B_2}\,\overline{B_0}$four corners: rows 10 and 00, columns 10 and 00; 1 of the cells is a don't care
• $\overline{B_2}B_1$2-by-2 square, wraps left and right: rows 11 and 10, columns 10 and 00; 2 of the cells are don't care
• $B_2\overline{B_1}B_0$horizontal pair: row 01, columns 01 and 11 (2 cells); 1 of the cells is a don't care

Karnaugh map of L3: columns B3,B2, rows B1,B0; cell values are 0, 1 or X for don't care

	B3B2=00	B3B2=01	B3B2=11	B3B2=10
B1B0=00	1	0	X	1
B1B0=01	0	1	X	1
B1B0=11	1	0	X	X
B1B0=10	1	1	X	X

Groups drawn:

1. B 3: group of eight in columns B3,B2=11 and 10; 8 cells, 6 of them don't care.
2. B 1 and not B 0: row of four in row B1,B0=10; 4 cells, 2 of them don't care.
3. not B 2 and not B 0: four corners in rows B1,B0=10 and 00, columns B3,B2=10 and 00; 4 cells, 1 of them don't care.
4. not B 2 and B 1: 2-by-2 square wrapping around the left and right edges in rows B1,B0=11 and 10, columns B3,B2=10 and 00; 4 cells, 2 of them don't care.
5. B 2 and not B 1 and B 0: horizontal pair in row B1,B0=01, columns B3,B2=01 and 11; 2 cells, 1 of them don't care.

Description: The same map with five groups, the largest covering the two columns where B3 is 1.

Figure 3.9.18. The five groups of L3.

Tags: StandardKarnaugh maps

Exercise 3.9.4

A multiplier takes two 2-bit numbers, the first with bits A (high) and B (low) and the second with bits C (high) and D (low), and gives their product on four outputs P3, P2, P1 and P0. The largest product is 3 times 3, which is 9. Fill in the table, draw a map for each output and find a minimal sum of products for each.

Hint

Start with the products of 0, which are 0 in every output, and the products of 1, which are the other number. Then ask which products have a 1 in each bit.

Solution

Here is the table.

Truth table with 4 inputs (A, B, C, D) and outputs P0, P1, P2, P3; 16 rows in ascending binary order, A most significant

A	B	C	D	$P_{0}$	$P_{1}$	$P_{2}$	$P_{3}$
0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0
0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	0	0	0	0	0
0	1	0	1	1	0	0	0
0	1	1	0	0	1	0	0
0	1	1	1	1	1	0	0
1	0	0	0	0	0	0	0
1	0	0	1	0	1	0	0
1	0	1	0	0	0	1	0
1	0	1	1	0	1	1	0
1	1	0	0	0	0	0	0
1	1	0	1	1	1	0	0
1	1	1	0	0	1	1	0
1	1	1	1	1	0	0	1

P0 is 1 when the product is odd, which happens only when both numbers are odd, that is when both low bits are 1.

P0 = $BD$

• $BD$2-by-2 square: rows 01 and 11, columns 01 and 11

Karnaugh map of P0: 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	0	0
CD=01	0	1	1	0
CD=11	0	1	1	0
CD=10	0	0	0	0

Groups drawn:

1. B and D: 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11; 4 cells.

Description: A four-variable Karnaugh map of P0 with one group of four cells.

Figure 3.9.19. P0: the product is odd.

P1 is 1 for the products 2, 3 and 6, and the 1s are scattered. Each of the four terms below is a pair that no larger group can absorb.

P1 = $BC\overline{D} + A\overline{C}D + A\overline{B}D + \overline{A}BC$

• $BC\overline{D}$horizontal pair: row 10, columns 01 and 11 (2 cells)
• $A\overline{C}D$horizontal pair: row 01, columns 11 and 10 (2 cells)
• $A\overline{B}D$vertical pair: rows 01 and 11, column 10 (2 cells)
• $\overline{A}BC$vertical pair: rows 11 and 10, column 01 (2 cells)

Karnaugh map of P1: 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	0	0
CD=01	0	0	1	1
CD=11	0	1	0	1
CD=10	0	1	1	0

Groups drawn:

1. B and C and not D: horizontal pair in row CD=10, columns AB=01 and 11; 2 cells.
2. A and not C and D: horizontal pair in row CD=01, columns AB=11 and 10; 2 cells.
3. A and not B and D: vertical pair in rows CD=01 and 11, column AB=10; 2 cells.
4. not A and B and C: vertical pair in rows CD=11 and 10, column AB=01; 2 cells.

Description: A four-variable Karnaugh map of P1 with four groups of two cells each.

Figure 3.9.20. P1: the second-lowest bit of the product.

P2 is 1 for the products 4 and 6: two times two, two times three and three times two.

P2 = $AC\overline{D} + A\overline{B}C$

• $AC\overline{D}$horizontal pair: row 10, columns 11 and 10 (2 cells)
• $A\overline{B}C$vertical pair: rows 11 and 10, column 10 (2 cells)

Karnaugh map of P2: 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	0	0
CD=01	0	0	0	0
CD=11	0	0	0	1
CD=10	0	0	1	1

Groups drawn:

1. A and C and not D: horizontal pair in row CD=10, columns AB=11 and 10; 2 cells.
2. A and not B and C: vertical pair in rows CD=11 and 10, column AB=10; 2 cells.

Description: A four-variable Karnaugh map of P2 with two groups of two cells.

Figure 3.9.21. P2: the product is 4 or 6.

P3 is 1 only for three times three, whose product is 9.

P3 = $ABCD$

• $ABCD$single cell: row 11, column 11

Karnaugh map of P3: 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	0	0
CD=01	0	0	0	0
CD=11	0	0	1	0
CD=10	0	0	0	0

Groups drawn:

1. A and B and C and D: single cell in row CD=11, column AB=11; 1 cell.

Description: A four-variable Karnaugh map of P3 with a single 1 in the cell where all four inputs are 1.

Figure 3.9.22. P3: the product is 9.

Tags: ChallengeKarnaugh mapsTruth tables