[Computer Architecture] 패리티 비트 & 해밍 코드

1. 패리티 비트(Parity Bit)의 원리 및 종류

(1) 정의 및 목적

• 패리티 비트는 정보 전달 과정에서 오류가 발생했는지 검사하기 위해 데이터에 추가하는 비트를 말한다.
• 전송하고자 하는 데이터의 각 문자에 1비트를 더하여 전송하는 방식이다.

(2) 종류

• 패리티 비트에는 짝수 패리티와 홀수 패리티 두 가지 종류가 있다.
• 이는 전체 비트(데이터 비트 + 패리티 비트)에서 1의 개수가 짝수 또는 홀수에 맞도록 패리티 비트를 정하는 것을 의미한다.

(3) 짝수 패리티 예시

• 7비트 데이터가 '1010001'일 경우, 데이터 내 1의 개수는 총 3개이다.
• 짝수로 맞추기 위해 패리티 비트로 '1'을 추가해야 한다.
• 최종 전송 데이터는 '11010001'이며, 이때 맨 앞의 '1'이 패리티 비트이다.

2. 해밍 코드(Hamming Code)의 원리 및 필요성

(1) 정의 및 기능

• 정의: 해밍 코드는 데이터 전송 시 1비트의 에러를 정정할 수 있는 자기 오류정정 코드를 말한다.
• 기능: 해밍 코드는 패리티 비트를 활용하여 1비트에 대한 오류 발생 위치를 찾아 수정할 수 있다.

(2) 필요성

• 일반적인 패리티 비트는 오류를 검출하기만 할 뿐 수정하지는 못하므로, 오류 수정 기능을 위해 해밍 코드를 활용한다.

3. 해밍 코드의 오류 정정 방법 (짝수 패리티 기준)

(1) 패리티 비트 위치 설정

• 해밍 코드는 2의 n승 번째 자리인 1, 2, 4, 8... 번째 자릿수를 패리티 비트(P)로 지정하는 것에서 시작한다.
• 이 패리티 비트들로부터 시작하는 세 개의 패리티 비트가 짝수인지, 홀수인지 기준으로 오류를 판별한다.

(2) 오류 정정 과정 예시

짝수 패리티의 해밍 코드 '0011011'에 오류가 발생했을 때 수정된 코드를 찾는 과정이다.

• P1(첫 번째 비트) 확인: 1, 3, 5, 7번째 비트(0, 1, 0, 1)를 확인한다. 1의 개수가 2개(짝수)이므로 패리티 비트 값은 0이다.
• P2(두 번째 비트) 확인: 2, 3, 6, 7번째 비트(0, 1, 1, 1)를 확인한다. 1의 개수가 3개(홀수)이므로 패리티 비트 값은 1이다.
• P4(네 번째 비트) 확인: 4, 5, 6, 7번째 비트(1, 0, 1, 1)를 확인한다. 1의 개수가 3개(홀수)이므로 패리티 비트 값은 1이다.

(3) 오류 위치 도출 및 수정

• 확인된 패리티 비트 값을 역순(P4, P2, P1 순서)으로 조합하여 '110'을 도출한다.

• 이 이진수 '110'을 10진법으로 변환하면 '6'이 되며, 이는 6번째 비트에 오류가 있음을 의미한다.

