빌헬름 라이프니츠가 발명한 이진법, 모스부호, 컴퓨터 등에 응용
⊙ 사용하지 않는 한 개의 비트 공간을 활용해 오류 여부를 확인하는 데 사용하는 게 ‘패리티 비트’
⊙ 사용하지 않는 한 개의 비트 공간을 활용해 오류 여부를 확인하는 데 사용하는 게 ‘패리티 비트’
마법의 카드. 그 비밀은?
1부터 31까지의 수가 적힌 5장의 카드가 있다. 이 카드는 당신이 생각하는 수를 맞힐 수 있는 마법의 카드이다.
1부터 31까지 수 중에서 하나의 수를 생각해 보자. A, B, C, D, E의 카드 중에서 선택한 수가 포함되어 있는 카드를 고르고, 그 카드의 첫 번째 칸의 수를 서로 더해 보자. 당신이 선택한 수가 맞는가? 만약 틀렸다면 계산에 실수가 있었을 것이다. 다시 한 번 해 보자. 방법은 동일하다. 1부터 31까지 수 중에서 처음 선택한 수와 다른 수를 선택하고, 선택한 수의 카드에서 색칠된 칸의 수를 더해 보자. 이번에도 당신이 선택한 수가 나왔을 것이다. 어떤 원리로 당신이 생각한 수를 모두 맞힐 수 있는 것일까? 눈치챈 사람도 있을 것이다. 정답은 진법이다. 그중에서도 이진법을 사용한 트릭이다. 아래 표를 기준으로 카드 안의 수들을 이진수로 바꿔 보자.
이 표를 기준으로 각 카드에 있는 수들의 공통점을 찾아보면 다음과 같다.
27을 예로 들어 보자. 27은 A, B, D, E 카드에 들어 있다. 27을 이진법으로 고치면 11011(₂)로 이것은 다음과 같이 풀이할 수 있다. 11011(₂) = 10000(₂) + 1000(₂) + 10(₂) + 1(₂)이며, 이것은 2⁴+2³+2+1 = 16+8+2+1과 같다. 즉 A, B, D, E 카드의 첫 번째 수의 합인 것이다.
컴퓨터가 이진법을 선택한 이유
‘삐삐삐 삐-삐-삐- 삐삐삐(짧은 신호 3번, 긴 신호 3번, 짧은 신호 3번)’ 영화 속에서 나오는 특이한 신호음을 들어 본 적이 있는가? 이 소리는 배가 난파되었을 때나 전쟁에서 적군에게 포위당했을 때와 같이 긴박한 상황에서 모스코드를 사용하여 보내는 SOS 신호이다. 모스코드는 미국인 사무엘 모스(Samuel Morse, 1791~1872)의 이름을 딴 것이다. 단음(·)과 장음(-)의 두 가지 기호만을 사용하여 문자 또는 수를 표현한 통신수단으로 0과 1만을 사용하는 이진법과 흡사하다. 그렇다면 이진법은 누구에 의해 언제부터 사용되었을까? 이진법을 처음 발명한 사람은 독일의 수학자 고트프리트 빌헬름 라이프니츠(Gottfried Wilhelm von Leibniz : 1646~1716)이다. 십진법에 익숙한 당시 사람들에게 이진법은 생소하고 불편하여 널리 사용되지 않았지만 십진법보다 논리 조립이 간단하고 전자, 전기 신호로 나타내기 편리하여 컴퓨터에서 사용하게 되었다. 이후 컴퓨터와 데이터 통신이 널리 쓰이는 현대에 와서는 그 중요성이 더욱 커졌다.
정확한 데이터가 맞을까?
정보화 사회에 있어서 데이터의 신뢰성은 굉장히 중요한 부분을 차지한다. 내가 받은 데이터에 오류가 있는 것인지 그렇지 않은 것인지를 매번 의심해야 한다면 어떨지 상상해 보자. 지금처럼 데이터 통신이 발달된 사회는 오지 않았을 수도 있다.
디지털 신호는 기본적으로 신호가 ‘있다’, ‘없다’ 이 두 가지 상태로 구분하며, 신호가 있을 때를 1, 없을 때를 0으로 표시한다. 사용자가 전송하고자 하는 데이터는 모두 0 또는 1의 디지털 신호로 변환되는 인코딩 과정을 거쳐 전송된다. 디지털 신호로 정보가 전송되는 동안 노이즈나 다른 장애가 생기면 신호가 있다, 없다를 반복하여 제대로 된 신호가 가지 못하는 경우가 발생한다. 예를 들어 설명해 보자. ‘100’이란 수 정보를 전달하려고 한다. 컴퓨터는 이 정보를 디지털 신호인 ‘1100100’으로 변환하고 전송하였다. 전송 과정 중에 순간적 오류가 생겨 신호를 줘야 하는 부분에서 신호를 주지 않고, 신호를 주지 않아야 하는 부분에서 신호를 주었다면 전송받은 데이터는 ‘0011011’이 된다. 즉, 수신된 정보는 ‘27’이 되는 것이다.
이렇듯 신뢰성 있는 통신을 위해서 데이터에 오류가 있는지 없는지를 확인하는 작업은 꼭 필요하다.
패리티 비트로 오류 발견하기
디지털 데이터에서 정보를 저장하는 최소 단위를 비트(binary digit=bit)라고 하고, 문자를 저장하는 최소의 단위는 8개의 비트가 모인 바이트(byte)라고 한다. 하나의 비트는 0 또는 1이란 두 개의 정보를 가질 수 있기 때문에 비트가 한 개씩 늘어날 때마다 표현 가능한 정보는 2의 거듭제곱 꼴로 늘어나게 된다. 바이트의 경우 8개의 비트가 모여 총 256개의 정보 표현이 가능하다. 한편, 미국에서 데이터 통신으로 사용하는 문자로는 영문 알파벳 대문자 26개, 소문자 26개, 숫자 10개, 특수문자 32개, 공백문자 1개가 있고, 출력이 불가능한 제어문자로는 33개가 있다. 이 문자들을 모두 표시하기 위해서는 총 128개의 정보를 구분할 수 있어야 하므로 최소 7개의 비트(개)가 필요하다. 문자를 저장하는 최소 단위로 바이트를 사용하는 컴퓨터에서 미국에서 사용하는 모든 문자를 사용하면 한 개의 비트 공간이 남아 있게 된다. 즉 버려지는 정보공간이 생긴다는 의미이다. 사람들은 이 공간을 버리지 않고, 오류 여부를 확인하는 데 사용하였다. 이를 ‘패리티 비트’라고 부른다.
패리티 비트는 다음과 같이 짝수 패리티나 홀수 패리티 중 하나로 결정한다.
● 짝수 패리티 : 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트 값을 0 또는 1로 결정
● 홀수 패리티 : 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트 값을 0 또는 1로 결정
〈그림 3〉의 경우 전송하려는 데이터 비트의 1의 개수가 3개이므로 짝수 패리티는 마지막 패리티 비트 자리에 1을 넣어 준다. 이때, 데이터 중 하나의 비트가 변경되었다고 가정해 보자. 짝수였던 1의 개수가 홀수 개로 바뀌게 된다. 즉, 홀짝성이 바뀜으로 오류가 있음을 알게 된다.
홀수 패리티를 준 경우는 어떨지 문제를 풀어 보면서 살펴보자. 위의 5개의 데이터 중에서 단 하나의 데이터에서 비트 하나가 변경되었다. 오류가 발생한 데이터는 몇 번일까?
정답을 찾는 건 아주 간단하다. 해당 데이터의 패리티 비트는 홀수 패리티이다. 즉, 전체 데이터의 1의 개수가 홀수여야 한다. ①번의 경우 1의 개수는 8개이므로 오류가 발생한 데이터라고 할 수 있다. 이렇게 홀짝성으로 오류를 검출하는 패리티 비트 검사는 매우 간단하고 쉬운 방법이지만 큰 약점이 존재한다. 오류가 난 위치를 알 수 없어 정정할 수 없고, 하나의 비트가 아닌 여러 개의 비트에서 한꺼번에 에러가 발생하면 단순 홀짝성으로 오류를 검출할 수 없다는 것이다.
해밍코드와 마법의 카드
패리티 비트의 약점을 보완한 방법이 해밍코드(Hamming code)이다. 해밍코드는 수학자 리처드 웨슬리 해밍(Richard Wesley Hamming)의 이름에서 유래되었다. 이 방법을 사용하면 오류를 검출할 뿐만 아니라 오류의 위치를 발견하고 정정까지 가능하다. 방법은 다음과 같다.
2의 거듭제곱번째 위치에 있는 비트들을 패리티로 사용한다. 즉, 1, 2, 4, 8, 16, 32, … 번째는 패리티 비트가 들어가고, 나머지 공간에 데이터 비트가 들어간다.
데이터 비트 사이에 들어가 있는 패리티 비트들은 아래와 같이 각각의 자리에 있는 비트들이 전송 중 오류가 발생했는지 여부를 확인한다.
● P1의 패리티 값 : 1, 3, 5, 7, 9, 11, … 의 값들의 패리티 검사를 통해 정함
● P2의 패리티 값 : 2, 3, 6, 7, 10, 11, … 의 값들의 패리티 검사를 통해 정함
● P3의 패리티 값 : 4, 5, 6, 7, 12, 13, 14, 15, … 의 값들의 패리티 검사를 통해 정함
● P4의 패리티 값 : 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, … 의 값들의 패리티 검사를 통해 정함
각각의 패리티 비트가 검사하는 자릿수를 자세히 살펴보자. 마법의 카드에 적힌 수 패턴과 동일한 패턴이라는 것을 발견할 수 있을 것이다. 각 카드에서 첫 번째 칸의 수가 패리티 비트 자릿수이고, 그 밖에 카드에 적힌 수는 패리티 비트가 오류 검사하는 비트들의 자릿수와 같다. 단순한 우연이라고 생각하는가? 그렇지 않다. 해밍코드는 마법의 카드와 동일한 원리를 갖는다. 데이터를 디지털 신호로 고쳤을 때, 끝자리가 1인 자릿수, 끝에서 두 번째 자리가 1인 자릿수, 끝에서 세 번째 자리가 1인 자릿수끼리 모아서 오류를 검증한다. 백문이 불여일견. 오류를 발견하고, 이를 정정하는 과정까지 예제를 통해 살펴보도록 하자. 우선 〈그림 4〉를 해밍코드로 수정해 보자. (해밍코드 수정 과정 참조)
해밍코드가 완성되었다면 임의로 오류를 발생시켜 보자. 예를 들어 〈그림 4〉처럼 오류가 발생한 데이터 비트를 자리라고 하면 9번째 자리가 0에서 1로 바뀐다. 이제 이 코드를 전달받은 컴퓨터의 입장이 되어 보자. 먼저 짝수 패리티가 맞는지 확인해야 한다. 각 패리티 비트마다 짝수가 맞으면 ‘0’, 홀수이면 ‘1’을 적는다.
〈그림 6〉과 같이 짝수 패리티를 맞추면 1001 값이 나온다. 이 값을 십진수로 고치면 2³+1=9가 나온다. 전달받은 컴퓨터는 9라는 값을 통해 9번째 자리에서 오류가 발생했다는 것으로 판단한다. 어떤 자리에 오류가 발생한 것인 줄 안다면 정정도 가능하다. 9번째 자리의 값을 1에서 0으로 바꾸어 값을 출력하게 된다.
데이터에서 오류를 찾아 정정까지 할 수 있는 해밍코드의 기법이 이진법을 사용한 트릭 마법과 같을 것이라고 예상할 수 있었을까? 지금 접한 해밍코드에도 약점은 있다. 여러 개의 비트에서 오류가 한꺼번에 발생할 때는 오류를 정정할 수 없다. 이러한 경우에는 또 다른 기법으로 오류를 발견하고, 정정할 수 있을 것이다. 생각만 해도 복잡하고 어려울 것 같다. 하지만, 어쩌면 우리가 모르는 다양한 기법과 기술력 안에도 해밍코드의 원리처럼 쉽게 접할 수 있는 간단한 수학적 원리가 숨겨져 있을 수 있다.⊙
1부터 31까지의 수가 적힌 5장의 카드가 있다. 이 카드는 당신이 생각하는 수를 맞힐 수 있는 마법의 카드이다.
1부터 31까지 수 중에서 하나의 수를 생각해 보자. A, B, C, D, E의 카드 중에서 선택한 수가 포함되어 있는 카드를 고르고, 그 카드의 첫 번째 칸의 수를 서로 더해 보자. 당신이 선택한 수가 맞는가? 만약 틀렸다면 계산에 실수가 있었을 것이다. 다시 한 번 해 보자. 방법은 동일하다. 1부터 31까지 수 중에서 처음 선택한 수와 다른 수를 선택하고, 선택한 수의 카드에서 색칠된 칸의 수를 더해 보자. 이번에도 당신이 선택한 수가 나왔을 것이다. 어떤 원리로 당신이 생각한 수를 모두 맞힐 수 있는 것일까? 눈치챈 사람도 있을 것이다. 정답은 진법이다. 그중에서도 이진법을 사용한 트릭이다. 아래 표를 기준으로 카드 안의 수들을 이진수로 바꿔 보자.
이 표를 기준으로 각 카드에 있는 수들의 공통점을 찾아보면 다음과 같다.
27을 예로 들어 보자. 27은 A, B, D, E 카드에 들어 있다. 27을 이진법으로 고치면 11011(₂)로 이것은 다음과 같이 풀이할 수 있다. 11011(₂) = 10000(₂) + 1000(₂) + 10(₂) + 1(₂)이며, 이것은 2⁴+2³+2+1 = 16+8+2+1과 같다. 즉 A, B, D, E 카드의 첫 번째 수의 합인 것이다.
컴퓨터가 이진법을 선택한 이유
 |
