# How to design code for arbitrary low error rate with achievable code rate under Binary Erasure Channel (BEC)

"I am looking for a code that can lower my error rate with a fixed code rate."

Assume a binary erasure channel that a bit is probably erased in probability 0.5, and any bit won't flip.

Then, the achievable rate R is defined as following: For a channel (𝒳,p(Y|X),𝒴) a rate R is achievable if and only if there for every ε>0 there exists an (M,n) code with (log M)/n ≥ R and λ ⩽ ε.

I would like to verify if R=1/2 is achievable rate, so I design the code: Index set is {1,2} only, the codebook is {00, 11}, respectively. In this code, M = 2 and n = 2, and it satisfies (log M)/n ≥ R. How about the error rate? The error only occurs when the received bits are both erased, which has probability 0.5*0.5=0.25.

If R = 1/2 is achievable rate, I should be able to find another (M,n) code that has a lower error rate ε. We are sure R = 1/2 is achievable rate because the channel capacity is 0.5 (calculated by 1 - 0.5). Do any one have idea about the code?

To add to Stelios' answer (+1): there is indeed a very simple (practically trivial) code ... but if feedback is allowed: just resend the previous symbol if the decoder finds out it was erased. In this scheme, the number of times that each symbol is sent follows a geometric distribution, with mean $2$ - hence it achieves the capacity.
The information theoretic limits become evident in practice with long codewords (i.e., $n\gg1$). I doubt there is any sophisticated algebraic approach for code design with very small $n$ (say, less than $10$), apart from brute-force computer search. Also, consideration of a rate $R=C$ makes the search for a good code a much more difficult, if not impossible, task (compared to the case $R<C$), even when large values of $n$ are considered.
There is a vast literature providing excellent code designs for the BEC with moderate-to-large $n$, typically based on graphs (e.g., Fountain codes).
• @Chien-YuChan Of course, a "good" code (such as LDPC or Turbo) is by definition one that is (1) able to provide very reliable communication and (2) operate at a rate $R$ that is as close as possible to $C$. A "bad" code such as a repetition code may achieve (1) for large block lengths but operates with $R\rightarrow 0$ Mar 2 '17 at 18:08