Hírközléselmélet - 2.ZH kvíz
A VIK Wikiből
Bináris lineáris hibajavító blokk kódokra igaz hogy:
- legalább 1 hiba mindig jelezhető, de a jelezhető hibák száma több is lehet
- a jelezhető hibák száma tjel<dmin
- a javítható hibák száma legalább 1, azaz tjav>=1
- javítható törléses hibák száma ttör = dmin-1
Azonos eseménytér felett értelmezett két diszkrét valószínűségi változó, X és Y esetén a relatív entrópia (Kullback-Leibler távolság)
- csak akkor határozható meg ha X és Y eloszlása megegyezik
- D(P(X)) || P(Y)) a P(X) és P(Y) eloszlások “hasonlóságának mértéke
- D(P(X,Y) || P(Y,X)) = 0 bármely P(X) és P(Y) eloszlás esetén
- D(P(X,Y) || P(X)P(Y)) = 0, ha X és Y függetlenek
Az Rc=K/N kódarányú (N,K,q) lineáris hibajavító blokk kód G generátor mátrixa c=u*G kódgenerálás esetén
- K sorból és N oszlopból áll
- K oszlopból és N sorból áll
- szisztematikus kód esetén tartalmazza az (N-K)x(N-K) méretű I egységmátrixot
- szisztematikus kód esetén minden esetben tartalmazza a K x K méretű I egységmátrixot
Lin. hibajavító blokk kódokra igaz, hogy érvényes kódszavak
- a kódtér egy lineáris alterét képezik
- kódteret teljes mértékben kitöltik
- a kódtér aritmetikai műveletekre zárt részét képezik
- aritmetikai összege megegyezik a kódtér dimenziójával
Bináris lineáris hibajavító blokk kódokra igaz hogy bármely két kód
- Hamming távolsága minimális, azaz 0 hogy 0 hiba maradjon azaz mindent ki tudjuk javítani
- Hamming távolság maximális
- Lineáris kombinációjával (N=3, K=2) esetben az összes többi kód előállítható
- kivéve a 0 vektor kódot, (N=3, K=2) esetben a kódok bázisát alkotja
Egy lineáris hibajavító blokk-kód szisztematikus például, ha a kódszó
- eleje azonos az üzenetszóval
- vége azonos az üzenet szóval
- a paritásszimbólumokat az üzenet szimbólumaival váltakozva tartalmazza
- csak az üzenetszó szimbólumait tartalmazza
Az Rc=K/N kódarányú (N,K,q) lineáris hibajavító blokk kód H paritásellenőrző mátrixa C=u*G kódgenerálás esetén
- K sorból és N oszlopból vagy K oszlopból és N sorból áll (N-K)*N vagy N*(N-K)
- az s szindróma vektor csak hibamentes esetben egyezik meg a 0 vektorral
- az s szindróma vektor a javítható nem törléses hibák számával megegyezik
- szisztematikus kód esetén tartalmazza az (N-K)x(N-K) méretű I egységmátrixot
Lineáris hibajavító kódolás esetén dmin
- bármely két kódszó közötti Hamming távolsággal egyenlő.
- bármely két kódszó közötti Hamming távolság maximumával egyenlő.
- bármely két kódszó közötti Hamming távolság minimumával egyenlő.
- jelezhető hibák számánál feltétlenül nagyobb.
Lineáris hibajavító kódok konstrukciós törvényei közül a
- Singleton korlát adott q, dmin és kódszó hossz mellett a kódszavak (ezzel persze az üzenetszavak) számának felső határát szabja meg.
- Singleton korlátot kielégítő összes kód maximális távolságú (MDS) kód.
- Hamming korlát adott hibajavító képesség mellett a kódparaméterek (N,K,q) értékeire ad korlátozó összefüggést.
- perfekt kód esetén az N dimenziós, q-áris kódtér minden pontja érvényes kódszó.
Lineáris hibajavító kódolás esetén
- minden hibát észlelhetünk, hiszen hiba esetén az adott érvényes kódvektortól eltérő vektort veszünk.
- minden olyan hibát észlelünk, ahol az adott és a vett vektorok Hamming távolsága megegyezik a dmin kódtávolsággal.
- bináris esetben a törléses hibák (akár több is) feltétlenül kijavíthatóak, hiszen csak invertálni kell a hibás biteket.
- szükségszerűen a kódtér minden elemére igaz, hogy az vagy egy érvényes kódszó, vagy egy ilyen döntési kódalterének eleme, ha a kód perfekt
GF(q) prím méretű véges test felett értelmezett lineáris blokk kódok vektoriális ábrázolásakor a vektorok
- összegzését vektorkoordinátánként modulo q operációval végezzük
- összegzését vektorkoordináták konvulúciójával végezzük
- konstanssal szorzást vektorkoordinátánként modulo q operációval végezzük
- szorzatát a vektorkoordinátákat konvolválva és modulo q operációt alkalmazva képezzük
GF(q) prím hatvány méretű véges test felett értelmezett lineáris blokk kódok polinomos ábrázolásakor (a(x)=a0+ay*x+a2*x^2+...) a polinomok
- összegzését az azonos fokú tagok együtthatóinak modulo q összegzésével végezzük
- összegzését a (a(x)+b(x)) mod p(x) művelettel végezzük, ahol p(x) egy q-ad fokú polinom
- szorzását az azonos fokú tagok együtthatóinak modulo q szorzatával végezzük
- szorzását a (a(x)+b(x)) mod p(x) művelettel végezzük, ahol p(x) egy q-ad fokú polinom
A lineáris Hamming kód
- bináris esetben egy hibát képes javítani
- nem bináris esetben egy hibát képes javítani
- esetén mindig teljesül, hogy a kódtér minden eleme valamely érvényes kódszó döntési kódalterének is eleme egyben
- bináris esetben perfekt kód is lehet de nem feltétlenül az
Az (N,K,q) ciklikus hibajavító kódok
- minden esetben bináris lineáris kódok, hiszem a linearitás miatt q=2
- minden esetben nem bináris lineáris kódok, hiszem a linearitás miatt q>2
- generálása a GF(q) felett értelmezett x^N-1 polinommal, mint generátor polinommal történik
- generálása a GF(q) felett értelmezett x^N-1 polinom bármelyik N-K-ad fokú osztó polinomjával, mint generátor polinommal történhet
A lineáris ciklikus hibajavító kódok
- kódszavai egymás ciklikus eltoltjai
- kódszavai közötti Hamming távolságok bináris esetben minimálisak, hiszem azok egymás ciklikus eltoltjai
- családjában léteznek szisztematikusak is
- a ciklikus eltolás miatt sohasem lehetnek szisztematikusak
Az (N,K,q) ciklikus hibajavító kódok
- képezhetőek a GF(q) véges test felett értelmezett N-K fokú generátor polinomokkal
- esetén, ha egy kódszó g(x) generátor polinommal generált, akkor annak ciklikus eltoltja is a g(x) polinommal generált
- családjába tartoznak a CRC kódok is
- esetén az üzenetszavak ciklikus eltoltjai alkotják a kódszavakat
