Lineær kode - Linear code

I kodeteori er en lineær kode en feilkorrigerende kode som enhver lineær kombinasjon av kodeord også er et kodeord for. Lineære koder er tradisjonelt delt inn i blokkoder og konvolusjonskoder , selv om turbokoder kan sees på som en hybrid av disse to typene. Lineære koder gir mulighet for mer effektive kodings- og dekodingsalgoritmer enn andre koder (jf . Syndromdekoding ).

Lineære koder brukes i feilkorrigering fremover og brukes i metoder for overføring av symboler (f.eks. Biter ) på en kommunikasjonskanal, slik at hvis feil oppstår i kommunikasjonen, kan noen feil bli korrigert eller oppdaget av mottakeren av en meldingsblokk. Kodeordene i en lineær blokkode er symbolblokker som er kodet med flere symboler enn den opprinnelige verdien som skal sendes. En lineær lengdekode n overfører blokker som inneholder n symboler. For eksempel er [7,4,3] Hamming-koden en lineær binær kode som representerer 4-biters meldinger ved hjelp av 7-biters kodeord. To forskjellige kodeord er forskjellige i minst tre biter. Som en konsekvens kan opptil to feil per kodeord oppdages mens en enkelt feil kan korrigeres. Denne koden inneholder 2 ⁴ = 16 kodeord.

Definisjon og parametere

En lineær kode med lengde n og rang k er et lineært underrom C med dimensjon k i vektorrommet hvor det endelige feltet med q elementer er. En slik kode kalles en q -ary -kode. Hvis q = 2 eller q = 3, beskrives koden som henholdsvis en binær kode eller en ternær kode . Vektorene i C kalles kodeord . Den størrelse av en kode er antall kodeord og er lik q ^k . ${\ displaystyle \ mathbb {F} _ {q}^{n}}$ ${\ displaystyle \ mathbb {F} _ {q}}$

Den vekt av et kodeord er antallet av dens elementer som er forskjellig fra null, og avstanden mellom to kodeord er den Hamming-avstand mellom dem, det vil si antallet av elementer i som adskiller de. Avstanden d til den lineære koden er minimumsvekten til dens nullkodeord, eller tilsvarende minimumsavstanden mellom forskjellige kodeord. En lineær kode med lengde n , dimensjon k og avstand d kalles en [ n , k , d ] kode.

Vi ønsker å gi standardgrunnlaget fordi hver koordinat representerer en "bit" som sendes over en "støyende kanal" med en liten sannsynlighet for overføringsfeil (en binær symmetrisk kanal ). Hvis et annet grunnlag brukes, kan denne modellen ikke brukes, og Hamming -metrikken måler ikke antall feil ved overføring, slik vi vil ha den. ${\ displaystyle \ mathbb {F} _ {q}^{n}}$

Generator og sjekk matriser

Som et lineært delrom av , kan hele koden C (som kan være veldig stor) bli representert som spennet til et sett med kodeord (kjent som et grunnlag i lineær algebra ). Disse basis kodeord blir ofte samlet i radene i en matrise G kjent som en genererende matrise for koden C . Når G har blokkmatriseformen , hvor betegner identitetsmatrisen og P er en matrise, så sier vi at G er i standardform . ${\ displaystyle \ mathbb {F} _ {q}^{n}}$ ${\ displaystyle k}$ ${\ displaystyle {\ boldsymbol {G}} = [I_ {k} | P]}$ ${\ displaystyle I_ {k}}$ ${\ displaystyle k \ ganger k}$ ${\ displaystyle k \ times (nk)}$

En matrise H som representerer en lineær funksjon hvis kjerne er C kalles en kontrollmatrise for C (eller noen ganger en paritetskontrollmatrise). På ekvivalent måte, H er en matrise hvis nullrommet er C . Hvis C er en kode med en genererende matrise G i standardform , så er en sjekkmatrise for C. Koden generert av H kalles den dobbelte koden til C. Det kan verifiseres at G er en matrise, mens H er en matrise. ${\ displaystyle \ phi: \ mathbb {F} _ {q}^{n} \ to \ mathbb {F} _ {q}^{nk}}$ ${\ displaystyle {\ boldsymbol {G}} = [I_ {k} | P]}$ ${\ displaystyle {\ boldsymbol {H}} = [-P^{T} | I_ {nk}]}$ ${\ displaystyle k \ ganger n}$ ${\ displaystyle (nk) \ ganger n}$