• 따라서 6번째 비트를 수정하여 정답 코드는 '0011001'이 된다.

  🌟 세 개의 패리티 비트란?

  "세 개의 패리티 비트"는 해밍 코드(특히 7비트 해밍 코드)가 작동하는 '체크 그룹'의 개수를 말하는 것이다.

  1. 왜 하필 '세 개'일까?
     우리가 7비트짜리 해밍 코드를 만들 때, 규칙에 따라 1번, 2번, 4번 자리에 패리티 비트를 넣기로 약속했다.
     • P1 (1번 자리): 첫 번째 패리티 비트
     • P2 (2번 자리): 두 번째 패리티 비트
     • P3 (3번 자리): 세 번째 패리티 비트

  2. 각 패리티 비트가 감시하는 영역 (세 개의 그룹)
     이 세 개의 비트는 각각 자기가 맡은 구역이 정해져 있다.

     패리티 비트	감시하는 비트 위치	결과
     첫 번째 (P1)	1, 3, 5, 7번째	짝수면 0, 홀수면 1
     두 번째 (P2)	2, 3, 6, 7번째	짝수면 0, 홀수면 1
     세 번째 (P4)	4, 5, 6, 7번째	짝수면 0, 홀수면 1

     감시하는 비트 위치는 각 비트의 위치 번호를 이진수로 써보면 알 수 있다.

     위치 (10진수)	위치 (2진수)	포함되는 그룹 (1이 있는 자리)
     1	001	첫 번째 그룹 (P1)
     2	010	두 번째 그룹 (P2)
     3	011	첫 번째(P1) + 두 번째(P2)
     4	100	세 번째 그룹 (P3)
     5	101	첫 번째(P1) + 세 번째(P3)
     6	110	두 번째(P2) + 세 번째(P3)
     7	111	첫 번째(P1) + 두 번째(P2) + 세 번째(P3)

     • P1 (1번 자리, 001): 이진수의 첫 번째 자리가 1인 모든 위치를 감시한다. ➡️ 1, 3, 5, 7
     • P2 (2번 자리, 010): 이진수의 두 번째 자리가 1인 모든 위치를 감시한다. ➡️ 2, 3, 6, 7
     • P3 (3번 자리, 100): 이진수의 세 번째 자리가 1인 모든 위치를 감시한다. ➡️ 4, 5, 6, 7

  3. 이 '세 개'의 결과가 모여 '주소'가 된다.
     위 내용에서 "역순으로 패리티 비트 '110'을 도출했다"는 부분이 핵심이다.
     1) 첫 번째 그룹 체크 결과: 0
     2) 두 번째 그룹 체크 결과: 1
     3) 세 번째 그룹 체크 결과: 1
     4) 이걸 거꾸로 합치면: 110 (2진수)
     5) 10진수로 바꾸면: 6
     즉, 세 개의 패리티 비트가 각각 검사한 결과(0 또는 1)를 모으면, 오류가 난 위치의 '주소'가 완성되는 원리이다. 그래서 "세 개의 패리티 비트를 기준으로 판별한다"고 말하는 것이다.

  🌟 패리티 비트를 역순으로 조합하는 이유

  그 이유는 우리가 숫자를 쓰는 '이진수 표기법'의 자릿수(가중치) 때문이다.
  따라서, 더 큰 숫자를 담당하는 패리티 비트를 앞(왼쪽)에 써야 우리가 아는 10진수 주소가 나오기 때문이다.

  1. 각 패리티 비트의 '무게(가중치)'
     해밍 코드에서 각 패리티 비트는 자기가 위치한 번호만큼의 가중치를 가진다.
     • P1 (1번 자리): 이진수에서 2^0(1의 자리)를 담당
     • P2 (2번 자리): 이진수에서 2^1(2의 자리)를 담당
     • P4 (4번 자리): 이진수에서 2^2(4의 자리)를 담당
  2. 왜 역순(P4→P2→P1)일까?
     우리가 10진수 '6'을 이진수로 쓸 때 110이라고 쓴다. 이때 왼쪽부터 읽으면 4의 자리, 2의 자리, 1의 자리 순서이다.
     만약 자료의 예시처럼 오류 위치가 6번이라면,
     • 4의 자리를 담당하는 P4는 오류를 감지해서 1이 된다.
     • 2의 자리를 담당하는 P2도 오류를 감지해서 1이 된다.
     • 1의 자리를 담당하는 P1은 6번을 감시하지 않으니 0이 된다.

  이 결과값들을 가중치가 큰 순서(P4→P2→P1)대로 나열해야 우리가 아는 이진수 110이 되고, 이걸 10진수로 바꿨을 때 정확히 6이라는 숫자가 나오는 것이다.