[TIL] Hamming Codes: 해밍 코드

게임을 하다가 발견한 문제가 마침 CS 지식을 요구하는군요. Bitburner라는 게임인데 광기에 물든 개발자들이 즐기는 게임인 것 같습니다. 

게임을 처음 시작하면 Sector-12라는 곳에서 게임을 시작하게 됩니다. 이곳 저곳 서버를 돌아다니면, contract 파일을 발견할 수 있는데 이 파일을 열어보면 다양한 문제가 등장합니다.

처음 발견한 문제가 아래의 해밍 코드를 활용한 문제입니다.

총 10번의 기회가 있다는군요. 해밍 코드를 이용해서 오류를 고치고 십진수 값을 구해달라고하네요.

 

Hamming Codes: Encoded Binary to Integer
You are attempting to solve a Coding Contract. You have 10 tries remaining, after which the contract will self-destruct.
You are given the following encoded binary string:
'0110100010000000000000000000001110000000010111100111010010111110'

Treat it as an extended Hamming code with 1 'possible' error at a random index. Find the 'possible' wrong bit, fix it and extract the decimal value, which is hidden inside the string.

Note: The length of the binary string is dynamic, but its encoding/decoding follows Hamming's 'rule'
Note 2: Index 0 is an 'overall' parity bit. Watch the Hamming code video from 3Blue1Brown for more information
Note 3: There's a ~55% chance for an altered Bit. So... MAYBE there is an altered Bit 😉
Note: The endianness of the encoded decimal value is reversed in relation to the endianness of the Hamming code.
Where the Hamming code is expressed as little-endian (LSB at index 0), the decimal value encoded in it is expressed as big-endian (MSB at index 0). Extra note for automation: return the decimal value as a string

 

해밍 코드라는 개념이 등장합니다. 데이터 전송간에 오류를 검출하고 수정할 수 있도록 고안된 코드입니다. 어디서 들어본 기억은 나는데 잘 모르는 개념이니 확실하게 알고가도록 합시다!

 

해밍 코드란 ?

수학자 리처드 웨슬리 해밍(Richard Wesley Hamming)이 1940년대 말에 벨(Bell) 연구소에서 개발하여 1950년에 작성된 저서에 소개 되어있는데, 그의 이름을 따서 해밍 코드(Hamming Code)라고 명명되었다.

해밍 코드는 데이터 비트에 몇가지의 패리티 비트가 추가된 코드이다. 기존의 패리티 비트들은 수신된 데이터열에 에러 유무만 확인할 수 있었는데,
해밍 코드를 이용하면 에러 비트의 위치뿐만아니라 정정도 가능하다.

 

위와 같이 해밍 코드는 에러를 검출할 뿐 아니라 패리티비트를 보고, 1비트에 대한 오류를 정정할 곳을 찾아 수정할 수 있습니다!!

이러한 해밍 코드의 단점은 상당히 많은 체크 비트가 추가된다는 점과 오류가 2개 이상일 경우 정정하지 못하는 약점이 있습니다. 이 경우 잘못된 오류 정정으로 인해 추가 오류를 발생시키기도 합니다.

필요한 패리티비트의 수 구하는 방법

데이터 비트의 수를 k라고 할 때, 패리티 비트의 수를 r로 표현할 수 있습니다. 이때, r의 값을 계산하는 공식은 다음과 같습니다:

r >= log2(k) + 1

• r은 반드시 k보다 크거나 같아야 합니다.
• r 값은 소수점 아래를 버림한 정수로 해야합니다.
• 이렇게 계산된 패리티 비트의 수는 최소한으로 필요한 패리티 비트의 개수입니다.

예를들어 1byte(=8bit)의 크기를 가진 데이터가 있다면

• r >= log2(8) + 1
• r >= 3 + 1
• r >= 4 

따라서 필요한 패리티비트의 수는 4가 되며 이를 합하면 총 12bit를 전송하게 됩니다.

패리티비트를 삽입하는 위치

