Data in Depth

Count the momos on a plate and you use ten digits, 0 to 9. After 9 you have run out, so you write 10: one ten and no ones. That is the decimal number system. A number system is a way of writing numbers with a fixed set of digits and a rule for what each place is worth.

The number of digits a system uses is its base, also called its radix. Decimal has base 10. In Grades 6 and 7 you counted in binary, base 2, with only 0 and 1. Two more bases are used in computing:

• Octal, base 8, with the eight digits 0 to 7.
• Hexadecimal (often just hex), base 16. It needs sixteen digits, so after 0 to 9 it uses the letters A to F for the values 10 to 15.

Place values are powers of the base

In every one of these systems, a digit’s worth depends on its place. The place on the right is worth 1; each place to the left is worth base times the place before it. So the places are the powers of the base: base⁰ = 1, base¹, base², base³ and so on.

So the decimal number 719 is

$$719 = 7 \times 10^2 + 1 \times 10^1 + 9 \times 10^0 = 700 + 10 + 9$$

The same digits mean different numbers in different bases: 101 is a hundred and one in decimal, but five in binary, sixty-five in octal and two hundred and fifty-seven in hex. So when bases are mixed, the base is written as a small number after the brackets: (101)₂, (101)₈, (101)₁₀, (101)₁₆. Programs write it in front instead: Python reads 0b101 as binary, 0o101 as octal and 0x101 as hex.

To change a number in any base into decimal, do what you did for binary in Grade 6: write the place values over the digits, multiply each digit by its place value, and add.

In Grade 7 you changed a number into binary by keeping halving and reading the remainders from the bottom up. The same method works for every base: keep dividing by the base.

1. Divide the decimal number by the base. Write down the remainder.
2. Divide the quotient (the answer) by the base again, and write down that remainder.
3. Carry on until the quotient is 0.
4. Read the remainders from the last to the first (bottom to top). In hex, write a remainder of 10 to 15 as A to F.

Why it works: the first remainder is what is left over after taking out every whole lot of the base, which is exactly the ones digit. Dividing then moves every digit one place to the right, so the next remainder is the next digit, and so on. The digits come out right-hand end first, so you read them upwards.

Python has these conversions built in. bin(), oct() and hex() give a number in binary, octal and hex as text, with the prefixes you saw above, and int() with a second number reads text in that base. Press Run.

print(bin(46), oct(345), hex(540))print(int("10011", 2), int("157", 8), int("1AC", 16))

0b101110 0o531 0x21c19 111 428

Here is the dividing method written out, so you can see that it is just Grade 8’s // and % in a loop. Change n and base and run it again.

digits = "0123456789ABCDEF"n = 540base = 16answer = ""while n > 0:    r = n % base    answer = digits[r] + answer    n = n // baseprint(answer)

21C

n % base is the remainder and n // base the quotient. Each new digit goes on the front of answer, so the digits end up in the right order without reading anything upwards. digits[r] picks the character at position r of the text: position 12 is C.

Why do computer people bother with hex and octal at all? Because they are shorthand for binary.

Look at the numbers 16 and 8. 16 = 2⁴, so one hex digit holds exactly what four bits hold: from 0000 (0) to 1111 (F). And 8 = 2³, so one octal digit is exactly three bits: 000 (0) to 111 (7). That means you can change between binary and hex, or binary and octal, without going through decimal at all, a few bits at a time.

Binary to hex: split the bits into groups of four, starting from the right. If the last group on the left is short, fill it with 0s in front (they change nothing). Write each group as one hex digit.

Hex to binary: write each hex digit as four bits.

Binary to octal, octal to binary: the same, with groups of three.

Where you will see hex

A byte is 8 bits, which is exactly two hex digits: 00 to FF (0 to 255). Hex is so much shorter than binary, and so much easier to split into bytes than decimal, that it is used wherever people need to read the bytes themselves:

