Problem-solving recipes

A step-by-step procedure for every problem type this course teaches — what to do first, what to do next, and how to tell which case you're in.

What are you being asked to do?

Start with what you're actually being asked to produce.

Given a Markov chain's transition matrix, need its long-run distribution — solve for the stationary distribution.

A proposed function for measuring information or surprise, need to know if it can even be a valid measure — test it for additivity.

A code's minimum distance and a received word, need the correction radius or the decoded codeword — the correction-radius recipe.

A message and a CRC generator polynomial, need the transmitted codeword, or need to check a received word — the same recipe covers both directions.

A source block and its reconstruction, need the distortion — pick Hamming or squared error based on the alphabet, then compute the per-symbol distortion.

Markov chains

Solve for a Markov chain's stationary distribution

Use when: you have a Markov chain's transition matrix $P$ and need the distribution $\boldsymbol\pi$ satisfying $\boldsymbol\pi P=\boldsymbol\pi$

Goal: the exact stationary distribution $\boldsymbol\pi$ , with entries nonnegative and summing to $1$

Stationary distributions

What makes a valid information measure

Test a candidate surprise function for additivity

Use when: you have a candidate function $s(p)$ meant to measure information or surprise, and need to check whether it satisfies $s(pq)=s(p)+s(q)$ for independent events

Goal: a definite pass or fail on the additivity requirement, using one concrete numeric pair as a fast screen

Why logarithms

Error-correcting and linear codes

Find a code's correction radius and decode by nearest codeword

Use when: you have a code's minimum distance (or the codewords needed to find it) and a received word, and need the guaranteed correction radius, the decoded codeword, or both

Goal: the correction radius $t=\lfloor(d_{min}-1)/2\rfloor$ , and the nearest codeword to the received word

Hamming distance and minimum distance

Compute a CRC codeword, and check a received word against it

Use when: you have a message, a generator polynomial $g(D)$ , and either need to produce the transmitted codeword or need to check whether a received word passes the CRC test

Goal: the transmitted codeword $x$ , or a definite pass/fail verdict on a received word

CRC and error detection

Rate-distortion theory

Compute a block's per-symbol distortion

Use when: you have a source block $x^n$ and its reconstruction $\hat x^n$ , and need the total or per-symbol distortion under Hamming or squared-error distortion

Goal: the per-symbol distortion $d(x^n,\hat x^n)=\frac1n\sum d(x_i,\hat x_i)$ , using the measure that matches the alphabet

Distortion measures (Hamming, squared error)