A kódnak meg kell felelnie az egyértelmű dekódolás tulajdonságának. EGE az informatikában, A9. Feladat, Polyakov K

  téma: Kódolás és dekódolás

  Ellenőrizze az elemeket : Képes kódolni és de kódolja az információt

Elméleti anyag :

  kódolás  - az információ egyik nyelvről a másikra történő fordítása (más szimbólumok rendszerének írása, másik ábécé).

A kódolt üzenet a kezdetektől egyedileg dekódolható, ha  Fano állapot: egy kódszó nem egy másik kódszó kezdete.

A kódolt üzenet a dátumtól függetlenül egyedileg dekódolható, ha  fordított fano állapot: egy kódszó nem egy másik kódszó vége.

A Fano állapot elégséges, de nem szükséges feltétel az egyértelmű dekódoláshoz.

Feladat példa:

Az A, B, C, D és D betűkből álló szekvencia kódolásához úgy döntöttünk, hogy egy egyenetlen bináris kódot használunk, amely lehetővé teszi számunkra, hogy a kommunikációs csatorna fogadó oldalán megjelenő bináris szekvenciát egyedileg dekódoljuk. Az alkalmazott kód A - 1, B - 000, B - 001, D - 011 volt. Adja meg a D. betű kódszavát

A kódnak meg kell felelnie az egyértelmű dekódolás tulajdonságának.

Általános megközelítés:

A Fano feltétele vagy logikus érvelés használata a válasz megtalálásához.

megoldás:

1) 00 - azóta sérti a Fano állapotát a kódlánc egybeesik a B = 000 és B = 001 kezdetével. Lehetetlen a 000000 lánc egyértelműen dekódolni: lehet DDD vagy BB, így az első opció nem illeszkedik

2) 01 - sérti a Fano állapotát a kódlánc egybeesik a T = 011 kezdetével.  H lehetetlen a 011 lánc egyértelműen dekódolása: lehet YES vagy G, így a második opció nem megfelelő

3) 11 - megsérti a Fano állapotát a kódlánc egybeesik az A = 1. kezdettel. Nlehetetlen a 111 lánc egyértelműen dekódolni: ez lehet YES vagy AAA; a harmadik opció nem illik

4) 010 - A Fano-állapot nem sérült.

Válasz: 4) 010

Feladatok a képzéshez:

1) Az A, B, C, D betűből álló üzenet kommunikációs csatornáján történő továbbítására úgy döntöttek, hogy egy hosszúságú kódot használnak: A = 00, B = 11, C = 100. Hogyan kell a G betűt kódolni úgy, hogy a kód hossza minimális legyen, és a kódolt üzenet egy-egy-egy megosztása megengedett?

2) Az A, B, C, D betűből álló üzenet kommunikációs csatornáján történő továbbítására úgy döntöttek, hogy egy hosszúságú kódot használnak: A = 1, B = 000, C = 001. Hogyan kell a G betűt kódolni úgy, hogy a kód hossza minimális legyen, és a kódolt üzenet egy-egy-egy megosztása megengedett?

3) Az A, B, C, D és D betűkből álló szekvencia kódolásához egy egyenlőtlen bináris kódot használunk, amely lehetővé teszi az eredményül kapott bináris szekvencia egyedi dekódolását. Ez a kód: A - 10, B - 11, B - 000, D - 001, D - 011. Lehet-e lerövidíteni a betűkód egyik hosszát, hogy a kódot egyértelműen dekódolni lehessen? A többi betű kódjait nem szabad megváltoztatni. Válassza ki a helyes választ.

1) lehetetlen

2) a B - 1 betű esetében

3) a B - 00 betű esetében

4) a D-01

4) Az A, B, C, D és D betűkből álló bizonyos szekvencia kódolásához egy egyenlőtlen bináris kódot használunk, amely lehetővé teszi az eredményül kapott bináris szekvencia egyértelmű meghatározását. Ez a kód: A - 11, B - 10, B - 011, D - 000, D - 001. Lehet-e lerövidíteni a betűkód egyik hosszát, hogy a kódot egyértelműen dekódolni lehessen? A többi betű kódjait nem szabad megváltoztatni. Válassza ki a helyes választ.

