Linjekod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 januari 2021; verifiering kräver 1 redigering .

Inom matematik och informationsteori är en linjekod en typ av blockkod som används i feldetekterings- och korrigeringskretsar. Linjära koder, i jämförelse med andra koder, gör det möjligt att implementera effektivare algoritmer för kodning och avkodning av information.

Grunderna

I processen att lagra data och överföra information över kommunikationsnätverk uppstår oundvikligen fel. Dataintegritetskontroll och felkorrigering är viktiga uppgifter på många nivåer av att arbeta med information (särskilt de fysiska , datalänk- och transportskikten i OSI -modellen ).

I kommunikationssystem är flera strategier för att hantera fel möjliga:

feldetektering i datablock och automatisk begäran om återsändning av skadade block - detta tillvägagångssätt används huvudsakligen vid datalänken och transportskikten;
feldetektering i datablock och kassering av dåliga block - detta tillvägagångssätt används ibland i strömmande mediasystem där överföringsfördröjning är viktig och det inte finns tid för återsändning;
felkorrigering ( engelska forward error correction ) tillämpas på det fysiska lagret.

Feldetekterings- och korrigeringskoder

Korrigeringskoder - koder som används för att upptäcka eller korrigera fel som uppstår under överföring av information under påverkan av störningar , såväl som under dess lagring.

För att göra detta, när de skriver (sänder) till användbar data, lägger de till speciellt strukturerad redundant information, och vid läsning (mottagning) används den för att upptäcka eller korrigera fel. Naturligtvis är antalet fel som kan korrigeras begränsat och beror på den specifika kod som används.

Nära relaterade till felkorrigerande koder är feldetekteringskoder . Till skillnad från den förra kan den senare endast fastställa förekomsten av ett fel i den överförda informationen, men inte korrigera den.

Faktum är att de använda feldetekteringskoderna tillhör samma klasser av koder som de felkorrigerande koderna. Faktum är att vilken felkorrigerande kod som helst kan också användas för att upptäcka fel (genom att göra det kommer den att kunna upptäcka fler fel än vad den kunde fixa).

Enligt metoden att arbeta med data är felkorrigerande koder indelade i blockkoder , som delar upp information i fragment av konstant längd och bearbetar var och en av dem separat, och faltningskoder , som arbetar med data som en kontinuerlig ström.

Blockera koder

Låt den kodade informationen delas upp i bitlängdsfragment, som omvandlas till bitlängdskodord . Då brukar motsvarande blockkod betecknas . I det här fallet kallas numret kodhastigheten . $k$ $n$ $(n,k)$ $R={\frac {k}{n}}$

Om koden lämnar de ursprungliga bitarna oförändrade och lägger till kontroller kallas en sådan kod systematisk , annars icke-systematisk . $k$ $nk$

Du kan ställa in blockkoden på olika sätt, inklusive en tabell där varje uppsättning informationsbitar är associerade med en bit av kodordet. Bra kod bör dock uppfylla åtminstone följande kriterier: $k$ $n$

förmågan att rätta till så många fel som möjligt,
så lite redundans som möjligt,
enkel kodning och avkodning.

Det är lätt att se att dessa krav motsäger varandra. Det är därför det finns ett stort antal koder, som var och en är lämplig för sitt utbud av uppgifter.

Nästan alla koder som används är linjära . Detta beror på det faktum att icke-linjära koder är mycket svårare att studera, och det är svårt för dem att tillhandahålla en acceptabel enkel kodning och avkodning.

Linjära mellanslag

Genererar matris

Låt vektorerna ligga till grund för det linjära rummet . Enligt definitionen av bas kan vilken vektor som helst representeras som en linjär kombination av basvektorer: , eller i matrisform , som: $\overrightarrow {x_{1}}=(x_{{11}},..,x_{{1n}}),\overrightarrow {x_{2}}=(x_{{21}},..,x_{ {2n}}),..,\overrightarrow {x_{k}}=(x_{{k1}},..,x_{{kn}})$ $C$ $\overrightarrow {v}\i C$ $\overrightarrow {v}={c_{1}}\overrightarrow {x_{1}}+{c_{2}}\overrightarrow {x_{2}}+...+{c_{k}}\overrightarrow {x_ {k}}$

$\overrightarrow {v}=({c_{1}},{c_{2}},..,{c_{k}}){\begin{bmatrix}x_{{11}}&x_{{12}}& ..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n}}\\..&..&..&..\\x_{{k1 }}&x_{{k2}}&..&x_{{kn}}\\\end{bmatrix}}=\överhögerpil {c}G$ ,

