nach oben

Problems of Information Transmission

Erschienen in:

01.10.2021 | CODING THEORY

On List Decoding of Certain \(\mathbb{F}_q\)-Linear Codes

verfasst von: N. A. Polyanskii

Erschienen in: Problems of Information Transmission | Ausgabe 4/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present a list decoding algorithm for \(\mathbb{F}_q\)-linear codes that generalize the Reed–Solomon \(s\)-codes.

Vorheriger Artikel On the Generalized Concatenated Construction for the Nordstrom–Robinson Code and the Binary Golay Code

Nächster Artikel On Intersections of Reed–Muller Like Codes

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Hirschfeld, J.W.P., Korchmáros, G., and Torres, F., Algebraic Curves over a Finite Field, Princeton: Princeton Univ. Press, 2008.CrossRef

Lidl, R. and Niederreiter, H., Finite Fields, Reading: Addison-Wesley, 1983. Translated under the title Konechnye polya, 2 vols., Moscow: Mir, 1988.MATH

Lucas, E., Théorie des fonctions numériques simplement périodiques, Amer. J. Math., 1878, vol. 1, no. 4, pp. 289–321. https://doi.org/10.2307/2369373MathSciNetCrossRef

Guo, A., Kopparty, S., and Sudan, M., New Affine-Invariant Codes from Lifting, in Proc. 4th Conf. on Innovations in Theoretical Computer Science (ITCS’13), Berkeley, CA, USA, Jan. 9–12, 2013, pp. 529–540. https://doi.org/10.1145/2422436.2422494

Rosenbloom, M.Yu. and Tsfasman, M.A., Codes for the m-Metric, Probl. Peredachi Inf., 1997, vol. 33, no. 1, pp. 55–63 [Probl. Inf. Transm. (Engl. Transl.), 1997, vol. 33, no. 1, pp. 45–52]. http://mi.mathnet.ru/eng/ppi359MathSciNet

Kopparty, S., Saraf, S., and Yekhanin, S., High-Rate Codes with Sublinear-Time Decoding, J. ACM, 2014, vol. 61, no. 5, Art. 28, pp. 1–20. https://doi.org/10.1145/2629416MathSciNetCrossRef

Holzbaur, L., Polyanskaya, R., Polyanskii, N., Vorobyev, I., and Yaakobi, E., Lifted Reed–Solomon Codes and Lifted Multiplicity Codes, IEEE Trans. Inform. Theory, 2021, vol. 67, no. 12, pp. 8051–8069. https://doi.org/10.1109/TIT.2021.3116520MathSciNetCrossRef

Wu, L., Revisiting the Multiplicity Codes: A New Class of High-Rate Locally Correctable Codes, in Proc. 53rd Annu. Allerton Conf. on Communication, Control, and Computing, Monticello, IL, USA, Sept. 29 – Oct. 2, 2015, pp. 509–513. https://doi.org/10.1109/ALLERTON.2015.7447047

Li, R. and Wootters, M., Lifted Multiplicity Codes and the Disjoint Repair Group Property, IEEE Trans. Inform. Theory, 2021, vol. 67, no. 2, pp. 716–725. https://doi.org/10.1109/TIT.2020.3034962MathSciNetCrossRef

10.

Nielsen, R.R., List Decoding of Linear Block Codes, PhD Thesis, Dept. Math., Tech. Univ. Denmark, Lyngby, Denmark, 2001. Available from https://orbit.dtu.dk/en/publications/list-decoding-of-linear-block-codes.

11.

Kopparty, S., List-Decoding Multiplicity Codes, Theory Comput., 2015, vol. 11, Art. 5, pp. 149–182. https://doi.org/10.4086/toc.2015.v011a005MathSciNetCrossRef

12.

Guruswami, V. and Wang, C., Optimal Rate List Decoding via Derivative Codes, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Proc. 14th Int. Workshop, APPROX’2011, and 15th Int. Workshop, RANDOM’2011, Princeton, NJ, USA, Aug. 17–19, 2011), Goldberg, L.A., Jansen, K., Ravi, R., and Rolim, J.D.P., Eds., Lect. Notes Comput. Sci, vol. 6845, Berlin: Springer, 2011, pp. 593–604. https://doi.org/10.1007/978-3-642-22935-0_50

13.

Guo, A. and Kopparty, S., List-Decoding Algorithms for Lifted Codes, IEEE Trans. Inform. Theory, 2016, vol. 62, no. 5, pp. 2719–2725. https://doi.org/10.1109/TIT.2016.2538766MathSciNetCrossRef

14.

Kopparty, S., Some Remarks on Multiplicity Codes, Discrete Geometry and Algebraic Combinatorics (AMS Special Session on Discrete Geometry and Algebraic Combinatorics, San Diego, CA, USA, Jan. 11, 2013), Barg, A. and Musin, O.R., Eds., Providence, RI: Amer. Math. Soc., 2014, pp. 155–176.

Titel: On List Decoding of Certain -Linear Codes
verfasst von: N. A. Polyanskii
Publikationsdatum: 01.10.2021
Verlag: Pleiades Publishing
Erschienen in: Problems of Information Transmission / Ausgabe 4/2021
Print ISSN: 0032-9460
Elektronische ISSN: 1608-3253
DOI: https://doi.org/10.1134/S0032946021040049

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Die Gewinner und Laudatoren des Sustainability Award in Automotive 2024/© Uli Regenscheit | ATZlive, Search Icon, Banner Hanser, Suresh Vittal/© Alteryx, Additiv gefertigte Teile/© Marina_Skoropadskaya | Getty Images | iStock, Warnschild "Land unter"/© Bluedesign / Fotolia, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade, chassis.tech plus 2023/© [M] ATZlive / TÜV SÜD PRODUCT SERVICE GMBH, adäsion-Webinar-Matinee/© krystiannawrocki_ Getty Images

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2021

On the Generalized Concatenated Construction for the Nordstrom–Robinson Code and the Binary Golay Code

On the Maximum -Divergence of Probability Distributions Given the Value of Their Coupling

New Modularity Bounds for Graphs and

On Data Compression and Recovery for Sequences Using Constraints on the Spectrum Range

New Turán Type Bounds for Johnson Graphs

New Lower Bounds on the Fraction of Correctable Errors under List Decoding in Combinatorial Binary Communication Channels

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.