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]$ .

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

Odpowiedzi:

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,