„2.ZH kvíz” változatai közötti eltérés
A VIK Wikiből
Nincs szerkesztési összefoglaló |
Nincs szerkesztési összefoglaló |
||
| (Egy közbenső módosítás ugyanattól a felhasználótól nincs mutatva) | |||
| 1. sor: | 1. sor: | ||
{{Kvízoldal|cím=Hírközléselmélet 2.ZH tippelős kérdések|pontozás=+}} | {{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: == | == Bináris lineáris hibajavító blokk kódokra igaz hogy: == | ||
| 9. sor: | 8. sor: | ||
# 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) | == 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}} | {{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 | # csak akkor határozható meg ha X és Y eloszlása megegyezik | ||
| 16. sor: | 15. sor: | ||
# D(P(X,Y) || P(X)P(Y)) = 0, ha X és Y függetlenek | # 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 | == 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}} | {{Kvízkérdés|típus=több|válasz=1,4}} | ||
# K sorból és N oszlopból áll | # K sorból és N oszlopból áll | ||
| 23. sor: | 22. sor: | ||
# szisztematikus kód esetén minden esetben tartalmazza a K x 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 | == Lin. hibajavító blokk kódokra igaz, hogy érvényes kódszavak == | ||
{{Kvízkérdés|típus=több|válasz=1,3}} | {{Kvízkérdés|típus=több|válasz=1,3}} | ||
# a kódtér egy lineáris alterét képezik | # a kódtér egy lineáris alterét képezik | ||
| 30. sor: | 29. sor: | ||
# aritmetikai összege megegyezik a kódtér dimenziójával | # 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 | == 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}} | {{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ága minimális, azaz 0 hogy 0 hiba maradjon azaz mindent ki tudjuk javítani | ||
| 37. sor: | 36. sor: | ||
# kivéve a 0 vektor kódot, (N=3, K=2) esetben a kódok bázisát alkotja | # 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ó | == 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}} | {{Kvízkérdés|típus=több|válasz=1,2}} | ||
# eleje azonos az üzenetszóval | # eleje azonos az üzenetszóval | ||
| 44. sor: | 43. sor: | ||
# csak az üzenetszó szimbólumait 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 | == 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}} | {{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) | # K sorból és N oszlopból vagy K oszlopból és N sorból áll (N-K)*N vagy N*(N-K) | ||
| 51. sor: | 50. sor: | ||
# szisztematikus kód esetén tartalmazza az (N-K)x(N-K) méretű I egységmátrixot | # 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 | == Lineáris hibajavító kódolás esetén dmin == | ||
{{Kvízkérdés|típus=több|válasz=3,4}} | {{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ággal egyenlő. | ||
| 58. sor: | 57. sor: | ||
# jelezhető hibák számánál feltétlenül nagyobb. | # 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 | == 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}} | {{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á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. | ||
| 65. sor: | 64. sor: | ||
# perfekt kód esetén az N dimenziós, q-áris kódtér minden pontja érvényes kódszó. | # 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 | == Lineáris hibajavító kódolás esetén == | ||
{{Kvízkérdés|típus=több|válasz=4}} | {{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 hibát észlelhetünk, hiszen hiba esetén az adott érvényes kódvektortól eltérő vektort veszünk. | ||
| 72. sor: | 71. sor: | ||
# 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 | # 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 | == 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}} | {{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ánként modulo q operációval végezzük | ||
| 79. sor: | 78. sor: | ||
# szorzatát a vektorkoordinátákat konvolválva és modulo q operációt alkalmazva képezzü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 | == 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}} | {{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 az azonos fokú tagok együtthatóinak modulo q összegzésével végezzük | ||
| 86. sor: | 85. sor: | ||
# szorzá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 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 | == A lineáris Hamming kód == | ||
{{Kvízkérdés|típus=több|válasz=1,2,3}} | {{Kvízkérdés|típus=több|válasz=1,2,3}} | ||
# bináris esetben egy hibát képes javítani | # bináris esetben egy hibát képes javítani | ||
| 93. sor: | 92. sor: | ||
# bináris esetben perfekt kód is lehet de nem feltétlenül az | # bináris esetben perfekt kód is lehet de nem feltétlenül az | ||
Az (N,K,q) ciklikus hibajavító kódok | == Az (N,K,q) ciklikus hibajavító kódok == | ||
{{Kvízkérdés|típus=több|válasz=4}} | {{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 bináris lineáris kódok, hiszem a linearitás miatt q=2 | ||
| 100. sor: | 99. sor: | ||
# 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 | # 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 | == A lineáris ciklikus hibajavító kódok == | ||
{{Kvízkérdés|típus=több|válasz=1,3}} | {{Kvízkérdés|típus=több|válasz=1,3}} | ||
# kódszavai egymás ciklikus eltoltjai | # kódszavai egymás ciklikus eltoltjai | ||
| 107. sor: | 106. sor: | ||
# a ciklikus eltolás miatt sohasem lehetnek szisztematikusak | # a ciklikus eltolás miatt sohasem lehetnek szisztematikusak | ||
Az (N,K,q) ciklikus hibajavító kódok | == Az (N,K,q) ciklikus hibajavító kódok == | ||
{{Kvízkérdés|típus=több|válasz=1,2,3}} | {{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 | # képezhetőek a GF(q) véges test felett értelmezett N-K fokú generátor polinomokkal | ||
A lap jelenlegi, 2019. április 18., 14:30-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
