패리티 비트와 해밍 코드 (Parity Bit · Hamming Code)

데이터를 보내거나 저장하는 중에 0이 1로, 1이 0으로 뒤집히는 오류가 생길 수 있습니다. 패리티 비트는 이런 오류가 생겼는지 검사하려고 덧붙이는 비트이고, 해밍 코드는 한 걸음 더 나아가 어느 비트가 틀렸는지 찾아서 고칠 수 있게 만든 코드입니다.

한눈에 보기

• 비유: 택배 상자에 "물건 개수는 짝수입니다"라는 쪽지를 넣어 보내는 것과 같습니다.
  • 받은 쪽에서 세어 봤는데 홀수면 "중간에 뭔가 잘못됐다"는 것은 알 수 있습니다. 이것이 패리티 비트입니다.
  • 하지만 어떤 물건이 잘못됐는지는 모릅니다.
• 해밍 코드는 물건을 여러 묶음으로 겹치게 나눠서 묶음마다 쪽지를 넣는 방식입니다. 어느 묶음들의 쪽지가 틀렸는지 조합해 보면, 잘못된 물건 하나를 정확히 짚어낼 수 있습니다.

패리티 비트 (Parity Bit)

정보를 전달하는 과정에서 오류가 생겼는지 검사하기 위해 추가하는 비트

전송하려는 데이터의 각 문자(비트 묶음)에 1비트를 더해서 전송합니다.

종류: 짝수 패리티와 홀수 패리티

전체 비트에서 1의 개수가 짝수 또는 홀수가 되도록 패리티 비트를 정합니다.

종류	규칙
짝수 패리티 (Even Parity)	패리티 비트를 포함한 전체의 1의 개수가 짝수가 되도록 맞춤
홀수 패리티 (Odd Parity)	패리티 비트를 포함한 전체의 1의 개수가 홀수가 되도록 맞춤

예제: 짝수 패리티일 때 7비트 데이터가 1010001이라면?

1. 1010001에서 1은 총 3개(홀수)입니다.
2. 짝수로 맞추려면 1을 하나 더해야 하므로 패리티 비트는 1입니다.
3. 패리티 비트를 맨 앞에 붙이면 답은 11010001 입니다.

def even_parity_bit(bits):
    # 1의 개수가 홀수면 1을 붙여 전체를 짝수로 맞춘다
    return '1' if bits.count('1') % 2 == 1 else '0'

data = '1010001'
p = even_parity_bit(data)
print(p + data)                       # 맨 앞에 패리티 비트를 붙인 결과

received = '11000001'                 # 전송 중 1비트가 뒤집힌 경우
print(received.count('1') % 2 == 0)   # 짝수면 정상, False면 오류 발견

11010001
False

패리티 비트의 한계

• 오류가 있다는 것만 알 수 있고, 몇 번째 비트가 틀렸는지는 모릅니다. 그래서 고칠 수 없고, 다시 보내 달라고 요청해야 합니다.
• 비트가 두 개 동시에 뒤집히면 1의 개수가 다시 짝수가 되어 오류를 발견하지 못합니다. 홀수 개의 비트가 틀렸을 때만 잡아냅니다.

해밍 코드 (Hamming Code)

데이터 전송 시 1비트 오류를 스스로 고칠 수 있는 자기 오류 정정 코드

패리티 비트는 오류를 검출만 할 뿐 고치지는 못하기 때문에 해밍 코드를 활용합니다. 패리티 비트 여러 개를 보고, 1비트 오류가 난 위치를 찾아 수정할 수 있습니다.

방법

1. 왼쪽부터 1번, 2번, 3번... 순서로 자리 번호를 붙입니다.
2. 2의 거듭제곱 번째 자리, 즉 1, 2, 4번째 자리가 패리티 비트입니다. 나머지 3, 5, 6, 7번째 자리에 데이터 4비트가 들어갑니다. (7비트 해밍 코드 기준)
3. 각 패리티 비트는 자기 번호에서 시작하는 겹치는 묶음을 담당하고, 묶음 안의 1의 개수가 짝수(또는 홀수)인지를 기준으로 판별합니다.

자리 번호	1	2	3	4	5	6	7
역할	P1	P2	데이터	P4	데이터	데이터	데이터
P1 묶음 (1, 3, 5, 7번)	O		O		O		O
P2 묶음 (2, 3, 6, 7번)		O	O			O	O
P4 묶음 (4, 5, 6, 7번)				O	O	O	O

묶음을 정하는 규칙은 자리 번호를 2진수로 썼을 때 보입니다. 1번 묶음은 2진수 맨 끝자리가 1인 번호(1, 3, 5, 7), 2번 묶음은 끝에서 둘째 자리가 1인 번호(2, 3, 6, 7), 4번 묶음은 끝에서 셋째 자리가 1인 번호(4, 5, 6, 7)입니다. 그래서 1~7번 자리마다 속한 묶음의 조합이 모두 다르고, 틀린 묶음들의 조합만 보면 몇 번 자리가 틀렸는지 알 수 있습니다.

