MATH3411 Information, Codes and Ciphers
UNSW Sydney
Formalities
Course authority: Thomas Britz
Email: britz@unsw.edu.au
Please email me if you have any questions or comments!
Check Moodle for course notes, lecture slides, and more.
Feel free to join the piazza forum and Facebook group!
Overview
Chapter 1 Introduction
Chapter 2 Error Detecting and Correcting Codes
Chapter 3 Compression Coding
Chapter 4 Information Theory
Chapter 5 Algebra and Number Theory
Chapter 6 Algebraic Coding
Chapter 7 Cryptography
1
Chapter 1: Introduction
Lectures 1-2
To preserve data, we encode it.
Chapters 2 & 6 introduce us to Coding Theory.
To keep data secret, we encrypt it.
Chapter 7 introduces us to Cryptography.
To keep data compact, we compress it.
Chapter 3 introduces us to Compression methods.
Communication Theory
Coding Theory
Cryptography
Compression methods
Information Theory (Chapter 4)
much more (but not in this course)
2
We will only deal with digital data (discrete information).
Most analogue information can be digitised satisfactorily.
pictures can be divided into a grid of pixels
whose mean colour and brightness are represented by a number.
sound can be divided into small time intervals,
whose mean frequency and amplitude are represented by a number.
text is usually divided into individual letters
each of which is represented by a number.
Example
Music CDs reproduce sound through 44100 bits per second,
represented by 216 = 65536 16-bit binary numbers.
We will only look at text data.
To give a mathematical framework for digital data transmission, define
a source alphabet S = {s1, s2, . . . , sq} of q symbols
a code alphabet A of r symbols
probabilities pi = P (si)
a code that encodes each symbol si by a codeword
which is a string of code symbols.
Example
A code encodes S = {a, b, c} to strings on A = {0, 1} as follows:
S codewords
a −→ 00
b −→ 01
c −→ 10
This is a binary code, and the code symbols are called bits (binary digits).
Modern computers are binary-based - but older computers were not. 3
A binary code is a radix 2 code.
More generally, a code is a radix r code if r = |A|.
The alphabet A is then usually {0, 1, . . . , r − 1} or {1, 2, . . . , r}.
Codewords can be seen as vectors.
The length of a codeword is the length of the corresponding vector.
Example
1001101 corresponds to (1, 0, 0, 1, 1, 0, 1) ∈ Z7
2
1001101 could thus be a binary codeword of length 7 (with 7 bits).
In contrast, 3411 could be a radix 5 codeword of length 4.
Assumed knowledge
modular arithmetic
prime numbers
probability theory
linear algebra
4
Division Algorithm
If a, b are integers and b > 0, then
a = qb+ r
for unique integers q, r with r ∈ {0, 1, . . . , b− 1}.
Here, q is the quotient and r is the remainder.
We define a mod b to equal r.
Example
11 = 2× 4 + 3 so 11 mod 4 = 3
Exercise
11 mod 3 =
15 mod 7 =
5 mod 7 =
−5 mod 7 =
Integers a and b are congruent modulo m, denoted by a ≡ b (mod m), if
(a mod m) = (b mod m)
In other words, a and b have the same remainder when divided by m.
Equivalent definitions of congruence
a ≡ b (mod m)
(a mod m) = (b mod m)
a = b+ qm for some integer q
a− b = qm for some integer q
m | (a− b)
Example
· · · ≡ −8 ≡ −3 ≡ 2 ≡ 7 ≡ 12 ≡ · · · (mod 5)
5
Theorem
Suppose that a ≡ b (mod m) and c ∈ Z.
Then
a+ c ≡ b+ c (mod m)
a− c ≡ b− c (mod m)
ac ≡ bc (mod m)
Addition, subtraction, and multiplication
are therefore performed as usual under congruence.
Division is not always possible - but if ax ≡ 1 (mod m),
then a has an inverse a−1 = x (mod m),
so we can “divide by a” by multiplying by a−1.
Exercise
3 + 4 ≡ (mod 5)
3− 4 ≡ (mod 5)
3× 4 ≡ (mod 5)
3× 2 ≡ (mod 5)
3−1 ≡ (mod 5)
Example
2x 6≡ 1 (mod 4) for all integers x
so 2 has no inverse modulo 4 (so we cannot “divide by 2” in modulo 4.)
6
Sometimes, we are only interested in remainders of numbers, not the
numbers themselves. For instance, we might be interested only in whether
a number is even or odd.
Using congruence under modulus 2, we can represent
all even numbers by 0
all odd numbers by 1 .
This gives us the set of numbers Z2 = {0, 1} modulo 2.
In general, Zm is the set of numbers {0, 1, . . . ,m− 1} modulo m.
Example
Z2 is the set {0, 1} with addition + and multiplication × modulo 2:
+ 0 1
0 0 1
1 1 0
× 0 1
0 0 0
1 0 1
We say that “1 + 1 = 0 in Z2”.
The modulo 2 is here given from the context.
Example
Z3 is the set {0, 1, 2} with addition + and multiplication × modulo 3:
+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
× 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1
In Z3, 2 + 2 = 1.
Exercise
In Z7,
3 + 5 =
3− 5 =
3× 5 =
3−1 = 7
A positive integer p is prime
if it has no other positive factor than 1 and itself.
The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . . .
There are infinitely many primes;
this was proved over 2000 years ago.
If an integer m > 1 is not prime, then it is composite.
1 is neither prime nor composite.
The Fundamental Theorem of Arithmetic
Every integer n > 1 has a unique prime factorization (ignoring order).
In other words, we can write
n = pα1
1
pα2
2
· · · pαkk ,
for unique primes p1 < p2 < · · · < pk and positive integers α1, α2, . . . , αk.
Example
60 = 22 × 3× 5
8
In Probability Theory, an event A is “stuff that might happen”.
Slightly more precisely, A is a set with a fixed probability P (A).
Example
Roll a die and consider the event A that we rolled a six:
A = {six is rolled} =
{ }
Then P (A) =
1
6
.
If we have two probabilites A and B,
then
P (A|B) is the conditional probability that A will happen if B happens.
Example
Roll a die and consider the events
A = {six is rolled} =
{ }
B = {an even number is rolled} =
{
, ,
}
Then P (A|B) =
1
3
and P (B|A) = 1 .
Bayes’ Rule
If A1, . . . , An form an event partition and B is also an event,
then P (Aj|B) =
P (B|Aj)P (Aj)∑n
i=1 P (B|Ai)P (Ai)
.
This rule lets us reverse the direction of conditional probabilities.
We can thereby solve problems like
“Student X achieved HD in MATH3411.
Knowing the probability of X achieving this by studying hard,
what is the probability that student X actually studied hard?” 9
It is often useful to represent events by (discrete) random variables X.
These have probabilities P (X = x) where x is any number.
MATH3411 mostly considers binomially distributed random variables X.
These have probabilities of the form
P (X = k) =
(
n
k
)
pk(1− p)n−k
which is the probability of
k Ys happening in n independent Y/N trials each with Y-probability p.
Linear algebra
Linear combination
linear independence
... and more: revise!
A linear combination of vectors v1, . . . ,vn is any sum of the form
λ1v1 + · · · + λnvn
The span of v1, . . . ,vn over a field F is the set of their linear combinations:
span{v1, . . . ,vn} = {λ1v1 + · · · + λnvn : λ1, . . . , λn ∈ F}
Vectors v1, . . . ,vn are linearly dependent if
λ1v1 + · · · + λnvn = 0
for some elements λ1, . . . , λn ∈ F not all of which are 0.
10
Equivalently, some vi is a linear combination of the other vectors.
They are linearly independent if they are not linearly dependent.
Vectors v1, . . . ,vn form a basis for a vector space V
if they span V and are linearly independent.
Example
Any three vectors a,b, c in R2 are linearly dependent:
2c
c
a = b+ 2c
b
For instance, a = b+ 2c is here a linear combination of b and c;
equivalently, a is in the span of b and c, namely span{b, c} = R2.
However, any two of these vectors are non-parallel
and are therefore linearly independent.
Since they furthermore span R2, these two vectors form a basis for R2.
Some wellknown codes
Morse code
ASCII
ISBN
11
Morse code
Morse code is a ternary code (radix 3).
Its alphabet is
• called dot (or dit or di)
− called dash (or dah)
p a pause
The codewords are strings of • and − terminated (separated) by p.
Example
The Morse code encodes the word “sky” into
•••p−•−p−•−−p
Cleverly, common letters have short codewords, and rarer ones longer:
E is •p
T is −p
Q is −−•−p
Morse code is thus a type of compression coding (still sometimes used).
•••−−−•••
A •− N −• 1 •−−−−
B −••• O −−− 2 ••−−−
C −•−• P •−−• 3 •••−−
D −•• 0.11% Q −−•− 4 ••••−
12.5% E • R •−• 5 •••••
F ••−• S ••• 6 −••••
G −−• 9.25% T − 7 −−•••
H •••• U ••− 8 −−−••
I •• V •••− 9 −−−−•
J •−−− W •−− 0 −−−−−
K −•− X −••−
L •−•• Y −•−−
M −− Z −−•• (See Appendix 1 for full list)
12
ASCII
American National Standard Code for Information Interchange
It is a binary code of fixed codeword length, namely 7,
with 27 = 128 encoded symbols, including control characters like ESCAPE.
Example
b7 b6 b5 b4 b3 b2 b1
A −→ 1 0 0 0 0 0 1
a −→ 1 1 0 0 0 0 1
b −→ 1 1 0 0 0 1 0
} −→ 1 1 1 1 1 0 1
The bit numbering goes from right to left:
each codeword is the binary expansion of the symbol’s list number:
a is number 26 +25 +20 = 64+ 32+ 1 = 97 on the list of characters
b is number 98 = 26 + 25 + 21 so has codeword 1100010.
Usually, ASCII is augmented by an 8th bit in front of the other 7.
This is either
to give the extended ASCII with 28 = 256 encoded symbols
or for use as a parity bit or check bit.
Usually, even parity is used:
choose the 8th bit so that each 8-bit codeword has an even number of 1s.
This code is usually also called ASCII.
Example
7− bit 8-bit (even parity)
A 1000001 01000001
a 1100001 11100001
b 1100010 11100010
} 1111101 01111101
Parity bit 13
Example
Suppose that we transmit 7-bit ASCII at 7× 106 bits/s
(in other words, 106 codewords per second),
and that the probability of a given bit being in error is p = 10−6,
independepently of the other bit errors.
The probability of an incorrectly transmitted word is 1−(1−p)7 ≈ 7×10−6
We thus expect 7 errors to occur unnoticed each second.
With an added parity check, only an even number of errors go undetected.
The probability of undetected error is then only 2.8×10−11 (see Problems).
The expected number of undetected errors per second is
1
8
× (7× 106)× (2.8× 10−11) ≈ 2.5× 10−5
This corresponds to 1 undetected error every 11 hours.
A simple parity check can make a big difference!
ISBN
International Standard Book Number
Books published between 1970-2007 were given a 10-digit ISBN of the form
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
x1, . . . , x9 are decimal digits signifying country group, publisher, and title.
x10 is a decimal digit or an X to represent 10.
It is a generalised parity number or check digit so that
10∑
i=1
ixi ≡ 0 (mod 11) .
14
Example
Conway & Guy’s Book of Numbers (hardback) has ISBN 0-387-97993-X.
Let us check that this is a correct ISBN.
10∑
i=1
ixi = 1·0 + 2·3 + 3·8 + 4·7 + 5·9 + 6·7 + 7·9 + 8·9 + 9·3 + 10·10
= 0 + 6 + 24 + 28 + 45 + 42 + 63 + 72 + 27 + 100
≡ 0 + 6 + 2 + 6 + 1 + 9 + 8 + 6 + 5 + 1 (mod 11)
≡ 0 (mod 11)
The ISBN is indeed correct.
To find x10, note that
0 ≡
10∑
i=1
i xi ≡
9∑
i=1
i xi + 10x10 ≡
9∑
i=1
i xi − x10 (mod 11)
Therefore, x10 =
9∑
i=1
i xi mod 11.
Example
What is the check digit for a book with partial ISBN 0-245-59812?
9∑
i=1
i xi = 1·0 + 2·2 + 3·4 + 4·5 + 5·5 + 6·9 + 7·8 + 8·1 + 9·2
= 0 + 4 + 12 + 20 + 25 + 54 + 56 + 8 + 18
≡ 0 + 4 + 1 + 9 + 3 + 10 + 1 + 8 + 7 (mod 11)
≡ 10 (mod 11)
The check digit should be X.
15