Lecture 10 Summary (Information Theory)

Lecture09 Summary

Trellis diagrams are basically state diagrams stretched out in time. For example let us consider two states S₀ and S₁. At time t = 0 the states as nodes are depicted as ◯ on the other hand at time t = 1 the states as nodes are depicted as ⬤.
For example for various cases of $x over y$ relation
If knowledge of x̅ (i.e, S(t = 0)) lets us know all possible output (generated) sequence y̅, then this channel with memory is called non-catastrophic or conditionally catastrophic.
If a channel does not incorporate a noise channel but there is still information loss, then such channels are called noise-less channels.
Channel capacity can be used to determine maximum information rate for class of inofrmation channel which are
- a noise-less channel that is non-catastrophic,
- either states S(t = 0) or S(t = t_final) is known, and
- output sequence y̅ is also known.

❶

The channel capacity or maximum information rate or maximum mutual information between X and Y for such class of channels with memory is

$C = limit as t tends to infinity of ((1 over t) times log base 2 of N sub T at t)$

where $n sub T at t$ is the possible number of Trellis paths in t steps reaching all S_j

$n sub T at time t is equal to for j = 0 to k-1, sum of all n sub j at time t$

such that $N(t) = [n sub 0 at t, n sub 1 at t, ellipsis, n sub k-1 at t]$ .
It is hard to compute the channel capacity by the approach of determining $n sub T at t$ . An easier approach is to diagonalize D ( $N(t) = N(0) times D sup t$ ). Thus

$D sup t = U inverse times Lambda sup t times U$

and

$n sub T at t is equal to for all j = 0 to k-1, sum of products (C sub j times lambda sub j sup t)$

C_j are constants because they are derived from U⁻¹, U and their constants.
In general you do not need to compute all C_j, just C_m. The maximum channel capacity is

$C sub m = log base 2 of lambda sub m$

where λ_m is the largest eigenvalue; $matrix D times psi = lambda times psi$ .

✪

Lectures on Information Theory