<p>A single-input-single-output communication channel is to be used repetitively. Denote by <span class="math-container">$X_i \in \mathcal X$</span> the input at time <span class="math-container">$i$</span> and by <span class="math-container">$Y_i \in \mathcal Y$</span> the output at time <span class="math-container">$i$</span>.</p>
<p>Assume the channel is <strong>not memoryless</strong> and <span class="math-container">$Y_i$</span> depends on some of the previous inputs and/or outputs in a particular way (that is the same through all <span class="math-container">$i$</span>). For example, <span class="math-container">$Y_i$</span> might depend on <span class="math-container">$X_i$</span> as well as <span class="math-container">$X_{i-1}$</span> through transition probabilities <span class="math-container">$P_{Y|X,X'}(\cdot|\cdot,\cdot)$</span> for all <span class="math-container">$i$</span> (where <span class="math-container">$X'$</span> represents the input at the previous transmission). For another example, <span class="math-container">$Y_i$</span> might depend on <span class="math-container">$X_i$</span> as well as <span class="math-container">$Y_{i-1}$</span> through transition probabilities <span class="math-container">$P_{Y|X,Y'}(\cdot|\cdot,\cdot)$</span> for all <span class="math-container">$i$</span> (where <span class="math-container">$Y'$</span> represents the output after the previous transmission).</p>
<p>We study the input-output relations of <span class="math-container">$n$</span> consecutive channel uses. <span class="math-container">$\{ X_i \}_{i=1}^n$</span> are the inputs and <span class="math-container">$\{ Y_i \}_{i=1}^n$</span> are the corresponding outputs. We represent the dependency relations of these by a graph with <span class="math-container">$2n$</span> nodes (one for each <span class="math-container">$X_i$</span> and for each <span class="math-container">$Y_i$</span>), where there is a directed edge whenever there is a dependency. See the examples in the figures below.</p>
<p><a href="https://i.sstatic.net/TM3sl1XJ.png" rel="nofollow noreferrer">Figure 1</a></p>
<p><a href="https://i.sstatic.net/pBPyRUBf.png" rel="nofollow noreferrer">Figure 2</a></p>
<p><a href="https://i.sstatic.net/6O3n30BM.png" rel="nofollow noreferrer">Figure 3</a></p>
<p>Call this graph the <em>dependency graph</em> of the channel.</p>
<p>My question is: <strong>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?</strong></p>

CC BY-SA 4.0
2024-05-18T12:08:18.213Z
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?
Kai
CC BY-SA 4.0
2024-05-20T23:32:23.427Z
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)
Euclid
<reference-request><graph-theory><it.information-theory>
Channel Capacity & Dependency Graph
Euclid
# Channel Capacity & Dependency Graph

(Asked by: username_0 on 2024-05-18)

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](https://i.sstatic.net/TM3sl1XJ.png)

[Figure 2](https://i.sstatic.net/pBPyRUBf.png)

[Figure 3](https://i.sstatic.net/6O3n30BM.png)

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?**

**Tags:** reference-request, graph-theory, it.information-theory
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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)  

---

## 0 answers

