0
$\begingroup$

There is an obvious construction of linear codes from graphs, where each codeword is a cycle in the graph. Physical bits are edges in the graph, and constraints are vertices.

This has been used in the construction of good LDPC codes with expander graphs by Sipser and Spielman [1], but their construction uses Tanner codes, where the local codes at each vertex are some other good code; it also uses an edge-vertex incidence graph as a Tanner graph, rather than using the incidence matrix of a graph directly.

If we restrict ourselves to just the incidence matrix of graphs, with bounded vertex degree, what is the best possible asymptotic encoding rate and distance we can achieve? I assume that this will also use expander graphs.

[1] M. Sipser and D. A. Spielman, "Expander codes," in IEEE Transactions on Information Theory, vol. 42, no. 6, pp. 1710-1722, Nov. 1996, doi: 10.1109/18.556667.

$\endgroup$

1 Answer 1

0
$\begingroup$

I have been pointed towards a reference which answers this precisely: https://link.springer.com/chapter/10.1007/978-3-642-01877-0_21. Here, it is claimed that the best I can hope for is constant rate and logarithmic distance - although the paper only proves this for regular graphs.

$\endgroup$

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.