Product of Sums (POS) using K-map: dangling 0

boolean-algebralogic

I came across this question in my homework:

Design a "One's count circuit" with 4-bit input ABCD and 3-bit output PQR. The circuit counts the number of "1"s in the input.

(e.g. If ABCD = 1011, then PQR = 011. If ABCD = 1000, PQR = 001.)

Below is the truth table I made (I believe it should be correct):

The truth table

The question breaks down into subquestions asking us to make K-maps to implement P, Q and R respectively. In particular, they asked for Q's product-of-sums (POS) and R's sum-of-products (SOP) forms.

Problem 1: Q's POS form

I know that POS form can be derived from a K-map by circling "0"s instead of "1"s. There are totally 4 groups of $2^n$ "0"s here, but I'm not sure what to do with the lonely "0" in blue:

Q's K-map

Do I still circle it or ignore it?

Problem 2: R's SOP form

The K-map for R is a checkerboard pattern:

Q's K-map

I have never encountered or heard of this. What do I do?

Best Answer

It would be incorrect to leave out the single $0$ cell.

The product-of-sums (or Conjunctive Normal Form) of $Q$ is

$$(B \lor C \lor D) \land (A \lor C \lor D) \land (A \lor B \lor D) \land (A \lor B \lor C) \land (\lnot A \lor \lnot B \lor \lnot C \lor \lnot D)$$

The last disjunction of four negated literals corresponds the the single $0$ cell you are asking about. Each of the other three terms with three literals each correspond to two adjacent $0$ cells in the Karnaugh map.

             CD
       00  01  11  10
      +---+---+---+---+
   00 | 0 | 0 | 1 | 0 |
      +---+---+---+---+
   01 | 0 | 1 | 1 | 1 |
AB    +---+---+---+---+
   11 | 1 | 1 | 0 | 1 |
      +---+---+---+---+
   10 | 0 | 1 | 1 | 1 |
      +---+---+---+---+
Related Question