Concept icon
Concept

A small local parity-check matrix with no low-weight kernel words

Use a c-by-d binary matrix, c=ceil(d/(8B)), and require every nonzero kernel word to have weight at least delta d, delta=1/(100Bmu). For a fixed nonzero word, select one nonzero coordinate. Given the other row bits, exactly one of the two choices there makes the parity zero. Thus half of rows accept it; independent rows accept it in fraction 2^{-c} of matrices. For h=ceil(delta d)-1>=1, the number of forbidden words is at most (h+1)(2d)^h<2^{d/(25B)}, using d<=m<2^mu. For h=0 there are none. The union bound makes the fraction of bad matrices less than 2^{d/(25B)-c}<1. Enumerate matrices and forbidden words sequentially in exp(poly(B,log(m+2))) time and polynomial space.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math