[데이터링크 계층] 오류 검출 (Error Detection)

오류의 유형 (Error Types)

단일 비트 오류 (Single-bit Error)

주어진 데이터 단위(문자 하나, 또는 패킷 전체 등)에서 오직 하나의 비트가 변경된 오류이다.

버스트 오류 (Burst Error)

데이터 단위에서 둘 이상의 연속적인 비트가 변경된 오류이다.

 

중복성 (Redundancy)

중복성은 에러를 감지하고 수정하는 것에 있어 핵심적인 개념이다. 우리는 오류를 검출하거나 수정하기 위해 데이터에 추가적인 비트를 보낸다. 이를 중복 비트(Redundant bit)라 하며, 이러한 중복 비트들은 송신자에 의해 더해지거나 수신자에 의해 제거된다.

 

코딩 (Coding)

송신자는 실제 데이터 비트와 관련된 중복 비트들을 전송한다. 수신자는 이 두 비트들 사이의 관계를 확인해 오류를 검출하거나 수정한다. 이러한 코딩은 블록 코딩과 컨볼루션(Convolution) 코딩으로 나뉜다.

블록 코딩 (Block Coding)

메시지를 데이터워드(Dataword)라는 k비트 단위 블록으로 쪼개어, 각 블록마다 중복 비트 r비트를 추가한다. 따라서 각 블록의 길이 n은 k + r이 된다. 결과적으로 생성되는 길이 n의 비트 블록을 코드워드(Codeword)라 한다.

k = 2, r = 1, n = 3인 경우

 

오류 검출 (Error Detection)

오류가 발생했는지 알아보는 것으로, 오류가 존재하는지에 대한 여부만 확인한다. 즉 오류가 몇 개 발생했는지에 대해서는 알 필요가 없다.

수신 측에서는 유효한 코드워드들에 대한 목록을 가지고 있다. 만약 전송된 코드워드가 유효하지 않다면, 오류가 발생한 것으로 간주한다. 위의 표를 다시 가져와보자.

이 표에서 데이터워드 00에 대한 유효 코드워드는 000이다. 만약 전송된 코드워드가 001이라면, 유효하지 않은 코드워드이므로 이는 오류로 간주된다.

하지만 만약 데이터워드 011의 오른쪽 두 비트가 손상되어 000이 전송된다면, 이는 유효한 코드워드로 인식될 것이다. 즉 이 경우에는 두 비트 이상에서 발생한 오류를 검출하지 못한다.

 

해밍 거리 (Hamming Distance)

오류 제어를 위해 사용되는 거리로, 길이가 같은 두 워드 간 다른 비트의 갯수이다. 즉, 두 워드에 대한 XOR 연산 결과값의 1 갯수이다. 예를 들어, 10101과 11110의 해밍 거리는 3이다.

이 중 최소 해밍 거리(Minimum Hamming Distance)를 통해 s개까지의 오류가 발생해도 이를 검출할 수 있다. s개까지의 오류를 검출할 수 있도록 하기 위해선 블록 코드의 최소 해밍거리는 s + 1이어야 한다. 이는 s개를 초과하는 비트에 대해 오류가 발생할 경우 손상된 코드워드가 유효 코드워드로 인식된다는 것을 의미한다.

이 표에서 각 코드워드 간의 최소 해밍 거리는 2이므로, 따라서 오직 단일 비트 오류만 검출할 수 있게 된다.

 

선형 블록 코드 (Linear Block Code)

두 유효 코드워드의 XOR 연산 결과로 다른 유효 코드워드를 생성하는 방법이다.

단순 패리티 검사 코드(Simple Parity Check Code)는 이러한 선형 블록 코드에 해당한다. 표에서 유효 코드워드 10010과 00011의 XOR 결과인 10001 역시 유효한 코드워드임을 확인할 수 있다.

 

패리티 검사 코드 (Parity Check Code)

패리티 비트(Parity bit)는 전체 데이터워드 중 1의 갯수가 짝수가 되도록 붙는다. 예를 들어 데이터워드가 1101001이면 1의 갯수가 4이므로, 추가되는 패리티 비트는 0이다. (홀수가 되도록 구현할 수도 있다)

데이터워드 a0 ~ a3에 대해 송신 측에서는 이들의 1 갯수에 따라 패리티 비트 r0을 추가해 수신 측에 전송한다.

수신 측에서는 전송받은 코드워드를 복호기의 검사기(Checker)에 넣어 오류를 검출한다. 이 때 검출의 결과는 신드롬(Syndrome, s0)을 통해 나타난다. 이 신드롬 값이 0이면 오류가 발생하지 않은 것으로, 코드워드는 수락되어 데이터워드를 추출한다. 만약 신드롬 값이 1이라면 이는 손상된(유효하지 않은) 코드워드로, 폐기된다.

만약 1011의 데이터워드를 전송하는 상황을 가정해 보자. 데이터워드 1011의 1은 3개이므로, 패리티 비트 1이 추가되고 10111이란 코드워드가 생성되어 보내진다.

만약 비트 하나가 손상되어 10011이라는 코드워드가 보내진다면, 코드워드의 1 갯수가 홀수이므로 검사기는 이 코드워드가 손상된 것임을 알 수 있다. 즉, 신드롬 값이 1이다. 패리티 비트는 1이 짝수 개가 되도록 붙기 때문이다.

하지만 만약 두 비트가 손상되어 00101이라는 코드워드가 보내진다면, 코드워드의 1 갯수가 짝수이므로 검사기는 이 코드워드를 유효한 것으로 판단한다. 즉, 신드롬 값이 0이다. 이를 통해 단순 패리티 검사 코드는 짝수 개의 오류를 검출할 수 없음을 알 수 있다.

 

순환 중복 검사 (CRC, Cyclic Redundancy Code)

순환 코드(Cyclic Code)에서는 유효 코드워드 하나를 Shift한 결과 또한 유효 코드워드가 된다.

순환 중복 검사는 이러한 순환 코드의 일종으로, LAN, WAN 등에 널리 사용된다.

CRC는 Divisor라는 요소를 통해 구현하는데, 데이터워드를 Divisor로 나눈 나머지(Remainder)를 데이터워드에 추가해 코드워드를 생성한다. 그림은 데이터워드 1001에 대한 코드워드를 생성하는 과정이다.

복호기는 코드워드를 Divisor로 나누어, 나머지를 신드롬 값으로 정한다. 손상이 없는 코드워드는 신드롬 값이 0이다.

전체 과정은 다음과 같다.

 

다항식 (Polynomial)

데이터의 0, 1 패턴을 계수가 0 또는 1인 다항식으로 표현할 수 있다.

다음은 다항식으로 표현된 데이터를 통해 CRC의 코드워드를 구하는 과정을 나타낸 것이다.

 

순환 코드 분석 (Cyclic Code Analysis)

순환 코드를 생성하는 Divisor를 생성기(Generator)라고 하자.

순환 코드를 생성하는 과정에서 사용되는 다음 항목들을 다항식으로 다음과 같이 나타낸다.

수신된 코드워드는 다음과 같이 표현할 수 있다. 

따라서 다음이 성립한다.

이는 순환 코드에서 g(x)로 나누어 떨어지는 오류는 검출되지 않음을 의미한다.

 

검사합 (Checksum)

검사합은 메시지의 길이와 관계없이 오류를 검출하는 기법이다. 데이터링크 계층보다는 네트워크 및 전송 계층에서 더 자주 사용된다. 다음과 같은 예시 상황에서 검사합 방법을 통해 오류를 검출하는 과정을 알아보자.

검사합 방법에서는 메시지를 일정 비트로 구간을 나눈다. 이 예시에서는 4비트로 나눈 숫자 (7, 11, 12, 0, 6)을 전송한다고 가정하자. 이 때 송신 측은 전송할 숫자의 전체 합(Checksum)을 추가해 보내게 된다. 즉, (7, 11, 12, 0, 6, 36)을 전송한다.

메시지가 수신 측에 전송되면, 수신 측에서는 마지막 Checksum을 제외한 5개의 숫자를 더한 결과와 전체합이 같은지 비교한다. 같다면 오류가 없는 것으로, Checksum을 제외한 숫자 5개를 Accept한다.

여기서 1의 보수 개념을 추가해 보내려는 숫자들에 대한 Checksum을 표현하는 비트 수를 줄일 수 있다. 메시지를 동일한 크기의 구간으로 나누어야 하기 때문이다.

예시의 전체합 36은 이진수로 100100이고, 이 수를 4비트씩 끊어 더하여 전체합을 4비트로 나타낸다. 즉 10 + 0100 = 0110 = 6이다. 이 값에 1의 보수를 취해 Checksum으로 전송한다. 따라서 전송되는 메시지는 (7, 11, 12, 0, 6, 9)이다. (6(0110)에 대한 1의 보수는 9(1001)이다.)

수신 측에서는 6개의 수를 모두 더한 값에 1의 보수를 취한 값을 확인한다. 오류가 없을 때 수신자는 (7, 11, 12, 0, 6, 9)를 받게 되고, 이를 모두 더하면 15를 얻을 수 있다. (초과되는 비트는 위와 같이 끊어 계산한다.) 이 15에 1의 보수를 취하게 되면 0을 얻을 수 있다. 이는 신드롬 값에 해당하며, 0일 경우 오류가 없음을 의미한다.

* 6개의 수에 1의 보수를 취한 후 합해도 결과는 같다.

* 일반적인 경우 메시지는 16비트 단위로 나뉜다.

 

※ 본 게시글은 『Data Communication and Network』 를 참고하여 작성되었습니다.