där kallas generatormatrisen för det linjära rummet . $G={\begin{bmatrix}x_{{11}}&x_{{12}}&..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n }}\\..&..&..&..\\x_{{k1}}&x_{{k2}}&..&x_{{kn}}\\\end{bmatrix}}$

Denna relation upprättar ett samband mellan vektorerna av koefficienter och vektorerna . Genom att lista alla vektorer av koefficienter kan du få alla vektorer . Matrisen genererar med andra ord ett linjärt utrymme. $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\i C$ $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\i C$ $G$

Kontrollera matris

Ett annat sätt att definiera linjära mellanrum är att beskriva dem i termer av en bockmatris.

Låta vara ett linjärt k-dimensionellt delrum av ett n-dimensionellt utrymme över ett ändligt fält och vara ett ortogonalt komplement till . Sedan, enligt en av satserna för linjär algebra, är dimensionen . Därför finns det r basvektorer i . Låt grunden vara i . $\mathbb {C}$ $\mathbb {F} _{q}$ ${\mathbb {W}}$ $\mathbb {C}$ ${\mathbb {W}}$ $r=nk$ ${\mathbb {W}}$ $\overrightarrow {h}_{1}=({{h_{1}}_{1}},...,{{h_{1}}_{n}}),\overrightarrow {h}_{2 }=({{h_{2}}_{1}},...,{{h_{2}}_{n}}),...,\overrightarrow {h}_{r}=({ {h_{r}}_{1}},...,{{h_{r}}_{n}})$ ${\mathbb {W}}$

Då uppfyller vilken vektor som helst följande linjära ekvationssystem : ${\overrightarrow {v}}\in \mathbb {C}$

${\begin{cases}h_{{11}}x_{1}+h_{{12}}x_{2}+...+h_{{1n}}x_{n}=0\\h_{{21 }}x_{1}+h_{{22}}x_{2}+...+h_{{2n}}x_{n}=0\\...\\h_{{r1}}x_{1 }+h_{{r2}}x_{2}+...+h_{{rn}}x_{n}=0\end{case}}$

Eller i matrisform : $\overrightarrow {v}H^{T}=0$

var är kontrollmatrisen. $H={\begin{bmatrix}\overrightarrow {h}_{1}\\\overrightarrow {h}_{2}\\...\\\overrightarrow {h}_{r}\\\end{bmatrix }}={\begin{bmatrix}h_{{11}}&h_{{12}}&..&h_{{1n}}\\h_{{21}}&h_{{22}}&..&h_{{ 2n}}\\..&..&..&..\\h_{{r1}}&h_{{r2}}&..&h_{{rn}}\\\end{bmatrix}}$

Det reducerade systemet med linjära ekvationer bör betraktas som ett kontrollsystem för alla vektorer i det linjära rummet, därför kallas matrisen en kontrollmatris. ${\mathbb {H}}$

Formell definition

En linjär kod med längden n och rang k är ett linjärt delrum C med dimensionen k av vektorrummet , där är ett ändligt fält av q element. En sådan kod med en parameter q kallas en q-är kod (till exempel om q = 5, så är detta en 5-är kod). Om q = 2 eller q = 3, är koden binär respektive ternär . ${\mathbb {F}}_{q}^{n}$ $\mathbb {F} _{q}$

En linjär (block) kod är en kod så att uppsättningen av dess kodord bildar ett -dimensionellt linjärt delrum (låt oss kalla det ) i ett -dimensionellt linjärt utrymme , isomorft till rymden av -bitvektorer . $k$ $C$ $n$ $k$

Detta betyder att kodningsoperationen motsvarar multiplikationen av den ursprungliga -bit-vektorn med en icke-singular matris , kallad generatormatrisen . $k$ $G$

Låta vara ett ortogonalt delrum med avseende på , och vara en matris som definierar grunden för detta delrum. Då är det sant för vilken vektor som helst : $C^{\perp}$ $C$ $H$ $\overrightarrow {v}\i C$

\overrightarrow {v}H^{T}=\overrightarrow {0}

Egenskaper och viktiga satser

Minsta avstånd och korrigerande kraft

Hamming-avståndet ( Hamming metric ) mellan två kodordärantalet olika bitar i motsvarande positioner, det vill säga antalet "enheter" i vektorn. $\overrightarrow {v_{1}}$ $\overrightarrow {v_{2}}$ $\overrightarrow {v_{1}}\oplus \overrightarrow {v_{2}}$

Det minsta linjekodavståndet är det minsta av alla Hamming-avstånd för alla kodordspar. $d$

Vikten av en vektor är Hamming-avståndet mellan denna vektor och nollvektorn, med andra ord, antalet icke-nollkomponenter i vektorn. $w$

Sats 1:

Minsta avstånd för en linjekod är lika med minimum av Hamming-vikter för kodord som inte är noll: $d$

$d=\min _{{\overrightarrow {c}\in C,\overrightarrow {c}\not =\overrightarrow {0}}}(w(\overrightarrow {c}))$

Bevis:

Avståndet mellan två vektorer uppfyller likheten , där är vektorns Hamming-vikt . Från det faktum att skillnaden mellan två kodord i en linjär kod också är ett kodord för en linjär kod, följer satsen: $d(\överhögerpil {x},\överhögerpil {y})$ $d(\överhögerpil {x},\överhögerpil {y})=w(\överhögerpil {x}-\överhögerpil {y})$ $w(\överhögerpil {t})$ $\overrightarrow {t}$ $d=\min _{{\överhögerpil {c}\in C,\överhögerpil {c}\not =\överhögerpil {0}}}w(\överhögerpil {c})$

Minsta Hamming-avstånd är en viktig egenskap hos en linjär blockkod. Den definierar en annan, inte mindre viktig egenskap - korrigerande förmåga : $d$

$t=\vänster\lgolv {\frac {d-1}{2}}\höger\rgolv$ , här betecknar vinkelparenteserna avrundning "nedåt".

Korrigeringsförmågan bestämmer vad som är det maximala antalet fel i ett kodord som koden kan garanteras korrigera.

Låt oss förklara med ett exempel. Anta att det finns två kodord A och B, Hamming-avståndet mellan dem är lika med 3. Om ord A sändes och kanalen introducerade ett fel i en bit, kan det korrigeras, eftersom även i detta fall det mottagna ordet är närmare kodord A än B. Men om tvåbitarsfel introducerades av kanalen, kan avkodaren anta att ord B sändes.

Antalet detekterade fel är antalet fel vid vilka avkodaren kan detektera en felsituation (och t.ex. initiera omsändning av meddelandet). Detta nummer är

f=d-1

Sats 2 (utan bevis):

Om några kolumner i kontrollmatrisen H för en linjär (n, k)-kod är linjärt oberoende, är det minsta kodavståndet minst d. Om det finns d linjärt beroende kolumner är det minsta kodavståndet exakt d. $l\leqslant d-1$

Sats 3 (utan bevis):

Om minimiavståndet för en linjär (n, k) kod är d, är alla kolumner i kontrollmatrisen H linjärt oberoende och det finns d linjärt beroende kolumner. $l\leqslant d-1$

Hamming-koder

Historiskt sett borde " Hamming-koder " kallas R. Fisher-koder och introducerades 1942 (Fisher RA Theory of confouding in factor to thr theory). Hammingkoder är de enklaste linjära koderna med ett minsta avstånd på 3, det vill säga kan korrigera ett fel. Hamming-koden kan representeras på ett sådant sätt att syndromet

\overrightarrow {s}=\overrightarrow {r}H^{T}

, var är den accepterade vektorn,

\overrightarrow{r}

kommer att vara lika med positionsnumret där felet inträffade. Denna egenskap gör avkodningen mycket enkel.

Reed-Muller-kod

Reed-Muller-koden är en linjär binär blockkod. Med en viss konstruktionsmetod kan det vara systematiskt. I allmänhet är Reed-Muller-koden inte cyklisk. Reed-Muller-koderna ges av följande parametrar: för alla värden påoch, kallad kodordningen, mindre än: $m$ $r$ $m$

kodordslängd

n=2^{m};

informationsdelens längd

k=1+C_{m}^{1}+\dots +C_{m}^{r};

testdellängd

nk=1+C_{m}^{1}+\dots +C_{m}^{mr-1};

minsta kodavstånd

d_{min}=2^{mr}.

Reed-Muller-koden bestäms med hjälp av en generatormatris som består av basvektorer, som är byggd enligt regeln:

låt vara en vektor, vars alla komponenter är lika med 1;

V_{0}

låt vara raderna i en matris vars kolumner alla är binära längduppsättningar

