Kódy pro opravu chyb se zpětnou vazbou - Error-correcting codes with feedback

v matematika, počítačová věda, telekomunikace, teorie informace, a teorie hledání, kódy opravující chyby se zpětnou vazbou odkazuje na chyba opravující kódy navržen tak, aby fungoval za přítomnosti zpětné vazby od přijímače k ​​odesílateli.[1]

Problém

Alice (odesílatel) si přeje poslat hodnotu X Bobovi (přijímači). Komunikační kanál mezi Alice a Bobem je nedokonalý a může způsobit chyby.

Řešení

Kód pro opravu chyb je způsob, jak kódování X jako zprávu tak, aby Bob úspěšně pochopil hodnotu X jak zamýšlí Alice, i když se zpráva, kterou Alice posílá, a zpráva, kterou Bob přijímá, liší. V kódu opravujícím chyby se zpětnou vazbou je kanál obousměrný: Bob může Alici zaslat zpětnou vazbu ohledně zprávy, kterou obdržel.

Hlučná zpětná vazba

V kódu opravujícím chyby bez hlučná zpětná vazba, zpětná vazba od odesílatele je vždy bez chyb. V kódu opravujícím chyby s hlučná zpětná vazba, mohou se vyskytnout chyby ve zpětné vazbě i ve zprávě.

Kód pro opravu chyb s bezhlučná zpětná vazba je ekvivalentní s adaptivní Vyhledávání strategie s chybami.[1]

Dějiny

V roce 1956 Claude Shannon představil oddělený bez paměti kanál s bezhlučnou zpětnou vazbou. V roce 1961 Alfréd Rényi představil Hra Bar-Kochba (také známý jako Dvacet otázek ), s daným procentem nesprávných odpovědí, a vypočítal minimální počet náhodně vybraných otázek k určení odpovědi.

Ve své disertační práci z roku 1964 Elwyn Berlekamp považováno za opravu chyb kódy s bezhlučnou zpětnou vazbou.[2] V Berlekampově scénáři si příjemce vybral podmnožinu možných zpráv a zeptal se odesílatele, zda je daná zpráva v této podmnožině, odpověď „ano“ nebo „ne“. Na základě této odpovědi pak příjemce vybral novou podmnožinu a postup zopakoval. Hra je dále komplikována hlukem; některé odpovědi budou chybné.

Zdroje

  • Deppe, Christian (2007), „Coding with Feedback and Searching with Lies“, Imre Csiszár; Gyula O.H. Katona; Gabor Tardos (eds.), Entropie, hledání, složitostMatematické studie společnosti Bolyai Society, 16, Berlin-Heidelberg: Springer, s. 27–70, doi:10.1007/978-3-540-32777-6, ISBN  978-3-540-32573-4.
  • Hill, Ray (1995), Hledání lží, Cambridge London Mathematical Society Lecture Note Series, Surveys in Combinatorics, Cambridge: Cambridge Univ. Stiskněte, str.41–70, ISBN  0-521-49797-3.

Reference

  1. ^ A b Vidět Deppe 2007 a Hill 1995.
  2. ^ Deppe 2007.

Viz také