Konvolutionskod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 september 2018; kontroller kräver 8 redigeringar .

En faltningskod är en felkorrigerande kod där

vid varje klockcykel för kodaren omvandlas symbolerna för den ingående halvoändliga sekvensen till symboler för utgångssekvensen $k$ $n>k$
tidigare karaktärer är också involverade i konverteringen $m$
egenskapen linjäritet är uppfylld (om två kodade sekvenser och motsvarar kodsekvenser och , då motsvarar den kodade sekvensen ). ${\mathbf x}$ ${\mathbf y}$ $\mathbf X$ $\mathbf Y$ $a\mathbf x+b\mathbf y$ $a\mathbf X+b\mathbf Y$

En faltningskod är ett specialfall av träd- och spaljékoder .

Origins

1955 föreslog L. M. Fink , som vid den tiden var chef för avdelningen för Leningrad Academy of Communications, den första återkommande koden.

1959 "återupptäckte" den västerländska specialisten Hegelberger ( Hegelbeger ), som inte hade någon aning om sovjetiska vetenskapsmäns arbete inom kodningsområdet, den återkommande koden och döpte den efter sig själv.

Fink skrev själv i sin monografi "The Theory of Discret Message Transmission" [1] : "I denna kod är sekvensen av kodsymboler inte uppdelad i separata kodkombinationer. Korrigeringssymboler ingår i informationssymbolströmmen så att en korrigeringssymbol placeras mellan varannan informationssymbol. Genom att beteckna informationstecken genom och korrigerande genom får vi följande teckensekvens: $a_{i}$ $bi}$

$a_{1}b_{1}\,a_{2}b_{2}\,a_{3}b_{3}\,\dots \,a_{k}b_{k}\,a_{k +1}b_{k+1}\,\dots$

Informationssymboler bestäms av det överförda meddelandet, och korrigerande symboler bildas enligt följande regel:

$b_{i}=\left(a_{ks}+a_{k+s+1}\right)\mod 2$ (1.1)

där är ett godtyckligt heltal som kallas kodsteget ( ). Uppenbarligen, om någon korrigerande symbol bi tas emot av misstag, kommer relationen (1.1) i den mottagna sekvensen inte att uppfyllas för . Vid felaktig mottagning av informationssymbolen kommer relation (1.1) inte att gälla för två värden på , nämligen för och för . Härifrån är det lätt att härleda en korrigeringsregel för avkodningsfel. I den accepterade kodsekvensen kontrolleras relation (1.1) för varje . Om den inte är nöjd med två värden ( och ), och samtidigt $s$ $s=0,1,2\dots$ $i=k$ $a_{i}$ $k_i$ $k_{1}=är-1$ $k_{2}=i+s$ $b_{k}$ $k$ $k=k_{1}$ $k=k_{2}$

$k_{2}-k_{1}=2s+1$ (1.2)

då måste informationselementet vändas. $a_{k_{1}+s+1}$

Uppenbarligen är kodredundansen . Det låter dig korrigera alla felaktigt mottagna tecken, förutom vissa dåliga kombinationer. Så, om , ger den korrekt avkodning när det finns minst tre (och i vissa fall två) korrekt mottagna symboler mellan två felaktigt mottagna symboler (både information och testsymboler tas med i beräkningen). $1/2$ $s=0$

Allmänt schema för en icke-rekursiv kodare

Kodardiagrammet för en icke-rekursiv faltningskod visas i fig . 1. Den består av -ary skiftregister med längder . Vissa (kanske alla) registeringångar och utgångar från vissa minnesceller är anslutna till flera modulo-adderare . Antalet adderare är större än antalet skiftregister: $k$ $q$ $m_1. m_2,...,m_k$ $n$ $q$ $n>k$

