I want to send one bit $x$ over a noisy channel, specifically, a binary symmetric channel with error probability $p$, where $p=(1-\epsilon)/2$ and $\epsilon$ is small. In other words, the error probability is close to 1/2, so the capacity of the channel is small.

The obvious method is to use a repetition code: repeat $x$ many times. The receiver will then use majority vote to recover $x$.

Suppose I want an overall error probability of at most $\delta$ (i.e., the probability that the receiver guesses $x$ incorrectly is at most $\delta$). How many times do I need to repeat $x$?

If $\delta$ is fixed, I can see that the number of repetitions needs to be proportional to $1/(1-h_2(p))$, where $h_2$ is the binary entropy function. My question is: what is the dependence on $\delta$?

I'm guessing we should send $c_\delta / (1-h_2(p))$ copies of $x$, for constant $c_\delta$ that depends on $\delta$; how does $c_\delta$ depend on $\delta$, asymptotically, for small values of $\epsilon,\delta$? (For example, is it something like $c_\delta \sim 1 + \log 1/\delta$?)

  • $\begingroup$ The repetition code is definitely suboptimal for the BSC (general $p$), in the sense that its performance is (much) below the Shannon bound. It requires a rate that tends to 0 to attain almost 0 probability of error (instead of $1-h(p)$. $\endgroup$
    – leonbloy
    May 11 '16 at 11:55

I think you are attacking the problem using the wrong conceptual frame.

The probability of decoding error for a repetition code of length $n$ (odd) corresponds to the event of majority of bit errors, that is, a Binomial:

$$\delta = \sum_{k=(n+1)/2}^{n} \binom{n}{k} (1-p)^{n-k} p^{k} \tag{1}$$

This gives $\delta$ as a function of $p$ and $n$; and in principle it allows the inverse calculation ($n$ as a function of given $\delta,p$). But, of course, it can be done only numerically.

A simplification can be done, assuming $n$ is large (then the above sum turns into the integral of a Gaussian density), and that $p=(1-\epsilon)/2$ , with $\epsilon \to 0^+$. But this is just math.

Here's the math.

The Binomial (which counts bit errors) tends to a Gaussian of mean $np$ and variance $n p (1-p)$. And the sum tends to an integral from $n/2$ to $\infty$, (Gaussian tail or Q function), hence, in this asymptotic approximation

$$\delta = Q\left(\frac{n/2-np}{\sqrt{n p (1-p)}}\right) \tag{2}$$ Given $p=(1-\epsilon)/2$, the argument is given by

$$ \sqrt{n} \frac{\epsilon/2}{\sqrt{\epsilon (1- \epsilon)/4}}=\sqrt{n \frac{\epsilon^2}{ 1- \epsilon^2}} \tag{3}$$

If we further assume $0<\epsilon \ll 1$ we get

$$\delta = Q( \epsilon \sqrt{n} ) \tag{4}$$

This equation relates $\delta$, $n$, and $\epsilon$. Namely

$$n = \frac{(Q^{-1}(\delta))^2}{\epsilon^2} \tag{5}$$

If you need asymptotics, you need to specify what tends to what. This is no specified in the question body.

If you want to find $n$ such that, as $\epsilon \to 0^+$ the probability of error keeps a finite constant value $\delta$, then you just use $(5)$ - the only conclusion is that $n \epsilon^2$ must be constant.

If instead you are told that $\delta \to 0$, then you can use $({\rm inverf} x)^2 \approx \log[(1-x)/\sqrt{\pi}]$ and $Q^{-1}(a)=\sqrt 2 \, {\rm inverf}(1-2a)$ Then

$$ n \approx\frac{1}{\epsilon^2} 2 \log^2 (2 \delta /\sqrt{\pi}) $$


When repeating the bit $n$ times, the error probability is

$$\delta = \sum_{i=(n+1)/2}^n {n \choose i} p^i (1-p)^{n-i}.$$

The latter is a tail of the Binomial distribution and is approximately $\exp(-cn)$ where

$$c = 0.5 \lg(0.5/p) + 0.5 \lg(0.5/(1-p)).$$

This is

$$c = 0.5 \lg(1/(1-\epsilon)) + 0.5 \lg(1/(1+\epsilon))$$

which, after applying a Taylor series approximation, is approximately (for small values of $\epsilon$)

$$c \approx -0.5 \epsilon^2 / \log 2.$$

So, we find

$$\delta \approx \exp(-0.72 \epsilon^2 n).$$

It follows that we need the number $n$ of repetitions to be approximately

$$n \approx -1.39 {\log \delta \over \epsilon^2},$$

i.e., the dependence on $\delta$ is logarithmic.

Note that we have

$$h_2(p) = -0.5 \lg p - 0.5 \lg(1-p) = 1 -0.5 \lg(1-\epsilon) - 0.5 \lg(1+\epsilon).$$

By a similar Taylor series approximation, we see that

$$h_2(p) \approx 1- 0.5 \epsilon^2/\log 2,$$


$$1/(1-h_2(p)) = 2 {\log 2 \over \epsilon^2}.$$

Therefore, the estimate $n \sim 1/(1-h_2(p))$ was actually correct (up to a constant factor, as stated in the question). In particular, when we take into account the dependence on $\delta$, we see that we need

$$n \approx {\log \delta \over 1 - h_2(p)}.$$


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.