Research Article
BibTex RIS Cite

A new formula for the minimum distance of an expander code

Year 2022, Volume: 9 Issue: 2, 9 - 14, 13.05.2022
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.

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.
Year 2022, Volume: 9 Issue: 2, 9 - 14, 13.05.2022
https://doi.org/10.13069/jacodesmath.1111379

Abstract

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.
There are 8 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Sudipta Mallik This is me 0000-0001-7496-2147

Publication Date May 13, 2022
Published in Issue Year 2022 Volume: 9 Issue: 2

Cite

APA Mallik, S. (2022). A new formula for the minimum distance of an expander code. Journal of Algebra Combinatorics Discrete Structures and Applications, 9(2), 9-14. https://doi.org/10.13069/jacodesmath.1111379
AMA Mallik S. A new formula for the minimum distance of an expander code. Journal of Algebra Combinatorics Discrete Structures and Applications. May 2022;9(2):9-14. doi:10.13069/jacodesmath.1111379
Chicago Mallik, Sudipta. “A New Formula for the Minimum Distance of an Expander Code”. Journal of Algebra Combinatorics Discrete Structures and Applications 9, no. 2 (May 2022): 9-14. https://doi.org/10.13069/jacodesmath.1111379.
EndNote Mallik S (May 1, 2022) A new formula for the minimum distance of an expander code. Journal of Algebra Combinatorics Discrete Structures and Applications 9 2 9–14.
IEEE S. Mallik, “A new formula for the minimum distance of an expander code”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 9, no. 2, pp. 9–14, 2022, doi: 10.13069/jacodesmath.1111379.
ISNAD Mallik, Sudipta. “A New Formula for the Minimum Distance of an Expander Code”. Journal of Algebra Combinatorics Discrete Structures and Applications 9/2 (May 2022), 9-14. https://doi.org/10.13069/jacodesmath.1111379.
JAMA Mallik S. A new formula for the minimum distance of an expander code. Journal of Algebra Combinatorics Discrete Structures and Applications. 2022;9:9–14.
MLA Mallik, Sudipta. “A New Formula for the Minimum Distance of an Expander Code”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 9, no. 2, 2022, pp. 9-14, doi:10.13069/jacodesmath.1111379.
Vancouver Mallik S. A new formula for the minimum distance of an expander code. Journal of Algebra Combinatorics Discrete Structures and Applications. 2022;9(2):9-14.