Computer science: TestAS practice testlets

Digital circuits process signals that have only two states, represented as 1 (true, high voltage) and 0 (false, low voltage). Logic gates combine input signals according to simple rules. An AND gate outputs 1 only if all its inputs are 1. An OR gate outputs 1 if at least one input is 1. A NOT gate, or inverter, reverses its single input. A NAND gate is an AND gate followed by NOT: it outputs 0 only if all inputs are 1. A NOR gate outputs 1 only if all inputs are 0. An exclusive OR (XOR) gate outputs 1 if exactly one of its two inputs is 1.

AND: A·B OR: A + B NOT: Ā XOR: 1 if A ≠ B

The behaviour of a gate or a network of gates is described by a truth table, which lists the output for every combination of inputs. With n inputs, there are 2 to the power of n combinations. Networks are evaluated step by step, working from the inputs towards the output and noting the value at each intermediate point.

NAND and NOR gates are called universal, because any other logic function can be built from them alone; chip manufacturers therefore often use them as basic building blocks. Logic networks are found in control systems, safety interlocks and, in vast numbers, in computer processors.

Logic expressions can be simplified with Boolean algebra, which reduces the number of gates needed. For example, A·B + A·B̄ simplifies to A, since the output then depends only on A.

In practice, engineers also consider what happens if a sensor fails: alarm inputs are often wired so that a broken wire is treated like an open door.

A security company designs the control logic for a building alarm. There are four input signals: D = 1 when a door is open, W = 1 when a window is open, A = 1 when the system is armed, and P = 1 when the panic button is pressed. The siren S is controlled by the network below. It first combines the door and window signals with an OR gate, then combines the result with the armed signal in an AND gate, and finally combines this with the panic button in a second OR gate.

Many technical systems behave differently depending on what has happened before. A traffic light, a lift or a vending machine must remember its current situation, its state, and respond to inputs by changing to another state and producing outputs. Such systems are modelled as finite-state machines: they have a finite number of states, one of which is the current state, and a set of transitions that specify, for each state and input, the next state and any output.

A state machine is described by a state diagram, in which states are circles and transitions are arrows labelled with the input that triggers them, or by a transition table. To trace the behaviour of a machine, one starts in the initial state and applies the inputs one after another, noting each new state and output. Inputs for which no transition is defined are usually ignored, so the machine stays in its current state.

State machines are used to design control software, communication protocols and user interfaces, because they make every possible situation explicit. Engineers check a design for unreachable states, which can never occur, and for situations without a defined response, which could cause the system to hang.

Timing diagrams show how signals change over time and are used to check that a machine responds correctly to sequences of inputs. Each signal is drawn as a line that is high or low, and changes of state happen at defined moments, for example at the rising edge of a clock signal.

Real vending machines have many more states, for example for selecting a product, for running out of change or for a jammed bottle, but the principle is the same.

A simple drinks machine sells a bottle for 1 euro and accepts only 50-cent and 1-euro coins. It has three states: S0 (no credit), S50 (50 cents credit) and a "dispense" action. If more than 1 euro is inserted, it returns the excess. The inputs are c50 (a 50-cent coin), c100 (a 1-euro coin) and R (the return button, which gives back any credit).