Revision: Paper 1 topics 1 to 3

Why computers use binary

A computer is made of billions of tiny switches called transistors. Each switch is either off or on.

We write off as 0 and on as 1. A number system with only two digits is called binary.

One binary digit is a bit. Eight bits together make a byte.

Every extra bit doubles the number of different patterns you can make.

Place value: denary and binary

Denary is our everyday number system. It has ten digits, 0 to 9, and each column is worth 10 times the column to its right.

Binary works the same way, but each column is worth 2 times the column to its right.

For 8 bits the column values, from left to right, are 128, 64, 32, 16, 8, 4, 2, 1.

To turn binary into denary, add up the column values that have a 1 under them.

Try the toy: switch on the 128 bit. What happens to the denary value? Now make 255.

There is something to try for this step in the IGCSE library.

Denary to binary

Start at the left column, 128. Ask: does 128 fit into my number?

If it fits, write 1 and take 128 away. If it does not fit, write 0.

Move to the next column and repeat with what is left. Stop when you reach the 1 column.

Always write all 8 bits, including the 0s at the front.

The biggest number n bits can hold

With n bits you get 2ⁿ patterns. One of those patterns is 0.

So the biggest number is one less than the number of patterns: 2ⁿ − 1.

8 bits hold 0 to 255. 16 bits hold 0 to 65,535.

A register is a small store inside the processor. An 8-bit register cannot hold anything bigger than 255.

Hexadecimal: base 16

Hexadecimal (hex) has sixteen digits. It uses 0 to 9, then the letters A to F for 10 to 15.

Each hex column is worth 16 times the column to its right. Two-digit hex has columns 16 and 1. Three digits add a 256 column.

One hex digit stands for exactly four bits. Four bits are called a nibble.

Hex to denary and denary to hex

Hex to denary: multiply each digit by its column value, then add. Change letters to numbers first (B = 11, F = 15).

Denary to hex: divide by 16. The whole-number answer is the left digit. The remainder is the right digit.

Change any digit from 10 to 15 into its letter.

Binary and hex using nibbles

Binary to hex: split the binary into groups of 4 bits, starting from the right. Change each group into one hex digit.

Hex to binary: change each hex digit into its 4-bit nibble. Write them side by side.

Each nibble uses the small column values 8, 4, 2, 1. This keeps the sums easy.

The fastest route between denary and hex is often through binary.

Why hexadecimal is used

Computers do not use hex. Inside, everything is still binary. Hex is for people.

Hex is shorter: 8 bits become 2 hex digits. It is easier to read, remember and type.

People make fewer mistakes copying hex than long strings of 0s and 1s.

It converts to binary very easily, because each digit is one nibble.

Adding binary: the four rules

You add binary in columns, from right to left, like denary addition.

In binary, 1 + 1 makes 2, and 2 is written 10. So you write 0 and carry 1 to the next column.

If a column has 1 + 1 plus a carry of 1, the total is 3. Three is 11: write 1 and carry 1.

Try the toy: it starts with 91 + 54. Press Step to add one column at a time and watch where each carry goes. Then press Overflow example.

There is something to try for this step in the IGCSE library.

A full 8-bit addition

Write the two numbers one under the other, with the column values on top.

Write each carry above the next column on the left. Then add that column, including the carry.

Check your answer by changing everything to denary.

Overflow

An 8-bit register can hold 0 to 255. Sometimes an addition gives more than 255.

Then the last column makes a carry that has nowhere to go. It would need a 9th bit.

This is called an overflow error. The 9th bit is lost, so the stored answer is wrong.

The processor sets an overflow flag so the program can deal with it.

Logical left shift

A logical shift moves every bit left or right by a number of places.

In a left shift, bits fall off the left end and are lost. 0s fill the gaps on the right.

Each place shifted left multiplies the number by 2. Two places is × 4. Three places is × 8.

If a 1 falls off the left end, the answer is wrong. This is a kind of overflow.

Try the toy: load 22 (00010110), choose 2 places and press Shift left. Then load 53 (00110101) and shift it left 3 places. Which answer is wrong?

There is something to try for this step in the IGCSE library.

Logical right shift

In a right shift, bits fall off the right end and are lost. 0s fill the gaps on the left.

Each place shifted right divides the number by 2. Two places is ÷ 4. Three places is ÷ 8.

If a 1 falls off the right end, the remainder is lost. The answer is rounded down, so accuracy is lost.

Two's complement: negative numbers

So far 8 bits only held positive numbers, 0 to 255. Two's complement is a way to store negative numbers too.

The only change: the leftmost column is worth −128 instead of 128. All other columns stay the same.

If the leftmost bit is 0, the number is positive. If it is 1, the number is negative.

8-bit two's complement holds −128 to +127.

Try the toy: press Smallest (−128) so only the −128 bit is on. Then tap the 64 bit. Watch the value climb towards 0.

There is something to try for this step in the IGCSE library.

Denary to two's complement

Positive number: write it in normal 8-bit binary. The leftmost bit will be 0.

Negative number, method 1: write the positive version in binary. Flip every bit (0 becomes 1, 1 becomes 0). Then add 1.

Negative number, method 2: start with −128. Work out what you must add to reach your number. Put that in the other 7 columns.

Use one method and check with the other, or check by adding the column values.

