Felrättande koder med återkoppling
Inom matematik , datavetenskap , telekommunikation , informationsteori och sökteori avser felkorrigerande koder med återkoppling felkorrigerande koder som är utformade för att fungera i närvaro av återkoppling från mottagaren till avsändaren.
Problem
Alice (avsändaren) vill skicka ett värde x till Bob (mottagaren). Kommunikationskanalen mellan Alice och Bob är ofullkomlig och kan introducera fel.
Lösning
En felkorrigerande kod är ett sätt att koda x som ett meddelande så att Bob kommer att lyckas förstå värdet x som Alice avsåg, även om meddelandet som Alice skickar och meddelandet som Bob tar emot skiljer sig åt. I en felkorrigerande kod med feedback är kanalen tvåvägs : Bob kan skicka feedback till Alice om meddelandet han fick.
Bullrig feedback
I en felkorrigerande kod utan brusig återkoppling är återkopplingen som mottas av avsändaren alltid felfri. I en felkorrigerande kod med brusig återkoppling kan fel uppstå i återkopplingen, såväl som i meddelandet.
En felkorrigerande kod med brusfri återkoppling motsvarar en adaptiv sökstrategi med fel.
Historia
1956 introducerade Claude Shannon den diskreta minneslösa kanalen med ljudlös feedback. 1961 introducerade Alfréd Rényi Bar-Kochba-spelet (även känt som tjugo frågor ), med en given procentandel av felaktiga svar, och beräknade det minsta antalet slumpmässigt valda frågor för att bestämma svaret.
I sin avhandling från 1964 övervägde Elwyn Berlekamp felkorrigerande koder med ljudlös återkoppling. I Berlekamps scenario valde mottagaren en delmängd av möjliga meddelanden och frågade avsändaren om det givna meddelandet fanns i denna delmängd, ett "ja" eller "nej" svar. Baserat på detta svar valde sedan mottagaren en ny delmängd och upprepade processen. Spelet är ytterligare komplicerat på grund av brus; några av svaren kommer att vara felaktiga.
Källor
- Deppe, Christian (2007), "Kodning med feedback och sökning med lögner", i Imre Csiszár; Gyula OH Katona; Gabor Tardos (red.), Entropy, Search, Complexity , Bolyai Society Mathematical Studies, vol. 16, Berlin-Heidelberg: Springer, s. 27–70, doi : 10.1007/978-3-540-32777-6 , ISBN 978-3-540-32573-4 .
- Hill, Ray (1995), Searching with lies , Cambridge London Mathematical Society Lecture Note Series, Surveys in Combinatorics, Cambridge: Cambridge Univ. Press, s. 41–70 , ISBN 0-521-49797-3 .