1비트 오류를 정정할 수 있는 오류 정정 부호의 대표. r개의 검사 비트를 사용하여, 길이 2^r − 1비트의 부호어 중 2^r − 1 − r비트를 데이터에 사용한다. r = 3인 해밍 부호(7, 4)에서는 4비트 데이터에 3비트 검사 비트를 붙인다. 각 검사 비트는 서로 겹치는 비트 조합의 패리티이며, 수신 측에서 검사를 다시 한 결과(신드롬)가 잘못된 비트의 위치를 2진수로 나타낸다. 최소 해밍 거리는 3이며, 전체 패리티를 1비트 더한 SECDED에서는 2비트 오류의 검출도 할 수 있다. 서버용 메모리의 ECC 등에 쓰인다.
일본어 명칭: ハミング符号
해밍 부호(Hamming Code)은(는) 정보 이론과 부호의 기초, 논리 회로 등 2개 분야의 연습 문제 5개에 나와요.
분야: 정보 이론과 부호의 기초
비트 위치를 1~7로 하고, 2의 거듭제곱 위치 1, 2, 4를 검사 비트로 합니다. 검사 1은 위치 번호를 2진수로 나타냈을 때 1의 자리가 1이 되는 위치(1, 3, 5, 7), 검사 2는 2의 자리가 1이 되는 위치(2, 3, 6, 7), 검사 4는 4의 자리가 1이 되는 위치(4, 5, 6, 7)의 1의 개수를 짝수로 합니다. 잘못된 위치 번호를 2진수로 나타냈을 때 1이 되는 자리에 해당하는 검사만 맞지 않게 되므로, 맞지 않는 검사의 가중치를 더하면 잘못된 위치를 알 수 있습니다.
검사 비트가 r개라면 부호어는 2^r − 1비트이며, (7, 4), (15, 11), (31, 26)처럼 길게 할수록 부호화율은 4/7 ≈ 0.57, 11/15 ≈ 0.73, 26/31 ≈ 0.84로 높아집니다. 그 대신 하나의 부호어로 정정할 수 있는 것은 1비트뿐이므로, 긴 부호어일수록 2비트 이상의 오류가 들어갈 확률이 높아집니다.
해밍 부호에 전체 패리티를 1비트 더하면 최소 해밍 거리가 4가 되어, 1비트 오류의 정정(SEC)과 2비트 오류의 검출(DED)을 할 수 있습니다. 64비트 데이터에는 8비트의 검사 비트가 필요하며, 서버용 메모리가 72비트 폭으로 되어 있는 것은 이 때문입니다. 더 많은 오류를 다루는 플래시 메모리 등에서는 BCH 부호나 LDPC 부호가 쓰입니다.
정답: B. 약 0.57
부호화율은 부호어의 길이 n 중 데이터 비트 수 k가 차지하는 비율 k/n입니다. 해밍 부호(7, 4)에서는 4/7 ≈ 0.57로, 보내는 비트의 약 57%가 데이터입니다. 부호화율이 낮을수록 검사 비트가 많아 오류에 강하게 만들기 쉬운 반면, 데이터를 보내는 효율은 떨어집니다.
정답: C. 6번째 비트
수신한 0110001에서 1, 3, 5, 7번째 비트는 0, 1, 0, 1로 1의 개수는 짝수(검사 1의 결과는 0), 2, 3, 6, 7번째 비트는 1, 1, 0, 1로 홀수(검사 2의 결과는 1), 4, 5, 6, 7번째 비트는 0, 0, 0, 1로 홀수(검사 4의 결과는 1)입니다. 검사 4, 검사 2, 검사 1의 결과를 늘어놓은 110을 2진수로 읽으면 6이므로, 6번째 비트가 잘못되었습니다. 6번째 비트를 반전한 0110011은 세 검사를 모두 만족합니다.
전체 패리티가 없는 해밍 부호에서는 2비트 오류라도 신드롬이 0이 아닌 어느 위치를 가리키므로, 올바른 비트를 반전해 버려 오류가 3비트로 늘어납니다. 이를 막기 위해 메모리 등에서는 전체 패리티를 더한 SECDED를 사용하고, 2비트 오류는 정정하지 않고 에러로 보고합니다.
쓰이고 있습니다. 계산이 간단하고 빠르므로 메모리의 ECC나 캐시, 레지스터의 보호 등 지연을 작게 하고 싶은 곳에서 널리 쓰입니다. 통신처럼 많은 오류를 효율적으로 정정하고 싶은 곳에서는 LDPC 부호 등 더 강력한 부호가 쓰입니다.
해밍 부호(7, 4)에서는 4/7 ≈ 0.57로, 보내는 비트의 약 57%가 데이터입니다.
4비트 데이터에 3비트 검사 비트를 붙여 7비트 부호어로 만드는 해밍 부호(7, 4)의 부호화율에 가장 가…r = 5에서는 2⁵ = 32 < 32 + 5 + 1 = 38로 부족하고, r = 6에서는 2⁶ = 64 ≥ 32 + 6 + 1 = 39이므로 해밍 부호의 검사 비트는 6비트입니다.
32비트 데이터에, 1비트 오류를 정정하고 2비트 오류를 검출할 수 있는 SECDED 부호를 붙인다. 해밍…그 때문에 연속된 5비트 이하의 버스트 오류는 원래 순서로 되돌리면 5개의 부호어에 1비트씩 이하로 나뉘어, 모두 해밍 부호로 정정할 수 있습니다.
해밍 부호(7, 4)의 부호어 5개를 늘어놓고, 각 부호어의 1번째 비트 5개, 다음으로 2번째 비트 5개…정정까지 필요한 메모리에서는 여러 패리티를 조합한 ECC(해밍 부호 등)가 사용됩니다.
7비트 데이터 1011001에 짝수 패리티 비트를 붙일 때 패리티 비트의 값은?패리티 비트(Parity Bit) ECC(오류 정정 부호) 런 렝스 부호화(Run-Length Encoding) 무손실 압축(Lossless Compression) 상호 정보량(Mutual Information) 손실 압축(Lossy Compression) 순방향 오류 정정(FEC) 이진 대칭 채널(Binary Symmetric Channel) 접두 부호(Prefix Code) 정보 엔트로피(Information Entropy)