1
$\begingroup$

In Shannon's paper on communication theory, two types of discrete channel are defined:

  • the "noiseless channel", in which the channel behaves like a finite state machine - it's deterministic but it has some hidden state that depends on previous inputs

  • the "noisy channel", where the output depends stochastically on the input, but there is no hidden state - the output depends only on the current input and not on previous inputs.

Since these definitions differ in two different ways, one might more accurately call them "noiseless channels with memory" and "noisy channels without memory." One could then also define a noisy channel with memory, which would combine the interesting features of both types of channel. Such a channel would have a hidden state that depends stochastically on the previous state as well as the current input. As far as I remember from the last time I read it in detail, Shannon doesn't define anything like that in his paper.

I'm interested in whether there are analogs of Shannon's coding theorems that have been worked out for these "noisy channels with memory". That is, can one define and calculate a channel capacity for them?

I imagine this is something that would have been worked out in detail soon after Shannon's paper, but it's one of those things that's hard to search for if you don't know the correct name. So I'm looking either for the correct terminology to search for or (ideally) the papers where this stuff was first worked out.

Edit: the current answers address some particular special cases of channels with memory. However, what I'm really interested in is a solution to the general case, for a discrete noisy channel with memory, along the lines of the coding theorems in Shannon's paper.

There are many ways one could go about defining such a thing. The following might be a reasonable first attempt, though I won't quibble if there is a resource that defines it slightly differently.

Let $X$, $Y$, $H$ and $F$ be finite sets. $X$ and $Y$ are the input and output alphabets, $H$ is the set of possible (hidden) channel states, and $F$ is an optional alphabet of feedback outputs, which the sender has access to. (These might be the same as the channel's outputs, but they could in general be different. I'm including this extra output because I suspect it would make a difference to the channel capacity.)

Then define the hidden state's dynamics as a "Markov chain with input", i.e. they are defined by a fixed probability distribution $p(H_{t}|H_{t-1},X_t)$. (One would probably want to require this to have some kind of ergodicity property, such that it has a unique stationary state whenever the inputs are drawn from a stationary process, but for now I'm not sure exactly what condition is needed for that.) Then let the output and feedback output be functions of the hidden state, i.e. $Y_t = y(H_t)$, $F_t = f(H_t)$.

Then the idea is that the sender provides the inputs $X_t$ and has access to the feedback outputs $F_t$, and the receiver has access only to the outputs $Y_t$. The question is whether we can calculate a channel capacity for such a channel, as a function of the probability distribution $p(H_{t}|H_{t-1},X_t)$ and the functions $f$ and $y$.

$\endgroup$
1
  • 1
    $\begingroup$ A general solution might not exist yet, as even for some special cases the capacity is not known exactly. I have added a recent publication that also summarizes results in that direction. $\endgroup$ Oct 8, 2021 at 11:43

2 Answers 2

0
$\begingroup$

The content of Part I, what Shannon calls a "encoding a noiseless channel", is in the current literature rather called a "encoding the source". Indeed, the finite-state machine that he considers actually refers to the source - and the result he gets is know as his "first theorem" or Source coding theorem. In part II, when he really deals with a (noisy) channel, he does not (IIRC) explicitly deal with the issue of channel with-without memory (or, equivalenty, independent vs correlated noise). His theory is quite general, though.

Some concrete considerations for channels with memory can be found in any textbook. For example, in Cover & Thomas book, see exercises 7.3 and 7.36.

$\endgroup$
0
$\begingroup$

I want to add reference to some papers (and references therein) that deal with channels with memory that might help starting your literature research.

[1] Caire, Giuseppe; Shamai, Shlomo, On the capacity of some channels with channel state information, IEEE Trans. Inf. Theory 45, No. 6, 2007-2019 (1999). ZBL0957.94013.
[2] Gel’fand, S. I.; Pinsker, M. S., Coding for channel with random parameters, Probl. Control Inf. Theory 9, 19-31 (1980). ZBL0427.94007.
[3] Mushkin, Mordechai; Bar-David, Israel, Capacity and coding for the Gilbert-Elliott channels, IEEE Trans. Inf. Theory 35, No. 6, 1277-1290 (1989). ZBL0695.94006.
[4] Huleihel, Bashar; Sabag, Oron; Permuter, Haim H.; Kashyap, Navin; Shitz, Shlomo Shamai, Computable upper bounds on the capacity of finite-state channels, ZBL07391893.

Further, as mentioned by leonbloy, many books on information theory contain sections on channels with memory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.