Błąd logiczny korygujący kod w

Czy istnieje znana konstrukcja kodu korygującego błędy liniowe (z rozsądnymi parametrami), na przykład gdy podano logiczny wektor zwraca również wartość logiczną wektora logicznego? (chociaż to koniec ) $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ $v\in \{0,1\}^n$ $\mathbb{F}_q$

(to znaczy $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$ , gdzie prawdopodobieństwo jest przejmowane równomiernie wybierając $v\in \{0,1\}^n$ , a $\epsilon$ jest dowolnie mały)

Jeśli nie, co jeśli złagodzimy warunek do

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

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

{E C C}_{i}

$\mathsf{ECC}_i$ zwraca

i

$i$ -tą współrzędną z

E C C

$\mathsf{ECC}$ ,

ϵ

$\epsilon$ jest arbitralnie mały, a prawdopodobieństwo jest przejęte zarówno przez jednolite wybranie

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

$v\in \{0,1\}^n$ i jednolite wybranie współrzędnej

i \in [m]

$i\in[m]$ .

co.combinatorics linear-algebra coding-theory

Z ciekawości masz na myśli jakieś aplikacje?

— Tsuyoshi Ito

Tak, faktycznie mam kilka wniosków o kod korygujący błędy o takiej właściwości. Uważam jednak, że wyjaśnienie w ramach komentarza jest niewykonalne. Jeśli jesteś zainteresowany, możesz skontaktować się ze mną pocztą.

Dziękuję za odpowiedź. Jeśli nie pasuje do komentarza, prawdopodobnie i tak nie mam czasu na zrozumienie całej sprawy, więc zostawię ją taką, jaka jest. Dzięki!

— Tsuyoshi Ito

Tak. Na przykład kod Reeda-Solomona zawiera kod BCH, który jest binarnym kodem liniowym, jako subkod. Są to tak zwane subkody-pola.

— Mahdi Cheraghchi
źródło

Czy to oznacza, że biorąc pod uwagę (liniowy w F_q) kod Reeda-Solomona, prawdopodobieństwo, że kod zwróci binarne słowo kodowe, przy danych binarnych, wynosi 1? Czy możesz skierować mnie do jakiejś pracy / ankiety, w której mogę przeczytać bardziej szczegółowo o tej nieruchomości? Jestem trochę nowy w teorii kodowania. Dzięki!

Najlepszym odniesieniem do binarnych kodów BCH są klasyczne podręczniki „Theory of Error Correctioning Codes” MacWilliamsa i Sloane'a, a także „Wprowadzenie do teorii kodowania” van Linta.

— Mahdi Cheraghchi

@TomGur: Nie jestem pewien, czy kody BCH spełniają twoje wymagania. Odpowiedź do pewnego stopnia zależy od tego, ile wysiłku obliczeniowego chcesz, aby dekoder włożył w to zadanie. Dekodery „z półki” to dekodery o ograniczonej odległości, które korygują tylko do unikalnego limitu dekodowalności (<połowa minimalnej odległości). W przypadku kodów BCH nieistotna część przestrzeni binarnej jest poza zakresem, co spowoduje błąd dekodera. Sam kod nie wystarczy, chyba że określisz algorytm dekodowania (nie wszystkie ECC mają znane znane).

— Jyrki Lahtonen,