• Colors on the web. In Grade 8 you wrote #8b1a1a for a dark red. Now you can read it: three bytes in hex, red 8B = 8 × 16 + 11 = 139, green 1A = 26, blue 1A = 26. #FFFFFF is white, all three at 255.
• Unicode. Characters are numbered in hex: न is U+0928 (below).
• Network cards. Every Wi-Fi and network card has a MAC address of six bytes, written in hex like 3C:22:FB:7A:91:0E. You will meet it in Unit 5.
• Memory addresses and error codes. When a program crashes, the message often names a place in memory or an error number in hex, such as 0x80070005.

Adding

You learned to add in binary in Grade 7 Grade 7: Adding in binary: add columns from the right, with 1 + 1 = 10 (write 0, carry 1) and 1 + 1 + 1 = 11 (write 1, carry 1). Exam questions often add numbers of different lengths: line them up on the right, as you would in decimal.

Subtracting

Subtraction also works in columns from the right, as in decimal. Three columns are easy: 0 − 0 = 0, 1 − 0 = 1, 1 − 1 = 0. The hard one is 0 − 1: you must borrow from the next column on the left.

In decimal, a borrowed 1 from the tens is worth ten ones. In binary, a borrowed 1 from the next column is worth two of this column. So 0 − 1 becomes (2 − 1) = 1, and the column you borrowed from goes down by 1.

Multiplying

Multiplying is the easiest of all, because there are only two times tables: anything × 0 = 0, and anything × 1 = itself. So long multiplication in binary is just copying and shifting: for each 1 in the bottom number, write the top number, moved left one place for each place along; then add.

Notice the shifted line: moving a binary number one place left (putting a 0 on the right) doubles it, just as putting a 0 on the right of a decimal number multiplies it by ten. Processors use this all the time: shifting bits is one of the fastest things they do.

A thermometer in Jumla in January reads −10 °C. A shop’s account can go below zero. A game character can walk left, a negative step. A computer must store negative numbers too, but it has no minus sign: only bits.

A sign bit

The first idea is to use the left-hand bit of a byte as a sign: 0 for plus, 1 for minus, and the other 7 bits for the size. This is called sign and magnitude. +5 is 00000101 and −5 is 10000101.

It is easy to read, but it has two problems. There are two zeros, 00000000 (+0) and 10000000 (−0). Worse, ordinary binary addition gives wrong answers: 5 + (−5) should be 0, but 00000101 + 10000101 = 10001010, which reads as −10. A computer using it would need separate circuits for adding and subtracting.

Two’s complement

Nearly every computer today uses a cleverer way, called two’s complement. In an 8-bit two’s complement number, the left-hand bit is worth −128 instead of +128. All the others keep their usual values.

So 11111011 is −128 + 64 + 32 + 16 + 8 + 2 + 1 = −128 + 123 = −5. Any number with a 1 on the left is negative (no other bits can add up to 128), and the numbers run from 10000000 = −128 to 01111111 = +127.

To write a negative number in two’s complement, there is a quick method:

1. Write the positive number in 8 bits.
2. Flip every bit: 0 becomes 1 and 1 becomes 0.
3. Add 1.

The same three steps also turn a negative number back into its positive: flip 11100010 to 00011101, add 1, and you get 00011110, which is 30.

Subtracting by adding

Here is why two’s complement won. To work out 45 − 30, a computer works out 45 + (−30) with the very same adding circuit it uses for every sum (the adder of Unit 1). No separate subtracting circuit is needed.

Now you can see why the Gangnam Style view counter of Unit 1 stopped at 2,147,483,647. A signed 32-bit number is two’s complement: its left bit is worth −2³¹, so its biggest value is a 0 followed by 31 ones, 2³¹ − 1. One more view would have carried into the left bit and turned the count into −2,147,483,648.

In Grade 7 you saw that every character is stored as a number, its code point in Unicode, and that UTF-8 stores English letters in 1 byte each and Devanagari in 3 Grade 7: Unicode: every script in the world. Now you can see how.

Code points in hex

Unicode’s own charts write code points in hex, after U+: A is U+0041 (65), न is U+0928 (2344), 😀 is U+1F600. Hex is used because the charts are laid out in columns of sixteen: the last hex digit gives the place in the column, and the digits before it name the column. The Devanagari block runs from U+0900 to U+097F: 128 codes, eight columns of sixteen. So a hex code point shows at a glance which script a character belongs to: every code from U+0900 to U+097F is Devanagari (Bengali comes next, from U+0980).

How UTF-8 packs a code point into bytes

UTF-8 has to solve a puzzle. A code point can be anything from 0 to U+10FFFF (1,114,111), so some need 1 byte and some need 4. But when a phone reads a stream of bytes, how does it know where one character ends and the next begins?

The answer is in the first few bits of every byte:

• A byte starting 0 is a whole character by itself: plain ASCII, so an English file in ASCII is already UTF-8.
• A byte starting 110, 1110 or 11110 starts a character, and its number of 1s says how many bytes the character has: two, three or four.
• A byte starting 10 is a continuation: it carries six more bits of the character already begun.

So the code point’s bits are cut into pieces and poured into the x’s, as Figure 2.1 shows for न.

Python can show you the bytes. encode("utf-8") turns text into its bytes, and len() counts them:

word = "नमस्ते"print(len(word), "code points")print(len(word.encode("utf-8")), "bytes")print("न".encode("utf-8"))

6 code points18 bytesb'\xe0\xa4\xa8'

b'\xe0\xa4\xa8' is Python’s way of writing three bytes: \x and then each byte in hex, E0, A4 and A8, exactly as in Figure 2.1.

One letter, many bytes

What you see as one Nepali letter is often several code points (Grade 7: क्ष is क, the halant ◌्, ष). Each Devanagari code point takes 3 bytes, so a single syllable such as क्षि is 4 code points, क ◌् ष ◌ि, and 12 bytes.

Pictures

In Grade 7 each pixel took 3 bytes, one each for red, green and blue. That is not the only choice. The number of bits used for each pixel is called the color depth (or bit depth), and it decides how many colors the picture can have:

The size of the pixels, before any compression, is

$$\text{size in bits} = \text{width} \times \text{height} \times \text{color depth}$$

Then divide by 8 for bytes, and by 1,024 for each step to KB and MB.

Sound

Sound is stored as samples (Grade 7), so its size depends on four things: how many samples a second (the sample rate), how many bits each sample takes (the bit depth), how many channels (1 for mono, 2 for stereo: left and right), and how long it lasts.

$$\text{size in bits} = \text{sample rate} \times \text{bit depth} \times \text{channels} \times \text{seconds}$$

A real file is a little bigger than these sums, because it also holds a header and metadata: the picture’s width and height or the sound’s sample rate, so it can be read back, and often a date, a place, a camera’s name or a song’s title Grade 8: Metadata: data about data. These are usually only a few kilobytes.

So a song is about 40 MB uncompressed, and a phone photo about 34 MB. Yet the files on a phone are about 4 MB and 3 MB. They have been compressed: stored in fewer bits by a program that finds a shorter way to say the same thing. Compressing a file makes it quicker to send, cheaper on a data pack, and lets a phone hold ten times as many.

How much smaller a file gets is its compression ratio: the original size ÷ the compressed size. A 40 MB song stored in 4 MB has been compressed 10 times, a ratio of 10 : 1.

As Grade 8 said Grade 8: Choosing a format, there are two families:

• Lossless compression keeps every bit. Decompress the file, and you get back exactly the original.
• Lossy compression throws away detail that people won’t notice, so it can squeeze far more, but the lost detail is gone for good.

Lossless: repeated runs

