Kooditeoria

Vuonna informaatioteoriaan The koodausteoriaan käsittelee koodien ja niiden ominaisuudet ja niiden kykyä palvella eri viestintäkanavia . Viestintämalleja on kaksi: melun kanssa ja ilman . Ilman kohinaa lähdekoodaus riittää viestintään. Melun avulla viestintä on mahdollista korjauskoodeilla .

Historia

Määrittelemällä tiedot niin matemaattisiksi , Claude Shannon otti koodausteorian perustusvaiheen . Muita määritelmiä on olemassa, mutta Shannonin entropia on ollut menestynein. Siten voidaan vastata kahteen tietoteorian peruskysymykseen : mitkä ovat resurssit, joita tarvitaan tiedon välittämiseen ja kuinka paljon tietoa voidaan siirtää luotettavasti.

Kooditeoria käsittelee tätä viimeistä kysymystä kanavakoodauksesta . Vastaamalla kahteen tietoteorian peruskysymykseen Shannon ei vain toimittanut erittäin tehokasta korjauskoodeja . Erityisesti se ei ole määrittänyt koodiesimerkkiä, joka saavuttaisi sen kanavakoodauslauseen tarjoaman rajan.

Kooditeoria täyttää tämän tyhjiön. Nykyään on olemassa lukuisia menetelmiä, joiden tarkoituksena on tuottaa hyviä korjauskoodeja.

Koodin ominaisuudet

Koodit erotetaan ensin symbolilla välitetyn informaation määrällä . Symmetrinen binary kanava on yleisin, me usein harkitsee binaarikoodin . On kuitenkin myös kolmikoodeja ja yleensä q-ary-koodeja.

Seuraavia muuttujien nimiä käytetään enimmäkseen sopimuksen mukaan. on koodi, joka sisältää koodisanoja , eli ulottuvuutta M. Koodisanan pituus on merkitty . Tällaista koodia kutsutaan koodiksi . $VS$ $M$ $ei$ $(n, M)$

Virheiden havaitseminen ja korjaaminen

Suurinta osaa koodeista käytetään joko virheen havaitsemiseen tai virheen korjaamiseen.

Pienin etäisyys ja dekoodaus

Koodin vähimmäisetäisyys vaikuttaa dekoodausvirheen todennäköisyyteen. Pienin etäisyys on tärkeä parametri, merkitty . Tällaista koodia kutsutaan koodiksi . $d$ $(n, M, d)$

Koodiperheet

Vastaavat koodit

Kaksi koodia ovat samanarvoisia, jos kaikki niiden virheenkorjausominaisuudet ovat samat.

Koodityypit

Koodeja on yleensä kolme tyyppiä.

Lineaarinen koodi on korjata koodi , johon vektori tila rakenne on määrätty .
Syklinen koodi on korjaus koodi, joka on enemmän rakenne kuin vektorin tilaa. Yleensä voit ajatella koodisanoja polynomeina . Esimerkki: Reed-Salomon-koodi .
Epälineaarinen koodi on korjata koodi, joka voidaan rakentaa eri tavoin, ilman saamiseksi rakenne vektorin tilaa.

Erikoistapauksia on pieni määrä. Triviaali koodi on koodi, joka kirjaimellisesti kopioi alkuperäisen viestin, joten sen triviaalisuutta . Systemaattinen koodi on koodi, jonka sanoman koodattu sisältyy koodatun viestin.

Lisäksi tiettyjä korjauskoodeja voidaan käyttää kvanttikoodeina .

Muita tärkeitä koodityyppejä ovat:

algebrallinen koodi
satunnainen koodi

Perheet

Korjauskoodit voidaan luokitella myös perheittäin.

Pariteettikoodi lisää yhden tai useamman pariteettibitin viestiin.
Toista koodi antaa useita kopioita kukin bitti voidaan lähettää.
Hamming-koodit ovat tunnetuimpia perhe. Binaariset Hamming-koodit vastaavat syklisiä koodeja ja jotkut ei-binääriset ovat myös.
Golay-koodi on lineaarinen koodi tärkeäksi teoriassa ja käytännössä.
Reed-Muller -koodi on lineaarinen koodi, jonka dekoodaus ominaisuudet pidetään erityisen käytännöllinen.
BCH koodit ovat yleistys Hamming koodien . Nämä ovat myös syklisiä koodeja. Erityistapaus on Reed-Salomon-koodi .
Neliönjäännös koodi on syklinen koodi neliönjäännös .
Goppa koodi , joka, kuten syklinen koodeja, perustuu polynomi, jota kutsutaan Goppa polynomi.
Stabiloiva koodi perustuu mittaus oireyhtymä , toisin sanoen on vektorin sisään . $F_ {2} ^ {{nk}}$
Laajentimen koodi (in) on lineaarinen koodi, jonka kanssa se on vielä mahdollista korjata vakio-osa virheistä.
Superconcentrateur koodi Spielman ovat vain koodit, jotka voidaan koodata ja dekoodata lineaarisessa ajassa.
Vuorotellen koodi on lineaarinen koodi on käytännön merkitystä.
Hadamard-koodi on koodi generoidaan Hadamard-matriisin .
LDPC- koodi on koodi, jolla on harvinainen pariteettimatriisi.

Koodiyhdistelmät

Uusia koodeja voidaan saada toiminnoista, joissa yhdistetään yksi tai kaksi peruskoodia.

triviaalit toimet: lävistys tai lyhentäminen
ketjutus: koodi Forney , koodi Justesen (en)
tuote

