Hamming 코드
데이터 전송 도중 발생한 에러를 검출할 때, 이 때 Hamming 코드가 사용된다.
Hamming 코드는 비트 오류를 검출하고 정정할 수 있는 코드이다. 오류가 발생한 위치를 식별하고 수정할 수 있는 기능이 있다.
일반적인 Hamming 코드는 4비트의 데이터 비트와 3비트의 패리티 비트를 포함하여 7비트의 코드워드를 형성한다.
4비트 데이터 비트: 실제 전송되는 데이터.
3비트 패리티 비트: 오류 검출 및 정정에 사용되는 추가 비트.
- 비트 1: 패리티 비트 (P1)
- 비트 2: 패리티 비트 (P2)
- 비트 3: 데이터 비트 (D1)
- 비트 4: 패리티 비트 (P3)
- 비트 5: 데이터 비트 (D2)
- 비트 6: 데이터 비트 (D3)
- 비트 7: 데이터 비트 (D4)
각 패리티 비트는 지정된 데이터 비트 집합의 XOR 연산 결과로 설정된다.
- P1: 비트 1, 3, 5, 7의 XOR
- P2: 비트 2, 3, 6, 7의 XOR
- P3: 비트 4, 5, 6, 7의 XOR
예를 들어 데이터 비트가 1011일 때 패리티 비트를 계산하면
이 상태에서
| P1 | P2 | D1 | P3 | D2 | D3 | P4 |
| 1 | 0 | 1 | 1 |
- P1 = D1 ⊕ D2 ⊕ D4 = 1 ⊕ 0 ⊕ 1 = 0
- P2 = D1 ⊕ D3 ⊕ D4 = 1 ⊕ 1 ⊕ 1 = 1
- P3 = D2 ⊕ D3 ⊕ D4 = 0 ⊕ 1 ⊕ 1 = 0
이를 대입하면 코드워드는 0110111이 된다.
전송된 코드워드가 수신된 후, 패리티 비트를 다시 계산하면 오류가 발생한 비트의 위치를 결정할 수 있다.
오류가 발생한 비트는 패리티 비트 검사를 통해 식별되며, 그 비트를 반전시켜 오류를 수정한다.
예를들어, 수신된 코드워드가 0111110 이라면
- 패리티 비트를 계산하여 오류 위치를 식별
- 오류가 비트 4에서 발생한 것으로 식별되면, 비트 4를 반전시켜 오류를 수정
- 수정된 코드워드는 0110111로 원래의 데이터 1011을 복원할 수 있다.
이 코드를 사용하는 여러가지 오류 검사 기법들이 있다.
패리티 검사 (parity check)
패리티 비트는 데이터 비트에 추가되는 1비트로, 데이터 비트들의 총합이 짝수(또는 홀수)가 되도록 설정한다.
이 비트는 오류 발생을 감지하기 위해 사용된다.
패리티 비트 설정 방법
- 짝수 패리티 (Even Parity):
- 패리티 비트를 설정하여 전체 비트(데이터 비트 + 패리티 비트)의 1의 개수가 짝수로 되도록 한다.
- 예: 데이터가 1011이면 1의 개수가 3개로 홀수이므로 패리티 비트를 1로 설정하여 10111로 전송한다.
- 홀수 패리티 (Odd Parity):
- 패리티 비트를 설정하여 전체 비트의 1의 개수가 홀수로 되도록 한다.
- 예: 데이터가 1011이면 1의 개수가 3개로 이미 홀수이므로 패리티 비트를 0으로 설정하여 10110으로 전송한다.
1. 단일 비트 에러 검출:
한 개의 비트가 잘못 전송된 경우는 이를 감지할 수 있다.
예를 들어, 짝수 패리티를 사용하는 경우를 생각해보자.
- 원래 전송된 데이터: 10111 (여기서는 짝수 패리티를 사용하여 1의 개수가 짝수임을 보장)
- 만약 이 데이터의 한 개의 비트가 잘못 바뀌어 10101이 되었다면, 1의 개수가 홀수가 되어 패리티 검사를 통해 오류를 감지할 수 있다.
2. 홀수 개의 비트 에러 검출:
홀수 개의 비트가 변경되었을 때도 오류를 감지할 수 있다.
예를 들어, 3개의 비트가 잘못 전송된 경우
- 원래 데이터: 10111
- 세 개의 비트가 잘못 바뀌어 10000이 되면, 1의 개수가 바뀌기 때문에 패리티 검사가 오류를 감지할 수 있다.
3. 짝수 개의 비트 에러
그런데 패리티 검사는 짝수 개의 비트가 잘못 전송된 경우 오류를 감지하지 못할 수 있다.
- 원래 데이터: 10111
- 두 개의 비트가 잘못 바뀌어 10001이 된 경우, 1의 개수는 원래와 동일한 짝수로 남게 된다. 이 경우 패리티 검사는 오류를 감지하지 못한다.
블록합 검사 (Block Sum Check)
데이터 블록의 무결성을 검증하기 위한 에러 검출 기법으로, 수평 및 수직 패리티 검사를 통해 오류를 검출한다.
- 수평 패리티 (Horizontal Parity):
- 각 데이터 블록의 각 행에 대해 패리티를 계산한다.
- 각 행의 비트 합이 짝수 또는 홀수가 되도록 패리티 비트를 설정한다.
일반적으로 홀수 패리티 (Odd Parity) 방식이 사용된다.
- 수직 패리티 (Vertical Parity):
- 각 열에 대해 패리티를 계산하여 블록의 무결성을 검증한다.
- 수직 패리티는 짝수 패리티 (Even Parity) 방식이 사용된다.
블록 합 검사 과정:
- 데이터 블록 준비:
- 전송할 데이터를 여러 블록으로 나누며, 각 블록의 크기는 일정하게 설정한다.
- 수평 패리티 계산:
- 각 블록의 행에 대해 패리티를 계산하고, 각 행의 비트 합이 짝수 또는 홀수인지에 따라 패리티 비트를 설정한다.
- 수직 패리티 계산:
- 각 블록의 열에 대해 패리티를 계산하고, 각 열의 비트 합이 짝수 또는 홀수인지에 따라 패리티 비트를 설정한다.
- 검사 데이터 추가:
- 수평 패리티와 수직 패리티를 모두 포함한 블록 합 검사를 통해 무결성을 확인하고, 데이터 전송 중 발생한 오류를 검출한다.
수평, 수직 패리티를 사용하면 데이터 블록 전체의 무결성을 빠르게 검증할 수 있지만, 짝수 개의 비트 또는 복잡한 다중 비트 오류가 동시에 발생하면 오류를 감지하지 못할 수 있다.
순환중복 검사 (Cyclic Redundancy Check, CRC)
CRC는 모듈로 2 산술(Modulo-2 arithmetic)을 사용하여 데이터의 오류를 검출한다.
이 방식은 배타적 논리합 (XOR) 연산을 사용하여 계산된다.
CRC 계산 과정
- 데이터 준비
- 데이터 비트를 다항식으로 변환한다. 데이터가 11001001이라면, 이를 다항식 x7+x6+x3+x0 형식으로 표현 후, 뒤에 특정 비트 수(예: CRC-16의 경우 16비트)를 추가하여 오류 검출을 위한 준비를 한다.
- 연산 과정
- 데이터 비트와 생성 다항식 사이의 XOR 연산을 통해 나머지를 계산한다. 이 과정에서 데이터를 왼쪽으로 시프트하여 연산을 이어간다.
- CRC 값 계산
- 계산된 나머지가 CRC 값이 되며, 이 값은 데이터 블록의 끝에 추가되어 전송된다.
수신 측에서는 이 CRC 값을 사용하여 오류가 발생했는지 검출한다.
- 계산된 나머지가 CRC 값이 되며, 이 값은 데이터 블록의 끝에 추가되어 전송된다.
예시
- 데이터 비트: M = 11001001
- 생성 다항식: x^4 + x^3 + 1
- 데이터 비트를 생성 다항식으로 나눈 후, 나머지를 구하여 CRC 값으로 사용한다.
데이터 비트 M을 다항식 x7+x6+x3+x0 로 변환하고, 데이터 비트 뒤에 생성 다항식의 길이(5비트)에 맞추어 0을 추가한다.
1100100100000 (총 13비트)
첫 번째 XOR 연산:
- 데이터: 1100100100000
- 생성 다항식: 11001
- 처음 5비트를 XOR 연산
11001 (생성 다항식 G)
11001 (데이터 비트의 처음 5비트)
------
00000 (XOR 결과)
다음 5비트 XOR 연산:
- XOR한 나머지 00000 뒤에 남은 데이터에서 새로운 비트를 붙여 다음 5비트를 다시 만든다.
즉, 00100 - 이 새로운 5비트 00100을 다시 생성 다항식 11001과 XOR 연산
11001 (생성 다항식 G)
00100 (데이터 비트에서 추출된 다음 5비트)
------
11101 (XOR 결과)
세 번째 XOR 연산:
- 다음으로 11101에 남은 비트를 붙여 5비트를 만들고 다시 XOR 연산
- 11101에 데이터의 남은 비트를 사용해 다음 XOR 연산
11001 (생성 다항식 G)
11101
------
00100 (XOR 결과)- 마지막으로 남은 비트를 XOR한다. 이 과정에서 남은 데이터 비트를 붙인다.
11001 (생성 다항식 G)
10000 ( XOR 대상)
------
01001
위의 XOR 연산이 완료되면, 나머지 값이 01001으로 계산된다.
데이터를 다항식으로 변환하여 생성 다항식과 나눈다는 면에서, 데이터 블록을 나눠서 체크하는 LRC와 비슷한 오류 검출 방법이다.
CRC는 특히 다중 비트 오류를 효과적으로 검출할 수 있다.
CRC생성 예시
M을 2⁵으로 시프트하여 G와 나눔으로써 CRC를 생성하고, 이 과정에서 나머지 R을 구하여 전송 데이터에 추가한다.
1. 초기 설정
- 데이터 비트 (M): 1010001101 (10비트)
- 생성 다항식 (G): 110101 (6비트)
이 경우, M은 우리가 전송할 데이터이고, G는 이 데이터를 나누기 위해 사용되는 생성 다항식이다.
G는 나눗셈을 수행할 때 사용되며, 이 과정에서 나머지 값을 CRC 값으로 사용하게 된다.
2. 데이터 비트 뒤에 0 추가
데이터 비트 M의 뒤에 생성 다항식의 비트 수(6비트)만큼 0을 추가한다. 이 과정은 데이터의 크기를 늘려 나눗셈을 수행하기 위한 준비이다.
- 데이터 비트(M) + 6비트 0을 추가한 값: 1010001101000000 (16비트)
3. 나눗셈 과정
나눗셈은 XOR 연산을 통해 이루어진다. XOR 연산이란 두 비트가 같으면 0, 다르면 1이 나오는 연산이다.
첫 번째 XOR 연산
- 첫 6비트를 생성 다항식 G와 맞춰 XOR 연산을 수행
- 101000 (M)
- 110101 (G)
- 결과: 011101
두 번째 XOR 연산
- 결과값에서 새로 남은 부분(앞의 0이 있는 자리)과 다음 비트를 이어 붙여 다시 XOR 연산을 수행
- 111011
- 110101
- 결과: 001110
세 번째 XOR 연산
- 마찬가지로 남은 부분과 다음 비트를 이어 붙여 XOR 연산을 계속 수행
- 111010와 110101
- 결과: 001111
이 과정을 반복하면서 데이터 비트를 순차적으로 처리한다. 나머지가 6비트가 나올 때까지 연산을 계속한다.
4. 나머지 R 계산
결과적으로 마지막에 남는 6비트가 CRC 값이 된다. 이 예시에서는 CRC 값(R) 011110
5. CRC 값을 데이터에 추가
이제 계산된 CRC 값(R)을 원래 데이터 비트(M)에 추가한다. 최종 데이터는 다음과 같다
- 전송할 데이터: 1010001101 + 011110 = 1010001101011110
수신 측에서는 동일한 생성 다항식을 사용하여 수신된 데이터를 나누어 나머지를 확인한다.
나머지가 0이면 오류 없이 전송된 것이고, 나머지가 0이 아니면 데이터 전송 중 오류가 발생했음을 알 수 있다.
CRC 생성 및 검출 과정
- 기본 정의:
- M: k 비트의 전송 메시지
- R: n 비트의 frame check sequence (FCS)
- T: M · 2ⁿ ⊕ R (전송 메시지에 R을 더한 값)
- G: FCS를 생성하기 위한 생성 다항식 (n+1 비트)
- 송신단에서의 CRC 계산 방식:
- CRC를 생성하기 위해 M을 2ⁿ으로 시프트한 후, 생성 다항식 G로 나누어 나머지 R을 구한다.
- T = M · 2ⁿ ⊕ R을 구하여 전송한다.
- 수신단에서의 오류 검출 방식:
- 수신단은 수신된 데이터 T를 생성 다항식 G로 나누고, 나머지가 0이 되면 오류가 없음을 확인할 수 있다.
CRC 생성 하드웨어의 구성 요소
- 레지스터:
- CRC FCS(Frame Check Sequence)의 길이와 같은 비트를 포함한다.
레지스터는 데이터 입력을 수신하고, CRC 계산 중 나머지를 저장한다.
- CRC FCS(Frame Check Sequence)의 길이와 같은 비트를 포함한다.
- 배타적 논리합 (XOR) 게이트:
- 최대 7개의 XOR 게이트가 사용되며, 생성 다항식의 각 항을 나타낸다.
각 항의 존재 여부에 따라 XOR 연산이 수행된다.
- 최대 7개의 XOR 게이트가 사용되며, 생성 다항식의 각 항을 나타낸다.
- 하드웨어 구성 요소:
- 시프트 레지스터(Shift Register): 데이터를 시프트하면서 CRC 연산을 수행한다.
- XOR 게이트 네트워크를 통해 각 항의 값과 연산하여 CRC를 생성한다.
위 구성 요소들을 바탕으로 한 CRC 생성 과정
- 초기화: 레지스터를 초기화하고 데이터를 입력
- XOR 연산: 시프트된 비트와 레지스터의 값을 XOR 연산
- 생성 다항식 사용: 생성 다항식의 각 항에 따라 계속 XOR 수행
- 결과 출력: 남은 비트 전송을 통해 CRC 코드를 출력