1) a G-00 betűre

2) lehetetlen

3) a B-01

4) a B - 1 betű esetében

5) Az A, B, C, D és D betűkből álló szekvencia kódolásához egy egyenlőtlen bináris kódot használunk, amely lehetővé teszi az eredményül kapott bináris szekvencia egyedi dekódolását. Itt van ez a kód: A - 10, B - 001, B - 0001, D - 110, D - 111. Lehet-e lerövidíteni a betűkód egyik hosszát, hogy a kódot egyértelműen dekódolni lehessen? A többi betű kódjait nem szabad megváltoztatni. Válassza ki a helyes választ.

1) a G-11

2) lehetetlen

3) a B-000

Az A, B, C, D, D és E betűkből álló bizonyos szekvencia kódolásához úgy döntöttünk, hogy egy egyenlőtlen bináris kódot használunk, amely kielégíti a Fano feltételt. Az A betű esetében a 0 kódszót használtuk; B betű esetén a 10. kódszó. Mi a legkisebb lehetséges összege a hat kódszó hosszának?
Megjegyzés. A Fano feltétel azt jelenti, hogy egyetlen kódszó nem egy másik kódszó kezdete. Ez lehetővé teszi a kódolt üzenetek egyértelmű visszafejtését.

Demonstrációs lehetőség EGE 2017 - 5. feladatszám

megoldás:

A kódszavak megtalálásához ezt a táblázatot fogjuk használni.

Ha a többi betű kódjai 0-tól kezdődnek, akkor az A = 0 betű kódja lesz a kódjaik kezdete, így ez az opció nem megfelelő. Ha B = 10 kód, akkor a C, D, D, E betűk kódjai 11-től kezdődnek. 4 különböző kód megszerzéséhez 4 karakterből álló kódokat kell használni (1111, 1110, 1101, 1100).

0	1
	1
	1		0
	1	0	1	0

A - 0 (1 karakter)
  B - 10 (2 karakter)
  B - 1100 (4 karakter)
  G - 1101 (4 karakter)
  D - 1110 (4 karakter)
  E - 1111 (4 karakter)

1+2+4+4+4+4 = 19

Válasz: 19

Demonstrációs lehetőség EGE 2016 - 5. feladatszám

A kommunikációs csatorna csak négy betűt tartalmazó üzeneteket küld: P, O, C, T; Az átvitelhez bináris kódot használunk, amely lehetővé teszi az egyértelmű dekódolást. A T, O, P betűk esetében a következő kódszavakat használjuk: T: 111, O: 0, P: 100.

Adja meg a C betű legrövidebb kódszavát, amelyben a kód lehetővé teszi az egyértelmű dekódolást. Ha több ilyen kód van, akkor adja meg a legalacsonyabb számértékű kódot.

megoldás:

A kódszavak megtalálásához ezt a rendszert fogjuk használni.

Ha a többi betű kódja kezdődik 0 betűkód Oh=0   a kódok kezdete lesz, ezért ez az opció nem megfelelő. Mivel a levél kódja P=100 és a betűkód T =111 akkor a levél C  nem kezdheti meg és nem fejezheti be ezeket a számokat.

Válasz: 101

Az A, B, C és D betűből álló üzenet kódolásához a bináris kód hosszúságú:

Ha ily módon a GAVBGV karakterek sorozatát kódolja és az eredményt hexadecimális kódban írja, akkor:

1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16

megoldás:

GAVBGV = 0110001011011010

0110	0010	1101	1010
6	2	D	A

Válasz: 4

A fekete-fehér bittérképes képet sorról sorra kódolja, a bal felső saroktól kezdve és a jobb alsó sarokban. A kódolás során az 1 jelzi a fekete értéket, a 0 pedig fehér.

A tömörség érdekében az eredményt oktális jelöléssel rögzítettük. Válassza ki a helyes kódbevitelt.

1) 57414 2) 53414 3) 53412 4) 53012

megoldás:

1	0	1	0	1
1	1	0	0	0
0	1	0	1	0

