WikiDer > Lee-Code

EIN Lee-Code ist eine Fehlerkorrektur linearer Code die als Erweiterung der Hamming-Code zu nicht-binären Wörtern. Lee-Codes können in den Fällen verwendet werden, in denen nicht-binäre Signale gesendet oder gespeichert werden.

Definitionen

Lee-Abstand

Für zwei gleich lange Wörter ohne Symbole ${displaystyle {0,1,ldots,q-1}}$ ist der Lee-Abstand definiert. Zwei Wörter ${Anzeigestil x}$ und ${Anzeigestil y}$ von ${displaystyle n}$ Symbole haben den Lee-Abstand:

${displaystyle d_{L}(x,y)=sum _{i=1}^{n}min(|x_{i}-y_{i}|,q-|x_{i}-y_{i}| )}$

Dieses metrisch sieht irgendwie so aus Manhattan-Metrik.

Lee-Atmosphäre

Die Sammlung ${displaystyle F^{n}}$ besteht aus allen Wörtern der Länge ${displaystyle n}$ mit Symbolen aus dem Alphabet ${displaystyle F={0,1,ldots,q-1}}$.

Das Lee-Atmosphäre mit Radius ${displaystyle e}$ um ein Wort ${Anzeigestil x}$ wird gegeben von:

${displaystyle S_{L}(x,e)={yin F^{n}|d_{L}(x,y)leq e}}$

Dies ist die Menge aller Wörter mit Länge ${displaystyle n}$ wessen Lee Abstand zu ${Anzeigestil x}$ überschreitet nicht ${displaystyle e}$ Einheiten.

Lee-Kugeln haben eine geometrische Interpretation. Zum Beispiel werden Wörter der Länge 2 in der Ebene dargestellt durch:

vor dem ${displaystyle e=1}$	vor dem ${Anzeigestil e=2}$

und so weiter. Das Wort ${Anzeigestil x}$ befindet sich in der Mitte der Figur. Die horizontale und vertikale Achse entsprechen den Koordinaten ${displaystyle x_{1}}$ und ${displaystyle x_{2}.}$ Die Worte höchstens in Lee-Distanz ${displaystyle e}$ befinden sich in der Mitte der Quadrate innerhalb der Figur. 13 Wörter haben also einen Abstand von 2 oder weniger von ${Anzeigestil x.}$

In drei Dimensionen (${Anzeigestil n=3}$) werden die Quadrate zu Würfeln, die um einen zentralen Punkt gestapelt sind.

Das Volumen (Anzahl der Wörter) einer Lee-Kugel beträgt:

${displaystyle sum _{i=0}^{min{n,e}}2^{i}{ inom {n}{i}}{ inom {e}{i}}}$ vor dem ${displaystyle qgeq 3}$

Lee-Code

Eine Teilmenge ${displaystyle Csubset F^{n}}$ ist ein e-Fehler Korrektur des Lee-Codes wenn für jedes Paar von Codewörtern ${Anzeigestil x,yin C}$ gilt, dass ihre Lee-Kugeln mit Radius ${displaystyle e}$ unzusammenhängend sein:

${displaystyle S_{L}(x,e)cap S_{L}(y,e)=varnothing für alle x,yin C,xeq y}$

Die Wörter innerhalb der ${displaystyle e}$-Sphäre eines Codewortes aus ${Anzeigestil C}$ Lüge werden von diesem Codewort "verdeckt".

Perfekter Lee-Code

Die Anzahl der Codewörter, d. h. die Anzahl codierbarer Nachrichten, eines e-Fehler korrigierenden Lee-Codes ist so groß wie möglich, wenn die Lee-Sphären der Codewörter eine dichte Packung aufweisen. Ein Lee-Code ist perfekt wann:

${displaystyle igcup _{xin C}S_{L}(x,e)=F^{n}}$

bedeutet die Lee-Kugeln mit Radius ${displaystyle e}$ der Codewörter mit Länge ${displaystyle n}$ das Vektorraum${displaystyle F_{n}}$völlig auffüllen oder Fliesen; sie bilden a Partition dieses Raumes. Mit anderen Worten, jedes Wort von Länge of ${displaystyle n}$ wird durch ein eindeutiges Codewort von . abgedeckt ${Anzeigestil C.}$

Nur wenn solche Fliesen von ${displaystyle F_{n}}$ mit Lee-Kugeln mit Radius ${displaystyle e}$ möglich, existiert ein perfekter Lee-Code, geschrieben als ${displaystyle mathrm {PL} (n,e).}$ Es gibt perfekte Lee-Codes ${Displaystil-Mathematik {PL} (n,1)}$ für jedes ${displaystyle ngeq 1}$ und ${displaystyle mathrm {PL} (2,e)}$ für jedes ${displaystyle egeq 1.}$ Es gibt kein ${displaystyle mathrm {PL} (2,3).}$^[1]

Vermutung von Golomb und Welch

golomb und Welch^[2] formuliert es Verdacht dass es kein perfekt gibt ${displaystyle e}$-fehlerkorrigierende Lee-Codes existieren für ${Anzeigestil n>2}$ und ${Anzeigestil e>1.}$ Es ist im Allgemeinen noch nicht bewiesen, aber es gibt viele Ergebnisse, die den Verdacht bestätigen. Es ist beispielsweise bewiesen, dass es keine perfekten Lee-Codes gibt, wenn ${displaystyle qgeq 2. 1.}$^[3][4] Gravier et al. haben 1998 bewiesen, dass mit Lee-Kugeln des Radius no keine Kachelung des dreidimensionalen Raums möglich ist ${displaystyle e}$ von 2 oder mehr. Die Vermutung von Golomb und Welch beweist das ${Anzeigestil n=3.}$ Die Vermutung wurde anschließend auch für . bewiesen ${Anzeigestil n=4}$ und ${Anzeigestil n=5.}$^[1]