Araştırma Makalesi
BibTex RIS Kaynak Göster

Asymptotically good homological error correcting codes

Yıl 2019, , 135 - 145, 13.09.2019
https://doi.org/10.13069/jacodesmath.617235

Öz

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. 

Kaynakça

  • [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.
Yıl 2019, , 135 - 145, 13.09.2019
https://doi.org/10.13069/jacodesmath.617235

Öz

Kaynakça

  • [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.
Toplam 14 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Mühendislik
Bölüm Makaleler
Yazarlar

Jason Mccullough Bu kişi benim

Heather Newman Bu kişi benim

Yayımlanma Tarihi 13 Eylül 2019
Yayımlandığı Sayı Yıl 2019

Kaynak Göster

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. Eylül 2019;6(3):135-145. doi:10.13069/jacodesmath.617235
Chicago Mccullough, Jason, ve Heather Newman. “Asymptotically Good Homological Error Correcting Codes”. Journal of Algebra Combinatorics Discrete Structures and Applications 6, sy. 3 (Eylül 2019): 135-45. https://doi.org/10.13069/jacodesmath.617235.
EndNote Mccullough J, Newman H (01 Eylül 2019) Asymptotically good homological error correcting codes. Journal of Algebra Combinatorics Discrete Structures and Applications 6 3 135–145.
IEEE J. Mccullough ve H. Newman, “Asymptotically good homological error correcting codes”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 6, sy. 3, ss. 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 (Eylül 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 ve Heather Newman. “Asymptotically Good Homological Error Correcting Codes”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 6, sy. 3, 2019, ss. 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.