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.
References
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.
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.
Sudipta Mallik, Bahattin Yildiz, Graph theoretic aspects of minimum distance and equivalence of binary linear codes, Australas. J. Combin. 79(3) (2021) 515–526.
Sudipta Mallik, Bahattin Yildiz, Isodual and self-dual codes from graphs, Algebra Discrete Math. 32(1) (2021) 49–64.
R. M. Roth, Introduction to coding theory, Cambridge University Press (2006).
M. Sipser, D. Spielman, Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722.
M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory 27(5) (1981) v533–547.
G. Zemor, On expander codes, IEEE Trans. Inf. Theory 47(2) (2001) 835-837.