패리티 비트의 위치를 결정하는 일반적인 방식은 "2의 거듭제곱 위치"에 패리티 비트를 배치하는 것입니다.
데이터와 패리티 비트를 조합하여 전체 코드워드를 만들 때, 코드워드의 비트 번호는 1 부터 시작합니다. 이때, 패리티 비트를 위치시키는 비트 번호는 2^0, 2^1, 2^2, 2^3, 등의 값을 갖게 됩니다.

즉 위와 같이 8bit의 데이터를 전송한다고 가정했을때 패리티비트의 위치는 각각 1, 2, 4, 8 번째에 위치합니다.

그 뒤 데이터 비트는 각각의 빈 공간에 할당합니다.

패리티비트를 결정하기

짝수 패리티비트의 개념을 정리할 필요가 있습니다.

첫번째 패리티비트의 영역은 1, 3, 5, 7, 9, 11 ... 로 홀수 인덱스를 검사합니다.
두번째 패리티비트의 영역은 (2,3), (6,7), (10,11), (14,15) ... 자신을 포함한 1칸 옆의 숫자 뒤에 2칸을 띄고 2개 다시 2칸을 띄고 2개를 검사한다.
세번째 패리티비트의 영역은 (4.5.6,7), (12,13,14,15) ...로 4칸을 간격으로 검사합니다.
네번째 패리티비트의 영역은 (8,9,10,11,12,13,14,15) ... 8칸 간격으로 검사합니다.

각각 검사 결과에 따라 1의 갯수가 짝수면 패리티비트에 0을 할당하고, 홀수면 1을 할당합니다.

예를 들어 다음과 같은 데이터를 전송한다고 가정해 보겠습니다.

11110001

그럼 패리티비트를 추가하여 최종 전송할 비트는 이렇습니다.

111011110001

오류를 검출하는 방법

신드롬(Syndrome) 값을 구해야합니다.
패리티비트를 포함하여 검사를 해줍니다.

C1 = P1 D3 D5 D7 D9 D11를 검사해서 짝수인지 확인합니다. 짝수면 0 홀수면 1
C2 = P2 D3 D6 D7 D10 D11 을 검사해서 짝수면 0 홀수면 1
C4 = P4 D5 D6 D7 D12 을 검사해서 짝수면 0 홀수면 1
C8 = P8 D9 D10 D11 D12 을 검사해서 짝수면 0 홀수면 1

C1C2C4C8의 값이 0이므로 신드롬 값은 0입니다.

신드롬 값이 0이면 오류가 없다는 뜻입니다.
만약 값이 5면 D5에서 오류가 발생한 것입니다.

오류가 발생한 비트의 값을 반전하여 데이터를 정정해 줄 수 있습니다.

문제 풀이

아래는 게임의 문제를 풀기 위해 작성된 스크립트입니다. JavaScript로 작성되었습니다.

_data를 입력 받아 코드를 검사하고 오류를 수정한 뒤 10진수로 출력하는 함수입니다.

위에서 말로 열심히 풀어 쓴 내용이 이 함수 안에 담겨 있네요.

// 전송 받은 데이터, 1개의 오류가 존재할 수 있다.
// 오류를 찾아 수정하여 정확한 데이터를 추출한 뒤 10진수로 출력해야합니다.
const _data = '0110100010000000000000000000001110000000010111100111010010111110';