101	011	100	001	010
5	3	4	1	2

Válasz: 3

A számok zajos csatornán keresztüli továbbításához a paritásellenőrző kódot használják. Mindegyik számjegye bináris ábrázolással van ellátva, 4-es hosszúságú nullákkal, és a moduló 2-es elemek összege hozzáadódik a kapott szekvenciához (például, ha 23-at haladunk, akkor a 0010100110 szekvenciát kapjuk). Határozzuk meg, hogy a csatornán keresztül melyik számot küldték 01100010100100100110 formátumban?

1) 6543 2) 62926 3) 62612 4) 3456

megoldás:

01100010100100100110

01100	01010	01001	00110
6	5	4	3

Válasz: 1

Az O, L, A, G, K betűk kódolásához a 0, 1, 2, 3 és 4 számok bináris kódjait használjuk (egy nem jelentéktelen nulla egybites ábrázolás esetén). Ha ezt a módszert kódolják a VOKOLKA karakterek sorozata és az eredményt hexadecimális kódban írja, akkor:

1) 4531253 2) 9876 3) E832 4) 238E

megoldás:

Oh	L	A	W	K
0=00	1=01	2=10	3=11	4=100

COUNT = 1110100000110010

1110	1000	0011	0010
E	8	3	2

Válasz: 3

Az A, B, C, D betűből álló üzenet kommunikációs csatornáján történő továbbítására úgy döntöttek, hogy egy hosszúságú kódot használnak: A = 00, B = 11, C = 100. Hogyan kell a G betűt kódolni úgy, hogy a kód hossza minimális legyen, és a kódolt üzenet egy-egy-egy megosztása megengedett?

1) 010 2) 0 3) 01 4) 011

megoldás:

A = 00, B = 11, C = 100, D =?

Válasz: 3

Az A, B, C, D és D betűkből álló szekvencia kódolásához úgy döntöttünk, hogy egy egyenetlen bináris kódot használunk, amely lehetővé teszi számunkra, hogy a kommunikációs csatorna fogadó oldalán megjelenő bináris szekvenciát egyedileg dekódoljuk. Az A, B, C és D betűk esetében a következő kódszavakat használtuk: A - 111, B - 110, C - 101, D - 100.

A D betű kódolásához adja meg az alább felsorolt ​​kódszót.

A kódnak meg kell felelnie az egyértelmű dekódolás tulajdonságának. Ha egynél több kódszó használható, adja meg a legrövidebb kódot.

1) 1 2) 0 3) 01 4) 10

megoldás:

A - 111, B - 110, B - 101, D - 100, D -?

Válasz: 2

A kommunikációs csatorna csak 4 betűt tartalmazó üzeneteket küld: A, B, C, G. 5 bites kódszavakat használnak az A, B, C betűk kódolására: A - 10110, B - 11000, C - 00101. A következő tulajdonság teljesült: a készlet két szava legalább három pozícióban különbözik egymástól. Ez a tulajdonság fontos az üzenetek dekódolásához interferencia jelenlétében. A következő kódszavak közül melyik használható a G betűhöz, így a megadott tulajdonság mind a négy kódszóra érvényes?

1) 01110 2) 01011 3) 10001 4) a fenti szavak egyike sem érvényes

megoldás:

1) 01 110: A - 10 110 - nem különböznek legalább három pozícióban

2) 01011: A - 101 10, B - 1 1000, B - 0010 1 - legalább három helyen különböznek

Válasz: 2

A kommunikációs csatornán történő adatátvitelhez 5 bites kódot kell használni. Az üzenet csak az A, B és C betűket tartalmazza, amelyeket a következő kódszó kódol:

A - 10001, B - 01101, B - 10110.

