boolean logic - circuits using karnaugh's map technique -

a combinational circuit designed counts number of occurrences of 1 bits in 4 bit input. however, input 1111 invalid input circuit , output in such case 00.

one valid input such circuit may 1110 output 11; valid input may 1010 output 10.

draw truth table circuit. use karnaugh map design circuit , draw using and,or , not gates.

because 4bit input can have @ 4 ones in it, can encode output 3bit long binary number.

the truth-table this:

 w x y z   y_2 y_1 y_0 ---------+-------------   number of positive bits  0 0 0 0 |  0   0   0   ~ 0  0 0 0 1 |  0   0   1   ~ 1  0 0 1 0 |  0   0   1   ~ 1  0 0 1 1 |  0   1   0   ~ 2 ---------+-------------  0 1 0 0 |  0   0   1   ~ 1  0 1 0 1 |  0   1   0   ~ 2  0 1 1 0 |  0   1   0   ~ 2  0 1 1 1 |  0   1   1   ~ 3 ---------+-------------  1 0 0 0 |  0   0   1   ~ 1  1 0 0 1 |  0   1   0   ~ 2  1 0 1 0 |  0   1   0   ~ 2  1 0 1 1 |  0   1   1   ~ 3 ---------+-------------   1 1 0 0 |  0   1   0   ~ 2  1 1 0 1 |  0   1   1   ~ 3  1 1 1 0 |  0   1   1   ~ 3  1 1 1 1 |  1   0   0   ~ 4 

but! output in case on 2 bits. specification consider 1111 input invalid 00 output. therefore can delete significant column in truth table , there no other change:

 w x y z   y_1 y_0 ---------+---------   number of positive bits  0 0 0 0 |  0   0   ~ 0  0 0 0 1 |  0   1   ~ 1  0 0 1 0 |  0   1   ~ 1  0 0 1 1 |  1   0   ~ 2 ---------+-------------  0 1 0 0 |  0   1   ~ 1  0 1 0 1 |  1   0   ~ 2  0 1 1 0 |  1   0   ~ 2  0 1 1 1 |  1   1   ~ 3 ---------+-------------  1 0 0 0 |  0   1   ~ 1  1 0 0 1 |  1   0   ~ 2  1 0 1 0 |  1   0   ~ 2  1 0 1 1 |  1   1   ~ 3 ---------+-------------   1 1 0 0 |  1   0   ~ 2  1 1 0 1 |  1   1   ~ 3  1 1 1 0 |  1   1   ~ 3  1 1 1 1 |  0   0   ~ invalid, showing zeros 

now can use different styles minimizing output functions y_1 , y_0, think karnaugh maps suitable this.

transfer lines of truth-table each of output functions separate k-map using indexes (number of line in table indexed zero) or comparing combinations of variables.

for output function y_0 final k-map looks , can see minimized sop (dnf; disjunction of conjunctions) function no larger groups (terms) found.

y_0 = ¬w·¬x·¬y·z + ¬w·x·¬y·¬z + ¬w·¬x·y·¬z + ¬w·x·y·z         + w·¬x·y·z + w·x·y·¬z + w·¬x·¬y·¬z + w·x·¬y·z 

for significant bit of output chose find pos (cnf; conjunction of disjunctions), because there fewer cases of 0 bits 1 bits in output.

the output function can in y_0 described marking out right bits. in case k-map , function:

y_1 = (w + x + y + z) · (w + x + y + ¬z) · (w + ¬x + y + z)        · (w + x + ¬y + z) · (¬w + ¬x + ¬y + ¬z) · (¬w + x + y + z) 

but can minimized output function in k-map:

y_1 = (w + x + y) · (w + y + z) · (w + x + z)        · (¬w + ¬x + ¬y + ¬z) · (x + y + z)  

after can use right gates or transform more suitable combination of gates using rott's grids.