Determining Channel Capacity

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 d_ij = number of Trellis paths from S_i to S_j. 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 i^th row represent the number of paths from S_i.

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 S_i can we compute the possible number of paths (and hence possible number of sequences) that can reach the same S_i state? The possible number of sequences at t steps can be computed by applying D. This is illustrated below.

❶

$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 S₀ and S₁ 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 S₀ at t = 0 to S₀ 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 S₀ at t = 0 to S₁ at t = 3. Therefore the possible number of Trellis paths from S₀ at t = 0 to S₀ and S₁ 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$