Konvoluutiokoodi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. syyskuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Konvoluutiokoodi on virheenkorjaava koodi , jossa

jokaisella kooderin kellojaksolla syötetyn puoliäärettömän sekvenssin symbolit muunnetaan lähtösekvenssin symboleiksi $k$ $n>k$
myös edelliset merkit ovat mukana muuntamisessa $m$
lineaarisuuden ominaisuus täyttyy (jos kaksi koodattua sekvenssiä ja vastaavat koodijonoja ja , niin koodattu sekvenssi vastaa ). ${\mathbf x}$ ${\mathbf y}$ $\mathbf X$ $\mathbf Y$ $a\mathbf x+b\mathbf y$ $a\mathbf X+b\mathbf Y$

Konvoluutiokoodi on puu- ja ristikkokoodien erikoistapaus .

Origins

Vuonna 1955 L. M. Fink , joka oli tuolloin Leningradin viestintäakatemian osaston johtaja, ehdotti ensimmäistä toistuvaa koodia.

Vuonna 1959 länsimainen asiantuntija Hegelberger ( Hegelbeger ), jolla ei ollut aavistustakaan Neuvostoliiton tutkijoiden työstä koodauksen alalla, "löysi uudelleen" toistuvan koodin ja nimesi sen omalla mukaansa.

Fink itse kirjoitti monografiassa "Theory of Discrete Message Transmission" [1] : "Tässä koodissa koodisymbolien sarjaa ei ole jaettu erillisiin koodiyhdistelmiin. Korjaussymbolit sisällytetään informaatiosymbolivirtaan siten, että jokaisen kahden informaatiosymbolin väliin sijoitetaan yksi korjaussymboli. Merkitään informatiivisia merkkejä kautta ja korjaavia merkkejä saamme seuraavan merkkijonon: $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}\,\pisteet$

Tietosymbolit määritetään lähetetyn viestin mukaan ja korjaavat symbolit muodostetaan seuraavan säännön mukaisesti:

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

jossa on mielivaltainen kokonaisluku, jota kutsutaan koodivaiheeksi ( ). Ilmeisesti, jos jokin korjaava symboli b i vastaanotetaan vahingossa, relaatio (1.1) vastaanotetussa sekvenssissä ei täyty arvolle . Jos tietosymboli vastaanotetaan virheellisesti, relaatio (1.1) ei päde kahdelle arvolle , nimittäin for ja for . Tästä on helppo johtaa dekoodausvirheen korjaussääntö. Hyväksytyssä koodisekvenssissä relaatio (1.1) tarkistetaan jokaiselle . Jos se ei ole tyytyväinen kahteen arvoon ( ja ), ja samanaikaisesti $s$ $s=0,1,2\dots$ $i=k$ $a_{i}$ $k_i$ $k_{1}=is-1$ $k_{2}=i+s$ $b_{k}$ $k$ $k=k_{1}$ $k=k_{2}$

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

silloin tietoelementti on käännettävä. $a_{k_{1}+s+1}$

Ilmeisesti koodin redundanssi on . Sen avulla voit korjata kaikki virheellisesti vastaanotetut merkit, lukuun ottamatta joitakin huonoja yhdistelmiä. Joten jos , se tarjoaa oikean dekoodauksen, kun kahden virheellisesti vastaanotetun symbolin välillä on vähintään kolme (ja joissakin tapauksissa kaksi) oikein vastaanotettua symbolia (sekä informaatio- että testisymbolit otetaan huomioon). $1/2$ $s = 0$

Ei-rekursiivisen kooderin yleinen kaavio

Ei-rekursiivisen konvoluutiokoodin kooderikaavio on esitetty kuviossa 1 . Se koostuu -ary-siirtorekistereistä, joiden pituus on . Jotkut (ehkä kaikki) joidenkin muistisolujen rekisteritulot ja -lähdöt on kytketty useisiin modulo-lisäjiin . Summainten määrä on suurempi kuin siirtorekisterien lukumäärä: $k$ $q$ $m_1. m_2,...,m_k$ $n$ $q$ $n>k$

Kooderin jokaisella kellojaksolla syötetään sen sisääntuloon informaatiosymbolit, jotka syötetään yhdessä siirtorekistereihin tallennettujen symbolien kanssa niiden summaimien tuloihin, joihin on yhteys. Lisäyksen tuloksena on koodisymbolit, jotka ovat valmiita lähetettäväksi. Tällöin jokaisessa siirtorekisterissä tapahtuu siirto: kaikkia soluja siirretään oikealle yhden bitin verran, kun taas vasemmanpuoleiset solut täytetään syötemerkeillä ja oikeimman puoleiset solut pyyhitään pois. Tämän jälkeen lyönti toistetaan. Rekistereiden alkutila tiedetään etukäteen (yleensä nolla). $k$ $n$