Vid varje klockcykel hos kodaren matas informationssymboler till dess ingång, de, tillsammans med symbolerna lagrade i skiftregistren, matas till ingångarna hos de adderare med vilka det finns en förbindelse. Resultatet av tillägget är kodsymboler redo för överföring. Sedan sker en förskjutning i varje skiftregister: alla celler flyttas åt höger med en bit, medan cellerna längst till vänster fylls med inmatningstecken, och cellerna längst till höger raderas. Därefter upprepas takten. Registrens initiala tillstånd är känt i förväg (vanligtvis noll). $k$ $n$

Den totala längden av alla skiftregister kallas kodgränsen och den maximala längden kallas fördröjningen . $m = \sum_{i=1}^k m_i$ $w = \max\{m_1,...,m_k\}$

Värdena för skiftregistren vid varje tidpunkt kallas kodarens tillstånd .

Binära faltningskodare

För tydlighetens skull kommer vi att beskriva faltningskodning enligt verkan av motsvarande kodningsenhet.

En faltningskodare är en anordning som i allmänhet tar emot k ingångsinformationssymboler vid varje operationscykel, och matar ut n utgångssymboler vid utgången av varje cykel. Numret kallas den relativa kodhastigheten. k är antalet informationssymboler, n är antalet symboler som sänds till kommunikationskanalen i en cykel av ankomst till informationssymbolens kodare. Utgångssymbolerna för den aktuella cykeln beror på m informationssymboler som anländer till denna och tidigare cykler, det vill säga utmatningssymbolerna för faltningskoden bestäms unikt av dess ingångssymboler och tillståndet, vilket beror på m - k tidigare informationssymboler . Huvudelementen i faltningskoden är: skiftregister, modulo 2-adderare, kommutator. $R={\frac {k}{n}}$

Skiftregistret är en dynamisk lagringsenhet som lagrar de binära tecknen 0 och 1. Kodminnet bestämmer antalet triggerceller m i skiftregistret . När ett nytt informationstecken kommer till skiftregistrets ingång tas tecknet som är lagrat i biten längst till höger bort från registret och återställs. De återstående tecknen flyttas en siffra till höger och därmed släpps siffran längst till vänster, där det nya informationstecknet kommer.

Modulo 2-adderaren adderar symbolerna 1 och 0 som kommer till den. Modulo 2-additionsregeln är som följer: summan av binära symboler är 0 om antalet ettor bland symbolerna som kommer in i ingångarna är jämnt, och lika med 1 om detta nummer är udda.

Omkopplaren läser sekventiellt symbolerna som kommer till dess ingångar och ställer in sekvensen av kodsymboler i kommunikationskanalen vid utgången. I analogi med blockkoder kan faltningskoder klassificeras i systematiska och icke-systematiska.

En systematisk faltningskod är en kod som i sin utgående sekvens av kodsymboler innehåller den sekvens av informationssymboler som genererade den. Annars kallas koden icke-systematisk.

Parametrar och egenskaper för faltningskoder

Med faltningskodning sker omvandlingen av informationssekvenser till utdata och kodsekvenser kontinuerligt. Den binära faltningskodaren innehåller ett skiftregister med m bitar och modulo 2-adderare för att generera kodsymboler i utmatningssekvensen. Adderarnas ingångar är kopplade till vissa bitar i registret. Utgångsomkopplaren bestämmer i vilken ordning kodsymboler skickas till kommunikationskanalen. Sedan bestäms kodstrukturen av följande egenskaper.