| 전신기와 모스부호를 발명한 사무엘 모스. |
 |
| 〈그림1〉 모스부호로 표시한 SOS. |
 |
| 이진법을 창안한 고트프리트 라이프니츠. |
정확한 데이터가 맞을까?
정보화 사회에 있어서 데이터의 신뢰성은 굉장히 중요한 부분을 차지한다. 내가 받은 데이터에 오류가 있는 것인지 그렇지 않은 것인지를 매번 의심해야 한다면 어떨지 상상해 보자. 지금처럼 데이터 통신이 발달된 사회는 오지 않았을 수도 있다.
디지털 신호는 기본적으로 신호가 ‘있다’, ‘없다’ 이 두 가지 상태로 구분하며, 신호가 있을 때를 1, 없을 때를 0으로 표시한다. 사용자가 전송하고자 하는 데이터는 모두 0 또는 1의 디지털 신호로 변환되는 인코딩 과정을 거쳐 전송된다. 디지털 신호로 정보가 전송되는 동안 노이즈나 다른 장애가 생기면 신호가 있다, 없다를 반복하여 제대로 된 신호가 가지 못하는 경우가 발생한다. 예를 들어 설명해 보자. ‘100’이란 수 정보를 전달하려고 한다. 컴퓨터는 이 정보를 디지털 신호인 ‘1100100’으로 변환하고 전송하였다. 전송 과정 중에 순간적 오류가 생겨 신호를 줘야 하는 부분에서 신호를 주지 않고, 신호를 주지 않아야 하는 부분에서 신호를 주었다면 전송받은 데이터는 ‘0011011’이 된다. 즉, 수신된 정보는 ‘27’이 되는 것이다.
이렇듯 신뢰성 있는 통신을 위해서 데이터에 오류가 있는지 없는지를 확인하는 작업은 꼭 필요하다.
패리티 비트로 오류 발견하기
디지털 데이터에서 정보를 저장하는 최소 단위를 비트(binary digit=bit)라고 하고, 문자를 저장하는 최소의 단위는 8개의 비트가 모인 바이트(byte)라고 한다. 하나의 비트는 0 또는 1이란 두 개의 정보를 가질 수 있기 때문에 비트가 한 개씩 늘어날 때마다 표현 가능한 정보는 2의 거듭제곱 꼴로 늘어나게 된다. 바이트의 경우 8개의 비트가 모여 총 256개의 정보 표현이 가능하다. 한편, 미국에서 데이터 통신으로 사용하는 문자로는 영문 알파벳 대문자 26개, 소문자 26개, 숫자 10개, 특수문자 32개, 공백문자 1개가 있고, 출력이 불가능한 제어문자로는 33개가 있다. 이 문자들을 모두 표시하기 위해서는 총 128개의 정보를 구분할 수 있어야 하므로 최소 7개의 비트(개)가 필요하다. 문자를 저장하는 최소 단위로 바이트를 사용하는 컴퓨터에서 미국에서 사용하는 모든 문자를 사용하면 한 개의 비트 공간이 남아 있게 된다. 즉 버려지는 정보공간이 생긴다는 의미이다. 사람들은 이 공간을 버리지 않고, 오류 여부를 확인하는 데 사용하였다. 이를 ‘패리티 비트’라고 부른다.
패리티 비트는 다음과 같이 짝수 패리티나 홀수 패리티 중 하나로 결정한다.
● 짝수 패리티 : 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트 값을 0 또는 1로 결정
● 홀수 패리티 : 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트 값을 0 또는 1로 결정
〈그림 3〉의 경우 전송하려는 데이터 비트의 1의 개수가 3개이므로 짝수 패리티는 마지막 패리티 비트 자리에 1을 넣어 준다. 이때, 데이터 중 하나의 비트가 변경되었다고 가정해 보자. 짝수였던 1의 개수가 홀수 개로 바뀌게 된다. 즉, 홀짝성이 바뀜으로 오류가 있음을 알게 된다.
홀수 패리티를 준 경우는 어떨지 문제를 풀어 보면서 살펴보자. 위의 5개의 데이터 중에서 단 하나의 데이터에서 비트 하나가 변경되었다. 오류가 발생한 데이터는 몇 번일까?
정답을 찾는 건 아주 간단하다. 해당 데이터의 패리티 비트는 홀수 패리티이다. 즉, 전체 데이터의 1의 개수가 홀수여야 한다. ①번의 경우 1의 개수는 8개이므로 오류가 발생한 데이터라고 할 수 있다. 이렇게 홀짝성으로 오류를 검출하는 패리티 비트 검사는 매우 간단하고 쉬운 방법이지만 큰 약점이 존재한다. 오류가 난 위치를 알 수 없어 정정할 수 없고, 하나의 비트가 아닌 여러 개의 비트에서 한꺼번에 에러가 발생하면 단순 홀짝성으로 오류를 검출할 수 없다는 것이다.
해밍코드와 마법의 카드
 |
