Asymptotically good homological error correcting codes

Year 2019, , 135 - 145, 13.09.2019

Jason Mccullough Heather Newman

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. 

Keywords

Error correcting codes, Simplicial complexes, Simplicial homology

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.