Trellis diagrams are basically state diagrams stretched out in time. For example let us consider two states S0 and S1. 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 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 = tfinal) 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
where is the possible number of Trellis paths in t steps reaching all Sj
such that .
It is hard to compute the channel capacity by the approach of determining . An easier approach is to diagonalize D (). Thus
Cj are constants because they are derived from U−1, U and their constants.
In general you do not need to compute all Cj, just Cm. The maximum channel capacity is