Antalet informationssymboler som kommer till kodarens ingång i en cykel är k.
Antalet symboler vid utgången av kodaren är n, vilket motsvarar de k ingångssymbolerna under cykeln.
Kodhastigheten bestäms av förhållandet R=k/n och kännetecknar redundansen som införs under kodningen.
Kodredundans $\vartheta = 1 - R$
Kodminnet (inmatningslängden för kodbegränsningen eller informationslängden för kodordet) bestäms av den maximala graden av det genererande polynomet i genereringsmatrisen G(X): $l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$
Markeringen av faltningskoden betecknas i de flesta fall (n, k, l), men variationer är möjliga.
Vikten w av binära kodsekvenser bestäms av antalet "enheter" som ingår i denna sekvens eller kodord.
Kodavståndet visar graden av skillnad mellan de i:te och j:te kodkombinationerna, förutsatt att de är av samma längd. För alla två binära kodkombinationer är kodavståndet lika med antalet tecken som inte matchar i dem. I allmänhet kan kodavståndet definieras som det totala resultatet av modulo 2-addition av samma namnbitar av kodkombinationer , där och är de k:te symbolerna för kodkombinationerna i och j; L är längden på kodkombinationen. $d$
$d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$ $k_{i,j}$ $k_{jk}$
Minsta kodavstånd är det minsta Hamming-avståndet för en uppsättning kodord med konstant längd. För att hitta det är det nödvändigt att räkna upp alla möjliga par av kodkombinationer. Då får vi . $d_{min}$ $d_{min} = \min d_{ij}$

Men! Denna definition är giltig för blockkoder med konstant längd. Faltningskoder är kontinuerliga och kännetecknas av många minimiavstånd som bestäms av längden på de initiala segmenten av kodsekvenserna, mellan vilka minimiavståndet tas. Antalet symboler i segmentlängden L som tas emot för behandling bestämmer, på den mottagande sidan, antalet celler i avkodaren.

Allmän vy av en binär faltningskodare

Låt skiftregistret innehålla m celler, det vill säga kodminnet är lika med m, omkopplaren utför en avfrågningscykel och skickar värdena för informationssymboler, där m är en multipel av k , medan den i en cykel pollar n 2 kodarutgångar. Antalet utgångskodsymboler som påverkas av en ändring av en ingångsinformationssymbol är . Värdet I all kallas den totala längden av kodbegränsningen . $1\le k<m$ $\geq$ $I_{all}=\frac{mn}{k}$

Eftersom de korrigerande egenskaperna för en viss faltningskod bestäms av längden på kodbegränsningen och valet av länkar för skiftregistret till modulo 2-adderaren ( XOR ), är det nödvändigt att specificera strukturen för faltningskodaren. specificera vilka bitar i skiftregistret som är associerade med var och en av modulo 2-adderarna ( XOR ).

Anslutningen av den j:te adderaren modulo 2 beskrivs av den j:te genereringssekvensen:

g j =(g j0 , g j1 ,g j2 ,...,g jm-1 ), (4.1)

där (4.2) $g_{ij} = \begin{cases} 1,&\text{om steg i av register kopplat till XOR-grind}\\ 0,&\text{i andra fall} \end{cases}$

Typiska parametrar för faltningskoder: k, n= 1,2,...,8; R=k/n=1/4,…,7/8; m=2,…,10.

Inställningsmetod för faltningskoder

Det är bekvämt att specificera en faltningskod med genererande polynom, som bestäms av formen av formel (4.1) i analogi med hur detta görs för linjära blockcykliska koder . [2]

Generatorpolynomet definierar fullständigt strukturen för den binära kodaren för faltningskoden. Till skillnad från blockkoder , som var och en beskrivs av endast ett genererande polynom , beskrivs en faltningskod av flera genererande polynom. Antalet polynom som beskriver faltningskoden bestäms av antalet utgående symboler n . Låt oss representera sekvensen av informationssymboler som kommer till kodarens ingång som ett polynom

A(X)=a_{0}+a_{1}X+a_{2}X^{2}+\dots ,

där Xi är symbolen för fördröjningsoperatorn för i -cykler i skiftregistret, och i = {0, 1} är binära informationssymboler. Polynom som beskriver n sekvenser av kodsymboler som går in i kodaromkopplarens ingång och sedan in i kommunikationskanalen har formen

B_{j}(X)=b_{0}^{j}+b_{1}^{j}X+b_{2}^{j}X^{2}+\dots ,

där finns binära kodsymboler vid den j -te ingången på kodaromkopplaren. ${\displaystyle b_{i}^{j}=\left\{{0;1}\right\))$

