패러티비트(Parity bit) & 해밍코드(Hamming Code)
Parity Bit 패러티 비트
정의
패러티 비트란 정보 전달 과정에서 오류가 생겼는 지 검사하기 위해 추가하는 비트를 말한다. 전송하고자 하는 데이터의 각 문자에 1비트를 더하여 전송한다.
종류
Even Parity Bit
전체 비트에서 1의 개수가 짝수가 되도록 패러티 비트를 설정하여 더해준다. 다시 말하자면 원본 데이터 비트에서 1의 개수가 홀수라면 패러티 비트로 1을 추가하여 1을 짝수개로 만드는 것이다.
Odd Parity Bit
전체 비트에서 1의 개수가 홀수가 되도록 패러티 비트를 설정하여 더해준다. 다시 말하자면 원본 데이터 비트에서 1의 개수가 짝수라면 패러티 비트로 1을 추가하여 1을 홀수개로 만드는 것이다.
예시
짝수 패러티일 때 7 비트 데이터가 1010001 이라면 패러티 비트로 어떤 비트를 더해주어야 할까?
답 : 11010001. 원본 데이터의 1의 개수가 총 3개이므로, 1의 개수를 짝수로 맞춰주기 위해 패러티 비트로 1을 더해주어야 한다.
단점
오류의 유무를 알 수는 있지만, 수정할 수는 없다. 수정하기 위해서는 해밍 코드를 이용하면 된다.
Hamming Code 해밍코드
정의
해밍코드는 데이터 비트에 몇 개의 체크비트가 추가된 코드이다. 데이터 전송 또는 메모리 엑세스 등의 경우에, 에러비트의 위치를 알 수 있을 뿐만 아니라, 정정도 할 수 있다. 최대 2 비트의 오류 검출이 가능하며, 최대 1 비트의 오류 정정이 가능하다.
해밍코드 사용 방법
해밍코드를 사용하기 위해서는 원본 데이터 양이 커질수록 꽤 많은 양의 체크 비트가 필요하기 때문에 비효율적이라 여길 수도 있지만, 장점도 많다.
필요한 체크비트의 개수
수학적인 계산을 통해 위와 같은 공식이 유도될 수 있다!
해밍코드에는 공식을 만족하는 p개 만큼의 체크비트가 필요하다.
예를 들어 데이터 비트 d = 8비트라면, p는 최소 4비트가 되어야 한다.
체크비트의 삽입 위치
대부분의 해밍 코드를 다루는 교재에서는 위와 같은 Little Endian 포맷을 사용한다.
예를 들어 데이터 8비트, 체크비트 4비트라 하면 총 12개의 비트가 필요하다. 이때 체크비트는 2^n(n = 0, 1, 2…) 위치에 삽입왼다. 따라서 다음과 같이 체크비트가 들어갈 수 있다.
그리고 나머지 위치에 원래 데이터 비트를 넣어준다. 그러면 아래와 같이 삽입된다!
체크비트의 값은 어떻게 결정될까?
위와 같이 모든 비트의 위치가 결정될 수 있다. 그렇다면 체크비트에는 0 또는 1 비트 중 어떤 비트가 들어가는 것일까? 이때 패러티 체크 개념을 사용한다.
즉, 각 체크비트는 미리 계산된 범위만큼 패러티 체크를 수행하여 자신의 값을 결정한다! 각 체크비트마다 패러티 체크를 하는 범위는 다음과 같다.
위 범위는 특정 공식을 통해 계산되어 나온 범위이다. 대략적인 특징을 봤을 때
P1은 2^0 = 1 번째 비트로, 자신을 포함하여 한 칸 단위로 포함하고, 건너뛰는 형태이고,
P2는 2^1 = 2 번째 비트로, 자신을 포함하여 두 칸 단위로 포함하고, 건너뛰는 형태이다.
P3, P4도 비슷한 형태이다.
다시 말하자면
Pn은 2^n 번째 비트로, 자신을 포함하여 2^n칸 단위로 포함하고, 건너뛰는 형태이다.
그렇다면 패러티 체크를 어떻게 하는 걸까? 짝수 패리터 체크를 이용해보자. P2를 예로 들면, P2는 D11, D10, D7, D6, D3, D2 비트의 값을 보고, 짝수 패러티를 적용하여 자신의 값을 결정하게 된다. 예를 들어 범위 내 비트 값이 100100이라면, 이미 1이 짝수이므로 자신은 0 비트를 값으로 가진다.
체크비트를 이용해서 어떻게 오류임을 판단할까?
위와 같은 방식으로 만든 데이터로, 송신 시 체크비트 P8.P4.P2.P1, 수신 시 체크비트 P8.P4.P2.P1를 비교하여 오류임을 확인할 수 있다.
예를 들어 송신 시 체크비트가 1001이라 하고, 수신 시 체크비트가 0011이라 하면 리틀 인디언 순서에서 두 번째 비트와 네 번째 비트가 다르다. 고로 에러코드는 1010이 된다. 이를 십진수로 바꾸면 10이므로 10 번째 비트에서 오류가 생긴 것이다! 고로 수신된 비트열에서 D10을 반전시키면 오류가 정정된다!
예제를 간단하게 살펴보자
Data bit = 01010101 = 8bit
check bit = 4bit
- 데이터 비트 채우기
- 각 범위만큼 패러티 체크를 수행하여 체크비트 채우기 ⇒ 송신 비트열 완성 : 체크비트 0111
- D9에서 에러 발생 가정
- 수신 비트열에서 패러티 체크를 수행하여 체크비트 다시 계산 ⇒ 수신 비트열 완성 : 체크비트 1110
- 송신 비트열에서의 체크비트와 수신 비트열에서의 체크비트 비교
- 완전히 똑같다면 에러 없음!
- 다른 부분이 있다면, 다른 비트 위치를 1로 설정하여 에러코드 생성. 해당 에러코드를 십진수 d로 바꾸면 d번째 비트가 에러!
##현재 작성한 설명은 쉬운 이해를 위해 작성된 것이다. 왜 이러한 방식으로 오류 정정이 가능한 것인지는 아직 확실하게 살펴보지 못했다. 다음 포스트를 통해 수학적 공식을 좀 더 깊이 살펴봐야겠다!
출처
https://m.blog.naver.com/ggggamang/221113176831
#22 Hamming Code(해밍코드)
데이터커뮤니케이션 중간고사를 공부하던 중 해밍코드를 만났다. 사실 그와 나는 구면인데, 1년 전 [디지털...
blog.naver.com