Constructing linear codes from digraphs and groups

시끄러운 방에서 비밀 메시지를 보내려고 한다고 상상해 보세요. 단순히 단어를 속삭이기만 한다면, 정전기나 소음이 그 말을 뭉개버릴 수 있습니다. 하지만 만약 당신이 영리한 패턴을 사용하여 메시지를 반복한다면, 듣는 사람은 일부 부분이 손실되더라도 원래의 단어를 알아낼 수 있습니다. 이것이 바로 **오류 정정 부호(error-correcting codes)**의 마법입니다. 이들은 수학적 레시피로서 당신의 문자, 사진, 은행 송금이 글리치(glitch)로부터 안전하게 보호되도록 유지해 줍니다. 수십 년 동안 수학자들은 "골디락스(Goldilocks)" 부호를 찾아 헤매왔습니다. 즉, 빠르게 전송할 수 있을 만큼 짧으면서도, 많은 오류를 고칠 수 있을 만큼 강력하고, 컴퓨터가 즉각적으로 확인할 수 있을 만큼 단순한 부호 말입니다.

이러한 부호를 만들기 위해 과학자들은 종종 두 가지 강력한 도구를 사용합니다. 하나는 **군(groups)**으로, 이는 대칭성을 위한 규칙책과 같아서 패턴을 깨뜨리지 않고 사물을 어떻게 섞을지 알려줍니다. 다른 하나는 **그래프(graphs)**로, 이는 점들이 선으로 연결된 지도와 같습니다. 유명한 종류의 지도로는 **케일리 그래프(Cayley graph)**가 있는데, 이는 군의 특정 규칙 세트를 따라 만들어집니다. 2012년, 연구자들은 이러한 특수한 지도를 사용하면 새로운 종류의 초효율적인 부호를 만들 수 있다는 것을 발견했습니다. 하지만 문제가 있었습니다. 이 지도들은 매우 엄격한 규칙에 의해 구축되었기 때문에, 만들 수 있는 부호의 종류가 제한적이었습니다. 이는 마치 환상적인 레시피를 가지고 있지만, 오직 특정 브랜드의 재료만 사용해야 하는 상황과 같았습니다.

이제 두 수학자, 코엔 델 바예(Coen Del Valle)와 셰릴 E. 프레이거(Cheryl E. Praeger)가 찬장을 열었습니다. 그들은 특정 종류의 지도뿐만 아니라 모든 종류의 지도를 사용하여 이 강력한 부호들을 만드는 방법을 알아냈습니다. 그들은 이 새로운 창조물을 **그래프 부호(graph codes)**와 **다이그래프 부호(digraph codes)**라고 부릅니다. 생각해보면, 표준 그래프는 도로가 양방향으로 통하는 지도이고, **다이그래프(digraph, 유향 그래프)**는 일방통행 도로가 있는 지도입니다. 이 더 유연한 지도들을 사용함으로써, 저자들은 우리가 훨씬 더 다양한 종류의 오류 정정 부호를 만들 수 있음을 보여줍니다. 그들은 이 새로운 부호들이 기존의 부호들만큼 강력하고 효율적이면서도, 상상할 수 있는 거의 모든 대칭적 구조로부터 자유롭게 구축될 수 있다는 것을 증了했습니다. 이는 엔지니어와 과학자들에게 더 나은, 더 빠르고, 더 신뢰할 수 있는 통신 시스템을 설계하기 위한 완전히 새로운 도구 상자를 제공한다는 점에서 매우 중요한 일입니다.

새로운 청사진: 엄격한 규칙에서 유연한 지도로

논문은 2012년 카우프만(Kaufman)과 루보츠키(Lubotzky)의 돌파구를 인정하며 시작됩니다. 그들은 최초로 "대칭적 LDPC 우수 부호(symmetric LDPC good codes)"의 가계(family)를 구축했습니다. 이를 나누어 설명하자면: "LDPC"는 부호가 확인하기 쉽다는 것(저밀도 패리티 검사)을 의미하고, "우수하다(good)"는 것은 효율적이면서도 강력하다는 뜻이며, "대칭적(symmetric)"이라는 것은 부호를 회전하거나 섞어도 모습이 동일하다는 것을 의미합니다. 그들은 이를 **케일리 부호(Cayley codes)**를 사용하여 구축했는데, 이는 마치 모든 방이 다음 방의 완벽한 복사본이며 엄격한 군 규칙에 따라 배치된 집을 짓는 것과 같습니다.

