오류 정정

앨리스와 밥은 놀라운 트릭을 발견했습니다 단단하거나 부드러운 전선을 퉁겨 0과 1을 전송하는 방식으로 의견을 주고 받았습니다 하지만 바람때문에 잘못된 0 또는 1이 전송 과정에서 발생할 수 있으며 그 결과 오류가 발생합니다 그렇지만 그들은 잡음이 발생하는 와중에도 오류 없이 가능한 전송 방법을 발견해냈습니다 어떻게 해낼 수 있었을까요? 1940년 리처드 해밍은 벨 연구소에서 근무하면서 이와 비슷한 문제에 직면했습니다 벨 전화 연구소에서는 약 10%의 실험을 컴퓨터에서 약 90%를 실험실에서 실시했습니다 언젠가 90%를 컴퓨터에서 10%를 실험실에서 실시하게 되기를 기대합니다 속도, 비용, 노력면에서 실험실 보다는 컴퓨터를 이용한 접근법이 선호됩니다 그 당시에는 컴퓨터가 자료를 저장하는 방법으로 천공 카드를 써서 0 아니면 1을 구멍 아니면 구멍 없음으로 나타냈습니다 이 시스템은 오류가 발생하기 쉬운데 카드가 구부려지거나 잘못 구멍이 나는 경우가 흔했기 때문입니다 잘못된 곳에 구멍이 나거나 뜻하지 않게 구멍이 없어서 비트가 뒤집어지는 일이 발생합니다 이러한 오류가 발생하면 일일이 직접 오류가 생긴 곳을 찾아 수정할 때까지 전체 시스템을 정지해야 할 수도 있었습니다 해밍은 비트 하나에서 발생한 오류를 별도의 계산 과정 없이 스스로 감지하고 수정하는 방법을 찾기 위해 고민했습니다 그의 해법은 어떤 일이든지 간섭을 받거나 메시지 일부가 손상될 가능성이 있다는 반복에 대한 직관적인 아이디어에 근거를 두고 있습니다 해밍의 오류 수정 코드는 패리티 비트라는 단순한 개념으로 만들어졌습니다 패리티 비트는 메시지 끝에 붙는 1비트로 메시지에 존재하는 1의 수가 짝수인지 또는 홀수인지를 나타냅니다 만일 오류가 하나 발생한다면 수신자는 이를 감지할 수 있는데 패리티 비트가 더 이상 일치하지 않기 때문입니다 하지만 오류 하나를 감지하고 수정하기 위해 해밍은 더 많은 패리티 비트를 추가해야 오류가 발생한 위치를 알아낼 수 있었습니다 이는 해밍(7,4) 코드로 발전하는데 패리티 비트 셋을 데이터 비트 넷으로 된 각 블럭에 추가하게 됩니다 먼저 원으로 나타낼 수 있는 패리티 비트 셋으로 시작합니다 이 원들은 교차해서 네 영역을 만들어 냅니다 데이터 비트 넷은 특정 순서에 따라 이러한 영역에 위치합니다 패리티 비트를 계산하기 위해 각 원을 하나씩 들여다 보면 각각 데이터 비트 셋을 포함하고 있습니다 앞서 설명한대로 패리티 비트를 결정할 수 있습니다 데이터 비트를 합해서 0 또는 2가 나오면 짝수이므로 패리티 비트는 0이며 1또는 3이 나오면 홀수이므로 패리티 비트는 1입니다 모든 원에 이를 적용하면 데이터 비트 넷에 해당하는 패리티 비트 셋이 나오게 됩니다 이들은 다음과 같은 표준화된 순서에 따라 배치됩니다 이제 이 시스템은 오류 하나 정도는 간단히 자동적으로 수정할 수 있다는 사실을 알았을 것입니다 오류가 하나 발생한다면 패리티 비트 둘 또는 셋이 맞지 않으며 오류가 발생한 지점은 교차 영역 양쪽에 해당합니다 이러한 교차 영역에 존재하는 비트는 자동적으로 뒤집어져 모든 패리티 비트가 올바르게 됩니다 이것이 앨리스와 밥이 찾아낸 트릭입니다 이렇게 추가된 패리티 비트는 새로운 정보를 포함하지는 않기 때문에 잉여 비트라고 불립니다 모든 오류 수정 코드는 이런 방식으로 동작합니다 이들은 자동적으로 오류를 수정하는데 드는 비용으로 원본 메시지의 크기를 약간 증가시킵니다 이러한 오류 수정 코드는 저장소에서도 사용하는데 물리적인 CD를 예로 들면 특수한 코드를 사용해서 부호화된 정보는 흠집이나 먼지에 의해 CD 표면에 저장된 1과 0으로 된 긴 수열의 손상으로 발생한 오류 조각을 수정하는데 사용됩니다 CD 표면이 손상되더라도 제대로 재생되는 경우는 바로 이 때문입니다 클로드 섀넌은 이러한 중복에 대한 아이디어를 사용해서 의사소통 채널의 용량을 다음과 같이 재정의하였습니다 채널이 늘어남에 따라 발생하는 잡음 때문에 오류가 없는 의사소통에 필요한 중복의 양은 늘어나야만 합니다 그리고 단위 시간마다 보낼 수 있는 효율적인 정보의 양은 줄어들어야만 합니다