2
$\begingroup$

Consider the following situation, I want to send one of two bitstrings, A or B, to a receiver. Clearly, I can do this by sending the shortest, but is there a better way? It seems that the requirement that one of either should arrive should allow us to save on bits.

To give a specific application: say the receiver and I have a DFA, and I want to send some word in the language described by the automaton. I can do this by encoding a path over the automaton as an n-ary string. But if there are several paths over the automaton, I don't care which the receiver decodes, so long as it decodes to the right word.

Is there research into this question? Are there google-able phrases that I don't know about?

Also, if we use a probabilistic DFA, it defines a probability distribution over the words in its language. By the Kraft inequality, there exists a coding for this probability whereby the length of the code for word W is equal to the logarithm of P(W). However if we use a specific path A over the automaton to encode W, that path may only contribute part of the probability mass of P(W). Say there are two paths A and B that produce W, so that P(A) + P(B) = P(W). Is there a scheme that allows us to send a message with length log(P(W)) that decodes into either A or B?

Improve this question
$\endgroup$
4
  • $\begingroup$ The domain of possible bitstrings is not restricted, in particular re length? Because if the domain of bitstrings is restricted, then it's trivially obvious that you can use a shorter encoding. Sort all bitstrings in the domain, and send the position of A instead of A. $\endgroup$
    – MSalters
    Jan 15, 2013 at 14:54
  • $\begingroup$ @MSalters: I don't understand. Do you mean that any bitstring x from a restricted set can be compressed (by encoding the set and the index of x)? That's just compression, isn't it? The key point here is that I want A or B to arrive, and whether this ambivalence allows a scheme to get my message across in less than min(l(a), l(B)) bits. $\endgroup$
    – Peter
    Jan 15, 2013 at 15:42
  • $\begingroup$ Yes. Assume that the domain is all possible bitstrings except just "0". Then 1 can be coded as 0, 10 as 1, 11 as 10, etc. This is of course compression, and that answers your very question wh ether it's optimal to just send A (No, send compressed(A) instead). That would be trivial, so that's why I wanted to clarify the domain assumptions. $\endgroup$
    – MSalters
    Jan 15, 2013 at 15:59
  • 1
    $\begingroup$ I guess I would say that the sender and receiver are already using some pre-arranged compression and sending the compressed messages over a basic channel. However, since the decompressor translates both A and B to the desired output, that seems like a fact you should be able to use somehow to shorten the message further. So, if it helps, we can assume that A and B are both reasonably/maximally compressed (ie. random). $\endgroup$
    – Peter
    Jan 16, 2013 at 10:29

1 Answer 1

Reset to default
1
$\begingroup$

I can answer my own question here. The original code over $S = \{A, B, \ldots\}$ corresponds (by the Kraft inequality) to a probability distribution on $S$. I can partition S by the subsets I'm ambivalent about, so in $S'$, there's an element $a = \{A, B\}$ to denote that I don't care about the difference between $A$ and $B$.

This gives me a simple probability distribution on $S'$: $p(a) = p(A) + p(B)$.

By the Kraft inequality, again, there is a coding that corresponds to this distribution, so that I can use an algorithm like arithmetic coding to achieve acode of length $- \log p(a) = - \log p(A) + p(B)$.

Improve this answer
$\endgroup$

Your Answer

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

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