[Data Communication] 비트오류 탐지 및 복구(수정)
우리가 데이터를 실제 전송하는 물리 계층은 신뢰할 수 없는 전송 (Unreliable Transmisson) 입니다. 왜냐하면, 물리 계층에서 전송하는 동안 간섭, 왜곡 등의 이유로 우리가 보내고자 의도했던 데이터가 정상적으로 전송되지 않을 확률이 있기 때문입니다.
예를 들어, "데이터통신" 이라는 글자를 전송했는데 수신자 측에서 받은 글자는 "데ㅇ ㅣㅌ ㅓㅌ ㅗ ㅇ 신" 이라고 합시다. 분명히 송신자가 전송한 데이터와는 상이하므로 오류가 발생했음을 우리는 인지할 수 있습니다. 그리고 우리는 잘못 수신한 "데ㅇ ㅣㅌ ㅓㅌ ㅗ ㅇ 신" 을 "데이터통신" 으로 오류를 수정할 수도 있습니다.
실제 데이터 통신 상에서는 이러한 과정을 어떻게 수행하는 지 알아봅시다.
먼저 비트오류 탐지 및 복구를 학습할 때 필요한 기초 용어에 대해 알아보겠습니다.
기초 용어
데이터 워드 : 원래의 데이터 k bits
코드 워드 : 원래의 데이터 k bits + 오류 탐지를 위한 데이터 r bits
송신자 : 코드워드를 전송하는 쪽
수신자 : 코드워드를 수신하는 쪽
+ 데이터 통신은 비신뢰성 채널에서 이루어진다.
비트 오류의 탐지 및 복구를 수행하는 Hamming code
해밍 코드는 이진 선형부호의 일종이며, 거리가 3이므로 1개 이하의 비트 에러를 수정할 수 있습니다.
해밍코드에 대해 자세히 알아보기에 앞서 해밍코드를 이해하기 위한 용어 두가지를 살펴보겠습니다.
해밍 거리 (Hamming Distance) : 코드워드 A 와 코드워드 B 가 있을 때 A 를 B로 (혹은 B를 A로) 변환하기 위해서 바꾸어주어야 하는 최소 비트개수. 두 코드워드 간의 XOR 연산을 통해 해밍 거리를 계산할 수 있습니다.
최소 해밍 거리 : 모든 코드워드 간의 해밍 거리 중 가장 작은 값
해밍 코드를 만드는 방법
송신자가 수신자에게 0 또는 1 을 전송한다고 합시다. 당연히 수신자는 0 또는 1 을 받을 것입니다.
하지만, 수신자가 받은 0 또는 1 이 정말 송신자가 전달한 비트가 맞을까요? 혹시 데이터 송신 중 오류로 잘못 전달된 것은 아닐까요?
수신자는 수신한 데이터가 올바르게 전송된 데이터인지 확신할 수 없습니다.
이를 해결하기 위해 올바르게 전송된 데이터인지 검증 (Validation) 하기 위해서 검증을 위한 데이터를 덧붙인 코드워드를 생성합니다.
- 0 을 송신할 때는 반드시 000 으로 전송 (1비트 데이터 워드 -> 3비트 코드워드)
- 1 을 송신할 때는 반드시 111 으로 전송 (1비트 데이터 워드 -> 3비트 코드워드)
000, 111 이 두가지 코드워드만이 오직 유효한 코드워드입니다.(Valid Codeword) 이외 다른 형태의 3 bits 데이터는 모두 오류가 발생한 코드워드입니다. (Corrupted Codeword, ex. 001, 010, 011 etc.)
그리고, 유효하지 않은 코드워드를 수신하였을 때 수신자는 유효한 코드워드 중 해밍거리가 짧은 쪽으로 코드워드를 수정합니다.
위와 같은 가정 하에 다음과 같은 상황이 발생할 수 있습니다.
- Case 1. 송신자가 000 을 전송하고 수신자가 001 을 수신했을 때 (1 bit error occurred)
- 유효한 코드워드는 000과 111 이다. 001 은 이 두 가지 코드워드에 해당하지 않으므로 비트 오류가 발생하였음을 "탐지" 할 수 있다. 001 (Corrupted Codeword) 와 000 의 해밍 거리는 1 이고, 111 과의 해밍거리는 2이다. 따라서 000 으로 비트오류 복구를 수행한다.
- 이 경우, 송신자가 전송한 코드에 맞게 오류 복구가 수행되었다.
- Case 2. 송신자가 111 을 전송하고 수신자가 011 을 수신했을 때 (1 bit error occurred)
- 유효한 코드워드는 000과 111이다. 001 은 이 두 가지 코드워드에 해당하지 않으므로 비트 오류가 발생하였음을 "탐지" 할 수 있다. 011 (Corrupted Codeword) 와 000 의 해밍거리는 2이고, 111 과의 해밍거리는 1이다. 따라서 111 으로 비트오류 복구를 수행한다.
- 이 경우, 송신자가 전송한 코드에 맞게 오류 복구가 수행되었다.
- Case 3. 송신자가 000 을 전송하고 수신자가 011 을 수신했을 때 (2 bits error occurred)
- 유효한 코드워드는 000과 111이다. 011 은 이 두 가지 코드워드에 해당하지 않으므로 비트 오류가 발생하였음을 "탐지" 할 수 있다. 011 (Corrupted Codeword) 와 000 의 해밍거리는 2이고, 111 과의 해밍거리는 1이다. 따라서 111 으로 비트오류 복구를 수행한다.
- 이 경우, 송신자가 전송한 코드와 다르게 오류 복구가 수행되었다.
해밍 코드의 조건과 한계점 정리
탐지 조건
해밍 코드를 이용해 비트 오류를 탐지하기 위해서는 위와 같은 조건이 요구됩니다. 그림에 대한 부연설명을 조금해보면, 유효한 코드워드 사이의 해밍 거리가 s+1 일 때, s 개의 오류를 탐지할 수 있다는 것입니다.
우리가 앞서 다뤄본 예시에서는 유효한 코드워드 000과 111의 해밍 거리가 3이었고 따라서 2개 비트의 오류를 "탐지" 할 수 있었습니다.
탐지 + 복구 조건
해밍 코드를 이용해 비트 오류를 "탐지" 하고 "복구" 까지 수행하기 위해서는 위와 같은 조건이 요구됩니다. 마찬가지로 부연 설명을 조금 해보면, 유효한 코드워드 간의 해밍 거리가 2t + 1 일 때 t 비트를 수정할 수 있습니다.
위에서 우리가 다뤄본 예시에서 유효한 코드워드 000과 111의 해밍거리가 3 = ( 2 * 1 + 1 ) 이므로, 1개의 오류가 발생한 Corrupted Codeword 에 대해서 정확하게 오류 수정을 수행할 수 있었습니다.
해밍 코드 개념 이해 시 주의할 점
- 오류 탐지 및 복구를 위해 해밍 코드를 이용하지만, 해밍 코드를 이용한다고 해서 모든 오류를 탐지하고 복구할 수 없습니다.
- 만약 3비트 에러가 발생한다면, (ex 000 -> 111) 수신자는 오류를 "탐지" 조차 할 수 없습니다.
- 오류를 수정한다고 해서 반드시 올바르게 수정할 수 있는 것이 아닙니다. 2t+1 조건의 t 보다 큰 개수의 비트 오류가 발생할 경우, 오류 복구를 수행하지만, 올바르지 않은 복구를 수행하게 됩니다.
다음으로 비트 오류의 탐지 및 복구를 수행하는 다른 방법인 Forward Error Correction 에 대해 알아봅시다.
FEC (Forward Error Correction)
FEC 이란? : 정보를 단방향으로 전송할 때 수신기에서 오류정정부호(errorcorrecting codes)를 이용하여 오류의 검출과 정정을 동시에 수행하는 방법입니다.
이 FEC 방법은 갈루아체 수학 이론에 기반을 두고 있습니다.
FEC 방법을 이용하여 K bits 의 데이터 워드를 N bits 의 코드워드로 변환하여 전송할 때, (N-K)/2 개 이하의 비트 오류를 검출하고 수정할 수 있습니다.
이제, 비트 오류의 "탐지" 만을 수행하는 방법에 대해 알아보겠습니다.
Parity
컴퓨터공학 전공자라면 누구나 한 번쯤은 들어봤을만한 Parity Bit 에 대한 이야기입니다.
보내고자 하는 코드워드의 0 또는 1 비트의 개수가 짝수 / 홀수가 되도록 에러 검출 비트를 데이터 워드에 붙이는 방법입니다.
Parity Bit 의 한계점은 짝수개의 비트오류가 발생 시 오류 검출이 불가능해진다는 것입니다.
CRC (Cyclic Redundant Check, 순환 중복 검사)
CRC 에서는 두가지 키워드가 중요합니다.
다항식 (Polynomial) : CRC 는 다항식의 나눗셈을 이용하여 계산됩니다. 따라서 제수 (Divisor) 가 되는 다항식이 필요합니다.
CRC : CRC 는 다항식의 나눗셈을 수행한 후의 나머지를 의미합니다.
CRC 는 다음과 같은 Step 으로 계산할 수 있습니다.
Step 1. 전송하고자 하는 데이터워드 + Polynomial 의 degree 만큼의 0 bits 를 데이터워드 뒤에 이어 붙입니다.
Step 2. Polynomial 의 계수를 바탕으로 divisor 비트를 계산합니다. (ex. x^3+x+1 -> 1011)
Step 3. Polynomial 로 수정된 데이터워드를 나눈다.
Step 4. 나머지를 원본 데이터워드 뒤에 붙여 코드워드를 생성한다.
이렇게 계산한 CRC 를 이용하여 오류 검출을 수행할 수 있습니다. 수신자가 polynomial 로 수신한 데이터를 나누었을 때 나머지가 0 이 아니면, 오류가 발생했음을 알 수 있습니다.
이러한 CRC 방식은 다양한 곳에서 사용됩니다.
Checksum
체크섬은 보내고자 하는 데이터를 4비트로 쪼개서 다 더한 뒤 1의 보수를 취한 값을 오류 검출 코드로 데이터 워드 뒤에 붙여 코드워드를 생성한 뒤 전송하는 방법입니다.
송신측에서 Checksum 을 데이터워드 뒤에 붙여 코드워들 생성해 전송합니다. 수신측은 동일한 방법으로 체크섬을 계산하고 계산된 체크섬 값이 0 이 아니면 오류가 발생했음을 "탐지" 할 수 있습니다.
지금까지 알아본 내용을 정리하면 아래와 같습니다.
비트 오류의 탐지 및 복구 (수정)
비트 오류의 탐지
- Parity
- CRC
- Checksum
비트 오류의 탐지 및 복구
- Hamming Code
- Forward Error Correction
위에서 알아본 비트 오류의 복구 방법은 전송 이전에 복구할 수 있는 데이터를 덧붙이는 방법이었습니다. 이러한 방법은 Overhead 가 큰 단점이 있습니다.
따라서 복구 방법에는 ARQ 라는, 오류가 발생하면 데이터의 재전송을 요청하는 방법이 있습니다. 이에 대해서는 다음에 알아보겠습니다.