Linearitet garanterer at den minste Hamming -avstanden d mellom et kodeord c ₀ og noen av de andre kodeordene c ≠ c ₀ er uavhengig av c ₀ . Dette følger av egenskapen at differansen c - c ₀ av to kodeord i C også er et kodeord (dvs. et element i underrommet C ), og egenskapen at d ( c , c ₀ ) = d ( c - c ₀ , 0). Disse egenskapene antyder det

{\ displaystyle \ min _ {c \ i C, \ c \ neq c_ {0}} d (c, c_ {0}) = \ min _ {c \ i C, \ c \ neq c_ {0}} d (c-c_ {0}, 0) = \ min _ {c \ i C, \ c \ neq 0} d (c, 0) = d.}

Med andre ord, for å finne ut minimumsavstanden mellom kodeordene til en lineær kode, trenger man bare å se på kodeordene som ikke er null. Det ikke-null kodeordet med den minste vekten har da minimumsavstanden til nullkodeordet, og bestemmer dermed minimumsavstanden til koden.

Avstanden d fra en lineær kode C også er lik det minimale antall lineært avhengige kolonnene i matrisen sjekken H .

Bevis: Fordi , som tilsvarer , hvor er kolonnen med . Fjern elementene med , de med er lineært avhengige. Derfor er minst det minste antallet lineært avhengige kolonner. På en annen side, tenk på minimumssettet av lineært avhengige kolonner hvor er kolonneindekssettet. . Vurder nå vektoren slik at if . Merk fordi . Derfor har vi , som er det minste antallet lineært avhengige kolonner i . Den påståtte eiendommen er derfor bevist. ${\ displaystyle {\ boldsymbol {H}} \ cdot {\ boldsymbol {c}}^{T} = {\ boldsymbol {0}}}$ ${\ displaystyle \ sum _ {i = 1}^{n} (c_ {i} \ cdot {\ boldsymbol {H_ {i}}}) = {\ boldsymbol {0}}}$ ${\ displaystyle {\ boldsymbol {H_ {i}}}}$ ${\ displaystyle i^{th}}$ ${\ displaystyle {\ boldsymbol {H}}}$ ${\ displaystyle c_ {i} = 0}$ ${\ displaystyle {\ boldsymbol {H_ {i}}}}$ ${\ displaystyle c_ {i} \ neq 0}$ ${\ displaystyle d}$ ${\ displaystyle \ {{\ boldsymbol {H_ {j}}} | j \ i S \}}$ ${\ displaystyle S}$ ${\ displaystyle \ sum _ {i = 1}^{n} (c_ {i} \ cdot {\ boldsymbol {H_ {i}}}) = \ sum _ {j \ i S} (c_ {j} \ cdot {\ boldsymbol {H_ {j}}})+\ sum _ {j \ notin S} (c_ {j} \ cdot {\ boldsymbol {H_ {j}}}) = {\ boldsymbol {0}}}$ ${\ displaystyle {\ boldsymbol {c '}}}$ ${\ displaystyle c_ {j} '= 0}$ ${\ displaystyle j \ notin S}$ ${\ displaystyle {\ boldsymbol {c '}} \ i C}$ ${\ displaystyle {\ boldsymbol {H}} \ cdot {\ boldsymbol {c '}}^{T} = {\ boldsymbol {0}}}$ ${\ displaystyle d \ leq wt ({\ boldsymbol {c '}})}$ ${\ displaystyle {\ boldsymbol {H}}}$

Eksempel: Hamming -koder

Som den første klassen av lineære koder utviklet for feilkorrigeringsformål, har Hamming -koder blitt mye brukt i digitale kommunikasjonssystemer. For ethvert positivt heltall finnes det en Hamming -kode. Siden kan denne Hamming-koden rette en 1-biters feil. ${\ displaystyle r \ geq 2}$ ${\ displaystyle [2^{r} -1,2^{r} -r-1,3] _ {2}}$ ${\ displaystyle d = 3}$

Eksempel: Den lineære blokkoden med følgende generatormatrise og paritetskontrollmatrise er en Hamming -kode. ${\ displaystyle [7,4,3] _ {2}}$

{\ displaystyle {\ boldsymbol {G}} = {\ begin {pmatrix} 1 \ 0 \ 0 \ 0 \ 1 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \ 0 \ 1 \ 1 \\ 0 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \\ 0 \ 0 \ 0 \ 1 \ 1 \ 0 \ 1 \ ende {pmatrix}},}

{\ displaystyle {\ boldsymbol {H}} = {\ begin {pmatrix} 1 \ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \\ 1 \ 1 \ 1 \ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \ 1 \ ende {pmatrix}}}

Eksempel: Hadamard -koder

Hadamard -koden er en lineær kode og kan korrigere mange feil. Hadamard -kode kan konstrueres kolonne for kolonne: kolonnen er bitene i den binære representasjonen av heltall , som vist i følgende eksempel. Hadamard -koden har minimum avstand og kan derfor rette feil. ${\ displaystyle [2^{r}, r, 2^{r-1}] _ {2}}$ ${\ displaystyle i^{th}}$ ${\ displaystyle i}$ ${\ displaystyle 2^{r-1}}$ ${\ displaystyle 2^{r-2} -1}$

Eksempel: Den lineære blokk-kode med den følgende generatormatrise er en Hadamard-kode: . ${\ displaystyle [8,3,4] _ {2}}$ ${\ displaystyle {\ boldsymbol {G}} _ {Had} = {\ begin {pmatrix} 0 \ 0 \ 0 \ 0 \ 1 \ 1 \ 1 \ 1 \\ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \ 1 \ 1 \\ 0 \ 1 \ 0 \ 1 \ 0 \ 1 \ 0 \ 1 \ ende {pmatrix}}}$

Hadamard -koden er et spesielt tilfelle av Reed - Muller -koden . Hvis vi tar den første kolonnen (alle-null-kolonnen) ut fra , får vi simplex-kode , som er den dobbelte koden til Hamming-koden. ${\ displaystyle {\ boldsymbol {G}} _ {Had}}$ ${\ displaystyle [7,3,4] _ {2}}$

Nærmeste nabo -algoritme

Parameteren d er nært knyttet til feilkorrigerende evne til koden. Følgende konstruksjon/algoritme illustrerer dette (kalt avkodingsalgoritmen for nærmeste nabo):

Inngang: En mottatt vektor v i . ${\ displaystyle \ mathbb {F} _ {q}^{n}}$

Utgang: et kodeord i nærmest , om noen. ${\ displaystyle w}$ ${\ displaystyle C}$ ${\ displaystyle v}$

Begynn med , gjenta de følgende to trinnene. ${\ displaystyle t = 0}$
Tell elementene i ballen med (Hamming) radius rundt det mottatte ordet , betegnet . ${\ displaystyle t}$ $t$ ${\ displaystyle v}$ $v$ ${\ displaystyle B_ {t} (v)}$ ${\ displaystyle B_ {t} (v)}$
- For hver inn , sjekk om du er inne . Returner i så fall som løsningen. ${\ displaystyle w}$ ${\ displaystyle B_ {t} (v)}$ ${\ displaystyle w}$ ${\ displaystyle C}$ ${\ displaystyle w}$
Økning . Mislykkes bare når oppregningen er fullført og det ikke er funnet noen løsning. ${\ displaystyle t}$ ${\ displaystyle t> (d-1)/2}$

Vi sier at en lineær er -feilkorrigering hvis det er høyst ett kodeord i , for hvert in . ${\ displaystyle C}$ ${\ displaystyle t}$ ${\ displaystyle B_ {t} (v)}$ ${\ displaystyle v}$ ${\ displaystyle \ mathbb {F} _ {q}^{n}}$

Populær notasjon

Koder generelt er ofte betegnet med bokstaven C , og en kode med lengde n og av rang k (dvs. å ha k kodeord i grunnlaget og k rader i generasjonsmatrisen ) blir generelt referert til som en ( n , k ) kode. Lineære blokkoder betegnes ofte som [ n , k , d ] koder, der d refererer til koden minste Hamming -avstand mellom to kodeord.

( Notasjonen [ n , k , d ] bør ikke forveksles med ( n , M , d ) notasjon som brukes for å betegne en ikke-lineær kode med lengde n , størrelse M (dvs. å ha M kodeord) og minimum Hamming avstand d .)

Singleton bundet

Lemma ( bundet Singleton ): Hver lineær [n, k, d] kode C tilfredsstiller . ${\ displaystyle k+d \ leq n+1}$

En kode C hvis parametere tilfredsstiller k+d = n+1 kalles maksimal distanseskillbar eller MDS . Slike koder, når de eksisterer, er på en eller annen måte best mulig.

Hvis C ₁ og C ₂ er to lengdekoder n og hvis det er en permutasjon p i den symmetriske gruppen S _n som (c ₁ , ..., c _n ) i C ₁ hvis og bare hvis (c _{p (1 )} , ..., c _{p (n)} ) i C ₂ , da sier vi at C ₁ og C ₂ er permutasjonsekvivalent . I mer generelle, hvis det er en monomial matrise som sender C ₁ isomorphically til C ₂ da vi si C ₁ og C- ₂ er tilsvarende . ${\ displaystyle n \ ganger n}$ ${\ displaystyle M \ colon \ mathbb {F} _ {q}^{n} \ to \ mathbb {F} _ {q}^{n}}$

Lemma : Enhver lineær kode er permutasjon ekvivalent med en kode som er i standardform.

Bonisolis teorem

En kode er definert som like langt hvis og bare hvis det eksisterer en konstant d slik at avstanden mellom to av kodens forskjellige kodeord er lik d . I 1984 bestemte Arrigo Bonisoli strukturen til lineære envektskoder over begrensede felt og beviste at hver like langt lineær kode er en sekvens av to Hamming-koder .

Eksempler

Noen eksempler på lineære koder inkluderer:

Gjentagelseskoder
Paritetskoder
Sykliske koder
Hamming -koder
Golay -kode , både den binære og den ternære versjonen
Polynomkoder , hvorav BCH -koder er et eksempel
Reed - Solomon koder
Reed – Muller koder
Goppa -koder
Lav tetthet paritetskontrollkoder
Utviderkoder
Flerdimensjonale paritetskontrollkoder
Toriske koder
Turbo koder

Generalisering

Hamming mellomrom over ikke-felt alfabeter har også blitt vurdert, spesielt over endelige ringer (spesielt over Z ₄ ) som gir opphav til moduler i stedet for vektorrom og ring-lineære koder (identifisert med submoduler ) i stedet for lineære koder. Den typiske beregningen som brukes i dette tilfellet Lee -avstanden . Det finnes en grå isometri mellom (dvs. GF (2 ^2m )) med Hamming -avstanden og (også betegnet GR (4, m)) med Lee -avstanden; hovedattraksjonen er at den etablerer en samsvar mellom noen "gode" koder som ikke er lineære over som bilder av ringlinjære koder fra . ${\ displaystyle \ mathbb {Z} _ {2}^{2m}}$ ${\ displaystyle \ mathbb {Z} _ {4}^{m}}$ ${\ displaystyle \ mathbb {Z} _ {2}^{2m}}$ ${\ displaystyle \ mathbb {Z} _ {4}^{m}}$

Nylig har noen forfattere referert til slike koder over ringer ganske enkelt som lineære koder også.

Se også

Dekodingsmetoder

Referanser

^ William E. Ryan og Shu Lin (2009). Kanalkoder: Klassisk og moderne . Cambridge University Press. s. 4 . ISBN 978-0-521-84868-8.
^ MacKay, David, JC (2003). Informasjonsteori, slutning og læringsalgoritmer (PDF) . Cambridge University Press . s. 9. bibcode : 2003itil.book ..... M . ISBN 9780521642989. I en lineær blokkode er de ekstra bitene lineære funksjoner til de originale bitene; disse ekstra bitene kalles paritetskontrollbiter ${\ displaystyle NK}$ ${\ displaystyle K}$
^ Thomas M. Cover og Joy A. Thomas (1991). Elementer av informasjonsteori . John Wiley & Sons, Inc. s. 210–211 . ISBN 978-0-471-06259-2.
^ Etzion, Tuvi; Raviv, Netanel (2013). "Equidistant codes in the Grassmannian". arXiv : 1308.6231 [ math.CO ].
^ Bonisoli, A. (1984). "Hver likeveis lineære kode er en sekvens av to Hamming -koder". Ars Combinatoria . 18 : 181–186.
^ Marcus Greferath (2009). "En introduksjon til ring-lineær kodingsteori". I Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (red.). Gröbner -baser, koding og kryptografi . Springer Science & Business Media. ISBN 978-3-540-93806-4.
^ "Encyclopedia of Mathematics" . www.encyclopediaofmath.org .
^ JH van Lint (1999). Introduksjon til kodingsteori (3. utg.). Springer. Kapittel 8: Koder over ℤ ₄ . ISBN 978-3-540-64133-9.
^ ST Dougherty; J.-L. Kim; P. Sole (2015). "Åpne problemer i kodeteori" . I Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (red.). Ikke -kommutative ringer og deres applikasjoner . American Mathematical Soc. s. 80. ISBN 978-1-4704-1032-2.

Bibliografi

JF Humphreys; MY Prest (2004). Numbers, Groups and Codes (2. utg.). Cambridge University Press. ISBN 978-0-511-19420-7. Kapittel 5 inneholder en mer skånsom introduksjon (enn denne artikkelen) til emnet lineære koder.

Eksterne linker

q -ary code generator program
Kodetabeller: Grenser for parametrene for ulike typer koder , IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)] . Online, oppdatert tabell med optimale binære koder, inkluderer ikke-binære koder.
Databasen over Z4 -koder Online, oppdatert database med optimale Z4 -koder.

[1] William E. Ryan og Shu Lin (2009). Kanalkoder: Klassisk og moderne . Cambridge University Press. s. 4 . ISBN 978-0-521-84868-8.

[DrMacKayECC-2] MacKay, David, JC (2003). Informasjonsteori, slutning og læringsalgoritmer (PDF) . Cambridge University Press . s. 9. bibcode : 2003itil.book ..... M . ISBN 9780521642989. I en lineær blokkode er de ekstra bitene lineære funksjoner til de originale bitene; disse ekstra bitene kalles paritetskontrollbiter ${\ displaystyle NK}$ ${\ displaystyle K}$

[Cover_and_Thomas-3] Thomas M. Cover og Joy A. Thomas (1991). Elementer av informasjonsteori . John Wiley & Sons, Inc. s. 210–211 . ISBN 978-0-471-06259-2.

[4] Etzion, Tuvi; Raviv, Netanel (2013). "Equidistant codes in the Grassmannian". arXiv : 1308.6231 [ math.CO ].

[5] Bonisoli, A. (1984). "Hver likeveis lineære kode er en sekvens av to Hamming -koder". Ars Combinatoria . 18 : 181–186.

[Greferath2009-6] Marcus Greferath (2009). "En introduksjon til ring-lineær kodingsteori". I Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (red.). Gröbner -baser, koding og kryptografi . Springer Science & Business Media. ISBN 978-3-540-93806-4.

[7] "Encyclopedia of Mathematics" . www.encyclopediaofmath.org .

[Lint1999-8] JH van Lint (1999). Introduksjon til kodingsteori (3. utg.). Springer. Kapittel 8: Koder over ℤ ₄ . ISBN 978-3-540-64133-9.

[DoughertyFacchini2015-9] ST Dougherty; J.-L. Kim; P. Sole (2015). "Åpne problemer i kodeteori" . I Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (red.). Ikke -kommutative ringer og deres applikasjoner . American Mathematical Soc. s. 80. ISBN 978-1-4704-1032-2.

Languages

In other projects