0
\$\begingroup\$

I'm trying to implement a clever way to do error correction of 4 bits with the classic 3 parity bit correction and such.

I'm constrained by the number of logic gates I can use, but I'm trying to implement the following logic expression

OUT = AB(~C) + A(~B)C + (~A)BC + ABC

I have access to A, B, C, ~A, ~B, ~C, (A + B), (A + B + C), ~(AB), ~(BC) from other parts of the circuit. I also have exactly one inverters and 4 NAND gates (2 inputs per gate) to spare. Is it possible to implement the above logic function?

(I am using ~ as logical NOT)

I've messed around with De Morgan and Karnaugh maps but they don't help much when it comes to gate-specific constraints like these.

UPDATE: I've freed up 1 extra inverter and 1 extra NAND, for a total of 2 inverters and 5 NANDs.

\$\endgroup\$
4
  • \$\begingroup\$ How many inputs on each of your NAND gates? It looks like four 3-input gates would do nicely. \$\endgroup\$
    – Dave Tweed
    Oct 1 '13 at 18:51
  • \$\begingroup\$ 2 inputs on each NAND. but if it's worth anything I'll upvote an explanation using 4 3-input gates \$\endgroup\$
    – ejang
    Oct 1 '13 at 18:54
  • \$\begingroup\$ Note that the last term can be combined with any one of the other three. \$\endgroup\$
    – Dave Tweed
    Oct 1 '13 at 18:58
  • \$\begingroup\$ yep, the k-map reveals that. i've figured out how to free up 1 more NAND gate and 1 more inverter from the rest of my circuit, so I have access to 5 now \$\endgroup\$
    – ejang
    Oct 1 '13 at 19:18
2
\$\begingroup\$

I think this is a solution, after playing with the expression a bit.

schematic

simulate this circuit – Schematic created using CircuitLab

Derivation:

$$ AB\overline{C} + A\overline{B}C + \overline{A}BC + ABC$$ $$ = AB(C+\overline{C}) + A\overline{B}C + \overline{A}BC $$ $$ = AB + A\overline{B}C + \overline{A}BC $$ $$ = AB + C\cdot(A\overline{B} + \overline{A}B) $$ $$ = \overline{\overline{AB} \cdot \overline{C\cdot (A\overline{B} + \overline{A}B)}} $$ $$ = \overline{\overline{AB} \cdot \overline{C\cdot (A+B)\cdot\overline{AB}}} $$ Turning the 3-input NAND into 2 2-input NANDs and an inverter: $$ = \overline{\overline{AB} \cdot \overline{C\cdot \overline{\overline{(A+B)\cdot\overline{AB}}}}} $$

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Great work. I love logic gate derivations. I'm seeing a therapist about it. \$\endgroup\$
    – scld
    Oct 1 '13 at 19:42
  • \$\begingroup\$ my favorite answer, for good explanation & clever use of my existing circuitry. thanks! \$\endgroup\$
    – ejang
    Oct 1 '13 at 19:46
2
\$\begingroup\$

Following up on @Dave Tweed, we can simplify the logical expression to

OUT = AB + BC + AC

Using DeMorgan's this again is equivalent to:

OUT = (AB)'' + (BC)'' + (AC)
OUT = ((AB)' (BC)')' + (AC)

This as it is, can easily be converted to a logic circuit that uses 2-input NAND gates

schematic

simulate this circuit – Schematic created using CircuitLab

\$\endgroup\$
5
  • \$\begingroup\$ However, this uses 4 more gates than available. \$\endgroup\$
    – scld
    Oct 1 '13 at 19:15
  • \$\begingroup\$ new development, i actually have 5 gates now. this one uses 5 gates and i can use the inverter to spare. cheers! \$\endgroup\$
    – ejang
    Oct 1 '13 at 19:28
  • \$\begingroup\$ @ejang Good to hear! I actually made a few changes. So I got rid of 2 NAND gates and put in that inverter of yours. Now this design is one you can work with! \$\endgroup\$
    – Shabab
    Oct 1 '13 at 19:30
  • \$\begingroup\$ @ChrisL Sorry for not mentioning earlier: Thanks for the review. I wouldn't have gone and been able to crrect my previous errors otherwise. \$\endgroup\$
    – Shabab
    Oct 1 '13 at 19:31
  • 1
    \$\begingroup\$ You can get rid of NAND1 and NAND2 because ~(AB) and ~(BC) already exist in "other parts of the circuit". \$\endgroup\$
    – Greg
    Oct 1 '13 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.