Ta-Shma zigzag code[1]
Description
Member of a family of \(\epsilon\)-balanced codes that nearly achieves the asymptotic GV bound. The codes have relative distance \(\frac{1}{2}-\frac{\epsilon}{2}\) and rate of order \(\Omega (\epsilon^{2+\beta})\) for \(\beta\to 0\) as \(n\to\infty\) [2].Decoding
Unique and list decoders [2].Cousin
- Balanced code— Ta-Shma codes are \(\epsilon\)-balanced.
Primary Hierarchy
References
- [1]
- A. Ta-Shma, “Explicit, almost optimal, epsilon-balanced codes”, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (2017) DOI
- [2]
- F. G. Jeronimo, D. Quintana, S. Srivastava, and M. Tulsiani, “Unique Decoding of Explicit \(ε\)-balanced Codes Near the Gilbert-Varshamov Bound”, (2020) arXiv:2011.05500
Page edit log
- Victor V. Albert (2022-09-16) — most recent
Cite as:
“Ta-Shma zigzag code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ta-shma
Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/ta-shma.yml.