Look at the sky in a photo of the Himalaya: hundreds of pixels side by side, all the same blue. Listing “blue, blue, blue, blue…” wastes space. Better to say “200 × blue”. This is run-length encoding (RLE): each run of the same value is stored as a count and the value once.

RLE is simple, and it shows the big truth about every lossless method: it works by finding a pattern. Where there is no pattern, there is nothing to squeeze. Here is RLE in Python: change the text and run it.

text = "WWWWWWBBBWWWW"encoded = ""count = 1for i in range(1, len(text) + 1):    if i < len(text) and text[i] == text[i - 1]:        count = count + 1    else:        encoded = encoded + str(count) + text[i - 1] + " "        count = 1print(encoded)

6W 3B 4W

text[i] is the character at position i (you will do much more with text in Unit 3). The loop compares each character with the one before it: while they match, the count goes up; when they differ, or the text ends, the run is written out and a new count starts.

Lossless: repeats anywhere (the idea inside ZIP)

Runs are only one kind of pattern. Text is full of others: a word or a phrase that came before, coming again. The ZIP files you download, and the PNG pictures of Grade 8, both use a cleverer idea: whenever a piece has appeared before, store a pointer back to it instead: “go back 34 characters and copy 18”.

ZIP and PNG then take a second step: letters and pointers that come up often get shorter codes, and rare ones longer codes. Morse code works the same way: E, the most common letter in English, is a single dot, and a rare Q is four signals. Together the two steps often shrink a text file to a third of its size or less, and get back every character exactly.

Lossy: what the eye misses (JPEG)

A photo has a different problem. Its pixels are almost never exactly the same: the sky changes color very slightly from pixel to pixel, so lossless methods find few runs or repeats, and a PNG of a photo stays big. So JPEG, which you met in Grade 8 Grade 8: Pixels and kilobytes, uses what is known about eyes:

1. Color is kept with less detail than brightness. Your eyes see fine detail in light and dark much better than in color. So a JPEG usually keeps the brightness of every pixel, but only one color for each 2 × 2 square of four pixels.
2. The picture is cut into blocks of 8 × 8 pixels, and each block is described as a mix of smooth patterns, from a plain block to fine stripes (the discrete cosine transform of Grade 8’s fact).
3. The finest patterns are thrown away or kept only roughly, because eyes hardly notice them. The quality setting decides how much: lower quality, rougher patterns, smaller file.
4. What is left is squeezed losslessly, with Huffman’s codes.

Push the quality too low, and the 8 × 8 blocks start to show, and smudges appear round sharp edges: the compression artifacts of Grade 8.

Lossy: what the ear misses (MP3)

MP3 does the same for sound, using what is known about ears:

• Sounds too high or too quiet to hear are dropped. People hear from about 20 to 20,000 vibrations a second, and quiet sounds only in the middle of that range.
• Loud sounds hide quiet ones near them in pitch. Next to a loud drum beat, a quiet note just a little higher can’t be heard at all; for a short moment after the beat, nothing quiet is heard either. This is called masking, and it is the biggest trick: whatever is masked isn’t stored.

Masking is what Karlheinz Brandenburg’s team was tuning when they played Suzanne Vega’s Tom’s Diner over and over, in Grade 8’s story Grade 8: Recording clean sound: a voice alone has nothing loud beside it to hide the encoder’s mistakes.

An MP3 is described by its bit rate: how many bits it stores for each second of sound, for example 128 kbps, 128 kilobits a second. Now the opening question has its answer:

Lossless or lossy?

Choose by asking one question: would a tiny change matter?

• Text, numbers, programs, spreadsheets and ZIP files must be lossless. Change one bit in a bank’s file, and Rs 1,000 could become Rs 9,000; change one bit in a program, and it may not run.
• Photos, music and video for people to look at and listen to can be lossy: they have far more detail than eyes and ears take in.
• Some pictures must stay exact even so: a screenshot with small writing, a diagram with sharp lines, an X-ray a doctor must read, a photo you are still editing. Keep those lossless.