1. Introduction
Definition – Encoding and Code
- Encoding is the process of converting data from one form to another. Every digital system must encode data (whole numbers, integers, real numbers, characters) before it can store or process it.
- A code is a correspondence between symbols and the objects they designate (semaphore flags, barcodes, Morse code…).
- A binary code uses only the symbols 0 and 1.
Bits and Bytes
- Bit (binary digit): the smallest unit of storage — a single 0 or 1 (an electric charge in a chip, a North/South magnetic spot on a disk).
- Byte: a group of 8 bits, e.g.
0101 1010. The leftmost bit is the MSB (Most Significant Bit), the rightmost is the LSB (Least Significant Bit). - Storage is measured in bytes: , , , , bytes.
⚠️ As in Chapter 1, the slide prints without its leading digit; the correct value is 1,125,899,906,842,624.
Theorem – Number of Patterns
An -bit code gives distinct patterns. Adding one bit doubles the number of patterns.
| Bits | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 16 | 32 |
|---|---|---|---|---|---|---|---|---|---|---|
| Patterns | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 65 536 | 4 294 967 296 |
Definition – -bit Binary Code
An -bit binary code is a bijection between the set of objects to encode and a subset of .
Example – 3-bit Code for the Rainbow Colours
| Colour | Red | Orange | Yellow | Green | Blue | Indigo | Violet |
|---|---|---|---|---|---|---|---|
| Code | 000 | 001 | 010 | 011 | 100 | 101 | 110 |
Seven colours need 3 bits; code 111 is left unused.
Theorem – Bits Needed for Elements
With bits there are codes, so we need , i.e. :
Example – Digits 0 to 9
, , so bits. Check: ✓.
There are ways to assign ten of the sixteen 4-bit patterns to the ten digits.
⚠️ The slide also writes . That formula fails when is a power of 2 (for it gives 4 instead of 3). Use the ceiling .
Common 4-bit Codes for the Decimal Digits
| Decimal | BCD (8 4 2 1) | Excess-3 | 8 4 −2 −1 | Gray |
|---|---|---|---|---|
| 0 | 0000 | 0011 | 0000 | 0000 |
| 1 | 0001 | 0100 | 0111 | 0001 |
| 2 | 0010 | 0101 | 0110 | 0011 |
| 3 | 0011 | 0110 | 0101 | 0010 |
| 4 | 0100 | 0111 | 0100 | 0110 |
| 5 | 0101 | 1000 | 1011 | 0111 |
| 6 | 0110 | 1001 | 1010 | 0101 |
| 7 | 0111 | 1010 | 1001 | 0100 |
| 8 | 1000 | 1011 | 1000 | 1100 |
| 9 | 1001 | 1100 | 1111 | 1101 |
- BCD (Binary-Coded Decimal): the code’s value is the digit’s value (weights 8, 4, 2, 1). Six patterns are unused: 1010 – 1111. Example: .
- Excess-3: BCD code ().
- 8, 4, −2, −1: weighted code with two negative weights. Example: .
- Gray code: two adjacent codes differ by exactly one bit.
- Self-complementing property (Excess-3 and 8 4 −2 −1): the codes of 0 and 9, 1 and 8, 2 and 7… are bitwise complements — they add to .
Example – Self-Complement Check
Excess-3: code(2) , code(7) → ✓.
Conversion vs. Encoding
| Representation of | |
|---|---|
| Conversion to base 2 | |
| BCD code | 0001 0011 (one 4-bit group per decimal digit) |
| 8-bit plain binary code | 0000 1101 |
⚠️ BCD is not the binary value of the number — each decimal digit is coded separately. in BCD is
0001 0011, not1101.
2. Encoding Positive Integers
Rule – -bit Plain Binary Code
Memory is organised in words of = 8, 16, 32 or 64 bits.
- Convert the number to binary.
- Pad with zeros on the left up to bits.
Example – 16-bit Code of
→ 16-bit code 0000 1011 0001 0101.
Range
A -bit code covers :
| Range | Max | |
|---|---|---|
| 8 | 255 | |
| 16 | 65 535 | |
| 32 | 4 294 967 295 |
Fixed width ⇒ fixed range ⇒ risk of overflow.
Theorem – Addition is Modulo
Adding two -bit codes and keeping bits computes the sum modulo . A carry out of the MSB means overflow.
Example – 8-bit Additions
| Operation | Binary | Result | Status |
|---|---|---|---|
01001001 + 10001100 = 11010101 | 213 | correct () | |
10001100 + 10001100 = (1)00011000 | 24 | overflow () | |
10001100 + 01110100 = (1)00000000 | 0 | overflow () |
Multiplication and Division by
- × : shift left positions, fill with zeros on the right — the leftmost bits are lost.
- ÷ : shift right positions, fill with zeros on the left — the rightmost bits are lost.
Example – 8-bit Code
- =
00110100; =11010000= 208 ✓ - =
10100000≠ 416 → overflow (a 1 was shifted out) - =
00110100= 52 ✓
3. Encoding Signed Integers
The sign is binary information, so it takes 1 bit. Convention: in a -bit code, the leftmost bit is the sign — 0 = positive, 1 = negative. Three representations exist: signed-magnitude, signed-1’s-complement and signed-2’s-complement.
3.1 Signed-Magnitude (SM)
Definition
- MSB = sign; the remaining bits = binary magnitude.
- Example (8 bits): =
0 0000001, =1 0000001. - Range: .
Example – 3-bit SM Code
| Code | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| Value | +0 | +1 | +2 | +3 | −0 | −1 | −2 | −3 |
- ✅ Simple to read.
- ❌ Two zeros (+0 and −0).
- ❌ Needs separate circuits for addition and subtraction, whereas a single circuit is preferable because .
Rule – SM Addition/Subtraction (Ordinary Arithmetic)
- Same signs: add magnitudes, keep the common sign: , .
- Different signs: subtract the smaller magnitude from the larger, take the sign of the larger: if , if , and if equal.
3.2 Complements of Numbers
Definition – Diminished Radix Complement (‘s complement)
For an -digit number in base :
- Decimal (9’s complement): .
- Binary (1’s complement): .
- Binary shortcut: invert every bit (since and ). Example:
01010→10101.
Definition – Radix Complement (‘s complement)
Since : ‘s complement = ‘s complement + 1.
- 10’s complement of = .
- 2’s complement of = .
- Binary shortcut: starting from the LSB, keep all trailing 0s and the first 1 unchanged, then invert all higher bits. Example:
01100→10100.
Theorem – Complement of the Complement
Complementing twice gives back the original number:
3.3 Signed-1’s-Complement (S-1’s-C)
Definition
Over bits:
- : a 0 followed by the -bit binary value.
- : the 1’s complement (over bits) of .
Example (8 bits): = 00001101, = 1’sC(00001101) = 11110010.
Range: ; MSB = sign; two zeros.
| Code | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| Value | +0 | +1 | +2 | +3 | −3 | −2 | −1 | −0 |
Solved Exercise – 6-bit S-1’s-C Value of 101010
MSB = 1 → negative. Value .
Rule – S-1’s-C Addition (End-Around Carry)
Add the codes including the sign bits; if there is a carry out of the MSB, add it back to the LSB (end-around carry).
Example – 5-bit S-1’s-C
| Operands | 10110 + 11011 | 10110 + 01001 |
| Raw sum | 1 10001 | 11111 |
| End-around carry | 10001 + 1 = 10010 | — |
| Value |
3.4 Signed-2’s-Complement (S-2’s-C)
Definition
Over bits:
- : a 0 followed by the -bit binary value.
- : the 2’s complement (over bits) of .
Example (8 bits): = 00001101, = 2’sC(00001101) = 11110011.
Range: — a single zero, and one extra negative value.
| Range | |
|---|---|
| 8 | |
| 16 | |
| 32 |
| Code | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| Value | +0 | +1 | +2 | +3 | −4 | −3 | −2 | −1 |
Solved Exercise – 6-bit S-2’s-C Value of 101010
MSB = 1 → negative. Value .
flowchart TD A["n-bit code"] --> B{"MSB?"} B -->|0| C["Positive:<br/>value = plain binary"] B -->|1| D{"Representation?"} D -->|SM| E["− (remaining n−1 bits)"] D -->|"S-1's-C"| F["− (invert all bits)"] D -->|"S-2's-C"| G["− (invert all bits, then +1)"]
Rule – S-2’s-C Addition
Add the two codes including the sign bits and discard the carry out of the sign position. A negative result is already in 2’s-complement form.
Example – 8-bit S-2’s-C Additions
| Operation | Codes | Sum | Value |
|---|---|---|---|
00000110 + 00001101 | 00010011 | +19 | |
11111010 + 00001101 | (1)00000111 | +7 | |
00000110 + 11110011 | 11111001 | −7 | |
11111010 + 11110011 | (1)11101101 | −19 |
(carry in parentheses is discarded)
Rule – S-2’s-C Subtraction
: take the 2’s complement of the subtrahend (sign bit included), add, discard the carry. Negating any number (either direction) is just taking its 2’s complement.
-
11111010 + 0000110100000111 -
11111010 + 1111001111101101
3.5 Overflow
With bits, a result outside the range is wrong. Overflow is detected when:
- the sum of two positive numbers is negative, or
- the sum of two negative numbers is positive.
(Adding numbers of opposite signs can never overflow.)
Example – 5-bit S-2’s-C (range )
- :
01001 + 01000 = 10001→ negative ⇒ overflow (+17 doesn’t fit). - :
10111 + 11000 = (1)01111→ positive ⇒ overflow (−17 doesn’t fit).
⚠️ In 2’s complement, a carry out of the MSB on its own is not an overflow (see above). Check the signs. Equivalently, overflow happens when the carry into the sign bit differs from the carry out of it.
3.6 Comparison over 4 bits
| Decimal | S-2’s-C | S-1’s-C | SM |
|---|---|---|---|
| +7 | 0111 | 0111 | 0111 |
| +6 | 0110 | 0110 | 0110 |
| +5 | 0101 | 0101 | 0101 |
| +4 | 0100 | 0100 | 0100 |
| +3 | 0011 | 0011 | 0011 |
| +2 | 0010 | 0010 | 0010 |
| +1 | 0001 | 0001 | 0001 |
| +0 | 0000 | 0000 | 0000 |
| −0 | — | 1111 | 1000 |
| −1 | 1111 | 1110 | 1001 |
| −2 | 1110 | 1101 | 1010 |
| −3 | 1101 | 1100 | 1011 |
| −4 | 1100 | 1011 | 1100 |
| −5 | 1011 | 1010 | 1101 |
| −6 | 1010 | 1001 | 1110 |
| −7 | 1001 | 1000 | 1111 |
| −8 | 1000 | — | — |
Example – over 16 bits
| SM | S-1’s-C | S-2’s-C | |
|---|---|---|---|
0000 1011 0001 0101 = 0B15₁₆ | 0B15₁₆ | 0B15₁₆ | |
1000 1011 0001 0101 = 8B15₁₆ | 1111 0100 1110 1010 = F4EA₁₆ | 1111 0100 1110 1011 = F4EB₁₆ |
Positive numbers look the same in all three systems.
4. Encoding Real Numbers
A real number has an integer part, a fractional part and a sign. The machine must know where the point is: either it is fixed (fixed point) or it moves (floating point).
4.1 Fixed-Point Representation
Definition
bits:
| Sign | Integer part | Fractional part |
|---|---|---|
| 1 bit (0 = +, 1 = −) | bits (magnitude) | bits (magnitude) |
Disadvantages: limited range and low precision.
Example – 14.42 in 16-bit Fixed Point (1 + 8 + 7)
- Sign: positive → 0
- Integer: →
00001110(8 bits) - Fraction: →
0110101(7 bits, truncated) - Code:
0 00001110 0110101=0000011100110101
Stored value: → precision loss.
Range vs. Precision
With fractional bits and integer bits, the magnitude is below and the step is .
- Increase → smaller range, better accuracy.
- Decrease → larger range, worse accuracy.
Real-world values span huge ranges (proton mass kg, Avogadro’s number ) — we need the same relative accuracy everywhere ⇒ floating point.
4.2 Floating-Point Representation
Definition – Scientific Notation
= mantissa, = radix, = exponent. Examples: ; ; .
Definition – -bit Floating-Point Format,
| Sign | Exponent | Normalized mantissa |
|---|---|---|
| 1 bit | bits (S-2’s-C or biased) | bits |
- Normalized mantissa: the number is written as . The leading 1 is always there — the hidden bit — so only the fractional bits are stored.
- Exponent: in signed-2’s-complement, or as a biased exponent to make it non-negative.
Definition – Biased Exponent
A -bit S-2’s-C exponent lies in . Adding the bias maps it onto :
Solved Exercise – , Format 1 + 4 (S-2’s-C) + 8
- Positive → sign 0.
- Mantissa: fractional part
101padded to 8 bits →10100000 - Exponent in 4-bit S-2’s-C: 2’sC(
0110) =1010
Result: 0 | 1010 | 10100000
Solved Exercise – , Format 1 + 4 (S-2’s-C) + 8
- Negative → sign 1.
- Mantissa:
101000001has 9 bits → keep 8:10100000(one bit lost — precision loss) - Exponent →
0011
Result: 1 | 0011 | 10100000
Solved Exercise – Biased Format 1 + 5 + 10
Bias .
| Sign | 1 | 0 |
| Binary | ||
| Biased exponent | = 01010 | = 01101 |
| Mantissa | 1000000000 | 1000000000 |
| Code | 1 01010 1000000000 | 0 01101 1000000000 |
4.3 IEEE 754 Standard
| Type | Total | Sign | Biased exponent | Mantissa |
|---|---|---|---|---|
| Single precision | 32 bits | 1 | 8 bits, | 23 bits |
| Double precision | 64 bits | 1 | 11 bits, | 52 bits |
| Quadruple precision | 128 bits | 1 | 15 bits, | 112 bits |
⚠️ The slide lists quadruple precision as “80 bits”, but bits. (The 80-bit format is the separate x87 “extended precision” with a 64-bit mantissa.)
⚠️ IEEE 754’s bias is (127, 1023…), one less than the course’s generic bias . Use whichever bias the exercise states.
5. Encoding Characters
US-ASCII (1960s, last updated 1986)
American Standard Code for Information Interchange — 7 bits ⇒ 128 codes:
- 95 printable codes (English letters, digits, punctuation)
- 33 control codes: text formatting (BS = backspace, CR = carriage return, LF = line feed…) and flow control (STX/ETX = start/end of text)
| Range | Hex codes |
|---|---|
Digits 0–9 | – |
Uppercase A–Z | – |
Lowercase a–z | – |
Upper ↔ lower case: flip the 6th bit from the right (value ): A = 100 0001, a = 110 0001.
Example – Reading the ASCII Table
The table is indexed by the high 3 bits (column) and the low 4 bits (row): a = column 110, row 0001 → 1100001 = . Digit 7 = = 011 0111.
⚠️ The ASCII code of a digit is not its value:
'7'= = 55, not 7. Subtract to get the value.
ISO 8859 (1987)
8-bit codes; the first 128 positions are identical to ASCII, the upper 128 add regional characters:
| Part | Script |
|---|---|
| 8859-1 | Latin-1, Western European |
| 8859-2 | Latin-2, Central European |
| 8859-3 | Latin-3, South European |
| 8859-4 | Latin-4, North European |
| 8859-5 | Latin/Cyrillic |
| 8859-6 | Latin/Arabic |
| 8859-7 | Latin/Greek |
Unicode (1991 –)
A universal character set using 1 to 4 bytes per character: all languages, music and math symbols, ancient scripts. (The slides cite Unicode 13.0 from 2020; newer versions have been released since.)
Exercises: solved exercises in the slides — S-1’s-C and S-2’s-C value of 101010 (§3.3, §3.4); floating-point codes of , , and (§4.2).