Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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 www.ee.caltech.edu/EE/Faculty/rjm/papers/PostFinal.pdf 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
add comment

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.