Коды исправления ошибок с обратной связью - 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.