8-bit Computer Made Solely From NAND Gates

As an electronics rookie, one of the first things they tell you when they teach you about logic gates is, “You can make everything from a combination of NAND gates”. There usually follows a demonstration of simple AND, OR, and XOR gates made from NAND gates, and maybe a flip-flop or two. Then you move on, when you want a logic function you use the relevant device that contains it, and the nugget of information about NAND gates recedes to become just another part of your electronics general knowledge.

Not [Alexander Shabarshin] though. He’s set himself the task of creating an entire CPU solely from NAND gates, and he’s using 74F00 chips to give a hoped-for 1MIPS performance.  His design has an 8-bit data bus but a 4-bit ALU, and an impressive 2-stage pipeline and RISC instruction set which sets it apart from the computers most of us had when 74-series logic was a much more recent innovation. So far he has completed PCBs for a D-type flip-flop and a one-bit ALU, four of which will work in parallel in the final machine

Unsurprisingly, we have maintained a keen interest in TTL computers here at Hackaday for a very long time. You might say that we have featured so many for the subject to deserve a review article of its own. There is the ASAP-3, the Magic-1, the Duo Basic, the Apollo181, the unnamed CPU made by [Donn Stewart], the BMOW, and a clone of the Apollo Guidance Computer. But what sets [Alexander’s] project aside from all these fine machines is his bare-metal NAND-only design. The other 74-series CPU designers have had the full range of devices such as the 74181 ALU at their disposal. By studying the building blocks at this most fundamental level a deeper understanding can be gained of the inner workings of parts normally represented just as black boxes.

One of the briefs for writing a Hackaday article is that if the subject makes the writer stop and read rather than skim over it then it is likely to do so for the reader too. This project may not yet have delivered a working CPU, but its progress so far is interesting enough for an in-depth read. Definitely one to watch.