Muut ominaisuudet

Erotamme myös tietyt koodiluokat ominaisuuksiensa mukaan.

leikkaava koodi
erotuskoodi
(2014) dissimile ja kuokka = 111110110

Koodi ja "suunnittelu"

Koodien ja kombinatoristen mallien välillä on yhteys .

Kooditeorian pääongelma

Antaa olla suurin , jolle on koodi ja -naire. Kooditeorian pääongelma on näiden arvojen määrittäminen. $A_ {q} (n, d)$ $M$ $(n, M, d)$ $q$

Lähdekoodaus

Lähdekoodauksen tavoitteena voi olla pakata kielen toistuva tieto, sen redundanssi . Minkä tahansa kielen kohdalla voimme harkita viestin entropiaa , toisin sanoen lähetetyn tiedon määrää. Tästä syntyy lähdekoodauslause .

Kanavakoodaus

Tavoitteena on lisätä redundantteja tietoja viestiin melun kompensoimiseksi viestintäkanavalla . Tämä aiheuttaa kanavankoodauksen lauseen ja juuri tähän, että olemme velkaa alkuperän koodin teorian .

Jotkut salausongelmat perustuvat oletukseen dekoodauksen vaikeudesta .

Algebrallinen kooditeoria

Algebrallinen kooditeoria on kooditeorian alakenttä, jossa koodien ominaisuudet ilmaistaan algebrallisesti. Toisin sanoen lähestymistapa on algebrallinen toisin kuin perinteinen lähestymistapa, joka on todennäköisyysperiaate . Tutkimme pääasiassa:

"hyvien" koodien muodostaminen, toisin sanoen tietyillä toivottavilla parametreilla, kuten:
- koodisanojen pituus
- kelvollisten koodisanojen kokonaismäärä
- pienin Hamming etäisyys kahden voimassa koodisanojen
näiden koodien tehokas dekoodaus

Käyttää tekstianalyysissä

Koodianalyysi on hyödyllinen salaustekstin purkamiseksi, jos käytetty koodi on heikko (esim. César- tai Vigenère- koodi ). Tekstin tilastollisten ominaisuuksien havaitseminen mahdollistaa myös kielen ymmärtämättä tarkistamisen, onko tekstillä ollut enemmän kuin yksi kirjoittaja (voimme siis vahvistaa, että Papyrus Voynichilla oli kaksi erillistä kirjoittajaa; katso vastaava artikkeli). Se antaa myös mahdollisuuden analysoida Victor Hugon tekstejä ja havaita näiden tilastollisten ominaisuuksien avulla niiden kirjoittamisen vuosikymmen. IBM: n tiedekeskus tutki myös Charles de Gaullen puheita ja osoitti, että nämä puheet pidentyivät ajan myötä, lukuun ottamatta muutamia "kriittisiä" puheita (kuten30. toukokuuta 1968). Stanfordin yliopiston myös verrattuna vastaavaan sanastojen esittäjät Marcel Proust ja Paul Valéry . Insinööri Jean-Jacques Walter suoritti myös tämän analyysin Koraanin tekstistä ja tuki valtion väitöskirjaa, jonka mukaan hänen mukaansa alun perin useita kymmeniä kirjoittajia (vähintään 30 erilaista kirjoittajaa, todennäköisesti 50, enintään 100) useilla kielillä kaksisataa vuotta.

Kaunokirjallisuudessa tämä teoria toimii Le Monde -lehden toimittajan Robert Escarpitin kirjassa Le Littératron , jossa asiantuntija käyttää tietokonetta rakentamaan kahviloissa käytyjen keskustelujen aikana esiin tuotuista huomautuksista lopullisen populistisen keskustelun , joka herättää ensinnäkin vitsejä. , mutta vähitellen osoittaa valtavan tehokkuuden.

Viitteet

Johdanto (in) Elwyn R. Berlekamp , Algebrallinen Koodausteoria , McGraw-Hill , 1968, 466 s.
Haastattelu Jean-Jacques Walter 10.8.2013 "Le Grand Witness" -ohjelmassa
Koraanin tilastollinen analyysi .

Katso myös

Aiheeseen liittyvät artikkelit

Bibliografia

Toimii

Jean-Guillaume Dumas, Jean-Louis Roch Éric Tannier Sébastien Varrette, Code teoria (pakkaus, salaus, korjaus) , Dunod , 2013, 2 nd ed. ( 1 st toim. 2007), 384 s. ( ISBN 978-2-10-059911-0 ) [ online-esitys ]
Bruno Martin, koodaus, salaus ja sovellukset , Lausanne, Presses polytechniques et universitaire romandes ,2004, 354 Sivumäärä ( ISBN 978-2-88074-569-1 , lue verkossa ).

Artikkelit

Adam Woryna , " Etuliitekoodien osuudesta kolmen elementin koodien joukossa ", Diskreetti matematiikka , voi. 343, n ° 8,2020, Kohta n o 111939 ( DOI 10,1016 / j.disc.2020.111939 ).

Ulkoiset linkit

Christine Bachoc, ” Code-kurssi ” , Bordeaux I -yliopistossa , 2004-2005
Joël Le Roux, Digitaalisen viestinnän käsitteet , Polytech Nice-Sophia , 2001
Yves Denneulin, Jean-Guillaume Dumas, Gregory Mounié, Jean-Louis Roch, Karim Samaké, Eric Tannier, Sébastien Varrette, "Koodien teoria (moniste)" (versio 15. syyskuuta 2008 Internet-arkistossa ) , ENSIMAGissa