MATH3411 Information, Codes And Ciphers 2019 T3
Course Notes
1 Introduction 1
Copyright By PowCoder代写 加微信 powcoder
1.1 MathematicalModel……………………………. 2
1.2 ModularArithmetic ……………………………. 3
1.3 Probability ………………………………… 5
1.4 MorseCode………………………………… 5
1.5 ASCIIcode………………………………… 6
1.6 ISBNNumbers………………………………. 6
2 Error Detection and Correction Codes 9
2.1 RandomNoise ………………………………. 9 2.2 ErrorProbabilities …………………………….. 10 2.3 ErrorcapabilitiesofISBNnumbers…………………….. 11 2.4 Burstnoise ………………………………… 13 2.5 Error-correctingcodes …………………………… 14 2.6 Typesofcodes ………………………………. 16 2.7 BinaryRepetitioncodes ………………………….. 17 2.8 Informationrateandredundancy……………………… 19 2.9 BinaryHammingerrorcorrectingcodes ………………….. 19 2.10BinaryHamming(n,k)codes……………………….. 24 2.11HammingDistance,Weights (Binarycase)………………… 24 2.12Connectionbetweendanderrorcorrection ………………… 25 2.13Spherepacking……………………………….. 28 2.14Perfectcodes ……………………………….. 32 2.15BinaryLinearcodes ……………………………. 32 2.16GeneratorMatrices…………………………….. 35 2.17StandardFormMatrices………………………….. 36 2.18Extendinglinearcodes…………………………… 38 2.19Radixgreaterthantwo ………………………….. 39
3 Compression Coding 43
3.1 InstantaneousandUDcodes ……………………….. 43 3.2 Illustrationofpartsoftheproof………………………. 49 3.3 Examplesforradix3……………………………. 50 3.4 MinimalUD-codes(binarycase) ……………………… 51 3.5 Huffman’salgorithm(binarycase) …………………….. 52 3.6 RadixrHuffmancodes ………………………….. 55 3.7 Extensions…………………………………. 57 3.8 Markovsources………………………………. 58 3.9 HuffmancodingforstationaryMarkovsources ………………. 61 3.10OtherTextCompressionMethods …………………….. 63 3.11OthertypesofCompression………………………… 67
4 Information Theory 69
4.1 Somemathematicalpreliminaries……………………… 72 4.2 MaximumEntropyTheorem………………………… 73 4.3 Entropyandcoding ……………………………. 74 4.4 Shannon-FanoCoding …………………………… 75 4.5 Entropyofextensionsformemorylesssources ……………….. 78 4.6 EntropyforMarkovsources ………………………… 80 4.7 ExtensionsofMarkovsources ……………………….. 82 4.8 Noisychannels ………………………………. 82 4.9 ChannelCapacity……………………………… 88 4.10Shannon’sNoisyChannelCodingTheorem ………………… 91 4.11Entropyofnaturallanguage………………………… 91
5 Number Theory and Algebra 93
5.1 RevisionofDiscreteMathematics……………………… 93 5.2 NumberTheoryResults(noproofsgiven) …………………. 96 5.3 PolynomialsoverZp(pprime) ………………………. 98 5.4 FiniteFields ……………………………….. 100 5.5 Minimalandprimitivepolynomials…………………….. 104 5.6 PrimalityTesting……………………………… 106 5.7 Factoring …………………………………. 110 5.8 RandomNumberGeneration ……………………….. 113
6 Algebraic Coding 119
6.1 Hammingcodesrevisited …………………………. 119 6.2 SingleerrorcorrectingBCHcodes …………………….. 120 6.3 Two-errorcorrectingBCHcodes ……………………… 122 6.4 Thegeneralcase(binary) …………………………. 125 6.5 Cycliccodes. ……………………………….. 128 6.6 TheGolaycodes………………………………. 132 6.7 Wherenext? ……………………………….. 134
7 Cryptography (Ciphers) 137
7.1 Someclassicalcryptosystems:……………………….. 138 7.2 Typesofciphers ……………………………… 143 7.3 One-way,hashandtrapdoorfunctions …………………… 145 7.4 CryptographyinthePublicEye………………………. 146 7.5 Publickeycryptography………………………….. 147 7.6 DigitalSignatures …………………………….. 151 7.7 ProbabalisticEncryption………………………….. 155 7.8 RecentDevelopments……………………………. 156 7.9 EntropyandCryptography ………………………… 158
Problems 161
APPENDIX 179
A.1 TheInternationalMorseCode……………………….. 179 A.2 ASCIICode………………………………… 180 A.3 LetterStatisticsfromtheBrownCorpus………………….. 181 A.4 26-letterFrequenciesinEnglish………………………. 182 A.5 Vigen`ereTable ………………………………. 182 A.6 Big-Onotation ………………………………. 183
A.7 FurtherReading ……………………………… 183
School of Mathematics and Statistics, UNSW Sydney
These notes are based on lectures given by , with some additional contributions and editing by other members of the School of Mathematics and Statistics: , , , and . Copyright is vested in UNSW Sydney ⃝c 2019.
Chapter 1 Introduction
MATH3411 Information, Codes and Ciphers is a subject which deals with various mathematical aspects of discrete communication theory: in particular, digital or binary communication. It does not look at any Engineering or implementation aspects, and is also unconcerned with the meaning of the communicated message, just its transmission.
The basic idea is that a sender wishes to send some information along some sort of com- munications link or channel to a destination. Usually this is from one place to another, but it could equally well be between one time and another by recording then later playing back the information.
Unfortunately there is almost certainly some noise or interference on the channel and this means that the signal does not get through correctly. For example, a small amount of noise on a phone line is usually not a disaster as the human ear can make out what was said even if some parts of it are distorted. This is because natural language is highly redundant.
On the other hand, the same noise on a modem or hard disk, where every single bit matters, can completely destroy any information being sent.
Our first problem is how to encode the signal so that, despite the noise, enough gets through so that the message is intelligible. Usually this encoding adds some extra information to the message, expanding its size, so that even after it has been corrupted by the noise, enough remains to be decoded into a meaningful message at the destination. This aspect is covered in Chapter 2 and later revisited in Chapter 6.
We use the following model of a channel subject to noise:
source −→ encode −→ channel −→ decode −→ destination ↑
On the other hand, sometimes we want to fit as much information as we can into as small a space as possible (assuming that the amount of noise is very small). This means that we want to compress the information in some way. In Chapter 3 we consider some of the simpler text compression methods. Then in Chapter 4 we examine how much information can be passed along a noisy channel and consider the ideas of information theory.
Sometimes an enemy may be listening to the channel and so you want to disguise the message to make it unintelligible to them. Even worse, the person listening in may be trying to alter the message you are sending or even trying to pretend that they are you. This is the realm of cryptography which we study in Chapter 7.
CHAPTER 1. INTRODUCTION
For cryptography we have a model of the channel
source −→ encrypt −→ channel −→ decrypt −→ destination ↕
In real life all three aspects may need to operate at once, so we would encrypt, then compress, then encode.
In this subject we deal only with digital information. There are a variety of techniques for compressing and encrypting analogue information, but we will not consider them here. Analogue information can always be digitised and sent as a string of digits if we wish, for example:
pictures: each pixel or small element of the picture is given a set of numbers which describe its colour and brightness. These are then transmitted as digital data.
audio: the height of the waveform is measured at certain time intervals and the heights are sent as digital data. For example, a standard music CD samples the height of the sound wave 44,100 times per second and uses 216 = 65536 different 16-bit height numbers.
Also we will not consider audio or visual information compression, coding or transmission, but restrict ourselves to text transmission only.
1.1 Mathematical Model
In general we will assume we have some source S consisting of q symbols from a given source alphabet
S={s1, s2, ···, sq} with associated probabilities of occuring of
p1, p2, ··· , pq.
Sometimes we will also use conditional probabilities such as pij to mean the probability that symbol si follows symbol sj. For example standard English uses q = 26 letters and these have various probabilities of occuring or following other letters. For example, the probability that in English text the letter ‘U’ occurs is 0.0271, but the probability that ‘U’ occurs immediately after a ‘Q’ is close to 1.
We think of the source as emitting the symbols one at a time.
The q symbols are then encoded, each by a string or word (which can be viewed as a vector) from a code alphabet having r symbols, (r < q usually).
Each of the source symbols is given a codeword made up of a number of symbols in the code alphabet. The length of a codeword is the number of symbols that occur in it.
The code alphabet will usually be {0, 1} and we then have binary codewords. The individual symbols in a binary codeword are called bits. In general when r symbols are used for the code alphabet we say this is a radix r code. Usually a radix r code uses the symbols {0,1,2,··· ,r−1} or {1,2,3,··· ,r}.
For example, 1001101 or (1,0,0,1,1,0,1) might be a particular binary codeword of length 7 or having 7 bits, and 25106 or (2,5,1,0,6) could be a radix 7 codeword of length 5. (But it could also be a radix 5 codeword of length 5, using the symbols {0, 1, 2, 5, 6} only.)
1.2. MODULAR ARITHMETIC 3 1.2 Modular Arithmetic
This subject will make extensive use of modular arithmetic. Modular arithmetic is assumed knowledge for this subject and you should revise the basics now.
We use the following notation:
Z denotes the integers {0, ±1, ±2, · · · }
N denotes the natural numbers {0, 1, 2, · · · } Z+ denotes the positive integers {1, 2, · · · }
The Division Algorithm says that for any a ∈ Z, b ∈ Z+ there exist unique integers q, r with
a = bq + r, 0 ≤ r < b.
Here q is the quotient and r, written as a (mod b) is the remainder.
For a positive integer m, we write
a≡b (mod m),
which is read as a is congruent to b modulo m, to mean that a and b leave the same (nonneg- ative) remainder when each is divided by m. This is equivalent to the condition that
a − b is exactly divisible by m
and we denote this last line by
which is read as m divides a−b or m is a factor of a−b.
m | (a−b) Do not confuse the notations | and /:
• | is a relation: b | a is either true or not, whereas • / is an operator: b/a is a number.
For example, 3 | 12 is true and 12/3 = 4 is an integer.
Addition, subtraction and multiplication (but NOT division) modulo m are done by doing the arithmetic as usual and then taking the positive remainder when divided by m.
Division is not in general allowed, but if for a given a we can solve the equation ax ≡ 1 (mod m) then we say that a has an inverse (modulo m). We write this as x ≡ a−1(mod m). We will look at how to find inverses in chapter 5.
For example modulo 11, we have
5+9=14≡3(mod11) 5−9=−4≡7(mod11) 5×9=45≡1(mod11) 5−1 ≡9(mod11)
We also use the following notation:
as 14−3=11isdivisibleby 11
as −4−7=−11isdivisibleby 11 as 45−1=44isdivisibleby 11
as 5×9≡1(mod11)
Zm = {0,1,2,··· ,m − 1}
to denote the set of nonnegative remainders when an integer is divided by m.
4 CHAPTER 1. INTRODUCTION Occasionally it is useful to use negative remainders for the larger elements, in which case we
For example,
−m−1, −m−1+1, ··· ,−1,0,1,2, ··· ,m−1 whenm isodd Zm=m2 m2 m2
−2 +1, −2 +2, ··· ,−1,0,1,2, ··· , 2 whenm iseven. Z6 = {0,1,2,3,4,5} or {−2,−1,0,1,2,3}
Z7 = {0,1,2,3,4,5,6} or {−3,−2,−1,0,1,2,3}
We perform arithmetic in the set Zm by doing the arithmetic as usual and then taking the nonnegative remainder of the result when divided by m.
So the above examples done in Z11 are written as
5+9=3, 5−9=7, 5×9=1, 5−1 =9 inZ11.
If a ≡ b (mod m) and c ≡ d (mod m) then
a+c ≡ b+d (mod m) a−c ≡ b−d (mod m) ac ≡ bd (mod m)
This allows us to mix integers and elements of Zm as in the calculation 5 · 9 ≡ 45 ≡ 9 (mod 12).
We will look more closely at Zm in chapter 5.
Mostly we will be working with Z2, that is the binary case, and then the arithmetic is
particularly simple.
0+0=0, 0+1=1+0=1, 1+1=0, 0·0=0·1=1·0=0, 1·1=1
For those who have done some logic, binary arithmetic is the same as the algebra of logic using XOR for “+” and AND for “.”.
Binary codewords of length n can be viewed as vectors in Zn2. All the usual rules of vector addition hold for such vectors. For example
1001101 + 1101010 = (1,0,0,1,1,0,1) + (1,1,0,1,0,1,0)
= (0,1,0,0,1,1,1) arithmeticmod2
We usually omit the steps in the middle of the above calculation.
A positive integer p > 1 is a prime if and only if p has no proper divisors, that is, ifandonlyiftheonlydivisorsinZ+ ofpare1andp
if and only if p ̸= 1 and for all d ∈ Z+, if d | p then d = 1 or d = p.
Example: 2, 3, 7, 101 are primes.
A number which is not prime is called composite. For example, 12 = 3 · 4 and 1001 = 7 · 143 are composites.
1.3. PROBABILITY 5 Every positive integer n has a unique prime factorization, that is, there exist unique
primes p1 < p2 < ··· < pr and unique α1,α2, ··· ,αr ∈ Z+ such that n=pα1pα2 ···pαr .
12r Forexample,12=3·4, 1001=7·11·13, 123456=28 ·3·643.
(We will later discuss how to prove a number is prime and how to factor it if it is composite.)
Another way of saying the definition of a prime p, is the following: if ab ≡ 0 (mod p) then at least one of a ≡ 0 (mod p) or b ≡ 0 (mod p).
This can also be expressed by saying that in Zp, if ab = 0 then either a = 0 or b = 0. 1.3 Probability
If X is a (discrete) random variable, then write P (X = x) for the probability that X takes the value x. We will only be interested in discrete random variables in this course.
The most important probability distribution for us will be the binomial distribution: if X is a random variable with probability distribution given by the binomial distribution with parameters n ∈ N and p ∈ [0,1], then X has positive probability on the set {0,1,2,...,n}, namely
P ( X = k ) = nk p k ( 1 − p ) n − k .
For two discrete random variables X and Y , P (Y = y, X = x) is the probability that Y = y andX=x. Also,P(Y =y|X=x)istheprobabilitythatY =ygiventhatX=x(i.e. conditional upon X = x). Now
P(Y =y,X=x)=P(Y =y|X=x)×P(X=x) =P(X =x|Y =y)×P(Y =y)
IfP(X=x|Y =y)=P(X=x)forallx,y,thenXandY areindependent.
Bayes’ Rule is very useful. It states that if we know P(X = x) and P(Y = y | X = x) for all
x, y, then
P(X =x|Y =y)= P(X =x,Y =y) P(Y =y)
P(Y =y|X=x)P(X=x) =P(Y =y|X=xi)P(X=xi)
Bayes’ Rule tells us how to reverse a conditional probability.
Morse code is a code that was designed for early wire telegraph systems and then was used on radio. It consists of two symbols dot (or di or dit) shown here as · and dash (or dah) shown here as − and letters are represented by a string of these symbols. Individual letters are separated by a third symbol which is a pause or p, so this is a radix 3 code. The p is needed to avoid confusion about where each letter’s codeword begins and ends.
In Appendix A.1 is a full listing of the International codewords. For example A has codeword · −p ,Bhas codeword − ·p , etc.
CHAPTER 1. INTRODUCTION
For example, in Morse code the English word
gets coded as
− − p · −p − p · · · ·p · · · − − p · · · · − p · − − − − p · − − − − p
Morse code is based roughly on the relative frequencies of letters in military English so as to keep messages short — it actually is a sort of compression code.
E ( ·p ), T ( −p ) and A ( · − p ) are the most frequent letters and Q ( − − · − p ) is far less frequent.
We call this a variable length codeword code, as codewords can have different lengths. 1.5 ASCII code
The 7-bit ASCII code is listed in full in Appendix A.2 and is a fixed length codeword code or block code with blocks of length 7 in the binary alphabet {0, 1}.
For example
A is a is } is
b7 b6 b5 b4 b3 b2 b1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1
Here the bi label the bits and the convention for ASCII is to number them from the right.
There are 128 = 27 symbols or characters that can be represented by 7-bit ASCII. (The first 32 symbols are special control characters and do not all appear on keyboards.)
Often, or rather usually, ASCII has an 8th bit in front of the other 7, but what it signifies depends on the application.
In some applications the 8th bit gives 28 = 256 different characters in the extended ASCII code, where for example
11110100 means the top half of an integral sign.
In other applications or the 8th bit is used as a parity bit or check bit. Usually even parity is used, which means that the 8th bit is chosen so that every 8-bit codeword contains an even number of ‘1’s. This code is usually just called the ASCII code.
For example in (8-bit even parity) ASCII code
parity bit
A is 01000001 a is 11100001
Even something as simple as a parity check can make a big difference to error detection.
1.6 ISBN Numbers
ISBN numbers are used to identify printed books, in particular, the country of publication, the publisher and the particular book number allocated by the publisher.
If you look inside the front cover of any book published before 2007 you will find that there is a 10 digit ISBN number of the form
x1x2x3x4x5x6x7x8x9x10
1.6. ISBN NUMBERS 7
where x1,··· ,x9 are decimal digits 0,1,··· ,9 and x10 is a decimal digit or an X (Roman numeral for 10). (There are usually some dashes as well but they are there to make it more readable and are not formally part of the number.)
The first 9 digits x1x2 · · · x9 have meaning and the 10th digit x10 is a generalised parity number or check digit chosen so that
ixi ≡ 0 (mod 11). i=1
For example the reference book by Roman has ISBN 0 − 387 − 97812 − 7
country publisher publishers check book no. digit
Let us check that this is a valid ISBN number:
ixi =1×0+2×3+3×8+4×7+5×9+6×7+7×8+8×1+9×2+10×7 = 297
≡ 0 ( m od 1 1 ) .
In other words, ixi is exactly divisible by 11.
The check digit x10 needs to be able to take a value in the range 0,1,··· ,9,10 = X to balance the equation mod 11.
The syndrome is a particular weighted check sum of x.
From the beginning of 2007 a 13 digit ISBN number, with a different check digit calculation,
has been used.
The expression S(x) =
ixi for x = x1x2 · · · x10 is called the syndrome of x in this code.
8 CHAPTER 1. INTRODUCTION
Error Detection and Correction Codes
Now suppose that an (8-bit even parity) ASCII codeword is transmitted and some noise causes one of the bits to change. That is, a ‘0’ becomes a ‘1’ or a ‘1’ becomes a ‘0’.
We say the codeword is corrupted to a corrupted codeword or just to a “word” and denote this by codeword word.
For example
11100001 10100001
If the decoder at the destination is set up to expect 8-bit even parity code words, it will recognise tha
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com