Hamming grænse

I kodningsteori definerer Hamming-grænsen grænserne for mulige værdier for parametrene for en vilkårlig blokkode . Også kendt som den sfæriske pakningsgrænse . Koder, der når Hamming-grænsen, kaldes perfekte eller tætpakkede koder .

Ordlyd

Lad betegne den maksimalt mulige kardinalitet af -ær bloklængdekode og minimumafstand ( -ær bloklængdekode er en delmængde af ord med alfabet bestående af elementer). $A_q(n,\;d)$ $q$ $C$ $n$ $d$ $q$ $n$ $\mathcal{A}_q^n$ $\mathcal{A}_q$ $q$

Derefter

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

hvor

t=\venstre\lgulv\frac{d-1}{2}\højre\rgulv.

Bevis

Per definition , hvis transmissionen af kodeordet skete før fejl, vil vi ved hjælp af afkodning begrænset af minimumsafstanden være i stand til nøjagtigt at genkende det transmitterede kodeord . $d$ $t=\venstre\lgulv\frac{d-1}{2}\højre\rgulv$

For et givet kodeord skal du overveje en kugle med radius omkring . På grund af det faktum, at denne kode er i stand til at rette fejl, skærer ingen sfære med nogen anden og indeholder $c\in C$ $t$ $c$ $t=\venstre\lgulv\frac{d-1}{2}\højre\rgulv$

\sum_{k=0}^t \binom{n}{k}(q-1)^k

ord, da vi kan tillade (eller færre) tegn (af alle tegn i et ord) at antage en af de mulige værdier, der er forskellig fra værdien af det tilsvarende tegn i et givet ord (husk at selve koden er -ic ).

t

n

(q-1)

q

Lad betegne antallet af ord i . Ved at samle sfærer omkring alle kodeord bemærker vi, at det resulterende sæt er indeholdt i . Da sfærerne er usammenhængende, kan vi summere elementerne i hver af dem og få $M$ $C$ $\mathcal{A}_q^n$

M\times\sum_{k=0}^t\binom{n}{k}(q-1)^k\leqslant|\mathcal{A}_q^n|=q^n,

hvorfra for enhver kode $C$

M\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

og derfor,

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k}.

Perfekte koder

Koder, der når Hamming-grænsen, kaldes perfekte koder . Følgende typer af perfekte koder er blevet opdaget: Hamming- koder og Golay-koder . Der er også trivielle perfekte koder: ulige længde binære koder, koder med ét kodeord og koder, der inkluderer hele sættet . $F_q^n$

Det blev bevist af Titvainen og Van Lint, at enhver ikke-triviel perfekt kode har parametrene for en Hamming -kode eller en Golay-kode [1] [2] .

Noter

↑ Tietavainen A., Perko A. Der er ingen ukendte perfekte binære koder. Annales Universitatis Turkuensis . Ser. A, I 148, 3-10[6], 1971.
↑ Lint van JH Ikke-eksistenssætninger for perfekte fejlkorrigerende koder. — Computere i algebra og talteori . — Bd. IV [6], 1971.

Litteratur