Bounds on Unique-Neighbor Codes

03/19/2022
by   Nati Linial, et al.
0

Let A be an m× n parity check matrix of a binary code of length n, rate R, and distance δ n. This means that for every δ n >k>0, every m× k submatrix of A has a row of odd weight. Message-passing decoding algorithms require the stronger unique neighbor property. Namely, that every such submatrix has a row of weight 1. It is well known that if δ≥1/2, then R=o_n(1) whereas for every 1/2>δ there exist linear codes of length n→∞ and distance > δ n with R bounded away from zero. We believe that the unique neighbor property entails sharper upper bounds on the rate. Concretely, we conjecture that for a proper choice of f(n) = o(n) and some constant ϵ_0 > 0, every n×(n+f(n)) binary matrix has an n× k submatrix with (1/2 -ϵ_0)n≥ k >0 where no row weighs 1. We make several contributions to the study of this conjecture.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset