Lohkokoodi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. tammikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Lohkokoodi on tietojenkäsittelytieteen eräänlainen kanavakoodaus. Se lisää viestin redundanssia niin, että vastaanottaja voi purkaa sen salauksen minimivirheellä (teoreettisesti nolla) edellyttäen, että tiedonsiirtonopeus (lähetettävän tiedon määrä bitteinä sekunnissa) ei ylitä kanavan suorituskykyä .

Lohkokoodin pääominaisuus on, että se on kiinteäpituinen kanavakoodi (toisin kuin tietolähteen koodausmenetelmä, kuten Huffman-koodaus , ja toisin kuin kanavakoodausmenetelmät, kuten konvoluutiokoodaus ("konvoluutiokoodaus)"). Tyypillisesti lohkokoodausjärjestelmä ottaa k - numeroisen koodisanan W syötteenä ja muuntaa sen n - numeroiseksi koodisanaksi C(W) . Tätä koodisanaa kutsutaan lohkoksi.

Lohkokoodaus oli pääasiallinen koodaustyyppi, jota käytettiin varhaisissa matkaviestinjärjestelmissä.

Muodollinen määritelmä

Lohkokoodi on koodi, joka koodaa merkistöjen sekvenssit aakkosesta S koodisanoiksi muuntaen jokaisen merkin S :stä erikseen. Antaa olla luonnollisten lukujen sarja , joista jokainen on pienempi kuin |S| . Jos jokin sana W aakkosesta S kirjoitetaan muodossa , niin W : tä vastaava koodisana , nimittäin C(W) , on: . $(k_{1},k_{2},\ldots ,k_{m})$ $S=\{s_{1},s_{2},\ldots ,s_{n}}\}$ $W=s_{k_{1}}s_{k_{2}}\ldots s_{k_{m}}$ $C(W)=C(s_{k_{1)))C(s_{k_{2)))\ldots C(s_{k_{m)))$

[n, d]

Tehokkuuden (korkeampi tiedonsiirtonopeus) ja korjausominaisuuksien välinen kompromissi voidaan nähdä myös yritettäessä asettaa kiinteää avainsanan pituutta ja kiinteää korjauskykyä (jota edustaa Hamming-etäisyys d ) ja maksimoida avainsanojen kokonaismäärä. [n, d] on avainsanojen enimmäismäärä tietylle avainsanan pituudelle n ja Hamming-etäisyydelle d .

Tietonormit

Kun C on kaksoislohkokoodi, joka koostuu n bitin pituisista A -avainsanoista, C :n informaationormi määritellään seuraavasti:

{\frac {\log _{2}(A)}{n))

Siinä tapauksessa, että avainsanan ensimmäiset k bittiä ovat itsenäisiä informaatiobittejä, tietonormi näyttää tältä:

{\frac {\log _{2}(2^{k})}{n))={\frac {k}{n))

Pallomaiset tiivisteet ja ristikot

Lohkokoodit liittyvät pallomaisen pakkauksen ongelmaan, joka on herättänyt huomiota viime vuosina. Se on helppo visualisoida kahdessa ulottuvuudessa ottamalla kourallinen identtisiä kolikoita ja asettamalla ne pöydälle kuusikulmion muotoon, kuten hunajakennoon. Suurissa mitoissa lohkokoodeja ei kuitenkaan voida visualisoida yhtä helposti. Syvän avaruuden viestinnässä käytetty vahva Golay-koodi käyttää 24 ulottuvuutta. Jos käytetään binääriä (kuten yleensä tehdään), mittaukset viittaavat avainsanan pituuteen, kuten edellä on määritelty.

Koodausteoriassa käytetään N-ulotteisen pallon mallia. Esimerkiksi kuinka monta kolikkoa voidaan asettaa ympyrään pöydän pinnalle tai 3-ulotteisena, kuinka paljon marmoria voidaan sijoittaa maapalloon. Muita näkökohtia ovat koodin valinnassa. Esimerkiksi rajoitettuun suorakaiteen muotoiseen laatikkoon sijoitettu kuusikulmio jättää kulmiin tyhjää tilaa. Mittojen kasvaessa tyhjän tilan osuus pienenee. Mutta tietyissä ulottuvuuksissa koko paikka on täynnä, ja nämä koodit ovat niin sanottuja täydellisiä koodeja. Mutta niitä on hyvin vähän.

Toinen asia, joka usein unohdetaan, on naapureiden määrä, joka yhdellä avainsanalla voi olla. Käytämme jälleen kolikoita esimerkkinä. Ensin pinoamme ne suorakaiteen muotoiseen verkkoon. Jokaisella kolikolla on 4 läheistä naapuria (ja 4 kaukaisimmissa kulmissa). Kuusikulmassa jokaisella kolikolla on 6 läheistä naapuria. Kun lisäämme ulottuvuuksien määrää, lähinaapureiden määrä kasvaa hyvin nopeasti.

Tuloksena on myös niiden polkujen määrän kasvu, joilla kohina pakottaisi vastaanottimen valitsemaan naapurin; siis virhe. Tämä on lohkokoodien ja itse asiassa kaikkien koodien perustavanlaatuinen rajoitus. Yksittäisen naapurin voi olla vaikeampaa aiheuttaa virhettä, mutta naapureiden lukumäärä voi olla tarpeeksi suuri, jotta virheen kokonaistodennäköisyys on todella mahdollista.

Kirjallisuus

J. H van Lint (1992). Johdatus koodausteoriaan. gtm. 86 (2. painos). Springer-Verlag. s. 31. ISBN 3-540-54894-7 .
FJ MacWilliams; NJA Sloane (1977). Virheenkorjauskoodien teoria. Pohjois-Hollanti. s. 35. ISBN 0-444-85193-3 .
Peterson W., Weldon E. Virheenkorjauskoodit. Ed. "Rauha", 1976.