피드백을 사용하여 코드 오류 수정
Error-correcting codes with feedback수학, 컴퓨터 과학, 통신, 정보 이론, 검색 이론에서 피드백이 있는 오류 수정 코드는 수신기에서 송신자에게 피드백이 있는 상태에서 작동하도록 설계된 코드를 오류 수정하는 것을 말한다.[1]
문제
앨리스(발신자)는 값 x를 밥(수신자)에게 보내고 싶어한다. 앨리스와 밥 사이의 의사소통 채널은 불완전하며 오류를 일으킬 수 있다.
해결책
오류 정정 코드는 앨리스가 보내는 메시지와 밥이 받는 메시지가 다르더라도 밥이 앨리스가 의도한 대로 x 값을 성공적으로 이해할 수 있도록 x를 메시지로 인코딩하는 방식이다. 피드백이 있는 오류 수정 코드에서, 이 채널은 양방향이다: 밥은 앨리스에게 그가 받은 메시지에 대한 피드백을 보낼 수 있다.
노이즈 피드백
노이즈가 없는 오류 수정 코드의 경우, 송신자가 수신한 피드백은 항상 오류가 없다. 노이즈가 많은 오류 수정 코드는 피드백뿐만 아니라 메시지에서도 오류가 발생할 수 있다.
무음 피드백의 오류 수정 코드는 오류가 있는 적응형 검색 전략과 동일하다.[1]
역사
1956년 클로드 섀넌은 잡음 없는 피드백으로 이산 메모리 없는 채널을 도입했다. 1961년 알프레드 레니는 바-코흐바 게임(일명 20문항)을 도입하여 오답의 비율을 일정하게 하고, 임의로 선택한 최소 문항의 수를 계산하여 정답을 결정한다.
Elwyn Berlekamp는 1964년 논문에서 소음이 없는 피드백으로 코드를 수정하는 오류를 고려했다.[2] Berlekamp의 시나리오에서, 수신자는 가능한 메시지의 서브셋을 선택하고 송신자에게 주어진 메시지가 이 서브셋에 있는지, 즉 '예스'인지 '아니오'인지를 물었다. 이어 이 대답을 바탕으로 수신자는 새로운 서브셋을 선택하고 그 과정을 반복했다. 그 게임은 소음 때문에 더 복잡하다. 일부 답은 틀릴 것이다.
원천
- Deppe, Christian (2007), "Coding with Feedback and Searching with Lies", in Imre Csiszár; Gyula O.H. Katona; Gabor Tardos (eds.), Entropy, Search, Complexity, Bolyai Society Mathematical Studies, 16, Berlin-Heidelberg: Springer, pp. 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, pp. 41–70, ISBN 0-521-49797-3.