54 thoughts on “8-bit Computer Made Solely From NAND Gates

    1. I disagree.

      This is an impressive physical demonstration of the “anything from NAND” law. Also, this could be a great teaching tool since you can actually logic-probe the states inside the functional blocks.

        1. Look how well that worked for reddit.
          A small group of outspoken individuals stifle discussions they deem “problematic”.
          Interesting comments with different perspectives get buried because they aren’t from a celebrity user.
          Comments and posts are viewed as “more valid” or “more important” if they have more upvotes.

          The inclusion of a voting mechanism turns discourse into a popularity contest.

          It takes less effort, and is better for the community if people learn to ignore a disruptor instead of imposing censorship.

          1. Here’s a different viewpoint that also agrees with you:

            Yes, upvote/downvote turns everything into a popularity contest. Yes, memes and references to video games would be pushed to the top. Yes, the quality of discussion would go down.

            however, and this is important here: We purposefully don’t moderate comments for content. Yes, if it’s actual illegal speech or spam we take it down, but other than that, everything goes up. It also goes up in chronological order. That means whoever is the first to shitpost steers the entire conversation. Because we (hackaday) effectively don’t moderate comments in the interests of allowing all viewpoints to be expressed, the most extreme viewpoints are the majority.

            Now, here’s what I’m thinking. There is a silent majority here (lurkers), who are real, actual, not shitheads. These are people who would upvote good comments and downvote bad ones. If we implemented a voting system, the incidence of ‘not a hack’ comments would go down, to be replaced with “lol, half life 3” comments. Yes, both options suck, but I’d rather have idiotic banality instead of dumbasses dumping on every single post here.

          2. @Brian Benchoff
            I think you’re right about this. I find it much easier to ignore boring-stupid than caustic-stupid.

            My only concern is that the subject matter of the site attracts people who are both able and likely to screw with the upvote system for fun. :V

          3. Dear Brian, I don’t think that’s the case. Why would this silent majority, who are completely separate from, and in no way resemble the active posters, want to sit there reading comments silently? Why does the first poster “steer” a conversation? That’s not true at all. People see something they agree / disagree with, and post a response, if they want to. That’s all there is.

            Hackaday isn’t a “social media” site. You have a very particular group of users here. I’ve tried explaining it before, it’s the sort of “engineer’s mindset”. Where being technically correct is the best kind of correct, and social conventions and niceties are seen as irrelevant fluff for the masses. Of course that doesn’t exclude the negative counterparts of those niceties, the nastyities. But I think most of us can take a punch on the chin or else we wouldn’t come back.

            There’s a lot to learn here from commentors. And also sometimes the opportunity for a good argument. Having outspoken arguments is everyday life for a particular sort of intelligent geek, the type we have here. It’s intellectual exercise, it’s good for you. We don’t need to make friends here, so it’s cool.

            Audience comes with the territory. I’m sure most of the other staff, the ones who’d worked in technical fields for years, aren’t shocked or surprised by the sort of people that post here. Sure, they might not exactly be PROUD of them. But it’s certainly a scene they’ve seen before.

            You’ve got a unique thing, here, and the best thing you can do is leave it like it is. Don’t worry about it. The site’s respected, even if some of the users aren’t. It has to be this way. I can’t think of a single way of making people “nicer”. In real life or on this site. Learn to see the good side of it, learn to understand the sort of people we have here, how they work, how they think, what’s important to them. It makes sense. You might not end up loving ’em, but you might understand.

          4. I agree with Greenaum (oh the dissonance of it all!) :-)

            The only information that adults should be concerned about is that which is deliberately counter-factual (a problem that other sites still have even with voting systems, sometimes more so) and or of a vexatious nature, which is harder to prove than some may claim.

          5. Also, Booby, I think Reddit’s voting system, particularly to screen out posts based on popularity, started because Reddit has so many posts, that come quickly. Their system, though I don’t agree with it, is intended to make a large volume of posts more manageable.

            Reddit is also much closer to mass culture. They have a lower average IQ than we do here. So idiocy and fluff is more the sort of thing they’re happy with. They also have problems like brigading, people bringing masses of others in (from F——-, >shudder<) to support their stupid shit.

            If you think this place is bad NOW…

          6. Brian, if SupplyFrame would be interested in comment enhancements I can write you a personalized user comment moderation plugin. User-side, running in the browser = no additional server load and no touching of the wordpress database.

            Something as simple as pull-down menu with 3 options:
            -gray out comments from this user
            -move all comments from this user to the bottom
            -block comments from this user

            By personalized I mean every reader would keep _his own moderation list_, just like in the good old days of usenet killfiles. No groupthink, no centralised censorship.
            It would simply be a mod of what I use for a couple of years now ( https://github.com/raszpl/HaDcomments )

          7. Rasz_pl, killfiles (that’s what you’re describing, mostly) are one of the many reasons Usenet, 30 years ago, was much better for all this conversation nonsense than web “forums” are today. For starters it was designed exactly for that, rather than sharing results round CERN as networked hypertext. Usenet also worked fine in offline reading mode, important when you had to pay for the time you spent online (back when I were a lad…).

            The user could do all the censorship and filtering he liked, at his end. He could decide exactly what he wanted to see. It shut the censorship argument right up. No crusading arse-pain soccer moms, deciding the Internet ought to be a fit babysitter for the children they couldn’t be bothered to supervise or spend time with. Everyone could see, or not see, whatever and whoever they wanted. Or didn’t want.

            Your idea seems quite a bit like that. Could you implement it as a browser plugin? Could you make it compatible with other sites?

            Either by adding in support yourself for particular sites (maybe as modules the user chooses to add), or you could have some mechanism where the user, or your plugin, figures out what it needs to block. Adblock Plus allows that, lets the user select certain elements of a page, visually. This version, that I’m imagining, could work like that. The user would select the name of the person they don’t want to see, and define the scope of each post, so the script would know what to look for, and what to block.

            Might end up being a popular thing. You could even charge for it. Or, possibly better, sell it to Facebook and retire! Well, probably not Facebook, they like to be in control of what “their” users see. Maybe WordPress or somebody. But the idea of doing it client-side would mean it didn’t need any support from sites.

            Might have legs. Just an idea. I get 5%, advisor’s fee.

    2. You’d need a hell of a lot of breadboards for the finished computer. This is a big and complex thing. I wouldn’t wanna have to chase down the bugs. Keeping everything modular and heirarchical should be the key, having replacable, standard modules that you can swap out to chase bugs.

    3. The understanding required to do this isn’t small. There is literally no pleasing some people, sometimes. Just understand that some people will like it, even if you do not. Do you write the editor of every newspaper and magazine that you read with this stuff? No? then don’t do it here. Fair?

  1. In my early years I worked for NCR before I had to join the military. I worked at their plant in Hawthorne CA wher they made their Century series of computers. Most if not all of their logic boards used either nand or nor chips. These were custom ICs IIRC they were NCR80 and NCR94 and operated on 4 volts. This was back in the late 60s.

      1. That’s a bit overkill really ;)
        Tetris in 6502 ASM fits in about 2k of RAM for both c64 and a2 versions.
        You’d be hard pressed to get your first hand-written non-optimized “i just wanted it to work” compiler to beat that.
        Of course that amount of RAM out of NAND gates may mean a few more sleepless months spent at the iron…

        1. You could store it in ROM. Lots of interesting ROMs, back in the day. One, I think IBM for microcode storage, was a grid of diodes, with address decoding on one edge. You program it with a pair of wire snippers

          Another, also IBM and I think maybe microcode storage, was capacitive. A grid of little circles cut into a dielectric material. You either made or didn’t make a hole, to set the 0 or 1. I dunno how the bits were accessed, I’d guess in a grid arrangement, rows and columns on either side. Obviously needed to be accessed with AC, or pulses, but all the supporting gubbins was simpler than using more complicated circuits for the storage itself. Was also, of course, fairly easy to re-program, which has to be an advantage.

          I think the “standard”, such as it is, method for ROM was core rope. Rather than core on a grid. Dunno why, sounds nightmarish, and gods help you debug it. You either ran, or didn’t run, the data sense line through a particular core, to get your 1s and 0s.

          Annnnyway…. By “a2” you mean Atari 2600? Only has 128 bytes of RAM. 1 kilobit. Games run from standard mask ROM chips, usually, in the plastic game cartridges. Some smaller companies might use EPROM instead.

          Most interesting / terrifying thing about programming the 2600, was it’s utter lack of screen RAM. Well, to be fair it had something like 15 bytes of screen RAM. Registers really. You send the data to the relevant registers, per scanline, which of course you have to keep count of. There’s an instruction STA WSYNC, which sends any old data to the WSYNC hardware register, which halts the CPU til the next horizontal sync comes round. Gives you just enough timing (and it’s all you’re gonna get!) to produce a stable screen.

          You had 1 8-bit register each for the 2 sprites, it’s appearance on that scanline. Another for balls and missiles. Another 20 bits for the chunky background. Which only filled half the screen horizontally, so there’s another bit to set to either reflect the background round the middle, or just repeat it. You can see that limitation in many, many games on it, though if you’re really quick with the timing you can sneak in new data for the second half.

          And that’s this week’s Antiques Roadshow For Geeks. Thankyou!

      1. If it’s Turing-complete, yes! Interfacing might be a bit of a bugger. And you’d need enough storage. Give it an old ISA network card though, and it could be Beowulfing away, perhaps enough to provide a few KIPS.

        Actually 7400-type logic was used in early supercomputers, rather than the CPU chips which were available. Bit-sliced ALUs and fast static RAM for registers. They could run up around 25 – 35 MHz, which was worth doing back then. Of course, it’d cost ya!

        Done right, and maybe using a fast variant rather than plain 7400, he might actually get something pretty powerful.

  2. Nice project – if the author is reading, where are you sourcing bulk TTL chips from?

    Fun fact of the day: The Cray-1 was built with only four different chips. From Wikipedia:

    The Cray-1 used only four different IC types, an ECL dual 5-4 NOR gate (one 5-input, and one 4-input, each with differential output), another slower MECL 10K 5-4 NOR gate used for address fanout, a 16×4-bit high speed (6 ns) static RAM (SRAM) used for registers and a 1,024×1-bit 48 ns SRAM used for the main memory. These integrated circuits were supplied by Fairchild Semiconductor and Motorola. In all, the Cray-1 contained about 200,000 gates.

    1. Interesting! Anyone have any idea why they used just NOR rather than a combination of different gates? Is there something about NOR that lends itself to computers, or logic generally? Was it perhaps to do with speed? So they’d know they were all the same speed, to help keep the design tolerable? AKA Seymour got to keep his mind in one piece. Is NOR particularly better than NAND? Did they need so many inputs, or were many of the gates’ inputs just tied to ground?

      I suppose Seymour knew what he was doing, even as he was inventing a new type of computer from bare bones. I’ll have to look up more about the Cray-1, wonder what sort of instruction set it had. Maybe some SIMD? Maybe RISC, which I’d wanna do if I had to implement the bloody thing in NOR gates.

  3. I have to chuckle a bit because way down at the bottom level, every computer you’ve ever used is made “solely of nand gates” (or, depending on the technology, nor gates.

    But that’s a quibble.

    This reminded me of my first days in engineering in the 80’s. I was working for an aerospace contractor and the new grads were assigned to a then new (for defense) concept called “asics” because we weren’t afraid of CAD stations.

    There was a catch, though. Our contracts stated that our delivered designs had to be compatible with any approved chip vendor – and all of them had wildly incompatible libraries and technologies with an enormous range of speeds.

    What they all *did* have, though were fast(ish) nand gates and D flip-flops, so I spent six months building a video-processing chip for a missile out of 20,000 individual gates. I remember one 12×12 bit pipelined multiplier that spread over 20 schematic pages.

    1. Did you put your NAND based work into a library of blocks so that you could then work at a higher level and still know that the end result was reasonably portable over those different offerings from vendors?

      1. There are many missiles that use a video imager (camera) for targeting. For instance, the AIM-9R was one such missile that was under development in the 1980’s but there are other missiles that were developed (and deployed) before the AIM-9R program.

    2. Well, not exactly NAND. Although flash ROM usually uses either NAND or NOR to store it’s bits. NOR is better in some ways, and a bit more expensive.

      Sure you CAN implement any logic in NAND, but obviously it’s faster, propagation delay wise, to use an AND gate, rather than a NAND followed by another NAND with it’s inputs tied together.

      Ultimately they end up implemented as transistors. Do they use a logic-gate level as an abstraction, so everything is described at the low level as logic gates? Or do they design straight to transistor level?

      Are CPUs designed much by hand nowadays? I know computers do a lot of the work, and the formal proofs. But maybe individual tweaks are made by humans? Or are computers better at that?

      There’s certainly some insanely clever stuff implemented in CPUs, it’s a bit of a miracle they end up working, all few billion transistors, functioning exactly correctly. Each transistor getting down to the scale of atoms, where quantum tunnelling letting current leak is a significant problem.

  4. Every week we had to turn in our programming assignment, plus something that interested us. So I remember one week I was interested in how a half-adder worked. So I created a half-adder using the BASIC language logic instructions. Of course it was all serial. But then the next week, I figured that was fun, so I created a full-adder.

    Sorry to say, I got really hot into more difficult weekly assignments, but this project reminded me of that.

  5. I’m sligitly interested that nobody’s queried his use of 74F series gates, because that was what came to my mind as I wrote it up. Are they really still the fastest on the block? I would expect some of the newer families to be a quicker choice.

    The answer could of course be that the choice available in a DIL form factor these days is more restricted.

  6. nand is the coolest gate. 0111. why? because its the inverse input of 1110 – but if all youve got is those gates, im afraid it doesnt work. this dickhead didnt explain how he had inverters going, because I KNOW. you cant make a computer out of nand without inverters, otherwise you wouldnt need transistors.

    1. You just join both inputs of the NAND gate together. There’s your inverter. You really can make any logic gate out of NANDs, it’s a long-established fact. Try it yourself on a bit of paper.

      Of course, nobody actually does build computers just from NAND, because it’s more efficient to use all the types of gate where they’re needed. An OR gate that’s actually an OR gate, not 4 or 5 NANDs. Saves space, transistors, power budget, and signal propagation time. Or to boil it all down, it saves transistors.

      The NAND gate itself is made from transistors, that’s why you need them!

      1. They were trying to say that signal inversion needs a transistor, the bit that is count-factual is the suggestion that the NAND does not contain and inverting transistor, which is a silly assertion.

        There is one exception, any gate can be represented by a lookup table, in fact all logic gates of a given bit-width can be constructed with the one table as some of the input bits are address lines that select the logic function that you want. This means you can have a universal gate as a ROM constructed with only diodes. The problem there is an electrical rather than a logical one, what keeps your voltage levels at the correct level throughout your entire circuit? Transistors, Valves, or transformers, and a few other exotic options.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s