Asymptotically good homological error correcting codes
DOI:
https://doi.org/10.13069/jacodesmath.617235Keywords:
Error correcting codes, Simplicial complexes, Simplicial homologyAbstract
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.
Received: 15 January 2018 Accepted: 23 July 2019Downloads
References
N. Alon, S. Hoory, and N. Linial, The Moore bound for irregular graphs, Graphs Combin. 18(1) (2002) 53–57.
L. Aronshtam, N. Linial, T. Łuczak, and R. Meshulam, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete Comput. Geom. 49(2) (2013) 317–334.
A. R. Calderbank and P. W. Shor, Good quantum error–correcting codes exist, Phys. Rev. A 54(2) (1996) 1098–1105.
D. Dotterrer, L. Guth, and M. Kahle, 2–complexes with large 2–girth, Discrete Comput. Geom. 59(2) (2018) 383–412.
R. G. Gallager, Low–density parity–check codes, IRE Trans. Inform. Theory 8(1) (1962) 21–28.
R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, Cambridge, MA, 1963.
X.-Y. Hu, E. Eleftheriou, and D. M. Arnold, Regular and irregular progressive edge–growth Tanner graphs, IEEE Trans. Inform. Theory 51(1) (2005) 386–398.
S. Roman, Coding and Information Theory, Graduate Texts in Mathematics, vol. 134, Springer-Verlag, New York, 1992.
P. Rytíř, Geometric representations of linear codes, Adv. Math. 282(10) (2015) 1–22.
C. Saltzer, Topological codes, In: H. B. Mann (Ed.), Error Correcting Codes, Proc. Sympos. Math. Res. Center, Madison, Wis., 1968, Wiley, New York (1968) 111–129.
P. W. Shor, Scheme for reducing decoherence in quantum memory, Phys. Rev. A 52(4) (1995) R2493–R2496.
A. M. Steane, Multiple–particle interference and quantum error correction, Proc. R. Soc. Lond. A 452(1954) (1996) 2551–2577.
S. Thomeier, Error–correcting polyhedral codes, J. Comput. Inf. 1(2) (1990) 91–101.
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, Heidelberg (2009) 259–273.
