Encoding Schemes and Number System

Written and reviewed by Rohit Singh, Computer Science & Commerce faculty at UniDrill (MCA, Osmania University · 6 years teaching). Based on NCERT Computer Science Class XI, Chapter 2.

You press A. What does the computer receive?

Not the letter. A computer is a machine of switches that are either on or off, so the only language it understands is 0 and 1. When you press the key A, the keyboard maps it to the code value 65, and 65 is stored as the binary number 1000001. Press the Devanagari letter अ and the code is the hexadecimal value 0905, stored as 0000100100000101.

Two questions follow, and this whole chapter answers them. Why 65 and not some other number? And how do we move comfortably between decimal (which humans use), binary (which the machine uses) and octal and hexadecimal (which are shortcuts for binary)?

Encoding: one agreed code for every character

Encoding is converting data into an equivalent code by following a specific scheme. The code for A is 65 on every keyboard, whatever its make, because manufacturers agreed on standard encoding schemes, in which each letter, numeral and symbol gets a unique code. Without a standard, a file typed on one machine would show gibberish on another.

ASCII. In the early 1960s computers could not exchange text because each represented keyboard keys differently. ASCII was created to standardise this, and it is still the most commonly used scheme. It encodes only English. Some printable codes to remember:

Capital letters run from 65 and small letters from 97, in alphabetical order. The code for any letter follows from the one you know: if A is 65, then D is 68 and T is 84.

Worked example: encode DATA. Write the ASCII code of each letter and its 7-bit binary.

Worked example: encode COMPUTER. The letters are C, O, M, P, U, T, E, R, which have the codes 67, 79, 77, 80, 85, 84, 69, 82 (counting from A = 65). Their 7-bit binary forms are 1000011, 1001111, 1001101, 1010000, 1010101, 1010100, 1000101 and 1010010. Eight letters at 7 bits each need $8 \times 7 = 56$ bits.

Worked example: small and capital letters. A is 65 and a is 97. The difference is 32. In binary A is 1000001 and a is 1100001, so changing case flips just one bit, the one worth $2^5 = 32$.

Common wrong step. Taking the position of a letter in the alphabet (A = 1, B = 2) as its code. The code is the ASCII value, so A is 65, not 1.

Pause and predict: how many different characters can a 7-bit code represent, and how many can an 8-bit code represent?

Check your answer: Each bit has two choices, so $n$ bits give $2^n$ patterns. Seven bits give $2^7 = 128$ and eight bits give $2^8 = 256$. This is why ASCII holds 128 characters and ISCII has room for 256.

ISCII. To use Indian languages on computers, India developed ISCII in the mid 1980s. It is an 8-bit code. It keeps all 128 ASCII codes and uses the remaining 128 for the Indian language character set, with the codes from 160 to 255 assigned to the aksharas of the language.

Unicode. Before Unicode, many schemes served different languages and could not talk to each other: text created in one scheme was unreadable on a machine that used another. Unicode fixes this by giving a unique number to every character of every written language, irrespective of the device (server, desktop, mobile), operating system (Linux, Windows, iOS) or software (browsers, text editors). Its common forms are UTF-8, UTF-16 and UTF-32. Unicode is a superset of ASCII: the values 0 to 127 are the same characters as in ASCII. Devanagari occupies a block that begins at 0900, where क is 0915 and अ is 0905. Unicode values are written in hexadecimal.

Worked example: the binary of a Hindi letter. Find the binary code of अ, whose Unicode value is 0905.

Beyond the textbook. For the exam: UTF-8, UTF-16 and UTF-32 are the common Unicode encodings, and Unicode includes ASCII. In reality: UTF-32 uses a fixed 32 bits for every character, UTF-16 uses 16 bits for most characters, and UTF-8 uses 1 byte for the ASCII characters and more bytes (up to 4) for others. This is why a character in UTF-32 takes more space than in UTF-16 or UTF-8, and why English text saved as UTF-8 is no bigger than it was in ASCII. Why it matters: it explains why UTF-8 became the most common encoding on the web.

Number systems: counting in different bases

A number system is a method of writing numbers. Each has a set of unique symbols, and the count of those symbols is its base or radix. The base is written as a subscript to tell systems apart: $(70)8$ is 70 in octal and $(70){10}$ is 70 in decimal.

These are positional number systems: the value of a symbol depends on where it stands. The rightmost symbol of the integer part sits at position 0, and position numbers go up by 1 towards the left. The first symbol of the fractional part is at position $-1$, going down by 1 towards the right. Each symbol contributes (symbol value) × (base raised to its position), and the number is the sum.

$$(d_n \ldots d_1 d_0 . d_{-1} d_{-2} \ldots)_b = \sum d_i \times b^{\,i}$$

For example, 237.25 in decimal is $2 \times 10^2 + 3 \times 10^1 + 7 \times 10^0 + 2 \times 10^{-1} + 5 \times 10^{-2}$.

Every number system has the same pattern: the base is the number of symbols, and the largest digit is one less than the base. So an octal number can never contain 8 or 9, and a binary number only 0 and 1.

Digits 0 to 7 with only their last three bits also form the octal table: octal 5 is 101 and octal 7 is 111.

Why 3 bits for octal and 4 bits for hexadecimal? Because $8 = 2^3$ and $16 = 2^4$. Three bits have $2 \times 2 \times 2 = 8$ patterns, exactly enough for the eight octal digits, and four bits have 16 patterns, exactly enough for the sixteen hex symbols. This is the reason conversions between binary and octal or hex are done by grouping bits.

Pause and predict: what is the decimal value of $(10)_2$, $(10)8$ and $(10){16}$?

