Trellis diagram and its application

Recall the system with dual binary channel

whose state diagram is

## Trellis diagram

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 input x and output y when the input over output relation is , the Trellis diagram is

However when is the Trellis diagram is

Hence the combined diagram for the two cases of relation is complicated. However to avoid complication a clockwise arc is used such that it indicates

• for the first state S0, the first output arrow (labelled 1) encountered by the arc is for output y = −2 and the second output arrow (labelled 2) encountered is for output y = 0.

• And similarly the reverse for S1 state.
Therefore the combined diagram (completed Trellis diagram) for various cases of relation is

## Non-catastrophic channel and Noise-less channel

Recall that the duo-binary channel contains catastrophic sequence, i.e, where two or more produce the same thus making ambiguous. For example if we have

Since the channel has memory, that is, the sequence has a particular relationship with the observed sequence , if the sequence of the initial state (either of S0 or of S1 as the initial state) is known, there is NO information loss.

Recall the definition that a channel with memory is catastrophic if there is same output sequence for two for more different sequences .

But if knowledge of (i.e, S(t = 0)) lets us know all possible output (generated) sequence , 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

Suppose

• a noise-less channel that is non-catastrophic,
• either states S(t = 0) or S(t = tfinal) is known, and
• output sequence is also known.
Then, the sequence sent to give the output can be figured out. In other words, all information from arrives at the output and hence lossless information channel.

[this statement is true because these channels satisfy corollary-1 pg.1288 Application of Set-Membership Techniques to Symbol-by-Symbol Decoding for Binary Data-Transmission Systems R.B Wells]

For such class of information channels maximum information rate can be determined from channel capacity.