nach oben

Problems of Information Transmission

Erschienen in:

01.10.2022 | CODING THEORY

Correcting a Single Error in Feedback Channels

verfasst von: I. V. Vorobyev, C. Deppe, A. V. Lebedev, V. S. Lebedev

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We address the problem of correcting a single error in an arbitrary discrete memoryless channel with error-free instantaneous feedback. For the case of a one-time feedback, we propose a method for constructing optimal transmission strategies. The obtained result allows us to prove that for a binary channel, two feedbacks are sufficient to transmit the same number of messages as in the case of complete feedback. We also apply the developed techniques to a binary asymmetric channel to construct transmission strategies for small lengths.

Vorheriger Artikel On One Construction Method for Hadamard Matrices

Nächster Artikel Nonoverlapping Convex Polytopes with Vertices in a Boolean Cube and Other Problems in Coding Theory

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

Rényi, A., On a Problem of Information Theory, Magyar Tud. Akad. Mat. Kutató Int. Közl., 1961, vol. 6, pp. 505–516.MathSciNetMATH

Berlekamp, E.R., Block Coding for the Binary Symmetric Channel with Noiseless, Delayless Feedback, Error-Correcting Codes (Proc. Conf. Conducted by the Mathematics Research Center, United States Army, at the University of Wisconsin, Madison, May 6–8, 1968), Mann, H.B., Ed., New York: Wiley, 1969, pp. 61–85.

Zigangirov, K.Sh., On the Number of Correctable Errors for Transmission over a Binary Symmetrical Channel with Feedback, Probl. Peredachi Inf., 1976, vol. 12, no. 2, pp. 3–19 [Probl. Inf. Transm. (Engl. Transl.), 1976, vol. 12, no. 2, pp. 85–97]. http://mi.mathnet.ru/eng/ppi1683MathSciNetMATH

Ulam, S.M., Adventures of a Mathematician, New York: Scribner, 1976.CrossRefMATH

Pelc, A., Solution of Ulam’s Problem on Searching with a Lie, J. Combin. Theory Ser. A, 1987, vol. 44, no. 1, pp. 129–140. https://doi.org/10.1016/0097-3165(87)90065-3MathSciNetCrossRefMATH

Guzicki, W., Ulam’s Searching Game with Two Lies, J. Combin. Theory Ser. A, 1990, vol. 54, no. 1, pp. 1–19. https://doi.org/10.1016/0097-3165(90)90002-EMathSciNetCrossRefMATH

Deppe, C., Solution of Ulam’s Searching Game with Three Lies or an Optimal Adaptive Strategy for Binary Three-Error-Correcting Codes, Discrete Math., 2000, vol. 224, no. 1–3, pp. 79–98. https://doi.org/10.1016/S0012-365X(00)00109-6MathSciNetCrossRefMATH

desJardins, D.L., Precise Coding with Noiseless Feedback, PhD Thesis, Dept. of Mathematics, Univ. of California, Berkeley, 2002. Available at http://www.desjardins.org/david/thesis/thesis.pdf

Rivest, R.L., Meyer, A.R., Kleitman, D.J., Winkelmann, K., and Spencer, J., Coping with Errors in Binary Search Procedures, J. Comput. System Sci., 1980, vol. 20, no. 3, pp. 396–404. https://doi.org/10.1016/0022-0000(80)90014-8MathSciNetCrossRefMATH

10.

Cicalese, F., Fault-Tolerant Search Algorithms: Reliable Computation with Unreliable Information, Berlin: Springer, 2013.CrossRefMATH

11.

Cicalese, F. and Mundici, D., Optimal Coding with One Asymmetric Error: Below the Sphere Packing Bound, Computing and Combinatorics (Proc. 6th Annu. Int. Conf. COCOON 2000, Sydney, Australia, July 26–28, 2000), Du, D.Z., Eades, P., Estivill-Castro, V., Lin, X., and Sharma, A., Eds., Lect. Notes Comput. Sci., vol. 1858, Berlin: Springer, 2000, pp. 159–169. https://doi.org/10.1007/3-540-44968-X_16

12.

Dumitriu, I. and Spencer, J., A Halfliar’s Game, Theoret., Comput Sci., 2004, vol. 313, no. 3, pp. 353–369. https://doi.org/10.1016/j.tcs.2002.09.001MathSciNetCrossRefMATH

13.

Spencer, J. and Yan, C.H., The Halflie Problem, J. Combin. Theory Ser. A, 2003, vol. 103, no. 1, pp. 69–89. https://doi.org/10.1016/S0097-3165(03)00068-2MathSciNetCrossRefMATH

14.

Bassalygo, L.A., Nonbinary Error-Correcting Codes with One-Time Error-Free Feedback, Probl. Peredachi Inf., 2005, vol. 41, no. 2, pp. 63–67 [Probl. Inf. Transm. (Engl. Transl.), 2005, vol. 41, no. 2, pp. 125–129]. https://doi.org/10.1007/s11122-005-0017-3MathSciNetMATH

15.

Dumitriu, I. and Spencer, J., The Two-Batch Liar Game over an Arbitrary Channel, SIAM J. Discrete Math., 2005, vol. 19, no. 4, pp. 1056–1064. https://doi.org/10.1137/040617510MathSciNetCrossRefMATH

16.

Delsarte, P. and Piret, P., Bounds and Constructions for Binary Asymmetric Error-Correcting Codes, IEEE Trans. Inform. Theory, 1981, vol. 27, no. 1, pp. 125–128. https://doi.org/10.1109/TIT.1981.1056290MathSciNetCrossRefMATH

17.

Kløve, T., Upper Bounds on Codes Correcting Asymmetric Errors, IEEE Trans. Inform. Theory, 1981, vol. 27, no. 1, pp. 128–131. https://doi.org/10.1109/TIT.1981.1056291MathSciNetCrossRefMATH

18.

Weber, J., de Vroedt, C., and Boekee, D., New Upper Bounds on the Size of Codes Correcting Asymmetric Errors, IEEE Trans. Inform. Theory, 1987, vol. 33, no. 3, pp. 434–437. https://doi.org/10.1109/TIT.1987.1057301CrossRefMATH

Titel: Correcting a Single Error in Feedback Channels
verfasst von: I. V. Vorobyev
C. Deppe
A. V. Lebedev
V. S. Lebedev
Publikationsdatum: 01.10.2022
Verlag: Pleiades Publishing
Erschienen in: Problems of Information Transmission / Ausgabe 4/2022
Print ISSN: 0032-9460
Elektronische ISSN: 1608-3253
DOI: https://doi.org/10.1134/S0032946022040044

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/2022

Lower Bound on the Minimum Number of Edges in Subgraphs of Johnson Graphs

Nonoverlapping Convex Polytopes with Vertices in a Boolean Cube and Other Problems in Coding Theory

On Codes with Distances and

On One Construction Method for Hadamard Matrices

Some Classes of Balanced Functions over Finite Fields with a Small Value of the Linear Characteristic

Remarks on Reverse Pinsker Inequalities

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.