Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 57 ยท Practice and Review

Practice: Combinational Logic

Ten worked exercises on number conversion, Boolean simplification, K-maps, adders, multiplexers, decoders and comparators, each solution checked by live Python.

Reading about logic is not the same as doing it. This lesson gives you ten exercises that cover the first half of the course: number systems, Boolean algebra, Karnaugh maps and the combinational building blocks. Each one has a short worked solution, and every solution is checked by a program so you can see that it really is correct.

The best way to use it: read an exercise, solve it on paper, then compare with the answer below it and run the checker. If your answer differs, run the checker on your expression. A wrong answer that fails a brute-force test teaches more than a right answer you only read.

A method for every exercise

Write the table A truth table removes ambiguity.
Simplify Use laws or a K-map, then group.
Check by brute force Compare against every input row.

Few-variable circuits are small enough to test exhaustively.

1 / 2

Before starting, you may want to revisit number systems, two's complement, Boolean laws and Karnaugh maps.

Part 1: numbers, algebra and K-maps

Exercise 1. Convert 0xB7 to binary and decimal. Convert decimal 156 to 8-bit binary and hexadecimal. Write -37 as an 8-bit two's complement number. Finally, give the 4-bit Gray code for the binary number 1011.

Exercise 2. Add 0x7F + 0x01 in 8 bits. What is the result, and what are the carry and signed-overflow flags?

Exercise 3. Simplify with Boolean laws: (a) F = A'B + AB + AB'; (b) F = AB + A'C + BC.

Exercise 4. Simplify F(A,B,C,D) = ฮฃm(0, 2, 5, 7, 8, 10, 13, 15) with a K-map.

Exercise 5. Simplify F(A,B,C,D) = ฮฃm(1, 3, 7, 11, 15) with don't-cares at d(0, 2, 5).

Run the checker below. It prints the conversions and then tests each simplified expression against the original over every input combination.

Python Check the answers to exercises 1 to 5

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions

Exercise 1. 0xB7 is 1011 0111: the nibble B is 1011 and 7 is 0111, so the value is 183. For 156, divide into powers of two: 128 + 16 + 8 + 4, giving 10011100, which groups as 1001 1100 = 0x9C. For -37, write 37 as 00100101, invert to 11011010 and add one to get 11011011 = 0xDB. The Gray code of a number is the number XOR itself shifted right by one: 1011 ^ 0101 = 1110.

Exercise 2. 0111 1111 + 0000 0001 = 1000 0000. The carry out is 0, because the result still fits in 8 bits as an unsigned number (128). But two positive signed numbers produced a negative result, so signed overflow is 1: 127 + 1 does not fit in the range -128 to 127.