Det j -te genererande polynomet i faltningskoden har formen Dessutom, på grund av linjäriteten hos faltningskoden och den accepterade notationen, får vi . ${\displaystyle G_{j}(X)=g_{0}+g_{1}X+g_{2}X^{2}+\dots +g_{m-1}X^{m-1))$ $g_{i}={0;1}$ $B_j(X) = G_j(X) A(X)$

Genom att använda representationen av en faltningskod med användning av genererande polynom, kan man specificera en faltningskod med hjälp av sekvenser av koefficienter för genererande polynom skrivna i binär eller oktal form. Den oktala notationen är mer kompakt och används när kodarskiftregistret är långt.

I det allmänna fallet kommer koefficientsekvensen för det j :te genererande polynomet att ha formen och sammanfalla med den genererande kodsekvensen (4.1). Sedan, om är en sekvens av kodade symboler, och är en sekvens av kodsymboler vid den j -: te ingången på kodaromkopplaren , så kan vi skriva för någon av dem som visas vid -: e gången ( ). $G^{j}={g_{0}^{j},g_{1}^{j},\dots ,g_{m-1}^{j))$ ${\displaystyle A={a_{0},a_{1},a_{2},\dots ))$ ${\displaystyle B_{j}={b_{0}^{j},b_{1}^{j},b_{2}^{j},\dots ))$ $\mu$ $\mu =0,1,2,\dots$

b_{\mu }^{j}=\sum _{i=0}^{m-1}a_{\mu -i}g_{i}^{j}.

Således bestäms varje kodsymbol för utmatningssekvensen från kodaren för faltningskoden av faltningen av den kodade informationen och genereringssekvensen, som bestämmer namnet på faltningskoderna. Konvolutionskoder är ett specialfall av iterativa eller återkommande koder.

Applikation

Konvolutionskoder används för tillförlitlig dataöverföring: video, mobilkommunikation, satellitkommunikation. De används tillsammans med Reed-Solomon-koden och andra liknande koder. Före uppfinningen av turbokoder var sådana konstruktioner de mest effektiva och uppfyller Shannons gräns. Dessutom används faltningskodning i 802.11a- protokollet vid det fysiska MAC-lagret för att uppnå en enhetlig fördelning av 0 och 1 efter att signalen passerat genom scramblern , vilket resulterar i att antalet överförda symboler fördubblas och därför kan uppnå gynnsam mottagning vid den mottagande enheten.

Se även

Anteckningar

↑ Fink L. M. Teori om överföring av diskreta meddelanden
↑ Sagalovich, 2014 , kapitel 4 och 5.

Litteratur

Gallagher R. Informationsteori och tillförlitlig kommunikation. - M . : Sovjetisk radio, 1974. - 720 sid.
Morelos-Zaragoza R. Konsten att felkorrigera kodning. Metoder, algoritmer, tillämpning / per. från engelska. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 sid. — (Kommunikationens värld). - 2000 exemplar. — ISBN 5-94836-035-0 .
Fink L. M. Teori om överföring av diskreta meddelanden. - M . : Sov. radio, 1963. - 576 sid.
Nikitin G.I. Konvolutionskoder: Lärobok. - St Petersburg. : Ugglor. radio, 2001. - 78 sid.
Sagalovich Yu. L. Introduktion till algebraiska koder - 3:e upplagan, reviderad. och ytterligare - M. : IPPI RAN , 2014. - 310 sid. — ISBN 978-5-901158-24-1
Handledning för Nikitin G.I. Convolutional codes
Bankett, VL "Signalkodkonstruktioner i telekommunikationssystem." S: Phoenix (2009).
Kolesnik VD, Poltyrev G. Sh. Kurs i informationsteori. - "Vetenskap", kapitel. ed. fysisk och matematisk litteratur, 1982.
Ngok DK Undersökning av sökmetoder för optimala faltnings- och perforerade faltningskoder: dis. – Avhandling för kandidatexamen för tekniska vetenskaper. St Petersburg: LETI, 2014.

Ordböcker och uppslagsverk	stor kines Britannica (online)