A single-input-single-output communication channel is to be used repetitively. Denote by $X_i \in \mathcal X$ the input at time $i$ and by $Y_i \in \mathcal Y$ the output at time $i$.

Assume the channel is not memoryless and $Y_i$ depends on some of the previous inputs and/or outputs in a particular way (that is the same through all $i$). For example, $Y_i$ might depend on $X_i$ as well as $X_{i-1}$ through transition probabilities $P_{Y|X,X'}(\cdot|\cdot,\cdot)$ for all $i$ (where $X'$ represents the input at the previous transmission). For another example, $Y_i$ might depend on $X_i$ as well as $Y_{i-1}$ through transition probabilities $P_{Y|X,Y'}(\cdot|\cdot,\cdot)$ for all $i$ (where $Y'$ represents the output after the previous transmission).

We study the input-output relations of $n$ consecutive channel uses. $\{ X_i \}_{i=1}^n$ are the inputs and $\{ Y_i \}_{i=1}^n$ are the corresponding outputs. We represent the dependency relations of these by a graph with $2n$ nodes (one for each $X_i$ and for each $Y_i$), where there is a directed edge whenever there is a dependency. See the examples in the figures below.

Figure 1

Figure 2

Figure 3

Call this graph the dependency graph of the channel.

My question is: Are there works in the literature where channel capacity or other quantities of the channel are studied in connection with the properties of its dependency graph?

  • $\begingroup$ Throwing away the actual channel matrix changes the model from a probabilistic to a possibilistic one. Taint analysis could take care of that. Have you checked for sources on that topic? $\endgroup$
    – Kai
    Commented May 18 at 12:08
  • $\begingroup$ It is not quite "throwing away the actual channel matrix". The catch is that the channel is not necessarily memoryless. At transmission $n$, the output $Y_n$ might be depending on $X_n$ as well as other quantities (such as $X_{n-1}$ and/or $Y_{n-1}$). There is still a transition matrix; it is just larger. Instead of $P_{Y|X}$, we would have transition probabilities for instance of the form $P_{Y|X,X'}$ or $P_{Y|X,Y'}$ (where $X'$ represents the previous output and $Y'$ represents the previous output, if the current output depends on them) $\endgroup$
    – Euclid
    Commented May 20 at 23:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.