„2.ZH kvíz” változatai közötti eltérés
(Új oldal, tartalma: „{{Kvízoldal|cím=Hírközléselmélet 2.ZH tippelős kérdések|pontozás=+}} == Bináris lineáris hibajavító blokk kódokra igaz hogy: == {{Kvízkérdés|típus=…”) |
|||
3. sor: | 3. sor: | ||
== Bináris lineáris hibajavító blokk kódokra igaz hogy: == | == Bináris lineáris hibajavító blokk kódokra igaz hogy: == | ||
− | {{Kvízkérdés|típus=több|válasz=1,2,4 | + | {{Kvízkérdés|típus=több|válasz=1,2,4}} |
# legalább 1 hiba mindig jelezhető, de a jelezhető hibák száma több is lehet | # 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 jelezhető hibák száma tjel<dmin | ||
# a javítható hibák száma legalább 1, azaz tjav>=1 | # 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 | # 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) | ||
+ | {{Kvízkérdés|típus=több|válasz=2,3,4}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1,4}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1,3}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=4}} | ||
+ | # 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ó | ||
+ | {{Kvízkérdés|típus=több|válasz=1,2}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=4}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=3,4}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1,3}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=4}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1,3}} | ||
+ | # ö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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1}} | ||
+ | # ö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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1,2,3}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=4}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1,3}} | ||
+ | # 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 | ||
+ | {{Kvízkérdés|típus=több|válasz=1,2,3}} | ||
+ | # 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 | ||
+ | |||
+ | |||
+ | ---- |
A lap 2019. április 18., 13:26-kori változata
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