Utvidelseskode - Expander code

Utvidelseskoder
todelt utvidelsesgraf
Klassifisering
Type	Lineær blokkode
Blokklengde	${\ displaystyle n}$
Meldingslengde	${\ displaystyle nm}$
Vurdere	${\ displaystyle 1-m / n}$
Avstand	${\ displaystyle 2 (1- \ epsilon) \ gamma \ cdot n}$
Alfabetets størrelse	${\ displaystyle 2}$
Notasjon	${\ displaystyle [n, nm, 2 (1- \ epsilon) \ gamma \ cdot n] _ {2}}$ -kode
v t e

I kodeteori , ekspansjons koder danner en klasse feilrettingskoder som er bygget opp av todelte ekspander grafer . Sammen med Justesen-koder er utviderkoder av spesiell interesse siden de har en konstant positiv hastighet , en konstant positiv relativ avstand og en konstant alfabetstørrelse . Faktisk inneholder alfabetet bare to elementer, så utviderkoder tilhører klassen av binære koder . Videre kan utviderkoder både kodes og dekodes i tid proporsjonalt med blokkens lengde.

Utvidelseskoder

I kodingsteorien er en utviderkode en lineær blokkodekode hvis paritetskontrollmatrise er tilstøtningsmatrisen til en tosidig utvidelsesgraf . Disse kodene har god relativ avstand , hvor og er egenskaper for utvidelsesgrafen som definert senere), hastighet og dekodbarhet (algoritmer for kjøretid eksisterer). ${\ displaystyle [n, nm] _ {2} \,}$ ${\ displaystyle 2 (1- \ varepsilon) \ gamma \,}$${\ displaystyle \ varepsilon \,}$${\ displaystyle \ gamma \,}$ ${\ displaystyle \ left (1 - {\ tfrac {m} {n}} \ right) \,}$${\ displaystyle O (n) \,}$

Definisjon

Tenk på en todelt graf , hvor og er toppunkt sett og er settet med kanter som forbinder hjørner inn til hjørner av . Anta at hver node i har grad (grafen er -left- vanlig ), og , . Da er en ekspander graf hvis hver liten nok undergruppe , har den egenskapen at har minst distinkte naboer i . Merk at dette holder trivielt for . Når og for en konstant , sier vi at det er en tapsfri utvidelse. ${\ displaystyle G (L, R, E) \,}$${\ displaystyle L \,}$${\ displaystyle R \,}$${\ displaystyle E \,}$${\ displaystyle L \,}$${\ displaystyle R \,}$${\ displaystyle L \,}$ ${\ displaystyle d \,}$${\ displaystyle d \,}$${\ displaystyle | L | = n \,}$${\ displaystyle | R | = m \,}$${\ displaystyle m <n \,}$${\ displaystyle G \,}$${\ displaystyle (n, m, d, \ gamma, \ alpha) \,}$${\ displaystyle S \ delmengde L \,}$${\ displaystyle | S | \ leq \ gamma n \,}$${\ displaystyle S \,}$${\ displaystyle d \ alpha | S | \,}$${\ displaystyle R \,}$${\ displaystyle \ gamma \ leq {\ tfrac {1} {n}} \,}$${\ displaystyle {\ tfrac {1} {n}} <\ gamma \ leq 1 \,}$${\ displaystyle \ alpha = 1- \ varepsilon \,}$${\ displaystyle \ varepsilon \,}$${\ displaystyle G \,}$

Siden er en todelt graf, kan vi vurdere dens nærhetsmatrise. Deretter er den lineære koden generert ved å se transponere av denne matrisen som en paritetskontrollmatrise en utvidelseskode. ${\ displaystyle G \,}$${\ displaystyle n \ times m \,}$${\ displaystyle C \,}$

Det har vist seg at det ikke eksisterer tapsløse utvidelsesdiagrammer. Videre kan vi eksplisitt konstruere dem.

Vurdere

Hastigheten på er dens dimensjon delt på blokklengden. I dette tilfellet har paritetskontrollmatrisen størrelse , og har derfor minst dimensjon . ${\ displaystyle C \,}$${\ displaystyle m \ times n \,}$${\ displaystyle C \,}$${\ displaystyle (nm) / n = 1 - {\ tfrac {m} {n}} \,}$