{\displaystyle V_{1},\ V_{2},\dots V_{m))

m.

Reed-Muller-koden av den e ordningen innehåller vektorer och alla komponentprodukter eller ett mindre antal av dessa vektorer som bas. $r$ ${\displaystyle V_{0},\ V_{1},\dots V_{m))$ $r$

Allmän metod för kodning av radkoder

En linjär kod med längden n med k informationssymboler är ett k-dimensionellt linjärt delrum, så varje kodord är en linjär kombination av delrummets basvektorer : $\overrightarrow {g_{1}}=(g_{{11}},..,g_{{1n}}),\overrightarrow {g_{2}}=(g_{{21}},..,g_{ {2n}}),..,\overrightarrow {g_{k}}=(g_{{k1}},..,g_{{kn}})$

$\overrightarrow {c}={m_{1}}\overrightarrow {g_{1}}+{m_{2}}\overrightarrow {g_{2}}+...+{m_{k}}\overrightarrow {g_ {k}}$ .

Eller med hjälp av generatormatrisen:

$\overrightarrow {c}=\overrightarrow {m}G=({m_{1}},{m_{2}},..,{m_{k}}){\begin{bmatrix}g_{{11}} &g_{{12}}&..&g_{{1n}}\\g_{{21}}&g_{{22}}&..&g_{{2n}}\\..&..&..&. .\\g_{{k1}}&g_{{k2}}&..&g_{{kn}}\\\end{bmatrix}}$ , var $\overrightarrow {m}=({m_{1}},..,{m_{k}}),{m_{1}},..,{m_{k}}\in {\mathbb {Q}}$

Detta förhållande är kodningsregeln enligt vilken informationsordet mappas till koden $\overrightarrow {m}=({m_{1}},..,{m_{k}})$ $\overrightarrow {c}=({c_{1}},..,{c_{n}})$

Allmän metod för att upptäcka fel i linjär kod

Vilken kod som helst (inklusive icke-linjär) kan avkodas med hjälp av en vanlig tabell, där varje värde på det mottagna ordet motsvarar det mest sannolika sända ordet . Emellertid kräver denna metod användning av enorma tabeller redan för kodord med relativt liten längd. $\overrightarrow {r_{i}}$ $\overrightarrow {u_{i}}$

För linjära koder kan denna metod förenklas avsevärt. I det här fallet, för varje mottagen vektor , beräknas syndromet . Eftersom , var är kodordet och är felvektorn, då . Sedan, med hjälp av syndromtabellen, bestäms en felvektor, med hjälp av vilken det överförda kodordet bestäms. I det här fallet är tabellen mycket mindre än när du använder den tidigare metoden. $\overrightarrow {r_{i}}$ $\overrightarrow {s_{i}}=\overrightarrow {r_{i}}H^{T}$ $\overrightarrow {r_{i}}=\overrightarrow {v_{i}}+\overrightarrow {e_{i}}$ $\overrightarrow {v_{i}}$ $\overrightarrow {e_{i}}$ $\overrightarrow {s_{i}}=\overrightarrow {e_{i}}H^{T}$

Linjära cykliska koder

Trots det faktum att felkorrigering i linjära koder redan är mycket lättare än korrigering i de flesta icke-linjära koder, är denna process fortfarande ganska komplicerad för de flesta koder. Cykliska koder har, förutom enklare avkodning, andra viktiga egenskaper.

En cyklisk kod är en linjär kod med följande egenskap: om är ett kodord, då är dess cykliska permutation också ett kodord. $\overrightarrow{v}$

Orden i en cyklisk kod representeras lämpligen som polynom. Till exempel representeras ett kodord som ett polynom . I detta fall är kodordets cykliska skiftning ekvivalent med att multiplicera polynomet med modulo . $\overrightarrow {v}=(v_{0},v_{1},...,v_{{n-1}})$ $v(x)=v_{0}+v_{1}x+...+v_{{n-1}}x^{{n-1}}$ $x$ $x^n-1$

I framtiden, om inte annat anges, kommer vi att anta att den cykliska koden är binär , det vill säga ... kan anta värdena 0 eller 1 . $v_{0},v_{1}$

Genererar polynom

Det kan visas att alla kodord i en viss cyklisk kod är multiplar av ett visst genererande polynom . Generatorpolynomet är en divisor . $g(x)$ $x^n-1$

Med hjälp av ett genererande polynom utförs kodning av en cyklisk kod. Särskilt:

