A new formula for the minimum distance of an expander code
DOI:
https://doi.org/10.13069/jacodesmath.1111379Keywords:
Linear code, Minimum distance, Expander graph, Adjacency matrixAbstract
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.
Received: 14 September 2021 | Accepted: 6 January 2022Downloads
References
N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth, Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs, IEEE Trans. Inform. Theory 38(2) (1992) 509–516.
M. R. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson, Randomness conductors and constant-degree lossless expanders, in: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2002), ACM, New York (2002) 659–668.
S. Mallik and B. Yildiz, Graph theoretic aspects of minimum distance and equivalence of binary linear codes, Australas. J. Combin. 79(3) (2021) 515–526.
S. Mallik and B. 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, Cambridge (2006).
M. Sipser and D. A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42(6) (1996) 1710–1722.
R. M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory 27(5) (1981) 533–547.
G. Zémor, On expander codes, IEEE Trans. Inform. Theory 47(2) (2001) 835–837.
