Коды, исправляющие ошибки с обратной связью

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

Проблема

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

Решение

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

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

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

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

История

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

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

См. также

• Теорема о кодировании канала с шумом

Источники

• Берлекамп, Элвин Р. (1964). Блочное кодирование с бесшумной обратной связью (PDF) (доктор философии). Массачусетский технологический институт.
• Деппе, Кристиан (2007), «Программирование с обратной связью и поиск с помощью лжи» , Имре Чисар; Дьюла Ох Катона; Габор Тардос (ред.), Энтропия, поиск, сложность , Математические исследования Общества Боляи, том. 16, Springer, стр. 27–70, номер документа : 10.1007/978-3-540-32777-6_2 , ISBN.  978-3-540-32573-4 .
• Хилл, Рэй (1995), «Поиск с помощью лжи» , Обзоры по комбинаторике , Серия лекций Лондонского математического общества, том. 218, Издательство Кембриджского университета, стр. 41–70, ISBN.  0-521-49797-3 .