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).

| cite | improve this answer | |
  • $\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 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 at 12:47
  • $\begingroup$ I improved to answer. $\endgroup$ – smapers Feb 19 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.