A new formula for the minimum distance of an expander code

Year 2022, , 9 - 14, 13.05.2022

Sudipta Mallik

https://doi.org/10.13069/jacodesmath.1111379

Abstract

An expander code is a binary linear code whose parity-check matrix is the bi-adjacency matrix of a bipartite expander graph. We provide a new formula for the minimum distance of such codes. We also provide a new proof of the result that $2(1-\varepsilon) \gamma n$ is a lower bound of the minimum distance of the expander code given by an $(m,n,d,\gamma,1-\varepsilon)$ expander bipartite graph.

Keywords

Linear code, Minimum distance, Expander graph, Adjacency matrix

References

• [1] N. Alon, J. Bruck, J. Naor, M. Naor, R. Roth, Construction of asymptotically good low-rate errorcorrecting codes through pseudo-random graphs, IEEE Trans. Inf. Theory 38(2) (1992) 509–516.
• [2] M. R. Capalbo, O. Reingold, S. Vadhan, A. Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the ACM Symposium on Theory of Computing (2002) 659–668.
• [3] Sudipta Mallik, Bahattin Yildiz, Graph theoretic aspects of minimum distance and equivalence of binary linear codes, Australas. J. Combin. 79(3) (2021) 515–526.
• [4] Sudipta Mallik, Bahattin Yildiz, Isodual and self-dual codes from graphs, Algebra Discrete Math. 32(1) (2021) 49–64.
• [5] R. M. Roth, Introduction to coding theory, Cambridge University Press (2006).
• [6] M. Sipser, D. Spielman, Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722.
• [7] M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory 27(5) (1981) v533–547.
• [8] G. Zemor, On expander codes, IEEE Trans. Inf. Theory 47(2) (2001) 835-837.