같은 길이의 두 비트열(또는 문자열)에서 같은 위치의 값이 다른 곳의 수. 두 비트열의 배타적 논리합을 취했을 때의 1의 개수와 같다. 예를 들어 1011010과 0110011의 해밍 거리는 4이다. 부호 안의 두 부호어 사이의 거리 중 가장 작은 것을 최소 해밍 거리라 하며, 최소 해밍 거리가 d인 부호는 d − 1비트까지의 오류를 검출할 수 있고, (d − 1) ÷ 2의 소수점 이하를 버린 비트 수까지의 오류를 정정할 수 있다.
일본어 명칭: ハミング距離
해밍 거리(Hamming Distance)은(는) 정보 이론과 부호의 기초 등 1개 분야의 연습 문제 3개에 나와요.
분야: 정보 이론과 부호의 기초
부호어끼리 떨어져 있을수록 오류로 다른 부호어로 바뀌기 어려워집니다. 최소 해밍 거리가 d인 부호에서는 d − 1비트 이하의 오류로는 다른 부호어가 되지 않으므로 검출할 수 있고, 오류가 (d − 1) ÷ 2 이하라면 수신어에 가장 가까운 부호어가 원래 부호어이므로 정정할 수 있습니다. 예를 들어 같은 비트를 3번 보내는 반복 부호는 d = 3으로, 1비트 오류를 다수결로 정정할 수 있습니다.
어느 두 부호어의 배타적 논리합도 부호어가 되는 선형 부호에서는, 두 부호어의 거리가 그 배타적 논리합인 부호어의 1의 개수와 같아집니다. 그래서 최소 해밍 거리는 0이 아닌 부호어의 1의 개수(무게)의 최솟값으로 구할 수 있으며, 모든 쌍을 비교할 필요가 없습니다.
해밍 거리는 두 데이터의 차이를 세는 일반적인 척도로 쓰입니다. PUF(물리적 복제 불가 함수)의 평가에서는 서로 다른 칩의 응답 사이의 해밍 거리가 전체 비트의 50%에 가까울수록 개체를 구별하기 쉽다고 봅니다. 또한 상태 머신의 부호화에서 이웃한 상태의 해밍 거리를 1로 해 두면 전이할 때 바뀌는 비트가 적어집니다.
정답: C. 4
해밍 거리는 같은 위치의 비트가 다른 곳의 수입니다. 두 부호어의 배타적 논리합은 1101001이고 1의 개수가 4이므로, 해밍 거리는 4입니다. 1비트씩 비교하면 1, 2, 4, 7번째 비트가 다릅니다.
정답: A. 검출은 4비트까지, 정정은 2비트까지
최소 해밍 거리가 d인 부호에서는 d − 1비트까지의 오류라면 다른 부호어로 바뀌어 버리는 일이 없으므로 검출할 수 있습니다. 정정에서는 수신한 비트열에 가장 가까운 부호어로 고치므로, 오류가 (d − 1) ÷ 2의 소수점 이하를 버린 값 이하라면 원래 부호어가 가장 가까운 채로 남습니다. d = 5에서는 검출은 4비트까지, 정정은 2비트까지입니다.
서로 다른 것입니다. 해밍 거리는 두 비트열의 차이를 세는 척도이고, 해밍 부호는 최소 해밍 거리가 3이 되도록 만든, 1비트 오류를 정정할 수 있는 부호입니다. 둘 다 해밍의 이름에서 유래합니다.
해밍 거리는 같은 길이끼리만 정의됩니다. 문자의 삽입이나 삭제를 포함하여 차이를 세고 싶을 때는 편집 거리(레벤슈타인 거리)를 사용합니다.
해밍 거리는 같은 위치의 비트가 다른 곳의 수입니다.
두 7비트 부호어 1011010과 0110011의 해밍 거리는?최소 해밍 거리가 d인 부호에서는 d − 1비트까지의 오류라면 다른 부호어로 바뀌어 버리는 일이 없으므로 검출할 수 있습니다.
어떤 부호의 최소 해밍 거리(어느 두 부호어 사이의 해밍 거리 중 최솟값)가 5이다. 오류 검출에만 사용하…6개 쌍의 해밍 거리는 00000과 11110, 01011과 10101의 쌍이 4이고 나머지 4개 쌍이 3이므로, 최소 해밍 거리는 3입니다.
4개의 부호어 00000, 01011, 10101, 11110으로 이루어진 부호의 최소 해밍 거리와, 확실…런 렝스 부호화(Run-Length Encoding) 무손실 압축(Lossless Compression) 상호 정보량(Mutual Information) 손실 압축(Lossy Compression) 순방향 오류 정정(FEC) 이진 대칭 채널(Binary Symmetric Channel) 접두 부호(Prefix Code) 정보 엔트로피(Information Entropy) 정보량(Self-Information) 크래프트 부등식(Kraft Inequality)