#11. 디데통(3) / CRC + 오류 수정 프로세스 + 해밍코드

[ 디지털 데이터 통신(3) - CRC + 오류 수정 프로세스 ]

 

 

 

 

 

 

# 순환 중복 검사(CRC)

• 가장 보편적이고 강력한 검사 중 하나

• k-bit 블록의 경우 송신기가 비트 시퀀스(n-k ) FCS(Frame Check Sequence)를 생성한다.

• 미리 결정된 숫자로 정확히 구분되는 n비트 프레임 전송

• 수신기가 프레임을 해당 숫자로 나눈다

∘남은 것이 없는 경우 오류 없다고 가정

• 구현 방법:

∘modulo 2 산술

∘polynomials (다항식)

∘digital logic (디지털 논리학)

 

# CRC - 구현

• Modulo 2 

 

- 운반이 없는 바이너리 추가(XOR)

- 데이터 끝에 (n-k ) 0의 추가

- 결과를 P로 나누고 나머지는 FCS로 나누기

 

# CRC - 구현

• Polynomials

 

- 모든 값을 이항 계수로 더미 변수 X에서 다항식으로 표현

- CRC-12 : 6비트 문자의 스트림 전송

- CRC-16(CRC-ANSI): 미국의 8비트 문자용

- CRC-CCITT: 유럽의 8비트 문자용

- CRC-32(IEEE-802): 포인트 투 포인트 동기식 전송,

IEEE 802 LAN

 

 

 

 

 

CRC - 구현

• Digital Logic

 

- 교대 레지스터 수 : FCS 길이

- XOR 관문 수 : (P의 1의 수 ) – 1

- i가 비트 위치인 i가 1인 i번째 레지스터 앞에 XOR 게이트 삽입

- 수신기에서는 같은 논리를 사용한다.

 

XOR을 삽입하는 위치 P에서 작은 번호의 레지스터부터

1을 가진 레지스터의 '앞'에 XOR을 삽입하고 만일 1을 가졌지만 대응되는 레지스터가 없다면 무시

 

 

# 오류 수정 //오류를 탐지할 뿐만 아니라 수정도 해야 함 따라서 오류의 위치를 알아야함

 

• 검출된 오류를 수정하려면 일반적으로 데이터 블록을 재전송해야 함

- 일단 오류를 감지하면 sender에게 알려서 다시 보내도록 해야함

근데 재전송이 가능하지 않을 수도 있음 다음과 같은 경우

• 무선 애플리케이션에 적합하지 않음

∘비트 오류율이 높음

- 재전송 횟수 증가

∘전파 지연이 프레임 전송시간보다 훨씬 긴 경우가 있다. (위성)

- 오류 프레임의 재전송 및 많은 후속 프레임의 재전송 가능

• 수신된 비트(이미 받은 내용)를 기반으로 오류를 수정해야 함

 

 

# 오류 수정 프로세스 다이어그램

 

 

 

 

 

# 오류 수정 프로세스

 

• 각 k-비트 블록은 FEC(Forward Error Correction) 인코더를 사용하여 코드 워드라고 불리는 n-비트 블록(n >k)에 매핑된다.

• 코드 워드가 전송됨(장애에 따라 다름)

• 수신된 비트 문자열은 전송된 비트 문자열과 유사하지만 오류를 포함할 수 있음

• 수신된 코드 워드가 FEC 디코더에 전달됨

∘오류 없는 경우, 원본 데이터 블록 출력

∘일부 오류패턴을 검출하여 수정할 수 있음

∘일부 오류패턴을 검출할 수 있으나 수정할 수 없음

∘일부 (경계) 에러패턴이 검출되지 않음

- FEC 디코더에서 잘못된 데이터 출력 발생

 

 

오류 수정 작업

• 전송된 메시지에 중복성 추가

• 특정 수준의 오류 발생률에도 불구하고 원본 메시지를 추론할 수 있음

• 예: 블록 오류 수정 코드

 일반적으로 블록 끝에 (n – k )- 비트를 추가한다.

∘n - 비트 블록 부여(코드워드)

∘원래 k-비트는 모두 코드 워드에 포함

 일부 FEC map k-bit 입력을 n-bit codeword에 입력하여 원본 k-비트가 나타나지 않도록 함

(해밍코드 아래의 사진이 그 예)

 

 

25-26

25: k가 2bit일 때 codeword를 5bit로 만들어야 함

data block 과 codeword 비교해보기

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

원래 데이터가 남아있는 경우, 믹스되는 경우, 없어지는 경우 모두 존재 CRC가 더 중요한 듯