Impulsionado pelo Prêmio de Proximidade da comunidade Ethereum e pelo que ficou conhecido não oficialmente como “Proxember”uma série de artigos espetaculares vem cutucando o “até a capacidade” conjectura de decodificação de lista do célebre Lacunas de proximidade para códigos Reed-Salomon. A primeira salva veio de Diamond-Angus, logo seguida pelo trabalho de Crites-Stewart, todos convergindo para a mesma mensagem: algo está terrivelmente errado com a crença folclórica de que os códigos Reed-Solomon podem ser decodificados em listas até (1-\rho).
Este post não tem como objetivo provar nada de novo. Seu único objetivo é fornecer uma imagem pequena e totalmente reproduzível exemplo numérico isso faz com que a teoria existente pareça concreta. No espírito da abordagem de Crites-Stewart, pego um código Reed-Solomon de brinquedo, escolho parâmetros que ficam estritamente entre o limite de interpolação trivial e a capacidade de decodificação de lista de Elias proveniente do limite clássico de Elias e mostro que o tamanho da lista já chega a dezenas de palavras-código. Seu trabalho oferece um tratamento mais construtivo e geral da explosão do tamanho da lista acima desse limite; aqui estou apenas instanciando o mesmo fenômeno em um pequeno exemplo do tamanho de uma tela que você pode reproduzir com algumas linhas de Python.
A conjectura de decodificação de lista “até a capacidade”
Antes de mergulhar nos números, vale a pena expor a conjectura que todos estão cutucando.
Trabalhamos com um código de comprimento Reed-Solomon (RS) ndimensão ksobre um campo finito \mathbb{F}_q. O avaliar é \rho = \frac{k}{n},
e cada palavra-código é a avaliação de um grau-<k polinômio em algum conjunto de avaliação de tamanho n.
Um código C \subseteq \mathbb{F}_q^n é dito ser (\delta, L)-lista decodificável se por todo palavra recebida e \in \mathbb{F}_q^na bola de Hamming de raio \deltan em volta sim contém no máximo eu palavras-código:
\bigl| \{ c \in C : \Delta(c, y) \le \delta n \} \bigr| \le L.
Aqui \delta é o tolerado fração de erroe eu é o tamanho da lista. A decodificação única clássica corresponde ao caso (L = 1).
O Conjectura de decodificação de lista “até a capacidade” (como aparece em Lacunas de proximidade para códigos Reed-Salomon) pode ser formulado informalmente da seguinte forma:
Para cada taxa 0 <\rho < 1 e cada \eta > 0cada código de taxa Reed-Solomon \rho é (\delta, \mathrm{poli}(1/\eta))-lista decodificável para todos
\delta \le 1 – \rho – \eta.
Em palavras:
- Um código de taxa \rho tem “espaço” para uma fração 1-\rho de erros.
- A conjectura afirma que os códigos RS podem ser eficientemente decodificados em lista a partir de quase tantos erros (até uma pequena folga \eta), com apenas um limitado polinomialmente tamanho da lista.
- É por isso que as pessoas resumiram isso como “Os códigos RS são decodificáveis em lista até a capacidade”, tratando implicitamente “capacidade” como o 1-\rho linha.
O que torna esta conjectura tão tentadora é que ela corresponde a uma heurística muito simples: se você compactar seus dados por um fator \rhoparece “moralmente correto” que você seja capaz de sobreviver até 1-\rho barulho. A diferença de Proxember é que, uma vez que você compara essa imagem folclórica com a Capacidade de decodificação de lista Elias (a curva \rho = 1 – H_q(\delta)), você descobre que essa conjectura de “capacidade máxima” é, na verdade, pedir demais e os tamanhos das listas são forçados a explodir.
O que Crites-Stewart faz na Seção 3.1
O ponto de partida em Crites-Stewart é o clássico teorema da capacidade de decodificação de lista de Elias (conforme apresentado, por exemplo, em Guruswami–Rudra–Sudão):
Deixar q \ge 2, 0 \le \delta < 1 - 1/qe deixe \eta > 0. Para todos os comprimentos de bloco suficientemente grandes n:
- Se \rho \le 1 – H_q(\delta) – \etaentão existe um (\delta, O(1/\eta))-list código decodificável.
- Se \rho \ge 1 – H_q(\delta) + \etaentão cada (\delta, L)-list código decodificável tem
eu \ge q^{\Omega(\eta n)}.
Em particular, a decodificação de lista capacidade é a curva \rho = 1 – H_q(\delta)onde H_q(\delta) é o qfunção de entropia -ária.
A Seção 3.1 faz três coisas principais:
-
Quantifica a lacuna entre \delta e H_q(\delta).
Eles provam uma desigualdade simples, mas crucial\delta < H_q(\delta) \le \delta + \frac{1}{\log_2 q}
para todos 0 < \delta \le 1 - 1/qe mostre que o limite superior é essencialmente restrito. Intuitivamente, isto diz: o custo de entropia de tolerar uma fração \delta de erros é um pouco maior do que \deltacom uma sobrecarga de no máximo 1/\log_2q.
-
Use isto para descartar a imagem de decodificação de lista “até $1-\rho$”.
Uma heurística muito comum é que um código de taxa \rho deve ser decodificável em lista até aproximadamente\delta \aproximadamente 1 – \rho
erros de fração com listas pequenas – ou seja, a capacidade é tratada informalmente como a linha \delta = 1 – \rho. Crites–Stewart aponta que isso é incompatível com o teorema da capacidade de Elias, uma vez que você lembra que H_q(\delta) > \delta:
- O verdadeiro limite da teoria da informação para listas pequenas é
\rho \le 1 – H_q(\delta).
- Se você tentar insistir na decodificação da lista até \delta \le 1 – \rho – \eta para alguns fixos \eta > 0então, na interessante gama de parâmetros, você inevitavelmente acaba na região
\rho \ge 1 – H_q(\delta) + \eta’,
onde Elias garante listas exponencialmente grandes.
Em outras palavras, o folclore “Reed-Solomon up-to-capacity” (interpretando “capacidade” como 1-\rho) está simplesmente solicitando parâmetros que estão acima da curva real de capacidade de decodificação de lista.
- O verdadeiro limite da teoria da informação para listas pequenas é
Em resumo, a Seção 3.1 não introduzir um novo teorema de capacidade; em vez disso, ele:
- lembra o clássico limite de capacidade de decodificação de lista de Elias,
- deixa explícito como este limite contradiz a visão “até $1-\rho$”,
O exemplo do brinquedo numérico mais adiante na postagem é apenas uma instanciação concreta desse mesmo fenômeno em parâmetros microscópicos, seguindo o espírito desta discussão da Seção 3.1 (o tratamento de Crites-Stewart é, obviamente, mais geral e mais construtivo).
O exemplo numérico: explosão trivial vs explosão de Elias
Vejamos agora o que acontece quando inserimos parâmetros concretos em um pequeno código Reed-Solomon e executamos a decodificação de lista de força bruta. O objetivo desta seção é separar duas razões diferentes para ampliação do tamanho da lista:
- um trivial razão baseada em dimensão (quando permitimos tantos erros que temos poucas restrições), e
- o Elias/capacidade razão (onde o cálculo da entropia força listas grandes mesmo que ainda tenhamos restrições “suficientes”).
Nosso experimento ficará estritamente entre estes dois limites:
Configurar
Trabalhamos com:
Para cada tentativa do experimento nós:
- Amostra de um grau aleatório < k polinômio sobre \mathbb{F}_{13}.
- Avalie-o em uma ordem multiplicativa-12 domínio para obter um comprimento12 Palavra-código RS c.
- Corrupto exatamente 6 coordenadas de c (escolhido uniformemente aleatoriamente e alterado para erros aleatórios diferentes de zero), obtendo a palavra recebida sim.
- Execute um decodificador de lista de força bruta que retorne todos Palavras-código RS c’ dentro da distância de Hamming no máximo 6 de sim.
O decodificador de lista calcula internamente o limite de acordo
s = \lceil (1 – \delta) n \rceil = \lceil 0,5 \cdot 12 \rceil = 6,
e mantém todas as palavras-código de acordo com sim em pelo menos 6 posições, ou seja, à distância \le 6.
Um desvio: o limiar de explosão trivial
Há uma razão muito simples de “contagem de dimensões” pela qual os tamanhos das listas podem explodir para os códigos Reed-Solomon. Se permitirmos tantos erros que o número de acordos (1-\delta)n é no máximo kentão temos no máximo k restrições em um diploma
Formalmente, o regime de explosão trivial é
(1-\delta)n \le k \Longleftrightarrow\quad \delta \ge 1 – \rho \quad\Longleftrightarrow\quad t = \delta n \ge n – k.
Neste regime:
- você pode escolher (1-\delta)n coordenadas e valores,
- há sempre algum grau
polinômio interpolando-os, - então você espera um grande número de palavras-código na bola de decodificação quase de graça, apenas da álgebra linear.
Para nosso pequeno código:
- n = 12,
- k = 5,
- então o limiar de explosão trivial é
t_{\text{triv}} = n – k = 12 – 5 = 7 \quad\text{erros},
equivalentemente
\delta_{\text{triv}} = \frac{7}{12} \aproximadamente 0,5833.
Se estivéssemos decodificando de 7 ou mais erros, qualquer explosão de lista que observamos poderia ser razoavelmente atribuída a esse mecanismo trivial.
Onde fica nosso experimento
Em nosso experimento, decodificamos de
\delta = 0,5 \quad\Longleftrightarrow\quad t = \delta n = 6.
Nós temos:
Então nós estamos estritamente abaixo o limite trivial:
- (1-\delta)n > k,
- equivalentemente t = 6 < t_{\text{triv}} = 7.
Isso significa:
Qualquer ampliação do tamanho de uma lista que vemos em t = 6 não pode ser explicado pelo simples “temos no máximo k restrições, então a interpolação fornece o argumento de muitas palavras-código.
Se as listas explodem aqui, deve ser por uma razão mais sutil, de teoria da informação.
Essa “razão mais sutil” é exatamente o limite da capacidade de decodificação de listas de Elias.
Acima do limite de capacidade do Elias
Para tamanho do alfabeto q = 13 e fração de erro delta = 0,5calculamos o qentropia -ária
H_{13}(0,5) \aproximadamente 0,754635,
então o capacidade de decodificação de lista nisso \delta é
1 – H_{13}(0,5) \aproximadamente 0,245365.
Nossa taxa é
\rho = \frac{5}{12} \aproximadamente 0,416667,
então nós somos bem acima capacidade:
\rho – (1 – H_q(\delta)) \aproximadamente 0,416667 – 0,245365 \aproximadamente 0,171302 > 0.
Um refinamento padrão do argumento de contagem no estilo de Elias fornece um limite inferior claro para o média tamanho da lista em todos os centros e \in \mathbb{F}_{13}^{12}:
\mathbb{E}_y\bigl(|B(y, \delta n) \cap C|\bigr) \;\ge\; \frac{q^{n(\rho + H_q(\delta) – 1)}}{\sqrt{8 n \delta (1-\delta)}}.
Para nossos parâmetros:
- n(\rho + H_q(\delta) – 1) \aproximadamente 12 \cdot 0,171302 \aproximadamente 2,0556então
q^{n(\rho + H_q(\delta) – 1)} = 13^{2,0556} \aproximadamente 195,
- e
\sqrt{8 n \delta (1-\delta)} = \sqrt{8 \cdot 12 \cdot 0,5 \cdot 0,5} = \sqrt{24} \approx 4,90.
Juntando isso,
\mathbb{E}_y\bigl(|B(y, 6) \cap C|\bigr) \;\gtrsim\; \frac{195}{4,9} \aproximadamente 40.
Então, em média, uma bola de Hamming de raio 6 em torno de uma palavra aleatória sim contém pelo menos cerca de 40 Palavras-código Reed-Solomon nesses parâmetros – e isso já é antes atingimos o limite trivial t_{\text{triv}} = 7 erros.
Em nosso experimento real, onde apenas amostramos sim da forma “palavra-código RS + 6 erros aleatórios”, observamos tamanhos de lista entre 40 e 55com uma média de cerca 48. Isso fica logo acima do limite inferior teórico de \aproximadamente 40exatamente como seria de esperar: estamos vendo uma manifestação concreta e de tamanho finito da explosão do tamanho da lista em um regime onde o simples (1-\delta)n \le k argumento não se aplica.
O que o experimento produz
Mais de 20 tentativas independentes do experimento (palavra-código aleatória, erro aleatório de 6 esparsos, decodificação de lista de força bruta com raio 6), obtemos:
Field size q = 13
n = 12, k = 5, rate rho = 0.416667
delta = 0.500000
(1 - delta)*n = 6.000 vs k = 5
-> (1 - delta)*n > k (OUT of the trivial interpolation regime)
H_q(delta) ≈ 0.754635
1 - 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.171302
Refined 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.79
Random corrupted codewords and their list sizes:
trial 0: s = 6, distance ≤ 6, list size = 47
trial 1: s = 6, distance ≤ 6, list size = 48
trial 2: s = 6, distance ≤ 6, list size = 45
trial 3: s = 6, distance ≤ 6, list size = 49
trial 4: s = 6, distance ≤ 6, list size = 53
trial 5: s = 6, distance ≤ 6, list size = 46
trial 6: s = 6, distance ≤ 6, list size = 42
trial 7: s = 6, distance ≤ 6, list size = 47
trial 8: s = 6, distance ≤ 6, list size = 50
trial 9: s = 6, distance ≤ 6, list size = 53
trial 10: s = 6, distance ≤ 6, list size = 50
trial 11: s = 6, distance ≤ 6, list size = 47
trial 12: s = 6, distance ≤ 6, list size = 52
trial 13: s = 6, distance ≤ 6, list size = 43
trial 14: s = 6, distance ≤ 6, list size = 46
trial 15: s = 6, distance ≤ 6, list size = 49
trial 16: s = 6, distance ≤ 6, list size = 48
trial 17: s = 6, distance ≤ 6, list size = 49
trial 18: s = 6, distance ≤ 6, list size = 55
trial 19: s = 6, distance ≤ 6, list size = 48
Observed 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 = 55
avg list size = 48.35
Conclusão
Este pequeno exemplo de brinquedo RS é apenas uma verificação de sanidade: nos parâmetros sentados entre Além do limiar de interpolação trivial e do limite de Elias, uma única bola de Hamming já contém dezenas de palavras-código, exatamente como prevê a análise de Elias e em tensão com qualquer “até 1-\rho ”folclore.
O código que usei está aqui:
https://github.com/asanso/ca/blob/50b6cfb4c3986a7695aa91401963b0ccf60eb986/elias-bound-toy.py
Se você quiser se juntar ao exército numérico, ajuste os parâmetros, execute experimentos maiores e veja se seus pontos de dados apoiar a imagem “nenhuma explosão abaixo de Elias” ou empurrar para trás contra isso.
Agradecimentos
Estou grato a Giacomo Fenzi por muitas discussões úteis, depuração paciente de meus experimentos com brinquedos e por geralmente me pressionar a virar “espere, esta lista está realmente explodindo?” em algo reproduzível e (espero) legível, e para George Kadianakis, Alistair Stewart e Benedito Wagner pela revisão cuidadosa e sugestões úteis.
Fontesethresear
