1
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

From a recent relevant paper:

Shannon investigated the zero-error information transmission by considering codes that must allow for a correct decoding with probability one, instead of an asymptotic probability one. This radically changes the nature of the problem, as the exact values of the non-null transition probabilities of the channel do not appear anymore. Shannon defined the zero-error capacity of a channel as the maximum asymptotic rate that can be reached with error probability exactly zero. The characterization of the zero-error capacity of an arbitrary channel is a wide open problem, that shares deep connections with Graph Theory.

Graph related parameters such as the $\theta$ function and spectral properties of adjacency matrices also come into play here. I believe there are variations on this where actual probabilities also play a part, but I am not an expert on this.

The review paper [2] is probably a good place to start. Some names who worked in this area are Korner, Lovasz, Orlitsky and of course Shannon.

References:

  1. C. Shannon, “The zero error capacity of a noisy channel,” IRE Transactions on Information Theory, vol. 2, no. 3, pp. 8–19, 1956.

  2. J. Körner and A. Orlitsky, “Zero-error information theory,” IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2207–2229, 1998.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the answer, but I do not see the connection to the zero-error capacity problem. The problem I tried to describe is the following. Fix (discrete) input and output alphabets $\mathcal X$ and $\mathcal Y$. The channel need not be memoryless; the output at each transmission might have a specific dependency to the past inputs & outputs. I.e., at transmission $n$, the output $Y_n$ will depend on $X_n$ as well as other quantities (e.g. $X_{n-1}$ and/or $Y_{n-1}$). We however assume that the dependency is the same as $n$ varies (other than a few possible first cases in the beginning) $\endgroup$
    – Euclid
    Commented May 20 at 23:24
  • $\begingroup$ Examples: 1) If $Y_n$ depends only on $X_n$, the channel is indeed memoryless, and we deal with transition probabilities $P_{Y|X}(\cdot|\cdot)$. This case is Fig.1 in my original post. 2) If $Y_n$ depends on $X_n$ and $X_{n-1}$, the channel has memory $1$, and we deal with transition probabilities $P_{Y|X,X'}$ where $X$ represents the current input and $X'$ the previous input. This case is Fig.2. 3) If $Y_n$ depends on $X_n$ and $Y_{n-1}$, we deal with transition probabilities $P_{Y|X,Y'}$ where $X$ represents the current input and $Y'$ the previous output. This case is Fig.3. $\endgroup$
    – Euclid
    Commented May 20 at 23:26
  • $\begingroup$ If we represent this particular dependency by a graph (given in Figures 1, 2, 3 in my original post), my question is: Has channel capacity been studied in connection with the properties of its corresponding graph (called dependency graph in my original post)? $\endgroup$
    – Euclid
    Commented May 20 at 23:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .