Which Codes Have$4$-Cycle-Free Tanner Graphs?

摘要

Let$cal C$be an$[n,k,d]$binary linear code with rate$R=k$and dual$cal C^bot$. In this correspondence, it is shown that$cal C$can be represented by a$4$-cycle-free Tanner graph only if:$$ pd^botleqleftlfloorsqrtnp(p-1)+n^2over 4+nover 2rightrfloor $$where$p=n-k$and$d^bot$is the minimum distance of$cal C^bot$. By applying this result, it is shown that$4$-cycle-free Tanner graphs do not exist for many classical binary linear block codes.