Kaikkien siirtorekisterien kokonaispituutta kutsutaan koodirajaksi ja maksimipituutta viiveeksi . $m = \sum_{i=1}^k m_i$ $w = \max\{m_1,...,m_k\}$

Siirtorekisterien arvoja kullakin hetkellä kutsutaan kooderin tilaksi .

Binäärikonvoluutiokooderit

Esityksen selkeyden vuoksi kuvaamme konvoluutiokoodausta vastaavan koodauslaitteen toiminnan mukaisesti.

Konvoluutiokooderi on laite, joka yleensä vastaanottaa k tuloinformaatiosymbolia kussakin toimintajaksossa ja tulostaa n lähtösymbolia kunkin jakson lähdössä. Numeroa kutsutaan suhteelliseksi koodinopeudeksi. k on informaatiosymbolien lukumäärä, n on viestintäkanavalle lähetettyjen symbolien määrä yhden saapumisjakson aikana informaatiosymbolin kooderiin. Tarkasteltavana olevan syklin lähtösymbolit riippuvat m:stä informaatiosymbolista, jotka saapuvat tähän ja edelliseen jaksoon, eli konvoluutiokoodin lähtösymbolit määräytyvät yksiselitteisesti sen tulosymbolien ja tilan mukaan, joka riippuu m - k aiemmasta informaatiosymbolista . Konvoluutiokoodin pääelementit ovat: siirtorekisteri, modulo 2 -summain, kommutaattori. $R={\frac {k}{n}}$

Siirtorekisteri on dynaaminen tallennuslaite, joka tallentaa binäärimerkit 0 ja 1. Koodimuisti määrittää liipaisusolujen m määrän siirtorekisterissä. Kun siirtorekisterin sisääntuloon saapuu uusi tietomerkki, oikeanpuoleisimpaan bittiin tallennettu merkki poistetaan rekisteristä ja nollataan. Loput merkit siirretään yhden numeron verran oikealle ja siten vapautetaan vasemmanpuoleisin numero, jonne uusi tietomerkki saapuu.

Modulo 2 -summain laskee yhteen siihen saapuvat symbolit 1 ja 0. Modulo 2:n summaussääntö on seuraava: binäärisymbolien summa on 0, jos syötteisiin tulevien symbolien ykkösten määrä on parillinen, ja yhtä suuri kuin 1, jos tämä luku on outoa.

Kytkin lukee peräkkäin sen tuloihin saapuvat symbolit ja asettaa koodisymbolien sarjan viestintäkanavalle lähdössä. Lohkokoodien analogisesti konvoluutiokoodit voidaan luokitella systemaattisiin ja ei-systeemisiin.

Systemaattinen konvoluutiokoodi on koodi, joka sisältää koodisymbolien lähtöjonossa sen informaatiosymbolien sarjan, joka on luonut sen. Muussa tapauksessa koodia kutsutaan ei-systeemiseksi.

Konvoluutiokoodien parametrit ja ominaisuudet

Konvoluutiokoodauksella informaatiosekvenssien muuntaminen lähtö- ja koodisekvensseiksi tapahtuu jatkuvasti. Binäärinen konvoluutiokooderi sisältää m bitin siirtorekisterin ja modulo 2 -summaimet koodisymbolien muodostamiseksi lähtösekvenssissä. Summainten tulot on kytketty tiettyihin rekisterin bitteihin. Lähtökytkin määrittää järjestyksen, jossa koodisymbolit lähetetään viestintäkanavalle. Sitten koodirakenne määräytyy seuraavien ominaisuuksien perusteella.

