A new formula for the minimum distance of an expander code

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

Kaynakça

1. [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. [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. [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. [4] Sudipta Mallik, Bahattin Yildiz, Isodual and self-dual codes from graphs, Algebra Discrete Math. 32(1) (2021) 49–64.
5. [5] R. M. Roth, Introduction to coding theory, Cambridge University Press (2006).
6. [6] M. Sipser, D. Spielman, Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722.
7. [7] M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory 27(5) (1981) v533–547.
8. [8] G. Zemor, On expander codes, IEEE Trans. Inf. Theory 47(2) (2001) 835-837.