| 해밍코드를 창안한 리처드 해밍. |
2의 거듭제곱번째 위치에 있는 비트들을 패리티로 사용한다. 즉, 1, 2, 4, 8, 16, 32, … 번째는 패리티 비트가 들어가고, 나머지 공간에 데이터 비트가 들어간다.
데이터 비트 사이에 들어가 있는 패리티 비트들은 아래와 같이 각각의 자리에 있는 비트들이 전송 중 오류가 발생했는지 여부를 확인한다.
● P1의 패리티 값 : 1, 3, 5, 7, 9, 11, … 의 값들의 패리티 검사를 통해 정함
● P2의 패리티 값 : 2, 3, 6, 7, 10, 11, … 의 값들의 패리티 검사를 통해 정함
● P3의 패리티 값 : 4, 5, 6, 7, 12, 13, 14, 15, … 의 값들의 패리티 검사를 통해 정함
● P4의 패리티 값 : 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, … 의 값들의 패리티 검사를 통해 정함
각각의 패리티 비트가 검사하는 자릿수를 자세히 살펴보자. 마법의 카드에 적힌 수 패턴과 동일한 패턴이라는 것을 발견할 수 있을 것이다. 각 카드에서 첫 번째 칸의 수가 패리티 비트 자릿수이고, 그 밖에 카드에 적힌 수는 패리티 비트가 오류 검사하는 비트들의 자릿수와 같다. 단순한 우연이라고 생각하는가? 그렇지 않다. 해밍코드는 마법의 카드와 동일한 원리를 갖는다. 데이터를 디지털 신호로 고쳤을 때, 끝자리가 1인 자릿수, 끝에서 두 번째 자리가 1인 자릿수, 끝에서 세 번째 자리가 1인 자릿수끼리 모아서 오류를 검증한다. 백문이 불여일견. 오류를 발견하고, 이를 정정하는 과정까지 예제를 통해 살펴보도록 하자. 우선 〈그림 4〉를 해밍코드로 수정해 보자. (해밍코드 수정 과정 참조)
해밍코드가 완성되었다면 임의로 오류를 발생시켜 보자. 예를 들어 〈그림 4〉처럼 오류가 발생한 데이터 비트를 자리라고 하면 9번째 자리가 0에서 1로 바뀐다. 이제 이 코드를 전달받은 컴퓨터의 입장이 되어 보자. 먼저 짝수 패리티가 맞는지 확인해야 한다. 각 패리티 비트마다 짝수가 맞으면 ‘0’, 홀수이면 ‘1’을 적는다.
〈그림 6〉과 같이 짝수 패리티를 맞추면 1001 값이 나온다. 이 값을 십진수로 고치면 2³+1=9가 나온다. 전달받은 컴퓨터는 9라는 값을 통해 9번째 자리에서 오류가 발생했다는 것으로 판단한다. 어떤 자리에 오류가 발생한 것인 줄 안다면 정정도 가능하다. 9번째 자리의 값을 1에서 0으로 바꾸어 값을 출력하게 된다.
데이터에서 오류를 찾아 정정까지 할 수 있는 해밍코드의 기법이 이진법을 사용한 트릭 마법과 같을 것이라고 예상할 수 있었을까? 지금 접한 해밍코드에도 약점은 있다. 여러 개의 비트에서 오류가 한꺼번에 발생할 때는 오류를 정정할 수 없다. 이러한 경우에는 또 다른 기법으로 오류를 발견하고, 정정할 수 있을 것이다. 생각만 해도 복잡하고 어려울 것 같다. 하지만, 어쩌면 우리가 모르는 다양한 기법과 기술력 안에도 해밍코드의 원리처럼 쉽게 접할 수 있는 간단한 수학적 원리가 숨겨져 있을 수 있다.⊙
월간조선
댓글 없음:
댓글 쓰기