icke-systematisk kodning utförs genom att multiplicera den kodade vektorn med : ; $g(x)$ $v(x)=u(x)g(x)$

systematisk kodning utförs genom att ”lägga till” till det kodade ordet resten av divisionen med , det vill säga . $x^{{nk}}u(x)$ $g(x)$ $v(x)=x^{{nk}}u(x)+[x^{{nk}}u(x)\mod g(x)]$

CRC-koder

CRC- koder (cyklisk redundanskontroll - cyklisk redundanskontroll) är systematiska koder utformade för att inte korrigera fel utan för att upptäcka dem. De använder den systematiska kodningsmetoden som beskrivs ovan: "kontrollsumman" beräknas genom att dividera med . Eftersom ingen felkorrigering krävs kan överföringsvalidering göras på samma sätt. $x^{{nk}}u(x)$ $g(x)$

Således anger formen av polynomet g(x) en specifik CRC-kod. Exempel på de mest populära polynomen:

kodnamn	grad	polynom
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC- CCITT	16	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^ {8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

BCH-koder

Bose-Chowdhury-Hockwingham (BCH)-koder är en underklass av binära cykliska koder. Deras utmärkande särdrag är förmågan att konstruera en BCH-kod med ett minsta avstånd som inte är mindre än ett givet. Detta är viktigt eftersom det generellt sett är en mycket svår uppgift att bestämma minimikodavståndet.

Matematiskt använder konstruktionen av BCH-koder och deras avkodning nedbrytningen av det genererande polynomet till faktorer i Galois-fältet . $g(x)$

Reed-Solomon-koder

Reed-Solomon- koder (RS-koder) är faktiskt icke- binära BCH-koder, det vill säga elementen i kodvektorn är inte bitar, utan grupper av bitar. Reed-Solomon-koder är mycket vanliga och arbetar med bytes ( oktetter ).

Fördelar och nackdelar med linjekoder

+ På grund av linjäritet, för att memorera eller räkna upp alla kodord, räcker det att lagra en betydligt mindre del av dem i kodarens eller avkodarens minne, nämligen endast de ord som utgör grunden för motsvarande linjära utrymme. Detta förenklar implementeringen av kodnings- och avkodningsanordningar avsevärt och gör linjära koder mycket attraktiva ur praktisk tillämpningssynpunkt.

— Även om linjära koder som regel klarar sällsynta men stora felskurar , är deras effektivitet med frekventa men små fel (till exempel i en kanal med AWGN ) mindre hög.

Prestationsbedömning

Kodernas effektivitet bestäms av antalet fel som den kan korrigera, mängden redundant information som måste läggas till och komplexiteten i implementeringen av kodning och avkodning (både hårdvara och datorprogramvara ).

Hamming bundna och perfekta koder

Låt det finnas en binär blockkod med korrigerande förmåga . Följande ojämlikhet gäller då (kallad Hamming bound ): $(n,k)$ $t$

\sum _{i=0}^{t}{C_{n}^{i}}\leq 2^{nk}

Koder som uppfyller denna jämställdhetsgräns sägs vara perfekta . Perfekta koder inkluderar till exempel Hamming-koder. Koder med stor korrigerande kraft som ofta används i praktiken (som Reed-Solomon-koder) är inte perfekta.

Energivinst

Vid sändning av information över en kommunikationskanal beror felsannolikheten på signal-brusförhållandet vid demodulatoringången, så vid en konstant brusnivå är sändareffekten av avgörande betydelse. I satellit- och mobilsystem, såväl som andra typer av kommunikationer, är frågan om energibesparing akut. Dessutom, i vissa kommunikationssystem (till exempel telefon), tillåter tekniska begränsningar inte en obegränsad ökning av signaleffekten.

Eftersom felkorrigerande kodning tillåter felkorrigering, kan dess tillämpning minska sändareffekten och lämna informationshastigheten oförändrad. Energivinsten definieras som skillnaden mellan s/n-förhållandena i närvaro och frånvaro av kodning.

Applikation

Linjekoder gäller:

i digitala kommunikationssystem , inklusive: satellit, radiorelä, cellulär, dataöverföring över telefonkanaler;
i informationslagringssystem, inklusive magnetiska och optiska;
i nätverksprotokoll på olika nivåer .

Litteratur

Explanatory Dictionary of Computing Systems. Ed. V. Illingworth m. fl.: Per. från engelska. - M.: Mashinostroenie , 1990. 560 s.: ill.