RETURN

Existence of Code

A source code $C$ for a random variable $X$ is a mapping from $\mathcal{X}$ to $D^*$

  • $X$: the range of $X$
  • $D$-ary alphabet is $\mathcal{D}={0,1,\cdots,D-1}$
  • $C(x)$: codeword for $x$
  • $l(x)$: length of $C(x)$
  • $L(C)=\sum_{x\in\mathcal{X}}p(x)l(x)$: the expected length of a source code $C(x)$ for a random variable
  • rate $R$: average length

Nonsigular code

  • every element of the range $X$ maps into a different string in $D^*$
  • $C^*$: extension of a code $C$ is mapping from finite length strings of $X$ to finite-length strings of $D$, $C(x_1x_2\cdots x_n)=C(x_1)C(x_2)\cdots C(x_n)$
  • Uniquely decodable: extension is nonsigular

Prefix Code (instantaneous code)

  • no codeword is a prefix of any other codeword
  • Tree representation
    • Kraft Inequality (1949): For any instantaneous code over an alphabet of size $D$, the codeword lengths $l_1,l_2,\cdots,l_m$ must satisfy the inequality $\sum_{i=1}^mD^{-l_i}\leq 1$
    • Conversly, given codeword satisfy above inequality, the prefix code exists.
  • Interval representation
    • Extended Kraft Inequality: For any countably infinite set of codewords

Optimal Codes

  • optimal: $\sum_{p_il_i}$ is minimal
  • optimization problem: Lagrange $$\min_{l_i} L=\sum p_il_i\\sum D^{-l_i}\leq 1$$
  • $p_i=D^{-l_i},l_i=-\log p_i,L^*\geq H_D(X)$
  • Bounds: $H_D(X)\leq L^*<H_D(X)+1$
  • Shannon codes: $l_i=\lceil\log_D\frac{1}{p_i}\rceil$

Encode $n$ symbols together (block encode to remove 1 in $H_D(X)+1$)

  • $\frac{H(X_1,X_2,\cdots,X_n)}{n}\leq L^<\frac{H(X_1,X_2,\cdots,X_n)}{n}+\frac{1}{n}$, if stationary stochastic process, $L^\rightarrow H(\mathcal{X})$
  • shortcome: alphabet has $|X^n|$

Wrong code

  • The expected length under $p(x)$ of the code assignment $l(x)=\log\frac{1}{q(x)}$: $H(p)+D(p|q)\leq E_pl(x)<H(p)+D(p|q)+1$

Kraft Inequality for Uniquely Decodable Codes (McMillan): The codeword length of any uniquely decodable $D$-ary code must satisfy the Kraft inequality $\sum_{D}^{-l_i}\leq 1$. Conversely, given a set of codeword satisfy this inequality, it is possible to construct a uniquely decodable with these codeword lengths. (prefix code is ’no less than’ any other code)

Codes

Huffman Codes

  • $D$-ary Huffman codes (prefix code) for a given distribution: Each time combine $D$ symbols with the lowest probabilities into a single source symbol, until there is only one symbol
  • add dummy symbols to the end of the set of symbols: $1+k(D-1)$
  • optimal: $C’$ is any other uniquely decodable code, $L(C)\leq L(C’)$

Shannon Codes

  • $D$-adic distribution: $P(X=x_i)=D^{-n}$, $l_i=\log\frac{1}{p_i}=n_i$
  • Shannon codes
    • attain optimality within 1
    • $D$-adic: Shannon codes are optimal
    • $p_i\rightarrow0$: Shannon codes may be worse

For any optimal coding scheme

  • lengths are ordered inversely with probability ($p_j>p_k,l_j\leq l_k$)
  • the two longest codewords have the same length
  • two of the longest codewords differ only in the last bit

Shannon-Fano-Elias Coding

  • $F(x)=\sum_{a\leq x}p(a)$
  • modified cumulative distribution function: $\overline F(x)=\sum_{a<x}p(a)+\frac{1}{2}p(x)=F(x)+\frac{1}{2}p(x)$
  • Truncate $\overline{F}(x)$ to $l(x)$ bit, $\overline F(x)-|\overline{F}(x)|_{l(x)}\leq\frac{1}{2^{l(x)}}$
  • $l(x)=\lceil\log\frac{1}{p(x)}\rceil+1$, $\frac{1}{2^{l(x)}}\leq\frac{p(x)}{2}=\overline{F}(x)-\overline{F}(x-1)$
  • $L=\sum p(x)l(x)<H(X)+2$

Random Variable Generation

  • fair coin toss: $Z_1,\cdots, Z_n$
  • expected number of fair bits $E(T)$
  • generate variable: leaves are given symbols of $X$
  • $E(T)\geq H(X)$
    • dyadic distribution: $E(T)=H(X)$
    • otherwise: use binary expansions for the probabilities, $H(X)\leq ET<H(X)+2$

Universal Source Coding

  • minimax redundancy: $R^*=\min_q\max_{p_0}R=\min_q\max_{p_0}D(p_\theta|q)$
  • Arithmetic Coding
  • LZ77: slidinig windows
  • LZ78: Trie