Blockera kod - Block code

I kodningsteori , blockkoder är en stor och viktig familj av felrättande koder som kodar data i block. Det finns ett stort antal exempel på blockkoder, varav många har ett brett spektrum av praktiska tillämpningar. Den abstrakta definitionen av blockkoder är begreppsmässigt användbar eftersom den tillåter kodande teoretiker, matematiker och datavetare att studera begränsningarna för alla blockkoder på ett enhetligt sätt. Sådana begränsningar har ofta formen av gränser som relaterar olika parametrar för blockkoden till varandra, såsom dess hastighet och dess förmåga att upptäcka och korrigera fel.

Exempel på blockkoder är Reed – Solomon-koder , Hamming-koder , Hadamard-koder , Expanderkoder , Golay-koder och Reed – Muller-koder . Dessa exempel tillhör också klassen linjära koder och kallas därför linjära blockkoder . Mer specifikt är dessa koder kända som algebraiska blockkoder eller cykliska blockkoder, eftersom de kan genereras med användning av booleska polynom.

Algebraiska blockkoder är vanligtvis hårt avkodade med algebraiska avkodare.

Termen blockkod kan också hänvisa till vilken felkorrigeringskod som verkar på ett block av bitar av inmatningsdata för att producera bitar av utdata . Följaktligen är blockkodaren en minnesfri anordning. Enligt denna definition skulle också koder som turbokoder , avslutade faltningskoder och andra iterativt avkodningsbara koder (turboliknande koder) betraktas som blockkoder. En icke-avslutad faltningskodare skulle vara ett exempel på en icke-blockerad (oinramad) kod, som har minne och istället klassificeras som en trädkod . ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle (n, k)}$

Denna artikel handlar om "algebraiska blockkoder".

Blockkoden och dess parametrar

Felkorrigeringskoder används för att på ett tillförlitligt sätt sända digital data över opålitliga kommunikationskanaler som utsätts för kanalbrus . När en avsändare vill sända en möjligen mycket lång dataström med hjälp av en blockkod, bryter avsändaren upp strömmen i bitar av viss fast storlek. Varje sådan bit kallas meddelande och proceduren som ges av blockkoden kodar varje meddelande individuellt till ett kodord, även kallat ett block i samband med blockkoder. Avsändaren överför sedan alla block till mottagaren, som i sin tur kan använda någon avkodningsmekanism för (förhoppningsvis) att återställa de ursprungliga meddelandena från de eventuellt skadade mottagna blocken. Prestandan och framgången för den totala överföringen beror på kanalens parametrar och blockkoden.

Formellt är en blockkod en injektiv kartläggning

${\ displaystyle C: \ Sigma ^ {k} \ to \ Sigma ^ {n}}$ .

Här är en ändlig och icke-fri uppsättning och och är heltal. Betydelsen och betydelsen av dessa tre parametrar och andra parametrar relaterade till koden beskrivs nedan. ${\ displaystyle \ Sigma}$${\ displaystyle k}$${\ displaystyle n}$

Alfabetet Σ

Dataströmmen som ska kodas modelleras som en sträng över något alfabet . Storleken på alfabetet skrivs ofta som . Om så kallas blockkoden en binär blockkod. I många applikationer är det användbart att överväga att vara en huvudmakt och att identifiera sig med det begränsade fältet . ${\ displaystyle \ Sigma}$${\ displaystyle | \ Sigma |}$${\ displaystyle q}$${\ displaystyle q = 2}$${\ displaystyle q}$${\ displaystyle \ Sigma}$ ${\ displaystyle \ mathbb {F} _ {q}}$

Meddelandets längd k

Meddelanden är delar av , det vill säga längdsträngar . Följaktligen kallas numret meddelandelängden eller dimensionen för en blockkod. ${\ displaystyle m}$${\ displaystyle \ Sigma ^ {k}}$${\ displaystyle k}$${\ displaystyle k}$

Blocklängden n

