2
$\begingroup$

Can we implement a reduced-error transmission over a channel with error frequency having $\liminf<\frac{1}{2}$ and $\limsup>\frac{1}{2}$?


We know that if a channel with error flips (in the limit) strictly less than 1/2 of the bits, we can recover asymptotically error-free transmission with an appropriate code. By bit-inversion, this applies if, in the limit, the channel flips strictly more than 1/2 of the bits.

These arguments don't actually deal with the limit, though... they simply require $$\limsup_{n\to\infty}{\frac{E\cap\left[0,n\right)}{n}}<\frac{1}{2}\text{ or }\liminf_{n\to\infty}{\frac{E\cap\left[0,n\right)}{n}}>\frac{1}{2},$$ taking $E$ to be the set of locations of the flipped bits. That is, we recover asymptotically error-free transmission if $E$ has upper density $<\frac{1}{2}$ or lower density $>\frac{1}{2}$.

Of course, there are channels with error density $\frac{1}{2}$ with capacity 0, so there's not always a useful code.

This leaves a gap I find interesting. Can we say anything about channels with error having lower density $<\frac{1}{2}$ and upper density $>\frac{1}{2}$? In particular, can we reduce the upper density by use of a (possibly standard) error-correcting code?

For the sake of argument, suppose we have a binary error channel that introduces errors with upper density $\frac{3}{4}$ and lower density $\frac{1}{4}$. Can we use this to implement a transmission with reduced upper density of error? (As a concrete goal - can we get the upper density of error below $\frac{5}{8}$?)

I suspect we can't guarantee asymptotically error-free transmission, but if it's possible, such a scheme would obviously answer my question. In any case, I have no objection to a code that sacrifices an increase in lower density of error to achieve a decrease in upper density of error.

$\endgroup$
  • $\begingroup$ Normally, there is some model for the noise, such as independent chances for flipping bits. Which model are you assuming that would produce that behavior? $\endgroup$ – Douglas Zare Oct 21 '14 at 15:00
  • $\begingroup$ @DouglasZare - I was actually noting that I think the standard results are independent of the model chosen, if we speak in terms of limiting error frequency; that is, they're valid against the adversarial model of noise with the given density. I mean to assume that same worst-case model, since I'm coming at this from the perspective of computability. $\endgroup$ – Eric Astor Oct 21 '14 at 17:01
  • 1
    $\begingroup$ I stand corrected that my previous answer is wrong. Thinking about this some more, the problem implies some complexity -- there must be increasingly long runs with BER bounded above 1/2 and long runs with BER bounded below 1/2. Otherwise, the cumulative BER couldn't have lim inf less than 1/2 and lim sup greater than 1/2. If you know in advance how far the limits are away from 1/2 and use an error-correcting code that works successfully in that regime, then you can send fixed-length data blocks and get an infinite number through successfully. $\endgroup$ – Dale Jun 4 '17 at 19:05
  • $\begingroup$ @Dale As it happens - this question's original motivation was resolved a few years ago, using almost exactly the method you suggest. Benoit Monin coupled that approach with list decoding, proved that infinitely many blocks would get through with positive information, and used this to show that one could essentially implement a transmission with arbitrarily small error. For reference, see lacl.fr/~benoit.monin/ressources/papers/resolution_gamma.pdf $\endgroup$ – Eric Astor Sep 21 '17 at 19:10
1
$\begingroup$

In the general case, the answer is clearly No, because the channel that flips each bit with independent probability 1/2 cannot transmit data and is within the general conditions.

If the question is, "Are there some channels with bit error rate near 1/2 through which data can be transmitted?", the answer is clearly Yes, because the channel that flips exactly every other bit can be used for asymptotically error-free communication because the receiver has to reconstruct only 1 bit of error information.

$\endgroup$
  • $\begingroup$ Sorry, that's actually not the question I asked. I asked something a little odd... If all we know about the channel is that it does not have a well-defined asymptotic bit error rate (lim sup != lim inf), can we use THAT in any interesting ways? Can we transmit data? I'm not aware of any standard examples that address this question. Or even if not, might there be some way to control the error? This still need not permit data transmission... but if it behaved as described in my question, it would be an interesting theoretical curiosity, and of use in other fields. $\endgroup$ – Eric Astor Apr 20 '15 at 3:14
  • $\begingroup$ Note that if the channel has lim sup < 1/2 or lim inf > 1/2, the answer is trivially known - which is why I excluded that in my question. $\endgroup$ – Eric Astor Apr 20 '15 at 3:20
  • $\begingroup$ @EricAstor In Dale's example, I understand the lim sup to be 1 and the lim inf to be 0. Since there can clearly be no information transmitted, Dale's example seems to answer your question. Is your understanding of what the lim sup or lim inf in this example different? You did not define very well what the limits mean when E is stochastic as it usually is. $\endgroup$ – Yoav Kallus May 19 '15 at 23:51
  • $\begingroup$ @YoavKallus Well, if E flips every other bit, the asymptotic error rate is exactly 1/2. I'm fairly certain that if E is stochastic with independent probability 1/2, then (with probability 1) the asymptotic error rate is still exactly 1/2, simply by the law of large numbers. Am I mistaken? $\endgroup$ – Eric Astor May 20 '15 at 5:01
  • $\begingroup$ @YoavKallus For clarity, by the asymptotic error rate, I simply mean the asymptotic density of bits flipped... and since it's stochastic, I probably mean to exclude events of probability 0. (I admit I'm no expert on this topic!) $\endgroup$ – Eric Astor May 20 '15 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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