User:Larix/MPL/7

At long last, i explored the potential of switching high-speed minecarts' path via doors and found that this doctrine offers very attractive options for core operations like decoding and arithmetics, requiring very few mechanisms, no power and only a single minecart per function, while the high operation speeds mean the "linear" evaluations still execute at impressively high speeds.

The atom of cart+door-logic: the door switch

As noted in the article on minecarts, paths of high-speed minecarts can be switched by offering them a track corner backed by a door or other switchable building. If the building is closed, the cart takes the corner. If the building is open, the cart's speed carries it over the corner and through the opening:

-	>	═	═	╗	D	-	>	1
				║

Note: in all diagrams, some track should be engraved under installed doors. The exact configuration is irrelevant (gets ignored at those speeds anyway), but i've seen a case or two where plain floor underneath the doors seemed to cause misfunctions.

The cart must move at speeds in excess of 50.000 to actually switch, slower carts will follow the corner in every case.

A fast cart can derail over a corner if there's no blocking building behind it. If the door D is open (input signal is on/1), the cart continues in a straight line. If the door is closed (input signal off/0), the straight path is blocked and the cart takes the corner.

Benefits and drawbacks

The advantages of this door switch are:

• takes no power to operate, only signals
• the "gate" reacts instantly to changing input when a door is used for switching
• evaluation time is very short: a cart passes through the array in less than five steps and both "on" and "off" output are reached at nearly the same time.

The disadvantages are:

• depending on layout, a cart could end up in the door jamb while the door tries to close. This results in the door staying wedged open. Proper timing of input acquisition vs. evaluation can completely avoid this.
• overall space consumption per gate is pretty large, because most paths require walls to keep carts contained
• speeds well in excess of what rollers can do are required for operation. That's fortunately easy enough to solve via impulse ramps. Of coure, due to the high operation speeds, dwarfs should be kept out of active circuits.
• high speeds can make picking up the resulting outputs difficult: very fast carts can skip past output pressure plates without touching them. This can be solved by using the checkpoint effect.

Designs

What makes Cart and Door Logic (CDL from here on) so interesting is that it can't just switch a cart coming from one input direction to one of two output paths. It can also switch carts coming from one of two possible input directions to one of four possible outputs:

			I	1
				║
				╚	═		O	1	'
I	2	═	╗	D	═		O	2
			║	║
	O	2	'	O	1

The cart comes from one of the two input directions I1 and I2. If the door D is open, the cart passes through in a straight line and leaves on path O1 or O2. If the door is shut, the cart is diverted and takes the path O1' or O2'.

This fully granular splitting of the inputs to individual outputs means any binary logic gate can be built with two linked doors. Notably, an XOR gate built only from doors will look like this:

╚	═	╗	#
A	#	╚	╗	#
╚	╗	B	╚	═	N	X	O	R
#	╚	╗	#
	#	║
	X	O	R

With the same position of doors, any other logic-gate function can be derived, it only takes different pathing on the output side behind the doors.

Making use of the full spread, decoding of a multi-bit input to single outputs - e.g. when choosing a function specified by an encoded command or addressing a memory location - can be done at relatively low cost in mechanisms and furniture, while offering a fairly short runtime of three to five steps per "gate"/bit consulted.

As a very attractive option, this doctrine can be used to make a powerless full adder with short runtime and very low mechanism count:

╚	═	╗	#
A	#	╚	═	╗	#
╚	╗	B	1	╚	╗	#
#	╚	╗	#	#	╚	═	╗	#
	#	╚	═	╗	C	2	╚	S	'
		#		╚	╗	#	#
				#	S

Inputs A and B are evaluated. If both are on, a carry is produced (1) and sent to the next adder cell. After the "generated" carry has been tested for, the "equal" (northeastern branch) and "inequal" (southwestern branch) results for the A/B comparison are collected and checked from both sides against the carry-in C. If A and B are equal while C is on, or if A and B are inequal and C is off, a sum is generated (S). If A and B are inequal and C is on, a "propagated" carry (2) is sent to the next adder cell. If the sum is not generated, a "non-sum" output can be read at S', e.g. to actively clear a bit at the register to which the result is written.

While this is a ripple-carry adder, the evaluation proceeds at less than ten steps per added bit. If the starting speed is at the limit of what's reachable by ramps, a twelve-bit addition takes less than 100 steps for the evaluation.

What i find particularly interesting about this adder is that it does the complete addition with three switchable doors per bit. Doors A and B are only linked to their input(s), door C is generally linked twice, to both the generated and propagated carry plates of the previous bit. Depending on the design of the components the adder outputs to, a single sum plate per bit could be sufficient, but to make best use of the high operation speed, it may be better to take both the sum and the negative-sum output.

Afterthoughts

1. I've sketched a few more designs; incrementation, derivation of the binary complement and comparison should be quite feasible in CDL - fast and with few mechanisms. Using weight-calibrated pressure plates and providing different-weight evaluation carts could offer deriving very different functions from the same overall device: the adder should be able to also do bitwise AND and bitwise XOR without changing anything in the switching and output logic, merely by picking different carts to run the course. Input selection would also allow doing direct copy from source to target and bitwise OR.

2. To provide carts with sufficient speed for proper and fast evaluation, a simple impulse-ramp circuit is recommended:

		#							#
#	╔	╗	R				#	╔	╗
#	▲	║					#	╗	║
#	▲	║					#	╗	║
#	▲	║					#	╗	║
#	╚	╝	#				#	╚	╝	#
#	D						#	║

D: door opened to start an evaluation/operation run. R: return path feeding the cart back into the holding coil. Carts should only return once D is shut again, or you get multiple runs.

Just enough ramps in a row that there's a full step of acceleration on every cycle. The cycle takes a while to rev up to full speed, but once it's at full speed, it holds that speed for an indefinite time, responds to opening of the door in at most five steps and the speed loss in my twelve-bit adder was compensated in short order.

3. Carts in these circuits should preferably move at speeds well in excess of one tile per step. Making sure that a cart actually touches an output pressure plate cannot be guaranteed by spacing - which tiles are actually visited depends on distances travelled and speed (largely influenced by the number of turns a cart takes, which varies). However, the checkpoint effect can be used: when moving off a ramp to a different tile, a cart will always touch the tile past the ramp and spend exactly one step there, regardless of speed. I put an impulse ramp before every pressure plate in the adder, which increases space and time consumption a bit, but there's no reliable alternative. The under 100 steps for a twelve-bit addition include that regulation cost.

4. It should be evident that a door can bifurcate as many input paths as it has "faces", i.e. four (five if going very crazy and including carts dropped from above). I've designed a layout for a three-in-six-out switch that should be useful to reduce door/mechanism count in large decoders, but haven't tested it yet. Four-in-eight-out switches are likely prohibitively spacious.

Link

Video of the twelve-bit full adder: http://mkv25.net/dfma/movie-2716-powerlessminecartadder