[network] Date-Link Layer 오류 검출 (Error Detection)

오류가 발생했는지 알아보는 것으로, 오류가 존재하는지에 대한 여부만 확인한다.

즉, 오류가 몇 개 발생했는지에 대해서는 알 필요가 없다.

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

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

 

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

참고: https://4legs-study.tistory.com/65

 

1. Hamming Distance

Block Coding에서는 오류를 검출하거나 수정하기 위해 Hamming Distance(해밍 거리)라는 개념을 사용한다.

해밍 거리란 길이가 같은 두 코드워드에서 서로 다른 비트의 개수를 의미한다.

즉, 두 코드워드를 XOR 연산했을 때 결과가 1인 비트의 개수와 같다.

 

예를 들어,

• 10101
• 11110

두 코드워드를 비교하면 서로 다른 비트가 3개이므로 해밍 거리는 3이다.

해밍 거리는 오류 검출 능력을 결정하는 중요한 기준이 된다.

전송 과정에서 비트가 손상되면 송신한 코드워드와 수신한 코드워드 사이의 해밍 거리가 증가하게 된다.

 

따라서 코드워드 집합의 최소 해밍 거리(Minimum Hamming Distance)가 클수록 더 많은 오류를 검출하거나 수정할 수 있다.

일반적으로 s개의 오류를 검출하기 위해서는 최소 해밍 거리가 s+1 이상이어야 한다.

 

 

2. Linear Block Code

오늘날 사용되는 대부분의 Block Coding은 Linear Block Code(선형 블록 코드)를 기반으로 한다.

선형 블록 코드란 두 개의 유효한 코드워드를 XOR 연산했을 때 결과 역시 유효한 코드워드가 되는 코드를 말한다.

이러한 성질 덕분에 오류 검출 과정을 단순하게 만들 수 있으며, 최소 해밍 거리도 쉽게 계산할 수 있다.

선형 블록 코드에서는 0이 아닌 유효한 코드워드 중 1의 개수가 가장 적은 값이 최소 해밍 거리가 된다.

 

 

3. Parity Check

가장 간단한 오류 검출 방법은 Parity Check(패리티 검사)이다.

Parity Check는 데이터 뒤에 Parity Bit(패리티 비트)를 하나 추가하여 전체 데이터에서 1의 개수가 짝수(Even Parity)가 되도록 만든다.

예를 들어, 데이터가 1101001 라면

1의 개수가 4개이므로 짝수 패리티에서는 패리티 비트 0을 추가한다.

 

반대로 1의 개수가 홀수라면 패리티 비트 1을 추가하여 전체 1의 개수를 짝수로 맞춘다.

수신자는 같은 방식으로 다시 계산하여 패리티가 맞지 않으면 오류가 발생한 것으로 판단한다.

1. 데이터워드 a0 ~ a3에 대해 송신 측에서는 이들의 1 갯수에 따라 패리티 비트 r0을 추가해 수신 측으로
2. 수신 측에서는 전송받은 코드워드를 복호기의 검사기(Checker)에 넣어 오류를 검출
3. 이 때 검출의 결과는 신드롬(Syndrome, s0)을 통해 나타남
4. 0 → 오류x , 1→ 손상된(유효하지않은) 코드워드로, 폐기함

Parity Check는 구현이 매우 간단하다는 장점이 있지만,

1개의 비트 오류는 검출할 수 있지만 짝수 개의 비트가 동시에 손상되면 오류를 검출하지 못한다는 한계가 있다.

 

 

4. CRC (Cyclic Redundancy Check) 순환 중복 검사

CRC(Cyclic Redundancy Check)는 가장 널리 사용되는 오류 검출 기법이다.

Ethernet, USB, 저장장치 등 대부분의 통신 시스템에서 사용될 만큼 오류 검출 성능이 뛰어나다.

CRC는 Divisor라는 요소를 통해 구현된다.

• 데이터워드를 미리 정해진 Divisor로 나눈 뒤
• 나머지(Remainder)를 데이터워드에 추가해 코드워드를 생성한다.
• 수신자는 동일한 Divisor로 다시 나누어 계산한다.
• 만약 나머지가 0이면 정상적인 데이터,
• 0이 아니면 전송 중 오류가 발생한 것으로 판단한다.

아래 그림은 데이터워드 1001에 대한 코드워드를 생성하는 과정이다.

CRC는 특히 Burst Error를 매우 높은 확률로 검출할 수 있기 때문에 실제 네트워크에서 가장 많이 사용되는 오류 검출 방식이다.

 

 

5. Checksum

Checksum은 메시지 전체를 일정한 크기의 블록으로 나눈 후 모든 값을 더하여 오류를 검출하는 방식이다.

데이터링크 계층보다 네트워크 및 전송 계층에서 자주 사용된다. 

송신자는 계산한 Checksum 값을 데이터와 함께 전송하고,

수신자는 동일한 방법으로 다시 계산하여 두 값을 비교한다.

 

값이 같으면 정상적인 데이터,

다르면 오류가 발생한 것으로 판단한다.

Checksum은 계산 과정이 매우 단순하여 구현이 쉽다는 장점이 있다.

다만 CRC보다 오류 검출 성능은 다소 낮기 때문에 주로 Network Layer(IP)나 Transport Layer(TCP, UDP)에서 사용된다.

 

- 오류 검출 기법 비교

대표적인 오류 검출 기법은 다음과 같이 정리할 수 있다.

• Parity Check : 구현이 가장 간단하지만 짝수 개의 오류는 검출하지 못한다.
• CRC : Burst Error 검출 성능이 뛰어나며 실제 데이터링크 계층에서 가장 널리 사용된다.
• Checksum : 계산이 간단하여 네트워크 계층과 전송 계층에서 주로 사용된다.

각 기법은 성능과 계산량의 차이가 있지만, 모두 Redundancy를 이용하여 오류를 검출한다는 공통점을 가진다.