Kódelmélet
Az információelméletben a kódolási elmélet a kódokkal és azok tulajdonságaival, valamint a különféle kommunikációs csatornákon történő szolgálatukkal foglalkozik . Két kommunikációs modell létezik: zajjal és zaj nélkül . Zaj nélkül a forráskódolás elegendő a kommunikációhoz. Zajjal a kommunikáció korrekciós kódokkal lehetséges .
Történelem
Az információk ilyen matematikai meghatározásával Claude Shannon vette át a kódolási elmélet alapszakaszát . Más meghatározások léteznek, de Shannon entrópiája volt a legsikeresebb. Így képes megválaszolni az információelmélet két alapvető kérdését : melyek az információ továbbításához szükséges erőforrások, és mennyi információt lehet megbízhatóan továbbítani.
A kódelmélet a csatornakódolás ezen utolsó kérdésével foglalkozik . Az információelmélet két alapvető kérdésének megválaszolásakor Shannon egyszerűen nem nyújtott be nagyon erős korrekciós kódkészletet . Különösen nem határozott meg olyan kódpéldát, amely eléri a csatornakódolási tétel által biztosított határt.
Ezt az ürességet tölti ki a kódok elmélete. Manapság számos módszer létezik, amelyek jó korrekciós kódok létrehozására irányulnak.
Kód tulajdonságai
A kódokat először egy szimbólummal továbbított információ mennyiségével különböztetjük meg . Mivel a szimmetrikus bináris csatorna a leggyakoribb, gyakran bináris kódot veszünk figyelembe . Vannak azonban trináris kódok és általában q-ary kódok is.
A következő változóneveket többnyire egyezmény szerint használják. egy kódszót tartalmazó kód , vagyis az M dimenzió . A kódszó hosszát jelöljük . Az ilyen kódot kódnak nevezzük .
Hiba észlelése és kijavítása
A legtöbb kódot hibakeresésre vagy hibajavításra használják.
Minimális távolság és dekódolás
A kód minimális távolsága befolyásolja a dekódolási hiba valószínűségét. A minimális távolság fontos paraméter, amelyet jelölni kell . Az ilyen kódot kódnak nevezzük .
Kódcsaládok
Ekvivalens kódokKét kód egyenértékű, ha valamennyi hibajavító tulajdonságuk megegyezik.
A kódok típusaiÁltalában háromféle kód létezik.
- A lineáris kód egy korrekciós kód , amelyre egy vektortér- struktúra van kikötve .
- A ciklikus kód egy olyan korrekciós kód, amelynek szerkezete nagyobb, mint egy vektortéré. Általánosságban elmondható, hogy a kódszavakat polinomnak tekintheti . Példa: a Reed-Salamon kód .
- A nemlineáris kód egy korrekciós kód, amelyet különféle módon lehet felépíteni, anélkül, hogy megszereznénk egy vektortér struktúráját.
Kevés a speciális eset. A triviális kód olyan kód, amely a szó szoros értelmében másolat az eredeti üzenet, így annak jelentéktelenség . A szisztematikus kód egy olyan kód, amelyre a kódolandó üzenet a kódolt üzenetben szerepel.
Ezenkívül bizonyos korrekciós kódok használhatók kvantumkódként .
További fontos kódtípusok:
- algebrai kód
- véletlenszerű kód
A korrekciós kódokat családok szerint is osztályozhatjuk.
- A paritáskód hozzáad egy vagy több paritásbitet az üzenethez.
- Az ismétlő kód minden továbbítandó bit több példányát küldi.
- A Hamming-kódok a legismertebb családok. A bináris Hamming kódok egyenértékűek a ciklikus kódokkal, és néhány nem bináris kód is.
- A Golay-kód egy lineáris kód, amelyet elméletben és a gyakorlatban is fontosnak tartanak.
- A Reed-Müller kód egy lineáris kód, amelynek dekódolási tulajdonságait különösen praktikusnak tartják.
- A BCH kódok a Hamming-kódok általánosításai . Ezek szintén ciklikus kódok. Különleges eset a Reed-Salamon kód .
- A másodfokú maradék kód a másodfokú maradékon alapuló ciklikus kód .
- Egy Goppa-kód, amely a ciklikus kódokhoz hasonlóan egy polinomon alapul, az úgynevezett Goppa-polinom.
- A stabilizáló kód alapul mérése egy szindróma , azaz egy vektor a .
- Az expander kód (in) egy lineáris kód, amellyel továbbra is lehetséges a hibák állandó töredékének kijavítása.
- A Spielman szuperkoncentrátor kód az egyetlen kód, amelyet lineáris időben lehet kódolni és dekódolni.
- A váltakozó kód egy gyakorlati fontosságú lineáris kód.
- A Hadamard-kód egy Hadamard-mátrixból előállított kód .
- Az LDPC kód ritka paritásmátrixú kód.
Új kódokat lehet beszerezni olyan műveletekből, amelyek egy vagy két alapkódot egyesítenek.
- triviális műveletek: lyukasztás vagy rövidítés
- összefűzés: kód Forney , kód Justesen (en)
- termék
A kódok bizonyos osztályait tulajdonságaik alapján is megkülönböztetjük.
- keresztező kód
- elválasztó kód
- (2014) disszimil és kapa = 111110110
Kód és "tervezés"
Kapcsolat van a kódok és a kombinatorikus tervek között .
A kódelmélet fő problémája
Legyen a legnagyobb , amelyhez van kód és -naire. A kódelmélet fő problémája ezen értékek meghatározása.
Forráskódolás
A forráskódolás célja lehet a nyelv ismétlődő információinak, redundanciájának tömörítése . Bármely nyelv esetében figyelembe vehetjük az üzenet entrópiáját , vagyis a továbbított információ mennyiségét. Ez eredményezi a forráskódolási tételt .
Csatornakódolás
A cél redundáns információk hozzáadása egy üzenethez a kommunikációs csatornán jelentkező zaj kompenzálása érdekében . Ez ad okot, hogy a csatorna kódolási tétel , és ez az, hogy ez, hogy mi tartozik az eredetét kódot elmélet .
Néhány kriptográfiai probléma a dekódolás nehézségének feltételezésén alapul .
Algebrai kódelmélet
Az algebrai kódelmélet a kódelmélet azon részterülete, ahol a kódok tulajdonságait algebraikusan fejezik ki. Más szavakkal, a megközelítés algebrai , szemben a hagyományos, valószínűségi megközelítéssel . Főleg tanulmányozzuk:
- a "jó" kódok felépítése, vagyis bizonyos kívánatos paraméterekkel, például:
- a kódszavak hossza
- az érvényes kódszavak teljes száma
- a minimális Hamming távolság két érvényes kódszó között
- ezeknek a kódoknak a hatékony dekódolása
Használja a szövegelemzésben
A kódelemzés akkor hasznos, ha megpróbáljuk dekódolni a titkosítást, ha a használt kód gyenge (pl. César vagy Vigenère kód ). A szöveg statisztikai jellemzőinek kimutatása lehetővé teszi a nyelv megértése nélkül is annak ellenőrzését, hogy egy szövegnek több szerzője van-e (megerősíthetjük, hogy a Papyrus Voynichnak két külön szerzője volt; lásd a megfelelő cikket). Lehetővé teszi Victor Hugo szövegeinek elemzését , és e statisztikai jellemzők révén felismerni írásuk évtizedét. Az IBM Tudományos Központ tanulmányozta Charles de Gaulle beszédeit is, és megmutatta, hogy ezek a beszédek az idők folyamán meghosszabbodtak, kivéve néhány "kritikus" beszédet (mint például a1968. május 30). Stanford Egyetem is , mint a megfelelő szótárakat által Marcel Proust és Paul Valéry . A mérnök, Jean-Jacques Walter is elvégezte ezt az elemzést a Korán szövegén, és megvédett egy állami tézist, amely szerinte több tucat szerző (legalább 30 különböző szerző, valószínűleg 50, legfeljebb 100) eredetileg több nyelven, kétszáz év alatt.
A kitalált irodalomban ez az elmélet a Le Monde újságírójának, Robert Escarpitnek a Le Littératron című könyvében szolgál forgatókönyvként, ahol egy szakember számítógép segítségével konstruálja a kávézókban folytatott beszélgetések során felvetett megjegyzésekből a végső populista beszédet , amely mindenekelőtt a poénokat ébreszti fel. , de apránként félelmetes hatékonyságot mutat.
Hivatkozások
- Előszó (in) Elwyn R. Berlekamp , Algebrai kódolási elmélet , McGraw-Hill , 1968, 466 p.
- Interjú Jean-Jacques Walterrel 2013.10.10. A "Le Grand Witness" című műsorban
- A Korán statisztikai elemzése .
Lásd is
Kapcsolódó cikkek
Bibliográfia
Művek- Jean-Guillaume Dumas, Jean-Louis Roch, Éric Tannier és Sébastien Varrette, Code elmélet (tömörítés, titkosítás, korrekció) , Dunod , 2013 2 nd ed. ( 1 st ed. 2007), 384 p. ( ISBN 978-2-10-059911-0 ) [ online előadás ]
- Bruno Martin, kódolás, rejtjelezés és alkalmazások , Lausanne, Presses polytechniques et universitaire romandes ,2004, 354 p. ( ISBN 978-2-88074-569-1 , online olvasás ).
- Adam Woryna , „ Az előtagkódok arányáról a háromelemes kódkészletben ”, Diszkrét matematika , 1. évf. 343, N o 8,2020Pont n o 111.939 ( DOI 10.1016 / j.disc.2020.111939 ).
Külső linkek
- Christine Bachoc, „ Code course ” , a Bordeaux I. Egyetemen , 2004-2005
- Joël Le Roux, A digitális kommunikáció fogalmai , Polytech Nice-Sophia , 2001
- Yves Denneulin, Jean-Guillaume Dumas, Gregory Mounié, Jean-Louis Roch, Karim Samaké, Eric Tannier, Sébastien Varrette, "A kódok elmélete (természetesen segédanyag )" (2008. szeptember 15-i verzió az Internetes Archívumban ) , az ENSIMAG- on