Complexity estimation of decoding problem and finding of low-weight codewords using basis reduction

This paper presents a complexity estimation of decoding problem and an analysis of efficiency of low-weight codeword problem solving for random binary codes. For this purpose we use recent basis reduction algorithms adapted to codes from LLL and BKZ-algorithm for lattices. In particular, we have implemented BKZ reduction algorithm for binary linear codes and performed computational experiments for block size $\beta \leq 24$, length of the code $n = 64, 128, 256, 512, 1024, 1280$ and code rate $R = 0.5$. Estimated complexity of random linear code decoding is compared with Prange, Stern, Dumer, MMT, and BJMM algorithms.