Den blocklängd av en blockkod är antalet symboler i ett block. Följaktligen är elementen av strängar av längd och motsvarar block som kan tas emot av mottagaren. Därför kallas de också mottagna ord. Om någon meddelande , då kallas kodord av . ${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle n}$${\ displaystyle c = C (m)}$${\ displaystyle m}$${\ displaystyle c}$${\ displaystyle m}$

Hastigheten R

Den hastighet av en blockkod är definierad som förhållandet mellan dess meddelandelängd och dess blocklängd:

${\ displaystyle R = k / n}$ .

En stor hastighet innebär att mängden faktiskt meddelande per överfört block är hög. I denna mening mäter hastigheten överföringshastigheten och kvantiteten mäter den overhead som uppstår på grund av kodningen med blockkoden. Det är ett enkelt informationsteoretiskt faktum att hastigheten inte kan överstiga eftersom data i allmänhet inte kan komprimeras förlustfritt. Formellt följer detta av det faktum att koden är en injektiv karta. ${\ displaystyle 1-R}$${\ displaystyle 1}$${\ displaystyle C}$

Avståndet d

Det avstånd eller minsta avståndet d av en blockkod är det minsta antalet positioner i vilka som helst två distinkta kodord skiljer, och den relativa avståndet är fraktionen . Formellt, för mottagna ord , låt beteckna Hamming-avståndet mellan och , det vill säga antalet positioner där och skiljer sig åt. Då definieras minsta avstånd för koden som ${\ displaystyle \ delta}$${\ displaystyle d / n}$${\ displaystyle c_ {1}, c_ {2} \ in \ Sigma ^ {n}}$${\ displaystyle \ Delta (c_ {1}, c_ {2})}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle d}$${\ displaystyle C}$

${\ displaystyle d: = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ ovanpå m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}) , C (m_ {2})]}$ .

Eftersom vilken kod som helst måste vara injicerande kommer två kodord inte att vara överens i minst en position, så avståndet för vilken kod som helst är minst . Dessutom är avståndet lika med minimivikten för linjära blockkoder eftersom: ${\ displaystyle 1}$

${\ displaystyle \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ ovanpå m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}), C ( m_ {2})] = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ ovanpå m_ {1} \ neq m_ {2}} \ Delta [\ mathbf {0}, C (m_ {1}) + C (m_ {2})] = \ min _ {m \ in \ Sigma ^ {k} \ ovanpå m \ neq \ mathbf {0}} w [C (m)] = w_ {\ min}}$ .

Ett större avstånd möjliggör mer felkorrigering och upptäckt. Om vi ​​till exempel bara tar hänsyn till fel som kan ändra symboler för det skickade kodordet men aldrig radera eller lägga till dem, så är antalet fel det antal positioner där det skickade kodordet och det mottagna ordet skiljer sig åt. En kod med avståndet d tillåter mottagaren att detektera upp till överföringsfel eftersom ändring av positioner för ett kodord aldrig av misstag kan ge ett annat kodord. Om inte mer än överföringsfel inträffar kan mottagaren dessutom avkoda det mottagna ordet till ett kodord. Detta beror på att varje mottaget ord har högst ett kodord på avstånd . Om fler än överföringsfel inträffar kan mottagaren inte unikt avkoda det mottagna ordet i allmänhet eftersom det kan finnas flera möjliga kodord. Ett sätt för mottagaren att hantera denna situation är att använda listavkodning , där avkodaren matar ut en lista över alla kodord i en viss radie. ${\ displaystyle d-1}$${\ displaystyle d-1}$${\ displaystyle (d-1) / 2}$${\ displaystyle (d-1) / 2}$${\ displaystyle (d-1) / 2}$

Populär notation

Notationen beskriver en blockkod över ett alfabet med storlek , med en blocklängd , meddelandelängd och avstånd . Om blockkoden är en linjär blockkod används fyrkantiga parenteser i notationen för att representera detta faktum. För binära koder med tappas ibland indexet. För maximala avståndsseparabla koder är avståndet alltid , men ibland är det exakta avståndet inte känt, inte trivialt att bevisa eller ange eller inte behövs. I sådana fall kan -komponenten saknas. ${\ displaystyle (n, k, d) _ {q}}$${\ displaystyle \ Sigma}$${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle q = 2}$${\ displaystyle d = n-k + 1}$${\ displaystyle d}$

