이더리움 커뮤니티의 근접성 상(Proximity Prize) 과 비공식적으로 "프록셈버(Proxember)" 로 알려진 것에 힘입어, 일련의 주목할 만한 논문들이 유명한 리드-솔로몬 코드의 근접성 갭(Proximity Gaps for Reed–Solomon Codes) 에서 제기된 "최대 용량" 리스트 디코딩 추측을 비판해 왔습니다. 다이아몬드-앵거스(Diamond–Angus) 에서 첫 번째 포문을 열었고, 이어서 크리테스-스튜어트(Crites–Stewart) 의 연구가 이어졌는데, 모두 같은 메시지로 수렴했습니다. 리드-솔로몬 코드가 (1-\rho) ( 1 - ρ ) 까지 리스트 디코딩될 수 있다는 속설에 심각한 문제가 있다는 것입니다.
이 글은 새로운 것을 증명하는 것이 아닙니다. 이 글 의 유일한 목표는 기존 이론을 구체적으로 느끼게 하는 작고 완벽하게 재현 가능한 수치적 예제를 제시하는 것입니다. Crites–Stewart의 접근 방식을 따라, 저는 간단한 Reed–Solomon 코드를 사용하여, 사소한 보간 임계값과 고전적인 Elias 경계 에서 도출되는 Elias 목록 디코딩 용량 사이에 정확히 위치하는 매개변수를 선택하고, 목록 크기가 이미 수십 개의 코드워드로 폭발적으로 증가함을 보입니다. 그들의 연구는 이 경계를 넘어서는 목록 크기 폭발에 대한 보다 건설적이고 일반적인 설명을 제공합니다. 여기서는 몇 줄의 Python 코드로 재현할 수 있는 작고 화면 크기의 예제에서 동일한 현상을 예시로 보여드릴 뿐입니다.
"최대 용량" 목록 디코딩 추측
숫자를 자세히 설명하기 전에, 모두가 궁금해하는 추측을 먼저 언급하는 게 좋을 것 같습니다.
우리는 유한체 \mathbb{F}_q F q 에 대해 길이 n n , 차원 k k 의 리드-솔로몬(RS) 코드를 사용합니다. 속도 는 \rho = \frac{k}{n} ρ = k n 입니다. ,
그리고 각 코드워드는 크기 n n 의 평가 집합에 대한 차수 < k k 다항식의 평가입니다.
코드 C \subseteq \mathbb{F}_q^n C ⊆ F n q 는 수신된 모든 단어 y \in \mathbb{F}_q^n y ∈ F n q 에 대해 y y 주위의 반경 \delta n δ n 의 해밍 볼이 최대 L L 개의 코드워드를 포함하는 경우 (\delta, L) ( δ , L ) - 리스트 디코딩 가능하다고 합니다.
여기서 \delta δ 는 허용 오차 비율 이고, L L은 목록 크기 입니다. 고전적인 고유 디코딩은 (L = 1) 경우에 해당합니다.
"최대 용량" 목록 디코딩 추측 ( Reed-Solomon 코드의 근접성 갭 에 나타난 대로)은 다음과 같이 비공식적으로 표현할 수 있습니다.
모든 속도 0 < \rho < 1 0 < ρ < 1 및 모든 \eta > 0 η > 0 에 대해 속도 \rho ρ 의 모든 Reed–Solomon 코드는 모든 것에 대해 (\delta, \mathrm{poly}(1/\eta)) ( δ , p o l y ( 1 / η ) ) -리스트 디코딩 가능합니다.
\델타 \le 1 - \rho - \eta.δ ≤ 1 − ρ − η .
말로 표현하면:
- 비율 \rho ρ 의 코드는 1-\rho 1 − ρ 의 분수 오차에 대한 "여유"를 갖습니다.
- 이 추측은 RS 코드가 다항식으로 제한된 목록 크기만으로 거의 그 수의 오류(약간의 여유 \eta η 까지)에서 효율적으로 목록 디코딩될 수 있다고 주장합니다.
- 이것이 사람들이 이를 "RS 코드는 용량까지 목록 디코딩 가능"으로 요약하고 암묵적으로 "용량"을 1-\rho 1 − ρ 선으로 취급하는 이유입니다.
이 추측이 그토록 매력적인 이유는 매우 간단한 추론 과 일치하기 때문입니다. 데이터를 ρ 배 만큼 압축하면 최대 1-ρ 1 − ρ 잡음까지 견딜 수 있어야 한다는 것이 "도덕적으로 옳다"는 것입니다. Proxember의 핵심은 이 민속 그림을 Elias 목록 디코딩 용량 (곡선 ρ = 1 - H_q(δ) ρ = 1 − H q ( δ ) )과 비교하면, 이 "용량까지"라는 추측이 실제로는 너무 많은 것을 요구하고 있으며, 목록 크기가 폭발적으로 증가할 수밖에 없다는 것을 알게 된다는 것입니다.
3.1절에서 크리테스-스튜어트가 하는 일
Crites–Stewart의 시작점은 Elias의 고전적인 목록 디코딩 용량 정리 입니다(예: Guruswami–Rudra–Sudan에서 제시된 대로):
q \ge 2 q ≥ 2 , 0 \le \delta < 1 - 1/q 0 ≤ δ < 1 − 1 / q , 그리고 \eta > 0 η > 0 이라 하자. 충분히 큰 모든 블록 길이 n n 에 대해:
- \rho \le 1 - H_q(\delta) - \eta ρ ≤ 1 − H q ( δ ) − η 인 경우 (\delta, O(1/\eta)) ( δ , O ( 1 / η ) ) -리스트 디코딩 가능 코드가 존재합니다.
- \rho \ge 1 - H_q(\delta) + \eta ρ ≥ 1 − H q ( δ ) + η 이면 모든 (\delta, L) ( δ , L ) -리스트 디코딩 가능 코드는 다음과 같습니다.
L \ge q^{\Omega(\eta n)}.L ≥ q Ω ( η n ) .특히, 목록 디코딩 용량 은 곡선 \rho = 1 - H_q(\delta) ρ = 1 − H q ( δ ) 이며, 여기서 H_q(\delta) H q ( δ ) 는 q q -항 엔트로피 함수입니다.
섹션 3.1에서는 세 가지 주요 작업을 수행합니다.
\delta δ 와 H_q(\delta) H q ( δ ) 사이의 간격을 정량화합니다 .
그들은 간단하지만 중요한 불평등을 증명합니다.\delta < H_q(\delta) \le \delta + \frac{1}{\log_2 q}δ < H q ( δ ) ≤ δ + 1 log 2 큐모든 0 < \delta \le 1 - 1/q 0 < δ ≤ 1 − 1 / q 에 대해, 상한이 본질적으로 엄격함을 보여라. 직관적으로 이는 다음과 같다. \delta δ 의 일부 오차를 허용하는 엔트로피 비용은 \delta δ 보다 약간 크며, 오버헤드는 최대 1/\log_2 q 1 / log 2 이다. 질문 .
이것을 사용하여 "최대 $1-\rho$" 목록 디코딩 그림을 배제합니다.
매우 일반적인 경험적 방법은 비율 \rho ρ 의 코드가 대략적으로 목록 디코딩 가능해야 한다는 것입니다.\델타 \약 1 - \rhoδ ≈ 1 − ρ작은 목록의 분수 오류 - 즉, 용량은 비공식적으로 선 \delta = 1 - \rho δ = 1 − ρ 로 처리됩니다. Crites–Stewart는 H_q(\delta) > \delta H q ( δ ) > δ 임을 기억하면 이것이 Elias 용량 정리와 양립할 수 없다고 지적합니다.
- 작은 목록에 대한 진정한 정보 이론적 한계는 다음과 같습니다.\rho \le 1 - H_q(\delta).ρ ≤ 1 − H q ( δ ) .
- 고정된 \eta > 0 η > 0 에 대해 \delta \le 1 - \rho - \eta δ ≤ 1 − ρ − η 까지 목록 디코딩 가능성을 고집하려고 하면 흥미로운 매개변수 범위에서 필연적으로 다음 영역에 도달하게 됩니다.\rho \ge 1 - H_q(\delta) + \eta',ρ ≥ 1 − H q ( δ ) + eta ' ,Elias는 기하급수적으로 큰 목록을 보장합니다.
다시 말해, "리드-솔로몬 최대 용량"이라는 속설(용량을 1-\rho 1 − ρ 로 해석)은 단순히 실제 목록 디코딩 용량 곡선 위에 있는 매개변수를 요구하는 것입니다.
- 작은 목록에 대한 진정한 정보 이론적 한계는 다음과 같습니다.
간단히 말해서, 섹션 3.1은 새로운 용량 정리를 소개하지 않습니다 . 대신 다음을 설명합니다.
- 고전적인 Elias 목록 디코딩 용량 한계를 떠올립니다.
- 이 경계가 "최대 $1-\rho$" 관점과 어떻게 모순되는지 명시합니다.
이 글의 뒷부분에 나오는 숫자적 장난감 예제는 이 섹션 3.1 논의의 정신을 따르는, 미시적 매개변수에서 이와 동일한 현상을 구체적으로 나타낸 것일 뿐입니다(물론 Crites-Stewart의 처리 방식이 더 일반적이고 건설적입니다).
수치적 예: 사소한 폭발 vs 엘리아스 폭발
이제 구체적인 매개변수를 작은 리드-솔로몬 코드에 대입하고 무차별 대입 목록 디코딩을 실행하면 어떤 일이 일어나는지 살펴보겠습니다. 이 섹션의 요점은 목록 크기 증가의 두 가지 이유를 구분하는 것입니다.
- 사소한 차원 기반 이유(우리가 너무 많은 오류를 허용하여 제약 조건이 너무 적은 경우)
- Elias/용량 이유(엔트로피 계산으로 인해 "충분한" 제약 조건이 있음에도 불구하고 큰 목록이 강제로 생성됨).
우리의 실험은 다음 두 임계값 사이에 엄격하게 위치할 것입니다.
설정
우리는 다음과 함께 일합니다:
- 필드 크기 q = 13 q = 13 (따라서 \mathbb{F}_{13} F 13 이상입니다),
- 블록 길이 n = 12 n = 12 ,
- 차원 k = 5 k = 5 이므로 비율은 다음과 같습니다.\rho = \frac{k}{n} = \frac{5}{12} \약 0.4167,ρ = k n = 5 12 ≈ 0.4167 ,
- 오차 분수\델타 = 0.5,δ = 0.5 ,즉, 디코딩 반경 t = \delta n = 6 t = δ n = 6 오류입니다.
실험의 각 시행에 대해 우리는 다음을 수행했습니다.
- \mathbb{F}_{13} F 13 에 대한 임의의 차수 < k < k 다항식을 샘플링합니다.
- 12 12 도메인의 곱셈 순서로 평가하여 길이가 12 12인 RS 코드워드 c c 를 얻습니다.
- c c 의 좌표 6개를 정확히 손상시키고(무작위로 균일하게 선택하고 무작위로 0이 아닌 오류로 변경), 수신된 단어 y y 를 얻습니다.
- 최대 y y 의 6 6 해밍 거리 내에 있는 모든 RS 코드워드 c' c ′ 를 반환하는 무차별 대입 목록 디코더를 실행합니다.
목록 디코더는 내부적으로 동의 임계값을 계산합니다.
그리고 모든 코드워드가 y y 와 적어도 6 6 위치에서 일치하도록 유지합니다. 즉, 거리는 \le 6 ≤ 6 입니다.
우회로: 사소한 폭발 임계값
리드-솔로몬 코드에서 목록 크기가 폭발적으로 증가하는 데에는 매우 간단한 "차원 계산" 이유가 있습니다. 만약 일치 횟수 (1-\delta)n ( 1 − δ ) n 이 최대 k k 가 되도록 많은 오류를 허용한다면, 차수가 <k < k인 다항식에 대해 최대 k k 개의 제약 조건을 갖게 됩니다.
형식적으로 사소한 폭발 체제는 다음과 같습니다.
이 체제에서는:
- (1-\delta)n ( 1 − δ ) n 좌표와 값을 선택할 수 있습니다.
- 항상 어느 정도 <k < k 다항식이 보간됩니다.
- 그래서 선형대수학만으로 디코딩 볼에서 엄청난 수의 코드워드를 거의 무료로 기대할 수 있습니다.
우리의 작은 코드에 대해:
- n = 12 n = 12 ,
- k = 5 k = 5 ,
- 따라서 사소한 폭발 임계값은 다음과 같습니다.t_{\text{triv}} = n - k = 12 - 5 = 7 \quad\text{오류},t triv = n − k = 12 − 5 = 7 오류 ,동등하게\delta_{\text{triv}} = \frac{7}{12} \약 0.5833.δ 트리브 = 7 12 ≈ 0.5833.
만약 우리가 7 , 7개 이상의 오류를 디코딩하고 있다면, 우리가 관찰한 목록 폭발은 이 사소한 메커니즘의 탓으로 돌릴 수 있을 것입니다.
우리 실험이 진행되는 곳
우리의 실험에서 우리는 다음에서 디코딩합니다.
우리는 가지고 있습니다:
- 계약:(1-\delta)n = 0.5 \cdot 12 = 6,( 1 − δ ) n = 0.5 ⋅ 12 = 6 ,
- 만족시키는6 > k = 5.6 > k = 5.
따라서 우리는 사소한 한계점 바로 아래에 있습니다.
- (1-\델타)n > k ( 1 − δ ) n > k ,
- 동등하게 t = 6 < t_{\text{triv}} = 7 t = 6 < t triv = 7 .
이는 다음을 의미합니다.
t = 6 t = 6 에서 볼 수 있는 목록 크기의 폭발은 단순히 "최대 k k 제약 조건이 있으므로 보간을 통해 많은 코드워드가 생성됩니다"라는 주장으로 설명할 수 없습니다 .
여기서 목록이 폭발적으로 늘어난다면, 그것은 좀 더 미묘하고 정보 이론적 이유 때문일 것입니다.
그 "더 미묘한 이유"는 바로 Elias 목록 디코딩 용량 한계입니다.
Elias 용량 임계값 이상
알파벳 크기 q = 13 q = 13 및 오류 비율 \delta = 0.5 δ = 0.5 의 경우 q q -항 엔트로피를 계산합니다.
따라서 이 \delta δ 에서의 목록 디코딩 용량은 다음과 같습니다.
우리의 요금은
그래서 우리는 수용 능력을 훨씬 초과했습니다 .
Elias 스타일의 계산 논거를 표준적으로 개선하면 모든 센터 y \in \mathbb{F}_{13}^{12} y ∈ F 12 13 에 대한 평균 목록 크기에 대한 명확한 하한이 제공됩니다.
우리의 매개변수에 대해:
- n(\rho + H_q(\delta) - 1) \approx 12 \cdot 0.171302 \approx 2.0556 n ( ρ + H q ( δ ) − 1 ) ≈ 12 ⋅ 0.171302 ≈ 2.0556 , 따라서q^{n(\rho + H_q(\delta) - 1)} = 13^{2.0556} \약 195,q n ( ρ + H q ( δ ) − 1 ) = 13 2.0556 ≒ 195 ,
- 그리고\sqrt{8 n \delta (1-\delta)}= \sqrt{8 \cdot 12 \cdot 0.5 \cdot 0.5}= \sqrt{24} \약 4.90.√ 8n δ ( 1 − δ ) = √ 8 ⋅ 12 ⋅ 0.5 ⋅ 0.5 = √ 24 ≒ 4.90 .
이것을 함께 넣어서,
따라서 평균적으로 임의의 단어 y y를 중심으로 반경 6 6 의 해밍 볼은 이러한 매개변수에서 적어도 약 40 40개의 리드-솔로몬 코드워드를 포함합니다. 그리고 이는 이미 사소한 임계값 t_{\text{triv}} = 7 t triv = 7 오류에 도달하기 전 입니다.
실제 실험에서는 "RS 코드워드 + + 6개의 무작위 오류" 형태의 y y 만 샘플링했는데, 목록 크기가 40 40 에서 55 55 사이이고 평균은 약 48 48 임을 관찰했습니다. 이는 예상했던 대로 이론적인 하한값인 \approx 40 ≈ 40 바로 위에 있습니다. 즉, 간단한 (1-\delta)n \le k ( 1 − δ ) n ≤ k 인수가 적용되지 않는 영역에서 목록 크기 폭발이 유한한 크기로 구체적으로 나타나는 것을 보고 있는 것입니다.
실험 결과
실험의 20회 이상의 독립적인 시도(무작위 코드워드, 무작위 6-희소 오류, 반경 6을 사용한 무차별 대입 목록 디코딩)를 통해 다음을 얻습니다.
Field size q = 13n = 12, k = 5, rate rho = 0.416667delta = 0.500000(1 - delta)*n = 6.000 vs k = 5-> (1 - delta)*n > k (OUT of the trivial interpolation regime)H_q(delta) ≈ 0.7546351 - H_q(delta) ≈ 0.245365 (capacity rate at this delta)rho - (1 - H_q(delta)) ≈ 0.171302 (above capacity)eta = rho + H_q(delta) - 1 ≈ 0.171302Refined Elias-style counting bound:E_y[|B(y, δn) ∩ C|] ≥ q^{n(ρ + H_q(δ) - 1)} / sqrt(8 n δ (1-δ))For these parameters that is ≥ 194.91 / 4.90 ≈ 39.79Random corrupted codewords and their list sizes:trial 0: s = 6, distance ≤ 6, list size = 47trial 1: s = 6, distance ≤ 6, list size = 48trial 2: s = 6, distance ≤ 6, list size = 45trial 3: s = 6, distance ≤ 6, list size = 49trial 4: s = 6, distance ≤ 6, list size = 53trial 5: s = 6, distance ≤ 6, list size = 46trial 6: s = 6, distance ≤ 6, list size = 42trial 7: s = 6, distance ≤ 6, list size = 47trial 8: s = 6, distance ≤ 6, list size = 50trial 9: s = 6, distance ≤ 6, list size = 53trial 10: s = 6, distance ≤ 6, list size = 50trial 11: s = 6, distance ≤ 6, list size = 47trial 12: s = 6, distance ≤ 6, list size = 52trial 13: s = 6, distance ≤ 6, list size = 43trial 14: s = 6, distance ≤ 6, list size = 46trial 15: s = 6, distance ≤ 6, list size = 49trial 16: s = 6, distance ≤ 6, list size = 48trial 17: s = 6, distance ≤ 6, list size = 49trial 18: s = 6, distance ≤ 6, list size = 55trial 19: s = 6, distance ≤ 6, list size = 48Observed list sizes: [47, 48, 45, 49, 53, 46, 42, 47, 50, 53, 50, 47, 52, 43, 46, 49, 48, 49, 55, 48]max list size = 55avg list size = 48.35결론
이 작은 RS 장난감 예제는 단지 정신 건강 검사일 뿐입니다. 사소한 보간 임계값과 엘리아스 경계 사이의 매개변수에서 단일 해밍볼에는 이미 수십 개의 코드워드가 포함되어 있습니다. 이는 엘리아스 분석에서 예측한 대로이며 "최대 $1-\rho$"까지의 모든 전설과 모순됩니다.
제가 사용한 코드는 다음과 같습니다.
https://github.com/asanso/ca/blob/50b6cfb4c3986a7695aa91401963b0ccf60eb986/elias-bound-toy.py
숫자 군대에 합류하고 싶다면 매개변수를 조정하고 더 큰 실험을 실행하여 데이터 포인트가 "엘리아스 아래에서 폭발 없음"이라는 그림을 뒷받침 하는지 아니면 이에 반하는지도 살펴보세요.
감사의 말
저는 Giacomo Fenzi 에게 많은 유익한 토론과 제 장난감 실험에 대한 인내심 있는 디버깅, 그리고 "잠깐만, 이 목록이 정말로 폭발하는 건가요?"라는 질문을 재현 가능하고 (바라건대) 읽기 쉬운 것으로 바꾸도록 전반적으로 격려해 준 것에 감사드리고, Alistair Stewart , George Kadianakis , Benedikt Wagner 에게 주의 깊게 교정하고 유익한 제안을 해준 것에 감사드립니다.
