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

Notice that elements in a particular ith row represent the number of paths from Si.

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

then If t = 0 ⇒ no steps are taken and hence where then, at t > 0 For example, if which is graphically

Then, at t = 1 Hence the Trellis diagram is

Similarly at t = 2

whose diagram is

Therefore if

then Hence at t = 3 Since by definition and k = 2 for the two states S0 and S1 at t = 3 Hence the possible number of Trellis paths (reaching and ) at t = 3 is

We know that and hence 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,

And hence similarly for 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, .

Hence

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 sequences (in t steps) is the possible number of distinct messagescorresponds to The channel capacity or maximum information rate or maximum mutual information between X and Y for such class of channels with memory is

## Alternative to determining for computing channel capacity

In practice it is hard to compute and , in . Therefore it is hard to compute the channel capacity by the approach of determining . An easier approach is to diagonalize D.

Let

Note that where k is the number of states. Also let the orthonormal eigenvectors of D form the columns of the modal matrix Then Thus

In general

where Therefore 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

Thus Plugging this into the channel capacity the maximum channel capacity is But as t → 0, thus the maximum channel capacity is

Example

From det(DλI) we get Hence for maximum channel capacity Note that Cm = H(X) implies lossless channel.

Next:

Summary (p:3) ➽