사전 코드
Lexicographic code사전 편찬 코드 또는 사전 편찬 코드는 탐욕스럽게 생성된 오류 수정 코드로서, 특성이 현저히 양호하다. 이 작품들은 블라디미르[1] 레벤쉬틴과 존 호튼 콘웨이, 닐 슬로운에 의해 독립적으로 제작되었다.[2] 2진법 사전 코드는 선형 코드로 해밍 코드와 2진법 골레이 코드를 포함한다.[2]
건설
한정된 장에 걸친 최소 거리 d와 길이 n의 어휘는 올제로 벡터로 시작하여 지금까지 추가된 벡터로부터 최소 해밍 거리 d의 다음 벡터(사전 편찬 순서)를 반복적으로 추가함으로써 생성된다. 예를 들어, 최소 거리 2의 길이-3 어휘는 다음 예에서 "X"로 표시된 벡터로 구성된다.
벡터 암호로? 000 X 001 010 011 X 100 101 X 110 X 111
어휘소는 선형이기 때문에, 그것들의 기초에 의해서도 구성될 수 있다.[3]
콤비네이터 게임 이론
사전 코드의 이론은 결합 게임 이론과 밀접하게 연결되어 있다. 특히 거리라는 2진법 사전 편찬 코드의 암호문구는 그룬디의 게임의 변형된 판에서 승리한 포지션을 암호화하는데, 이 판은 각각의 움직임이 한 무더기의 더미를 최대 d - 1의 작은 힙으로 대체하는 것으로 구성되며, 목표는 마지막 돌을 차지하는 것이다.[2]
메모들
- ^ Levenšteĭn, V. I. (1960), "Об одном классе систематических кодов" [A class of systematic codes], Doklady Akademii Nauk SSSR (in Russian), 131 (5): 1011–1014, MR 0122629; 소비에트 수학의 영어 번역. 독레이디 1(1960), 368–371
- ^ a b c Conway, John H.; Sloane, N. J. A. (1986), "Lexicographic codes: error-correcting codes from game theory", IEEE Transactions on Information Theory, 32 (3): 337–348, doi:10.1109/TIT.1986.1057187, MR 0838197
- ^ Trachtenberg, Ari (2002), "Designing lexicographic codes with a given trellis complexity", IEEE Transactions on Information Theory, 48 (1): 89–100, doi:10.1109/18.971740, MR 1866958