Ibland, särskilt för icke-blockkoder, används notationen för koder som innehåller kodord med längd . För blockkoder med meddelanden med längd över ett alfabet av storlek skulle detta nummer vara . ${\ displaystyle (n, M, d) _ {q}}$${\ displaystyle M}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle q}$${\ displaystyle M = q ^ {k}}$

Exempel

Som nämnts ovan finns det ett stort antal felkorrigeringskoder som faktiskt är blockkoder. Den första felkorrigerande koden var Hamming (7,4) -koden, utvecklad av Richard W. Hamming 1950. Denna kod förvandlar ett meddelande bestående av 4 bitar till ett kodord på 7 bitar genom att lägga till 3 paritetsbitar. Därför är den här koden en blockkod. Det visar sig att det också är en linjär kod och att den har avstånd 3. I förkortningen ovan betyder detta att Hamming (7,4) -koden är en kod. ${\ displaystyle [7,4,3] _ {2}}$

Reed – Solomonkoder är en familj av koder med och som en primärmakt . Rangkoder är koderfamiljer med . Hadamard-koder är en familj av koder med och . ${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle d = n-k + 1}$${\ displaystyle q}$${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle d \ leq n-k + 1}$${\ displaystyle [n, k, d] _ {2}}$${\ displaystyle n = 2 ^ {k-1}}$${\ displaystyle d = 2 ^ {k-2}}$

Feldetekterings- och korrigeringsegenskaper

Ett kodord kan betraktas som en punkt i -dimensionsutrymmet och koden är delmängden av . En kod har avstånd betyder att det inte finns något annat kodord i Hamming-bollen centrerad på med radie , vilket definieras som samlingen av -dimensionsord vars Hamming-avstånd till inte är mer än . På samma sätt har (minsta) avstånd följande egenskaper: ${\ displaystyle c \ in \ Sigma ^ {n}}$${\ displaystyle n}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle d}$${\ displaystyle \ forall c \ i {\ mathcal {C}}}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle d}$