Az adás interferenciát okozhat. Néhány hiba azonban megpróbálja megjavítani. E három kódszó közül bármelyik kettő legalább három helyen különbözik egymástól. Ezért, ha hiba lépett fel egy szó átadásakor egynél több pozícióban, akkor lehetséges egy ésszerű feltételezés, hogy melyik levelet küldték. (Azt mondják, hogy „a kód egy hibát kijavít.”) Például, ha a 01111 kódszó érkezik, úgy tekintjük, hogy a B. betűt továbbították (a különbség a B kódkódtól csak egy pozícióban van, más kódszavaknál több különbség van.) Ha a kapott kódszó nagyobb. Mivel a szó különbözik az A, B, C betűk kódszavától több pozícióban, úgy tekinthető, hogy hiba történt (az 'x' jelzéssel van jelölve).

Üzenet érkezett 00110 11101 11000 11001. Dekódolja ezt az üzenetet - válassza ki a megfelelő beállítást.

1) VBHH 2) ABBVA 3) xxxx 4) VBHA

megoldás:

00110	11101	11000	11001
B = 1,1010	B = 0,011	x	A = 10 001

Válasz: 4

Az A, B, C, D és D betűkből álló bizonyos szekvencia kódolásához egy egyenlőtlen bináris kódot használunk, amely lehetővé teszi az eredményül kapott bináris szekvencia egyedülálló dekódolását. Itt van a kód: A - 1; B - 0100; B - 000; G-011; D - 0101. Az egyik betű egy kódjának hosszát meg kell rövidíteni, hogy a kód még mindig dekódolható legyen. A többi betű kódjait nem szabad megváltoztatni. A következő módszerek közül melyiket lehet megtenni?

A-1, B-011, B-00, G-010

Válasz: 9

A kommunikációs csatorna üzeneteket küld, amelyek mindegyike 15 betűt tartalmaz A, 10 betű B, 6 betű és 4 betű D (az üzenetekben nincs más betű). Minden betű egy bináris sorrendben van kódolva. A kód kiválasztásakor két követelményt vettek figyelembe:

a) egy kódszó nem egy másik kezdete (szükséges, hogy a kód egyértelmű dekódolást tegyen lehetővé);

b) a kódolt üzenet teljes hosszának a lehető legrövidebbnek kell lennie.

Melyik kódot kell választani az A, B, C és D betűk kódolására?

1) A: 1, B: 01, B: 001, D: 111

2) A: 1, B: 01, C: 10, D: 111

3) A: 00, B: 01, C: 10, D: 11

4) A: 100, B: 101, C: 11, D: 0

megoldás:

Egy kódszó nem egy másik kezdete: A  a kezdet D  az 1. és 2. változatban.

A kódolt üzenet teljes hosszának a lehető legrövidebbnek kell lennie.

3) A: 00 (15), B: 01 (10), B: 10 (6), D: 11 (4)

2.15+2.10+2.6+2.4 = 70

4) A: 100 (15), B: 101 (10), B: 11 (6), D: 0 (4)

3.15+3.10+2.6_1.4 = 61

Válasz: 3

A kommunikációs csatorna egységes bináris kódot használ az olyan üzenetek továbbítására, amelyek csak 4 betű P, P, C, T. Minden betű megfelel a saját kódszavának, és a következő tulajdonságok teljesülnek a kódszókészlethez: a két szavak közül legalább kettő különbözik legalább három pozíció. Ez a tulajdonság fontos az üzenetek dekódolásához interferencia jelenlétében. A P, P, C betűk kódolásához 5 bites kódszavakat használunk: P: 01111, P: 00001, C: 11000. A T betű 5 bites kódja 1-től kezdődik és 0-nál fejeződik be.

megoldás:

C: 1 1000

T: 1,011 0 (T 1-től kezdődik és 0-nál fejeződik be)

C és T: 2 betű ugyanaz, ez azt jelenti, hogy a másik 3 betűnek másnak kell lennie.

válaszolni: 1 0110

Egységes állami vizsga a számítástechnikában, A9. Feladat, K. Polakov

Az A, B, C, D és D betűkből álló bizonyos szekvencia kódolásához egy egyenlőtlen bináris kódot használunk, amely lehetővé teszi az eredményül kapott bináris szekvencia egyedülálló dekódolását. Ez a kód: A - 00, B - 010, B - 011, D - 101, D - 111. Lehet-e lerövidíteni a betűkód egyik hosszát, hogy a kódot egyértelműen dekódolni lehessen? A többi betű kódjait nem szabad megváltoztatni. Válassza ki a helyes választ.

