1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Martin Leslie
    Mar 25, 2012 at 13:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.