Forgot your password?
typodupeerror
Education Programming Hardware News

From a NAND Gate To Tetris 103

Posted by Unknown Lamer
from the artisinal-programming dept.
mikejuk writes "Long before the current crop of MOOCs (Massive Online Open Course) there was a course that taught you all you needed to know about computers by starting from the NAND gate and working its way up through the logic circuits needed for a computer, on to an assembler, a compiler, an operating system, and finally Tetris. Recently one of the creators of the course, Shimon Schocken, gave a TED talk explaining how it all happened and why it is still relevant today. Once you have seen what is on offer at http://www.nand2tetris.org/ you will probably decide that it is not only still relevant but the only way to really understand what computers are all about."
This discussion has been archived. No new comments can be posted.

From a NAND Gate To Tetris

Comments Filter:
  • by wdef (1050680) on Tuesday October 16, 2012 @03:54AM (#41666583)

    Looks great, much like I imagined studying Comp Sci ought to be. Ok one can get the book and use the materials for self-learning, but is there a list of institutions using the course for credit?

    So many great courses and great teachers around now. Pity they didn't get all this together way back in my day. I've just been working my way through http://michaelnielsen.org/blog/quantum-computing-for-the-determined/ [michaelnielsen.org] and am astonished at the simplicity and lucidity of Nielsen's teaching.

  • Re:Logic is Logic (Score:5, Informative)

    by dkf (304284) <donal.k.fellows@manchester.ac.uk> on Tuesday October 16, 2012 @04:44AM (#41666771) Homepage

    AND, OR, NOT, NAND, NOR, XOR and XNOR are still the 7 basic logic elements that make up all digital electronics and programming.

    Actually, real digital circuit design uses rather more elements than that, some of which can't be derived from those ideal elements either. Even excluding the clock generator (a thoroughly analog component in its core) there's still some really strange things you can usefully do with transistors that just won't model as anything simpler; my favorite is the arbitrator, it determines which signal rose (or lowered) first and which is used to connect together parts of a chip that use a common power supply but unsynchronized clocks. Simplistic digital theory says it can never work, but in reality it's very effective (and it depends on the fact that transistors are analog devices with some quantum mechanical behavior for disambiguating in the tricky cases. Mad, fun, mad fun!)

  • Re:Logic is Logic (Score:5, Informative)

    by sFurbo (1361249) on Tuesday October 16, 2012 @05:27AM (#41666909)
    You have 2 inputs that can each be 1 or 0, so there are 4 different inputs. For each of those, you have 2 possible outputs, so there are 2^4=16 different truth tables.

    Of these, 8 are symmetrical in A and B (gives the same output for input (1,0) and (0,1)). Theses are AND, OR, NAND, NOR, XOR, XNOR, TRUE and FALSE

    The remaining 8 are 4 sets of duplicates (if you switch A and B, we call the gate the same name). These are A, not-A, A AND NOT-B, and its negation, NOT-A OR B. The two last does not seem to be standard gates, so no, there are, in fact, two more non-trivial truth tables for two inputs.
  • Re:Logic is Logic (Score:5, Informative)

    by famebait (450028) on Tuesday October 16, 2012 @05:31AM (#41666927)

    No, but it sums up all the useful/practical ones.
    If you only have two inputs, there are only 4 rows in the table,:
    | A | B |
    | 0 | 0 |
    | 0 | 1 |
    | 1 | 0 |
    | 1 | 1 |

    This yields only 16 possible output columns:
    0000 - does not vary with input
    0001 - AND
    0010 - not commutative
    0011 - reacts only to A
    0100 - not commutative
    0101 - reacts only to B
    0110 - XOR
    0111 - OR
    1000 - NOR
    1001 - XNOR
    1010 - reacts only to B
    1011 - not commutative
    1100 - reacts only to A
    1101 - not commutative
    1110 - NAND
    1111 - does not react to input

    That makes 6 potentialy desirable operations. The seventh is NOT, which takes only one input.
    The not commutative ones could conceivably be put to useful work, but in physical designs the asymmetry is impractical, and you can trivially construct them from other gates if need be. In fact some of the useful ones ar also usually constructed from combinations of the others, and all of them *can* be constructed from combinations of NAND gates.

  • by Anonymous Coward on Tuesday October 16, 2012 @07:08AM (#41667261)

    This was given as a course in my University (the Hebrew University in Jerusalem) eight years ago in which the lecturer was the other creator (Prof. Noam Nissan).
    I think the beauty of it is the fact that you manage to understand the principles of each level of the architecture without going into deep depth of each one, and so it manages to remain interesting throughout the course.
    At the end of the course, we ended up writing xonix (which involved writing a non-recursive flood-fill algorithm).
    Some team even wrote Socoban.

  • Re:Logic is Logic (Score:4, Informative)

    by tlhIngan (30335) <(ten.frow) (ta) (todhsals)> on Tuesday October 16, 2012 @11:41AM (#41669607)

    AND, OR, NOT, NAND, NOR, XOR and XNOR are still the 7 basic logic elements that make up all digital electronics and programming

    Of which, NAND and NOR are the primitives - you can constract any gate (and thus truth table result) you want out of purely NAND or purely NOR gates.

    Why you pick one over the other is down to limitations of CMOS - PMOS transistors have to be much larger than NMOS ones to be as fast. NAND puts the fast NMOS transistors in series giving you much faster switching than if the PMOS transistors were in series (as it would be in a NOR gate)

Often statistics are used as a drunken man uses lampposts -- for support rather than illumination.

Working...