Példák.
1. Az A, B, C, D és D betűkből álló szekvencia kódolásához úgy döntöttünk, hogy egy egyenetlen bináris kódot használunk, amely lehetővé teszi számunkra, hogy a kommunikációs csatorna fogadó oldalán megjelenő bináris szekvenciát egyedileg dekódoljuk. Használt kód:
A - 1, B - 000, B - 001, D - 011. Adja meg a D betű kódszavát. Ennek a kódszónak a hossza a lehető legkisebb legyen. A kódnak meg kell felelnie az egyértelmű dekódolás tulajdonságának.
1) 00 2) 01 3)11 4) 010
megoldás:
8) vegye figyelembe, hogy a kód ismert részénél a Fano feltétel teljesül - nincs kódszó egy másik kódszó kezdete
9) ha D = 00, akkor egy ilyen kódlánc egybeesik a B = 000 és B = 001 kezdetével, a 000000 karakterláncot nem lehet egyértelműen dekódolni: ez lehet DDD vagy BB; így az első opció nem illik
10) ha D = 01, egy ilyen kódlánc egybeesik a T = 011 kezdetével, lehetetlen a 011 lánc egyértelműen dekódolni: lehet YES vagy T; így a második opció szintén nem megfelelő
11) ha D = 11, akkor a Fano-feltétel is megsérül: az A = 1 kódszó egybeesik a D betű kódjának kezdetével, lehetetlen a 111 lánc egyértelműen dekódolni: ez lehet YES vagy AAA; a harmadik opció nem illik
12) a negyedik opció esetében D = 010, a Fano-feltétel nem sérül;
13) A helyes válasz 4.

2. Az A, B, C, D betűből álló üzenet kommunikációs csatornáján történő továbbítására úgy döntöttek, hogy egy hosszúságú kódot használnak: A = 0, B = 10, C = 110. Hogyan kell a G betűt kódolni úgy, hogy a kód hossza minimális legyen, és a kódolt üzenet egy-egy-egy megosztása megengedett?
1) 1 2) 1110 3) 111 4) 11
Megoldás (1. lehetőség, kiválasztási módszer):
1) vegye figyelembe az összes lehetőséget a G betűjel hosszának növelése érdekében
2) T = 1; kiderül, hogy a "10" üzenet kétféleképpen dekódolható: GA vagy B, így ez az opció nem megfelelő
3) a következő leghosszabb opció T = 11; ebben az esetben a "110" üzenet dekódolható HA-ként vagy B-ként, így ez az opció szintén nem megfelelő
4) a harmadik opció, G = 111, egyértelmű betűtípust ad minden betűkombinációban, ezért ...
5) ... a helyes válasz 3.

Lehetséges problémák:
  iteráláskor tévedhet, és bármilyen opciót megtekinthet

Megoldás (2. opció, „intelligens” módszer):
1) annak érdekében, hogy egy nem egységes kóddal rögzített üzenet egyértelműen dekódolható legyen, nem szükséges, hogy egy kód egy másik (hosszabb) kód kezdete legyen; ezt a feltételt Fano állapotnak nevezik
2) mint az első megoldásnál, az Γ betű legrövidebb kódjával kezdődő lehetőségeket tekintjük; esetünkben a T = 1 kód a B és C betűk kódjainak kezdete, így a Fano feltétel nem teljesül, ez a kód nem illik
3) a D = 11 kód egy másik kód elejét is jelenti (a B betű kódja), ezért ez is hibás változat
4) a kód harmadik változata, G = 111, nem a már ismert kód kezdete; emellett a meglévő kódok egyike sem a 111-es kód kezdete; így a fano feltétel teljesül
5) ezért a helyes válasz 3.

Ingyenesen letöltheti az e-könyvet egy kényelmes formátumban és olvassa el:

Töltse le a vizsgát számítógépes tudományról, A9. Feladat, Polyakov K. - fileskachat.com, gyors és ingyenes letöltés.