Kody korygujące błędy z informacją zwrotną
W matematyce , informatyce , telekomunikacji , teorii informacji i teorii wyszukiwania kody korekcji błędów ze sprzężeniem zwrotnym odnoszą się do kodów korekcji błędów zaprojektowanych do działania w obecności informacji zwrotnej od odbiorcy do nadawcy.
Problem
Alicja (nadawca) chce wysłać wartość x do Boba (odbiorcy). Kanał komunikacji między Alicją a Bobem jest niedoskonały i może wprowadzać błędy.
Rozwiązanie
Kod korekcji błędów to sposób kodowania x jako wiadomości, dzięki której Bob z powodzeniem zrozumie wartość x zgodnie z zamierzeniami Alicji, nawet jeśli wiadomość wysyłana przez Alicję i wiadomość odbierana przez Boba różnią się. W kodzie korygującym błędy ze sprzężeniem zwrotnym kanał jest dwukierunkowy : Bob może wysłać Alicji informację zwrotną na temat otrzymanej wiadomości.
Głośne sprzężenie zwrotne
W kodzie korygującym błędy bez hałaśliwych informacji zwrotnych , informacja zwrotna otrzymana przez nadawcę jest zawsze wolna od błędów. W kodzie korygującym błędy z hałaśliwym sprzężeniem zwrotnym mogą wystąpić błędy zarówno w sprzężeniu zwrotnym, jak iw komunikacie.
Kod korygujący błędy z bezgłośnym sprzężeniem zwrotnym jest odpowiednikiem adaptacyjnej strategii wyszukiwania z błędami.
Historia
W 1956 roku Claude Shannon wprowadził dyskretny kanał bez pamięci z bezszumowym sprzężeniem zwrotnym. W 1961 roku Alfréd Rényi wprowadził grę Bar-Kochba (znaną również jako Dwadzieścia pytań ) z określonym odsetkiem błędnych odpowiedzi i obliczył minimalną liczbę losowo wybranych pytań, aby określić odpowiedź.
W swojej rozprawie z 1964 roku Elwyn Berlekamp rozważał kody korygujące błędy z bezgłośnym sprzężeniem zwrotnym. W scenariuszu Berlekampa odbiorca wybierał podzbiór możliwych wiadomości i pytał nadawcę, czy dana wiadomość znajduje się w tym podzbiorze, odpowiedź „tak” lub „nie”. Na podstawie tej odpowiedzi odbiorca wybrał następnie nowy podzbiór i powtórzył proces. Gra jest dodatkowo skomplikowana ze względu na hałas; niektóre odpowiedzi będą błędne.
Źródła
- Deppe, Christian (2007), „Kodowanie ze sprzężeniem zwrotnym i wyszukiwanie za pomocą kłamstw”, w: Imre Csiszár; Gyula OH Katona; Gabor Tardos (red.), Entropia, wyszukiwanie, złożoność , Bolyai Society Mathematical Studies, tom. 16, Berlin-Heidelberg: Springer, s. 27–70, doi : 10.1007/978-3-540-32777-6 , ISBN 978-3-540-32573-4 .
- Hill, Ray (1995), Wyszukiwanie za pomocą kłamstw , seria notatek z wykładów Cambridge London Mathematical Society, Surveys in Combinatorics, Cambridge: Cambridge Univ. Prasa, s. 41–70 , ISBN 0-521-49797-3 .