Trellis diagram and its application

Recall the system with dual binary channel

Figure 1 DMS X sends symbol x(n -1) and x(n) to form y(n)

whose state diagram is
Figure 2 State daigram for Fig 1 system

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  x over y is  -1 over -2 , the Trellis diagram is

Figure 3 Trellis diagram for -1 over -2 relation

However when  x over y is  +1 over 0 the Trellis diagram is
Figure 4 Trellis diagram for +1 over 0 relation

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

Therefore the combined diagram (completed Trellis diagram) for various cases of  x over y relation is
Figure 7 Completed Trellis diagram for various x over y relations

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

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 ...

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


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.


Determining channel capacity
Alternative to determining nT(t) for computing channel capacity (p:2) ➽