Coding and Cryptography

Define a communication channel

Accepts string of symbols from finite alphabet, outputs string of symbols from another finite alphabet. Modelled by the probabilities P(y1…yn received| x1…xn sent)

Define a discrete memoryless channel

p_ij = P(bj received | ai sent) are same for each channel use and independent of past and future use.

Define channel matrix of a discrete memoryless channel

r x s stochastic matrix P=(p_ij) (where p_ij = P(bj received | ai sent)

What’s the information rate of a code

rho(C) = 1/n log2 (m) (Where n is the number of letters sent per message and m is the number of messages)

What is the error rate of a code

max x in M of P(error | x sent)

When can a channel transmit reliably at rate R

Sequence of codes of length n for which lim as n → nifty rho(Cn) + R and lim as n→infty e(Cn) = 0. (information tends to R and error tends to 0).

What is the capacity of a channel

Supremum of all reliable transmission rates

Define a code

function c: A→B where A,B alphabets

Define the codewords of c

Elements in Im(c)

When is a code c decipherable

If c* is injective

Give some codes which are always decipherable

Block codes, comma codes, prefix-free codes

State Kraft’s inequality

sum from I=1 to m of a^-li <= 1 (m is size of alphabet of A, a is size of alphabet of B, c: A → B* is a code with codewords of length l1,…,lm)

Give an equivalent condition to a prefix-free code existing

Kraft’s inequality holds

Prove a prefix free code exists iff Kraft’s inequality holds.

rewrite K inequality, (forward direction) consider all strings length s in B and each codeword as a preifx of these, make sum, divide by a^s. (backward direction) Induction, s=1 clear, use expanded K inequality and multiply by a^s, calculate strings already taken up by prefixes, room to add n_s strings of length s, done.

What does any decipherable code satisfy

Kraft’s inequality

Prove any decipherable code satisfies Kraft’s inequality.

Send R codewords in a row, simplify expression, b_l <= |B^l| =a^l, give inequality again, R root, as R to infinity, RHS tends to 1

A decipherable code with prescribed word length exists if and only if…

a prefix-free code with the same word lengths exists

Define the entropy of a random variable

H(X)=H(p1, …, pn) = -sum from i=1 to n of (pi log(pi)) = -E[log pi] (logs base 2). x1, …, xn are values te RV X takes and p1,…,pn are the probabilities of each

State Gibbs inequality

-sum(pi log(pi)) <= - sum(pi log(qi)) where (p1,…,pn) and (q1,…qn) are discrete probability distributions.

When does equality hold for Gibb’s inequality

If pi=qi

Prove Gibb’s inequality

log x = ln x/ln 2, define I, ln inequality, qi-pi situ, RHS <=0, result, equality if qi sum = 1 and qi/pi=1 for all I, so pi=qi.

Give an inequality regarding H(p1,…,pn), when does equality hold?

H(p1,…,pn) <= log n, with equality iff p1=…=pn

When is a code called optimal

When it has the smallest possible expected word length (sum pi li = E[S]) of all decipherable codes

State Shannon’s Noiseless Coding Theorem

Expected word length of a decipherable code satisfies H(X)/log a <= E[S] < H(X)/log a +1

Prove Shannon’s Noiseless Coding Theorem

lower bound: Let qi=a^(-li)/D, so sum qi=1, Gibb’s inequality, simplify, McMillans inequality (log d neg), so first result (equality with D=1, pi=qi=a^-li/D).

upper bound: construct shannon fano code, let li= roof(-log_a pi), so -log_a pi<= li < -log_a pi +1, reverse inequality and exponentiate, Krafts satisfied, so prefix code exists with (calculate E[S]).

When does equality hold in Shannon’s Noiseless Coding Theorem?

If pi=a^(-li) with sum(a^(-li)) =1

If we have some messages in A with probabilities p1,…,pm and c is an optimal prefix-free code with word lengths l1,…,lm, then give two statements we can deduce and prove them.

If pi>pl then li<=lj, else can swap the ith and jth codewords.

Among all codewords of maximal length, there must be two which only differ by the last digit, else can just delete the last digit, and as prefix-free, we get another prefix-free code with smaller expected word length.

What can we say Huffman codes are?

Optimal

Prove that Huffman codes are optimal.

Induction, base case m=2 clear. Suppose true for m-1, and suppose we combine two least likely of our m probabilities to get m-1, then E[Sm]=E[Sm-1] + p_(m-1) + p_m.

Other optimal code c’m, wlog prefix free and by prev lemma, codewords of max length differ by final symbol, (so c’m(mu_(m-1))=y0 and c’m(mu_m)=y1 for some y in {0,1}*). Make c’(m-1) be prefix free code for X_m-1, E[S’m]=E[S’_{m-1}] +pm-1+pm, E[Sm-1]<=E[S’m-1] as by induction cm-1 is optimal, so E[Sm]<=E[S’m] so cm optimal.

Define the joint entropy of X and Y

H(X,Y)= - sum over x in A, sum over y in B of [P(X=x,Y=y)logP(X=x,Y=y)]

Give an inequality with joint entropy, when does equality hold?

H(X,Y)<=H(X) + H(Y), equality iff X and Y are independent

Prove H(X,Y)<=H(X) + H(Y), equality iff X and Y are independent

Define A, B, pij, pi and qj. Apply Gibbs to pij and piqj, expand with log rules into result. Equality iff pij=piqj for all ij, or rather if independent.