Tutorials/Redstone computers

This article examines the design and implementation of computing systems within Minecraft.

Computers facilitate the implementation of ideas which are communicated from humans through programming.

All computer systems have accessible memory and at least one processing unit. During operation, processing units execute instructions stored in the computer's memory.

Most computers are made of redstone, torches, and repeaters leading into sticky pistons or redstone lamps. They are controlled using a series of buttons, levers, pressure plates, etc. Alternatively, in versions such as Pocket Edition, there is no redstone. Using sand/gravel and signs might be a better choice.

Implementations

Computers can be used in many ways from creating a smart house or using it to run a whole city. It could also be used in mini games for example it can store info about who has the high score and calculate if it is possible to beat this score. The uses are almost infinite.

Planning a Redstone computer

When designing a computer ( Redstone or otherwise ) key design decisions that will affect the organization, size and performance of your prospective computer should be made concretely prior to the construction of specific components.

Some things to consider:

• Execution model ( The computer's organization of memory relating to program storage and execution )
• Word-size ( The size of the information blocks which your computer will operate on )
• Instruction Set ( That set of operations which your computer will execute )
• Memory Size ( The amount of data able to be stored in memory )

Having a selection decided upon will provide strong guidance during the design of various components in your computer.

Execution Model

The technique of storing blocks of instructions called programs within memory is what allows computers to perform such a variety of tasks.

The apparatus employed by a computer for storing and retrieving these programs is the computer's Execution Model.

Two of the world's most successful Execution Models, Harvard and von Neumann, run on nearly 100% of the computers available today.

Harvard

The Harvard architecture physically separates the apparatus for retrieving the instructions which makeup an active program from that of the data access apparatus which the program accesses during execution.

Programs written for computers employing a Harvard architecture may perform up-to 100% faster for tasks which access the main memory bus. Note however that certain memory circuitry is necessarily larger for those who select a Harvard architecture.

von Neumann

The von Neumann architecture uses a two-step process to execute instructions. First, memory containing the next instruction is loaded, then the new instruction just loaded is allowed to access this same memory as it executes; using a single memory for both program and data facilitates Meta-Programming technology like compilers and Self modifying Code.

The von Neumann architecture was the first proposed model of computation and almost all real-world computers are von Neumann in nature.

Word sizes

Word-size is a primary factor in a computer's physical size.

In Minecraft, machines from 1-bit all the way up-to 32-bits have been successfully constructed.

Common word-size combinations :

Data	Instruction
4	8
8	8
8	16
16	16

Data-Word

The amount of information a computer can manipulate at any particular time is representative of the computer's Data Word-size.

In Digital Binary, the computer's Data-Word size ( measured in bits ) is equal to the width of or number of channels in the computers main bus.

Data-Words commonly represent integers, or whole numbers encoded as patterns of binary digits.

The maximum sized number representable by a Binary encoded integer is given by 2 ^ Data-Word width in bits - 1.

Some common Integer data sizes are:

Max Representable Number	Number of Bits Required
1 ( 2 ^ 1 - 1 )	1
7 ( 2 ^ 3 - 1 )	3
15 ( 2 ^ 4 - 1 )	4
255 ( 2 ^ 8 - 1 )	8
65535 ( 2 ^ 16 - 1 )	16
4294967295 ( 2 ^ 32 - 1 )	32

Data-Word size also governs the maximum size of numbers which can be processed by a computer's ALU (Arithmetic and Logic Unit).

Instruction-Word

The amount of data a computer needs in order to complete one single instruction is representative of a computers Instruction Word-size.

The Instruction-Word size of a computer is generally a multiple of its Data-Word size, This helps minimize memory misalignment while retrieving instructions during program execution.

Designing a Computer

Instruction-Set-Architecture

States

Memory is a set number of bits. In Minecraft, memory usually holds 8 or 16 bits, though 32 bit memory computers have been successfully built before. Each bit is in one of two possible states: on or off. Memory is a series of these ons and offs, which can be used to perform certain tasks.

Symbols

Real world computers use binary, which is a series of 1s and 0s. "1" means "on" and "0" means "off". In Minecraft, the best representation is redstone dust: having a signal means "1" and no signal means "0". However, depending on how far away the redstone is from the memory storage, it is possible for "0" to be anything from signal strength 0 all the way to 14. You can also design things to make "1" equal anything from signal strength 1 to 15.

Numbers

Our normal decimal system is a number system in base 10. Binary, the number system within computers, is in base 2. To compare, take a look at 2-digit number. In decimal, the left digit is the 10s digit. In binary, it is the 2s digit. For example in decimal, "10" is read as "ten". In binary, "10" is read as "two". There are two commonly-used methods of converting from decimal to binary:

Highest Bit First: This method requires a bit of intuition. Lets use 42 as an example. We first start by looking for the largest exponential of 2 (i.e. 32 [2^5] or 65536 [2^16]). In this case, its 32. We then subtract that number from the number in question. 42-32=10. Also, the very first bit from the left is a "1". We then step down to the next exponential of 2 and see if it is less than or equal to our current number. For this example, the next one is 16. 16 is not less than 10, so the next bit is "0". We keep doing this until the number reaches 0. Whenever the 2 exponential is less than or equal to the number, subtract them and the next bit is "1". If not, the next bit is "0". To continue our example: 8<10-->10-8=2-->"1" 4>2-->"0" 2=2-->2-2=0-->"1" 1>0-->"0" So our final binary representation of 42 is "101010". Fancy.

Lowest Bit First: This method requires no memorization of 2 exponentials. Instead, it repeatedly divides the number by 2, using the quotient as the next number, and the remainder as the binary bit. Keep in mind, though, that this method writes the binary number from right to left, as opposed to the previous method which wrote it from left to right. Let's reuse our example, 42. 42/2=21 r 0 (right most bit is 0) 21/2=10 r 1 (next bit to the left is 1) 10/2=5 r 0 (next bit to the left is 0) 5/2=2 r 1 (next bit to the left is 1) 2/2=1 r 0 (next bit to the left is 0) 1/2=0 r 1 (next bit to the left is 1)

Quotient is 0, so we stop. This gives us our binary number as "101010". Same as the previous method.

Transitions

Instructions

Instructions are essentially functions run by the computer, examples of instructions include:

• Add, subtract, multiply and divide
• Read/Write from RAM/ROM/tertiary memory
• load and unload data into the RAM
• Branching to other parts of the code
• Comparing registers
• Selecting a Logic function (NAND, NOR, NOT etc.)

Instructions can be programmed into the RAM, loaded from ROM or directly activated via a lever or button. Each instruction would have its own specific binary string assigned to it (e.g. 0000=Load data from register 0001=add A and B 1011=Save RAM into teritary memory etc.) and would probably require its own binary to decimal or binary to BCD to decimal encoders and buses to the ALU/registers.

Formalization

Variables

Variables are numbers, strings (sets of characters) or booleans (true or false) stored in RAM for the purposes of running a program. For instance, booleans can be used to keep information for if the program has reached a certain state. The following information needs to be kept about a variable: Its name, type (number, string or boolean), and value. A variable's value can, as its name suggests, change. Operations can be done on variables. Variables are created while running the program and deleted from memory once the program closes. When a program is re-opened, the variables are re-created. It is the same in Minecraft.

Hierarchies

Memory

Memory is where data for programs is kept. It is volatile (It is deleted when the computer is turned off) and is used for the program to store data. For example, in a program which counts up from 1, 1 is saved to memory, 1 is loaded from memory and 1 is added to it to get 2.

Semantics

Data

Data is the information being processed by the computer and is represented using binary.

Machine-Architecture

Data paths

Arithmetic Logic Unit

The ALU is one of the most important components in a computer, both in real life and in Minecraft. First, you must choose the functions you want to be able to achieve. Most often, those are addition, subtraction and a set of logic options such as AND, OR, NAND and the likes. You must then build the unit with all the logic gates and math functions you want and a way to choose which one's output to display.

Busing

Busing is what allows the components of your computer to communicate with each other. A bus can be created by using redstone wiring to connect your computer's ALU, RAM, ROM, CPU, and registers together so that they can send data between each other. It is usually important to plan where to build the components of your computer so that you won't have to create busing wires too long, or even worse, have no space to create busing, in which case you can remove the offending component and rebuild it an appropriate location, or use a mod like WorldEdit to move the component somewhere else.

Storage

Register

Random Access Memory

Random Access Memory also know as RAM is a kind of memory used by programs and is volatile. Most often, making it volatile has no use in Minecraft, so the easiest way to make some is to use d-flip flops and to add a reading and writing function. Making one is simple. You can make 1 flip-flop and then just stack it for as long as needed, with one block taken of each byte. See the following plan for help:

(redstone schematic to be done) Reference the picture if not sure (click on it to get it larger) r=wire p=repeater b=block t=torch on side of block 0=air

Layer 1
00trb00
rpb0tr0

Layer 2
0b0t00b
tbbbbtb

Layer 3
0r0t00r
0rprr0r

Tertiary memory

Tertiary memory is used to compactly store large amounts of data at the expense of speed. This kind of memory consists of the database, where all the data is actually stored, and a physical mechanism, usually a robotic arm, that must physically move around the database to fetch data. For this reason, it is extremely slow, and is only used for information that is rarely accessed.

In the latest versions of Minecraft, it may be possible to create tertiary memory with sticky pistons combined with slime blocks, which can create "ships" that move around, and presumably store a redstone component that can extract, read, and write from a wall of conducting and non-conducting blocks.

Machine State

Program Counter

The program counter is used to keep track of which line of code the computer should be reading from. During each clock cycle, the decoder will access this counter in order to fetch the next instruction to be executed. Some instructions will access a different amount of data than another, or no data at all, so the decoder will in turn increment the program counter by the appropriate amount to the next instruction. The counter is also used by jump instructions to control program flow.

In real life, this counter isn't a component by itself, and is simply a register right next to all the other ones. In minecraft, however, it may be less confusing to create a separate register apart from the others to store program counter data.

Control paths

Storage

Program Memory

Program memory is, most basically, ROM (Read-only Memory). ROM is most often used to perform a series of task remotely (such as a program, hence the name). It can be made to be used on user control (as in the picture) or with a clock and sufficient delay between each line so 2 aren't on at the same time. One of the simplest and most efficient design is the one in the picture, which may or may not be coupled with a decoder. It can be enlarged easily, which is another advantage.

Machine State

Program Counter

Clock

Clocks are used to synchronize components or to time them. In most (Minecraft) cases, it is possible to avoid the use of one but sometimes it is necessary for the computer's functioning. It can be either made from redstone torches in basically a line/circle of NOT gates (an odd number is recommended or your output will have to be NOT'ed), or from repeaters, as in the picture above.

Tips

• You may want to use mods like WorldEdit
• If you're in survival and don't have any repeaters you can use two redstone torches
• Color code your computer (use blue wool for RAM yellow for the ALU etc.)