Enkooderin sisääntuloon saapuvien informaatiosymbolien määrä yhdessä jaksossa on k.
Symbolien lukumäärä kooderin lähdössä on n, mikä vastaa k tulosymbolia jakson aikana.
Koodinopeus määräytyy suhteella R=k/n ja se kuvaa koodauksen aikana esiintyvää redundanssia.
Koodin redundanssi $\vartheta = 1 - R$
Koodimuistin (koodirajoitteen syötepituus tai koodisanan informaatiopituus) määrää generoivan polynomin maksimiaste generointimatriisissa G(X): $l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$
Konvoluutiokoodin merkintä on useimmissa tapauksissa merkitty (n, k, l), mutta variaatiot ovat mahdollisia.
Binäärikoodisekvenssien paino w määräytyy tähän sekvenssiin tai koodisanoihin sisältyvien "yksiköiden" lukumäärän mukaan.
Koodietäisyys näyttää eron i:nnen ja j:nnen koodiyhdistelmien välillä, mikäli ne ovat samanpituisia. Kahdessa binäärikoodiyhdistelmässä koodin etäisyys on sama kuin niiden merkkien määrä, jotka eivät täsmää niissä. Yleisesti koodin etäisyys voidaan määritellä kokonaistuloksena modulo 2 -lisäyksestä koodiyhdistelmien samannimisille biteille , missä ja ovat koodiyhdistelmien i ja j k:nnet symbolit; L on koodiyhdistelmän pituus. $d$
$d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$ $k_{i,j}$ $k_{jk}$
Koodin vähimmäisetäisyys on vakiopituisten koodisanojen joukon pienin Hamming-etäisyys . Sen löytämiseksi on tarpeen luetella kaikki mahdolliset koodiyhdistelmien parit. Sitten saamme . $d_{min}$ $d_{min} = \min d_{ij}$

Mutta! Tämä määritelmä pätee vakiopituisille lohkokoodeille. Konvoluutiokoodit ovat jatkuvia ja niille on tunnusomaista monet minimietäisyydet, jotka määräytyvät koodisekvenssien alkusegmenttien pituuksien perusteella, joiden välillä otetaan pienin etäisyys. Prosessoitavaksi vastaanotetun segmentin pituuden L symbolien lukumäärä määrää vastaanottopuolella dekooderissa olevien solujen lukumäärän.

Yleinen näkymä binäärikonvoluutiokooderista

Olkoon siirtorekisterissä m solua, eli koodimuisti on yhtä suuri kuin m, kytkin suorittaa yhden kyselysyklin välittäen informaatiosymbolien arvot, missä m on k :n kerrannainen , kun taas yhdessä syklissä se pollaa n 2 enkooderin lähtöä. Niiden lähtökoodisymbolien lukumäärä, joihin yhden tuloinformaatiosymbolin muutos vaikuttaa, on . Arvoa I all kutsutaan koodirajoitteen kokonaispituudeksi . $1\le k<m$ $\geq$ $I_{all}=\frac{mn}{k}$

Koska tietyn konvoluutiokoodin korjaavat ominaisuudet määräytyvät koodirajoitteen pituuden ja siirtorekisterin linkkien valinnan mukaan modulo 2 -summaimeen ( XOR ), konvoluutiokooderin rakenteen määrittelemiseksi on tarpeen määrittää, mitkä siirtorekisterin bitit liittyvät kuhunkin modulo 2 -summaimeen ( XOR ).

j:nnen summaimen modulo 2 kytkentä kuvataan j:nnellä generointisekvenssillä:

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

missä (4.2) $g_{ij} = \begin{cases} 1,&\text{jos rekisterin vaihe i on sidottu XOR-porttiin}\\ 0,&\teksti{muissa tapauksissa} \end{cases}$

Konvoluutiokoodien tyypilliset parametrit: k, n= 1,2,…,8; R = k/n = 1/4,…, 7/8; m = 2,…,10.

Konvoluutiokoodien asetusmenetelmä

On kätevää määrittää konvoluutiokoodi generoimalla polynomeja, jotka määritetään kaavan (4.1) muodossa analogisesti sen kanssa, miten tämä tehdään lineaarisille lohkosyklisille koodeille . [2]

Generaattoripolynomi määrittelee täysin konvoluutiokoodin binäärikooderin rakenteen. Toisin kuin lohkokoodit , joista jokaista kuvaa vain yksi generoiva polynomi , konvoluutiokoodia kuvataan useilla generoivilla polynomeilla. Konvoluutiokoodia kuvaavien polynomien lukumäärä määräytyy lähtösymbolien lukumäärän n mukaan . Esitetään enkooderin sisäänmenoon tuleva tietosymbolien sarja polynomina

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

missä X i on viiveoperaattorin symboli siirtorekisterin i jaksolle, ja i = {0, 1} ovat informaation binäärisymboleja. Polynomit, jotka kuvaavat n koodisymbolisarjaa, jotka tulevat enkooderikytkimen tuloon ja sitten viestintäkanavaan, ovat muotoa

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

