New optimal linear codes over $\ZZ_4$

당신이 시끄러운 방에서 비밀 메시지를 전달하고 있다고 상상해 보세요. 친구가 메시지를 제대로 듣게 하기 위해, 당신은 단순히 단어를 외치는 것이 아니라 단어를 반복하거나, 음조를 바꾸거나, 추가적인 "확인" 소리를 넣습니다. 디지털 통신 세계에서는 이를 **코딩 이론(coding theory)**이라고 부릅니다. 이는 정보(information)를 숫자의 문자열로 채워 넣어, 약간의 정전기나 간섭이 신호를 망가뜨리더라도 수신자가 원래의 메시지를 파악할 수 있게 만드는 과학입니다.

오랫동안 과학자들은 주로 단순한 "온/오프(on/off)" 스위치(0 또는 1과 같은)를 사용하여 이러한 코드를 만들었습니다. 이는 마치 전등 스위치가 꺼져 있거나 켜져 있는 것과 같습니다. 하지만 1970년대에 연구자들은 네 가지 상태(0, 1, 2, 3)를 가질 수 있는 약간 더 복잡한 스위치를 사용하면 훨씬 더 똑똑하고 효율적인 메시지를 만들 수 있다는 것을 깨달았습니다. 이것이 바로 $\mathbb{Z}_4$ 코드의 세계입니다. 이것은 단순히 "정지" 또는 "진행"만을 말하는 것이 아니라, 운전자에게 "주의"나 "서행"과 같은 뉘앙스를 줄 수 있는 신호등과 같습니다. 수학자들의 목표는 "완벽한" 코드를 찾는 것입니다. 즉, 공간을 절약하기 위해 가능한 한 짧으면서도, 가장 강력한 "오류 탐지 초능력"을 가진 코드입니다. 이 초능력을 **최소 거리(minimum distance)**라고 합니다. 유효한 메시지들 사이의 거리가 멀수록, 노이즈에 의해 우연히 다른 유효한 메시지로 변질되기가 더 어려워집니다.

이 논문에서 저자인 호파인 크리스토펜 탱(Hopein Christofen Tang)과 조코 수프리잔토(Djoko Suprijanto)는 이 디지털 도시의 숙련된 설계자처럼 행동합니다. 그들은 단순히 좋은 건물 하나를 찾는 것이 아니라, 완벽한 코드의 전체 동네를 건설하기 위한 새로운 청사진을 발명하고 있습니다. 그들은 먼저 이 메시지들이 안전을 유지하기 위해 얼마나 떨어져 있어야 하는지에 대한 근본적인 규칙을 증명하는 것으로 시작하는데, 이때 오래되고 복잡한 수학적 증명을 아주 쉬운 기술로 간단하게 만들어 버립니다. 그런 다음 이 규칙을 사용하여 새로운 도구 상자를 구축합니다. 이 도구들을 통해, 그들은 대규모의 새로운 코드 모음을 성공적으로 구축하였으며, 이 코드들은 "최적(optimal)"입니다. 즉, 그 크기에 대해 수학적으로 가능한 만큼 강력하다는 뜻입니다. 그들은 특정 크기에 대한 모든 최적의 코드를 찾아냈으며, 전 세계 코드 데이터베이스에 기록된 기존 기록들을 경신한 수많은 새로운 챔피언들도 발견했습니다. 또한 그들은 가능하다고 여겨졌던 일부 오래된 생각들이 실제로는 불가능하다는 것을 보여줌으로써, 새로운 발견을 위한 길을 열어주었습니다.

완벽한 메시지의 이야기

당신이 친구에게 비밀 코드를 보내려고 하는데, 메시지를 전달하는 과정에서 글자를 하나 떨어뜨리거나 숫자를 실수로 바꿀 수도 있다는 것을 알고 있다고 상상해 보세요. 메시지를 보호하기 위해, 당신은 추가적인 "가드(guard)" 숫자를 더합니다. 가드가 많을수록 메시지는 더 안전해지지만, 메시지는 더 길어집니다. 이 분야의 핵심 질문은 이것입니다: 어떻게 하면 메시지를 최대한 안전하게 유지하면서도 가능한 한 짧게 만들 수 있을까?

이 논문의 저자들은 0, 1, 2, 3이라는 네 개의 글자를 가진 특별한 수학적 알파벳을 다루고 있습니다. 과거에는 주로 0과 1만을 사용했습니다. 하지만 네 개의 글자를 사용하면 더 복잡하고 효율적인 코드를 만들 수 있습니다. 코드의 "안전성"은 **리 거리(Lee distance)**라고 불리는 것으로 측정됩니다. 이것은 하나의 유효한 코드를 다른 유효한 코드로 바꾸는 데 드는 "노력"이라고 생각하면 됩니다. 거리가 작으면, 작은 실수(예: 1이 2로 변함)가 당신의 비밀 메시지를 완전히 다른 유효한 메시지로 우연히 바꿔놓을 수 있으며, 이 경우 친구는 이를 알아차리지 못할 것입니다. 만약 거리가 매우 크다면, 메시지를 망가뜨리기 위해 아주 많은 실수가 필요하므로 코드는 매우 강력해집니다.

이 논문은 두 가지 주요 과제를 다룹니다. 첫째, 저자들은 이 코드들의 "속도 제한"을 증명하고자 했습니다. **플로트킨 경계(Plotkin bound)**라고 불리는 유명한 규칙은 "코드를 이보다 더 짧게 만들면 약해질 수밖에 없다"라고 말합니다. 저자들은 이 규칙을 그들의 네 글자 알파벳에 대해 증명하는 훨씬 더 단순하고 새로운 방법을 찾아냈습니다. 이는 복잡한 물리 방정식 대신 간단한 논리 퍼즐을 사용하여, 자동차가 사고 없이 달릴 수 없는 속도 제한을 보여주는 것과 같습니다.

