# Coding theorems for discrete noisy channels with memory

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

• 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. Oct 8, 2021 at 11:43