Why errors happen

Bits travel as electrical pulses, light or radio waves. These can be disturbed on the way.

Interference is unwanted signal from outside, such as from a motor, a microwave oven or lightning.

Because of interference, data can suffer data loss (bits go missing), data gain (extra bits appear) or data change (a 1 becomes a 0, or a 0 becomes a 1).

Parity check: odd and even

A parity check adds one extra bit, the parity bit, to each byte. Usually it is the leftmost bit.

In even parity, the total number of 1s in the byte must be even. In odd parity, the total must be odd.

The sender and receiver agree the type first. The receiver counts the 1s. If the count is wrong, there is an error.

There is something to try for this step in the IGCSE library.

Parity byte and parity block

To find which bit is wrong, we send a block of bytes, each with its own parity bit.

Then we add a parity byte at the end. Each bit of the parity byte gives parity for one column.

If one bit flips, one row fails and one column fails. The wrong bit is where they cross, so the receiver can even correct it.

Checksum

A checksum is a value calculated from all the data in a block, using an agreed method.

The sender calculates the checksum and sends it with the data.

The receiver calculates the checksum again from the data it received. If the two values match, the data is probably correct. If not, it asks for the data again.

Echo check

In an echo check, the receiver sends a copy of the data straight back to the sender.

The sender compares the copy with the original. If they are the same, the data arrived correctly. If not, the sender sends it again.

Check digits

A check digit is an extra digit added to the end of a number, such as an ISBN (book number) or a supermarket barcode.

It is calculated from the other digits. It catches data entry errors: a digit typed wrongly, or two digits swapped (transposed).

This is different from parity and checksums. Those catch errors in transmission; a check digit catches human errors when a number is typed or scanned.

There is something to try for this step in the IGCSE library.

Automatic repeat query (ARQ)

ARQ uses an error check (such as a checksum) plus messages back to the sender.

If the data arrives correctly, the receiver sends a positive acknowledgement. If it finds an error, it sends a negative acknowledgement and the sender sends the data again.

The sender also starts a timeout: a set time to wait. If no acknowledgement arrives before the time runs out, the sender re-sends the data automatically.

The CPU and the microprocessor

The CPU (central processing unit) is the part of the computer that processes instructions and data. It carries out the instructions of every program.

It does this by fetching an instruction from memory, decoding it, then executing it. Then it repeats, billions of times a second.

A microprocessor is a CPU built as an integrated circuit on a single chip. An integrated circuit is a whole electronic circuit made on one small piece of silicon.

Von Neumann architecture

Most computers follow the von Neumann architecture. Its key idea is the stored program: instructions and data are both stored in the same main memory.

The CPU has a control unit (CU). The CU manages the fetch–decode–execute cycle. It decodes instructions and sends control signals to the other parts.

The CPU has an arithmetic logic unit (ALU). The ALU does calculations (such as add and subtract) and logic operations (such as comparing two numbers).

The CPU also has registers: very small, very fast stores inside the CPU. The CPU is joined to memory by three buses (sets of wires).

There is a diagram for this step in the IGCSE library.

The five registers

A register holds one item at a time: an address, an instruction or a piece of data.

An address is the number of a location in memory, like a locker number in a school corridor.

The three buses

The address bus carries addresses from the CPU (the MAR) to memory. It is one-way (unidirectional), because only the CPU chooses addresses.

The data bus carries data and instructions between the CPU (the MDR) and memory. It is two-way (bidirectional), because data is both read and written.

The control bus carries control signals from the control unit, such as 'read', 'write' and the clock signal. It is two-way, because devices also send signals back.

The fetch–decode–execute cycle

Every instruction goes through the same three stages. Learn the fetch stage in order: it is worth most marks.

Fetch: the address in the PC is copied to the MAR, using the address bus. The PC is incremented (1 is added), so it points to the next instruction. The instruction at that address is sent along the data bus to the MDR. It is then copied from the MDR to the CIR.

Decode: the control unit decodes the instruction in the CIR. It works out what the instruction means and what needs to happen.

Execute: the instruction is carried out. The control unit sends signals on the control bus. If there is a calculation, the ALU does it and the result goes in the ACC. Then the cycle starts again.

There is something to try for this step in the IGCSE library.

The instruction set

An instruction set is the list of all the instructions (commands) that a particular CPU can understand and carry out.

Each instruction is a binary code, called machine code. Examples are load, add, store, compare and jump.

The CU decodes instructions using this set. Different CPU families have different instruction sets.

Cores, cache and clock speed

Clock speed is the number of fetch–decode–execute cycles the CPU can do per second, measured in hertz (Hz). A 3.5 GHz CPU has 3,500,000,000 clock ticks per second. Higher clock speed means more instructions per second.

Cache is a small amount of very fast memory inside or next to the CPU. It stores instructions and data that are used often, so the CPU does not have to wait for slower RAM. More cache means fewer slow trips to RAM.

A core is a complete processing unit (with its own ALU, CU and registers). A quad-core CPU has four cores, so it can process four instructions at the same time.

Embedded systems

An embedded system is a small computer system built inside a larger device, to do one dedicated job.

It uses a microprocessor (or a microcontroller) and usually runs one fixed program stored in ROM.

A general-purpose computer, like a laptop, can run many different programs and do many jobs.