통신 오류 검출
- 수신 측으로 전송한 데이터는 송신 측의 데이터와 동일해야 하지만, 다양한 원인 때문에 데이터 오류가 발생할 수 있음
- 따라서 신뢰할 수 있는 네트워크 통신을 하려면 오류를 검출·수정해야 함
- 오류의 종류에는 단일 비트 오류, 다중 비트 오류, 집단 오류가 있음
단일-비트 오류 (Single-bit Error)
다중-비트 오류 (Multiple-bit Error)
- 데이터 단위 중 두 개 이상의 비연속적인 비트를 변경하는 오류
집단 오류 (Burst Error)
- 데이터 단위 중 두 개 또는 그 이상의 연속적인 비트를 변경하는 오류
- 송신 측이 보내려는 데이터 외에 별도로 잉여(중복)분의 데이터를 추가해서 전송하면 수신 측은 이 잉여 데이터를 검사하여 오류를 검출할 수 있음
- 오류를 검출하는 방식에는 패리티 비트 검사(parity bit check), 블록 합 검사(block sum check), 순환 중복 검사(Cyclic Redundancy Check) 등이 있음
패리티 비트 검사
- Parity Bit Check
- 전송하는 데이터마다 패리티 비트를 하나씩 추가하여 홀수 또는 짝수 검사 방법으로 오류를 검출
- e.g. 7 bit 데이터를 전송할 때 1 bit 검사 비트를 추가로 전송하여 수신 측에서 데이터 전송 중 발생한 오류를 검출
- 추가로 전송되는 1비트를 ‘패리티 비트’라고 함
- 패리티 비트의 값은 데이터 코드 내에 있는 1의 수를 계산함으로써 결정
홀수 패리티 방식 (Odd Parity)
- 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트를 정하는 것
- 데이터 비트에서 1의 개수가 짝수면 패리티 비트를 1로 정하여 전송되는 전체 데이터에 있는 1의 개수는 홀수가 됨
짝수 패리티 방식 (Even Parity)
- 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트를 정하는 것
- 데이터 비트에서 1의 개수가 홀수면 패리티 비트를 1로 정하여 전송되는 전체 데이터에 있는 1의 개수는 짝수가 됨
- 인코딩(Encoding) 예제: 7비트 데이터가 0100111인 경우
- 짝수 패리티 방식을 사용하면 0100111에서 1이 4개이므로 짝수
- 여기에 패리티 비트 0을 추가해도 전송되는 전체 데이터에 있는 1의 개수는 짝수(00100111)
- 디코딩(Decoding) 예제
- 짝수 패리티 검사 원리
- 00100111에서 패리티 비트는 0이므로 1의 개수가 짝수인지 확인
- 짝수 패리티 방식은 패리티 비트를 포함해서 각각 XOR 연산
- 결과가 0(1의 개수가 짝수)이면 오류가 없는 것이고, 1(1의 개수가 홀수)이면 오류가 검출된 것
- 0 XOR 0 XOR 1 XOR 0 XOR 0 XOR 1 XOR 1 XOR 1 = 0
- 홀수 패리티 검사 오류 검출 예
블록 합 검사
- Block Sum Check
- 문자를 블록으로 전송하면 오류 확률이 높아지는데, 오류 검출 능력을 향상시키려고 문자 블록에 수평 패리티와 수직 패리티를 2차원적으로 검사하는 방법
- 행 단위 패리티에 열 단위의 오류 검사를 수행할 수 있는 열 패리티 문자를 추가하여 이중으로 오류 검출 작업을 수행
- 추가된 열 패리티 문자를 ‘블록 검사 문자(BCC, Block Check Character)’라고 함
- 블록 합 검사를 사용하면 한 데이터에서 짝수 개의 오류가 발생하더라도 오류를 검출할 수 있음
예제
- ‘HyeJin’이라는 단어를 전송하는 데 블록 합 검사를 적용한 경우
- 송신 측: 수평 패리티 검사는 홀수 패리티를 적용하고, 수직 패리티 검사는 짝수 패리티를 적용하여 프레임(단어) 끝에 1 0 0 1 1 0 0 1 BCC를 추가해서 전송
- 수신 측: 수신된 프레임의 문자에 대해 BCC를 계산( 1 0 0 1 0 1 1 1 계산된 결과 )하고 송신 측이 전송한 BCC와 비교하여 오류를 검출
- 이때 두 값이 같으면 오류가 없는 것
- 만약 두 값이 다르면 1비트 오류는 위치까지 알 수 있고, 2비트 오류의 경우 위치는 알 수 없으나 오류 여부는 판단이 가능
- 블록 합 검사라도 연속된 2개의 문자에서 같은 위치의 2비트가 오류일 때는 오류를 검출할 수 없음
- J(11) 문자와 i(01) 문자를 전송하다가 각 문자당 2비트에 오류가 발생했는데도 불구하고 수직 패리티 검사를 해보면 송신 측의 BCC(01)와 일치하기 때문에 오류 검출이 불가능
순환 중복 검사
- CRC, Cyclic Redundancy Check
- 정확하게 오류를 검출하려고 다항식 코드를 사용하는 방법
오류가 없을 때는 계속 발생하지 않다가 오류가 발생하면 그 주위에 집중적으로 오류를 발생시키는 집단 오류를 검출하는 능력이 탁월하고, 구현이 단순
- 다항식 (Polynomial): CRC 발생기는 0과 1의 스트링 보다는 대수 다항식으로 표현하며, 하나의 다항식은 하나의 제수(Divisor)를 표현
- 다항식을 이용한 순환 중복 검사의 오류 검출 과정
- 송신 측이 데이터를 전송하기 전에 송수신 측은 동일한 생성 다항식을 결정
- 송신 측에서는 K비트의 전송 데이터를 생성 다항식으로 나눈 n비트의 나머지 값을 구하고 K비트의 전송 데이터에 n비트의 나머지 값을 추가하여 K+n비트의 데이터를 수신 측으로 전송
- 수신 측에서는 수신된 K+n비트의 데이터를 생성 다항식으로 나누고 나눈 나머지가 0이면 오류가 없는 것이고, 0이 아니면 오류가 발생한 것임
CRC 검사 과정
① 송신 측
- 데이터 전송
- 오류 검출코드 계산
- CRC 추가
② 수신 측
- 데이터 수신
- 오류 검출코드 계산
- 수신된 CRC와 계산된 CRC 비교 검사
- 동일하지 않으면 오류 검출 신호 발생
예제
- 전송 데이터 다항식: P(x) = 10101101(x7+x5+x3+x2+1)
- 생성 다항식: G(x) = 11101(x4+x3+x2+1)
- FCS 비트 수는 생성 다항식(제수)보다 1비트 작은 4비트
1단계
- P′(x): 전송 데이터 다항식 P(x)를 FCS의 비트 수만큼 왼쪽 시프트 shift
- P(x) = 10101101을 FCS 비트 수만큼 왼쪽 시프트
- P′(x) = 101011010000
2단계
- P′(x)를 G(x)로 나누어 나머지 계산
- 나눗셈 연산은 캐리(overflow, borrow)를 무시하고 XOR(mod-2)을 수행
- XOR 연산: 서로 다른 값일 때는 1, 같은 값일 때는 0을 반환
3단계
4단계
5단계
- 수신 측에서는 전송받은 P″(x)를 생성 다항식으로 나눔
- 나머지가 0이면 오류가 없는 것이고, 0이 아니면 오류가 발생한 것임
