computer-architecturedigital-logiclogic-gates
I would like to implement a XOR gate which takes a 3-bit input (in other words, the modulo-2 sum of the input bits) using only 5 OR and AND gates. As this is a pure thought experiment, any number of inverters can be used.
Is this even possible? After crawling the web for a long time, the only solution I come up with is chaining two 3-gates XOR, which yields a sum of 6 gates.
Thank you in advance for your answers!
For the logic that you descibed you need a 32 input OR gate followed by an inverter. You do not want the XOR that you show in your diagram.
If you cannot get an OR gate with 32 inputs then work with some smaller sizes. For example, if all you can get are 4-input OR gates then it will take 8 of these gates to accept the 32 total inputs. Next use a second bank of two more of the 4-input gates to pickup the 8 outputs of the first stage. Finally use a 3rd stage of one final gate to accept the two outputs of the 2nd stage. The two remaining inputs of that 3rd stage gate can be tied to GND. The output of that 3rd stage gate connects to your inverter to produce the final output.
It really isn't worth worrying too much about this detail. Adding 1 to a number is such a common idiom in HDL that synthesis tools have highly-evolved methods for dealing wtih it. Also, most modern FPGAs have dedicated, hard-wired fast carry logic that does not consume logic cells, and that synthesis tools know how to take advantage of.
Best Answer
Expanding on Tom Carpenter's comment
simulate this circuit – Schematic created using CircuitLab where the 3 OR gates can be combined into a single 4-input OR gate (sorry, but the editor only provides 2 and 3 input gates).
It's not necessary to generate a Karnaugh map for this function. The output will be high if all 3 inputs are high (AND 1) or 1 input is high while the other 2 are low (AND 2,3,4).