ISPRAVLENIE ODNOY OShIBKI V ASIMMETRIChNOM KANALE S OBRATNOY SVYaZ'Yu

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

Доказывается новая нижняя оценка мощности кода с полной обратной связью, исправляющего одну ошибку в двоичном асимметричном канале. Также представлена верхняя граница мощности кода, близкая к новой нижней границе.

About the authors

I. V Vorob'ev

Технический университет Мюнхена

Email: vorobyev.i.v@yandex.ru
Мюнхен, Германия

A. V Lebedev

Институт проблем передачи информации им. А.А. Харкевича РАН

Email: al_lebed95@mail.ru
Москва, Россия

V. S Lebedev

Институт проблем передачи информации им. А.А. Харкевича РАН

Email: lebedev37@mail.ru
Москва, Россия

References

  1. Варшамов Р.Р., Тененгольц Г.М. Код, исправляющий одиночные несимметрические ошибки // АиТ. 1965. Т. 26. № 2. С. 288–292. http://www.mathnet.ru/at11293
  2. Варшамов Р.Р. К теории несимметрических кодов // Докл. АН СССР. 1965. Т. 164. № 4. С. 757–760. http://www.mathnet.ru/dan31642
  3. Варшамов Р.Р. О некоторых особенностях линейных кодов, корректирующих несимметрические ошибки // Докл. АН СССР. 1964. Т. 157. № 3. С. 546–548. https://www.mathnet.ru/dan29877
  4. Бассалыго Л.А. Новые верхние границы для кодов, исправляющих ошибки // Пробл. передачи информ. 1965. Т. 1. № 4. С. 41–44. http://www.mathnet.ru/ppi762
  5. Deppe C., Lebedev V., Maringer G., Polyanskii N. Coding with Noiseless Feedback over the Z-Channel // IEEE Trans. Inform. Theory. 2022. V. 68. № 6. P. 3731–3739. https://doi.org/10.1109/TIT.2022.3148446
  6. Lebedev A., Lebedev V., Polyanskii N. Two-Stage Coding over the Z-Channel // IEEE Trans. Inform. Theory. 2022. V. 68. № 4. P. 2290–2299. https://doi.org/10.1109/TIT.2022.3141082
  7. Cicalese F., 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). Lect. Notes Comput. Sci. V. 1858. Berlin: Springer, 2000. P. 159–169. https://doi.org/10.1007/3-540-44968-X_16
  8. Dumitriu I., Spencer J. A Halfliar’s Game // Theoret. Comput Sci. 2004. V. 313. № 3. P. 353–369. https://doi.org/10.1016/j.tcs.2002.09.001
  9. Spencer J., Yan C.H. The Halflie Problem // J. Combin. Theory Ser. A. 2003. V. 103. № 1. P. 69–89. https://doi.org/10.1016/S0097-3165(03)00068-2
  10. Бассалыго Л.А. Недвоичные коды, исправляющие ошибки при наличии одноразовой безошибочной обратной связи // Пробл. передачи информ. 2005. Т. 41. № 2. С. 63–67. http://www.mathnet.ru/ppi96
  11. Dumitriu I., Spencer J. The Two-Batch Liar Game over an Arbitrary Channel // SIAM J. Discrete Math. 2005. V. 19. № 4. P. 1056–1064. https://doi.org/10.1137/040617510
  12. Pelc A. Solution of Ulam’s Problem on Searching with a Lie // J. Combin. Theory Ser. A. 1987. V. 44. № 1. P. 129–140. https://doi.org/10.1016/0097-3165(87)90065-3
  13. Воробьев И.В., Деппе К., Лебедев А.В., Лебедев В.С. Исправление одной ошибки в ка- налах с обратной связью // Пробл. передачи информ. 2022. Т. 58. № 4. С. 38–49. https://doi.org/10.31857/S0555292322040040
  14. Vorobyev I., Lebedev A., Lebedev V. Correcting Errors in Asymmetric and Generalized Asymmetric Channels with Feedback // Proc. XVIII Int. Symp. “Problems of Redundancy in Information and Control Systems” (REDUNDANCY’2023). Moscow, Russia. Oct. 24–27, 2023. P. 163–167. https://doi.org/10.1109/Redundancy59964.2023.10330199
  15. Spencer J., Florescu L. Asymptopia. Providence, RI: Amer. Math. Soc., 2014.
  16. Hoeffding W. Probability Inequalities for Sums of Bounded Random Variables // J. Amer. Statist. Assoc. 1963. V. 58. № 301. P. 13–30. https://doi.org/10.2307/2282952. Reprinted in: The Collected Works of Wassily Hoeffding. New York: Springer, 1994. P. 409–426.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences