오류 검출 방식(패리티 검사, CRC, 체크섬, 해밍코드)::네트워크

 OSI 7 계층에서 Data Link Layer에 여러 기능 중 가장 중요한 기능은 오류를 감지하고 수정하는 기능입니다.

(OSI 7 계층 모형을 다시 알고싶다면 -> https://junboom.tistory.com/16)

 

 

 데이터가 전송되는 도중에 노이즈로 인해 1을 0으로 인식하고, 0을 1로 인식하는 문제가 발생할 수 있습니다.

 Data Link Layer에서는 이러한 에러를 검출하고, 수정하는 역할을 합니다.

 

오류 발생 원인

 

1) 감쇠(Attenuation)

 전송 신호가 전송 매체를 통과하는 과정에서 거리에 따라 점차 약해지는 현상

 

2) 지연 왜곡(Delay Distortion)

 주로 유선 전송 매체에서 발생하며 하나의 전송 매체를 통해 여러 신호를 전달했을 경우 주파수에 따라 속도가 달라지면서 생기는 오류

 

3) 상호 변조 잡음(Intermodulation Noise)

 서로 다른 주파수들이 하나의 전송 매체를 공유할 때 주파수 간 합이나 차로 인해 새로운 주파수가 생성되는 잡음

 

4) 충격 잡음(Impulse Noise)

 번개와 같은 외부적인 충격이나 기계적인 통신 시스템의 결함 등 순간적으로 높은 진폭이 발생하는 잡음

 

 

Single-bit Error

sent      -> 00000100

received -> 00010100

 

 1 bit가 바뀌어서 전송된 것을 Single-bit Error라고 합니다.

 하지만 인터넷이 매우 빠른 속도로 전송되기 때문에 보통은 잘 발생하지 않고, 2 bit 이상 바뀌어서 전송되는 Burst Error가 발생합니다.

 

 어디서부터 오류가 발생했는지 해당 오류 길이를 Length of Burst라고 합니다.

 이러한 전송 오류를 제어하는 Error Correction 방식에는 FEC와 BEC가 있습니다.

 

FEC(Forward Error Correction : 전진 에러 수정)

 데이터 전송 과정에서 발생한 오류를 검출해 재전송 요구 없이 스스로 수정하는 방식입니다.

 송신측에서 문자나 프레임에 오류 검출을 위한 확장 데이터를 추가해 전송해 수신측에서 이를 활용해 수신한 데이터에 오류가 발생했는지 검출하고 수정합니다.

 연속적인 데이터 전송이 가능하지만, 확장 데이터로 인해 전송 효율이 떨어집니다.

 

BEC(Backward Error Correction : 후진 에러 수정)

 데이터 전송 과정에서 오류가 발생하면 송신측에 재전송을 요구하는 방식입니다.

 패리티 검사, CRC 등을 이용해 오류를 검출하고, 자동 반복 요청(ARQ: Automatic Repeat reQuest)으로 오류를 제어합니다.

 (오류 제어 방식과 관련한 슬라이딩 윈도우 프로토콜 다시 학습하기 -> https://junboom.tistory.com/22)

 

 

 여기서 이용하는 패리티 검사, CRC, 체크섬, 해밍코드에 대해서 알아보겠습니다.

 

 

1. 패리티 검사(Parity Check)

 

 1의 개수를 짝수 개로 맞춰서 보낼지(Even Parity), 홀수 개로 맞춰서 보낼지(Odd Parity) 송신측과 수신측이 약속하고 여분의 bit(패리티 비트)를 채워 보내는 것입니다.

 

 하지만 패리티 비트는 Single-bit Error와 같이 홀수 개의 오류만 검출할 수 있고, 짝수 개의 오류는 검출하지 못하는 문제점이 발생합니다.

 

 이를 해결하기 위해 Two-dimensional Parity Check(2차원 패리티 검사)가 나왔습니다.

 

 Two-dimensional Parity Check는 수평(LRC: Longitudinal Redundancy Check)과 수직(VRC: Vertical Redundancy Check)으로 패리티 비트를 추가하고, 모두 카운트합니다. 만약 수평에서 짝수 개의 비트가 바뀐다고 해도 수직 패리티 검사에서 검출할 수 있습니다.

 

 하지만 수평과 수직으로 짝수 개씩 똑같이 바뀐다면 검출이 불가능 합니다. 근본적으로 이러한 패리티 비트의 한계가 있기 때문에 에러 검출 능력이 떨어집니다.

 

ex) Even Parity에서 검출 불가

sent                 received

1001 l 0            1001 l 0

0110 l 0            0000 l 0

0110 l 0    ->     0000 l 0

1001 l 0            1001 l 0

ㅡㅡㅡ 0             ㅡㅡㅡ 0

0000   0            0000  0

 

 

2. CRC(Cyclic Redundancy Chcek: 순환 중복 검사)

 

 패리티 검사의 한계를 채워주기 위해 나온 오류 검출 방식입니다.

 데이터에 오류가 발생했는지 확인하는 코드를 데이터 뒤에 확장 데이터를 덧붙여 보내는 방식입니다.

 

송신부

 

1) CRC 발생 코드를 선정합니다.