둘째, 가장 중요한 것은, 그들은 이 속도 제한에 딱 맞닿아 있는 최적의 코드들을 구축하고자 했습니다. 이들을 **최적 코드(optimal codes)**라고 부릅니다. 이들은 "골디락스(Goldilocks)" 코드입니다. 너무 길지도 않고, 너무 약하지도 않으며, 딱 적당한 상태입니다.

새로운 코드 구축하기

저자들은 단지 한두 개의 좋은 코드를 찾은 것이 아니라, 그것들을 위한 공장을 세웠습니다. 그들은 서로 다른 재료를 섞어 완벽한 코드를 만드는 레시 Recipe와 같은 여러 가지 새로운 구축 방법들을 도입했습니다.

그들의 핵심 발견 중 하나는 모든 비제로(non-zero) 메시지가 정확히 동일한 강도를 갖는 특정한 유형의 코드입니다. 그들은 이를 일정 가중치(constant weight) 코드라고 부릅니다. 모든 멤버가 정확히 동일한 초능력 수준을 가진 슈퍼히어로 팀을 상상해 보세요. 이 팀은 믿을 수 없을 정도로 예측 가능하고 강력합니다. 저자들은 원하는 어떤 크기에 대해서도 이 완벽한 팀을 구축할 수 있음을 증명했습니다.

그 후 그들은 이 완벽한 팀들을 빌딩 블록(building blocks)으로 사용했습니다. 그들은 두 개의 좋은 코드를 나란히 붙이면 여전히 매우 강력한 새로운 긴 코드를 얻을 수 있다는 것을 보여주었습니다. 또한 하나의 코드를 가져와서 네 배로 길게 늘리면서도 그 강도를 비례적으로 유지하는 방법도 보여주었습니다. 이 단계들을 반복함으로써, 그들은 방대한 양의 새로운 코드 목록을 생성했습니다.

결과: 기록 경신

저자들은 자신들의 새로운 레시피를 다른 수학자들이 관리하는 알려진 코드들의 "명예의 전당"과 대조 테스트했습니다. 그들은 특정 구조(코드의 첫 부분이 2개의 "자유" 차원을 가지고 두 번째 부분이 0인 경우)를 가진 코드들에 대해 모든 최적의 코드를 찾아냈습니다. 이는 그들이 단순히 좋은 코드를 찾은 것이 아니라, 해당 크기에 대한 가능한 모든 최적의 코드를 찾아냈음을 의미합니다.

조금 다른 구조(첫 부분이 3차원인 경우)에 대해서는, 이전에 알려진 그 어떤 것보다 더 나은 수많은 새로운 코드들을 찾아냈습니다. 실제로 많은 길이에서, 그들의 새로운 코드는 이전의 챔피언들보다 더 높은 "안전 거리"를 가졌습니다. 그들은 심지어 플로트킨 최적(Plotkin-optimal)인, 즉 수학적으로 허용되는 이론적 속도 제한에 가장 근접한 코드들도 찾아냈습니다.

하지만 그들은 때때로 "나쁜 소식"을 전하는 역할도 해야 했습니다. 그들은 특정 길이의 경우, 절대적인 이론적 한계에 완벽하게 도달하는 코드를 구축하는 것이 불가능하다는 것을 증명했습니다. 이는 마치 사각형 모양의 원을 만들려는 것과 같습니다. 수학적으로 그것은 불가능합니다. 그들은 어떤 길이에서는 최선을 다하더라도 아주 근소한 차이(최대 1 또는 2 단위의 거리)만큼은 항상 차이가 날 수밖에 없다는 것을 보여주었습니다. 이는 매우 중요한 발견인데, 왜냐하면 다른 연구자들이 불가능한 퍼즐을 풀기 위해 시간을 낭비하는 것을 막아주기 때문입니다.

이것이 왜 중요한가

왜 호기-한 십 대가 네 글자 코드에 관심을 가져야 할까요? 그것은 당신이 문자를 보내거나, 영상을 스트리밍하거나, 파일을 다운로드할 때마다 이 코드들이 배경에서 작동하여 데이터가 오류 없이 도착하도록 만들기 때문입니다. 이 코드들이 더 효율적이고 강력해질수록, 우리의 디지털 세계는 더 빠르고 신뢰할 수 있게 됩니다.

새로운 규칙을 증명하고 더 강력한 코드를 구축함으로써, 탱과 수프리잔토는 엔지니어들에게 디지털 노이즈에 맞서 싸울 수 있는 더 나은 도구를 제공했습니다. 그들은 단순히 몇 개의 새로운 열쇠를 찾은 것이 아니라, 새로운 열쇠 꾸러미를 통째로 만든 것입니다. 비록 그들이 코드의 우주에 있는 모든 미스터리를 해결한 것은 아니지만(완벽한 코드가 아직 알려지지 않은 크기도 많이 남아 있습니다), 그들은 무엇이 가능한지에 대한 지도를 크게 확장했습니다. 그들은 적절한 구축 방법을 사용한다면, 정보를 오류로부터 안전하게 보호하면서도 신호 안에 얼마나 많은 정보를 담을 수 있는지의 경계를 넓힐 수 있다는 것을 보여주었습니다.

결국, 이 논문은 단순하고 영리한 사고의 힘을 보여주는 증거입니다. 복잡한 문제를 관리 가능한 작은 빌딩 블록으로 나누고 새로운 관점으로 게임의 규칙을 증명함으로써, 저자들은 우리의 디지털 대화를 명확하고 안전하게 유지하는 데 도움이 될 새로운 최적 코드들의 보물 상자를 열었습니다.