„2.ZH kvíz” változatai közötti eltérés
Ugrás a navigációhoz
Ugrás a kereséshez
| 1. sor: | 1. sor: | ||
| + | Hírközléselmélet 2.ZH tippelős kvíz | ||
| + | |||
{{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=+}} | ||
| 9. sor: | 11. 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: | 18. 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: | 25. 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: | 32. 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: | 39. 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: | 46. 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: | 53. 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: | 60. 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: | 67. 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: | 74. 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: | 81. 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: | 88. 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: | 95. 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: | 102. 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: | 109. 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 2019. április 18., 13:29-kori változata
Hírközléselmélet 2.ZH tippelős kvíz
Tartalomjegyzék
- 1 Bináris lineáris hibajavító blokk kódokra igaz hogy:
- 2 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)
- 3 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
- 4 Lin. hibajavító blokk kódokra igaz, hogy érvényes kódszavak
- 5 Bináris lineáris hibajavító blokk kódokra igaz hogy bármely két kód
- 6 Egy lineáris hibajavító blokk-kód szisztematikus például, ha a kódszó
- 7 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
- 8 Lineáris hibajavító kódolás esetén dmin
- 9 Lineáris hibajavító kódok konstrukciós törvényei közül a
- 10 Lineáris hibajavító kódolás esetén
- 11 GF(q) prím méretű véges test felett értelmezett lineáris blokk kódok vektoriális ábrázolásakor a vektorok
- 12 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
- 13 A lineáris Hamming kód
- 14 Az (N,K,q) ciklikus hibajavító kódok
- 15 A lineáris ciklikus hibajavító kódok
- 16 Az (N,K,q) ciklikus hibajavító kódok
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
