Griesmer vázán - Griesmer bound

V matematika z teorie kódování, Griesmer vázán, pojmenovaný podle Jamese Huga Griesmera, je vázán na délku lineární binární kódy dimenze k a minimální vzdálenost dK dispozici je také velmi podobná verze pro nebinární kódy.

Prohlášení o vazbě

Pro binární lineární kód je Griesmerova vazba:

{displaystyle ngeqslant sum _ {i = 0} ^ {k-1} leftlceil {frac {d} {2 ^ {i}}} ightceil.}

Důkaz

Nechat ${displaystyle N (k, d)}$ označují minimální délku binárního kódu dimenze k a vzdálenost d. Nechat C být takový kód. Chceme to ukázat

{displaystyle N (k, d) geqslant součet _ {i = 0} ^ {k-1} leftlceil {frac {d} {2 ^ {i}}} ightceil.}

Nechat G být maticí generátoru C. Vždy můžeme předpokládat, že první řada G je ve formě r = (1, ..., 1, 0, ..., 0) s hmotností d.

{displaystyle G = {egin {bmatrix} 1 & dots & 1 & 0 & dots & 0 ast & ast & ast && G '& end {bmatrix}}}

Matice ${displaystyle G '}$ generuje kód ${displaystyle C '}$ , kterému se říká zbytkový kód ${displaystyle C.}$ ${displaystyle C '}$ zjevně má rozměr ${displaystyle k '= k-1}$ a délka ${displaystyle n '= N (k, d) -d.}$ ${displaystyle C '}$ má vzdálenost ${displaystyle d ',}$ ale nevíme to. Nechat ${displaystyle uin C '}$ být takový, že ${displaystyle w (u) = d '}$ . Existuje vektor ${displaystyle vin mathbb {F} _ {2} ^ {d}}$ takové, že zřetězení ${displaystyle (v | u) v C.}$ Pak ${displaystyle w (v) + w (u) = w (v | u) geqslant d.}$ Na druhou stranu také ${displaystyle (v | u) + rin C,}$ od té doby ${displaystyle rin C}$ a ${displaystyle C}$ je lineární: ${displaystyle w ((v | u) + r) geqslant d.}$ Ale

{displaystyle w ((v | u) + r) = w (((1, cdots, 1) + v) | u) = d-w (v) + w (u),}

tak se to stane ${displaystyle d-w (v) + w (u) geqslant d}$ . Sečtením to s ${displaystyle w (v) + w (u) geqslant d,}$ získáváme ${displaystyle d + 2w (u) geqslant 2d}$ . Ale ${displaystyle w (u) = d ',}$ takže máme ${displaystyle d'geqslant {frac {d} {2}}.}$ Z toho vyplývá