Exercise 3. (a) Combine A'B + AB into B, leaving B + AB'. The absorption-style identity X + X'Y = X + Y turns this into B + A. So F = A + B. (b) This is the consensus theorem: BC is redundant because every input where BC is 1 already makes AB or A'C 1 (when B = C = 1, either A = 1 so AB = 1, or A = 0 so A'C = 1). So F = AB + A'C. Consensus terms matter again when you study hazards, where adding such a term is sometimes deliberate.

Exercise 4. The ones at minterms 0, 2, 8 and 10 are the four corners of the map. They form one group where B = 0 and D = 0, giving B'D'. The ones at 5, 7, 13 and 15 form a 2 by 2 block where B = 1 and D = 1, giving BD. So F = B'D' + BD, which is XNOR of B and D. The checker confirms it.

Exercise 5. Treat the don't-cares as ones where they help. Cells 0, 1, 2 and 3 form a group with A = 0 and B = 0, giving A'B'; it uses the don't-cares 0 and 2 for free. Cells 3, 7, 11 and 15 are the group C = 1, D = 1, giving CD. So F = A'B' + CD. Another correct answer is A'D + CD, which uses the don't-care at 5 instead; both agree on every row where the function is specified, which is exactly what the checker tests.

Part 2: building blocks

Exercise 6. Add 0110 + 0111 with a 4-bit ripple-carry adder. Give the carry out of each stage and the final result and flags.

Exercise 7. Implement F(A,B,C) = ฮฃm(1, 2, 4, 7) with a single 4:1 multiplexer. Use A and B as the select lines.

Exercise 8. Build the full adder's sum and carry out using one 3:8 decoder and two OR gates.

Exercise 9. Write the logic for a 2-bit comparator output A > B, where A = A1A0 and B = B1B0.

Exercise 10. Design a 4-input priority encoder (highest-numbered active input wins) with outputs Y1, Y0 and a valid flag.

Python Check the answers to exercises 6 to 10

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions

Exercise 6. Bit 0: 0 + 1 = 1 with no carry. Bit 1: 1 + 1 = 10, so sum 0, carry 1. Bit 2: 1 + 1 + carry 1 = 11, so sum 1, carry 1. Bit 3: 0 + 0 + carry 1 = 1, carry 0. The result is 1101, with carry out 0. As unsigned numbers 6 + 7 = 13, correct. As signed numbers 1101 is -3, so signed overflow is 1 (the carry into the top bit is 1 and the carry out is 0). See Half Adders and Full Adders if the flag rule feels unfamiliar.

Exercise 7. With A and B as selects, each mux data input is a function of C alone. Look at the four rows of the truth table. For AB = 00, F is 1 only when C = 1 (minterm 1), so the input is C. For AB = 01 (minterm 2 is 010), F = 1 when C = 0, so the input is C'. For AB = 10 (minterm 4 is 100), again C'. For AB = 11 (minterm 7 is 111), F = 1 when C = 1, so C. The data inputs are C, C', C', C. This is the three-input XOR: a mux can implement any 3-variable function this way. More in Multiplexers and Demultiplexers.

Exercise 8. A decoder outputs one line per minterm, so any function is the OR of its minterm lines. The full adder's sum is 1 for minterms 1, 2, 4, 7 and its carry for minterms 3, 5, 6, 7. That is one 4-input OR for S and one for Cout. This is the "decoder as minterm generator" idea from Decoders, Encoders and Priority Encoders.

Exercise 9. A > B happens if the high bits already decide it (A1 = 1, B1 = 0), or if the high bits are equal and the low bits decide it (A0 = 1, B0 = 0). Equality of two bits is XNOR. So A>B = A1ยทB1' + (A1 โŠ™ B1)ยทA0ยทB0'. It checks out on all 16 input pairs. Wider comparators repeat this pattern from the most significant bit down.

Exercise 10. Input D3 has the highest priority. Y1 = D3 + D2, because both codes 11 and 10 have the top bit set. Y0 = D3 + D2'ยทD1: code 11 for D3, and code 01 only when D2 is off and D1 is on. The valid flag is the OR of all four inputs; without it, "no input active" and "input 0 active" would both produce 00.

Where to go next

If any exercise went badly, go back to the lesson linked from it and redo the matching example. Once these feel comfortable, move on to the sequential half of the course with Practice: Sequential Logic, where the same approach (write the table, derive, check by simulation) applies to flip-flops and state machines.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the quickest way to be sure a simplified expression equals the original?

    With only a handful of variables you can test every row of the truth table, and equal outputs on all rows means the functions are the same.
  2. 2. In exercise 5, why may the group A'B' include cells 0 and 2?

    Don't-care cells may be treated as 1 or 0, whichever gives a larger group and a simpler term. Here treating them as 1 lets A'B' cover cells 0 to 3.
  3. 3. A mux with selects A and B implements a 3-variable function. What goes on its data inputs?

    For each combination of A and B, the function depends only on C, so each data input is one of 0, 1, C or C'.
  4. 4. 0x7F + 0x01 in 8 bits gives 0x80. Which flags are set?

    The unsigned result 128 fits in 8 bits, so there is no carry out. As signed numbers, 127 + 1 exceeds the maximum of 127, so signed overflow is set.

Summary

  • Convert between bases by grouping bits in fours, and negate two's complement numbers by inverting and adding one.
  • Simplify with Boolean laws or a K-map; use don't-cares to build larger groups.
  • A multiplexer implements any function when its data inputs are 0, 1, a variable or its complement.
  • A decoder generates minterms, so any function is an OR of decoder outputs.
  • Always verify a design by testing every input combination; for few variables it is cheap and conclusive.

Next: Practice: Sequential Logic.