Konvolution kode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. september 2018; checks kræver 8 redigeringer .

En foldningskode er en fejlkorrigerende kode , hvori

ved hver clock-cyklus af indkoderen konverteres symbolerne for input-semi-infinite-sekvensen til symboler for output-sekvensen $k$ $n>k$
tidligere karakterer er også involveret i konverteringen $m$
egenskaben linearitet er opfyldt (hvis to kodede sekvenser og svarer til kodesekvenser og , så svarer den kodede sekvens til ). ${\mathbf x}$ ${\mathbf y}$ $\mathbf X$ $\mathbf Y$ $a\mathbf x+b\mathbf y$ $a\mathbf X+b\mathbf Y$

En foldningskode er et specialtilfælde af træ- og espalierkoder .

Oprindelse

I 1955 foreslog L. M. Fink , som på det tidspunkt var leder af afdelingen for Leningrad Academy of Communications, den første tilbagevendende kode.

I 1959 "genopdagede" den vestlige specialist Hegelberger ( Hegelbeger ), som ikke anede noget om sovjetiske videnskabsmænds arbejde inden for kodning, den tilbagevendende kode og opkaldte den efter sig selv.

Fink skrev selv i sin monografi "The Theory of Discrete Message Transmission" [1] : "I denne kode er sekvensen af kodesymboler ikke opdelt i separate kodekombinationer. Korrektionssymboler er inkluderet i informationssymbolstrømmen, således at der placeres et korrektionssymbol mellem hvert andet informationssymbol. Ved at angive informationstegn gennem , og korrigerende gennem får vi følgende sekvens af tegn: $a_{i}$ $b_{i}$

$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 bestemmes af den transmitterede meddelelse, og korrigerende symboler dannes i henhold til følgende regel:

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

hvor er et vilkårligt heltal kaldet kodetrinnet ( ). Det er klart, at hvis et korrigerende symbol bi modtages ved en fejl, vil relation (1.1) i den modtagne sekvens ikke være opfyldt for . I tilfælde af fejlagtig modtagelse af informationssymbolet, vil relation (1.1) ikke gælde for to værdier af , nemlig for og for . Herfra er det let at udlede en afkodningsfejlkorrektionsregel. I den accepterede kodesekvens kontrolleres relation (1.1) for hver . Hvis den ikke er tilfreds med to værdier ( og ), og på samme tid $s$ $s=0,1,2\dots$ $i=k$ $a_{i}$ $k_i$ $k_{1}=er-1$ $k_{2}=i+s$ $b_{k}$ $k$ ${\displaystyle k=k_{1))$ ${\displaystyle k=k_{2))$

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

så skal informationselementet vendes om. $a_{k_{1}+s+1}$

Det er klart, at koderedundansen er . Det giver dig mulighed for at rette alle fejlagtigt modtagne tegn, bortset fra nogle dårlige kombinationer. Så hvis , giver det korrekt afkodning, når der er mindst tre (og i nogle tilfælde to) korrekt modtagne symboler mellem to fejlagtigt modtagne symboler (både information og testsymboler tages i betragtning). $1/2$ $s=0$

Generelt skema for en ikke-rekursiv encoder

Indkoderdiagrammet for en ikke-rekursiv foldningskode er vist i fig . Den består af -ary skifteregistre med længder . Nogle (måske alle) registerindgange og -udgange fra nogle hukommelsesceller er forbundet med flere modulo-addere . Antallet af addere er større end antallet af skifteregistre: $k$ $q$ $m_1. m_2,...,m_k$ $n$ $q$ $n>k$

Ved hver pulscyklus for indkoderen tilføres informationssymboler til dens indgang, de sammen med de i skifteregistrene lagrede symboler føres til indgangene på de addere, som der er forbindelse med. Resultatet af tilføjelsen er kodesymboler klar til transmission. Så sker der en forskydning i hvert skifteregister: alle celler flyttes til højre med en bit, mens cellerne længst til venstre er fyldt med inputtegn, og cellerne længst til højre slettes. Derefter gentages slaget. Registrenes begyndelsestilstand er kendt på forhånd (normalt nul). $k$ $n$

Den samlede længde af alle skifteregistre kaldes kodegrænsen , og den maksimale længde kaldes forsinkelsen . $m = \sum_{i=1}^k m_i$ $w = \max\{m_1,...,m_k\}$

Værdierne af skifteregistrene på hvert tidspunkt kaldes koderens tilstand .

Binære foldningskodere

For klarhed i præsentationen vil vi beskrive foldningskodning i henhold til handlingen af den tilsvarende kodningsenhed.

En foldningskoder er en enhed, der generelt modtager k inputinformationssymboler ved hver operationscyklus og udsender n outputsymboler ved outputtet af hver cyklus. Nummeret kaldes den relative kodesats. k er antallet af informationssymboler, n er antallet af symboler transmitteret til kommunikationskanalen i en cyklus af ankomst til informationssymbolets indkoder. Udgangssymbolerne for den pågældende cyklus afhænger af m informationssymboler, der ankommer til denne og tidligere cykler, det vil sige, at outputsymbolerne for foldningskoden er entydigt bestemt af dens inputsymboler og tilstanden, som afhænger af m - k tidligere informationssymboler . Hovedelementerne i foldningskoden er: skifteregister, modulo 2-adder, kommutator. $R={\frac {k}{n}}$

Skifteregisteret er en dynamisk lagerenhed, der gemmer de binære tegn 0 og 1. Kodehukommelsen bestemmer antallet af triggerceller m i skifteregistret . Når et nyt informationstegn ankommer til indgangen til skifteregisteret, fjernes tegnet, der er lagret i bit længst til højre, fra registret og nulstilles. De resterende tegn flyttes et ciffer til højre, og dermed frigives cifferet længst til venstre, hvor det nye informationstegn ankommer.

Modulo 2 addereren tilføjer symbolerne 1 og 0, der kommer til den. Modulo 2 additionsreglen er som følger: summen af binære symboler er 0, hvis antallet af ener blandt de symboler, der kommer ind i input, er lige, og er lig med 1, hvis dette tal er mærkeligt.

Switchen læser sekventielt de symboler, der ankommer til dens indgange, og sætter sekvensen af kodesymboler i kommunikationskanalen ved udgangen. Analogt med blokkoder kan foldningskoder klassificeres i systematiske og ikke-systematiske.

En systematisk foldningskode er en kode, der i sin outputsekvens af kodesymboler indeholder den sekvens af informationssymboler, der genererede den. Ellers kaldes koden ikke-systematisk.

Parametre og karakteristika for foldningskoder

Med foldningskodning sker transformationen af informationssekvenser til output- og kodesekvenser kontinuerligt. Den binære foldningskoder indeholder et skifteregister på m bit og modulo 2-addere til at generere kodesymboler i outputsekvensen. Adderens indgange er forbundet med bestemte bits af registeret. Udgangskontakten bestemmer rækkefølgen, i hvilken kodesymboler sendes til kommunikationskanalen. Derefter bestemmes kodestrukturen af følgende karakteristika.

Antallet af informationssymboler, der ankommer til indgangen til koderen i en cyklus, er k.
Antallet af symboler ved udgangen af koderen er n, svarende til de k indgangssymboler under cyklussen.
Kodehastigheden bestemmes af forholdet R=k/n og karakteriserer redundansen, der indføres under kodningen.
Kode redundans $\vartheta = 1 - R$
Kodehukommelsen (inputlængden af kodebegrænsningen eller informationslængden af kodeordet) bestemmes af den maksimale grad af det genererende polynomium i genereringsmatrixen G(X): $l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$
Mærkningen af foldningskoden er angivet i de fleste tilfælde (n, k, l), men variationer er mulige.
Vægten w af binære kodesekvenser bestemmes af antallet af "enheder", der er inkluderet i denne sekvens eller kodeord.
Kodeafstanden viser graden af forskel mellem de i-te og j-te kodekombinationer, forudsat at de er af samme længde. For alle to binære kodekombinationer er kodeafstanden lig med antallet af tegn, der ikke stemmer overens i dem. Generelt kan kodeafstanden defineres som det samlede resultat af modulo 2-addition af samme navn bits af kodekombinationer , hvor og er de k-te symboler af kodekombinationer i og j; L er længden af kodekombinationen. $d$
$d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$ $k_{i,j}$ $k_{jk}$
Den mindste kodeafstand er den mindste Hamming-afstand for et sæt kodeord med konstant længde. For at finde det er det nødvendigt at opregne alle mulige par kodekombinationer. Så får vi . $d_{min}$ $d_{min} = \min d_{ij}$

Men! Denne definition er gyldig for blokkoder med konstant længde. Konvolutionskoder er kontinuerlige og er karakteriseret ved mange minimumsafstande bestemt af længderne af de indledende segmenter af kodesekvenserne, mellem hvilke minimumsafstanden tages. Antallet af symboler i segmentlængden L modtaget til behandling bestemmer, på modtagesiden, antallet af celler i dekoderen.

Generel visning af en binær foldningskoder

Lad skiftregisteret indeholde m celler, det vil sige, at kodehukommelsen er lig m, omskifteren udfører en pollingcyklus og sender værdierne af informationssymboler, hvor m er et multiplum af k , mens den i en cyklus poller n 2 encoder udgange. Antallet af outputkodesymboler, der påvirkes af en ændring i ét inputinformationssymbol, er . Værdien I all kaldes den samlede længde af kodebegrænsningen . $1\le k<m$ $\geq$ $I_{alle}=\frac{mn}{k}$

Da de korrigerende egenskaber af en bestemt foldningskode bestemmes af længden af kodebegrænsningen og valget af links i skifteregisteret til modulo 2 adderen ( XOR ), er det nødvendigt at specificere strukturen af foldningskoderen . specificere, hvilke bits af skifteregisteret, der er knyttet til hver af modulo 2-adderne ( XOR ).

