MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'd like to know if there's any literature about information channels of the following sort.

Sender can transmit a 0 or a 1 on each clock cycle --- but with the side condition that all the delays between sending a 1 and sending the very next 1 must belong to a prescribed set ("the lengths of the permitted dots-and-dashes") of positive integers (possibly infinite).

Solving some elementary recursion relations computes the entropy of such channels. Curiously, quite different sets of dots-and-dashes yield the same entropy and thus give channels of the same capacity.

For example, {2,3} and {1,5}. Of course one can see this algebraically. But also bijectively: the sender using {2,3} could amalgamate each "3" with the next dash, effectively translating any {2,3}-code into a {2,5,6}. The other sender using {1,5} could so the same thing with each "1". Composing one translation with the inverse of the other does the job (up to a bounded number of clock cycles).

But the bijections aren't always so simple...try {2,5,8} and {3,5,7,9}!

So I'd like to know about the structure of the set of pairs of codes with the same capacities and bounds on the complexity of bijections as a function of the complexity of the codes...or anything else that happens to be known about these codes.

share|cite|improve this question
I don't know a lot about this but these are called "constrained noiseless channels" or "discrete noiseless channels" or some combination of such words. They are discussed in Shannon's 1948 paper. See for complete proofs of Shannon's results. – Martin Leslie Mar 25 '12 at 13:45
Thanks for that reference and the terminology. – David Feldman Mar 25 '12 at 18:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.