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.

Bits123456781632
Patterns24816326412825665 5364 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

ColourRedOrangeYellowGreenBlueIndigoViolet
Code000001010011100101110

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

DecimalBCD (8 4 2 1)Excess-38 4 −2 −1Gray
00000001100000000
10001010001110001
20010010101100011
30011011001010010
40100011101000110
50101100010110111
60110100110100101
70111101010010100
81000101110001100
91001110011111101
  • 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 code0001 0011 (one 4-bit group per decimal digit)
8-bit plain binary code0000 1101

⚠️ BCD is not the binary value of the number — each decimal digit is coded separately. in BCD is 0001 0011, not 1101.


2. Encoding Positive Integers

Rule – -bit Plain Binary Code

Memory is organised in words of = 8, 16, 32 or 64 bits.

  1. Convert the number to binary.
  2. 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 :

RangeMax
8255
1665 535
324 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

OperationBinaryResultStatus
01001001 + 10001100 = 11010101213correct ()
10001100 + 10001100 = (1)0001100024overflow ()
10001100 + 01110100 = (1)000000000overflow ()

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

Code000001010011100101110111
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.

Code000001010011100101110111
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

Operands10110 + 1101110110 + 01001
Raw sum1 1000111111
End-around carry10001 + 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
Code000001010011100101110111
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

OperationCodesSumValue
00000110 + 0000110100010011+19
11111010 + 00001101(1)00000111+7
00000110 + 1111001111111001−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 + 00001101 00000111
  • 11111010 + 11110011 11101101

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

DecimalS-2’s-CS-1’s-CSM
+7011101110111
+6011001100110
+5010101010101
+4010001000100
+3001100110011
+2001000100010
+1000100010001
+0000000000000
−0—11111000
−1111111101001
−2111011011010
−3110111001011
−4110010111100
−5101110101101
−6101010011110
−7100110001111
−81000——

Example – over 16 bits

SMS-1’s-CS-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:

SignInteger partFractional 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,

SignExponentNormalized 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 101 padded 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: 101000001 has 9 bits → keep 8: 10100000 (one bit lost — precision loss)
  • Exponent → 0011

Result: 1 | 0011 | 10100000

Solved Exercise – Biased Format 1 + 5 + 10

Bias .

Sign10
Binary
Biased exponent = 01010 = 01101
Mantissa10000000001000000000
Code1 01010 10000000000 01101 1000000000

4.3 IEEE 754 Standard

TypeTotalSignBiased exponentMantissa
Single precision32 bits18 bits, 23 bits
Double precision64 bits111 bits, 52 bits
Quadruple precision128 bits115 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)
RangeHex 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:

PartScript
8859-1Latin-1, Western European
8859-2Latin-2, Central European
8859-3Latin-3, South European
8859-4Latin-4, North European
8859-5Latin/Cyrillic
8859-6Latin/Arabic
8859-7Latin/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).