Onde posso encontrar exemplos de códigos de correção de erros dos seguintes tipos?

Primeiro, peça desculpas se esta pergunta é apropriada ou trivial para este site. Sou físico procurando ajuda fora de sua zona de conforto.

Em PRL 87 167902 (2001) , alega-se que

"... para um arbitrariamente pequeno , existe um código de correção de erros com (para alguma constante ) tal que a distância de Hamming entre quaisquer duas palavras de código distintas e esteja entre e ".E : { 0 , 1 } n → { 0 , 1 } m m ≤ n / δ c c E ( x ) E ( y ) ( 1 - δ ) m / 2 ( 1 + δ ) m /$\delta>0$$E: \{0,1\}^n \rightarrow \{0,1\}^m$$m\leq n / \delta^c$$c$$E(x)$$E(y)$$(1 - \delta)m/2$$(1 + \delta)m/2$

No artigo, isso é conhecido por causa de provas não construtivas da existência. Eu gostaria de saber se existem exemplos explícitos de tais códigos (ou similares, ou mesmo melhores), dado que o artigo existia há 16 anos.

Em particular, estou interessado nos códigos que e a distância de Hamming entre duas palavras de código distintas têm uma menor vinculado pelo menos linear em (sou bastante flexível sobre o comportamento com , pois só preciso do caso ).$E: \{0,1\}^n \rightarrow \{0,1\}^m$$m = O(n)$$m$$\delta$$\delta = 1/2$

Eu pergunto aqui, porque tenho certeza de que essa será uma pergunta muito fácil para a pessoa correta, mas não sou essa pessoa e não tenho certeza de onde é melhor começar a procurar. Qualquer sugestão de onde procurar seria muito apreciada.

Se você só precisa de qualquer código onde e onde a distância é linear em , então o que você está procurando é chamado de "código assintoticamente bom". Existem muitas construções explícitas desses códigos, e você pode encontrar as básicas nas notas de aula dos cursos sobre a teoria da codificação. Por exemplo, você pode encontrar uma descrição de uma construção clássica na Aula 7 aqui . Outro exemplo de uma construção são os códigos de expansão, que são descritos na Aula 14.$E : \{0,1\}^n \to \{0,1\}^m$$m=O(n)$$m$

Se estiver olhando especificamente para códigos em que a distância entre quaisquer duas palavras de código é perto de , e em particular é superior delimitada por , então as coisas são um pouco mais complicadas. Esses códigos estão intimamente relacionados a objetos chamados " conjuntos tendenciosos ", que foram estudados por um bom tempo no TCS. Você pode encontrar uma construção muito recente desses códigos aqui . As construções mais antigas podem ser encontradas aqui e aqui (apesar de fornecer apenas ).$\frac{m}{2}$$(1+\delta)\cdot \frac{m}{2}$$\epsilon$$m = \rm{poly}(n)$