2) CRC 발생 코드의 최고 차수만큼 기존 데이터 뒤, 확장 데이터에 0을 붙입니다.

3) 기존 데이터 + 확장 데이터를 CRC 발생 코드로 Modulo-2 연산을 이용해 나눕니다.

4) 나머지가 0이면 확장 데이터를 그대로 전송합니다.

5) 나머지가 0이 아니라면 기존 데이터에 나머지를 붙여 전송합니다.

 

수신부

 

1) 수신된 코드를 동일한 CRC 발생 코드로 나눕니다.

2) 나머지가 0이면 오류가 발생하지 않은 것으로 판단합니다.

3) 나머지가 0이 아니라면 오류가 발생한 것으로 판단합니다.

 

Modulo-2 연산(XOR: Exclusive-OR과 동일)

0 +(-) 0 = 0

0 +(-) 1 = 1

1 +(-) 0 = 1

1 +(-) 1 = 0

 

 

3. 체크섬(Checksum)

 

 중복 검사의 한 형태로 오류 정정을 통해 공간이나 시간 속에서 송신된 자료의 무결성을 보호하는 단순한 방법입니다.

 

송신부

 

1) 모든 byte 데이터를 더합니다.

2) 캐리니블(최상위 니블, 가장 앞에 위치한 4bit를 가리키는 컴퓨터 용어)을 버립니다.

3) 2의 보수를 취해 체크섬을 만듭니다.

 

수신부

 

1) 모든 byte 데이터와 체크섬을 더합니다.

2) 캐리니블을 버립니다.

3) 0x00이 나오면 오류가 발생하지 않은 것으로 판단합니다(오류가 발생해도 나오는 예외가 있음).

4) 0x00이 나오지 않으면 오류가 발생한 것으로 판단합니다.

 

ex)

0x84, 0xF2, 0x10, 0x55 데이터가 들어왔다고 가정합니다.

 

송신부

1) 모든 byte 데이터를 더합니다.

0x84 = 132,

0xF2 = 242,

0x10 = 16,

0x55 = 85

132 + 242 + 16 + 85 = 475

475 = 0x1DB

 

2) 캐리니블을 버립니다.

0x1DB = 0001 1101 1011 (2) -> 1101 1011

 

3) 2의 보수를 취해 체크섬을 만듭니다.

기존 :        1101 1011

1의 보수 :  0010 0100

2의 보수 :  0010 0101

체크섬 :     0010 0101 = 0x25

 

수신부

1) 모든 byte 데이터와 체크섬을 더합니다.

0x1DB + 0x25 = 0x200

 

2) 캐리니블을 버립니다.

0x200 = 0010 0000 0000 (2) -> 0000 0000

 

3) 0x00이 나왔기 때문에 오류가 발생하지 않은 것으로 판단합니다.

 

 

4. 해밍코드(Hamming Code)

 

 하나의 데이터 단위에 대해 충분한 패리티 비트를 추가해 오류를 검출하고, 수정까지 할 수 있는 방식입니다.

 

송신부

 

1) 아래 부등식을 만족하는 최소 p를 구합니다(p : 추가할 패리티 비트 수, n : 데이터의 비트 수).

2^p >= p + n + 1

2) 2^(k-1) 번째 자리마다 자신의 범위에 대한 Even/Odd Parity를 가지는 패리티 비트를 추가합니다.

 

수신부

 

1) 패리티 비트마다 유효성 검사를 실행합니다.

2) p1부터 패리티 비트에 오류가 없으면 0, 있으면 1을 기록합니다.

3) 기록된 것을 10진수로 변환한 수가 오류가 발생된 자리수를 나타냅니다.

 

ex)

1010 데이터가 들어왔다고 가정합니다.

 

1) 2^p >= p + 4 + 1 -> p >= 3

 

   7 6 5  4  3 2  1

2) 0 1 0 ㅁ 1 ㅁ ㅁ -> 0 1 0 1 1 0 1 (Even Parity)

 

7, 6, 5번째 자리 + 4번째 자리(패리티 비트) = 0 -> p3 패리티 비트 = 1

7, 6, 3번째 자리 + 2번째 자리(패리티 비트) = 0 -> p2 패리티 비트 = 0

7, 5, 3번째 자리 + 1번째 자리(패리티 비트) = 0 -> p1 패리티 비트 = 1

Even Parity이기 때문에 Modulo-2 연산에 의해 0이 나와야 합니다.

따라서 해밍코드는 0101101가 됩니다.

 

만약, 수신부에서 1101101이 수신됐다면,

 

7 6 5 4 3 2 1

1 1 0 1 1 0 1 -> 1

p1(1, 3, 5, 7번째 자리 중 오류 -> 1을 기록)

 

7 6 5 4 3 2 1

1 1 0 1 1 0 1 -> 1

p2(2, 3, 6, 7번째 자리 중 오류 -> 1을 기록)

 

7 6 5 4 3 2 1

1 1 0 1 1 0 1 -> 1

p3(4, 5, 6, 7번째 자리 중 오류 -> 1을 기록)

 

111 (2)가 기록되었고, 111 (2) = 7, 즉 7번째 자리에서 오류가 난 것을 알 수 있습니다.