소개
지구와 이웃 은하들 사이에서는 매 밀리초마다 수조의 수조 배에 달하는 메시지가 오가요.
하지만 이렇게 먼 거리로 전송하는 일은 까다로워요.
성가신 태양 플레어, 시간 왜곡, 떠도는 힘, 그리고 심지어 우주 나비의 날갯짓 한 번까지도 전송 중에 임의의 비트 하나를 바꿔버릴 수 있어요.
이제 그 결과를 상상해 봐요:
- "싸게 사"가 "지금 팔아"로 바뀌어 은하 간 주식 시장이 폭락하는 일.
- "save new worm hole"이 "cave new worm hole"로 바뀌어 Kepler Whirl 성계와의 연락이 끊기는 일.
- 아니면 카우보이 이모지 🤠가 광대 이모지 🤡로 바뀌어 우주를 실존적 공포에 빠뜨리는 일.
손상된 메시지를 탐지하는 건 그저 중요한 게 아니라 꼭 필요한 일이에요.
수신자는 재앙이 닥치기 전에 뭔가 잘못됐다는 걸 반드시 알아야 해요.
그런데 어떻게 해야 할까요?
우주 곳곳의 과학자와 엔지니어들은 아주 오랜 세월 동안 이 문제와 씨름해 왔어요.
온 우주의 AI 슈퍼클러스터가 데이터를 뒤지고 또 뒤졌죠.
그러던 어느 날, 하나의 전설이 다시 떠올라요. 디버깅 포럼에서 속삭여지고, 너무 많은 걸 봐버린 엔지니어들이 중얼거리던, 오래되고 강력한 방법이요...
패리티 비트!
너무나 단순하고 너무나 강력해서, 어쩌면 성간 통신을 구해낼지도 모르는 방법이에요.
지침
해야 할 일은 다음 두 가지를 구현하는 걸 돕는 거예요.
- 전송 시퀀스를 계산하는 송신기, 그리고
- 그 시퀀스를 디코딩하는 수신기예요.
패리티 비트는 전송 오류를 감지하는 간단한 방법이에요.
송신기와 수신기는 한 번에 정확히 8비트(패리티 비트 포함)만 주고받을 수 있어요.
패리티 비트는 각 전송에 1비트가 짝수 개가 되도록 설정하고, 항상 오른쪽에서 첫 번째 비트예요.
그래서 수신기가 11000001, 01110101, 01000000(즉, 1비트가 홀수 개인 전송)을 받으면 오류가 있다는 걸 알아요.
그런데 메시지가 이렇게 짧은 경우는 드물고, 더 길면 시퀀스 단위로 전송해야 해요.
예를 들어, 11000000 00000001 11000000 11011110(16진수로는 C0 01 C0 DE)이라는 메시지를 생각해 봐요.
각 전송에는 정확히 8비트가 들어가므로, 데이터 7비트와 패리티 비트만 담을 수 있어요.
따라서 데이터 7비트마다 그 뒤에 패리티 비트를 넣어야 해요.
11000000 00000001 11000000 11011110
↑ ↑ ↑ ↑ (7th bits)
이 메시지의 전송 시퀀스는 이렇게 생겼어요.
1100000_ 0000000_ 0111000_ 0001101_ 1110
↑ ↑ ↑ ↑ (parity bits)
시퀀스의 첫 번째 전송에 있는 데이터(1100000)에는 1비트가 두 개(짝수) 있어서 패리티 비트는 0이에요.
첫 번째 전송은 11000000(16진수로는 C0)이 돼요.
그다음 전송의 데이터(0000000)에는 1비트가 하나도 없어요(역시 짝수죠).
그래서 패리티 비트도 다시 0이에요.
따라서 두 번째 전송은 00000000(16진수로는 00)이 돼요.
다음 두 전송의 데이터(0111000과 0001101)에는 1비트가 세 개 있어요.
전송에 1비트가 짝수 개가 되도록 두 데이터의 패리티 비트는 1로 설정해요.
그래서 01110001과 00011011(16진수로는 71과 1B)로 전송돼요.
마지막 전송(1110)에는 데이터가 4비트뿐이에요.
한 번에 정확히 8비트를 전송해야 하고 패리티 비트가 맨 오른쪽 비트이므로, 0비트 세 개를 넣고 그 뒤에 패리티 비트를 붙여 8비트를 맞춰요.
이제 이렇게 돼요(_는 패리티 비트예요).
1110 000_
↑↑↑ (added 0 bits)
여기에도 1비트가 홀수 개 있어서 패리티 비트는 1이에요.
시퀀스의 마지막 전송은 11100001(16진수로는 E1)이 돼요.
이 메시지의 전체 전송 시퀀스는 11000000 00000000 01110001 00011011 11100001(16진수로는 C0 00 71 1B E1)이에요.