missä ovat binäärikoodisymbolit kooderikytkimen j :nnessä sisääntulossa. ${\displaystyle b_{i}^{j}=\left\{{0;1}\oikea\))$

Konvoluutiokoodin j : nnellä generoivalla polynomilla on muoto Lisäksi konvoluutiokoodin lineaarisuuden ja hyväksytyn merkintätavan ansiosta saamme . ${\displaystyle G_{j}(X)=g_{0}+g_{1}X+g_{2}X^{2}+\pisteet +g_{m-1}X^{m-1))$ $g_{i}={0;1}$ $B_j(X) = G_j(X) A(X)$

Konvoluutiokoodin esitystä käyttämällä polynomeja generoimalla voidaan määrittää konvoluutiokoodi binääri- tai oktaalimuotoon kirjoitettujen polynomien generointikertoimien avulla. Oktaalimerkintä on kompaktimpi ja sitä käytetään, kun kooderin siirtorekisteri on pitkä.

Yleisessä tapauksessa j :nnen generoivan polynomin kertoimien sekvenssi on muotoa ja yhtyy koodin generoivan sekvenssin (4.1) kanssa. Sitten, jos on koodattujen symbolien sekvenssi ja koodisymbolien sarja enkooderikytkimen j : nnessä sisääntulossa, niin mille tahansa niistä, jotka esiintyvät -: nnella hetkellä ( ), voimme kirjoittaa $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$ ${\näyttötyyli \mu =0,1,2,\pisteet }$

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

Siten jokainen konvoluutiokoodin kooderin lähtösekvenssin koodisymboli määräytyy koodatun informaation konvoluution ja generoivan sekvenssin mukaan, joka määrittää konvoluutiokoodien nimet. Konvoluutiokoodit ovat iteratiivisten tai toistuvien koodien erikoistapaus.

Sovellus

Konvoluutiokoodeja käytetään luotettavaan tiedonsiirtoon: video, matkaviestintä, satelliittiviestintä. Niitä käytetään yhdessä Reed-Solomon-koodin ja muiden vastaavien koodien kanssa. Ennen turbokoodien keksimistä tällaiset mallit olivat tehokkaimpia ja täyttävät Shannonin rajan. Konvoluutiokoodausta käytetään myös 802.11a -protokollassa fyysisellä MAC-kerroksella tasaisen 0:n ja 1:n jakautumisen saavuttamiseksi sen jälkeen, kun signaali kulkee sekoituslaitteen läpi , minkä seurauksena lähetettyjen symbolien määrä kaksinkertaistuu ja siksi me voi saavuttaa suotuisan vastaanoton vastaanottavassa laitteessa.

Katso myös

Muistiinpanot

↑ Fink L. M. Diskreettien viestien lähettämisen teoria
↑ Sagalovich, 2014 , luvut 4 ja 5.

Kirjallisuus

Gallagher R. Tietoteoria ja luotettava viestintä. - M . : Neuvostoliiton radio, 1974. - 720 s.
Morelos-Zaragoza R. Virheenkorjauskoodauksen taito. Menetelmät, algoritmit, sovellus / per. englannista. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 s. — (Viestintämaailma). - 2000 kappaletta. — ISBN 5-94836-035-0 .
Fink L. M. Diskreettien viestien lähettämisen teoria. - M . : Sov. radio, 1963. - 576 s.
Nikitin G.I. Konvoluutiokoodit: Oppikirja. - Pietari. : Pöllöt. radio, 2001. - 78 s.
Sagalovich Yu. L. Johdatus algebrallisiin koodeihin - 3. painos, tarkistettu. ja ylimääräistä - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Nikitin G.I. Konvoluutiokoodit opetusohjelma
Juhlatilaisuus, VL "Signaalikoodirakenteet tietoliikennejärjestelmissä." V: Phoenix (2009).
Kolesnik VD, Poltyrev G. Sh. Tiedon teorian kurssi. - "Tiede", luku. toim. fyysinen ja matemaattinen kirjallisuus, 1982.
Ngok DK Optimaalisen konvoluutiokoodin ja rei'itetyn konvoluutiokoodin hakumenetelmien tutkimus: dis. – Väitös teknisten tieteiden kandidaatin tutkinnosta. Pietari: LETI, 2014.

Sanakirjat ja tietosanakirjat	iso kiinalainen Britannica (verkossa)