function main(_data) {
  // 변경된 비트를 확인하고 복원합니다.
  const _build = _data.split(""); // 작업을 위한 배열 생성
  const _testArray = []; // "진리표"용 배열. 어떤 값이라도 거짓이면 데이터에 변경된 비트가 있음을 나타냄
  const _sumParity = Math.ceil(Math.log2(_data.length)); // 나중에 사용할 패리티 비트의 합계
  const count = (arr, val) =>
    arr.reduce((a, v) => (v === val ? a + 1 : a), 0);
  // 카운트 함수... 다시 한번 ;)

  let _overallParity = _build.splice(0, 1).join(""); // 첫 번째 인덱스를 저장하고, 다음 단계에서 확인하고 _build를 올바르게 수정함
  _testArray.push(_overallParity == (count(_build, "1") % 2).toString() ? true : false); // 전체 패리티 비트와 비교하여 첫 번째 확인
  for (let i = 0; i < _sumParity; i++) {
    // 나머지 패리티 비트에 대해 확인
    const _tempIndex = Math.pow(2, i) - 1; // 패리티 비트의 인덱스 가져오기
    const _tempStep = _tempIndex + 1; // 스텝 크기 설정
    const _tempData = [..._build]; // 작업용으로 빌드 데이터의 "복사본" 가져오기
    const _tempArray = []; // "테스트"용 빈 배열 초기화
    while (_tempData[_tempIndex] != undefined) {
      // "시작" 인덱스가 정의되지 않을 때까지 데이터에서 추출
      const _temp = [..._tempData.splice(_tempIndex, _tempStep * 2)]; // 2*스텝 크기 추출
      _tempArray.push(..._temp.splice(0, _tempStep)); // 그리고 다시 반으로 나누어 첫 번째 반만 유지
    }
    const _tempParity = _tempArray.shift(); // 다시 첫 번째 인덱스를 분리하여 나머지 데이터와 비교하기 위해 저장
    _testArray.push(_tempParity == (count(_tempArray, "1") % 2).toString() ? true : false);
    // _tempParity가 계산된 데이터와 일치하는지 확인하여 "진리표"에 결과를 추가
  }
  let _fixIndex = 0; // "수정" 인덱스 초기화 및 0으로 시작
  for (let i = 1; i < _sumParity + 1; i++) {
    // _testArray의 모든 부울 값을 2번째 인덱스부터 이진법으로 더하기
    _fixIndex += _testArray[i] ? 0 : Math.pow(2, i) / 2;
  }
  _build.unshift(_overallParity); // 이제 "전체" 패리티 비트를 원래 자리에 다시 넣어야 함
  // 실제 인코딩된 이진 문자열에 오류가 있는 경우 수정을 시도합니다.
  if (_fixIndex > 0 && _testArray[0] == false) {
    // 전체가 거짓이고 계산된 값의 합이 0 이상인 경우 해당하는 해밍 비트를 수정합니다.
    _build[_fixIndex] = _build[_fixIndex] == "0" ? "1" : "0";
  } else if (_testArray[0] == false) {
    // 그렇지 않으면 전체 패리티 비트만 잘못된 경우 해당 비트를 수정합니다.
    _overallParity = _overallParity == "0" ? "1" : "0";
  } else if (_testArray[0] == true && _testArray.some((truth) => truth == false)) {
    return 0; // 음, 뭔가 이상한 일이 벌어지고 있습니다... 2개의 비트가 변경되었나요? 어떻게 이럴 수 있을까요? 👀
  }
  // 중간까지 완료되었습니다... 가능한 변경된 비트를 수정했으므로 이제 _build에서 패리티 비트를 "추출"합니다.
  for (let i = _sumParity; i >= 0; i--) {
    // 마지막 패리티부터 2번째 인덱스까지 역순으로 추출합니다.
    _build.splice(Math.pow(2, i), 1);
  }
  _build.splice(0, 1); // 전체 패리티 비트를 제거하고 이제 이진 값을 얻습니다.
  return parseInt(_build.join(""), 2); // 이진 값을 10진수로 변환하여 결과 반환
};

const solved = main(_data);

console.log(solved);

 

 

이 코드를 실행하면 아래와 같이 콘솔에 결과가 출력됩니다.

6448641214

 

이 게임의 고수들은 게임 내 이러한 문제를 자동으로 찾아 풀어주는 스크립트를 만들어 자동화하고 있지만 이미 자동화된 스크립트를 받아 낼름 풀어버리는 것 보다는 이렇게 하나의 지식을 얻어가는 것이 더 도움이 될 것 같습니다.