Boolescher Fehler beim Korrigieren des Codes über

Gibt es eine bekannte Konstruktion eines linearen Fehlerkorrekturcodes (mit vernünftigen Parametern), so dass bei Angabe eines Booleschen Vektors gibt es auch einen Booleschen Vektor zurück whp? (obwohl es vorbei ist ) $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ $v\in \{0,1\}^n$ $\mathbb{F}_q$

( , wobei die Wahrscheinlichkeit übernommen wird, indem einheitlich gewählt wird und ist beliebig klein) $\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon$ $v\in \{0,1\}^n$ $\epsilon$

Wenn nicht, was ist, wenn wir die Bedingung auf

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

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

{E C C}_{i}

$\mathsf{ECC}_i$ die

i

$i$ -te Koordinate zurückgibt von

E C C

$\mathsf{ECC}$ ist

ϵ

$\epsilon$ beliebig klein, und die Wahrscheinlichkeit wird sowohl für die einheitliche Auswahl von

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

$v\in \{0,1\}^n$ als auch für die einheitliche Auswahl einer Koordinate

i \in [m]

$i\in[m]$ .

Haben Sie aus Neugier irgendwelche Anwendungen im Sinn?

Tsuyoshi Ito

Ja, ich habe tatsächlich einige Anwendungen für einen Fehlerkorrekturcode mit einer solchen Eigenschaft. Ich halte es jedoch für unmöglich, dies im Rahmen eines Kommentars zu erklären. Sie können mich per E-Mail kontaktieren, wenn Sie interessiert sind.

Danke für die Antwort. Wenn es nicht in einen Kommentar passt, habe ich wahrscheinlich sowieso keine Zeit, das Ganze zu verstehen, also werde ich es so lassen, wie es ist. Vielen Dank!

Tsuyoshi Ito

Antworten:

Ja. Beispielsweise enthält ein Reed-Solomon-Code einen BCH-Code, der ein binärer linearer Code ist, als Subcode. Diese werden Subfeld-Subcodes genannt.

MCH
quelle

Bedeutet dies, dass bei einem (linear in F_q) Reed-Solomon-Code die Wahrscheinlichkeit, dass der Code bei einer binären Eingabe ein binäres Codewort zurückgibt, 1 beträgt? Können Sie mich bitte auf ein Papier / eine Umfrage verweisen, in der ich mehr über diese Immobilie lesen kann? Ich bin ein bisschen neu in der Codierungstheorie. Vielen Dank!

Die beste Referenz zum Lesen über binäre BCH-Codes sind die klassischen Lehrbücher "The Theory of Error Correcting Codes" von MacWilliams und Sloane sowie "Introduction to Coding Theory" von van Lint.

MCH

@ TomGur: Ich bin nicht sicher, ob BCH-Codes Ihren Anforderungen entsprechen. In gewissem Maße hängt die Antwort davon ab, wie viel Rechenaufwand der Decoder für die Aufgabe aufwenden soll. Die "Standard" -Decoder sind Decoder mit begrenztem Abstand und korrigieren nur bis zur eindeutigen Decodierbarkeitsgrenze (<die Hälfte des Mindestabstands). Bei BCH-Codes liegt ein nicht zu vernachlässigender Teil des Binärraums außerhalb des Bereichs, und es entsteht ein Decoderfehler. Nur einen Code zu haben, reicht nicht aus, es sei denn, Sie spezifizieren den Decodierungsalgorithmus (nicht alle ECCs haben einen effizienten bekannten).

Jyrki Lahtonen