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 x̅ produce the same y̅ thus making x̅ 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 x̅ has a particular relationship with the observed sequence y̅, if the sequence x̅ of the initial state (either x̅ of S0 or x̅ 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 y̅ for two for more different sequences x̅.

But 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

Suppose

Then, the sequence sent to give the output y̅ can be figured out. In other words, all information from x̅ arrives at the output y̅ 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.

❺

Next:

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

✪