In this question, a mapping is defined between EBCDIC and a superset of ISO-8859-1.

Your task is to build a network of two-input NAND gates that will take eight inputs A1, A2, A4, ..., A128 representing an EBCDIC character and return eight outputs B1, B2, B4, ..., B128 that represent the corresponding "ISO-8859-1" character according to that mapping.

To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4

Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

The logic circuit that uses the fewest NAND gates to correctly implement all the above requirements wins.

up vote 7 down vote accepted

727 Gates

How I did it:

  1. turned the code page translation from wikipedia into an appropriately formatted truth table using Excel (15 minutes)
  2. minimized the truth table using Espresso (5 minutes, 30 minutes on 1st iteration getting back into the saddle)
  3. fed the minimized truth table into a schematic generator (1 minute)
  4. iterated on 2&3 until I got a reasonable answer (<1 hour)
  5. turned the schematic into an uploadable image (30 min, %$#@! Microsoft)

Here's the 100% NAND gate result:

enter image description here

If I was actually going to implement this, I'd drop the NAND-centric scoring. Building XOR gates out of NANDs is a big waste of transistors. Then I'd start worrying about UMC, fire up the FPGA design tools, maybe break out the HDL manuals, etc. Whew! I love software.

NB, for hobbyists interested in FPGAs, I'll recommend FPGA4fun.

  • even when viewing image in new tab parts are unrecognizable :( – masterX244 May 3 '14 at 10:57
  • I decided to upload the largest image that fit on my screen. The original, at 23339x8538, kills browsers -- literally. Chrome "Aw, snap!"ed and Firefox just refused to load it. IE displays it, but hangs for a while preparing it. – Scott Leadley May 3 '14 at 17:56
  • zipping and then uploading that to your favourite cloud hoster should work case browser sdon't display images in zips – masterX244 May 3 '14 at 21:32
  • @masterX244 I could upload the gigantic bitmap, but (1) StackExchange wants us to upload to to avoid link-rot and Imgur would have reduced the resolution anyway. (2) If Imgur didn't reduce the resolution, every visitor to this page using Chrome would see "Aw, snap!" as it tried to read the entire image before scaling. (3) WYSIWYG; this answer ain't worth revising again. – Scott Leadley May 4 '14 at 0:02

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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