Tilslutningen af den j-te adder modulo 2 er beskrevet af den j-te genereringssekvens:

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

hvor (4.2) $g_{ij} = \begin{cases} 1,&\text{hvis fase i af register bundet med XOR gate}\\ 0,&\text{i andre tilfælde} \end{cases}$

Typiske parametre for foldningskoder: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.

Indstillingsmetode for foldningskoder

Det er praktisk at specificere en foldningskode ved hjælp af genererende polynomier, som bestemmes af formlen (4.1) i analogi med, hvordan dette gøres for lineære blokcykliske koder . [2]

Generatorpolynomiet definerer fuldstændigt strukturen af den binære koder af foldningskoden. I modsætning til blokkoder , som hver er beskrevet af kun ét genererende polynomium , er en foldningskode beskrevet af flere genererende polynomier. Antallet af polynomier, der beskriver foldningskoden, bestemmes af antallet af outputsymboler n . Lad os repræsentere sekvensen af informationssymboler, der kommer til indkoderen som et polynomium

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

hvor Xi er symbolet for forsinkelsesoperatoren for i -cykler af skifteregisteret, og i = {0, 1 } er binære informationssymboler. Polynomier, der beskriver n sekvenser af kodesymboler, der kommer ind i indkoderkontaktens input og derefter ind i kommunikationskanalen, har formen

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

hvor er binære kodesymboler ved den j - te indgang på indkoderkontakten. ${\displaystyle b_{i}^{j}=\venstre\{{0;1}\højre\))$

Det j - te genererende polynomium af foldningskoden har formen På grund af lineariteten af foldningskoden og den accepterede notation opnår vi desuden . ${\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)$

Ved at bruge repræsentationen af en foldningskode ved hjælp af genererende polynomier, kan man specificere en foldningskode ved hjælp af sekvenser af koefficienter for at generere polynomier skrevet i binær eller oktal form. Den oktale notation er mere kompakt og bruges, når koderens skiftregister er langt.

I det generelle tilfælde vil koefficientsekvensen for det j . genererende polynomium have formen og falde sammen med den genererende kodesekvens (4.1). Så, hvis er en sekvens af kodede symboler, og er en sekvens af kodesymboler ved den j -te indgang på indkoderkontakten, så kan vi skrive for enhver af dem, der vises på -. $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}.

Hvert kodesymbol af outputsekvensen af foldningskodens indkoder bestemmes således af foldningen af den kodede information og genereringssekvensen, som bestemmer navnet på foldningskoderne. Konvolutionskoder er et særligt tilfælde af iterative eller tilbagevendende koder.

Ansøgning

Konvolutionskoder bruges til pålidelig datatransmission: video, mobilkommunikation, satellitkommunikation. De bruges sammen med Reed-Solomon-koden og andre lignende koder. Før opfindelsen af turbokoder var sådanne designs de mest effektive og tilfredsstiller Shannons grænse. Konvolutionskodning bruges også i 802.11a -protokollen på det fysiske MAC-lag for at opnå en ensartet fordeling på 0 og 1 efter signalet passerer gennem scrambleren , som et resultat af hvilket antallet af transmitterede symboler fordobles, og derfor kan opnå en gunstig modtagelse ved den modtagende enhed.

Se også

Noter

↑ Fink L. M. Teori om transmission af diskrete meddelelser
↑ Sagalovich, 2014 , kapitel 4 og 5.

Litteratur

Gallagher R. Informationsteori og pålidelig kommunikation. - M . : Sovjetisk radio, 1974. - 720 s.
Morelos-Zaragoza R. Kunsten at fejlkorrigere kodning. Metoder, algoritmer, anvendelse / pr. fra engelsk. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 s. — (kommunikationens verden). - 2000 eksemplarer. — ISBN 5-94836-035-0 .
Fink L. M. Teori om transmission af diskrete meddelelser. - M. : Sov. radio, 1963. - 576 s.
Nikitin G.I. Konvolutionskoder: Lærebog. - Sankt Petersborg. : Ugler. radio, 2001. - 78 s.
Sagalovich Yu. L. Introduktion til algebraiske koder - 3. udgave, revideret. og yderligere - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Nikitin G.I. Convolutional codes Tutorial
Banket, VL "Signalkodekonstruktioner i telekommunikationssystemer." A: Phoenix (2009).
Kolesnik VD, Poltyrev G. Sh. Kursus i informationsteori. - "Videnskab," kapitel. udg. fysisk og matematisk litteratur, 1982.
Ngok DK Undersøgelse af søgemetoder for optimale foldnings- og perforerede foldningskoder : dis. – Afhandling for graden af kandidat for tekniske videnskaber. St. Petersborg: LETI, 2014.

Ordbøger og encyklopædier	stor kinesisk Britannica (online)