Check your answer: In every base $b$, the written number 10 means one group of $b$. So the values are 2, 8 and 16. The same digits mean different amounts in different bases, which is why the base subscript matters.

Decimal to binary, octal and hexadecimal

Divide the number again and again by the base, writing down each remainder, until the quotient is zero. Then read the remainders from bottom to top. The last remainder is the most significant digit.

Worked example: 93 to binary.

Reading the remainders from the bottom up gives $(93)_{10} = (1011101)_2$. Check by adding place values: $64 + 16 + 8 + 4 + 1 = 93$.

Common wrong step. Reading the remainders from top to bottom. The number 93 happens to read the same both ways, so test the habit on 122: the remainders come out as 0, 1, 0, 1, 1, 1, 1 from top to bottom, and the correct answer is 1111010 (bottom to top). Top to bottom gives 0101111, a different number. Always read bottom to top.

Worked example: 500 to octal and hexadecimal.

So $(500)_{10} = (764)8 = (1F4){16}$. In the hex row the remainder 15 is written as F, not as "15".

Two more results are worth knowing. The ASCII code of A, $(65)_{10}$, is $(1000001)_2 = (101)8 = (41){16}$. And $(122)_{10} = (1111010)_2 = (172)8 = (7A){16}$.

Other bases back to decimal

Write the position number under each digit (starting from 0 on the right), multiply each digit by the base raised to that position, and add.

Worked example: binary, octal and hexadecimal to decimal.

Common wrong step. In $(3A5)_{16}$, using 1 for A (the first letter) or 11 for A. The letters stand for 10 to 15: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

Binary to octal or hexadecimal, and back

Because 3 bits make one octal digit and 4 bits make one hex digit, no arithmetic is needed. Group the bits from the right, add zeros on the left if the last group is short, and replace each group with its digit.

Worked example: binary to octal and hexadecimal. Convert $(1101011)_2$.

Check: all three equal 107 in decimal ($64 + 32 + 8 + 2 + 1 = 107$; $1 \times 64 + 5 \times 8 + 3 = 107$; $6 \times 16 + 11 = 107$).

Common wrong step. Grouping from the left. For 1101011 this gives 110 101 1, which is no longer a valid grouping and gives a wrong answer. The integer part is always grouped from the right.

To go the other way, replace each octal digit by 3 bits or each hex digit by 4 bits and join them. So $(705)_8 = 111\ 000\ 101 = (111000101)2$, and $(23D){16} = 0010\ 0011\ 1101 = (001000111101)2$. Octal and hexadecimal can also be converted to each other through binary: $(7A){16} = 0111\ 1010 = 001\ 111\ 010 = (172)_8$.

Worked example: cross check 500. $(500)_{10} = (111110100)_2$. Groups of 3 give 111, 110, 100, which is 764. Groups of 4, padded, give 0001, 1111, 0100, which is 1F4. Both agree with the division method above.

Numbers with a fractional part

Decimal fraction to another base. Multiply the fractional part by the base, record the integer part, and keep multiplying the new fractional part until it becomes 0. Read the integer parts from top to bottom. If the fraction never reaches 0, stop when it starts repeating, or after about 10 steps.

Worked example: $(0.625)_{10}$ to binary.

The fraction reached 0, so $(0.625)_{10} = (0.101)_2$. Check: $\tfrac{1}{2} + \tfrac{1}{8} = 0.625$.

The fraction $(0.675)_{10}$ does not end. In binary it begins 0.1010110 and the fractional part 0.4 then repeats, so we stop. In octal it begins 0.53146, and in hexadecimal it is 0.ACCC and so on, which is written 0.AC after stopping.

Common wrong step. Reading the integer parts from bottom to top, as for whole numbers. For fractions the first digit produced is the most significant, so read top to bottom.

Non-decimal with a fraction to decimal. Use negative positions for the fractional digits.

Fractional binary to octal or hexadecimal. Group the integer part from the right, as before. Group the fractional part from the left, adding zeros on the right to complete the last group.

In the first row the fraction 01011 had only five bits, so one zero was added on the right to make the second group 110.

Beyond the textbook. For the exam: stop a fractional conversion when it ends or repeats. In reality: many decimal fractions never end in binary. $(0.1)_{10}$ is 0.000110011..., repeating forever, so a computer stores only an approximation. That is why Python prints 0.30000000000000004 for 0.1 + 0.2. Why it matters: a repeating binary fraction is the reason computers sometimes give tiny errors in decimal arithmetic. The Python functions below check conversions.

Where hexadecimal is used

A main memory location has a unique address, usually 16 or 32 bits long. Writing a 16-bit address in binary is clumsy and easy to get wrong, so hexadecimal (or octal) is used.

Worked example: a memory address. Write the address 1100000011110001 in hexadecimal and octal.

The 16 bits shrank to four hex digits, which is easy to remember.

Colours on web pages. Every colour is a mix of red, green and blue (RGB). Each component needs 8 bits, so a colour needs $3 \times 8 = 24$ bits, which allows $2^{24} = 16{,}777{,}216$ colours, about 16 million. A 24-bit binary code is hard to remember, so colours are written as three hex pairs.

Each pair works because one byte (8 bits) is exactly two hex digits, and $255 = (FF)_{16}$ is the largest value of a byte.

Exam traps

60-second revision

Conversion formula sheet

Where this chapter connects

• Previous: Computer System introduced bits, bytes and memory units, which this chapter fills with actual code values.
• Next: Emerging Trends covers how data of all kinds, all stored as these codes, is used in modern technology.
• Programming link: Getting Started with Python uses the same code values through the ord and chr functions, and the same decimal numbers as binary floating point.