Коды исправления ошибок с обратной связью - Error-correcting codes with feedback

В математике , информатика , телекоммуникации , теория информации и поиск теории , коды коррекции с обратной связью относятся к кодам коррекции ошибок , предназначенные для работы при наличии обратной связи от приемника к отправителю.

Проблема

Алиса (отправитель) желает отправить значение x Бобу (получателю). Канал связи между Алисой и Бобом несовершенен и может привести к ошибкам.

Решение

Код с исправлением ошибок - это способ кодирования x как сообщения, чтобы Боб успешно понял значение x, как задумано Алисой, даже если сообщение, отправленное Алисой, и сообщение, полученное Бобом, различаются. В коде исправления ошибок с обратной связью канал является двусторонним : Боб может отправить отзыв Алисе о полученном сообщении.

Шумная обратная связь

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

Код исправления ошибок с бесшумной обратной связью эквивалентен стратегии адаптивного поиска с ошибками.

История

В 1956 году Клод Шеннон представил дискретный канал без памяти с бесшумной обратной связью. В 1961 году Альфред Реньи представил игру Бар-Кохба (также известную как « Двадцать вопросов» ) с заданным процентом неправильных ответов и рассчитал минимальное количество случайно выбранных вопросов, чтобы определить ответ.

В своей диссертации 1964 года Элвин Берлекамп рассмотрел коды исправления ошибок с бесшумной обратной связью. В сценарии Берлекампа получатель выбрал подмножество возможных сообщений и спросил отправителя, было ли данное сообщение в этом подмножестве, ответ «да» или «нет». На основании этого ответа получатель затем выбрал новое подмножество и повторил процесс. Игра еще более усложняется из-за шума; некоторые ответы будут неправильными.

Источники

  • Деппе, Кристиан (2007), «Кодирование с обратной связью и поиск с помощью лжи», в Имре Цисар; Дьюла Ох Катона; Габор Tardos (ред.), Энтропия, поиск, сложность , Боляй Общество математических исследований, 16 , Berlin-Heidelberg:. Springer, С. 27-70, DOI : 10.1007 / 978-3-540-32777-6 , ISBN 978-3-540-32573-4.
  • Hill, Ray (1995), Searching with lie , Cambridge London Mathematical Society Lecture Note Series, Surveys in Combinatorics, Cambridge: Cambridge Univ. Press, стр.  41–70 , ISBN. 0-521-49797-3.

Ссылки

Смотрите также