Erro booleano ao corrigir o código sobre

Existe alguma construção conhecida de um erro linear para corrigir o código (com parâmetros razoáveis), de modo que, quando dado um vetor booleano , ele também retorna um vetor booleano whp? (embora esteja acima de ) $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ $v\in \{0,1\}^n$ $\mathbb{F}_q$

(ou seja, $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$ , em que a probabilidade é assumida ao escolher uniformemente $v\in \{0,1\}^n$ e $\epsilon$ é arbitrariamente pequeno)

Caso contrário, e se relaxarmos a condição para

Pr [{E C C}_{i} (v) \in {0, 1}] > 1 - ϵ

$\Pr[\mathsf{ECC}_i(v) \in \{0,1\}]> 1-\epsilon$ Onde

{E C C}_{i}

$\mathsf{ECC}_i$ retorna a

i

$i$ ésima coordenada de

E C C

$\mathsf{ECC}$ ,

ϵ

$\epsilon$ é arbitrariamente pequeno, e a probabilidade é assumida ao escolher uniformemente

v \in {0, 1}^{n}

$v\in \{0,1\}^n$ escolher uniformemente uma coordenada

i \in [m]

$i\in[m]$ .

Por curiosidade, você tem alguma aplicação em mente?

Tsuyoshi Ito

Sim, na verdade, tenho alguns aplicativos para um código de correção de erros com essa propriedade. No entanto, acho inviável explicar dentro do escopo de um comentário. Você pode entrar em contato comigo por e-mail se estiver interessado.

Obrigado pela resposta. Se não se encaixa em um comentário, provavelmente não tenho tempo para entender a coisa toda, então deixarei como está. Obrigado!

Tsuyoshi Ito

Respostas:

Sim. Por exemplo, um código Reed-Solomon contém um código BCH, que é um código linear binário, como um subcódigo. Estes são chamados subcódigo-subcampo.

Mahdi Cheraghchi
fonte

Isso significa que, dado um código Reed-Solomon (linear em F_q), a probabilidade de o código retornar uma palavra de código binária, dada uma entrada binária, é 1? Você pode me indicar um artigo / pesquisa em que eu possa ler sobre essa propriedade com mais detalhes? Eu sou um pouco novo em teoria de codificação. Obrigado!

A melhor referência para ler sobre códigos binários de BCH é os livros de texto clássicos "A teoria dos códigos de correção de erros", de MacWilliams e Sloane, e também "Introdução à teoria de codificação" de van Lint.

Mahdi Cheraghchi

@ TomGur: Não tenho certeza de que os códigos BCH atendam aos seus requisitos. Até certo ponto, a resposta depende de quanto esforço computacional você deseja que o decodificador coloque na tarefa. Os decodificadores "prontos para uso" são decodificadores de distância limitada e corrigem apenas até o limite único de decodibilidade (<metade da distância mínima). Para códigos BCH, uma fração não desprezível do espaço binário está fora da faixa e ocorrerá um erro no decodificador. Apenas ter um código não é suficiente, a menos que você especifique o algoritmo de decodificação (nem todos os ECCs possuem um conhecido eficiente).

Jyrki Lahtonen