Generally, low density parity codes are decoded using sum product decoder (also known as decoding under belief propagation). Such codes are usually decoded nicely if there are no short length cycles in tanner graph, in particular length 4 cycles are to be avoided. Naturally, this puts some bound on column weight in such a parity matrix. What is the general column weight $t$ that is allowed (in terms of code dimensions $k,n$) so that there are no 4-cycles?

To state it formally

given n and k what is maximum value of $t$ for which tanner graph (bipartite t regular) has no 4 cycle?


Your question is somewhat ill-posed: given $n$ and $k$, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2.

Instead, you can ask the question of what is the maximum column weight of a Tanner graph, given that is has no 4-cycle. Assuming uniform column weights, then the maximum column weight is $O(\sqrt{k})$. This is known as the Kővári–Sós–Turán theorem (see e.g. here), which states that the number of edges in an $(n,k)$-bipartite graph without 4-cycle is at most $$ (n-1)\sqrt{k} + k. $$ If the Tanner graph has uniform column weights $d$, then it has $nd$ edges, which gives the bound on $d$.

This is tight up to constants for the case where $k = n$ (see e.g. here).

  • $\begingroup$ By allowed I meant max weight. Anyway, the fact that this expression doesn't have $k$ in it is making me a little worried. I think in the form the answer is, it gives freedom to select any $k$ and then solve for max t for given $n$. $\endgroup$
    – Root
    Feb 19 '20 at 12:45
  • $\begingroup$ I agree, if $k$ is small then the bound should be smaller. As I mention, the bound is tight up to constant when $k = n$. $\endgroup$
    – smapers
    Feb 19 '20 at 12:47
  • $\begingroup$ I improved to answer. $\endgroup$
    – smapers
    Feb 19 '20 at 12:56

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.