델 바예와 프레이거는 간단한 질문을 던졌습니다. 우리가 정말로 그 엄격한 규칙들이 필요한가? 그들은 케일리 부호의 마법이 군의 규칙 자체에서 오는 것이 아니라, 그들이 사용한 지도(그래프)가 **정점 전이적(vertex-transitive)**이라는 사실에서 온다는 것을 깨달았습니다. 쉬운 말로, 이는 지도가 모든 점의 관점에서 똑같이 보인다는 것을 의미합니다. 어떤 점 위에 서 있더라도, 당신 주변의 도로 패턴은 다른 어떤 점 주변의 패턴과 동일하게 보입니다.

저자들은 지도가 이 "닮은 꼴" 속성을 가지고 있다면, 훌륭한 부호를 만들기 위해 반드시 케일리 그래프일 필요는 없다는 것을 깨달았습니다. 이것이 그들의 두 가지 주요 발명으로 이어졌습니다:

1. 그래프 부호 (Graph Codes): 이들은 무방향 지도(도로가 양방향으로 통함)를 기반으로 구축됩니다. 시작점을 하나 정하고, 그 이웃들을 살펴본 뒤, 연결 관계에 작은 로컬 부호를 적용합니다. 그런 다음, 지도 전체가 모든 점에서 동일하게 보이므로, 이 로컬 규칙을 모든 곳에 복사합니다.
2. 다이그래프 부호 (Digraph Codes): 이들은 유향 지도(일방통행 도로)를 기반으로 구축됩니다. 여기서는 "나가는" 이웃(도로가 향하는 곳)이 "들어오는" 이웃(도로가 오는 곳)과 다를 수 있기 때문에 조금 더 주의해야 합니다. 따라서 나가는 도로에는 하나의 로컬 부호를 적용하고, 들어오는 도로에는 다른 로코 부호를 적용합니다.

게임의 규칙

저자들은 단순히 이 부호들을 발명한 것이 아니라, 그것이 작동함을 증명했습니다. 그들은 만약 당신이 사용하는 작은 "재료들"(작은 부호들)을 올바르게 선택한다면, 최종적인 거대한 부호가 지도의 대칭성을 물려받게 된다는 것을 보여주었습니다.

그들은 핵심적인 정리를 증명했습니다: 만약 당신이 이웃들에게 사용하는 작은 부호가 지도의 대칭성을 존중한다면, 큰 부호 역시 지도 전체의 대칭성을 존중하게 됩니다. 이는 부호가 대칭적이라는 것을 의미하며, 이는 디코딩(해독)을 쉽게 만드는 데 바람직한 특성입니다. 또한 그들은 만약 작은 부호가 "단일 궤도 대칭적(single-orbit symmetric)"이라면(하나의 반복되는 패턴에 의해 생성된다는 뜻), 큰 부호의 "쌍대(dual)"(오류를 확인하는 데 사용되는 관련 부호) 역시 단순한 반복 패턴에 의해 생성된다는 것을 보여주었습니다. 이는 이 새로운 부호들이 매우 대칭적이며, 유명한 2012년의 부호들처럼 효율적이고 확인하기 쉬운 LDPC임을 의미합니다.

가장 흥수는 발견 중 하나는 **연결성(connectivity)**에 관한 것입니다. 저자들은 만 만약 지도가 연결되지 않았다면(마치 서로 닿지 않는 두 개의 별도 섬이 있는 지도처럼), 큰 부호는 각 섬 위에 구축된 작은 부호들의 집합이 된다는 것을 증명했습니다. 이는 우리가 연결된 지도(하나의 큰 섬)에 대한 부호를 만드는 데 집중하면, 나머지는 자동으로 처리할 수 있음을 의미합니다. 이는 문제를 상당히 단순화합니다.

숫자의 게임: 얼마나 좋은가?

