Capacity of Additive-Noise Sticky Channels

당신이 무전기로 비밀 메시지를 보내고 있다고 상상해 보세요. 하지만 신호가 약간 불안정합니다. 때때로 하나의 '삐' 소리가 길게 늘어져서 '비이이이입'처럼 들리기도 하고, 짧은 '삐' 소리가 중복되어 나타나기도 합니다. 정보 이론의 세계에서 이것을 '스티키 채널(sticky channel)'이라고 부릅니다. 이는 마치 글을 쓸 때 펜이 종이에 가끔 걸려서 의도치 않게 같은 글자를 두 번이나 세 번 연속으로 쓰는 것과 같습니다. 단, 글자를 건너뛰거나 지우지는 않습니다. 과학자들이 이 문제에 관심을 갖는 이유는 현실 세계에서 이런 오류가 빈번하게 발생하기 때문이며, 특히 우리가 데이터를 DNA에 저장하려고 할 때 그렇습니다. DNA는 생물학적 하드 드라이브와 같지만, 이를 다시 읽어낼 때 기계들이 긴 동일한 유전자 문자 배열 때문에 혼란을 겪곤 합니다. 문자가 늘어나거나 압축되는 현상이 발생하는 것이죠. 여기서 핵심적인 질문은, 메시지가 뒤섞인 상태가 되지 않고 얼마나 많은 정보를 이 결함 있는 채널을 통해 전달할 수 있는가 하는 점입니다. 이것이 바로 채널의 '용량(capacity)', 즉 오류 없이 데이터를 보낼 수 있는 최대 속도입니다.

본 논문은 '애디티브 노이즈 스티키 채널(additive-noise sticky channel)'이라는 특정 유형의 스티키 채널을 깊이 있게 파헤칩니다. 이것을 구슬 줄을 보내는 게임이라고 생각해 봅시다. 각 그룹의 동일한 구슬들(하나의 '런', run)마다 장난꾸러기 괴물이 그 끝에 임의의 개수만큼 추가 구슬을 붙이는 식입니다. 괴로의 행동은 '노이즈 분포'를 따릅니다. 저자들은 이 게임을 통해 아무런 혼동 없이 메시지를 보낼 수 있는 절대적인 최고 속도(용량)를 알아내고자 했습니다. 우선 연구진은 괴물이 구슬 하나를 더하거나 혹은 아예 더하지 않는, 동전을 던지는 것과 같은 단순한 버전부터 시작했습니다.

연구진은 이 게임에서 매우 놀라운 규칙들을 발견했습니다. 특정 범위의 동전 앞면 확률(구체적으로 구슬을 추가할 확률이 약 0.382에서 0.5 사이일 때) 내에서는 최선의 전략이 뜻밖에도 아주 간단하다는 것을 발견했는데, 그것은 오직 홀수 길이의 구슬 그룹만을 사용하여 메시지를 보내는 것입니다. 알고 보니 이 특정한 '스위트 스팟(sweet spot)'에서는 이 단순한 기술이 실제로 가장 뛰어난 방법이었으며, 더 복잡한 코드로도 이를 능가할 수 없었습니다. 그러나 만약 동전의 결과가 다르게 편향된다면(즉, 구슬을 거의 추가하지 않거나 또는 매우 자주 추가한다면), 이 단순한 기술은 왕좌에서 물러나야 하며, 채널로부터 최대한의 효율을 얻기 위해서는 더 똑똑하고 복잡한 인코딩 방식이 필요하게 됩니다.

또한 연구팀은 노이즈가 극단적으로 변할 때 어떤 일이 일어나는지도 살펴보았습니다. 만약 괴물이 항상 구슬을 추가하는 경우(확률이 1에 가까울 때)에는 용량이 떨어지는데, 저자들은 정확히 어떻게 감소하는지를 계산해 냈습니다. 심지어 노이즈가 매우 희귀할 때의 동작 양상이 노이즈가 흔할 때와 다르다는 것도 밝혀냈는데, 이는 직관과는 조금 다른 결과입니다. 나아가 연구팀은 (실제 DNA 저장 시 필요한 제약 조건인) 구슬 그룹의 길이를 제한하는 상황을 탐구했습니다. 만약 구슬 그룹을 짝수로만 한정한다면, 위에서 언급한 단순한 '홀수 길이 전용' 전략은 절대로 최고의 전략이 될 수 없음을 찾아냈습니다.

마지막으로 팀은 관점을 넓혀, 단순히 구슬 하나뿐 아니라 여러 개의 구슬을 추가할 수도 있는 훨씬 큰 규모의 괴물을 고려했습니다. 그들은 평균적인 노이즈 양에 대해, 성능의 하한선을 설정하는 데 결정적인 역할을 하는 '최악의 사례'(특정한 종류의 노이즈 분포)가 존재함을 증명했습니다. 또한 특정 형태의 노이즈에 대해서는, 아무리 설정을 조정하더라도 단순한 홀수 길이 전략이 결코 최선이 될 수 없음을 보여주었습니다. 모든 가능한 노이즈 유형에 대한 수학적 퍼즐을 완벽하게 해결하지는 못했을지라도, 그들은 매우 정교한 수학적 경계를 제공했고 자신들의 공식이 옳다는 강력한 근거를 제시함으로써, 이전보다 훨씬 명확하게 이 결함 있는 통신 환경의 지도(map)를 그려냈습니다.