Year 2019, Volume 6 , Issue 3, Pages 135 - 145 2019-09-13

Asymptotically good homological error correcting codes

Jason MCCULLOUGH [1] , Heather NEWMAN [2]


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. 
Error correcting codes, Simplicial complexes, Simplicial homology
  • [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.
Primary Language en
Subjects Engineering
Journal Section Articles
Authors

Author: Jason MCCULLOUGH (Primary Author)

Author: Heather NEWMAN

Dates

Publication Date : September 13, 2019

Bibtex @research article { jacodesmath617235, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2019}, volume = {6}, pages = {135 - 145}, doi = {10.13069/jacodesmath.617235}, title = {Asymptotically good homological error correcting codes}, key = {cite}, author = {Mccullough, Jason and Newman, Heather} }
APA Mccullough, J , Newman, H . (2019). Asymptotically good homological error correcting codes . Journal of Algebra Combinatorics Discrete Structures and Applications , 6 (3) , 135-145 . DOI: 10.13069/jacodesmath.617235
MLA Mccullough, J , Newman, H . "Asymptotically good homological error correcting codes" . Journal of Algebra Combinatorics Discrete Structures and Applications 6 (2019 ): 135-145 <https://dergipark.org.tr/en/pub/jacodesmath/issue/48724/617235>
Chicago Mccullough, J , Newman, H . "Asymptotically good homological error correcting codes". Journal of Algebra Combinatorics Discrete Structures and Applications 6 (2019 ): 135-145
RIS TY - JOUR T1 - Asymptotically good homological error correcting codes AU - Jason Mccullough , Heather Newman Y1 - 2019 PY - 2019 N1 - doi: 10.13069/jacodesmath.617235 DO - 10.13069/jacodesmath.617235 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 135 EP - 145 VL - 6 IS - 3 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.617235 UR - https://doi.org/10.13069/jacodesmath.617235 Y2 - 2019 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Asymptotically good homological error correcting codes %A Jason Mccullough , Heather Newman %T Asymptotically good homological error correcting codes %D 2019 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 6 %N 3 %R doi: 10.13069/jacodesmath.617235 %U 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
AMA Mccullough J , Newman H . Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019; 6(3): 135-145.
Vancouver Mccullough J , Newman H . Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019; 6(3): 135-145.