Determining Channel Capacity and diagonalizing matrix D

Determining Channel Capacity

For a particular Trellis diagram we define a connection matrix D. Hence for k states the size of the matrix is k × k. D is called the connection matrix because its entries dij = number of Trellis paths from Si to Sj. For example

Figure 1 Illustration of connection matrix D for two states S sub 0 and S sub 1

Notice that elements in a particular ith row represent the number of paths from Si.
Figure 2 Highlighted illustration of connection matrix D for two states S sub 0 and S sub 1

The connection matrix D is therefore a transition matrix from the present state to next state. Therefore after a certain time t and hence t steps, for a particular state Si can we compute the possible number of paths (and hence possible number of sequences) that can reach the same Si state? The possible number of sequences at t steps can be computed by applying D. This is illustrated below.

If

n sub j at time t is the number of Trellis paths reaching S sub j in t steps
then
vector n(t) = [n sub 0 at t, n sub 1 at t, ellipsis, n sub k-1 at t]
If t = 0 ⇒ no steps are taken and hence  vector n(0) where
ybar: 0 0 0 0 0 ... From S sub 0 at t = 0 implies xbar: +1 -1 +1 -1 +1 ... or S sub 1 at t = 0 implies xbar: -1 +1 -1 +1 -1 ...
then, at t > 0
vector n(t) = vector n(0) times D sup t
For example, if
vector n(0) = [1, 0] and D = [1, 1; 1, 1]
which is graphically
Figure 3 Step-1 construction of Trellis diagram at time t = 0

Then, at t = 1
vector n(1) = vector n(0) times D sup 1 = [1, 0] times [1, 1; 1, 1] = [1, 1]
Hence the Trellis diagram is
Figure 4 Step-2 construction of Trellis diagram at time t = 1

Similarly at t = 2

vector n(2) = vector n(0) times D sup 2 = [1, 0] times [2, 2; 2, 2] = [2, 2]
whose diagram is
Figure 5 Step-3 construction of Trellis diagram at time t = 2

Therefore if

n sub T at time t is the possible number of Trellis paths in t steps (reaching all S sub j)
then
n sub T at time t is equal to for j = 0 to k-1, sum of all n sub j at time t
Hence at t = 3
vector n(3) = vector n(0) times D sup 3 = [2, 2] times [1, 1; 1, 1] = [4, 4]
Since by definition
vector n(t) = [n sub 0 at t, n sub 1 at t, ellipsis, n sub k-1 at t]
and k = 2 for the two states S0 and S1 at t = 3
vector n(3) = [n sub 0 at 3, n sub k-1 at 3]
Hence the possible number of Trellis paths (reaching  S sub 0 and  S sub 1 ) at t = 3 is
n sub T at time 3 is equal to for j = 0 to 2-1, sum of all n sub j at time 3 = n sub 0 at 3 plus n sub 1 at 3 = 4+4 = 8

We know that  vector n(3) = [4, 4] and hence  n sub 0 at 3 is equal to 4 which implies there are four possible ways (same as four possible Trellis paths) from state S0 at t = 0 to S0 at t = 3. Graphically,

Figure 6 Step-4 construction of Trellis diagram at time t = 3 higlighting (red) only one Trellis path
Figure 6 Step-4 construction of Trellis diagram at time t = 3 higlighting (blue) only one Trellis path
Figure 6 Step-4 construction of Trellis diagram at time t = 3 higlighting (orange) only one Trellis path
Figure 6 Step-4 construction of Trellis diagram at time t = 3 higlighting (green) only one Trellis path
And hence similarly for  n sub 1 at 3 is equal to 4 or four possible ways (same as four possible Trellis paths) from state S0 at t = 0 to S1 at t = 3. Therefore the possible number of Trellis paths from S0 at t = 0 to S0 and S1 at t = 3 is eight,  n sub T at 3 is equal to 8 .

Hence

 n sub T at t gives the possible number of distinct messages (sequences) that can be sent by the channel in exactly t steps.

Since the number of bits required to represent symbols in  n sub T at t sequences (in t steps) is
log base 2 of N sub T at t
the possible number of distinct messages n sub T at t corresponds to
(1 over t) times log base 2 of N sub T at t
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)

Alternative to determining  n sub T at t for computing channel capacity

In practice it is hard to compute  vector n(t) and  vector n(0) , in  N(t) = N(0) times D sup t . Therefore 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.

Let

lambda: eigenvalue, (vector) psi: eigenvector, D times psi = lambda times psi and det(D - lambda times I) = 0
Note that
D times Psi sub 0 = lambda times Psi sub 0, D times Psi sub 1 = lambda times Psi sub 1, ellipsis, D times Psi sub k-1 = lambda times Psi sub k-1, and Psi sub i transpose times Psi sub j = 0 iff i is not equal to j
where k is the number of states. Also let the orthonormal  Psi sub i eigenvectors of D form the columns of the modal matrix
U = [Psi sub 0, Psi sub 1, ellipsis, Psi sub k-1]
Then
D = U inverse times Lambda times U
Thus
D squared = U inverse times Lambda squared times U

In general

D sup t = U inverse times Lambda sup t times U
where
Lambda sup t = [lambda sub 0 sup t, 0 , ..., 0; 0, lambda sub 1 sup t, ..., 0; ellipsis; 0, 0, ..., lambda sub k-1 sup t]
Therefore
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)
where Cj are constants because they are derived from U−1, U and their constants.

If λm is the largest positive eigenvalue of D, then for very large t

n sub T at t tends to product (C sub m times lambda sub m sup t)
Thus
log base 2 of n sub T at t is equal to (log base 2 C sub m) plus (t times log base 2 lambda sub m)
Plugging this into the channel capacity
C = limit as t tends to infinity of ((1 over t) times log base 2 of N sub T at t)
the maximum channel capacity is
C sub m = limit as t tends to infinity of ((1 over t) times (log base 2 of C sub m + t times log base 2 of lambda sub m))
But as t → 0,  log base 2 of (C sub m over t) tends to 0 thus the maximum channel capacity is
C sub m = log base 2 of lambda sub m

Example

D = [1, 1; 1, 1] and det(D - lambda times I) = lambda squared - 2 times lambda
From det(DλI) we get
lambda equals 0 and 2
Hence for maximum channel capacity
lambda sub m = 2 and C sub m = log base 2 of lambda sub m = 1
Note that Cm = H(X) implies lossless channel.

Next:

Summary (p:3) ➽