섀넌의 정보이론
아날로그 데이터를 전송할 때는 먼저 인코딩 과정을 거쳐 bit 의 형태로 변형한 뒤 변형된 데이터를 채널을 통해 전송한다.
이때 채널을 통해 전송되는 데이터에는 잡음이 껴서 데이터가 손상될 수 있다. (패킷 오염)
따라서 정보를 수신하는 측에서는 잡음을 제거하고, bit 데이터를 디코딩하여 본래의 아날로그 데이터 형태로 변환하여 데이터를 수신한다.
잡음을 제거하는 방법 중 하나는 비트를 전송할 때 3번씩 전송해서 수신한 3개의 비트중 더 많은 값을 최종 비트로 결정하는 방법이 있다.
만약 bit 하나가 뒤바뀔 가능성이 10% 라고 한다면, 3개의 비트중 2개 이상의 비트가 뒤바뀔 가능성은 많이 낮아진다.
하지만 결국 0%는 아니기 때문에 이 방법이 완전한 방법은 아니다.
해밍 코드
그래서 해밍 코드를 사용하여 오류를 정정하는 방법이 있다.
해밍 코드는 parity 비트를 사용하여 오류를 정정한다.
원데이터가 1011 인 데이터가 있다고 해보자.
해밍코드는 원데이터의 1, 2, 4, .. (2의 거듭제곱 위치) 에 패리티 비트를 삽입한다.
그러면 xx1x011 이 된다.
1번 위치 패리티 비트는 위치 인덱스를 이진수로 표현했을 때 2^0 = 1 인 인덱스의 비트를 체크한다. (1 3 5 7)
2번 위치 패리티 비트는 위치 인덱스를 이진수로 표현했을 때 2^1 = 1 인 인덱스의 비트를 체크한다. (2 3 6 7)
4번 위치 패리티 비트는 위치 인덱스를 이진수로 표현했을 때 2^2 = 1 인 인덱스의 비트를 체크한다. (4 5 6 7)
그리고 그 비트를 체크해서 1의 개수를 세었을 때, 짝수 혹은 홀수가 되도록 맞춰준다.
이 예시에서는 짝수 패리티 비트를 사용한다고 해보자.
그러면
1번 패리티 비트의 값은 x 1 0 1 에서 1의 개수가 짝수가 되어야 하니 x = 0
2번 패리티 비트의 값은 x 1 1 1 에서 1의 개수가 짝수가 되어야 하니 x = 1
4번 패리티 비트의 값은 x 0 1 1 에서 1의 개수가 짝수가 되어야 하니 x = 0
결론적으로 7-비트 코드워드의 형태는 0110011 이된다.
이제 이 데이터를 그대로 전송하였고 6번 비트에서 오류가 발생했다고 해보자.
0110001
오류를 정정하기 위해 각 패리티 비트의 담당 인덱스 비트들을 체크한다.
1번 패리티 비트의 경우 0 1 0 1 이므로 문제가 없다.
(3, 5, 7 비트는 정상)
2번 패리티 비트의 경우 1 1 0 1 이므로 1이 홀수개이다. 따라서 오류가 존재한다.
(2, 3, 6, 7 중 오류 존재, 3, 7 은 정상이므로 2, 6 중 하나에서 오류 발생)
4번 패리티 비트의 경우 0 0 0 1 이므로 1이 홀수개이다. 따라서 오류가 존재한다.
(4, 5, 6, 7 중 오류 존재, 따라서 2, 6 중 6에서 오류가 발생한 것을 탐지 가능)
따라서 6번 비트를 바꿔주면 원본 코드워드를 복원할 수 있다.
또는 패리티 비트의 담당 비트를 xor 연산했을 때
p0 = 0
p1 = 1
p2 = 1
이므로 이를 이진수로 표현한 110 은 십진수로 6 이므로 6번째 비트를 고쳐야 한다고 알 수도 있다.
이렇게 여분 비트를 활용하면 채널 용량이 정해져 있을 때, 어떤 범위 내에서는 오류 없이 안전하게 데이터를 전송할 수 있다.
지금은 오류 발생 확률을 10% 로 잡았지만, 오류 발생 확률이 점점 증가해서 50%가 되면 전송 후 비트의 값은 완전 랜덤과 같다.
이럴 때는 엔트로피(불확실성)가 제일 높으며, 데이터를 전송 가능한 채널의 용량도 0이 된다.
반면 오류 발생 확률이 0이거나 100 일 때는 확실하게 비트를 뒤집거나 안뒤집는 결정을 내릴 수 있으므로, 채널의 용량도 최대가 된다.
'CS > 분산시스템특론' 카테고리의 다른 글
[분산시스템특론] 5. CAP 이론 & FLP 정리 (0) | 2025.10.22 |
---|---|
[분산시스템특론] 4. 시간 동기화 문제와 램포트 시계 (0) | 2025.10.21 |
[분산시스템특론] 3. 2단계 커밋 프로토콜 (1) | 2025.10.21 |
[분산시스템특론] 2. 두 장군 이야기 (3) | 2025.10.20 |
[분산시스템특론] 1. AI Agents vs. Agentic AI (0) | 2025.10.20 |