[ Editor: What is the minimum number of two-input NAND gates needed to build a crossover circuit, which...
logic/crossover New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
[ Editor: What is the minimum number of two-input NAND gates needed to
build a crossover circuit, which swaps two signals without any wires
crossing? ]
Cross the wires without crossing the wires! [ Editor: Fill the black
box with two-input NAND gates (each NAND has 2 inputs and 1 output) so
that the input on the top line comes out on the bottom line and vice
versa. Reworded from the original: "IMPROVE THE CROSSOVER CIRCUIT /
Find the minimum number of NAND-gates / fill the black box with some
quantity of NANDs / each NAND has 2 inputs & 1 output" ]
input output
A -----> +-------+ -----> B
| black |
B -----> | box | -----> A
+-------+
trivial: 12 two-input NAND gates
easy: 10 two-input NAND gates
difficult [ Editor: "dificult" in the original ]: 8 two-input NAND gates
Show solution
I think 8 NANDs [ Editor: "8*NAND" in the original ] is the best
solution.
eight-gate solution:
U.S. Patent 3,248,573 [ Editor: "3'248'573" in the original ] (1966)
to Lester M. Spandorfer - Cheltenham, Pa.
Albert B. Tonik - Dresher, Pa. [ Editor: "Pa" in the original ]
Shimon Even - Cambridge, Mass.
-- Jose Manuel Oliveira <si504340@ci.uminho.pt> [ Editor: name posted
as "jose manuel oliveira", signed "ZE OLIVEIRA" ]
[ Editor: The eight-gate circuit itself was not given in the collected
postings. ]