• ${\ displaystyle {\ mathcal {C}}}$ kan upptäcka fel: Eftersom ett kodord är det enda kodordet i Hamming-bollen centrerad i sig själv med radie , kan inget felmönster eller färre fel ändra ett kodord till ett annat. När mottagaren upptäcker att den mottagna vektorn inte är ett kodord för detekteras felen (men ingen garanti att korrigera). ${\ displaystyle d-1}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle d-1}$${\ displaystyle {\ mathcal {C}}}$
• ${\ displaystyle {\ mathcal {C}}}$ kan korrigera fel. Eftersom ett kodord är det enda kodordet i Hamming-bollen centrerad i sig själv med radie , överlappar inte de två Hamming-kulorna som är centrerade på två olika kodord med båda radierna. Om vi ​​anser felkorrigering som att hitta kodordet närmast det mottagna ordet , så länge antalet fel inte är mer än , finns det bara ett kodord i hammingkulan centrerad på med radie , därför kunde alla fel korrigeras . ${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$${\ displaystyle y}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$${\ displaystyle y}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$
• För att avkoda i närvaro av mer än fel kan listavkodning eller maximal sannolikhetsavkodning användas. ${\ displaystyle (d-1) / 2}$
• ${\ displaystyle {\ mathcal {C}}}$ kan korrigera raderingar . Med radering betyder det att positionen för den raderade symbolen är känd. Korrigering kan uppnås genom att passera avkodning: vid passering fylls den raderade positionen med symbolen och felkorrigering utförs. Det måste passera att antalet fel inte är mer än och därför kan raderingarna korrigeras. ${\ displaystyle d-1}$ ${\ displaystyle q}$${\ displaystyle i ^ {th}}$${\ displaystyle i ^ {th}}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$

Nedre och övre gränser för blockkoder

Hamminggräns

Det finns teoretiska gränser (som Hamming-gränsen), men en annan fråga är vilka koder som faktiskt kan konstrueras. Det är som att packa sfärer i en låda i många dimensioner. Detta diagram visar de konstruerbara koder, som är linjära och binära. De x -axeln visar antalet skyddade symboler k , den y axel antalet nödvändiga symboler check n-k . Plottade är gränserna för olika Hamming-avstånd från 1 (oskyddad) till 34. Markerade med prickar är perfekta koder:

• ljus orange på x- axeln: triviala oskyddade koder
• orange på y- axeln: triviala upprepningskoder
• mörk orange på datamängden d = 3: klassiska perfekta Hamming-koder
• mörkröd och större: den enda perfekta binära Golay-koden

Familj med koder

${\ displaystyle C = \ {C_ {i} \} _ {i \ geq 1}}$ kallas kodfamilj , var är en kod med monoton ökning . ${\ displaystyle C_ {i}}$${\ displaystyle (n_ {i}, k_ {i}, d_ {i}) _ {q}}$${\ displaystyle n_ {i}}$

Familjegrad för koder C definieras som ${\ displaystyle R (C) = \ lim _ {i \ to \ infty} {k_ {i} \ över n_ {i}}}$

Relativt avstånd från familjen av koder C definieras som ${\ displaystyle \ delta (C) = \ lim _ {i \ to \ infty} {d_ {i} \ över n_ {i}}}$

För att utforska förhållandet mellan och är en uppsättning nedre och övre gränser för blockkoder kända. ${\ displaystyle R (C)}$${\ displaystyle \ delta (C)}$

Hamming bunden

${\ displaystyle R \ leq 1- {1 \ over n} \ cdot \ log _ {q} \ cdot \ left [\ sum _ {i = 0} ^ {\ left \ lfloor {{\ delta \ cdot n-1 } \ över 2} \ höger \ rfloor} {\ binom {n} {i}} (q-1) ^ {i} \ höger]}$

Singleton bunden

Singleton-gränsen är att summan av frekvensen och det relativa avståndet för en blockkod inte kan vara mycket större än 1:

${\ displaystyle R + \ delta \ leq 1 + {\ frac {1} {n}}}$ .

Med andra ord uppfyller varje blockkod ojämlikheten . Reed – Solomon-koder är icke-triviala exempel på koder som uppfyller singleton bunden med jämlikhet. ${\ displaystyle k + d \ leq n + 1}$

Plotkin bunden

För , . Med andra ord . ${\ displaystyle q = 2}$${\ displaystyle R + 2 \ delta \ leq 1}$${\ displaystyle k + 2d \ leq n}$

För det allmänna fallet gäller följande Plotkin-gränser för alla med avstånd d : ${\ displaystyle C \ subseteq \ mathbb {F} _ {q} ^ {n}}$

1. Om ${\ displaystyle d = \ left (1- {1 \ over q} \ right) n, | C | \ leq 2qn}$
2. Om ${\ displaystyle d> \ left (1- {1 \ over q} \ right) n, | C | \ leq {qd \ over {qd- \ left (q-1 \ right) n}}}$

För alla q- koder med avstånd , ${\ displaystyle \ delta}$${\ displaystyle R \ leq 1- \ left ({q \ over {q-1}} \ right) \ delta + o \ left (1 \ right)}$

Gilbert – Varshamov bunden

${\ displaystyle R \ geq 1-H_ {q} \ left (\ delta \ right) - \ epsilon}$ , där , är q -ary entropifunktionen. ${\ displaystyle 0 \ leq \ delta \ leq 1- {1 \ över q}, 0 \ leq \ epsilon \ leq 1-H_ {q} \ vänster (\ delta \ höger)}$${\ displaystyle H_ {q} \ left (x \ right) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ -x \ cdot \ log _ {q} {x \ over {q-1}} - \ vänster (1-x \ höger) \ cdot \ log _ {q} {\ vänster (1-x \ höger)}}$

Johnson bunden

Definiera . Låta vara det maximala antalet kodord i en Hamming boll med radien e för någon kod av avståndet d . ${\ displaystyle J_ {q} \ left (\ delta \ right) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ \ left (1- {1 \ over q} \ right ) \ vänster (1 - {\ sqrt {1- {q \ delta \ över {q-1}}}} \ höger)}$
${\ displaystyle J_ {q} \ vänster (n, d, e \ höger)}$${\ displaystyle C \ subseteq \ mathbb {F} _ {q} ^ {n}}$

Sedan har vi Johnson Bound  : om ${\ displaystyle J_ {q} \ vänster (n, d, e \ höger) \ leq qnd}$${\ displaystyle {e \ over n} \ leq {{q-1} \ over q} \ left ({1 - {\ sqrt {1- {q \ over {q-1}} \ cdot {d \ over n }}}} \, \ höger) = J_ {q} \ vänster ({d \ över n} \ höger)}$

Elias – Bassalygo bunden

${\ displaystyle R = {\ log _ {q} {| C |} \ över n} \ leq 1-H_ {q} \ vänster (J_ {q} \ vänster (\ delta \ höger) \ höger) + o \ vänster (1 \ höger)}$

Sfärförpackningar och galler

Blockkoder är knutna till sfärpaketeringsproblemet som har fått viss uppmärksamhet genom åren. I två dimensioner är det lätt att visualisera. Ta ett gäng öre platt på bordet och skjut dem ihop. Resultatet är ett sexkantigt mönster som ett bi-bo. Men blockkoder är beroende av fler dimensioner som inte lätt kan visualiseras. Den kraftfulla Golay-koden som används i rymdkommunikation använder 24 dimensioner. Om de används som en binär kod (som den vanligtvis är) hänvisar dimensionerna till längden på kodordet som definierats ovan.

Teorin om kodning använder N- dimensionell sfärmodell. Till exempel hur många öre som kan packas i en cirkel på en bordsskiva eller i tre dimensioner, hur många kulor kan packas i en jordglob. Andra överväganden anger valet av en kod. Till exempel kommer hexagonpackning i begränsningen av en rektangulär låda att lämna tomt utrymme i hörnen. När dimensionerna blir större blir andelen tomt utrymme mindre. Men vid vissa dimensioner använder förpackningen allt utrymme och dessa koder är så kallade perfekta koder. Det finns väldigt få av dessa koder.

En annan egenskap är antalet grannar som ett enda kodord kan ha. Återigen, betrakta öre som ett exempel. Först packar vi pennorna i ett rektangulärt rutnät. Varje öre kommer att ha fyra nära grannarna (och fyra i hörnen som ligger längre bort). I en sexkant kommer varje öre att ha 6 nära grannar. Respektivt, i tre och fyra dimensioner, ges den maximala packningen av 12-ansiktet och 24-cellen med 12 respektive 24 grannar. När vi ökar dimensionerna ökar antalet nära grannar mycket snabbt. I allmänhet ges värdet av de kyssande siffrorna .

Resultatet är att antalet sätt för buller för att få mottagaren att välja en granne (därmed ett fel) växer också. Detta är en grundläggande begränsning av blockkoder, och faktiskt alla koder. Det kan vara svårare att orsaka ett fel för en enskild granne, men antalet grannar kan vara tillräckligt stort så att den totala felsannolikheten faktiskt lider.

Se även

• Kanal kapacitet
• Sats Shannon – Hartley
• Bullrande kanal
• Listavkodning
• Sfärförpackning

Referenser

• JH van Lint (1992). Introduktion till kodningsteori . GTM . 86 (2: a upplagan). Springer-Verlag. sid.  31 . ISBN   3-540-54894-7 .
• FJ MacWilliams ; NJA Sloane (1977). Teorin om felkorrigeringskoder . Nord-Holland. sid.  35 . ISBN   0-444-85193-3 .
• W. Huffman; V.Pless (2003). Grundläggande för felkorrigeringskoder . Cambridge University Press. ISBN   978-0-521-78280-7 .
• S. Lin; DJ Jr. Costello (1983). Felkontrollkodning: grundläggande och applikationer . Prentice-Hall. ISBN   0-13-283796-X .

externa länkar

• Charan Langton (2001) Kodningskoncept och blockkodning