Kód opravující chyby - Rank error-correcting code - Wikipedia

v teorie kódování, hodnostní kódy (také zvaný Kódy gabidulinu) nejsou binární^[1] lineární kódy opravující chyby přes ne Hamming ale hodnost metrický. Popsali systematický způsob vytváření kódů, které dokázaly detekovat a opravit více náhodný hodnost chyby. Přidáním redundance s kódováním k-symbolové slovo pro a n-symbolové slovo, kód pořadí může opravit jakékoli chyby v pořadí až t = ⌊ (d - 1) / 2 ⌋, kde d je vzdálenost kódu. Jako mazací kód, může opravit až d - 1 známá výmaz.

A hodnostní kód je algebraický lineární kód přes konečné pole ${ displaystyle GF (q ^ {N})}$ podobný Reed-Solomonův kód.

Hodnost vektoru skončila ${ displaystyle GF (q ^ {N})}$ je maximální počet lineárně nezávislých komponent ${ displaystyle GF (q)}$. Vzdálenost mezi dvěma vektory ${ displaystyle GF (q ^ {N})}$ je hodnost rozdílu těchto vektorů.

Kód pořadí opravuje všechny chyby, přičemž pořadí vektoru chyb není větší nežt.

Hodnocení metriky

Nechat ${ displaystyle X ^ {n}}$ být n-dimenzionální vektorový prostor nad konečné pole ${ displaystyle GF left ({q ^ {N}} right)}$, kde ${ displaystyle q}$ je moc prvočísla a ${ displaystyle N}$ je kladné celé číslo. Nechat ${ displaystyle left (u_ {1}, u_ {2}, dots, u_ {N} right)}$, s ${ displaystyle u_ {i} v GF (q ^ {N})}$, být základnou ${ displaystyle GF left ({q ^ {N}} right)}$ jako vektorový prostor nad polem ${ displaystyle GF left ({q} right)}$.

Každý prvek ${ displaystyle x_ {i} v GF vlevo ({q ^ {N}} vpravo)}$ lze reprezentovat jako ${ displaystyle x_ {i} = a_ {1i} u_ {1} + a_ {2i} u_ {2} + tečky + a_ {Ni} u_ {N}}$. Proto každý vektor ${ displaystyle { vec {x}} = vlevo ({x_ {1}, x_ {2}, tečky, x_ {n}} vpravo)}$ přes ${ displaystyle GF left ({q ^ {N}} right)}$ lze zapsat jako matici:

${ displaystyle { vec {x}} = vlevo | { začátek {pole} {* {20} c} a_ {1,1} & a_ {1,2} & ldots & a_ {1, n} a_ {2,1} & a_ {2,2} & ldots & a_ {2, n} ldots & ldots & ldots & ldots a_ {N, 1} & a_ {N, 2} & ldots & a_ {N, n} end {pole}} doprava |}$

Pořadí vektoru ${ displaystyle { vec {x}}}$ přes pole ${ displaystyle GF left ({q ^ {N}} right)}$ je hodnost odpovídající matice ${ displaystyle A left ({ vec {x}} right)}$ přes pole ${ displaystyle GF left ({q} right)}$ označeno ${ displaystyle r left ({{ vec {x}}; q} right)}$.

Sada všech vektorů ${ displaystyle { vec {x}}}$ je prostor ${ displaystyle X ^ {n} = A_ {N} ^ {n}}$. Mapa ${ displaystyle { vec {x}} to r doleva ({ vec {x}}; q doprava)}$) definuje normu nad ${ displaystyle X ^ {n}}$ a a hodnostní metrika:

${ displaystyle d left ({{ vec {x}}; { vec {y}}} right) = r left ({{ vec {x}} - { vec {y}}; q }že jo)}$

Hodnostní kód

Sada ${ displaystyle {x_ {1}, x_ {2}, tečky, x_ {n} }}$ vektorů z ${ displaystyle X ^ {n}}$ se nazývá kód s kódovou vzdáleností ${ displaystyle d = min d left (x_ {i}, x_ {j} right)}$. Pokud sada také tvoří a k-rozměrný podprostor ${ displaystyle X ^ {n}}$, pak se nazývá lineární (n, k) -kód se vzdáleností ${ displaystyle d}$. Takový metrický kód s lineárním hodnocením vždy vyhovuje Singletonovi ${ displaystyle d leq n-k + 1}$.

Generování matice

Existuje několik známých konstrukcí hodnostních kódů, které jsou maximální hodnost vzdálenost (nebo MRD) kódy s d = n − k + 1. Nejjednodušší z nich je konstruován jako (zobecněný) gabidulinový kód, objevil ho nejprve Delsarte (který jej nazval Singletonský systém) a později (Kshevetskiy a) Gabidulin.

Pojďme definovat sílu Frobenius ${ displaystyle [i]}$ prvku ${ displaystyle x v GF (q ^ {N})}$ tak jako

${ displaystyle x ^ {[i]} = x ^ {q ^ {i mod N}}. ,}$

Pak každý vektor ${ displaystyle { vec {g}} = (g_ {1}, g_ {2}, tečky, g_ {n}), ~ g_ {i} v GF (q ^ {N}), ~ n leq N}$, lineárně nezávislé přes ${ displaystyle GF (q)}$, definuje generující matici MRD (n, k, d = n − k + 1) -kód.

${ displaystyle G = left | { begin {array} {* {20} c} g_ {1} & g_ {2} & dots & g_ {n} g_ {1} ^ {[m]} & g_ {2} ^ {[m]} & dots & g_ {n} ^ {[m]} g_ {1} ^ {[2m]} & g_ {2} ^ {[2m]} & dots & g_ {n } ^ {[2m]} tečky & tečky & tečky & tečky g_ {1} ^ {[km]} & g_ {2} ^ {[km]} & dots & g_ {n} ^ {[km]} end {array}} right |,}$

kde ${ displaystyle gcd (m, N) = 1}$.

Aplikace

Existuje několik návrhů kryptosystémů veřejného klíče založených na hodnostních kódech. Většina z nich se však ukázala jako nejistá (viz např. Journal of Cryptology, duben 2008^[2]).

Hodnostní kódy jsou také užitečné pro opravu chyb a mazání v síťové kódování.

Viz také

• Lineární kód
• Reed – Solomonova korekce chyb
• Algoritmus Berlekamp – Massey
• Síťové kódování

Poznámky

Reference

• Gabidulin, Ernst M. (1985), "Teorie kódů s maximální vzdáleností", Problémy přenosu informací, 21 (1): 1–12
• Kshevetskiy, Alexander; Gabidulin, Ernst M. (4. – 9. Září 2005), „Nová konstrukce hodnostních kódů“, Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005: 2105–2108, doi:10.1109 / ISIT.2005.1523717, ISBN  978-0-7803-9151-2
• Gabidulin, Ernst M .; Pilipchuk, Nina I. (29. června - 4. července 2003), „Nová metoda opravy výmazu podle hodnostních kódů“, Proceedings of the IEEE 2003 International Symposium on Information Theory: 423, doi:10.1109 / ISIT.2003.1228440, ISBN  978-0-7803-7728-8

externí odkazy

• Implementace MATLAB kodeku Rank – metric