Dwarf Fortress Wiki - User contributions [en]

v0.31 Talk:Computing

2010-04-30T10:02:13Z

Jong: Created page with 'I don't see why the examples from the previous version were not included. Generally, designs for fluid and mechanical logic should still work in the current version as there hasn…'

I don't see why the examples from the previous version were not included. Generally, designs for fluid and mechanical logic should still work in the current version as there hasn't been any relevant changes in those areas.
[[User:Jong|Jong]] 10:02, 30 April 2010 (UTC)

v0.31:Computing

2010-04-30T09:54:41Z

Jong: Scooped up the examples from the 40d page

{{av}}
{{human}}
Computing in dwarf fortress is the practice of setting up complex constructions to perform logical operations and calculations, ideally to control some functionality of your fortress. Even if it isn't a young concept anymore, there is still lots of room for improvement and development. One reason is that there are many ways to solve one problem. Innovation and invention is encouraged.
=== Binary information ===
Binary information can have one of two possible states: true or false, respectively 1 or 0. In dwarf fortress they can be represented by different entities:
* on/off state or signal of a {{l|trigger|trigger}} (pressure plate, lever)
* power or connection state of a {{l|machine component|machine component}}
* open or closed state of a {{l|door|door}} or similar buildings
* {{l|pressure plate|low/high}} or {{l|flow|flowing/standing}} {{l|water|fluid}}
* present {{l|creature|creature}}s and {{l|dwarf|borgs}}

