Chapter 6. Error Detection and Correction

Chapter 6. Error Detection and Correction

Type of Errors

Q. 오류의 종류를 설명하시오.

오류는 송신과 수신 사이에 한 비트가 변경됐을 때 일어난다. 예를 들어 1이 보내졌는데, 0을 받았다든가 반대로 0을 보냈는데, 1을 받았다든지 할 때다.

오류의 종류는 두 가지가 있다.

1. Single-bit error
2. Burst error

1. A single-bit error

단 한 비트에만 오류가 있다. 그 주변에는 영향을 끼치지 않았다.

2. A burst error of length B

2 이상의 B 길이의 인접한 비트 수 안에서 오류인 경우를 말한다. 오류의 처음과 끝을 기준으로 길이가 정해지며, 그 안에도 오류가 일어날 수 있다.

Error Detection

Q. 오류 검출은 어떤 계층에서 하는가?

데이터 링크 계층이다. 데이터 링크 계층은 네트워크 개체들 사이에 데이터를 전송하기 위해 여러 기능들을 제공한다. 또한, 물리 계층으로부터 일어날 수 있는 오류를 검출하고 수정할 수 있는 기능도 제공한다.

전송 시스템의 설계와 관련 없이, 전달된 프레임안에 하나 이상의 비트가 변경되는 오류가 발생할 것이다. 

( 프레임은 전송된 하나 이상의 연속적인 비트들이다. )

Q. 오류가 발생할 가능성을 설명하시오.

P1. 비트 오류가 발생하지 않은 경우

P2. 오류 검출 알고리즘을 거쳤지만, 하나 이상의 오류가 검출되지 않은 경우

P3. 오류 검출 알고리즘을 거쳐, 하나 이상의 오류가 모두 검출된 경우

Error Detection Process

Q. 오류 검출 과정을 설명하시오.

모든 오류 검출 기법은 다음과 같은 원칙에 기반한다.

< 송신자 >

1. 주어진 비트 프레임에, 전송자가 추가 오류 검출 코드를 덧붙인다.
2. 데이터 블록이 k 비트라면, 에러 검출 코드는 n - k 비트다.
3. 오류 검출 코드, 또는 체크 비트,를 추가해 n 비트의 데이터 블록을 만들고 전송한다

< 수신자 >

1. 수신자는 프레임을 k 비트의 데이터와 n - k 비트의 오류 검출 코드를 분리한다.
2. 수신자는 같은 오류 검출 계산 과정을 거치며, 받은 오류 검출 코드와 비교한다.
3. 만약, 다르다면 오류가 발생한 것이다.
4. 오류를 모두 검출했다면, P3 가 발생했다.
5. P2는 residual error rate 로 불리며, 오류가 검출되지 않은 경우를 말한다.

Parity Check

Q. Parity Check 을 설명하시오.

패리티 비트는 가장 간단한 오류 검출 방법이다. 데이터가 홀수 인지, 짝수 인지 확인하여 오류 검출 코드를 덧 붙인다.

수신자는 송신자가 사용했던 오류 검출 함수로, 전송된 데이터 블록으로 패리티 코드를 구한 다음에 비교한다.

그러나, 패리티 비트는 오류가 발생했는지만 알지, 오류를 고쳐주지는 못한다.

Checksum

Q. Checksum 을 설명하시오.

체크섬은 오류 검출 방법으로, 어떤 수를 계산하여 각 메시지 프레임에 같이 보낸다.

수신자는 같은 체크섬 함수를 메시지 프레임에 적용해 수를 구한다음 비교한다.

체크섬이 이루어지는 과정 예시는 다음과 같다.

1. 모든 데이터를 더한다.
2. 캐리는 무시한다.
3. 2의 보수를 취한 값이 체크섬 바이트다.
4. 검산은 모든 데이터를 더한 값과 체크섬 바이트를 더하면 캐리를 무시하고 0이 나와야 한다.

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

Q. CRC에 대해 설명하시오.

순환 중복 검사(Cyclic Redundancy Check, CRC)는 가장 흔하고 강한 오류 검출 코드다. 다음의 과정을 거친다.

• 전송자는 n 비트의 프레임을 생성한다. 그 비트는 미리 만든 수로 정확히 나눌 수 있다.
• 수신자 또한 들어온 프레임으로, 미리 만든 수로 나누어본다. 만약에 정확히 나누어 떨어지면, 오류가 없다는 뜻이다.

Forward Error Correction

Q. FEC 을 설명하시오.

Forward Error Correction (FEC) 는, 송신자가 Redundancy 데이터를 보낼 때 오류를 제어하는 방법이다.

수신자는 오류가 없는 데이터 일부를 받을 것이다.

FEC는 노이즈가 있는 통신 채널로 데이터를 전송할 때 쓰인다. 송신자는 ECC(Error-correcting code)로 메시지를 인코딩하여 보낸다. Redundancy 는 수신자가 메시지 어디에서든 오류를 검출하고 수정할 수 있게 한다.

Hamming Code

Q. Hamming Code 를 설명하시오.

해밍코드는 오류를 검출하고 수정하는데 쓰이는, 오류 검출 코드의 집합이다.

Redundant 비트는 이진 비트로서, 원본 데이터에 추가되어 전송된다.

Redundant 비트는 다음 공식을 따른다. 2^r >= m + r + 1 ( r = redundant bit, m = data bit )

만약, 데이터 비트가 7이라면, r은 4이어야 위 식을 만족한다.

해밍코드는 각각 2^n ( n <= r ) 에 위치하며, 이진 수로 n 번째 비트가 1인 위치들의 패리티 비트가 만족되도록 설정된다.

오류 검출과 수정 방법은 다음과 같다. 짝수 패리티 코드인 경우, 홀수 패리티 코드로 다시 계산해본다. 0이 아닌 수가 나온다면, 그 위치의 해밍코드가 잘못된 것이므로 그 반대로 수정한다.