저자들은 이론에만 머물지 않았습니다. 그들은 이 부호들이 실제로 얼마나 좋은지 계산했습니다. 그들은 두 가지 주요 통계를 살펴보았습니다:

• 율(Rate): 전체 메시지 크기에 비해 얼마나 많은 유용한 정보를 보낼 수 있는가.
• 상대적 거리(Relative Distance): 부호가 얼마나 많은 오류를 고칠 수 있는가.

그들은 새로운 부호들이 기존의 케일리 부호들만큼 성능이 좋으며, 어떤 경우에는 심지어 더 뛰어나다는 것을 발견했습니다. 구체적으로, 그들은 부호의 "오류 대응" 능력을 예측하는 수학적 공식을 개선했습니다. 기존의 공식이 특정 하한선을 제공했다면, 그들의 새로운 공식은 그 한계치를 약간 더 높게 밀어 올립니다.

이것이 실제로 작동함을 증명하기 위해, 그들은 이 새로운 부호들의 **무한 가계(infinite family)**를 구축했습니다. 그들은 $PSL_2(q)$(행렬 그룹)라는 그룹과 소수 $p = 4093$에 기반한 특정 유향 그래프를 사용했습니다. 그들은 무한히 많은 소수 $q$에 대해, 다음과 같은 부호를 구축할 수 있음을 보여주었습니다:

• 율이 최소 $2/(p+1)$, 즉 약 $0.0005$ 이상.
• 상대적 거리가 최소 $0.001$ 이상.

이 숫자들은 부호가 커지더라도 양수 값을 유지하므로, 그들은 이를 "우수한 다이그래프 부호의 무한 가계"라고 부릅니다. 이는 매우 중요한 진전인데, 왜냐하면 부호가 커지더라도 효율성을 잃지 않고 계속해서 더 크게 만들 수 있음을 증명하기 때문입니다.

다음 단계는 무엇인가? 열린 질문들

논문은 수학계에 도전 과제를 던지며 끝을 맺습니다. 저자들은 새로운 세계로 가는 다리를 놓았지만, 아직 탐험되지 않은 영역들이 남아 있습니다. 그들은 세 가지 구체적인 질문을 제기합니다:

1. 케일리 그래프로부터 구축되지 않은 대칭적 부호의 무한 가계를 찾을 수 있는가? (그들은 그렇다고 추측하지만, 아직 증명하지는 못했습니다).
2. **적절한 다이그래프(proper digraphs)**로부터 구축된 대칭적 부한 가계를 찾을 수 있는가? "적절한 다이그래프"는 적어도 하나의 도로가 일방통행인 지도(A에서 B로 갈 수 있다고 해서 반드시 B에서 A로 올 수 있는 것은 아닌 지도)를 말합니다. 이는 대부분의 대칭적 지도가 양방향인 데 반해 매우 까les한 문제입니다.
3. "나가는" 부호와 "들어오는" 부호가 서로 다른 대칭적 부호를 구축할 수 있는가?

또한 저자들은 그들의 방법이 직접 곱(direct product) 부호(두 개의 부호를 결합하여 하나의 큰 부호를 만드는 것)와 같은 다른 알려진 부호 구축법들을 재현할 수 있다는 점을 언급합니다. 실제로 그들은 유명한 페터슨 그래프(Petersen graph)(10개의 점을 가진 특정 비-케일리 지도)가 매우 대칭적이면서도 케일리 부호로는 구축될 수 없는 부호를 만드는 데 사용될 수 있음을 보여주었습니다. 이는 그들의 이론이 실제로 작동함을 보여주는 구체적인 사례로, 기존의 엄격한 규칙이 만들어낼 수 있는 것보다 더 낫거나 다른 부호를 만들어낸 것입니다.

요약하자면, 델 바예와 프레이거는 강력한 수학적 도구를 가져와서 그 제약을 완화했고, 더 많은 자유가 주어졌을 때 오히려 더 잘 작동한다는 것을 보여주었습니다. 그들은 단순히 새로운 부호를 찾은 것이 아니라, 부호를 구축하는 새로운 방식, 즉 엄격한 군 규칙이라는 문 뒤에 갇혀 있던 광범위한 가능성의 문을 여는 새로운 사고방식을 찾아낸 것입니다.