Electronic devices and computers base on this elementary form of information, and if you want to go into computing, you’ll have to familiarize yourself with it. [http://en.wikipedia.org/wiki/Propositional_calculus propositional calculus]
=== Input/Output ===
Input can be any device which can be linked to another device with mechanisms, such as {{l|lever|levers}} or {{l|pressure plate|pressure plates}}. Pressure plates can measure water, magma, or creature weight, and can be set to react to your own dwarves if measuring creature weight. If measuring water or magma you specify the minimum and maximum levels at which it should output 'on', and at all other levels it will output an 'off' signal. Regardless of the actual amount of water, magma, or creature weight on your pressure plate, the plate can only output an 'on' or 'off' signal (1 or 0) to whatever devices it is linked to. So everything you build will have a binary base.

====Input elements====
* manual: {{l|lever|lever}} -> binary on/off signal
* triggered: {{l|pressure plate|pressure plate}} -> binary on/off signal

According to input, output can be anything that is able to react to an on/off signal. This can be doors, bridges, floodgates allowing or stopping flow, gears controlling pumps and much more. In some special configurations - when {{l|mechanical logic|mechanical logic}} is involved - output may not be a on/off signal but power, thus running or not running a machine component.

Currently to convert from power to an on/off signal, the only way is to use a screw pump connected to that power source with an unlimited amount of water and drainage at the output, and a pressure plate to measure whether water is being pumped out by the pump.

====Output elements====
* signal: {{l|pressure plate|pressure plate}} -> binary on/off signal -> linkable Object(s)
* power: {{l|gear assembly|gear assembly}} -> binary power on/power off -> machine

=== Binary logic ===
Basic binary logic takes one or two input bits and creates an output based on them. The devices that perform these operations are commonly called '''logic gates'''. 
* NOT - takes one input and returns the opposite of the input 
{| class="wikitable" border=1
|-
! input A
! NOT
|-
| 0
| 1
|-
| 1
| 0
|} 
* AND - takes two inputs and returns true if both inputs are true
* OR - takes two inputs and returns true if at least one input is true
* XOR - takes two inputs and returns true if exactly one input is true
* NAND - takes two inputs and returns true if either input is false
* NOR - takes two inputs and returns true if both inputs are false
* NXOR - takes two inputs and returns true if both inputs are identical 
{| class="wikitable" border=1
|-
! input A
! input B
! AND
! OR
! XOR
! NAND
! NOR
! NXOR
|-
| 0
| 0
| 0
| 0
| 0
| 1
| 1
| 1
|-
| 0
| 1
| 0
| 1
| 1
| 1
| 0
| 0
|-
| 1
| 0
| 0
| 1
| 1
| 1
| 0
| 0
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 1
|} 
The most human-understandable logic system requires NOT, AND and OR gates, but having a design for either a NAND or a NOR gate is enough to build any of the other gates. Some gates are easier to create or need fewer components than others depending on what discipline your logic relies on. Designing each individual gate that you will need (or using designs that had each individual gate designed) rather than building a gate out of multiple NAND gates or the like will generally result in your dorfputer reacting faster and using less resources (power, water, kittens, construction materials, what-have-you).

=== Complex gates ===
* {{l|Latch|Latch}} - storing and reading a single binary value
* {{l|Repeater|Repeater}} - sending a repeating signal
* {{l|Counter|Counter}}/{{l|Adder|Adder}} - binary calculation

== Disciplines ==
Historically, prior to DF2010 there have been 3 main disciplines of dwarfputing, depending on what would drive the dwarfputer. Each of them had its assets and drawbacks. So far, DF2010 at 0.31.01 appears to be essentially the same as far as power transmission goes, barring some differences with pump vertical power transmission (they don't without the floor between being channeled, apparently). Science! will determine what, if anything, differs as far as water flow, falling, and animal pathfinding.

The three disciplines are:
=== Fluid logic ===
{{l|Infinite flow fluid logic|Infinite flow fluid logic}} is controlling the ''flow of fluid'' over different pressure plates. Fluid logic can be easily constructed and every known logic gate in dwarf fortress has already been built with it. On the other hand this discipline depends on a somehow unlimited source of the used fluid to deal with its {{l|evaporation|evaporation}} and {{L|Water#Water in Fortress Mode|destruction}}.
=== Mechanical logic ===
{{l|Mechanical logic|Mechanical logic}} uses systems of axles and {{l|gear assemblies|gear assemblies}} to build logical gates. Mechanical logic reacts very fast and can be easily constructed, except for the need for a fluid-pump-based power->signal converter in every gate. Since every gear can itself be linked to a trigger (or multiple triggers), and automatically connect to adjacent gears for transferring either power or load, mechanical logic gates are very flexible and don't require anywhere near the number of different devices that tend to be used in fluid logic gates (except, again, for the requirement for a fluid-pump-based power->signal converter in every gate, unless you intend to use it to control a pump). On the other hand this discipline uses a LOT of mechanical power, and due to the lack of a power->signal converter, also referred to as a "rotation sensor" (a device to convert from power to on/off link signals), you need to build one using fluid logic components if you want to connect multiple mechanical logic gates together or connect a mechanical logic gate to any output other than a pump. There is, however, now a fully functional fluid preserving rotation sensor design. So, in truth, current mechanical logic is more correctly termed mechanical-fluid hybrid logic, as you need some source of fluid to "prime" the rotation sensors your design will need. Along with new techniques to construct logic gates by "pre-toggling" a gear assembly (see {{l|Pre-Toggled Mechanical Logic|Pre-Toggled Mechanical Logic}}), any logical circuit can be built, given enough space in the game to do it.
=== Animal logic ===
{{l|Animal logic|Animal logic}} places animals in an enclosed room, with a door blocking the path to where they desire to go, and a pressure plate below a hatch, with obstacles which are controlled by triggers. The animal thinks it can walk through the door, and if it has a path to the door will walk up to it and stand on the hatch. When the hatch is opened by a trigger, it falls onto the pressure plate. As long as the hatch is open, or other obstacles block its path to the door it remains on the pressure plate and the output is 'on'. Once it sees a path to the door it will leave the pressure plate. Generally this is made possibly by the fact that animals try to go to their parent while they're children, or to the meeting area. There are also be designs which use captured hostiles.

There was a fourth, theoretical, discipline, Borg Logic, but there was never any reported success inventing any functioning and useful borg logic systems.

===Examples of things you could do with logic gates===
* Repeater: Repeatedly toggling hatches open and closed, or spikes up and down.
* Latch: Making resettable one-use pressure plates which are reset by a lever.
* NOT gate: Reversing the effect of a switch or creature-sensing pressure plate, generally linked to a latch device. You can, of course, mod the latch device to send the opposite signal instead of using a NOT gate.
* AND gate: Requiring more than one condition to be true for something to occur. For instance, you could have a group of AND gates, with a system on/off switch, and and other triggers, with each trigger linked to a different AND gate with the system on/off switch linked to the the second input on all the AND gates, so that when the system on/off switch is OFF the output will be OFF on all the AND gates.
* OR gate: You could link two 1-7 water sensors to an OR gate, and link that to a NOT gate, and link that to some floodgates or doors which act as emergency bulkheads, closing when water is detected in the area. Or, link the OR gate to bridges which raise instead (but you may crush things, and bridges are slower than doors).
* XOR gate: You could use pressure plates hooked to latches at different points in your fort to detect enemy intrusion, and set them up to seal off the area with both an interior and exterior bulkhead when the intrusion occurs, but hook your latches up with an XOR gate and hook the output to the interior bulkhead to unseal that one if your pressure plates have detected that the enemy has gotten past it.
* NOR gate: A NOR gate returns TRUE (ON) only if both inputs are FALSE. Instead of using the OR gate example with a NOT gate, you could use a NOR gate linked to two 1-7 water sensors, whose output goes to doors or floodgates. When the pressure plates are both waterless, the floodgates will be open. When one detects water, the floodgates close. (If you used 0-0 pressure plates with an OR, you would get an OFF signal if both plates detected water, or an ON signal otherwise (which is the same as 1-7 NAND 1-7))
* NAND gate: A NAND gate returns TRUE (ON) whenever both inputs are not both TRUE (e.g. ON NAND ON is OFF, but every other combination is ON). Instead of the OR NOT or NOR example, you could link two 0-0 water sensors to a NAND gate, and link the NAND gate's output to raising bridges. 0-0 NAND 0-0 is the same as 1-7 OR 1-7. If there is no water on both pressure plates, the NAND gate will output an OFF signal. If, however, either has water, it will output an ON signal.

* And here's a more complicated example, omitting the details of what gates to use: An automated swimming training room, where you pull a lever to close exit doors and open hatches to drop water into it, then pressure plates detect when there's enough water and close the hatches, and after a certain amount of time (using a very slow repeater, for instance), drains and exit doors open and the system resets until you pull the lever again. Or, the lever could be taken out entirely and the system could be made fully automatic (with dwarves set to train in the room, for instance) using the repeater.

== Examples ==
There are few examples of a really useful dwarfputer and some concepts which have the potential to become useful for others. But in most cases they are made just for fun. What doesn't mean to diminish their designers achievements, because these are in general the more complex ones. At the moment there are no known examples of animal or borg logic.
=== Useful ===
* Magma trap
** This is an example of a useful dwarfputer controlling a magma trap. It automatically floods an area with lava, cleans up and resets afterwards. The timing is perfectly adjusted to let the victims vanish only leaving their valuable metal behind. video: http://mkv25.net/dfma/movie-1808-perfectmagmatrap design: http://i576.photobucket.com/albums/ss208/kanddak/magmatrap.png

=== Concepts ===
* repeater
** mechanical logic http://mkv25.net/dfma/movie-1370-pump-basedautorepeater
* adding machine
** mechanical logic, 6-bit: http://mkv25.net/dfma/movie-1561-addingmachine
** fluid logic, 8-bit: http://mkv25.net/dfma/movie-1084-numberabbeydemonstration
=== Such a doddle ===
* decimal display for 4-bit binary input
** mechanical logic, decimal with overflow-bit: http://mkv25.net/dfma/movie-1745-dwarfputerv01
** probably fluid logic: http://mkv25.net/dfma/movie-1657-7segmentlcddisplay
** fluid logic, hexadecimal: http://mkv25.net/dfma/movie-1092-7-segmentdisplaydemonstration
* tic tac toe
** mechanical logic http://mkv25.net/dfma/movie-1813-tictactoev10simple

== Related user pages ==
*[[User:BaronW]] - The Almighty Dwarven Calculator
*[[User:Jong]] - The first fully programmable digital Dwarven Computer
*[[User:SL/Logic Gates]] - These use mechanisms for connecting gates and devices and so forth, but fluid for logic. They're built on top of a body of water, and require power (for a pump or two per gate).
*[[User:Kyace/Adder]] - A full adder built using fluid logic, with a video of a rough prototype. Trivial to combine 8 of these to make a fluid device capable of adding two 8 bit numbers together.
*[[User:Soundandfury#Logic_Gates]] - These have a water supply reservoir above and a drain below. The drained water can be pumped back to the supply reservoir.
*[[User:Bidok]] - Animal logic with all gates, memory, repeater and counter. All powered by kittens.
*[[User:LordOOTFD#Animal_Logic]] - Animal logic with fast complex gates, building upon Bidok's kitten powered systems.
*[[User:Hussell#Assorted_Devices]] - Fluid logic
*[[User:Gammon]] - Fluid logic. Very detailed CMOS gates.

{{buildings}}

User:Jong/Dwarven Computer

2010-04-30T09:38:19Z

Jong:

This page documents the design of my Dwarven Computer. A number of designs were modified for the final implementation.

Adapted from my GoogleDocs [http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en manuscript]

== Notes ==

Toggled gear assemblies are designed as though they are off in when untriggered. However they are constructed in the on position. This means that you need to build and link a lever to toggle it to the off state.

==Power sensor (output device)==

# %>^ #
~ ~ ~ ~# Power sensor side view

In order to do useful things, such as toggling gears assemblies, opening doors, etc., mechanical power signals need to be converted to a trigger signal. There are only 2 trigger signal generators in dwarf fortress. One is the lever, which cannot be linked to machine power. The other is a pressure plate, which can.

The basic operation of this component is simple. Power operates the pump, pushing water over the pressure plate, generating a signal. When the pump is not powered, the water drains, switching the pressure plate off after at least 100 steps.

The smooth operation of this unit depends on several factors:
1. Adequate supply of water in the input tile so that the pump can maintain 7/7 or 6/7 water levels on the pressure plate. Can be done by providing more water tiles adjacent to the input tile.
2. Fast drainage to minimize the time needed for the plate to switch off. Just make sure that the level below the pumps is not completely full.
3. Since the minimum recovery time of the pressure plate is 100 steps, it can take a good long time for a 0-bit to reach the end of a chain of output units.

==Design for a memory cell for use in registers/memory unit==

###
#H#
#^#PRoO
#%#
#%WIP
#~#
###

This design is based on plans found at User:SL/Logic_Gates on the wiki. For this design, the write-in signal is linked to gear W and hatch H, while the read-out signal is linked to gear R. Gear o is linked to the pressure plate ^ and represents the state of the cell. Big O represents to output signal and I represents the input signal. P represents a power source. The hatch prevents the water from draining thus preserving the data.

In order to act as a memory cell, this unit must do 3 things:
1. Output its state when told to read-out
2. Change state to match an input when told to write-in
3. Maintain its state when not told to do anything

Let's check this by examining the operation of this unit.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|R
!width="40"|W
!width="40"|I
!width="40"|State
!width="40"|O
|-
| 0
| 0
| Ignored
| Unchanged
| 0
|-
| 1
| 0
| Ignored
| 0
| 0
|-
| 1
| 0
| Ignored
| 1
| 1
|-
| 0
| 1
| 1
| 1
| 0
|-
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

When both read and write are turned on, the device will act as a power sensor for the input. This could be a problem if the input and output are linked.

One point of concern is that the unit may not contain sufficient water to trigger the plate because the amount of water in the square above the hatch may not be 7 when it closes.

The plate could be set to trigger at a lower threshold, which would slightly slow down response time, or a door could be used instead of a hatch and the unit extended by one tile to provide space for the drain. This would have the downside of destroying some water after every write operation.

Another method is to use another pump to drain the water from the holding tile. This pump will only activate when W is 1 and I is 0.

==Computer registers==

The dwarven computer prototype is going to have an 8-bit instruction length, a 3-bit operon and a 5-bit address space. Why? The best reason for this is that other designs of Very Simple Computers (VSC) on the Internet are also only 8-bit and I am basing the design of the prototype dwarven computer off several of them. Naturally a bigger computer is better in many ways but the current goal is to produce an operational one. Now its not clear to me why a VSC shouldn't be smaller, but I suppose it doesn't matter.

8-bit words need 8-bit registers. Fortunately this just means stacking 8 memory units up and making sure they receive the same read/write signals.

[[image:memreg.png|Schematic of an 8-bit register]]

The lines in the diagram don't actually represent physical connections but imaginary ones. After all, the write signal must be sent remotely.

Now we consider the most compact designs for such an array. Let us assume that the output signals will be sent remotely. For clarity, the arrays ought to be rectangular.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~R
P`````````````````````````````````````````````P
Note that the O is omitted since it was a placeholder for the output device.

Not all registers in the computer are 8 bit registers. For example the memory address register is 5 bits.

==Memory unit==

Since there are only 5 bits of address space, I only need 256 memory cells. It should be fine if I don't use complicated column and row addressing schemes. I shall simply have 32 8-bit registers sticking somewhere. In order for the memory unit to work, I need a decoder to change the 5-bit address into 32 outputs. This will enable the memory unit to read and write from any register. I guess this makes it random access memory.

===Decoder===

This type of decoder is called an n to 2^n decoder, since it converts n inputs into 2^n outputs, in this case 5 to 32(2^5).

To illustrate the design for this unit, let us consider a simpler example where n=2. There will be 2 binary inputs which will be converted into 4 unique outputs, 1 for each memory address.

Here is the truth table for the operation:

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|2^0 (1)
!width="40"|2^1 (2)
!width="40"|O0
!width="40"|O1
!width="40"|O2
!width="40"|O3
|-
| 0
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
| 0
| 0
|-
| 0
| 1
| 0
| 0
| 1
| 0
|-
| 1
| 1
| 0
| 0
| 0
| 1
|} 

Now let us examine the implementation into the dwarfputer. Remember that gear assemblies are toggleable. I can implement a NOT operation by simply reversing the default state of a triggered gear (which is OFF in this system).

Let us represent the 2^0 gear as A when it is default OFF and as a when it is default ON, and represent the 2^1 gear as B and b. O0 to O3 represent output devices.

P P P P
a A a A
b b B B
O0 O1 O2 O3

This is the easiest to understand implementation. Looking at O0, we see that O0 is powered only when a and b are active. This corresponds to the state when 2^0 and 2^1 are both 0. Examining all the devices reveals that this arrangement obeys the truth table detailed above. Further examination would reveal that this arrangement also follows a pattern. Basically, the full set of columns represent every single possible combination of a, A, b, and B. Therefore we can easily see how to expand this system to n=5.

However, this implementation is not the most efficient one. I can also arrange the gears like so:

O3A AO1
BPb
O2a aO0

This arrangement uses 7 gears while the first arrangement uses 12 gears (including power gears). I put B and b closest to the power supply to obtain an orderly arrangement of O0 to O3 although this isn't strictly necessary.

Schematically this arrangement looks like this:

[[Image:2nscheme.png|Schematic of a 2 to 4 decoder]]

Which is just some sort of tree diagram. I can easily expand this to n=5 which is what I want.

[[Image:5nscheme.png|Schematic of a 5 to 32 decoder]]

I drew this diagram in rectangular form so that I can better see how to construct the decoder. The outputs of the decoder will be in a 4x8 grid. Since the output units are longer in one direction than the other, I will align their long axis along the short axis of the diagram. It is probably best to place all the mechanisms for the decoder in the level above the outputs.

===Memory unit registers===

The registers in the memory unit need some modification to work correctly. Only the register indicated in the memory address register ought to respond to read write signals. Therefore each of the 32 registers needs to be connected to one of the outputs from the decoder.

In this example, the register only responds when 00000 is in the memory address register.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~R
CP```P`````P`````P`````P`````P`````P`````P```PC

C in this diagram represents the output O0. I believe this is called the chip select signal in real computers.

It may be possible to wire the decoder directly to the power supply of the memory, which would remove the need for an output device.

===Memory unit architecture===

Right, I based the design of the memory unit off a java applet simulator I found on the Internet.

[[Image:Memarchi.png|Schematic of the memory unit's architecture]]

What this diagram is supposed to illustrate is that ALL the memory cells are linked to respond to the same read-out signal and the same write-in signal. Similarly, all the corresponding cells respond to same input, and all output to the same place. However, they will do none of these things unless they get a signal from the decoder, and only one register will get the signal as indicated in the memory address register.

Now the input and output buffers shown here may not be in the final blueprints, depending on the design of the rest of the computer.

==Machine language design==

The machine language is the set of instructions the computer will be able to execute. What these instructions are will define the design of the remaining components. For example, the Arithmetic Logic Unit needs to be able to perform the various operations listed in these instructions.

Ideally this language should be complete, that is, any function can be simulated as a combination of these instructions. I also want to be as simple as possible, to minimize the complexity of the ALU. It is worth restating that I am basing the overall design for the computer on a design for a VSC off the Internet.

Since the opcode for this computer is 3-bits long, there can only be 8 instructions.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!Opcode
!Function
!Operand
|-
| 000
| Load Accumulator from memory (indirectly)
| Memory Address
|-
| 001
| Store Accumulator to memory
| Memory Address
|-
| 010
| Add
| Memory Address
|-
| 011
| Subtract
| Memory Address
|-
| 100
| Jump to address if accumulator is not negative
| Memory Address
|-
| 101
| Binary shift left (*2) (input 0 as LSB)
| Memory Address
|-
| 110
| Binary shift right (/2) (retain MSB)
| Memory Address
|-
| 111
| Halt
| None
|} 

==Arithmetic Logic Unit (ALU)==

Now I know that the ALU needs to be able to perform 4 functions: Add, subtract, shift left and shift right. The unit needs to do one of these functions based on one of 4 input signals it may receive.

The ALU will receive 2 8-bit inputs and produce 1 8-bit output. It will require 3 systems, the adder-subtractor, bitshift left and bitshift right. These systems would be integrated to form the ALU.

===Half adder===

While there are existing dwarven adder designs out there, they do not come with schematics detailing the links between their components. Therefore I feel the need to design from scratch.

A simple half adder would take 2 inputs, and produce an output and an overflow output called a carry.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!width="40"|C
!width="40"|O
|-
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 1
|-
| 1
| 1
| 1
| 0
|} 

Carry out circuit C==ABP

aBP
Output circuit O==o
bAP

C===A
Combined circuit aBP
O==obA

This schematic shows a dwarven half adder that obeys the above truth table. In this diagram, the o represents a normal gear assembly and = represents axles. This design rests on the assumption that axles do not receive power except from their end tiles. It also takes advantage of the assumption that a matched pair of gears will not transmit information across their connection (here it is the B and b gear)

I believe this design uses the minimum number of gear assemblies, although I am not sure.

===Full adder===

In order for an adder to work properly, it must also receive the carry bit in addition to the 2 inputs. Ultimately, even the first adder in the final adder-subtracter must be able to receive a carry bit to operate successfully, which is why I didn't draw up a full plan for the half adder.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!C (carry in)
!O2 (carry out)
!width="40"|O1
|-
| 0
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 0
| 1
|-
| 1
| 1
| 0
| 1
| 0
|-
| 0
| 0
| 1
| 0
| 1
|-
| 1
| 0
| 1
| 1
| 0
|-
| 0
| 1
| 1
| 1
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

PB
CAo==O2 Carry Out Circuit
oBo

o=o=o=o==O1 Output Circuit
C c c C
B b B b
A A a a
P P P P

O1 O2 Combined Circuit
oo=oo |
Cc cC oo
Bb BbBAB
PAo oaPCo

Now that looks pretty monstrous. Undoubtedly the arrangement of gears could be changed here and there depending on the exact dimensions you need the array to be, but hopefully this diagram illustrates methods that can be used to minimize the complexity of the device. Note that where there are adjacent identical gears directly connected to the power source, one of them can be replaced by an ordinary gear, which will remove a linking task for that gear.

````` oCBAP
```` ocbo
##### ``|``
#.#.#` ``ocBo
#^#^#` `ooCba Hypothetical implementation
#%#%#` `o``BP
`%`%`` ```oAC
`~`~`` ```oBo
````` `````
lvlz lvlz+1

The above diagram details a hypothetical implementation for a full adder. The ```s represent the shadow of the mechanisms above and below the level. The left power sensor produces the output signal while the right power sensor produces the carry signal to be relayed to the next adder. The total footprint of the unit is 6x9. In an array, the units can overlap one tile so the total footprint of an 8-bit adder would be 41x9. Maximum operational power draw is 131x8(1048) units of power.

===8-bit ripple-carry adder-subtracter===

[[Image:Rippleaddersubtracter.png|Schematic of an 8-bit ripple-carry adder-subtractor]]

In order to build a full 8-bit adder-subtracter, all you need to do is to stack up 8 full adders next to each other and ensure that all the gears have been linked to the appropriate plates.

Now to get the adder-subtracter to subtract, all you have to do is to link up every single A and a (or B and b) gear assembly to the pressure plate sending the subtract signal. When the signal is sent, all the gears linked to a register will toggle. This will have the effect of inverting whatever input the register is sending. Finally the signal also needs to activate the carry in gears in the first adder, which will have the effect of adding 1 to the resulting sum (difference), giving the correct answer in two's complement representation.

===Carry-look-ahead adder===

I did some research into carry-look-ahead adders to see if it was worth implementing. Carry-look-ahead adders are faster than ripple-carry adders as ripple carry adders have to wait for the carry bit to 'ripple' through the chain of adders before getting the correct result. This is most significant for users of fluid logic, as fluid logic adders need to wait n*100 steps (n being the number of bits) for the carry to ripple all the way to the end. (Floodgates and bridges have a 100 step delay before activating or deactivating)

I found that I could easily design a carry-look-ahead adder using mechanical logic that calculates the carry in bit for all bits in a single step. I would also like to point out that real carry-look-ahead adders are more complicated because they don't have teleporting switch signals.

Firstly, looking at the carry-out circuit for the full adder, I see that not only can it exist independently from the sum circuit, the C gear is directly attached to the power source. I can take advantage of this by separating the carry bit calculation circuits from the adder and attaching them to each other like so.

[[Image:Carrycircuit.png|Schematic of a carry calculation circuit for a carry-look-ahead adder]]

Then for the summing part of the adder, I simply build only the output circuit, which I can now simplify like this

O1 Output Circuit
oo=oo
Cc cC
Bb Bb
oAPao

Or I can make it long instead of square so that it will tile better with the output buffers.

O1
|
oBCoCbo
AbcocBa
P P

I could construct these directly above the output buffers and they would all tile a lot better. Not only that, it fits almost perfectly within the footprint of a bank of output buffers. There is also no cost of increased complexity, only spatial separation between the summation unit and the carry unit, plus providing all the advantages of the carry-look-ahead system.

Since this system is superior in all ways to the ripple-carry system, this will be the one going into the final dwarven computer.

===Bitshifting operations===

Setting up a bitshifting operation is relatively simple. I simply wire the inputs directly into slightly different outputs as illustrated in the following diagrams (source: Wikipedia http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift).

[[Image:175px-Rotate right arithmetically.svg.png|Bitshift Right]]

[[Image:Rotate left logically.svg.png|Bitshift Left]]

Ideally all these operations would be linked into the same bank of output buffers in the assembled ALU, which will be the subject of the next section.

===ALU architecture===

[[Image:Aluarchi.png|Schematic of the ALU architecture]]

This diagram illustrates the various signals moving around the ALU. I decided that I ought to dragoon the ALU into incrementing the program counter as well, but I'm not sure whether that will work or not. We'll see in the later sections.

I defined the inputs from AR1 to be A since there are fewer A and a gears in the current designs and they all have to be toggled by the subtract signal. The operations listed on the right are signals generated by the control unit and they tell the ALU which operation to perform and transfer to the output buffer banks. The component critical to this function is the multiplexer.

The concept of the multiplexer is quite simple, suppose I had 2 inputs I and J, and I wanted to choose which one to pass based on signals Q and R, I would have to build something like this

PQIoJRP
|
O

Adding a multiplexer onto the output circuit would require an additional z-level if the tiling efficiency is to be maintained.

[[Image:ALUmulti.png|Schematic of a ALU multiplexer implementation]]

This diagram illustrates a hypothetical implementation of the multiplexer, as well as the bitshifting logic. I don't think I need a support axle on z+2 as it should be supported by O1.

==Bus design==

I've decided to ditch the plan for a bus, which would have been the conduit for data transfers between registers throughout the computer. Initially there were 2 methods, one had a output buffer attached to the end of the bus while the other the bus directly supplied power to the inputs of the appropriate registers.

Method 2 would not work on memory cells that used an active pump for bit-clearing. Method 1 would have worked but the output buffers had to be overwritten every step and that could cause cascading delays throughout the computer. Since this computer is relatively simple, I opted for hard wiring everything instead.

[[Image:Datatransfers.png|Schematic of the data transfers within the CPU]]

This diagram illustrates the data transfers that occur throughout the computer. The red arrows depict confirmed hard-wired connections, while the blue arrows would have been routed through a bus. I've decide AR1 is superfluous so I got rid of it. As you can see, each register has at most 2 inputs or 2 outputs going through the bus, so hardwiring is feasible.

==Timing circuit==

Before the computer can execute its instructions, it needs to perform some operations first.

#Transfer the contents of the accumulator to AR2. Dump instruction register and memory address register. 
#Transfer the program counter to the memory address register. Also, activate the program counter incrementation system in the ALU and transfer the results into program counter +1. 
#Load the data from memory at the specified address into the instruction register. 
#Transfer the data from program counter +1 to the program counter. Also, dump the memory address register 
#Load the last 5 digits of the instruction register into the memory address register. Also, dump program counter +1. 
#Execution (write accumulator, memory or program counter, read instruction register, memory, AR2) 

There needs to be a 100 step delay from the time a memory cell is written (or dumped, if it is pre-dumped) and when it is read, or it may cause cascading delays. The writing process is practically instantaneous, but 100 steps are needed before the correct result can be read if the memory was not cleared to begin with. Of course this point is entirely moot if the computer is running automatically, in which case every step will last at least 100 steps anyway and the prime consideration is to ensure that every step can be performed in 100 steps.

==Oscillator==

A typical mechanical oscillator is unsatisfactory because it will usually be sending out 2 on signals at once, one from the pressure plate the water is on and the other from the pressure plate waiting to reset.

0%%6%%0%%5%%0%%4
% %
% %
1%%0%%2%%0%%3%%0

This diagram shows a 12 step 6 signal oscillator. At the locations marked 0, there are no pressure plates. A lever operates the mechanism. When the lever is in the ON position, the #%%0 pumps activate, and when the lever is in the OFF position, the 0%%# pumps activate. The oscillator can also be fully automated by using the pressure plates themselves to replace the lever function. The oscillator's power supply also needs to be cut if a halt signal is received from the control unit.

===Oscillator link table===

#Read accumulator, write AR2, write IR, write MAR 
#Read PC, write MAR, activate ALU (adder select, C0=1), write PC+1 
#Read MEM, read MAR. activate decoder, write IR 
#Read PC+1, write PC, write MAR 
#Read IR, write MAR, write PC+1 
#Execution (read IR, turn on control unit) 

A dump operation can be performed by telling the memory register to write when its linked inputs are inactive, effectively writing 0s.

==Control unit==

The control unit can be implemented simply as a 3-8 decoder with appropriately linked pressure plates. The execute signal controlled gear assembly is located at the root of the decoder.

===Control unit link table===

:O0. Read memory, read MAR, activate decoder, write accumulator, select transfer 
:O1. Read accumulator, write memory, read MAR, activate decoder 
:O2. Read memory, read MAR, activate decoder, read AR2, Send Add signal to ALU (adder select), write accumulator 
:O3. Read memory, read MAR, activate decoder, read AR2, Send Subtract signal to ALU (adder select, C0=1, invert input A), write accumulator 
:O4. Read IR, write PC if ACC7=0 
:O5. Read memory, read MAR, activate decoder, Send Shift left signal to ALU (SHL select), write accumulator 
:O6. Read memory, read MAR, activate decoder, Send Shift right signal to ALU (SHR select), write accumulator 
:O7. Cut power to oscillator. 

==See also==

[[DF2010:Computing|Computing]]

==External links==
*[http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en GoogleDocs Design Manuscript]
*[http://www.bay12forums.com/smf/index.php?topic=49641.0 Bay12 Forums thread] - Includes discussion on modifications and testing results
*[http://mkv25.net/dfma/map-8269 Map at DF Map Archive]
*[http://dffd.wimbli.com/file.php?id=1929 Save File at DF File Depot]

v0.31:Computing

2010-04-30T09:36:27Z

Jong:

{{av}}
{{human}}
Computing in dwarf fortress is the practice of setting up complex constructions to perform logical operations and calculations, ideally to control some functionality of your fortress. Even if it isn't a young concept anymore, there is still lots of room for improvement and development. One reason is that there are many ways to solve one problem. Innovation and invention is encouraged.
=== Binary information ===
Binary information can have one of two possible states: true or false, respectively 1 or 0. In dwarf fortress they can be represented by different entities:
* on/off state or signal of a {{l|trigger|trigger}} (pressure plate, lever)
* power or connection state of a {{l|machine component|machine component}}
* open or closed state of a {{l|door|door}} or similar buildings
* {{l|pressure plate|low/high}} or {{l|flow|flowing/standing}} {{l|water|fluid}}
* present {{l|creature|creature}}s and {{l|dwarf|borgs}}

Electronic devices and computers base on this elementary form of information, and if you want to go into computing, you’ll have to familiarize yourself with it. [http://en.wikipedia.org/wiki/Propositional_calculus propositional calculus]
=== Input/Output ===
Input can be any device which can be linked to another device with mechanisms, such as {{l|lever|levers}} or {{l|pressure plate|pressure plates}}. Pressure plates can measure water, magma, or creature weight, and can be set to react to your own dwarves if measuring creature weight. If measuring water or magma you specify the minimum and maximum levels at which it should output 'on', and at all other levels it will output an 'off' signal. Regardless of the actual amount of water, magma, or creature weight on your pressure plate, the plate can only output an 'on' or 'off' signal (1 or 0) to whatever devices it is linked to. So everything you build will have a binary base.

====Input elements====
* manual: {{l|lever|lever}} -> binary on/off signal
* triggered: {{l|pressure plate|pressure plate}} -> binary on/off signal

According to input, output can be anything that is able to react to an on/off signal. This can be doors, bridges, floodgates allowing or stopping flow, gears controlling pumps and much more. In some special configurations - when {{l|mechanical logic|mechanical logic}} is involved - output may not be a on/off signal but power, thus running or not running a machine component.

Currently to convert from power to an on/off signal, the only way is to use a screw pump connected to that power source with an unlimited amount of water and drainage at the output, and a pressure plate to measure whether water is being pumped out by the pump.

====Output elements====
* signal: {{l|pressure plate|pressure plate}} -> binary on/off signal -> linkable Object(s)
* power: {{l|gear assembly|gear assembly}} -> binary power on/power off -> machine

=== Binary logic ===
Basic binary logic takes one or two input bits and creates an output based on them. The devices that perform these operations are commonly called '''logic gates'''. 
* NOT - takes one input and returns the opposite of the input 
{| class="wikitable" border=1
|-
! input A
! NOT
|-
| 0
| 1
|-
| 1
| 0
|} 
* AND - takes two inputs and returns true if both inputs are true
* OR - takes two inputs and returns true if at least one input is true
* XOR - takes two inputs and returns true if exactly one input is true
* NAND - takes two inputs and returns true if either input is false
* NOR - takes two inputs and returns true if both inputs are false
* NXOR - takes two inputs and returns true if both inputs are identical 
{| class="wikitable" border=1
|-
! input A
! input B
! AND
! OR
! XOR
! NAND
! NOR
! NXOR
|-
| 0
| 0
| 0
| 0
| 0
| 1
| 1
| 1
|-
| 0
| 1
| 0
| 1
| 1
| 1
| 0
| 0
|-
| 1
| 0
| 0
| 1
| 1
| 1
| 0
| 0
|-
| 1
| 1
| 1
| 1
| 0
| 0
| 0
| 1
|} 
The most human-understandable logic system requires NOT, AND and OR gates, but having a design for either a NAND or a NOR gate is enough to build any of the other gates. Some gates are easier to create or need fewer components than others depending on what discipline your logic relies on. Designing each individual gate that you will need (or using designs that had each individual gate designed) rather than building a gate out of multiple NAND gates or the like will generally result in your dorfputer reacting faster and using less resources (power, water, kittens, construction materials, what-have-you).

=== Complex gates ===
* {{l|Latch|Latch}} - storing and reading a single binary value
* {{l|Repeater|Repeater}} - sending a repeating signal
* {{l|Counter|Counter}}/{{l|Adder|Adder}} - binary calculation

== Disciplines ==
Historically, prior to DF2010 there have been 3 main disciplines of dwarfputing, depending on what would drive the dwarfputer. Each of them had its assets and drawbacks. So far, DF2010 at 0.31.01 appears to be essentially the same as far as power transmission goes, barring some differences with pump vertical power transmission (they don't without the floor between being channeled, apparently). Science! will determine what, if anything, differs as far as water flow, falling, and animal pathfinding.

The three disciplines are:
=== Fluid logic ===
{{l|Infinite flow fluid logic|Infinite flow fluid logic}} is controlling the ''flow of fluid'' over different pressure plates. Fluid logic can be easily constructed and every known logic gate in dwarf fortress has already been built with it. On the other hand this discipline depends on a somehow unlimited source of the used fluid to deal with its {{l|evaporation|evaporation}} and {{L|Water#Water in Fortress Mode|destruction}}.
=== Mechanical logic ===
{{l|Mechanical logic|Mechanical logic}} uses systems of axles and {{l|gear assemblies|gear assemblies}} to build logical gates. Mechanical logic reacts very fast and can be easily constructed, except for the need for a fluid-pump-based power->signal converter in every gate. Since every gear can itself be linked to a trigger (or multiple triggers), and automatically connect to adjacent gears for transferring either power or load, mechanical logic gates are very flexible and don't require anywhere near the number of different devices that tend to be used in fluid logic gates (except, again, for the requirement for a fluid-pump-based power->signal converter in every gate, unless you intend to use it to control a pump). On the other hand this discipline uses a LOT of mechanical power, and due to the lack of a power->signal converter, also referred to as a "rotation sensor" (a device to convert from power to on/off link signals), you need to build one using fluid logic components if you want to connect multiple mechanical logic gates together or connect a mechanical logic gate to any output other than a pump. There is, however, now a fully functional fluid preserving rotation sensor design. So, in truth, current mechanical logic is more correctly termed mechanical-fluid hybrid logic, as you need some source of fluid to "prime" the rotation sensors your design will need. Along with new techniques to construct logic gates by "pre-toggling" a gear assembly (see {{l|Pre-Toggled Mechanical Logic|Pre-Toggled Mechanical Logic}}), any logical circuit can be built, given enough space in the game to do it.
=== Animal logic ===
{{l|Animal logic|Animal logic}} places animals in an enclosed room, with a door blocking the path to where they desire to go, and a pressure plate below a hatch, with obstacles which are controlled by triggers. The animal thinks it can walk through the door, and if it has a path to the door will walk up to it and stand on the hatch. When the hatch is opened by a trigger, it falls onto the pressure plate. As long as the hatch is open, or other obstacles block its path to the door it remains on the pressure plate and the output is 'on'. Once it sees a path to the door it will leave the pressure plate. Generally this is made possibly by the fact that animals try to go to their parent while they're children, or to the meeting area. There are also be designs which use captured hostiles.

There was a fourth, theoretical, discipline, Borg Logic, but there was never any reported success inventing any functioning and useful borg logic systems.

===Examples of things you could do with logic gates===
* Repeater: Repeatedly toggling hatches open and closed, or spikes up and down.
* Latch: Making resettable one-use pressure plates which are reset by a lever.
* NOT gate: Reversing the effect of a switch or creature-sensing pressure plate, generally linked to a latch device. You can, of course, mod the latch device to send the opposite signal instead of using a NOT gate.
* AND gate: Requiring more than one condition to be true for something to occur. For instance, you could have a group of AND gates, with a system on/off switch, and and other triggers, with each trigger linked to a different AND gate with the system on/off switch linked to the the second input on all the AND gates, so that when the system on/off switch is OFF the output will be OFF on all the AND gates.
* OR gate: You could link two 1-7 water sensors to an OR gate, and link that to a NOT gate, and link that to some floodgates or doors which act as emergency bulkheads, closing when water is detected in the area. Or, link the OR gate to bridges which raise instead (but you may crush things, and bridges are slower than doors).
* XOR gate: You could use pressure plates hooked to latches at different points in your fort to detect enemy intrusion, and set them up to seal off the area with both an interior and exterior bulkhead when the intrusion occurs, but hook your latches up with an XOR gate and hook the output to the interior bulkhead to unseal that one if your pressure plates have detected that the enemy has gotten past it.
* NOR gate: A NOR gate returns TRUE (ON) only if both inputs are FALSE. Instead of using the OR gate example with a NOT gate, you could use a NOR gate linked to two 1-7 water sensors, whose output goes to doors or floodgates. When the pressure plates are both waterless, the floodgates will be open. When one detects water, the floodgates close. (If you used 0-0 pressure plates with an OR, you would get an OFF signal if both plates detected water, or an ON signal otherwise (which is the same as 1-7 NAND 1-7))
* NAND gate: A NAND gate returns TRUE (ON) whenever both inputs are not both TRUE (e.g. ON NAND ON is OFF, but every other combination is ON). Instead of the OR NOT or NOR example, you could link two 0-0 water sensors to a NAND gate, and link the NAND gate's output to raising bridges. 0-0 NAND 0-0 is the same as 1-7 OR 1-7. If there is no water on both pressure plates, the NAND gate will output an OFF signal. If, however, either has water, it will output an ON signal.

* And here's a more complicated example, omitting the details of what gates to use: An automated swimming training room, where you pull a lever to close exit doors and open hatches to drop water into it, then pressure plates detect when there's enough water and close the hatches, and after a certain amount of time (using a very slow repeater, for instance), drains and exit doors open and the system resets until you pull the lever again. Or, the lever could be taken out entirely and the system could be made fully automatic (with dwarves set to train in the room, for instance) using the repeater.

{{buildings}}

== Related user pages ==
*[[User:BaronW]] - The Almighty Dwarven Calculator
*[[User:Jong]] - The first fully programmable digital Dwarven Computer

User:Jong

2010-04-30T09:32:55Z

Jong:

==Dwarven Computer==
[[Image:DCOverview.png|thumb|Overview of the Dwarven Computer]]
{{Main|User:Jong/Dwarven_Computer}}

I successfully built first fully programmable digital computer in Dwarf Fortress! It has been tested and works as expected, although incredibly slow.

I did make a few changes from the documented design in the final implementation, but the basic design is sound and should only have a few bugs.

==Single-Stage carry-look-ahead adder==

In another [http://www.bay12forums.com/smf/index.php?topic=55380.0 thread] on the official forums, I came up with an improved design for a carry-look-ahead adder. [[Image:Single stage adder.png|thumb|Single Stage Adder]]

It directly attaches the output gears of the carry calculation circuit to the root of the sum circuit's gear tree, where the carry-in gears would have been. This allows the power availability, which is determined by the carry circuit, to substitute for a toggled gear and thus making the whole adder single stage.

I further optimized the design by replacing most of the simple single-input gears with double input gears that were mentioned in that thread as well. This greatly reduced the complexity of the adder.

==Binary Multiplier==

===Multiple Input Adder===

Given the efficiency of my new adder design, and multiple input design, I have been considering the problem of creating an efficient multiple input adder, which could be used as a component of a binary multiplier.

It turns out that the sum calculation circuit needs no modification at all, as it simply determines whether the total of the inputs and the carry is odd or even, producing a result when it is odd.

However the carry calculation could become very complex, as the quantity of the carry is variable depending on the total number of inputs. For example 1+1+1+1 gives 100, which is 2 units down the row.

File:Single stage adder.png

2010-04-30T09:19:49Z

Jong: Schematic of a single-stage carry-look ahead adder. The gears indicated by the lighter circles are disengaged by default while the gears indicated by th bold coloured circles are engaged by default. Gears labeled with multiple letters indicates that mul

Schematic of a single-stage carry-look ahead adder.

The gears indicated by the lighter circles are disengaged by default while the gears indicated by th bold coloured circles are engaged by default.

Gears labeled with multiple letters indicates that multiple inputs are linked to the gear.

File:DCOverview.png

2010-04-30T09:07:23Z

Jong: Overview of the Dwarven Computer

Overview of the Dwarven Computer

User:Jong/Dwarven Computer

2010-04-30T08:56:11Z

Jong:

This page documents the design of my Dwarven Computer. A number of designs were modified for the final implementation.

Adapted from my GoogleDocs [http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en manuscript]

== Notes ==

Toggled gear assemblies are designed as though they are off in when untriggered. However they are constructed in the on position. This means that you need to build and link a lever to toggle it to the off state.

==Power sensor (output device)==

# %>^ #
~ ~ ~ ~# Power sensor side view

In order to do useful things, such as toggling gears assemblies, opening doors, etc., mechanical power signals need to be converted to a trigger signal. There are only 2 trigger signal generators in dwarf fortress. One is the lever, which cannot be linked to machine power. The other is a pressure plate, which can.

The basic operation of this component is simple. Power operates the pump, pushing water over the pressure plate, generating a signal. When the pump is not powered, the water drains, switching the pressure plate off after at least 100 steps.

The smooth operation of this unit depends on several factors:
1. Adequate supply of water in the input tile so that the pump can maintain 7/7 or 6/7 water levels on the pressure plate. Can be done by providing more water tiles adjacent to the input tile.
2. Fast drainage to minimize the time needed for the plate to switch off. Just make sure that the level below the pumps is not completely full.
3. Since the minimum recovery time of the pressure plate is 100 steps, it can take a good long time for a 0-bit to reach the end of a chain of output units.

==Design for a memory cell for use in registers/memory unit==

###
#H#
#^#PRoO
#%#
#%WIP
#~#
###

This design is based on plans found at User:SL/Logic_Gates on the wiki. For this design, the write-in signal is linked to gear W and hatch H, while the read-out signal is linked to gear R. Gear o is linked to the pressure plate ^ and represents the state of the cell. Big O represents to output signal and I represents the input signal. P represents a power source. The hatch prevents the water from draining thus preserving the data.

In order to act as a memory cell, this unit must do 3 things:
1. Output its state when told to read-out
2. Change state to match an input when told to write-in
3. Maintain its state when not told to do anything

Let's check this by examining the operation of this unit.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|R
!width="40"|W
!width="40"|I
!width="40"|State
!width="40"|O
|-
| 0
| 0
| Ignored
| Unchanged
| 0
|-
| 1
| 0
| Ignored
| 0
| 0
|-
| 1
| 0
| Ignored
| 1
| 1
|-
| 0
| 1
| 1
| 1
| 0
|-
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

When both read and write are turned on, the device will act as a power sensor for the input. This could be a problem if the input and output are linked.

One point of concern is that the unit may not contain sufficient water to trigger the plate because the amount of water in the square above the hatch may not be 7 when it closes.

The plate could be set to trigger at a lower threshold, which would slightly slow down response time, or a door could be used instead of a hatch and the unit extended by one tile to provide space for the drain. This would have the downside of destroying some water after every write operation.

Another method is to use another pump to drain the water from the holding tile. This pump will only activate when W is 1 and I is 0.

==Computer registers==

The dwarven computer prototype is going to have an 8-bit instruction length, a 3-bit operon and a 5-bit address space. Why? The best reason for this is that other designs of Very Simple Computers (VSC) on the Internet are also only 8-bit and I am basing the design of the prototype dwarven computer off several of them. Naturally a bigger computer is better in many ways but the current goal is to produce an operational one. Now its not clear to me why a VSC shouldn't be smaller, but I suppose it doesn't matter.

8-bit words need 8-bit registers. Fortunately this just means stacking 8 memory units up and making sure they receive the same read/write signals.

[[image:memreg.png|Schematic of an 8-bit register]]

The lines in the diagram don't actually represent physical connections but imaginary ones. After all, the write signal must be sent remotely.

Now we consider the most compact designs for such an array. Let us assume that the output signals will be sent remotely. For clarity, the arrays ought to be rectangular.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~R
P`````````````````````````````````````````````P
Note that the O is omitted since it was a placeholder for the output device.

Not all registers in the computer are 8 bit registers. For example the memory address register is 5 bits.

==Memory unit==

Since there are only 5 bits of address space, I only need 256 memory cells. It should be fine if I don't use complicated column and row addressing schemes. I shall simply have 32 8-bit registers sticking somewhere. In order for the memory unit to work, I need a decoder to change the 5-bit address into 32 outputs. This will enable the memory unit to read and write from any register. I guess this makes it random access memory.

===Decoder===

This type of decoder is called an n to 2^n decoder, since it converts n inputs into 2^n outputs, in this case 5 to 32(2^5).

To illustrate the design for this unit, let us consider a simpler example where n=2. There will be 2 binary inputs which will be converted into 4 unique outputs, 1 for each memory address.

Here is the truth table for the operation:

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|2^0 (1)
!width="40"|2^1 (2)
!width="40"|O0
!width="40"|O1
!width="40"|O2
!width="40"|O3
|-
| 0
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
| 0
| 0
|-
| 0
| 1
| 0
| 0
| 1
| 0
|-
| 1
| 1
| 0
| 0
| 0
| 1
|} 

Now let us examine the implementation into the dwarfputer. Remember that gear assemblies are toggleable. I can implement a NOT operation by simply reversing the default state of a triggered gear (which is OFF in this system).

Let us represent the 2^0 gear as A when it is default OFF and as a when it is default ON, and represent the 2^1 gear as B and b. O0 to O3 represent output devices.

P P P P
a A a A
b b B B
O0 O1 O2 O3

This is the easiest to understand implementation. Looking at O0, we see that O0 is powered only when a and b are active. This corresponds to the state when 2^0 and 2^1 are both 0. Examining all the devices reveals that this arrangement obeys the truth table detailed above. Further examination would reveal that this arrangement also follows a pattern. Basically, the full set of columns represent every single possible combination of a, A, b, and B. Therefore we can easily see how to expand this system to n=5.

However, this implementation is not the most efficient one. I can also arrange the gears like so:

O3A AO1
BPb
O2a aO0

This arrangement uses 7 gears while the first arrangement uses 12 gears (including power gears). I put B and b closest to the power supply to obtain an orderly arrangement of O0 to O3 although this isn't strictly necessary.

Schematically this arrangement looks like this:

[[Image:2nscheme.png|Schematic of a 2 to 4 decoder]]

Which is just some sort of tree diagram. I can easily expand this to n=5 which is what I want.

[[Image:5nscheme.png|Schematic of a 5 to 32 decoder]]

I drew this diagram in rectangular form so that I can better see how to construct the decoder. The outputs of the decoder will be in a 4x8 grid. Since the output units are longer in one direction than the other, I will align their long axis along the short axis of the diagram. It is probably best to place all the mechanisms for the decoder in the level above the outputs.

===Memory unit registers===

The registers in the memory unit need some modification to work correctly. Only the register indicated in the memory address register ought to respond to read write signals. Therefore each of the 32 registers needs to be connected to one of the outputs from the decoder.

In this example, the register only responds when 00000 is in the memory address register.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~R
CP```P`````P`````P`````P`````P`````P`````P```PC

C in this diagram represents the output O0. I believe this is called the chip select signal in real computers.

It may be possible to wire the decoder directly to the power supply of the memory, which would remove the need for an output device.

===Memory unit architecture===

Right, I based the design of the memory unit off a java applet simulator I found on the Internet.

[[Image:Memarchi.png|Schematic of the memory unit's architecture]]

What this diagram is supposed to illustrate is that ALL the memory cells are linked to respond to the same read-out signal and the same write-in signal. Similarly, all the corresponding cells respond to same input, and all output to the same place. However, they will do none of these things unless they get a signal from the decoder, and only one register will get the signal as indicated in the memory address register.

Now the input and output buffers shown here may not be in the final blueprints, depending on the design of the rest of the computer.

==Machine language design==

The machine language is the set of instructions the computer will be able to execute. What these instructions are will define the design of the remaining components. For example, the Arithmetic Logic Unit needs to be able to perform the various operations listed in these instructions.

Ideally this language should be complete, that is, any function can be simulated as a combination of these instructions. I also want to be as simple as possible, to minimize the complexity of the ALU. It is worth restating that I am basing the overall design for the computer on a design for a VSC off the Internet.

Since the opcode for this computer is 3-bits long, there can only be 8 instructions.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!Opcode
!Function
!Operand
|-
| 000
| Load Accumulator from memory (indirectly)
| Memory Address
|-
| 001
| Store Accumulator to memory
| Memory Address
|-
| 010
| Add
| Memory Address
|-
| 011
| Subtract
| Memory Address
|-
| 100
| Jump to address if accumulator is not negative
| Memory Address
|-
| 101
| Binary shift left (*2) (input 0 as LSB)
| Memory Address
|-
| 110
| Binary shift right (/2) (retain MSB)
| Memory Address
|-
| 111
| Halt
| None
|} 

==Arithmetic Logic Unit (ALU)==

Now I know that the ALU needs to be able to perform 4 functions: Add, subtract, shift left and shift right. The unit needs to do one of these functions based on one of 4 input signals it may receive.

The ALU will receive 2 8-bit inputs and produce 1 8-bit output. It will require 3 systems, the adder-subtractor, bitshift left and bitshift right. These systems would be integrated to form the ALU.

===Half adder===

While there are existing dwarven adder designs out there, they do not come with schematics detailing the links between their components. Therefore I feel the need to design from scratch.

A simple half adder would take 2 inputs, and produce an output and an overflow output called a carry.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!width="40"|C
!width="40"|O
|-
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 1
|-
| 1
| 1
| 1
| 0
|} 

Carry out circuit C==ABP

aBP
Output circuit O==o
bAP

C===A
Combined circuit aBP
O==obA

This schematic shows a dwarven half adder that obeys the above truth table. In this diagram, the o represents a normal gear assembly and = represents axles. This design rests on the assumption that axles do not receive power except from their end tiles. It also takes advantage of the assumption that a matched pair of gears will not transmit information across their connection (here it is the B and b gear)

I believe this design uses the minimum number of gear assemblies, although I am not sure.

===Full adder===

In order for an adder to work properly, it must also receive the carry bit in addition to the 2 inputs. Ultimately, even the first adder in the final adder-subtracter must be able to receive a carry bit to operate successfully, which is why I didn't draw up a full plan for the half adder.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!C (carry in)
!O2 (carry out)
!width="40"|O1
|-
| 0
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 0
| 1
|-
| 1
| 1
| 0
| 1
| 0
|-
| 0
| 0
| 1
| 0
| 1
|-
| 1
| 0
| 1
| 1
| 0
|-
| 0
| 1
| 1
| 1
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

PB
CAo==O2 Carry Out Circuit
oBo

o=o=o=o==O1 Output Circuit
C c c C
B b B b
A A a a
P P P P

O1 O2 Combined Circuit
oo=oo |
Cc cC oo
Bb BbBAB
PAo oaPCo

Now that looks pretty monstrous. Undoubtedly the arrangement of gears could be changed here and there depending on the exact dimensions you need the array to be, but hopefully this diagram illustrates methods that can be used to minimize the complexity of the device. Note that where there are adjacent identical gears directly connected to the power source, one of them can be replaced by an ordinary gear, which will remove a linking task for that gear.

````` oCBAP
```` ocbo
##### ``|``
#.#.#` ``ocBo
#^#^#` `ooCba Hypothetical implementation
#%#%#` `o``BP
`%`%`` ```oAC
`~`~`` ```oBo
````` `````
lvlz lvlz+1

The above diagram details a hypothetical implementation for a full adder. The ```s represent the shadow of the mechanisms above and below the level. The left power sensor produces the output signal while the right power sensor produces the carry signal to be relayed to the next adder. The total footprint of the unit is 6x9. In an array, the units can overlap one tile so the total footprint of an 8-bit adder would be 41x9. Maximum operational power draw is 131x8(1048) units of power.

===8-bit ripple-carry adder-subtracter===

[[Image:Rippleaddersubtracter.png|Schematic of an 8-bit ripple-carry adder-subtractor]]

In order to build a full 8-bit adder-subtracter, all you need to do is to stack up 8 full adders next to each other and ensure that all the gears have been linked to the appropriate plates.

Now to get the adder-subtracter to subtract, all you have to do is to link up every single A and a (or B and b) gear assembly to the pressure plate sending the subtract signal. When the signal is sent, all the gears linked to a register will toggle. This will have the effect of inverting whatever input the register is sending. Finally the signal also needs to activate the carry in gears in the first adder, which will have the effect of adding 1 to the resulting sum (difference), giving the correct answer in two's complement representation.

===Carry-look-ahead adder===

I did some research into carry-look-ahead adders to see if it was worth implementing. Carry-look-ahead adders are faster than ripple-carry adders as ripple carry adders have to wait for the carry bit to 'ripple' through the chain of adders before getting the correct result. This is most significant for users of fluid logic, as fluid logic adders need to wait n*100 steps (n being the number of bits) for the carry to ripple all the way to the end. (Floodgates and bridges have a 100 step delay before activating or deactivating)

I found that I could easily design a carry-look-ahead adder using mechanical logic that calculates the carry in bit for all bits in a single step. I would also like to point out that real carry-look-ahead adders are more complicated because they don't have teleporting switch signals.

Firstly, looking at the carry-out circuit for the full adder, I see that not only can it exist independently from the sum circuit, the C gear is directly attached to the power source. I can take advantage of this by separating the carry bit calculation circuits from the adder and attaching them to each other like so.

[[Image:Carrycircuit.png|Schematic of a carry calculation circuit for a carry-look-ahead adder]]

Then for the summing part of the adder, I simply build only the output circuit, which I can now simplify like this

O1 Output Circuit
oo=oo
Cc cC
Bb Bb
oAPao

Or I can make it long instead of square so that it will tile better with the output buffers.

O1
|
oBCoCbo
AbcocBa
P P

I could construct these directly above the output buffers and they would all tile a lot better. Not only that, it fits almost perfectly within the footprint of a bank of output buffers. There is also no cost of increased complexity, only spatial separation between the summation unit and the carry unit, plus providing all the advantages of the carry-look-ahead system.

Since this system is superior in all ways to the ripple-carry system, this will be the one going into the final dwarven computer.

===Bitshifting operations===

Setting up a bitshifting operation is relatively simple. I simply wire the inputs directly into slightly different outputs as illustrated in the following diagrams (source: Wikipedia http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift).

[[Image:175px-Rotate right arithmetically.svg.png|Bitshift Right]]

[[Image:Rotate left logically.svg.png|Bitshift Left]]

Ideally all these operations would be linked into the same bank of output buffers in the assembled ALU, which will be the subject of the next section.

===ALU architecture===

[[Image:Aluarchi.png|Schematic of the ALU architecture]]

This diagram illustrates the various signals moving around the ALU. I decided that I ought to dragoon the ALU into incrementing the program counter as well, but I'm not sure whether that will work or not. We'll see in the later sections.

I defined the inputs from AR1 to be A since there are fewer A and a gears in the current designs and they all have to be toggled by the subtract signal. The operations listed on the right are signals generated by the control unit and they tell the ALU which operation to perform and transfer to the output buffer banks. The component critical to this function is the multiplexer.

The concept of the multiplexer is quite simple, suppose I had 2 inputs I and J, and I wanted to choose which one to pass based on signals Q and R, I would have to build something like this

PQIoJRP
|
O

Adding a multiplexer onto the output circuit would require an additional z-level if the tiling efficiency is to be maintained.

[[Image:ALUmulti.png|Schematic of a ALU multiplexer implementation]]

This diagram illustrates a hypothetical implementation of the multiplexer, as well as the bitshifting logic. I don't think I need a support axle on z+2 as it should be supported by O1.

==Bus design==

I've decided to ditch the plan for a bus, which would have been the conduit for data transfers between registers throughout the computer. Initially there were 2 methods, one had a output buffer attached to the end of the bus while the other the bus directly supplied power to the inputs of the appropriate registers.

Method 2 would not work on memory cells that used an active pump for bit-clearing. Method 1 would have worked but the output buffers had to be overwritten every step and that could cause cascading delays throughout the computer. Since this computer is relatively simple, I opted for hard wiring everything instead.

[[Image:Datatransfers.png|Schematic of the data transfers within the CPU]]

This diagram illustrates the data transfers that occur throughout the computer. The red arrows depict confirmed hard-wired connections, while the blue arrows would have been routed through a bus. I've decide AR1 is superfluous so I got rid of it. As you can see, each register has at most 2 inputs or 2 outputs going through the bus, so hardwiring is feasible.

==Timing circuit==

Before the computer can execute its instructions, it needs to perform some operations first.

#Transfer the contents of the accumulator to AR2. Dump instruction register and memory address register. 
#Transfer the program counter to the memory address register. Also, activate the program counter incrementation system in the ALU and transfer the results into program counter +1. 
#Load the data from memory at the specified address into the instruction register. 
#Transfer the data from program counter +1 to the program counter. Also, dump the memory address register 
#Load the last 5 digits of the instruction register into the memory address register. Also, dump program counter +1. 
#Execution (write accumulator, memory or program counter, read instruction register, memory, AR2) 

There needs to be a 100 step delay from the time a memory cell is written (or dumped, if it is pre-dumped) and when it is read, or it may cause cascading delays. The writing process is practically instantaneous, but 100 steps are needed before the correct result can be read if the memory was not cleared to begin with. Of course this point is entirely moot if the computer is running automatically, in which case every step will last at least 100 steps anyway and the prime consideration is to ensure that every step can be performed in 100 steps.

==Oscillator==

A typical mechanical oscillator is unsatisfactory because it will usually be sending out 2 on signals at once, one from the pressure plate the water is on and the other from the pressure plate waiting to reset.

0%%6%%0%%5%%0%%4
% %
% %
1%%0%%2%%0%%3%%0

This diagram shows a 12 step 6 signal oscillator. At the locations marked 0, there are no pressure plates. A lever operates the mechanism. When the lever is in the ON position, the #%%0 pumps activate, and when the lever is in the OFF position, the 0%%# pumps activate. The oscillator can also be fully automated by using the pressure plates themselves to replace the lever function. The oscillator's power supply also needs to be cut if a halt signal is received from the control unit.

===Oscillator link table===

#Read accumulator, write AR2, write IR, write MAR 
#Read PC, write MAR, activate ALU (adder select, C0=1), write PC+1 
#Read MEM, read MAR. activate decoder, write IR 
#Read PC+1, write PC, write MAR 
#Read IR, write MAR, write PC+1 
#Execution (read IR, turn on control unit) 

A dump operation can be performed by telling the memory register to write when its linked inputs are inactive, effectively writing 0s.

==Control unit==

The control unit can be implemented simply as a 3-8 decoder with appropriately linked pressure plates. The execute signal controlled gear assembly is located at the root of the decoder.

===Control unit link table===

:O0. Read memory, read MAR, activate decoder, write accumulator, select transfer 
:O1. Read accumulator, write memory, read MAR, activate decoder 
:O2. Read memory, read MAR, activate decoder, read AR2, Send Add signal to ALU (adder select), write accumulator 
:O3. Read memory, read MAR, activate decoder, read AR2, Send Subtract signal to ALU (adder select, C0=1, invert input A), write accumulator 
:O4. Read IR, write PC if ACC7=0 
:O5. Read memory, read MAR, activate decoder, Send Shift left signal to ALU (SHL select), write accumulator 
:O6. Read memory, read MAR, activate decoder, Send Shift right signal to ALU (SHR select), write accumulator 
:O7. Cut power to oscillator. 

==See also==

[[DF2010:Computing|Computing]]

==External links==
*[http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en GoogleDocs Design Manuscript]
*[http://www.bay12forums.com/smf/index.php?topic=49641.0 Bay12 Forums thread]
*[http://mkv25.net/dfma/map-8269 Map at DF Map Archive]
*[http://dffd.wimbli.com/file.php?id=1929 Save File at DF File Depot]

User:Jong/Dwarven Computer

2010-04-30T08:54:38Z

Jong:

This page documents the design of my Dwarven Computer. A number of designs were modified for the final implementation.

Adapted from my GoogleDocs [http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en manuscript]

== Notes ==

Toggled gear assemblies are designed as though they are off in when untriggered. However they are constructed in the on position. This means that you need to build and link a lever to toggle it to the off state.

==Power sensor (output device)==

# %>^ #
~ ~ ~ ~# Power sensor side view

In order to do useful things, such as toggling gears assemblies, opening doors, etc., mechanical power signals need to be converted to a trigger signal. There are only 2 trigger signal generators in dwarf fortress. One is the lever, which cannot be linked to machine power. The other is a pressure plate, which can.

The basic operation of this component is simple. Power operates the pump, pushing water over the pressure plate, generating a signal. When the pump is not powered, the water drains, switching the pressure plate off after at least 100 steps.

The smooth operation of this unit depends on several factors:
1. Adequate supply of water in the input tile so that the pump can maintain 7/7 or 6/7 water levels on the pressure plate. Can be done by providing more water tiles adjacent to the input tile.
2. Fast drainage to minimize the time needed for the plate to switch off. Just make sure that the level below the pumps is not completely full.
3. Since the minimum recovery time of the pressure plate is 100 steps, it can take a good long time for a 0-bit to reach the end of a chain of output units.

==Design for a memory cell for use in registers/memory unit==

###
#H#
#^#PRoO
#%#
#%WIP
#~#
###

This design is based on plans found at User:SL/Logic_Gates on the wiki. For this design, the write-in signal is linked to gear W and hatch H, while the read-out signal is linked to gear R. Gear o is linked to the pressure plate ^ and represents the state of the cell. Big O represents to output signal and I represents the input signal. P represents a power source. The hatch prevents the water from draining thus preserving the data.

In order to act as a memory cell, this unit must do 3 things:
1. Output its state when told to read-out
2. Change state to match an input when told to write-in
3. Maintain its state when not told to do anything

Let's check this by examining the operation of this unit.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|R
!width="40"|W
!width="40"|I
!width="40"|State
!width="40"|O
|-
| 0
| 0
| Ignored
| Unchanged
| 0
|-
| 1
| 0
| Ignored
| 0
| 0
|-
| 1
| 0
| Ignored
| 1
| 1
|-
| 0
| 1
| 1
| 1
| 0
|-
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

When both read and write are turned on, the device will act as a power sensor for the input. This could be a problem if the input and output are linked.

One point of concern is that the unit may not contain sufficient water to trigger the plate because the amount of water in the square above the hatch may not be 7 when it closes.

The plate could be set to trigger at a lower threshold, which would slightly slow down response time, or a door could be used instead of a hatch and the unit extended by one tile to provide space for the drain. This would have the downside of destroying some water after every write operation.

Another method is to use another pump to drain the water from the holding tile. This pump will only activate when W is 1 and I is 0.

==Computer registers==

The dwarven computer prototype is going to have an 8-bit instruction length, a 3-bit operon and a 5-bit address space. Why? The best reason for this is that other designs of Very Simple Computers (VSC) on the Internet are also only 8-bit and I am basing the design of the prototype dwarven computer off several of them. Naturally a bigger computer is better in many ways but the current goal is to produce an operational one. Now its not clear to me why a VSC shouldn't be smaller, but I suppose it doesn't matter.

8-bit words need 8-bit registers. Fortunately this just means stacking 8 memory units up and making sure they receive the same read/write signals.

[[image:memreg.png|Schematic of an 8-bit register]]

The lines in the diagram don't actually represent physical connections but imaginary ones. After all, the write signal must be sent remotely.

Now we consider the most compact designs for such an array. Let us assume that the output signals will be sent remotely. For clarity, the arrays ought to be rectangular.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~R
P`````````````````````````````````````````````P
Note that the O is omitted since it was a placeholder for the output device.

Not all registers in the computer are 8 bit registers. For example the memory address register is 5 bits.

==Memory unit==

Since there are only 5 bits of address space, I only need 256 memory cells. It should be fine if I don't use complicated column and row addressing schemes. I shall simply have 32 8-bit registers sticking somewhere. In order for the memory unit to work, I need a decoder to change the 5-bit address into 32 outputs. This will enable the memory unit to read and write from any register. I guess this makes it random access memory.

===Decoder===

This type of decoder is called an n to 2^n decoder, since it converts n inputs into 2^n outputs, in this case 5 to 32(2^5).

To illustrate the design for this unit, let us consider a simpler example where n=2. There will be 2 binary inputs which will be converted into 4 unique outputs, 1 for each memory address.

Here is the truth table for the operation:

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|2^0 (1)
!width="40"|2^1 (2)
!width="40"|O0
!width="40"|O1
!width="40"|O2
!width="40"|O3
|-
| 0
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
| 0
| 0
|-
| 0
| 1
| 0
| 0
| 1
| 0
|-
| 1
| 1
| 0
| 0
| 0
| 1
|} 

Now let us examine the implementation into the dwarfputer. Remember that gear assemblies are toggleable. I can implement a NOT operation by simply reversing the default state of a triggered gear (which is OFF in this system).

Let us represent the 2^0 gear as A when it is default OFF and as a when it is default ON, and represent the 2^1 gear as B and b. O0 to O3 represent output devices.

P P P P
a A a A
b b B B
O0 O1 O2 O3

This is the easiest to understand implementation. Looking at O0, we see that O0 is powered only when a and b are active. This corresponds to the state when 2^0 and 2^1 are both 0. Examining all the devices reveals that this arrangement obeys the truth table detailed above. Further examination would reveal that this arrangement also follows a pattern. Basically, the full set of columns represent every single possible combination of a, A, b, and B. Therefore we can easily see how to expand this system to n=5.

However, this implementation is not the most efficient one. I can also arrange the gears like so:

O3A AO1
BPb
O2a aO0

This arrangement uses 7 gears while the first arrangement uses 12 gears (including power gears). I put B and b closest to the power supply to obtain an orderly arrangement of O0 to O3 although this isn't strictly necessary.

Schematically this arrangement looks like this:

[[Image:2nscheme.png|Schematic of a 2 to 4 decoder]]

Which is just some sort of tree diagram. I can easily expand this to n=5 which is what I want.

[[Image:5nscheme.png|Schematic of a 5 to 32 decoder]]

I drew this diagram in rectangular form so that I can better see how to construct the decoder. The outputs of the decoder will be in a 4x8 grid. Since the output units are longer in one direction than the other, I will align their long axis along the short axis of the diagram. It is probably best to place all the mechanisms for the decoder in the level above the outputs.

===Memory unit registers===

The registers in the memory unit need some modification to work correctly. Only the register indicated in the memory address register ought to respond to read write signals. Therefore each of the 32 registers needs to be connected to one of the outputs from the decoder.

In this example, the register only responds when 00000 is in the memory address register.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~R
CP```P`````P`````P`````P`````P`````P`````P```PC

C in this diagram represents the output O0. I believe this is called the chip select signal in real computers.

It may be possible to wire the decoder directly to the power supply of the memory, which would remove the need for an output device.

===Memory unit architecture===

Right, I based the design of the memory unit off a java applet simulator I found on the Internet.

[[Image:Memarchi.png|Schematic of the memory unit's architecture]]

What this diagram is supposed to illustrate is that ALL the memory cells are linked to respond to the same read-out signal and the same write-in signal. Similarly, all the corresponding cells respond to same input, and all output to the same place. However, they will do none of these things unless they get a signal from the decoder, and only one register will get the signal as indicated in the memory address register.

Now the input and output buffers shown here may not be in the final blueprints, depending on the design of the rest of the computer.

==Machine language design==

The machine language is the set of instructions the computer will be able to execute. What these instructions are will define the design of the remaining components. For example, the Arithmetic Logic Unit needs to be able to perform the various operations listed in these instructions.

Ideally this language should be complete, that is, any function can be simulated as a combination of these instructions. I also want to be as simple as possible, to minimize the complexity of the ALU. It is worth restating that I am basing the overall design for the computer on a design for a VSC off the Internet.

Since the opcode for this computer is 3-bits long, there can only be 8 instructions.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!Opcode
!Function
!Operand
|-
| 000
| Load Accumulator from memory (indirectly)
| Memory Address
|-
| 001
| Store Accumulator to memory
| Memory Address
|-
| 010
| Add
| Memory Address
|-
| 011
| Subtract
| Memory Address
|-
| 100
| Jump to address if accumulator is not negative
| Memory Address
|-
| 101
| Binary shift left (*2) (input 0 as LSB)
| Memory Address
|-
| 110
| Binary shift right (/2) (retain MSB)
| Memory Address
|-
| 111
| Halt
| None
|} 

==Arithmetic Logic Unit (ALU)==

Now I know that the ALU needs to be able to perform 4 functions: Add, subtract, shift left and shift right. The unit needs to do one of these functions based on one of 4 input signals it may receive.

The ALU will receive 2 8-bit inputs and produce 1 8-bit output. It will require 3 systems, the adder-subtractor, bitshift left and bitshift right. These systems would be integrated to form the ALU.

===Half adder===

While there are existing dwarven adder designs out there, they do not come with schematics detailing the links between their components. Therefore I feel the need to design from scratch.

A simple half adder would take 2 inputs, and produce an output and an overflow output called a carry.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!width="40"|C
!width="40"|O
|-
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 1
|-
| 1
| 1
| 1
| 0
|} 

Carry out circuit C==ABP

aBP
Output circuit O==o
bAP

C===A
Combined circuit aBP
O==obA

This schematic shows a dwarven half adder that obeys the above truth table. In this diagram, the o represents a normal gear assembly and = represents axles. This design rests on the assumption that axles do not receive power except from their end tiles. It also takes advantage of the assumption that a matched pair of gears will not transmit information across their connection (here it is the B and b gear)

I believe this design uses the minimum number of gear assemblies, although I am not sure.

===Full adder===

In order for an adder to work properly, it must also receive the carry bit in addition to the 2 inputs. Ultimately, even the first adder in the final adder-subtracter must be able to receive a carry bit to operate successfully, which is why I didn't draw up a full plan for the half adder.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!C (carry in)
!O2 (carry out)
!width="40"|O1
|-
| 0
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 0
| 1
|-
| 1
| 1
| 0
| 1
| 0
|-
| 0
| 0
| 1
| 0
| 1
|-
| 1
| 0
| 1
| 1
| 0
|-
| 0
| 1
| 1
| 1
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

PB
CAo==O2 Carry Out Circuit
oBo

o=o=o=o==O1 Output Circuit
C c c C
B b B b
A A a a
P P P P

O1 O2 Combined Circuit
oo=oo |
Cc cC oo
Bb BbBAB
PAo oaPCo

Now that looks pretty monstrous. Undoubtedly the arrangement of gears could be changed here and there depending on the exact dimensions you need the array to be, but hopefully this diagram illustrates methods that can be used to minimize the complexity of the device. Note that where there are adjacent identical gears directly connected to the power source, one of them can be replaced by an ordinary gear, which will remove a linking task for that gear.

````` oCBAP
```` ocbo
##### ``|``
#.#.#` ``ocBo
#^#^#` `ooCba Hypothetical implementation
#%#%#` `o``BP
`%`%`` ```oAC
`~`~`` ```oBo
````` `````
lvlz lvlz+1

The above diagram details a hypothetical implementation for a full adder. The ```s represent the shadow of the mechanisms above and below the level. The left power sensor produces the output signal while the right power sensor produces the carry signal to be relayed to the next adder. The total footprint of the unit is 6x9. In an array, the units can overlap one tile so the total footprint of an 8-bit adder would be 41x9. Maximum operational power draw is 131x8(1048) units of power.

===8-bit ripple-carry adder-subtracter===

[[Image:Rippleaddersubtracter.png|Schematic of an 8-bit ripple-carry adder-subtractor]]

In order to build a full 8-bit adder-subtracter, all you need to do is to stack up 8 full adders next to each other and ensure that all the gears have been linked to the appropriate plates.

Now to get the adder-subtracter to subtract, all you have to do is to link up every single A and a (or B and b) gear assembly to the pressure plate sending the subtract signal. When the signal is sent, all the gears linked to a register will toggle. This will have the effect of inverting whatever input the register is sending. Finally the signal also needs to activate the carry in gears in the first adder, which will have the effect of adding 1 to the resulting sum (difference), giving the correct answer in two's complement representation.

===Carry-look-ahead adder===

I did some research into carry-look-ahead adders to see if it was worth implementing. Carry-look-ahead adders are faster than ripple-carry adders as ripple carry adders have to wait for the carry bit to 'ripple' through the chain of adders before getting the correct result. This is most significant for users of fluid logic, as fluid logic adders need to wait n*100 steps (n being the number of bits) for the carry to ripple all the way to the end. (Floodgates and bridges have a 100 step delay before activating or deactivating)

I found that I could easily design a carry-look-ahead adder using mechanical logic that calculates the carry in bit for all bits in a single step. I would also like to point out that real carry-look-ahead adders are more complicated because they don't have teleporting switch signals.

Firstly, looking at the carry-out circuit for the full adder, I see that not only can it exist independently from the sum circuit, the C gear is directly attached to the power source. I can take advantage of this by separating the carry bit calculation circuits from the adder and attaching them to each other like so.

[[Image:Carrycircuit.png|Schematic of a carry calculation circuit for a carry-look-ahead adder]]

Then for the summing part of the adder, I simply build only the output circuit, which I can now simplify like this

O1 Output Circuit
oo=oo
Cc cC
Bb Bb
oAPao

Or I can make it long instead of square so that it will tile better with the output buffers.

O1
|
oBCoCbo
AbcocBa
P P

I could construct these directly above the output buffers and they would all tile a lot better. Not only that, it fits almost perfectly within the footprint of a bank of output buffers. There is also no cost of increased complexity, only spatial separation between the summation unit and the carry unit, plus providing all the advantages of the carry-look-ahead system.

Since this system is superior in all ways to the ripple-carry system, this will be the one going into the final dwarven computer.

===Bitshifting operations===

Setting up a bitshifting operation is relatively simple. I simply wire the inputs directly into slightly different outputs as illustrated in the following diagrams (source: Wikipedia http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift).

[[Image:175px-Rotate right arithmetically.svg.png|Bitshift Right]]

[[Image:Rotate left logically.svg.png|Bitshift Left]]

Ideally all these operations would be linked into the same bank of output buffers in the assembled ALU, which will be the subject of the next section.

===ALU architecture===

[[Image:Aluarchi.png|Schematic of the ALU architecture]]

This diagram illustrates the various signals moving around the ALU. I decided that I ought to dragoon the ALU into incrementing the program counter as well, but I'm not sure whether that will work or not. We'll see in the later sections.

I defined the inputs from AR1 to be A since there are fewer A and a gears in the current designs and they all have to be toggled by the subtract signal. The operations listed on the right are signals generated by the control unit and they tell the ALU which operation to perform and transfer to the output buffer banks. The component critical to this function is the multiplexer.

The concept of the multiplexer is quite simple, suppose I had 2 inputs I and J, and I wanted to choose which one to pass based on signals Q and R, I would have to build something like this

PQIoJRP
|
O

Adding a multiplexer onto the output circuit would require an additional z-level if the tiling efficiency is to be maintained.

[[Image:ALUmulti.png|Schematic of a ALU multiplexer implementation]]

This diagram illustrates a hypothetical implementation of the multiplexer, as well as the bitshifting logic. I don't think I need a support axle on z+2 as it should be supported by O1.

==Bus design==

I've decided to ditch the plan for a bus, which would have been the conduit for data transfers between registers throughout the computer. Initially there were 2 methods, one had a output buffer attached to the end of the bus while the other the bus directly supplied power to the inputs of the appropriate registers.

Method 2 would not work on memory cells that used an active pump for bit-clearing. Method 1 would have worked but the output buffers had to be overwritten every step and that could cause cascading delays throughout the computer. Since this computer is relatively simple, I opted for hard wiring everything instead.

[[Image:Datatransfers.png|Schematic of the data transfers within the CPU]]

This diagram illustrates the data transfers that occur throughout the computer. The red arrows depict confirmed hard-wired connections, while the blue arrows would have been routed through a bus. I've decide AR1 is superfluous so I got rid of it. As you can see, each register has at most 2 inputs or 2 outputs going through the bus, so hardwiring is feasible.

==Timing circuit==

Before the computer can execute its instructions, it needs to perform some operations first.

#Transfer the contents of the accumulator to AR2. Dump instruction register and memory address register. 
#Transfer the program counter to the memory address register. Also, activate the program counter incrementation system in the ALU and transfer the results into program counter +1. 
#Load the data from memory at the specified address into the instruction register. 
#Transfer the data from program counter +1 to the program counter. Also, dump the memory address register 
#Load the last 5 digits of the instruction register into the memory address register. Also, dump program counter +1. 
#Execution (write accumulator, memory or program counter, read instruction register, memory, AR2) 

There needs to be a 100 step delay from the time a memory cell is written (or dumped, if it is pre-dumped) and when it is read, or it may cause cascading delays. The writing process is practically instantaneous, but 100 steps are needed before the correct result can be read if the memory was not cleared to begin with. Of course this point is entirely moot if the computer is running automatically, in which case every step will last at least 100 steps anyway and the prime consideration is to ensure that every step can be performed in 100 steps.

==Oscillator==

A typical mechanical oscillator is unsatisfactory because it will usually be sending out 2 on signals at once, one from the pressure plate the water is on and the other from the pressure plate waiting to reset.

0%%6%%0%%5%%0%%4
% %
% %
1%%0%%2%%0%%3%%0

This diagram shows a 12 step 6 signal oscillator. At the locations marked 0, there are no pressure plates. A lever operates the mechanism. When the lever is in the ON position, the #%%0 pumps activate, and when the lever is in the OFF position, the 0%%# pumps activate. The oscillator can also be fully automated by using the pressure plates themselves to replace the lever function. The oscillator's power supply also needs to be cut if a halt signal is received from the control unit.

===Oscillator link table===

#Read accumulator, write AR2, write IR, write MAR 
#Read PC, write MAR, activate ALU (adder select, C0=1), write PC+1 
#Read MEM, read MAR. activate decoder, write IR 
#Read PC+1, write PC, write MAR 
#Read IR, write MAR, write PC+1 
#Execution (read IR, turn on control unit) 

A dump operation can be performed by telling the memory register to write when its linked inputs are inactive, effectively writing 0s.

==Control unit==

The control unit can be implemented simply as a 3-8 decoder with appropriately linked pressure plates. The execute signal controlled gear assembly is located at the root of the decoder.

===Control unit link table===

:O0. Read memory, read MAR, activate decoder, write accumulator, select transfer 
:O1. Read accumulator, write memory, read MAR, activate decoder 
:O2. Read memory, read MAR, activate decoder, read AR2, Send Add signal to ALU (adder select), write accumulator 
:O3. Read memory, read MAR, activate decoder, read AR2, Send Subtract signal to ALU (adder select, C0=1, invert input A), write accumulator 
:O4. Read IR, write PC if ACC7=0 
:O5. Read memory, read MAR, activate decoder, Send Shift left signal to ALU (SHL select), write accumulator 
:O6. Read memory, read MAR, activate decoder, Send Shift right signal to ALU (SHR select), write accumulator 
:O7. Cut power to oscillator. 

==See also==

[[DF2010:Computing]]

==External links==
*[http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en GoogleDocs Design Manuscript]
*[http://www.bay12forums.com/smf/index.php?topic=49641.0 Bay12 Forums thread]
*[http://mkv25.net/dfma/map-8269 Map at DF Map Archive]
*[http://dffd.wimbli.com/file.php?id=1929 Save File at DF File Depot]

File:Datatransfers.png

2010-04-30T08:36:15Z

Jong: Schematic of the data transfers within the CPU

Schematic of the data transfers within the CPU

File:ALUmulti.png

2010-04-30T08:34:28Z

Jong: Schematic of a ALU multiplexer implementation

Schematic of a ALU multiplexer implementation

File:Aluarchi.png

2010-04-30T08:32:46Z

Jong: Schematic of the ALU architecture

Schematic of the ALU architecture

File:Rotate left logically.svg.png

2010-04-30T08:31:16Z

Jong: Bitshift Left (adapted from Wikipedia http://en.wikipedia.org/wiki/File:Rotate_left_logically.svg)

Bitshift Left (adapted from Wikipedia http://en.wikipedia.org/wiki/File:Rotate_left_logically.svg)

File:175px-Rotate right arithmetically.svg.png

2010-04-30T08:29:07Z

Jong: Bitshift right (adapted from Wikipedia http://en.wikipedia.org/wiki/File:Rotate_right_logically.svg)

Bitshift right (adapted from Wikipedia http://en.wikipedia.org/wiki/File:Rotate_right_logically.svg)

File:Carrycircuit.png

2010-04-30T08:26:27Z

Jong: Schematic of a carry calculation circuit for a carry-look-ahead adder

Schematic of a carry calculation circuit for a carry-look-ahead adder

File:Rippleaddersubtracter.png

2010-04-30T08:23:24Z

Jong: Schematic of an 8-bit ripple-carry adder-subtractor

Schematic of an 8-bit ripple-carry adder-subtractor

File:Memarchi.png

2010-04-30T08:19:52Z

Jong: Schematic of the memory unit's architecture

Schematic of the memory unit's architecture

File:5nscheme.png

2010-04-30T08:17:58Z

Jong: Schematic of a 5 to 32 decoder

Schematic of a 5 to 32 decoder

File:2nscheme.png

2010-04-30T08:15:21Z

Jong: Schematic of a 2 to 4 decoder

Schematic of a 2 to 4 decoder

File:Memreg.png

2010-04-30T08:10:56Z

Jong: Schematic of an 8-bit register

Schematic of an 8-bit register

User:Jong

2010-04-30T08:08:27Z

Jong: Replaced content with '==Dwarven Computer== User:Jong/Dwarven_Computer'

==Dwarven Computer==
[[User:Jong/Dwarven_Computer]]

User:Jong/Dwarven Computer

2010-04-30T08:08:08Z

Jong: Dwarven Computer Design

Adapted from http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en

Need to wikify it.

== Notes ==

Toggled gear assemblies are designed as though they are off in when untriggered. However they are constructed in the on position. This means that you need to build and link a lever to toggle it to the off state.

==Designs for power sensor (output device)==

# %>^ #
~ ~ ~ ~# Power sensor side view

In order to do useful things, such as toggling gears assemblies, opening doors, etc., mechanical power signals need to be converted to a trigger signal. There are only 2 trigger signal generators in dwarf fortress. One is the lever, which cannot be linked to machine power. The other is a pressure plate, which can.

The basic operation of this component is simple. Power operates the pump, pushing water over the pressure plate, generating a signal. When the pump is not powered, the water drains, switching the pressure plate off after at least 100 steps.

The smooth operation of this unit depends on several factors:
1. Adequate supply of water in the input tile so that the pump can maintain 7/7 or 6/7 water levels on the pressure plate. Can be done by providing more water tiles adjacent to the input tile.
2. Fast drainage to minimize the time needed for the plate to switch off. Just make sure that the level below the pumps is not completely full.
3. Since the minimum recovery time of the pressure plate is 100 steps, it can take a good long time for a 0-bit to reach the end of a chain of output units.

==Design for a memory cell for use in registers/memory unit==

###
#H#
#^#PRoO
#%#
#%WIP
#~#
###

This design is based on plans found at User:SL/Logic_Gates on the wiki. For this design, the write-in signal is linked to gear W and hatch H, while the read-out signal is linked to gear R. Gear o is linked to the pressure plate ^ and represents the state of the cell. Big O represents to output signal and I represents the input signal. P represents a power source. The hatch prevents the water from draining thus preserving the data.

In order to act as a memory cell, this unit must do 3 things:
1. Output its state when told to read-out
2. Change state to match an input when told to write-in
3. Maintain its state when not told to do anything

Let's check this by examining the operation of this unit.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|R
!width="40"|W
!width="40"|I
!width="40"|State
!width="40"|O
|-
| 0
| 0
| Ignored
| Unchanged
| 0
|-
| 1
| 0
| Ignored
| 0
| 0
|-
| 1
| 0
| Ignored
| 1
| 1
|-
| 0
| 1
| 1
| 1
| 0
|-
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

When both read and write are turned on, the device will act as a power sensor for the input. This could be a problem if the input and output are linked.

One point of concern is that the unit may not contain sufficient water to trigger the plate because the amount of water in the square above the hatch may not be 7 when it closes.

The plate could be set to trigger at a lower threshold, which would slightly slow down response time, or a door could be used instead of a hatch and the unit extended by one tile to provide space for the drain. This would have the downside of destroying some water after every write operation.

Another method is to use another pump to drain the water from the holding tile. This pump will only activate when W is 1 and I is 0.

==Design for the computer registers==

The dwarven computer prototype is going to have an 8-bit instruction length, a 3-bit operon and a 5-bit address space. Why? The best reason for this is that other designs of Very Simple Computers (VSC) on the Internet are also only 8-bit and I am basing the design of the prototype dwarven computer off several of them. Naturally a bigger computer is better in many ways but the current goal is to produce an operational one. Now its not clear to me why a VSC shouldn't be smaller, but I suppose it doesn't matter.

8-bit words need 8-bit registers. Fortunately this just means stacking 8 memory units up and making sure they receive the same read/write signals.

The lines in the diagram don't actually represent physical connections but imaginary ones. After all, the write signal must be sent remotely.

Now we consider the most compact designs for such an array. Let us assume that the output signals will be sent remotely. For clarity, the arrays ought to be rectangular.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~R
P`````````````````````````````````````````````P
Note that the O is omitted since it was a placeholder for the output device.

Not all registers in the computer are 8 bit registers. For example the memory address register is 5 bits.

==Design for the Memory Unit==

Since there are only 5 bits of address space, I only need 256 memory cells. It should be fine if I don't use complicated column and row addressing schemes. I shall simply have 32 8-bit registers sticking somewhere. In order for the memory unit to work, I need a decoder to change the 5-bit address into 32 outputs. This will enable the memory unit to read and write from any register. I guess this makes it random access memory.

===Design for a decoder===

This type of decoder is called an n to 2^n decoder, since it converts n inputs into 2^n outputs, in this case 5 to 32(2^5).

To illustrate the design for this unit, let us consider a simpler example where n=2. There will be 2 binary inputs which will be converted into 4 unique outputs, 1 for each memory address.

Here is the truth table for the operation:

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|2^0 (1)
!width="40"|2^1 (2)
!width="40"|O0
!width="40"|O1
!width="40"|O2
!width="40"|O3
|-
| 0
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
| 0
| 0
|-
| 0
| 1
| 0
| 0
| 1
| 0
|-
| 1
| 1
| 0
| 0
| 0
| 1
|} 

Now let us examine the implementation into the dwarfputer. Remember that gear assemblies are toggleable. I can implement a NOT operation by simply reversing the default state of a triggered gear (which is OFF in this system).

Let us represent the 2^0 gear as A when it is default OFF and as a when it is default ON, and represent the 2^1 gear as B and b. O0 to O3 represent output devices.

P P P P
a A a A
b b B B
O0 O1 O2 O3

This is the easiest to understand implementation. Looking at O0, we see that O0 is powered only when a and b are active. This corresponds to the state when 2^0 and 2^1 are both 0. Examining all the devices reveals that this arrangement obeys the truth table detailed above. Further examination would reveal that this arrangement also follows a pattern. Basically, the full set of columns represent every single possible combination of a, A, b, and B. Therefore we can easily see how to expand this system to n=5.

However, this implementation is not the most efficient one. I can also arrange the gears like so:

O3A AO1
BPb
O2a aO0

This arrangement uses 7 gears while the first arrangement uses 12 gears (including power gears). I put B and b closest to the power supply to obtain an orderly arrangement of O0 to O3 although this isn't strictly necessary.

Schematically this arrangement looks like this:

Which is just some sort of tree diagram. I can easily expand this to n=5 which is what I want.

I drew this diagram in rectangular form so that I can better see how to construct the decoder. The outputs of the decoder will be in a 4x8 grid. Since the output units are longer in one direction than the other, I will align their long axis along the short axis of the diagram. It is probably best to place all the mechanisms for the decoder in the level above the outputs.

===Design for Memory Unit Registers===

The registers in the memory unit need some modification to work correctly. Only the register indicated in the memory address register ought to respond to read write signals. Therefore each of the 32 registers needs to be connected to one of the outputs from the decoder.

In this example, the register only responds when 00000 is in the memory address register.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~R
CP```P`````P`````P`````P`````P`````P`````P```PC

C in this diagram represents the output O0. I believe this is called the chip select signal in real computers.

It may be possible to wire the decoder directly to the power supply of the memory, which would remove the need for an output device.

===Memory Unit Architecture===

Right, I based the design of the memory unit off a java applet simulator I found on the Internet.

What this diagram is supposed to illustrate is that ALL the memory cells are linked to respond to the same read-out signal and the same write-in signal. Similarly, all the corresponding cells respond to same input, and all output to the same place. However, they will do none of these things unless they get a signal from the decoder, and only one register will get the signal as indicated in the memory address register.

Now the input and output buffers shown here may not be in the final blueprints, depending on the design of the rest of the computer.

==Designing the machine language==

The machine language is the set of instructions the computer will be able to execute. What these instructions are will define the design of the remaining components. For example, the Arithmetic Logic Unit needs to be able to perform the various operations listed in these instructions.

Ideally this language should be complete, that is, any function can be simulated as a combination of these instructions. I also want to be as simple as possible, to minimize the complexity of the ALU. It is worth restating that I am basing the overall design for the computer on a design for a VSC off the Internet.

Since the opcode for this computer is 3-bits long, there can only be 8 instructions.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!Opcode
!Function
!Operand
|-
| 000
| Load Accumulator from memory (indirectly)
| Memory Address
|-
| 001
| Store Accumulator to memory
| Memory Address
|-
| 010
| Add
| Memory Address
|-
| 011
| Subtract
| Memory Address
|-
| 100
| Jump to address if accumulator is not negative
| Memory Address
|-
| 101
| Binary shift left (*2) (input 0 as LSB)
| Memory Address
|-
| 110
| Binary shift right (/2) (retain MSB)
| Memory Address
|-
| 111
| Halt
| None
|} 

==Design for the Arithmetic Logic Unit (ALU)==

Now I know that the ALU needs to be able to perform 4 functions: Add, subtract, shift left and shift right. The unit needs to do one of these functions based on one of 4 input signals it may receive.

The ALU will receive 2 8-bit inputs and produce 1 8-bit output. It will require 3 systems, the adder-subtractor, bitshift left and bitshift right. These systems would be integrated to form the ALU.

===Design for a half adder===

While there are existing dwarven adder designs out there, they do not come with schematics detailing the links between their components. Therefore I feel the need to design from scratch.

A simple half adder would take 2 inputs, and produce an output and an overflow output called a carry.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!width="40"|C
!width="40"|O
|-
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 1
|-
| 1
| 1
| 1
| 0
|} 

Carry out circuit C==ABP

aBP
Output circuit O==o
bAP

C===A
Combined circuit aBP
O==obA

This schematic shows a dwarven half adder that obeys the above truth table. In this diagram, the o represents a normal gear assembly and = represents axles. This design rests on the assumption that axles do not receive power except from their end tiles. It also takes advantage of the assumption that a matched pair of gears will not transmit information across their connection (here it is the B and b gear)

I believe this design uses the minimum number of gear assemblies, although I am not sure.

===Design for a full adder===

In order for an adder to work properly, it must also receive the carry bit in addition to the 2 inputs. Ultimately, even the first adder in the final adder-subtracter must be able to receive a carry bit to operate successfully, which is why I didn't draw up a full plan for the half adder.

{| class="wikitable" border=1 style="text-align:center" cellpadding="2" cellspacing="0"
|-
!width="40"|A
!width="40"|B
!C (carry in)
!O2 (carry out)
!width="40"|O1
|-
| 0
| 0
| 0
| 0
| 0
|-
| 1
| 0
| 0
| 0
| 1
|-
| 0
| 1
| 0
| 0
| 1
|-
| 1
| 1
| 0
| 1
| 0
|-
| 0
| 0
| 1
| 0
| 1
|-
| 1
| 0
| 1
| 1
| 0
|-
| 0
| 1
| 1
| 1
| 0
|-
| 1
| 1
| 1
| 1
| 1
|} 

PB
CAo==O2 Carry Out Circuit
oBo

o=o=o=o==O1 Output Circuit
C c c C
B b B b
A A a a
P P P P

O1 O2 Combined Circuit
oo=oo |
Cc cC oo
Bb BbBAB
PAo oaPCo

Now that looks pretty monstrous. Undoubtedly the arrangement of gears could be changed here and there depending on the exact dimensions you need the array to be, but hopefully this diagram illustrates methods that can be used to minimize the complexity of the device. Note that where there are adjacent identical gears directly connected to the power source, one of them can be replaced by an ordinary gear, which will remove a linking task for that gear.

````` oCBAP
```` ocbo
##### ``|``
#.#.#` ``ocBo
#^#^#` `ooCba Hypothetical implementation
#%#%#` `o``BP
`%`%`` ```oAC
`~`~`` ```oBo
````` `````
lvlz lvlz+1

The above diagram details a hypothetical implementation for a full adder. The ```s represent the shadow of the mechanisms above and below the level. The left power sensor produces the output signal while the right power sensor produces the carry signal to be relayed to the next adder. The total footprint of the unit is 6x9. In an array, the units can overlap one tile so the total footprint of an 8-bit adder would be 41x9. Maximum operational power draw is 131x8(1048) units of power.

===Design for an 8-bit ripple carry adder-subtracter===

In order to build a full 8-bit adder-subtracter, all you need to do is to stack up 8 full adders next to each other and ensure that all the gears have been linked to the appropriate plates.

Now to get the adder-subtracter to subtract, all you have to do is to link up every single A and a (or B and b) gear assembly to the pressure plate sending the subtract signal. When the signal is sent, all the gears linked to a register will toggle. This will have the effect of inverting whatever input the register is sending. Finally the signal also needs to activate the carry in gears in the first adder, which will have the effect of adding 1 to the resulting sum (difference), giving the correct answer in two's complement representation.

===Design for a carry-look-ahead adder===

I did some research into carry-look-ahead adders to see if it was worth implementing. Carry-look-ahead adders are faster than ripple-carry adders as ripple carry adders have to wait for the carry bit to 'ripple' through the chain of adders before getting the correct result. This is most significant for users of fluid logic, as fluid logic adders need to wait n*100 steps (n being the number of bits) for the carry to ripple all the way to the end. (Floodgates and bridges have a 100 step delay before activating or deactivating)

I found that I could easily design a carry-look-ahead adder using mechanical logic that calculates the carry in bit for all bits in a single step. I would also like to point out that real carry-look-ahead adders are more complicated because they don't have teleporting switch signals.

Firstly, looking at the carry-out circuit for the full adder, I see that not only can it exist independently from the sum circuit, the C gear is directly attached to the power source. I can take advantage of this by separating the carry bit calculation circuits from the adder and attaching them to each other like so.

Then for the summing part of the adder, I simply build only the output circuit, which I can now simplify like this

O1 Output Circuit
oo=oo
Cc cC
Bb Bb
oAPao

Or I can make it long instead of square so that it will tile better with the output buffers.

O1
|
oBCoCbo
AbcocBa
P P

I could construct these directly above the output buffers and they would all tile a lot better. Not only that, it fits almost perfectly within the footprint of a bank of output buffers. There is also no cost of increased complexity, only spatial separation between the summation unit and the carry unit, plus providing all the advantages of the carry-look-ahead system.

Since this system is superior in all ways to the ripple-carry system, this will be the one going into the final dwarven computer.

===Design for bitshifting operations===

Setting up a bitshifting operation is relatively simple. I simply wire the inputs directly into slightly different outputs as illustrated in the following diagrams (source: Wikipedia http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift).

Ideally all these operations would be linked into the same bank of output buffers in the assembled ALU, which will be the subject of the next section.

===Design for ALU architecture===

This diagram illustrates the various signals moving around the ALU. I decided that I ought to dragoon the ALU into incrementing the program counter as well, but I'm not sure whether that will work or not. We'll see in the later sections.

I defined the inputs from AR1 to be A since there are fewer A and a gears in the current designs and they all have to be toggled by the subtract signal. The operations listed on the right are signals generated by the control unit and they tell the ALU which operation to perform and transfer to the output buffer banks. The component critical to this function is the multiplexer.

The concept of the multiplexer is quite simple, suppose I had 2 inputs I and J, and I wanted to choose which one to pass based on signals Q and R, I would have to build something like this

PQIoJRP
|
O

Adding a multiplexer onto the output circuit would require an additional z-level if the tiling efficiency is to be maintained.

This diagram illustrates a hypothetical implementation of the multiplexer, as well as the bitshifting logic. I don't think I need a support axle on z+2 as it should be supported by O1.

==Design of the bus==

I've decided to ditch the plan for a bus, which would have been the conduit for data transfers between registers throughout the computer. Initially there were 2 methods, one had a output buffer attached to the end of the bus while the other the bus directly supplied power to the inputs of the appropriate registers.

Method 2 would not work on memory cells that used an active pump for bit-clearing. Method 1 would have worked but the output buffers had to be overwritten every step and that could cause cascading delays throughout the computer. Since this computer is relatively simple, I opted for hard wiring everything instead.

This diagram illustrates the data transfers that occur throughout the computer. The red arrows depict confirmed hard-wired connections, while the blue arrows would have been routed through a bus. I've decide AR1 is superfluous so I got rid of it. As you can see, each register has at most 2 inputs or 2 outputs going through the bus, so hardwiring is feasible.

==Design of the timing circuit==

Before the computer can execute its instructions, it needs to perform some operations first.

#Transfer the contents of the accumulator to AR2. Dump instruction register and memory address register. 
#Transfer the program counter to the memory address register. Also, activate the program counter incrementation system in the ALU and transfer the results into program counter +1. 
#Load the data from memory at the specified address into the instruction register. 
#Transfer the data from program counter +1 to the program counter. Also, dump the memory address register 
#Load the last 5 digits of the instruction register into the memory address register. Also, dump program counter +1. 
#Execution (write accumulator, memory or program counter, read instruction register, memory, AR2) 

There needs to be a 100 step delay from the time a memory cell is written (or dumped, if it is pre-dumped) and when it is read, or it may cause cascading delays. The writing process is practically instantaneous, but 100 steps are needed before the correct result can be read if the memory was not cleared to begin with. Of course this point is entirely moot if the computer is running automatically, in which case every step will last at least 100 steps anyway and the prime consideration is to ensure that every step can be performed in 100 steps.

==Design of the oscillator==

A typical mechanical oscillator is unsatisfactory because it will usually be sending out 2 on signals at once, one from the pressure plate the water is on and the other from the pressure plate waiting to reset.

0%%6%%0%%5%%0%%4
% %
% %
1%%0%%2%%0%%3%%0

This diagram shows a 12 step 6 signal oscillator. At the locations marked 0, there are no pressure plates. A lever operates the mechanism. When the lever is in the ON position, the #%%0 pumps activate, and when the lever is in the OFF position, the 0%%# pumps activate. The oscillator can also be fully automated by using the pressure plates themselves to replace the lever function. The oscillator's power supply also needs to be cut if a halt signal is received from the control unit.

===Oscillator Link table===

#Read accumulator, write AR2, write IR, write MAR 
#Read PC, write MAR, activate ALU (adder select, C0=1), write PC+1 
#Read MEM, read MAR. activate decoder, write IR 
#Read PC+1, write PC, write MAR 
#Read IR, write MAR, write PC+1 
#Execution (read IR, turn on control unit) 

A dump operation can be performed by telling the memory register to write when its linked inputs are inactive, effectively writing 0s.

==Design of the control unit==

The control unit can be implemented simply as a 3-8 decoder with appropriately linked pressure plates. The execute signal controlled gear assembly is located at the root of the decoder.

===Control unit link table===

:O0. Read memory, read MAR, activate decoder, write accumulator, select transfer 
:O1. Read accumulator, write memory, read MAR, activate decoder 
:O2. Read memory, read MAR, activate decoder, read AR2, Send Add signal to ALU (adder select), write accumulator 
:O3. Read memory, read MAR, activate decoder, read AR2, Send Subtract signal to ALU (adder select, C0=1, invert input A), write accumulator 
:O4. Read IR, write PC if ACC7=0 
:O5. Read memory, read MAR, activate decoder, Send Shift left signal to ALU (SHL select), write accumulator 
:O6. Read memory, read MAR, activate decoder, Send Shift right signal to ALU (SHR select), write accumulator 
:O7. Cut power to oscillator.

User:Jong

2010-04-30T08:05:03Z

Jong:

User:Jong

2010-04-30T07:05:37Z

Jong:

Adapted from http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en

== Notes ==

Toggled gear assemblies are designed as though they are off in when untriggered. However they are constructed in the on position. This means that you need to build and link a lever to toggle it to the off state.

==Designs for power sensor (output device)==

# %>^ #
~ ~ ~ ~# Power sensor side view

In order to do useful things, such as toggling gears assemblies, opening doors, etc., mechanical power signals need to be converted to a trigger signal. There are only 2 trigger signal generators in dwarf fortress. One is the lever, which cannot be linked to machine power. The other is a pressure plate, which can.

The basic operation of this component is simple. Power operates the pump, pushing water over the pressure plate, generating a signal. When the pump is not powered, the water drains, switching the pressure plate off after at least 100 steps.

The smooth operation of this unit depends on several factors:
1. Adequate supply of water in the input tile so that the pump can maintain 7/7 or 6/7 water levels on the pressure plate. Can be done by providing more water tiles adjacent to the input tile.
2. Fast drainage to minimize the time needed for the plate to switch off. Just make sure that the level below the pumps is not completely full.
3. Since the minimum recovery time of the pressure plate is 100 steps, it can take a good long time for a 0-bit to reach the end of a chain of output units.

==Design for a memory cell for use in registers/memory unit==

###
#H#
#^#PRoO
#%#
#%WIP
#~#
###

This design is based on plans found at User:SL/Logic_Gates on the wiki. For this design, the write-in signal is linked to gear W and hatch H, while the read-out signal is linked to gear R. Gear o is linked to the pressure plate ^ and represents the state of the cell. Big O represents to output signal and I represents the input signal. P represents a power source. The hatch prevents the water from draining thus preserving the data.

In order to act as a memory cell, this unit must do 3 things:
1. Output its state when told to read-out
2. Change state to match an input when told to write-in
3. Maintain its state when not told to do anything

Let's check this by examining the operation of this unit.

R W I State O
0 0 Ignored Unchanged 0
1 0 Ignored 0 0
1 0 Ignored 1 1
0 1 1 1 0
0 1 0 0 0
1 1 1 1 1

{| class="wikitable"
|-
! R
! W
! I
! State
! O
|-
| 0
| 0
| Ignored
| Unchanged
| 0
|-
| 1
| 0
| Ignored
| 0
| 0
|-
| 1
| 0
| Ignored
| 1
| 1
|-
| 0
| 1
| 1
| 1
| 0
|-
| 0
| 1
| 0
| 0
| 0
|-
| 1
| 1
| 1
| 1
| 1
|}

When both read and write are turned on, the device will act as a power sensor for the input. This could be a problem if the input and output are linked.

One point of concern is that the unit may not contain sufficient water to trigger the plate because the amount of water in the square above the hatch may not be 7 when it closes.

The plate could be set to trigger at a lower threshold, which would slightly slow down response time, or a door could be used instead of a hatch and the unit extended by one tile to provide space for the drain. This would have the downside of destroying some water after every write operation.

Another method is to use another pump to drain the water from the holding tile. This pump will only activate when W is 1 and I is 0.

Design for the computer registers

The dwarven computer prototype is going to have an 8-bit instruction length, a 3-bit operon and a 5-bit address space. Why? The best reason for this is that other designs of Very Simple Computers (VSC) on the Internet are also only 8-bit and I am basing the design of the prototype dwarven computer off several of them. Naturally a bigger computer is better in many ways but the current goal is to produce an operational one. Now its not clear to me why a VSC shouldn't be smaller, but I suppose it doesn't matter.

8-bit words need 8-bit registers. Fortunately this just means stacking 8 memory units up and making sure they receive the same read/write signals.

The lines in the diagram don't actually represent physical connections but imaginary ones. After all, the write signal must be sent remotely.

Now we consider the most compact designs for such an array. Let us assume that the output signals will be sent remotely. For clarity, the arrays ought to be rectangular.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~R
P`````````````````````````````````````````````P
Note that the O is omitted since it was a placeholder for the output device.

Not all registers in the computer are 8 bit registers. For example the memory address register is 5 bits.

Design for the Memory Unit

Since there are only 5 bits of address space, I only need 256 memory cells. It should be fine if I don't use complicated column and row addressing schemes. I shall simply have 32 8-bit registers sticking somewhere. In order for the memory unit to work, I need a decoder to change the 5-bit address into 32 outputs. This will enable the memory unit to read and write from any register. I guess this makes it random access memory.

Design for a decoder

This type of decode is called an n to 2^n decoder, since it converts n inputs into 2^n outputs, in this case 5 to 32(2^5).

To illustrate the design for this unit, let us consider a simpler example where n=2. There will be 2 binary inputs which will be converted into 4 unique outputs, 1 for each memory address.

Here is the truth table for the operation:

2^0 (1) 2^1 (2) O0 O1 O2 O3
0 0 1 0 0 0
1 0 0 1 0 0
0 1 0 0 1 0
1 1 0 0 0 1

Now let us examine the implementation into the dwarfputer. Remember that gear assemblies are toggleable. I can implement a NOT operation by simply reversing the default state of a triggered gear (which is OFF in this system).

Let us represent the 2^0 gear as A when it is default OFF and as a when it is default ON, and represent the 2^1 gear as B and b. O0 to O3 represent output devices.

P P P P
a A a A
b b B B
O0 O1 O2 O3

This is the easiest to understand implementation. Looking at O0, we see that O0 is powered only when a and b are active. This corresponds to the state when 2^0 and 2^1 are both 0. Examining all the devices reveals that this arrangement obeys the truth table detailed above. Further examination would reveal that this arrangement also follows a pattern. Basically, the full set of columns represent every single possible combination of a, A, b, and B. Therefore we can easily see how to expand this system to n=5.

However, this implementation is not the most efficient one. I can also arrange the gears like so:

O3A AO1
BPb
O2a aO0

This arrangement uses 7 gears while the first arrangement uses 12 gears (including power gears). I put B and b closest to the power supply to obtain an orderly arrangement of O0 to O3 although this isn't strictly necessary.

Schematically this arrangement looks like this:

Which is just some sort of tree diagram. I can easily expand this to n=5 which is what I want.

I drew this diagram in rectangular form so that I can better see how to construct the decoder. The outputs of the decoder will be in a 4x8 grid. Since the output units are longer in one direction than the other, I will align their long axis along the short axis of the diagram. It is probably best to place all the mechanisms for the decoder in the level above the outputs.

Design for Memory Unit Registers

The registers in the memory unit need some modification to work correctly. Only the register indicated in the memory address register ought to respond to read write signals. Therefore each of the 32 registers needs to be connected to one of the outputs from the decoder.

In this example, the register only responds when 00000 is in the memory address register.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~R
CP```P`````P`````P`````P`````P`````P`````P```PC

C in this diagram represents the output O0. I believe this is called the chip select signal in real computers.

It may be possible to wire the decoder directly to the power supply of the memory, which would remove the need for an output device.

Memory Unit Architecture

Right, I based the design of the memory unit off a java applet simulator I found on the Internet.

What this diagram is supposed to illustrate is that ALL the memory cells are linked to respond to the same read-out signal and the same write-in signal. Similarly, all the corresponding cells respond to same input, and all output to the same place. However, they will do none of these things unless they get a signal from the decoder, and only one register will get the signal as indicated in the memory address register.

Now the input and output buffers shown here may not be in the final blueprints, depending on the design of the rest of the computer.

Designing the machine language

The machine language is the set of instructions the computer will be able to execute. What these instructions are will define the design of the remaining components. For example, the Arithmetic Logic Unit needs to be able to perform the various operations listed in these instructions.

Ideally this language should be complete, that is, any function can be simulated as a combination of these instructions. I also want to be as simple as possible, to minimize the complexity of the ALU. It is worth restating that I am basing the overall design for the computer on a design for a VSC off the Internet.

Since the opcode for this computer is 3-bits long, there can only be 8 instructions.

Opcode Function Operand
000 Load Accumulator from memory (indirectly) Memory Address
001 Store Accumulator to memory Memory Address
010 Add Memory Address
011 Subtract Memory Address
100 Jump to address if accumulator is not negative Memory Address
101 Binary shift left (*2) (input 0 as LSB) Memory Address
110 Binary shift right (/2) (retain MSB) Memory Address
111 Halt Irrelevant

Design for the Arithmetic Logic Unit (ALU)

Now I know that the ALU needs to be able to perform 4 functions: Add, subtract, shift left and shift right. The unit needs to do one of these functions based on one of 4 input signals it may receive.

The ALU will receive 2 8-bit inputs and produce 1 8-bit output. It will require 3 systems, the adder-subtractor, bitshift left and bitshift right. These systems would be integrated to form the ALU.

Design for a half adder

While there are existing dwarven adder designs out there, they do not come with schematics detailing the links between their components. Therefore I feel the need to design from scratch.

A simple half adder would take 2 inputs, and produce an output and an overflow output called a carry.

A B C O
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 0

Carry out circuit C==ABP

aBP
Output circuit O==o
bAP

C===A
aBP
O==obA
Combined circuit

This schematic shows a dwarven half adder that obeys the above truth table. In this diagram, the o represents a normal gear assembly and = represents axles. This design rests on the assumption that axles do not receive power except from their end tiles. It also takes advantage of the assumption that a matched pair of gears will not transmit information across their connection (here it is the B and b gear)

I believe this design uses the minimum number of gear assemblies, although I am not sure.

Design for a full adder

In order for an adder to work properly, it must also receive the carry bit in addition to the 2 inputs. Ultimately, even the first adder in the final adder-subtracter must be able to receive a carry bit to operate successfully, which is why I didn't draw up a full plan for the half adder.

A B C (carry in) O2 (carry out) O1
0 0 0 0 0
1 0 0 0 1
0 1 0 0 1
1 1 0 1 0
0 0 1 0 1
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1

PB
CAo==O2 Carry Out Circuit
oBo

o=o=o=o==O1 Output Circuit
C c c C
B b B b
A A a a
P P P P

O1 O2 Combined Circuit
oo=oo |
Cc cC oo
Bb BbBAB
PAo oaPCo

Now that looks pretty monstrous. Undoubtedly the arrangement of gears could be changed here and there depending on the exact dimensions you need the array to be, but hopefully this diagram illustrates methods that can be used to minimize the complexity of the device. Note that where there are adjacent identical gears directly connected to the power source, one of them can be replaced by an ordinary gear, which will remove a linking task for that gear.

````` oCBAP
```` ocbo
##### ``|``
#.#.#` ``ocBo
#^#^#` `ooCba Hypothetical implementation
#%#%#` `o``BP
`%`%`` ```oAC
`~`~`` ```oBo
````` `````
lvlz lvlz+1

The above diagram details a hypothetical implementation for a full adder. The ```s represent the shadow of the mechanisms above and below the level. The left power sensor produces the output signal while the right power sensor produces the carry signal to be relayed to the next adder. The total footprint of the unit is 6x9. In an array, the units can overlap one tile so the total footprint of an 8-bit adder would be 41x9. Maximum operational power draw is 131x8(1048) units of power.

Design for an 8-bit ripple carry adder-subtracter

In order to build a full 8-bit adder-subtracter, all you need to do is to stack up 8 full adders next to each other and ensure that all the gears have been linked to the appropriate plates.

Now to get the adder-subtracter to subtract, all you have to do is to link up every single A and a (or B and b) gear assembly to the pressure plate sending the subtract signal. When the signal is sent, all the gears linked to a register will toggle. This will have the effect of inverting whatever input the register is sending. Finally the signal also needs to activate the carry in gears in the first adder, which will have the effect of adding 1 to the resulting sum (difference), giving the correct answer in two's complement representation.

Design for a carry-look-ahead adder

I did some research into carry-look-ahead adders to see if it was worth implementing. Carry-look-ahead adders are faster than ripple-carry adders as ripple carry adders have to wait for the carry bit to 'ripple' through the chain of adders before getting the correct result. This is most significant for users of fluid logic, as fluid logic adders need to wait n*100 steps (n being the number of bits) for the carry to ripple all the way to the end. (Floodgates and bridges have a 100 step delay before activating or deactivating)

I found that I could easily design a carry-look-ahead adder using mechanical logic that calculates the carry in bit for all bits in a single step. I would also like to point out that real carry-look-ahead adders are more complicated because they don't have teleporting switch signals.

Firstly, looking at the carry-out circuit for the full adder, I see that not only can it exist independently from the sum circuit, the C gear is directly attached to the power source. I can take advantage of this by separating the carry bit calculation circuits from the adder and attaching them to each other like so.

Then for the summing part of the adder, I simply build only the output circuit, which I can now simplify like this

O1 Output Circuit
oo=oo
Cc cC
Bb Bb
oAPao

Or I can make it long instead of square so that it will tile better with the output buffers.

O1
|
oBCoCbo
AbcocBa
P P

I could construct these directly above the output buffers and they would all tile a lot better. Not only that, it fits almost perfectly within the footprint of a bank of output buffers. There is also no cost of increased complexity, only spatial separation between the summation unit and the carry unit, plus providing all the advantages of the carry-look-ahead system.

Since this system is superior in all ways to the ripple-carry system, this will be the one going into the final dwarven computer.

Design for bitshifting operations

Setting up a bitshifting operation is relatively simple. I simply wire the inputs directly into slightly different outputs as illustrated in the following diagrams (source: Wikipedia http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift).

Ideally all these operations would be linked into the same bank of output buffers in the assembled ALU, which will be the subject of the next section.

Design for ALU architecture

This diagram illustrates the various signals moving around the ALU. I decided that I ought to dragoon the ALU into incrementing the program counter as well, but I'm not sure whether that will work or not. We'll see in the later sections.

I defined the inputs from AR1 to be A since there are fewer A and a gears in the current designs and they all have to be toggled by the subtract signal. The operations listed on the right are signals generated by the control unit and they tell the ALU which operation to perform and transfer to the output buffer banks. The component critical to this function is the multiplexer.

The concept of the multiplexer is quite simple, suppose I had 2 inputs I and J, and I wanted to choose which one to pass based on signals Q and R, I would have to build something like this

PQIoJRP
|
O

Adding a multiplexer onto the output circuit would require an additional z-level if the tiling efficiency is to be maintained.

This diagram illustrates a hypothetical implementation of the multiplexer, as well as the bitshifting logic. I don't think I need a support axle on z+2 as it should be supported by O1.

Design of the bus

I've decided to ditch the plan for a bus, which would have been the conduit for data transfers between registers throughout the computer. Initially there were 2 methods, one had a output buffer attached to the end of the bus while the other the bus directly supplied power to the inputs of the appropriate registers.

Method 2 would not work on memory cells that used an active pump for bit-clearing. Method 1 would have worked but the output buffers had to be overwritten every step and that could cause cascading delays throughout the computer. Since this computer is relatively simple, I opted for hard wiring everything instead.

This diagram illustrates the data transfers that occur throughout the computer. The red arrows depict confirmed hard-wired connections, while the blue arrows would have been routed through a bus. I've decide AR1 is superfluous so I got rid of it. As you can see, each register has at most 2 inputs or 2 outputs going through the bus, so hardwiring is feasible.

Design of the timing circuit

Before the computer can execute its instructions, it needs to perform some operations first.

Transfer the contents of the accumulator to AR2. Dump instruction register and memory address register.
Transfer the program counter to the memory address register. Also, activate the program counter incrementation system in the ALU and transfer the results into program counter +1.
Load the data from memory at the specified address into the instruction register.
Transfer the data from program counter +1 to the program counter. Also, dump the memory address register
Load the last 5 digits of the instruction register into the memory address register. Also, dump program counter +1.
Execution (write accumulator, memory or program counter, read instruction register, memory, AR2)

There needs to be a 100 step delay from the time a memory cell is written (or dumped, if it is pre-dumped) and when it is read, or it may cause cascading delays. The writing process is practically instantaneous, but 100 steps are needed before the correct result can be read if the memory was not cleared to begin with. Of course this point is entirely moot if the computer is running automatically, in which case every step will last at least 100 steps anyway and the prime consideration is to ensure that every step can be performed in 100 steps.

Design of the oscillator

A typical mechanical oscillator is unsatisfactory because it will usually be sending out 2 on signals at once, one from the pressure plate the water is on and the other from the pressure plate waiting to reset.

0%%6%%0%%5%%0%%4
% %
% %
1%%0%%2%%0%%3%%0

This diagram shows a 12 step 6 signal oscillator. At the locations marked 0, there are no pressure plates. A lever operates the mechanism. When the lever is in the ON position, the #%%0 pumps activate, and when the lever is in the OFF position, the 0%%# pumps activate. The oscillator can also be fully automated by using the pressure plates themselves to replace the lever function. The oscillator's power supply also needs to be cut if a halt signal is received from the control unit.

Oscillator Link table

Read accumulator, write AR2, write IR, write MAR
Read PC, write MAR, activate ALU (adder select, C0=1), write PC+1
Read MEM, read MAR. activate decoder, write IR
Read PC+1, write PC, write MAR
Read IR, write MAR, write PC+1
Execution (read IR, turn on control unit)

A dump operation can be performed by telling the memory register to write when its linked inputs are inactive, effectively writing 0s.

Design of the control unit

The control unit can be implemented simply as a 3-8 decoder with appropriately linked pressure plates. The execute signal controlled gear assembly is located at the root of the decoder.

Control unit link table

O0. Read memory, read MAR, activate decoder, write accumulator, select transfer
O1. Read accumulator, write memory, read MAR, activate decoder
O2. Read memory, read MAR, activate decoder, read AR2, Send Add signal to ALU (adder select), write accumulator
O3. Read memory, read MAR, activate decoder, read AR2, Send Subtract signal to ALU (adder select, C0=1, invert input A), write accumulator
O4. Read IR, write PC if ACC7=0
O5. Read memory, read MAR, activate decoder, Send Shift left signal to ALU (SHL select), write accumulator
O6. Read memory, read MAR, activate decoder, Send Shift right signal to ALU (SHR select), write accumulator
O7. Cut power to oscillator.

User:Jong

2010-04-30T06:50:18Z

Jong: Created page with 'Notes Toggled gear assemblies are designed as though they are off in when untriggered. However they are constructed in the on position. This means that you need to build and lin…'

Notes

Toggled gear assemblies are designed as though they are off in when untriggered. However they are constructed in the on position. This means that you need to build and link a lever to toggle it to the off state.

Designs for power sensor (output device)

# %>^ #
06:50, 30 April 2010 (UTC)~~#

Power sensor side view.

In order to do useful things, such as toggling gears assemblies, opening doors, etc., mechanical power signals need to be converted to a trigger signal. There are only 2 trigger signal generators in dwarf fortress. One is the lever, which cannot be linked to machine power. The other is a pressure plate, which can.

The basic operation of this component is simple. Power operates the pump, pushing water over the pressure plate, generating a signal. When the pump is not powered, the water drains, switching the pressure plate off after at least 100 steps.

The smooth operation of this unit depends on several factors:
1. Adequate supply of water in the input tile so that the pump can maintain 7/7 or 6/7 water levels on the pressure plate. Can be done by providing more water tiles adjacent to the input tile.
2. Fast drainage to minimize the time needed for the plate to switch off. Just make sure that the level below the pumps is not completely full.
3. Since the minimum recovery time of the pressure plate is 100 steps, it can take a good long time for a 0-bit to reach the end of a chain of output units.

Design for a memory cell for use in registers/memory unit

###
#H#
#^#PRoO
#%#
#%WIP
#~#
###

This design is based on plans found at User:SL/Logic_Gates on the wiki. For this design, the write-in signal is linked to gear W and hatch H, while the read-out signal is linked to gear R. Gear o is linked to the pressure plate ^ and represents the state of the cell. Big O represents to output signal and I represents the input signal. P represents a power source. The hatch prevents the water from draining thus preserving the data.

In order to act as a memory cell, this unit must do 3 things:
1. Output its state when told to read-out
2. Change state to match an input when told to write-in
3. Maintain its state when not told to do anything

Let's check this by examining the operation of this unit.

R W I State O
0 0 Ignored Unchanged 0
1 0 Ignored 0 0
1 0 Ignored 1 1
0 1 1 1 0
0 1 0 0 0
1 1 1 1 1

When both read and write are turned on, the device will act as a power sensor for the input. This could be a problem if the input and output are linked.

One point of concern is that the unit may not contain sufficient water to trigger the plate because the amount of water in the square above the hatch may not be 7 when it closes.

The plate could be set to trigger at a lower threshold, which would slightly slow down response time, or a door could be used instead of a hatch and the unit extended by one tile to provide space for the drain. This would have the downside of destroying some water after every write operation.

Another method is to use another pump to drain the water from the holding tile. This pump will only activate when W is 1 and I is 0.

Design for the computer registers

The dwarven computer prototype is going to have an 8-bit instruction length, a 3-bit operon and a 5-bit address space. Why? The best reason for this is that other designs of Very Simple Computers (VSC) on the Internet are also only 8-bit and I am basing the design of the prototype dwarven computer off several of them. Naturally a bigger computer is better in many ways but the current goal is to produce an operational one. Now its not clear to me why a VSC shouldn't be smaller, but I suppose it doesn't matter.

8-bit words need 8-bit registers. Fortunately this just means stacking 8 memory units up and making sure they receive the same read/write signals.

The lines in the diagram don't actually represent physical connections but imaginary ones. After all, the write signal must be sent remotely.

Now we consider the most compact designs for such an array. Let us assume that the output signals will be sent remotely. For clarity, the arrays ought to be rectangular.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~RPI~`~R
P`````````````````````````````````````````````P
Note that the O is omitted since it was a placeholder for the output device.

Not all registers in the computer are 8 bit registers. For example the memory address register is 5 bits.

Design for the Memory Unit

Since there are only 5 bits of address space, I only need 256 memory cells. It should be fine if I don't use complicated column and row addressing schemes. I shall simply have 32 8-bit registers sticking somewhere. In order for the memory unit to work, I need a decoder to change the 5-bit address into 32 outputs. This will enable the memory unit to read and write from any register. I guess this makes it random access memory.

Design for a decoder

This type of decode is called an n to 2^n decoder, since it converts n inputs into 2^n outputs, in this case 5 to 32(2^5).

To illustrate the design for this unit, let us consider a simpler example where n=2. There will be 2 binary inputs which will be converted into 4 unique outputs, 1 for each memory address.

Here is the truth table for the operation:

2^0 (1) 2^1 (2) O0 O1 O2 O3
0 0 1 0 0 0
1 0 0 1 0 0
0 1 0 0 1 0
1 1 0 0 0 1

Now let us examine the implementation into the dwarfputer. Remember that gear assemblies are toggleable. I can implement a NOT operation by simply reversing the default state of a triggered gear (which is OFF in this system).

Let us represent the 2^0 gear as A when it is default OFF and as a when it is default ON, and represent the 2^1 gear as B and b. O0 to O3 represent output devices.

P P P P
a A a A
b b B B
O0 O1 O2 O3

This is the easiest to understand implementation. Looking at O0, we see that O0 is powered only when a and b are active. This corresponds to the state when 2^0 and 2^1 are both 0. Examining all the devices reveals that this arrangement obeys the truth table detailed above. Further examination would reveal that this arrangement also follows a pattern. Basically, the full set of columns represent every single possible combination of a, A, b, and B. Therefore we can easily see how to expand this system to n=5.

However, this implementation is not the most efficient one. I can also arrange the gears like so:

O3A AO1
BPb
O2a aO0

This arrangement uses 7 gears while the first arrangement uses 12 gears (including power gears). I put B and b closest to the power supply to obtain an orderly arrangement of O0 to O3 although this isn't strictly necessary.

Schematically this arrangement looks like this:

Which is just some sort of tree diagram. I can easily expand this to n=5 which is what I want.

I drew this diagram in rectangular form so that I can better see how to construct the decoder. The outputs of the decoder will be in a 4x8 grid. Since the output units are longer in one direction than the other, I will align their long axis along the short axis of the diagram. It is probably best to place all the mechanisms for the decoder in the level above the outputs.

Design for Memory Unit Registers

The registers in the memory unit need some modification to work correctly. Only the register indicated in the memory address register ought to respond to read write signals. Therefore each of the 32 registers needs to be connected to one of the outputs from the decoder.

In this example, the register only responds when 00000 is in the memory address register.

##### ##### ##### ##### ##### ##### ##### #####
#H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.# #H#.#
#^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^# #^#^#
#%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%# #%#%#
W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o W%`%o
I~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~RCI~`~R
CP```P`````P`````P`````P`````P`````P`````P```PC

C in this diagram represents the output O0. I believe this is called the chip select signal in real computers.

It may be possible to wire the decoder directly to the power supply of the memory, which would remove the need for an output device.

Memory Unit Architecture

Right, I based the design of the memory unit off a java applet simulator I found on the Internet.

What this diagram is supposed to illustrate is that ALL the memory cells are linked to respond to the same read-out signal and the same write-in signal. Similarly, all the corresponding cells respond to same input, and all output to the same place. However, they will do none of these things unless they get a signal from the decoder, and only one register will get the signal as indicated in the memory address register.

Now the input and output buffers shown here may not be in the final blueprints, depending on the design of the rest of the computer.

Designing the machine language

The machine language is the set of instructions the computer will be able to execute. What these instructions are will define the design of the remaining components. For example, the Arithmetic Logic Unit needs to be able to perform the various operations listed in these instructions.

Ideally this language should be complete, that is, any function can be simulated as a combination of these instructions. I also want to be as simple as possible, to minimize the complexity of the ALU. It is worth restating that I am basing the overall design for the computer on a design for a VSC off the Internet.

Since the opcode for this computer is 3-bits long, there can only be 8 instructions.

Opcode Function Operand
000 Load Accumulator from memory (indirectly) Memory Address
001 Store Accumulator to memory Memory Address
010 Add Memory Address
011 Subtract Memory Address
100 Jump to address if accumulator is not negative Memory Address
101 Binary shift left (*2) (input 0 as LSB) Memory Address
110 Binary shift right (/2) (retain MSB) Memory Address
111 Halt Irrelevant

Design for the Arithmetic Logic Unit (ALU)

Now I know that the ALU needs to be able to perform 4 functions: Add, subtract, shift left and shift right. The unit needs to do one of these functions based on one of 4 input signals it may receive.

The ALU will receive 2 8-bit inputs and produce 1 8-bit output. It will require 3 systems, the adder-subtractor, bitshift left and bitshift right. These systems would be integrated to form the ALU.

Design for a half adder

While there are existing dwarven adder designs out there, they do not come with schematics detailing the links between their components. Therefore I feel the need to design from scratch.

A simple half adder would take 2 inputs, and produce an output and an overflow output called a carry.

A B C O
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 0

Carry out circuit C==ABP

aBP
Output circuit O==o
bAP

C===A
aBP
O==obA
Combined circuit

This schematic shows a dwarven half adder that obeys the above truth table. In this diagram, the o represents a normal gear assembly and = represents axles. This design rests on the assumption that axles do not receive power except from their end tiles. It also takes advantage of the assumption that a matched pair of gears will not transmit information across their connection (here it is the B and b gear)

I believe this design uses the minimum number of gear assemblies, although I am not sure.

Design for a full adder

In order for an adder to work properly, it must also receive the carry bit in addition to the 2 inputs. Ultimately, even the first adder in the final adder-subtracter must be able to receive a carry bit to operate successfully, which is why I didn't draw up a full plan for the half adder.

A B C (carry in) O2 (carry out) O1
0 0 0 0 0
1 0 0 0 1
0 1 0 0 1
1 1 0 1 0
0 0 1 0 1
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1

PB
CAo==O2 Carry Out Circuit
oBo

o=o=o=o==O1 Output Circuit
C c c C
B b B b
A A a a
P P P P

O1 O2 Combined Circuit
oo=oo |
Cc cC oo
Bb BbBAB
PAo oaPCo

Now that looks pretty monstrous. Undoubtedly the arrangement of gears could be changed here and there depending on the exact dimensions you need the array to be, but hopefully this diagram illustrates methods that can be used to minimize the complexity of the device. Note that where there are adjacent identical gears directly connected to the power source, one of them can be replaced by an ordinary gear, which will remove a linking task for that gear.

````` oCBAP
```` ocbo
##### ``|``
#.#.#` ``ocBo
#^#^#` `ooCba Hypothetical implementation
#%#%#` `o``BP
`%`%`` ```oAC
`~`~`` ```oBo
````` `````
lvlz lvlz+1

The above diagram details a hypothetical implementation for a full adder. The ```s represent the shadow of the mechanisms above and below the level. The left power sensor produces the output signal while the right power sensor produces the carry signal to be relayed to the next adder. The total footprint of the unit is 6x9. In an array, the units can overlap one tile so the total footprint of an 8-bit adder would be 41x9. Maximum operational power draw is 131x8(1048) units of power.

Design for an 8-bit ripple carry adder-subtracter

In order to build a full 8-bit adder-subtracter, all you need to do is to stack up 8 full adders next to each other and ensure that all the gears have been linked to the appropriate plates.

Now to get the adder-subtracter to subtract, all you have to do is to link up every single A and a (or B and b) gear assembly to the pressure plate sending the subtract signal. When the signal is sent, all the gears linked to a register will toggle. This will have the effect of inverting whatever input the register is sending. Finally the signal also needs to activate the carry in gears in the first adder, which will have the effect of adding 1 to the resulting sum (difference), giving the correct answer in two's complement representation.

Design for a carry-look-ahead adder

I did some research into carry-look-ahead adders to see if it was worth implementing. Carry-look-ahead adders are faster than ripple-carry adders as ripple carry adders have to wait for the carry bit to 'ripple' through the chain of adders before getting the correct result. This is most significant for users of fluid logic, as fluid logic adders need to wait n*100 steps (n being the number of bits) for the carry to ripple all the way to the end. (Floodgates and bridges have a 100 step delay before activating or deactivating)

I found that I could easily design a carry-look-ahead adder using mechanical logic that calculates the carry in bit for all bits in a single step. I would also like to point out that real carry-look-ahead adders are more complicated because they don't have teleporting switch signals.

Firstly, looking at the carry-out circuit for the full adder, I see that not only can it exist independently from the sum circuit, the C gear is directly attached to the power source. I can take advantage of this by separating the carry bit calculation circuits from the adder and attaching them to each other like so.

Then for the summing part of the adder, I simply build only the output circuit, which I can now simplify like this

O1 Output Circuit
oo=oo
Cc cC
Bb Bb
oAPao

Or I can make it long instead of square so that it will tile better with the output buffers.

O1
|
oBCoCbo
AbcocBa
P P

I could construct these directly above the output buffers and they would all tile a lot better. Not only that, it fits almost perfectly within the footprint of a bank of output buffers. There is also no cost of increased complexity, only spatial separation between the summation unit and the carry unit, plus providing all the advantages of the carry-look-ahead system.

Since this system is superior in all ways to the ripple-carry system, this will be the one going into the final dwarven computer.

Design for bitshifting operations

Setting up a bitshifting operation is relatively simple. I simply wire the inputs directly into slightly different outputs as illustrated in the following diagrams (source: Wikipedia http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift).

Ideally all these operations would be linked into the same bank of output buffers in the assembled ALU, which will be the subject of the next section.

Design for ALU architecture

This diagram illustrates the various signals moving around the ALU. I decided that I ought to dragoon the ALU into incrementing the program counter as well, but I'm not sure whether that will work or not. We'll see in the later sections.

I defined the inputs from AR1 to be A since there are fewer A and a gears in the current designs and they all have to be toggled by the subtract signal. The operations listed on the right are signals generated by the control unit and they tell the ALU which operation to perform and transfer to the output buffer banks. The component critical to this function is the multiplexer.

The concept of the multiplexer is quite simple, suppose I had 2 inputs I and J, and I wanted to choose which one to pass based on signals Q and R, I would have to build something like this

PQIoJRP
|
O

Adding a multiplexer onto the output circuit would require an additional z-level if the tiling efficiency is to be maintained.

This diagram illustrates a hypothetical implementation of the multiplexer, as well as the bitshifting logic. I don't think I need a support axle on z+2 as it should be supported by O1.

Design of the bus

I've decided to ditch the plan for a bus, which would have been the conduit for data transfers between registers throughout the computer. Initially there were 2 methods, one had a output buffer attached to the end of the bus while the other the bus directly supplied power to the inputs of the appropriate registers.

Method 2 would not work on memory cells that used an active pump for bit-clearing. Method 1 would have worked but the output buffers had to be overwritten every step and that could cause cascading delays throughout the computer. Since this computer is relatively simple, I opted for hard wiring everything instead.

This diagram illustrates the data transfers that occur throughout the computer. The red arrows depict confirmed hard-wired connections, while the blue arrows would have been routed through a bus. I've decide AR1 is superfluous so I got rid of it. As you can see, each register has at most 2 inputs or 2 outputs going through the bus, so hardwiring is feasible.

Design of the timing circuit

Before the computer can execute its instructions, it needs to perform some operations first.

Transfer the contents of the accumulator to AR2. Dump instruction register and memory address register.
Transfer the program counter to the memory address register. Also, activate the program counter incrementation system in the ALU and transfer the results into program counter +1.
Load the data from memory at the specified address into the instruction register.
Transfer the data from program counter +1 to the program counter. Also, dump the memory address register
Load the last 5 digits of the instruction register into the memory address register. Also, dump program counter +1.
Execution (write accumulator, memory or program counter, read instruction register, memory, AR2)

There needs to be a 100 step delay from the time a memory cell is written (or dumped, if it is pre-dumped) and when it is read, or it may cause cascading delays. The writing process is practically instantaneous, but 100 steps are needed before the correct result can be read if the memory was not cleared to begin with. Of course this point is entirely moot if the computer is running automatically, in which case every step will last at least 100 steps anyway and the prime consideration is to ensure that every step can be performed in 100 steps.

Design of the oscillator

A typical mechanical oscillator is unsatisfactory because it will usually be sending out 2 on signals at once, one from the pressure plate the water is on and the other from the pressure plate waiting to reset.

0%%6%%0%%5%%0%%4
% %
% %
1%%0%%2%%0%%3%%0

This diagram shows a 12 step 6 signal oscillator. At the locations marked 0, there are no pressure plates. A lever operates the mechanism. When the lever is in the ON position, the #%%0 pumps activate, and when the lever is in the OFF position, the 0%%# pumps activate. The oscillator can also be fully automated by using the pressure plates themselves to replace the lever function. The oscillator's power supply also needs to be cut if a halt signal is received from the control unit.

Oscillator Link table

Read accumulator, write AR2, write IR, write MAR
Read PC, write MAR, activate ALU (adder select, C0=1), write PC+1
Read MEM, read MAR. activate decoder, write IR
Read PC+1, write PC, write MAR
Read IR, write MAR, write PC+1
Execution (read IR, turn on control unit)

A dump operation can be performed by telling the memory register to write when its linked inputs are inactive, effectively writing 0s.

Design of the control unit

The control unit can be implemented simply as a 3-8 decoder with appropriately linked pressure plates. The execute signal controlled gear assembly is located at the root of the decoder.

Control unit link table

O0. Read memory, read MAR, activate decoder, write accumulator, select transfer
O1. Read accumulator, write memory, read MAR, activate decoder
O2. Read memory, read MAR, activate decoder, read AR2, Send Add signal to ALU (adder select), write accumulator
O3. Read memory, read MAR, activate decoder, read AR2, Send Subtract signal to ALU (adder select, C0=1, invert input A), write accumulator
O4. Read IR, write PC if ACC7=0
O5. Read memory, read MAR, activate decoder, Send Shift left signal to ALU (SHL select), write accumulator
O6. Read memory, read MAR, activate decoder, Send Shift right signal to ALU (SHR select), write accumulator
O7. Cut power to oscillator.

Adapted from http://docs.google.com/Doc?docid=0AdISzBuNg6ZWZGd0d2t4YjlfMjJ0ejlzc2dnaA&hl=en