Avstand

Anta . Da er avstanden til en utviderkode i det minste . ${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$${\ displaystyle (n, m, d, \ gamma, 1- \ varepsilon) \,}$${\ displaystyle C \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n \,}$

Bevis

Merk at vi kan vurdere hver kodeord i som en undergruppe av hjørnene , ved å si at toppunktet hvis og bare hvis th indeks av kodeord er en 1. Deretter er et kodeord iff hver toppunktet ligger i tilknytning til et likt antall noder i . (For å være et kodeord, hvor er paritetskontrollmatrisen. Deretter tilsvarer hvert toppunkt hver kolonne . Matrisemultiplikasjon over gir det ønskede resultatet.) Hvis et toppunkt ligger ved siden av et enkelt toppunkt i , vi vet umiddelbart at det ikke er et kodeord. La betegne naboene i fra , og betegner de naboer av dem er unike, det vil si, ved siden av en enkelt toppunktet . ${\ displaystyle c \,}$${\ displaystyle C \,}$${\ displaystyle S \ delmengde L \,}$${\ displaystyle v_ {i} \ i S \,}$${\ displaystyle i \,}$${\ displaystyle c \,}$${\ displaystyle v \ i R \,}$${\ displaystyle S \,}$${\ displaystyle cP = 0 \,}$${\ displaystyle P \,}$${\ displaystyle R \,}$${\ displaystyle P \,}$${\ displaystyle {\ text {GF}} (2) = \ {0,1 \} \,}$${\ displaystyle v \ i R \,}$${\ displaystyle S \,}$${\ displaystyle c \,}$${\ displaystyle N (S) \,}$${\ displaystyle R \,}$${\ displaystyle S \,}$${\ displaystyle U (S) \,}$${\ displaystyle S \,}$${\ displaystyle S \,}$

Lemma 1

For hver av størrelse , . ${\ displaystyle S \ delmengde L \,}$${\ displaystyle | S | \ leq \ gamma n \,}$${\ displaystyle d | S | \ geq | N (S) | \ geq | U (S) | \ geq d (1-2 \ varepsilon) | S | \,}$

Bevis

For det første, antyder siden . følger siden graden av hvert toppunkt i er . Ved utvidelsesegenskapen til grafen må det være et sett med kanter som går til forskjellige hjørner. De resterende kantene gjør at de fleste naboer ikke er unike, så . ${\ displaystyle | N (S) | \ geq | U (S) | \,}$${\ displaystyle v \ in U (S) \,}$${\ displaystyle v \ i N (S) \,}$${\ displaystyle | N (S) | \ leq d | S | \,}$${\ displaystyle S \,}$${\ displaystyle d \,}$${\ displaystyle d (1- \ varepsilon) | S | \,}$${\ displaystyle d \ varepsilon | S | \,}$${\ displaystyle d \ varepsilon | S | \,}$${\ displaystyle U (S) \ geq d (1- \ varepsilon) | S | -d \ varepsilon | S | = d (1-2 \ varepsilon) | S | \,}$

Resultat

Hver tilstrekkelig liten har en unik nabo. Dette følger siden . ${\ displaystyle S \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$

Lemma 2

Hver delmengde med har en unik nabo. ${\ displaystyle T \ subset L \,}$${\ displaystyle | T | <2 (1- \ varepsilon) \ gamma n \,}$

Bevis

Lemma 1 viser saken , antar det . La slik det . Ved Lemma 1 vet vi det . Deretter et toppunkt er i IFF , og vi vet at , så ved første del av Lemma 1, vet vi . Siden , og dermed ikke er tom. ${\ displaystyle | T | \ leq \ gamma n \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n> | T |> \ gamma n \,}$${\ displaystyle S \ delmengde T \,}$${\ displaystyle | S | = \ gamma n \,}$${\ displaystyle | U (S) | \ geq d (1-2 \ varepsilon) | S | \,}$${\ displaystyle v \ in U (S) \,}$${\ displaystyle U (T) \,}$${\ displaystyle v \ notin N (T \ setminus S) \,}$${\ displaystyle | T \ setminus S | \ leq 2 (1- \ varepsilon) \ gamma n- \ gamma n = (1-2 \ varepsilon) \ gamma n \,}$${\ displaystyle | N (T \ setminus S) | \ leq d (1-2 \ varepsilon) \ gamma n \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$${\ displaystyle | U (T) | \ geq | U (S) \ setminus N (T \ setminus S) | \ geq | U (S) | - | N (T \ setminus S) |> 0 \,}$${\ displaystyle U (T) \,}$

Resultat

Merk at hvis a har minst 1 unik nabo, dvs. at det tilsvarende ordet som tilsvarer ikke kan være et kodeord, da det ikke vil multiplisere med vektoren for alle nuller med paritetskontrollmatrisen. Ved forrige argument, . Siden er lineær, konkluderer vi med minst avstand . ${\ displaystyle T \ subset L \,}$${\ displaystyle | U (T) |> 0 \,}$${\ displaystyle c \,}$${\ displaystyle T \,}$${\ displaystyle c \ in C \ innebærer wt (c) \ geq 2 (1- \ varepsilon) \ gamma n \,}$${\ displaystyle C \,}$${\ displaystyle C \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n \,}$

Koding

Kodingstiden for en utvidelseskode er øvre avgrenset av en generell lineær kode - ved matriksmultiplikasjon. Et resultat på grunn av Spielman viser at koding er mulig i tide. ${\ displaystyle O (n ^ {2}) \,}$${\ displaystyle O (n) \,}$

Dekoding

Avkoding av utviderkoder er mulig i tide når du bruker følgende algoritme. ${\ displaystyle O (n) \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {4}} \,}$

La være toppunktet for det som tilsvarer den indeksen i kodeordene til . La være et mottatt ord, og . La være , og være . Tenk deretter på den grådige algoritmen: ${\ displaystyle v_ {i} \,}$${\ displaystyle L \,}$${\ displaystyle i \,}$${\ displaystyle C \,}$${\ displaystyle y \ in \ {0,1 \} ^ {n} \,}$${\ displaystyle V (y) = \ {v_ {i} \ mid {\ text {the}} i ^ {\ text {th}} {\ text {position of}} y {\ text {is a}} 1 \} \,}$${\ displaystyle e (i) \,}$${\ displaystyle | \ {v \ in R \ mid v_ {i} \ in N (v) {\ text {and}} N (v) \ cap V (y) {\ text {is even}} \} | \,}$${\ displaystyle o (i) \,}$${\ displaystyle | \ {v \ in R \ mid v_ {i} \ in N (v) {\ text {and}} N (v) \ cap V (y) {\ text {is odd}} \} | \,}$

---

Inngang: mottatt ord . ${\ displaystyle y \,}$

initialize y' to y
while there is a v in R adjacent to an odd number of vertices in V(y')
    if there is an i such that o(i) > e(i)
        flip entry i in y'
    else
        fail

Utgang: mislykkes eller endres kodeord . ${\ displaystyle y '\,}$

---

Bevis

Vi viser først korrektheten til algoritmen, og undersøker deretter kjøretiden.

Korrekthet

Vi må vise at algoritmen slutter med riktig kodeord når det mottatte kodeordet er innenfor halve kodens avstand fra det opprinnelige kodeordet. La settet av skadede variabler være , og settet av utilfredsstilt (ved siden av et ulike antall hjørner) topp-punkt i be . Følgende lemma vil vise seg å være nyttig. ${\ displaystyle S \,}$${\ displaystyle s = | S | \,}$${\ displaystyle R \,}$${\ displaystyle c \,}$

Lemma 3

Hvis , så er det en med . ${\ displaystyle 0 <s <\ gamma n \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle o (i)> e (i) \,}$

Bevis

Av Lemma 1 vet vi det . Så en gjennomsnittlig toppunkt har i det minste unike naboer (husk at unike naboer er misfornøyde og dermed bidrar til ), siden , og dermed er det et toppunkt med . ${\ displaystyle U (S) \ geq d (1-2 \ varepsilon) s \,}$${\ displaystyle d (1-2 \ varepsilon)> d / 2 \,}$${\ displaystyle o (i) \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {4}} \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle o (i)> e (i) \,}$

Så hvis vi ennå ikke har nådd et kodeord, vil det alltid være noe toppunkt å snu. Deretter viser vi at antall feil aldri kan øke utover . ${\ displaystyle \ gamma n \,}$

Lemma 4

Hvis vi begynner med , når vi aldri noe punkt i algoritmen. ${\ displaystyle s <\ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle s = \ gamma n \,}$

Bevis

Når vi snur et toppunkt , og byttes ut, og siden vi hadde det , betyr dette at antallet utilfredse hjørner til høyre reduseres med minst en etter hver snu. Siden er det opprinnelige antall utilfredse hjørner på det meste av grafens regelmessighet. Hvis vi nådde en streng med feil, ville det ved Lemma 1 være minst unike naboer, noe som betyr at det i det minste ville være utilfredse hjørner, en motsetning. ${\ displaystyle v_ {i} \,}$${\ displaystyle o (i) \,}$${\ displaystyle e (i) \,}$${\ displaystyle o (i)> e (i) \,}$${\ displaystyle s <\ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle d \ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle d \,}$${\ displaystyle \ gamma n \,}$${\ displaystyle d \ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle d \ gamma (1-2 \ varepsilon) n \,}$

Lemmas 3 og 4 viser oss at hvis vi begynner med (halvparten av avstanden til ), så vil vi alltid finne et toppunkt å snu. Hver flipp reduserer antall utilfredse hjørner med minst 1, og dermed slutter algoritmen i de fleste trinn, og den slutter ved et kodeord, av Lemma 3. (Hvis det ikke var ved et kodeord, ville det være noe toppunkt å snu ). Lemma 4 viser oss at vi aldri kan være lenger enn unna riktig kodeord. Siden koden har avstand (siden ), må kodeordet den ender på være riktig kodeord, siden antallet bitvipp er mindre enn halvparten av avstanden (så vi kunne ikke ha reist langt nok til å nå noe annet kodeord). ${\ displaystyle s <\ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle C \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle R \,}$${\ displaystyle m \,}$${\ displaystyle \ gamma n \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n> \ gamma n \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$

Kompleksitet

Vi viser nå at algoritmen kan oppnå lineær tidsavkoding. La være konstant, og være den maksimale graden av et toppunkt i . Merk at det også er konstant for kjente konstruksjoner. ${\ displaystyle {\ tfrac {n} {m}} \,}$${\ displaystyle r \,}$${\ displaystyle R \,}$${\ displaystyle r \,}$

1. Forbehandling: Det tar tid å beregne om hvert toppunkt i har et odde eller jevnt antall naboer. ${\ displaystyle O (mr) \,}$${\ displaystyle R \,}$
2. Pre-prosessering 2: Vi tar deg tid til å beregne en liste over topp-punkt i som har . ${\ displaystyle O (dn) = O (dmr) \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle L \,}$${\ displaystyle o (i)> e (i) \,}$
3. Hver gjentakelse: Vi fjerner bare det første listeelementet. For å oppdatere listen over odde / jevne hjørner , trenger vi bare å oppdatere oppføringer, sette inn / fjerne etter behov. Vi oppdaterer deretter oppføringene i listen over hjørner med mer rare enn til og med naboer, og setter inn / fjerner etter behov. Dermed tar hver iterasjon tid. ${\ displaystyle R \,}$${\ displaystyle O (d) \,}$${\ displaystyle O (dr) \,}$${\ displaystyle L \,}$${\ displaystyle O (dr) \,}$
4. Som argumentert ovenfor er det totale antallet gjentakelser på det meste . ${\ displaystyle m \,}$

Dette gir en total kjøretid , hvor og er konstanter. ${\ displaystyle O (mdr) = O (n) \,}$${\ displaystyle d \,}$${\ displaystyle r \,}$

Se også

• Utvid grafen
• Paritetskontrollkode med lav tetthet
• Lineær tidskoding og dekoding av feilrettingskoder
• ABNNR- og AEL-koder

Merknader

Denne artikkelen er basert på Dr. Venkatesan Guruswamis kursnotater.

Referanser