Johnson vázán - Johnson bound

V aplikované matematice je Johnson vázán (pojmenoval podle Selmer Martin Johnson ) je limit velikosti kódy opravující chyby, jak se používá v teorie kódování pro přenos dat nebo komunikace.

Definice

Nechat ${displaystyle C}$ být q-ary kód délky ${displaystyle n}$ , tj. podmnožina ${displaystyle mathbb {F} _ {q} ^ {n}}$ . Nechat ${displaystyle d}$ být minimální vzdálenost ${displaystyle C}$ , tj.

{displaystyle d = min _ {x, yin C, xeq y} d (x, y),}

kde ${displaystyle d (x, y)}$ je Hammingova vzdálenost mezi ${displaystyle x}$ a ${displaystyle y}$ .

Nechat ${displaystyle C_ {q} (n, d)}$ být množinou všeho q-ary kódy s délkou ${displaystyle n}$ a minimální vzdálenost ${displaystyle d}$ a nechte ${displaystyle C_ {q} (n, d, w)}$ označit sadu kódů v ${displaystyle C_ {q} (n, d)}$ tak, že každý prvek má přesně ${displaystyle w}$ nenulové položky.

Označit podle ${displaystyle | C |}$ počet prvků v ${displaystyle C}$ . Poté definujeme ${displaystyle A_ {q} (n, d)}$ být největší velikostí kódu s délkou ${displaystyle n}$ a minimální vzdálenost ${displaystyle d}$ :

{displaystyle A_ {q} (n, d) = max _ {Cin C_ {q} (n, d)} | C |.}

Podobně definujeme ${displaystyle A_ {q} (n, d, w)}$ být největší velikostí kódu v ${displaystyle C_ {q} (n, d, w)}$ :

{displaystyle A_ {q} (n, d, w) = max _ {Cin C_ {q} (n, d, w)} | C |.}

Věta 1 (Johnson směřoval k ${displaystyle A_ {q} (n, d)}$ ):

Li ${displaystyle d = 2t + 1}$ ,

{displaystyle A_ {q} (n, d) leq {frac {q ^ {n}} {sum _ {i = 0} ^ {t} {n zvolte i} (q-1) ^ {i} + {frac {{n zvolit t + 1} (q-1) ^ {t + 1} - {d zvolit t} A_ {q} (n, d, d)} {A_ {q} (n, d, t + 1 )}}}}.}

Li ${displaystyle d = 2t}$ ,

{displaystyle A_ {q} (n, d) leq {frac {q ^ {n}} {sum _ {i = 0} ^ {t} {n zvolte i} (q-1) ^ {i} + {frac {{n vyberte t + 1} (q-1) ^ {t + 1}} {A_ {q} (n, d, t + 1)}}}}}

Věta 2 (Johnson směřoval k ${displaystyle A_ {q} (n, d, w)}$ ):

(i) Li ${displaystyle d> 2 t,}$

{displaystyle A_ {q} (n, d, w) = 1.}

ii) Li ${displaystyle dleq 2w}$ , poté definujte proměnnou ${displaystyle e}$ jak následuje. Li ${displaystyle d}$ je sudé, pak definujte ${displaystyle e}$ prostřednictvím vztahu ${displaystyle d = 2e}$ ; -li ${displaystyle d}$ je liché, definujte ${displaystyle e}$ prostřednictvím vztahu ${displaystyle d = 2e-1}$ . Nechat ${displaystyle q ^ {*} = q-1}$ . Pak,

{displaystyle A_ {q} (n, d, w) leq leftlfloor {frac {nq ^ {*}} {w}} leftlfloor {frac {(n-1) q ^ {*}} {w-1}} leftlfloor cdots leftlfloor {frac {(n-w + e) ​​q ^ {*}} {e}} ightfloor cdots ightfloor ightfloor ightfloor}

kde ${displaystyle lfloor ~~ floor}$ je funkce podlahy.

Poznámka: Zapojením meze věty 2 do meze věty 1 se vytvoří numerická horní mez ${displaystyle A_ {q} (n, d)}$ .

Viz také

Reference

Johnson, Selmer Martin (Duben 1962). Msgstr "Nová horní hranice pro kódy opravující chyby". Transakce IRE na teorii informací: 203–207.
Huffman, William Cary; Pless, Vera S. (2003). Základy kódů pro opravu chyb. Cambridge University Press. ISBN 978-0-521-78280-7.