A JavaScript and HTML5 canvas project to simulate logic circuits arranged on a 2D square lattice.
See the project in action here.
The inspiration for this project comes from marble machines used to demonstrate logic circuits and computation. Great examples of these include:
- Digi-Comp II
- Turing Tumble
- This adding machine on YouTube
- This Rule 110 on YouTube
- This AND gate on YouTube
Many of these examples were inspired by the Digi-Comp. Many other mechanical computer predate these examples, most relying on gear systems for their computation. Notable examples include:
The marble machines in the list aboves generally keep track of these state using the positions of switches, whose positions are changed by the marbles, and whose position affect the path of the marbles.
My goal is to create a marble machine that is closer to the electronic implementations fo logic circuits: where the marbles falling represent current, and o he presence of current indicates the HIGH logic level, and the lack of current represents the LOW logic level.
I'd also like to make the logic gates be interchangeable pieces so that any circuit can be constructed (given enough space).
With these considerations in mind the most obvious approach is to arrange a lattice of logic gates in a diamond pattern. Connections from gates above representing inputs, and connections with gates below representing outputs. The "current" flows from the top to the bottom.
Given this description, what does this say about the logic gates we can choose? Well, each gate will be 2-input and 2-output, and furthermore we'll restrict ourselves so that we can drop a ball if needed, but we cannot generate one: The Hamming weight of the output must be equal to or less than that of the output.
Formally:
The function of the logic gate can be defined as a function mapping 2 binary inputs to 2 binary outputs
And the Hamming weight, or L1 norm, of the input must be less than the output
So what gates are included in this set? Let's start by counting them:
In the general case, the number of n input gate with n outputs such that the Hamming weight of the output is less than that of the input is:
This result can be found by noticing that each possible input Hamming weight, k, represents nCk possible inputs, and each input can only have output Hamming weights i<=k, which in turn represent kCi possibile outputs.
For the case n=2, we have 36 possible gates.
So, what are these 36 gates? We could simply iterate over all possible truth tables and output those that match our condition, but we can do better: let's instead synthesize and describe these allowed gates in terms of logic gates we're more familiar with. Let's describe them in terms of pairs of our classic 2-input 1-output logic gates.
We can describe the truth table of a given gate by appending the outputs column into a binary string. Therefore all possible 2-input 1-output gates can be described in terms of a 4-bit binary string.
Here we have a table of all possible 2-input 1-output gates, where the rows show the values of the first 2 bits, and the columns show the last 2 bits:
| 00 | 01 | 10 | 11 | |
|---|---|---|---|---|
| 00 | 0 | ∧ | ∧A̅ | B |
| 01 | ∧B̅ | A | ≢ | ∨ |
| 10 | ⊽ | ≡ | A̅ | ∨A̅ |
| 11 | B̅ | ∨B̅ | ⊼ | 1 |
Notice that in order to match out Hamming weight constraint the first bit of our truth table encoding must always be zero: therefore only the first 2 rows of the table contain gates we can use in our synthesis.
Now we can takes these gates and determine which pairs valid:
| A\B | 0 | ∧ | A | B | ∧A̅ | ∧B̅ | ∨ | ≢ |
|---|---|---|---|---|---|---|---|---|
| 0 | X | X | X | X | X | X | X | X |
| ∧ | X | X | X | X | X | X | X | X |
| A | X | X | X | X | ||||
| B | X | X | X | X | ||||
| ∧A̅ | X | X | X | X | ||||
| ∧B̅ | X | X | X | X | ||||
| ∨ | X | X | ||||||
| ≢ | X | X |
And here we count the total 36 gates we're looking for.
So now that we have our set of logic gates, how can we actually implement them? Well, I'll leave the physical implementation to future project, but for this project I'd like to simply simulate their action in code.
This project takes the form of a simple webpage using HTML5 canvas and JavaScript to implement the lattice of logic gates. The gates are labeled by ordered pairs of 2-input 1-output gates we're familiar with. The left gate of the pair represent the value given to the left-output of the gate, and the right follows suit.
The user also has the option to toggle between the animated 'falling marble' simulation, and the more instantaneous electric circuit simulation.
In the animated simulation the presence of a falling ball or lack thereof represent HIGH and LOW logic accordingly.
In the instantaneous simulation the red wired and blue wires represent HIGH and LOW logic accordingly.
| Operator | Mathematical Symbol | Name | Description | Wikipedia Link |
|---|---|---|---|---|
| 0 | 0 | The False gate | Always returns 0 | link |
| 1 | 1 | The Truth gate | Always returns 1 | link |
| L | A | The left identity operator | Returns the value of the left input | link |
| R | B | The right identity operator | Returns the value of right input | link |
| & | ∧ | The AND gate | Only returns 1 if both inputs are 1 | link |
| & | ∨ | The OR gate | Returns 1 if any input is 1 | link |
| ^ | ≢ | The XOR gate | Returns 1 if either input is 1 but not both | link |
- Note: The Truth gate is not a gate that respects the Hamming weight condition, but is useful for defining inputs in the logic lattice.