3
$\begingroup$

Where can I find examples of "scalable" good LDPC codes, namely classical codes with properties [n, O(n), O(n] and an explicit prescription of how to increase the bit number n?

I am new to this field, so I do not know whether this is an obvious question or something that does not exist at all.

$\endgroup$

1 Answer 1

2
$\begingroup$

Good Classical LDPC Code of Infinitely Large Lengths.

So, the state-of-the-art solution is attributed to Sipser and Shpilman, and the modern formulation of the idea is remarkably simple. Let $C_0$ be $\Delta$-length linear binary code for some finite $\Delta$. Now let $\{ G_{n} \}$ be a family of $\Delta$-regular graphs, such that $G_{n}$ has $n$ edges.

Now Define the Code $C_{n}$ to be all the assignments of $n$ bits over the $G_{n}$ edges such that any vertex in the graph sees on its local view (edges adjoint to it) a codeword of $C_{0}$. Consider the following:

  1. That construction invented by Tanner, by definition, any check $C_{n}$ has weight at most the degree of the graph, namely $\Delta$. By simple linear algebra, one can show that if the rate of $C_{0}$ is greater than half, then $C_{n}$ has a positive rate.

  2. Sipser and Shpilman proved that if the graph is an expander graph, then the code $C_{n}$ also has a linear distance. In particular, they present a simple proof that any sublinear assignment of bits (non-zero bits) on the edges implies that there is at least one vertex that sees a non-trivial local view (means at least one $1$-bit) yet that local view has not enough bits to exceeds the distance of $C_{0}$ and therefore can't be a codeword of it.

  3. We know how to construct explicitly family of expanders graph, For example, consider Lubotzky, in which the graph is a Cayley graph.

So now it should be clear how to construct a family of good classical LDPC codes.

BTW - QLDPC.

The construction of good quantum LDPC code family is not so different from the above, and even those that prove that the construction obtains a linear distance is hard the technical implementation is easy.

$\endgroup$
1
  • $\begingroup$ Thanks. If I require only a constant rate and $d \geq \sqrt{n}$, are there other examples? $\endgroup$ Mar 10 at 7:52

Your Answer

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

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