4주차. 데이터 에러 검출 및 복구

데이터 에러 검출 복구(반복 코드)

1. 데이터의 중복성을 계산할 수 있다.
2. 데이터 에러 복구에 대해 설명할 수 있다.
   • 데이터 중복성을 높임으로써 잡음에 의한 에러가 생겼을 때, 에러를 복구하는 것
3. 채널 용량을 계산할 수 있다.
4. 데이터의 에러를 복구하는 반복코드 방법을 사용할 수 있다.
   • 데이터의 같은 비트를 n번 반복함 (n은 홀수)
   • n개의 비트를 읽어 과반수의 비트를 복호함(투표 방식)

Shannon-Weaver의 통신 모델

✅ 정보이론이란??

⇒ 통신 모델에 따른 통신에서 발생하는 4가지의 개념에 대한 이론

1. Entropy → 엔트로피가 높을수록 정보량이 많다
2. Redundancy → 정보의 중복성
3. Noise → 정보 노이즈
4. Channel Capacity → 전송 채널 용량

정보의 중복성

부호화된 정보가 원래 정보가 가지고 있는 고유의 Entropy 보다 몇 비트 더 많은지로 나타낼 수 있음

Redundancy(M): 부호화된 정보 크기 - 정보의 엔트로피

⇒ Cross Entropy - Entropy

Absolute Rate ⇒ R(n), n개의 심볼로 구성된 정보

✅ 데이터를 얼마나 압축했는가를 나타낼 때 기준으로 사용됨

D(n): 절대 중복성, Absolute Redundancy

상대 중복성

Repetition Coding

⇒ 원본 데이터의 심볼 당 3bit 부호화

• Redundancy가 증가했다.
• 데이터의 에러 검출 복구에 사용 가능
• 정보의 전송과정에서 Noise 발생 시 제고하고 데이터를 복원 시 사용

Redundancy

부호화된 정보의 크기 - 정보의 엔트로피

엔트로피는 정보의 고유한 확률에 의해 결정 됨

데이터 압축 vs 에러 정정

• 데이터 압축: Redundancy를 줄여서 정보를 엔트로피에 가깝게 데이터의 크기를 줄임
• 에러 정정: 데이터의 크기를 증가해서 Redundancy를 늘여서 잡음에 의한 에러가 생겼을 때 에러복구

💡 채널의 잡음 특성에 따라 Redundancy를 증가시켜 에러복구를 하도록 데이터를 증가시키는 과정

Channel Capacity

어떤 통신 채널의 데이터 속도, 1초에 몇 비트를 전송할 수 있는가를 나타냄

✅ 채널 속도 고속화

• 큰 주파수 대역폭 fbw
• 큰 신호세기 (S)
• 작은 잡음 (N)

Repetition 코드

n-Repetition Code

• 데이터의 같은 비트를 n번 반복함 (n은 홀수)
• n개의 비트를 읽어 과반수의 비트를 복호함(투표 방식)

해밍코드 이론

1. Hamming Distance(해밍 거리)를 계산할 수 있다.
   1. 두 개의 Codeword에서 같은 위치의 비트의 값이 다른 개수
2. 3-Repetition Code의 에러 검출과 복구능력에 대해 설명할 수 있다.
   1. 검출 가능
   2. 1개의 비트에러만 복구 가능
3. Minimum Hamming Distance(최소 해밍 거리)와 에러 검출과 복구에 대해 설명할 수 있다.
   1. Hamming Distance 중 가장 작은 값
4. Hamming(7,4) 코드로 부호화 할 수 있다.

Hamming Distance

n bit의 두 개의 Codeword에서 같은 위치의 비트의 값이 다른 개수

• 하나의 정보에서 다른 정보로 만들기 위해 대체 해야 할 수
• 하나의 정보에서 다른 정보로 변경되는 데 필요한 최소 에러 개수

Minimum Hamming Distance

Codeword 집합이 주어졌을 때 가능한 Hamming Distance 중 가장 작은 값

🚨 집합은 같은 값의 원소를 가질 수 없기 때문에 Minimum Hamming Distance는 0이 될 수 없음

Hamming weight

Hamming distance(codeword,zero codeword)의 1의 개수

N-Repetition Code

하나의 비트의 값을 n번 반복하는 부호화 방법

⇒ Minimum Hamming Distance 이상의 에러는 검출할 수 없음

• 심볼 - 0, Codeword - 000
• 심볼 - 1, Codeword - 111

3-Repetition Code의 복호

수신된 데이터는 Hamming Distance가 작은 Codeword로 복호(1bit 에러 복구)

🚨 에러 복구를 못 하는 경우

에러 복구를 못 하는 경우

Error Recovery

Minimum Hamming Distance는 d라고 한다

• 에러 검출: d -1개
• 에러 복구: (d/2*2) / 2개

d = 3: 에러 검출은 2개, 에러 복구는 1개

d = 5: 에러 검출은 4개, 에러 복구는 2개

Hamming Code

Hamming Code(n, k)

💡 입력된 k개의 데이터 r개의 Parity 비트를 추가해 n = k+r 비트의 Codeword로 만들어 1비트의 에러를 복구하는 부호화 방법

패러티 비트(Parity Bit)

Codeword의 1의 개수가 짝수 or 홀수가 되도록 추가하는 Bit

Minimum Hamming Distance = 2

⇒ 1bit Error 검출

Hamming Code(7,4) + (8,4)

Hamming Coding

• 패러티 비트로 Redundancy를 높여서 1비트의 에러를 복구하는 부호화 방법
• 패러티 검사를 통해 에러비트의 위치를 파악하고 그 비트를 반전시켜 에러를 복구함

Hamming Encoding & Decoding

• Hamming Encoding

• Hamming Decoding

✅ 검사 데이터 위치 변환

검사비트 C3, C2, C1의 값이 에러 비트의 위치와 일치하게 되어 에러복구를 쉽게 할 수 있다.

Hamming(8,4) Code

C4 집합을 추가해서 2비트 에러 영역 감지 가능 (해결 하지는 않음)