이 관계는 원 세 개가 겹친 그림으로 보면 한눈에 들어옵니다. 원 하나가 패리티 비트 하나의 묶음이고, 데이터 비트 d1~d4는 각자 다른 조합의 원이 겹치는 자리에 들어 있습니다. 그림의 p1, p2, p3은 위 표의 P1, P2, P4이고, d1, d2, d3, d4는 3, 5, 6, 7번 자리입니다. 예를 들어 세 원이 모두 겹치는 d4(7번)가 틀리면 세 묶음이 모두 틀리고, p1에만 속한 자리가 틀리면 p1 묶음만 틀립니다.

그림 출처: Wikimedia Commons (CC BY-SA 3.0)

예제: 짝수 패리티의 해밍 코드가 0011011일 때, 오류를 수정한 코드는?

자리 번호   1  2  3  4  5  6  7
받은 값     0  0  1  1  0  1  1

1. 1, 3, 5, 7번째 비트 확인: 0 1 0 1, 1이 2개로 짝수이므로 0 (이상 없음)
2. 2, 3, 6, 7번째 비트 확인: 0 1 1 1, 1이 3개로 홀수이므로 1 (이상 있음)
3. 4, 5, 6, 7번째 비트 확인: 1 0 1 1, 1이 3개로 홀수이므로 1 (이상 있음)

세 결과를 역순(4번 묶음, 2번 묶음, 1번 묶음 순)으로 읽으면 110입니다. 2진수 110을 10진수로 바꾸면 6이므로, 6번째 비트가 틀린 것입니다.

6번째 비트 1을 0으로 바꾸면 정답은 0011001 입니다.

검사 결과가 000이면 오류가 없다는 뜻입니다.

코드로 확인하기

def hamming_encode(d):
    # d: 데이터 4비트 문자열 (3, 5, 6, 7번째 자리에 들어감)
    b = [0] * 8                        # 1번부터 쓰려고 0번은 비워 둠
    b[3], b[5], b[6], b[7] = (int(c) for c in d)
    b[1] = (b[3] + b[5] + b[7]) % 2   # 1, 3, 5, 7번 묶음을 짝수로
    b[2] = (b[3] + b[6] + b[7]) % 2   # 2, 3, 6, 7번 묶음을 짝수로
    b[4] = (b[5] + b[6] + b[7]) % 2   # 4, 5, 6, 7번 묶음을 짝수로
    return ''.join(map(str, b[1:]))

def hamming_check(code):
    b = [0] + [int(c) for c in code]
    c1 = (b[1] + b[3] + b[5] + b[7]) % 2
    c2 = (b[2] + b[3] + b[6] + b[7]) % 2
    c4 = (b[4] + b[5] + b[6] + b[7]) % 2
    pos = c4 * 4 + c2 * 2 + c1        # 거꾸로 읽은 2진수 = 틀린 자리
    if pos:
        b[pos] ^= 1                    # 그 자리 비트를 뒤집어 고친다
    return f'{c4}{c2}{c1}', pos, ''.join(map(str, b[1:]))

print(hamming_check('0011011'))
print(hamming_encode('1001'))
print(hamming_check('0011001'))

('110', 6, '0011001')
0011001
('000', 0, '0011001')

• 첫 줄: 예제의 0011011을 검사하면 110, 즉 6번 자리 오류이고, 고친 결과는 0011001입니다.
• 둘째 줄: 데이터 1001을 해밍 코드로 만들면 정확히 0011001이 나옵니다. 예제의 원래 데이터가 1001이었다는 뜻입니다.
• 셋째 줄: 고친 코드를 다시 검사하면 000, 오류가 없습니다.

해밍 코드의 한계와 실제 쓰임

• 7비트 해밍 코드는 1비트 오류만 고칠 수 있습니다. 2비트가 동시에 틀리면 엉뚱한 자리를 고쳐 버릴 수 있습니다.
• 그래서 실제로는 전체 패리티 비트를 하나 더 붙여 1비트 오류는 고치고, 2비트 오류는 발견만 하는 방식(SECDED)을 많이 씁니다.
• 서버용 ECC 메모리가 이런 원리로 RAM에서 생기는 비트 오류를 자동으로 고칩니다. 메모리 자체에 대해서는 컴퓨터의 구성과 메모리 관리를 참고하세요.

정리

개념	비전공자 버전 요약
패리티 비트	1의 개수를 짝수(또는 홀수)로 맞추려고 붙이는 확인용 비트 하나
짝수 / 홀수 패리티	전체 1의 개수를 짝수로 맞추느냐, 홀수로 맞추느냐
패리티의 한계	틀렸다는 것만 알고 위치는 모름. 2비트가 틀리면 못 잡음
해밍 코드	겹치는 묶음마다 패리티를 둬서 틀린 1비트의 위치를 찾아 고침
패리티 자리	1, 2, 4, 8번처럼 2의 거듭제곱 번째 자리
오류 위치 찾기	묶음별 검사 결과를 거꾸로 읽은 2진수가 틀린 자리 번호
ECC 메모리	해밍 코드 원리로 RAM의 비트 오류를 자동으로 고치는 메모리