Research Article
BibTex RIS Cite

Asymptotically good homological error correcting codes

Year 2019, , 135 - 145, 13.09.2019
https://doi.org/10.13069/jacodesmath.617235

Abstract

Let $\Delta$ be an abstract simplicial complex. We study classical homological error correcting codes associated to $\Delta$, which generalize the cycle codes of simple graphs. It is well-known that cycle codes of graphs do not yield asymptotically good families of codes. We show that asymptotically good families of codes do exist for homological codes associated to simplicial complexes of dimension at least $2$. We also prove general bounds and formulas for (co-)cycle and (co-)boundary codes for arbitrary simplicial complexes over arbitrary fields. 

References

  • [1] N. Alon, S. Hoory, N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18(1) (2002) 53–57.
  • [2] L. Aronshtam, N. Linial, T. Łuczak, R. Meshulam, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete Comput. Geom. 49(2) (2013) 317–334.
  • [3] A. R. Calderbank, P. W. Shor, Good quantum error–correcting codes exist, Physical Review A 54(2) (1996) 1098–1105.
  • [4] D. Dotterrer, L. Guth, M. Kahle 2–complexes with large 2–girth, Discrete Computational Geometry 59(2) (2018) 383–412.
  • [5] R. G. Gallager, Low–density parity–check codes, IRE Trans. 8(1) (1962) 21–28.
  • [6] R. G. Gallager, Low–Density Parity–Check Code, MIT Press, 1963.
  • [7] X.-Y. Hu, E. Eleftheriou, D. M. Arnold, Regular and irregular progressive edge–growth Tanner graphs, IEEE Trans. Inform. Theory 51(1) (2005) 386–398.
  • [8] Steven Roman, Coding and Information Theory, Graduate Texts in Mathematics, vol. 134, Springer– Verlag, New York, 1992.
  • [9] Pavel Rytír, Geometric representations of linear codes, Adv. Math. 282(10) (2015) 1–22.
  • [10] Charles Saltzer, Topological codes, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), Wiley, New York (1968) 111–129.
  • [11] P. W. Shor, Scheme for reducing decoherence in quantum memory, Phys. Rev. A. 52(4) (1995) R2493–R2496.
  • [12] A. M. Steane, Multiple–particle interference and quantum error correction, Proc. Roy. Soc. A. 452(1954) (1996) 2551–2577.
  • [13] S. Thomeier, Error–correcting polyhedral codes, J. Comput. Inform. 1(2) (1990) 91–101.
  • [14] G. Zémor, On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction, Coding and cryptology, Lecture Notes in Comput. Sci., vol. 5557, Springer, Berlin (2009) 259–273.
Year 2019, , 135 - 145, 13.09.2019
https://doi.org/10.13069/jacodesmath.617235

Abstract

References

  • [1] N. Alon, S. Hoory, N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18(1) (2002) 53–57.
  • [2] L. Aronshtam, N. Linial, T. Łuczak, R. Meshulam, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete Comput. Geom. 49(2) (2013) 317–334.
  • [3] A. R. Calderbank, P. W. Shor, Good quantum error–correcting codes exist, Physical Review A 54(2) (1996) 1098–1105.
  • [4] D. Dotterrer, L. Guth, M. Kahle 2–complexes with large 2–girth, Discrete Computational Geometry 59(2) (2018) 383–412.
  • [5] R. G. Gallager, Low–density parity–check codes, IRE Trans. 8(1) (1962) 21–28.
  • [6] R. G. Gallager, Low–Density Parity–Check Code, MIT Press, 1963.
  • [7] X.-Y. Hu, E. Eleftheriou, D. M. Arnold, Regular and irregular progressive edge–growth Tanner graphs, IEEE Trans. Inform. Theory 51(1) (2005) 386–398.
  • [8] Steven Roman, Coding and Information Theory, Graduate Texts in Mathematics, vol. 134, Springer– Verlag, New York, 1992.
  • [9] Pavel Rytír, Geometric representations of linear codes, Adv. Math. 282(10) (2015) 1–22.
  • [10] Charles Saltzer, Topological codes, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), Wiley, New York (1968) 111–129.
  • [11] P. W. Shor, Scheme for reducing decoherence in quantum memory, Phys. Rev. A. 52(4) (1995) R2493–R2496.
  • [12] A. M. Steane, Multiple–particle interference and quantum error correction, Proc. Roy. Soc. A. 452(1954) (1996) 2551–2577.
  • [13] S. Thomeier, Error–correcting polyhedral codes, J. Comput. Inform. 1(2) (1990) 91–101.
  • [14] G. Zémor, On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction, Coding and cryptology, Lecture Notes in Comput. Sci., vol. 5557, Springer, Berlin (2009) 259–273.
There are 14 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Jason Mccullough This is me

Heather Newman This is me

Publication Date September 13, 2019
Published in Issue Year 2019

Cite

APA Mccullough, J., & Newman, H. (2019). Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications, 6(3), 135-145. https://doi.org/10.13069/jacodesmath.617235
AMA Mccullough J, Newman H. Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications. September 2019;6(3):135-145. doi:10.13069/jacodesmath.617235
Chicago Mccullough, Jason, and Heather Newman. “Asymptotically Good Homological Error Correcting Codes”. Journal of Algebra Combinatorics Discrete Structures and Applications 6, no. 3 (September 2019): 135-45. https://doi.org/10.13069/jacodesmath.617235.
EndNote Mccullough J, Newman H (September 1, 2019) Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications 6 3 135–145.
IEEE J. Mccullough and H. Newman, “Asymptotically good homological error correcting codes”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 6, no. 3, pp. 135–145, 2019, doi: 10.13069/jacodesmath.617235.
ISNAD Mccullough, Jason - Newman, Heather. “Asymptotically Good Homological Error Correcting Codes”. Journal of Algebra Combinatorics Discrete Structures and Applications 6/3 (September 2019), 135-145. https://doi.org/10.13069/jacodesmath.617235.
JAMA Mccullough J, Newman H. Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019;6:135–145.
MLA Mccullough, Jason and Heather Newman. “Asymptotically Good Homological Error Correcting Codes”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 6, no. 3, 2019, pp. 135-4, doi:10.13069/jacodesmath.617235.
Vancouver Mccullough J, Newman H. Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019;6(3):135-4.