Kod kodi aniq kodlash xususiyatiga mos bo'lishi kerak. EGE in Informatics, A9 vazifasi, Polyakov K.

Mavzu: Kodlash va kodni dekodlash

Elementlarni tekshiring : Kodlash va kodlash qobiliyati ma'lumotni kodlash

Nazariy material :

Kodlash - bir tildan ikkinchisiga ma'lumotni tarjima qilish (boshqa alfavitda boshqa belgilar tizimida yozish).

Agar shifrlangan xabar boshidan noyob tarzda kodlansa Fano holati: Hech qaysi kodeks boshqa bir kodistning boshlanishi.

Agar shifrlangan xabar oxiridan noyob tarzda dekodlangan bo'lishi mumkin teskari fano holati: Hech bir so'zlovchi boshqa bir so'zning oxiridir.

Fano konditsionasi aniq bir dekodlash uchun etarli, ammo zarur shart emas.

Vazifa misoli:

A, B, C, D va D harflaridan tashkil topgan ketma-ketlikni kodlash uchun, biz aloqa kanalining qabul qiluvchi tomonida ko'rinadigan ikkilik ketma-ketlikni noyob tarzda kodlash imkonini beruvchi noaniq ikkilik koddan foydalanishga qaror qildik. Amaldagi kod A - 1, B - 000, B - 001, D - 011 edi. D harfi uchun kod so'zini ko'rsating.

Kod kodi aniq kodlash xususiyatiga mos bo'lishi kerak.

Umumiy yondashuv:

Javobni topish uchun Fano holatini yoki mantiqiy asoslashni qo'llash.

Biznes:

1) 00 - buyon Fano holatini buzadi kod zanjiri B = 000 va B = 001 boshlanishiga to'g'ri keladi. 000000 zanjirini bir-biridan ajratib bo'lmaydi: DDD yoki BB bo'lishi mumkin, shuning uchun birinchi variant mos emas

2) 01 - Fano holatini buzadi kod zanjiri T = 011 boshlanishiga to'g'ri keladi. H 011 zanjirini bir-biridan ajratish mumkin emas: U Y yoki T bo'lishi mumkin, shuning uchun ikkinchi variant ham mos emas

3) 11 - Fano holatini buzadi kod zanjiri A = 1. N boshiga to'g'ri keladizanjirni bir-biridan ajratish mumkin emas: bu YES yoki AAA bo'lishi mumkin; uchinchi variant mos emas

4) 010 - Fano holati buzilmaydi.

Javob: 4) 010

Trening vazifalari:

1) A, B, C, D harflaridan tashkil topgan xabarning aloqa kanali orqali uzatilishi uchun ular A = 00, B = 11, C = 100 teng bo'lmagan kodni ishlatishga qaror qilishdi. G kodi kodning uzunligi minimal va kodlangan xabarni birma-bir ajratish uchun kodlanishi kerak?

2) A, B, C, D harflaridan tashkil topgan xabarning aloqa kanali orqali uzatilishi uchun ular uzunligi teng bo'lmagan kodni ishlatishga qaror qildilar: A = 1, B = 000, C = 001. G kodi kodning uzunligi minimal va kodlangan xabarni birma-bir ajratish uchun kodlanishi kerak?

3) A, B, C, D va D harflaridan tashkil topgan ketma-ketlikni kodlash uchun noyob ikkilik ketma-ketlikni noyob tarzda hal qilishga imkon beruvchi noaniq ikkilik kod ishlatiladi. Bu kod shu erda: A - 10, B - 11, B - 000, D - 001, D - 011. Harflarning birortasi uchun kod so'zi uzunligini qisqartirish mumkinmi, shunda kod hali ham bir nechta koddan hal qilinishi mumkin? Qolgan harflarning kodlari o'zgartirilmasligi kerak. To'g'ri javobni tanlang.

1) mumkin emas

2) B harfi - 1 uchun

3) B - 00 harfi uchun

4) D - 01 xatida

4) A, B, C, D va D harflaridan tashkil topgan ma'lum bir ketma-ketlikni kodlash uchun noyob ikkilik kod ishlatiladi va natijada olingan ikkilik ketma-ketlikni bir-biridan ajratish mumkin. Bu kod shu erda: A - 11, B - 10, B - 011, D - 000, D - 001. Harflarning birortasi uchun kod so'zi uzunligini qisqartirish mumkinmi, shunda kod hali ham bir nechta koddan hal qilinishi mumkin? Qolgan harflarning kodlari o'zgartirilmasligi kerak. To'g'ri javobni tanlang.

1) G - 00 harfi uchun

2) mumkin emas

3) B - 01 harfi uchun

4) B harfi - 1 uchun

5) A, B, C, D va D harflaridan tashkil topgan ketma-ketlikni kodlash uchun noyob ikkilik ketma-ketlikni noyob tarzda kodlash imkonini beruvchi noaniq ikkilik kod ishlatiladi. Bu kod quyidagilar: A - 10, B - 001, B - 0001, D - 110, D - 111. Harflarning birortasi uchun kod so'zi uzunligini qisqartirish mumkinmi, shunda kod hali ham bir nechta koddan hal qilinishi mumkin? Qolgan harflarning kodlari o'zgartirilmasligi kerak. To'g'ri javobni tanlang.

1) G - 11 harfi uchun

2) mumkin emas

3) B - 000 xatida

A, B, C, D, D va E harflaridan tashkil topgan ma'lum bir ketma-ketlikni kodlash uchun Fano konditsionasini qondiradigan tengsiz ikkilik kodni ishlatishga qaror qildik. A harfi uchun kod so'zi 0 ishlatilgan; B harfi uchun kod so'zi 10. Oltita kodli so'zlarning eng kichik miqdori qancha?
Eslatma Fano holati, boshqa kodsal yozuvning boshlanishi bo'lishi mumkin emas. Bu kodlangan xabarlarni bir-biridan parchalanishiga imkon beradi.

Namoyish etiketi EGE 2017 - vazifa raqami 5

Biznes:

Kodni topish uchun biz ushbu jadvalni ishlatamiz.

Agar qolgan harflarning kodlari 0dan boshlanadigan bo'lsa, A = 0 harfining kodi kodlarining boshlanishi bo'ladi, shuning uchun ushbu parametr mos emas. Agar kod B = 10 bo'lsa, C, D, D, E harflari kodi 11 da boshlanadi. 4 xil kodni olish uchun siz 4 ta belgidan (1111, 1110, 1101, 1100) iborat kodlardan foydalanishingiz kerak.

0	1
	1
	1		0
	1	0	1	0

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

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

Javob: 19

EGE 2016 namoyish raqami - vazifa raqami 5

Aloqa kanali faqat to'rt harfdan iborat xabarlarni yuboradi: P, O, C, T; Yuborish uchun, aniq kod hal qilinishiga imkon beruvchi ikkilik kod ishlatiladi. T, O, P harfi uchun quyidagi kod so'zlari ishlatiladi: T: 111, O: 0, P: 100.

C kodi uchun eng qisqa kod so'zini ko'rsating, unda kod bir-biridan aniq kodlashni ta'minlaydi. Agar bir nechta bunday kodlar mavjud bo'lsa, eng past raqamli kodni kiriting.

Biznes:

Kod so'zlarini topish uchun biz ushbu sxemadan foydalanamiz.

Qolgan harflarning kodlari boshlanadi 0 harf kodi Oh=0 kodlarining boshlanishi bo'ladi, shuning uchun bu variant mos emas. Xat kodi beri F.=100 va harflar kodi T =111 keyin maktubni Bilan bu raqamlar bilan boshlash va tugatish mumkin emas.

Javob: 101

Faqat A, B, C va D harflaridan iborat xabarni kodlash uchun ikkilik kod uzunligi teng emas:

Agar GAVBGV belgilar ketma-ketligini kodlash va natijani o'n oltita kodga yozsangiz, quyidagilarni amalga oshirasiz:

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

Biznes:

GAVBGV = 0110001011011010

0110	0010	1101	1010
6	2	D	A

Javob: 4

Qora va oq bitmap tasvirni yuqori chap burchakdan boshlab va pastki o'ng burchakda tugagan chiziq bo'yicha kodlangan. Kodlashda 1 qora, 0 esa oq rangni bildiradi.

Kompaktlik uchun natija sakkizinchi nashrda qayd etilgan. To'g'ri kod kiritishni tanlang.

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

Biznes:

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

Javob: 3

Raqamlarni shovqinli kanal orqali uzatish uchun parite nazorat kodi ishlatiladi. Har bir raqam uning ikkilik tavsifida, uzunligi 4gacha etuvchi nol bilan birga yoziladi va modulo 2 elementlarining yig'indisi hosil bo'ladigan ketma-ketlikka qo'shiladi (masalan, biz 23 ga o'tib, keyin biz 0010100110 qatorini olamiz). 01100010100100100110 shaklidagi kanal orqali qanday raqamni uzatganini aniqlang.

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

Biznes:

01100010100100100110

01100	01010	01001	00110
6	5	4	3

Javob: 1

O, L, A, G, K harflarini kodlash uchun navbati bilan 0, 1, 2, 3 va 4 raqamlarining ikkilik kodlari qo'llaniladi (bir bitli vakillik holatida bir nolga teng). Agar VOKOLKA belgilar ketma-ketligini kodlash va natijani o'n oltita kodga yozsangiz, shunday bo'lasiz:

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

Biznes:

Oh	L	A	H	To
0=00	1=01	2=10	3=11	4=100

COUNT = 1110100000110010

1110	1000	0011	0010
E	8	3	2

Javob: 3

A, B, C, D harflaridan tashkil topgan xabarning aloqa kanali orqali uzatilishi uchun ular A = 00, B = 11, S = 100 teng bo'lmagan kodni ishlatishga qaror qilishdi. G kodi kodning uzunligi minimal va kodlangan xabarni birma-bir ajratish uchun kodlanishi kerak?

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

Biznes:

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

Javob: 3

A, B, C, D va D harflaridan tashkil topgan ketma-ketlikni kodlash uchun, biz aloqa kanalining qabul qiluvchi tomonida ko'rinadigan ikkilik ketma-ketlikni noyob tarzda kodlash imkonini beruvchi noaniq ikkilik koddan foydalanishga qaror qildik. A, B, C va D harflari uchun quyidagi kod so'zlari ishlatilgan: A - 111, B - 110, S - 101, D - 100.

D harfini kodlash uchun quyida keltirilgan kod so'zini kiriting.

Kod kodi aniq kodlash xususiyatiga mos bo'lishi kerak. Agar bir nechta kod so'zini ishlatsa, eng qisqa raqamni belgilang.

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

Biznes:

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

Javob: 2

A, B, C, 00101, A - 10110, B - 11000, C - 00101 harflarini kodlash uchun A, B, C, G. 5-bit kodli so'zlar ishlatiladi. Ushbu kod so'zlari uchun Quyidagi funktsiyalar bajarildi: to'plamdagi har qanday ikki so'z kamida uchta pozitsiyada farq qiladi. Bu xususiyat shovqin mavjud bo'lgan xabarlarni dekodlash uchun juda muhimdir. G harfi uchun quyidagi kod so'zi qaysi biri ishlatilishi mumkin?

1) 01110 2) 01011 3) 10001 4) Yuqoridagi so'zlardan hech biri amal qilmaydi

Biznes:

1) 01 110: A - 10 110 - kamida uchta pozitsiyada farq qilmang

2) 01011: A - 101 10, B - 1 1000, B - 0010 1 - kamida uchta pozitsiyada farqlanadi

Javob: 2

Aloqa kanallari orqali ma'lumotlarni uzatish uchun 5-bit kod ishlatiladi. Xabarda quyidagi kod so'zlari bilan kodlangan A, B va C harflari keltirilgan:

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

Etkazish parazitga olib kelishi mumkin. Biroq, ba'zi xatolar tuzatishga urinishi mumkin. Ushbu uchta kod so'zining ikkitasi kamida uchta pozitsiyada bir-biridan farq qiladi. Shuning uchun, agar so'zni bir martalik topshirishda xatolik yuzaga kelsa, unda qaysi maktubni etkazish haqida o'rtacha taxmin qilish mumkin. ("Kod bir xatoni tuzatadi" deb aytiladi). Masalan, agar 01111 kodli so'z olinadigan bo'lsa, B. harfini qabul qilgan deb hisoblanadi (B kodi so'zining farqli tomoni faqat bitta holatda, boshqa kod so'zlari uchun esa ko'proq farqlar mavjud). Agar olingan kod so'zi So'z A, B, C harflaridan bir nechta pozitsiyada kod so'zlaridan farq qilganligi sababli, xato paydo bo'lgan deb hisoblanadi ("x" bilan belgilanadi).

Xabar qabul qilindi 00110 11101 11000 11001. Ushbu xabarni dekodlash - to'g'ri variantni tanlang.

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

Biznes:

00110	11101	11000	11001
B = 1.0110	B = 0 1101	x	A = 10 001

Javob: 4

A, B, C, D va D harflaridan tashkil topgan aniq bir qatorni kodlash uchun noyob ikkilik ketma-ketlikni noyob tarzda hal qilish imkonini beradigan noyob ikkilik kod ishlatiladi. Bu erda kod: A - 1; B - 0100; B - 000; G - 011; D - 0101. Kodlardan birining uzunligi kodning uzunligini qisqartirishi kerak, shunda kod yana ham noyob bo'lishi mumkin. Qolgan harflarning kodlari o'zgartirilmasligi kerak. Buning qaysi usullaridan biri amalga oshirilishi mumkin?

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

Javob: 9

Aloqa kanali xabarlarni uzatadi, ularning har birida 15 harfdan iborat A, 10 ta harf B, 6 ta C va 4 ta harf D (xabarlarda boshqa harflar yo'q). Har bir harf ikki tomonlama ketma-ketlikda kodlangan. Kodni tanlashda ikkita talab hisobga olingan:

a) kod so'zi boshqa birining boshlanishi (kodning aniq bir tarzda dekodlashiga ruxsat berish kerak);

b) kodlangan xabarning umumiy uzunligi iloji boricha qisqa bo'lishi kerak.

A, B, C va D harflarini kodlash uchun quyidagilardan qaysi kodni tanlash kerak?

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

Biznes:

Hech bir yozuvning boshi emas: A boshlanishi R. 1 va 2-chi versiyalarda.

Kodlangan xabarning umumiy uzunligi iloji boricha qisqa bo'lishi kerak.

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

Javob: 3

Aloqa kanali faqat P, P, C, T harflaridan iborat bo'lgan xabarlarni uzatish uchun bir martalik ikkilik koddan foydalanadi. Har bir harf o'z kodi so'ziga mos keladi va quyidagi xususiyatlar bir qator kod so'zlari uchun bajariladi: to'plamdagi har qanday ikkita so'z kamida farq qiladi uch pozitsiya. Bu xususiyat shovqin mavjud bo'lgan xabarlarni dekodlash uchun juda muhimdir. P, P, C harflarini kodlash uchun 5-bit kodli so'zlar ishlatiladi: P: 01111, P: 00001, C 11000. T harfi uchun 5-bitlik kod 1da boshlanadi va 0 bilan tugaydi. T harfi uchun kod so'zini aniqlang.

Biznes:

Javob: 1 1000

T: 1,011 0 (T 1 dan boshlanadi va 0da tugaydi)

C va T: 2 ta harf bir xil, demak, boshqa 3 ta harf turli xil bo'lishi kerak.

Javob: 1 0110

Kompyuter fanlari bo'yicha yagona davlat sinalishi, A9 vazifasi, Polyakov K.

A, B, C, D va D harflaridan tashkil topgan aniq bir qatorni kodlash uchun noyob ikkilik ketma-ketlikni noyob tarzda hal qilish imkonini beradigan noyob ikkilik kod ishlatiladi. Bu kod shu erda: A - 00, B - 010, B - 011, D - 101, D - 111. Harflarning birortasi uchun kod so'zi uzunligini qisqartirish mumkinmi, shunda kod hali ham bir nechta koddan hal qilinishi mumkin? Qolgan harflarning kodlari o'zgartirilmasligi kerak. To'g'ri javobni tanlang.

Misollar
A, B, C, D va D harflaridan tashkil topgan ketma-ketlikni kodlash uchun, biz aloqa kanalining qabul qiluvchi tomonida ko'rinadigan ikkilik ketma-ketlikni noyob tarzda kodlash imkonini beradigan tengsiz ikkilik koddan foydalanishga qaror qildik. Ikkinchi kod:
A - 1, B - 000, B - 001, D - 011. D harfi uchun kod so'zini ko'rsating. Ushbu kod so'zining uzunligi eng kichik bo'lishi kerak. Kod kodi aniq kodlash xususiyatiga mos bo'lishi kerak.
1) 00 2) 01 3)11 4) 010
Biznes:
8) kodning ma'lum qismi uchun Fano sharti bajarilganini - kod so'zini boshqa kod so'zining boshi emasligini unutmang
9) D = 00 bo'lsa, bunday kod satrlari B = 000 va B = 001 boshiga to'g'ri kelib qolsa, 000000 satrini bir-biridan ajratib ko'rsatish mumkin emas: bu DDD yoki BB bo'lishi mumkin; shuning uchun birinchi variant mos emas
10) D = 01 bo'lsa, bunday kod zanjiri T = 011 boshiga to'g'ri kelib qolsa, zanjirni bir-biridan ajratish mumkin emas: bu - YES yoki T; shuning uchun ikkinchi variant ham mos emas
11) D = 11 bo'lsa, Fano sharti ham buziladi: kod A = 1 kodi D harfi kodining boshiga to'g'ri keladi, zanjirning birma-bir aniqlanmasligi mumkin emas: bu YES yoki AAA bo'lishi mumkin; uchinchi variant mos emas
12) to'rtinchi variant uchun, D = 010, Fano holati buzilmaydi;
To'g'ri javob 4 ga teng.

2. A, B, C, D harflaridan tashkil topgan xabarning aloqa kanali orqali uzatilishi uchun ular uzunligi teng bo'lmagan kodni ishlatishga qaror qilishdi: A = 0, B = 10, C = 110. G kodi kodning uzunligi minimal va kodlangan xabarni birma-bir ajratish uchun kodlanishi kerak?
1) 1 2) 1110 3) 111 4) 11
Biznes (parametr 1, tanlov usuli):
1) barcha variantlarni G kodi xatining uzunligini oshirish tartibini hisobga oling
2) biz T = 1 dan boshlaymiz; "10" xabarining ikki shaklda kodlanishi mumkin: GA yoki B, shuning uchun ushbu parametr mos emas
3) keyingi eng uzun variant - T = 11; bu holatda "110" xabarini HA yoki B deb o'zgartirishi mumkin, shuning uchun bu parametr ham mos emas
4) uchinchi variant G = 111, barcha harflar kombinatsiyalarida aniq bir dekodlashni beradi, shuning uchun ...
5) ... to'g'ri javob 3 ga teng.

Mumkin bo'lgan muammolar:
yineleyici, xato qilish va har qanday variantni "ko'rish" mumkin

Biznes (variant 2, "aqlli" usul):
1) yagona bo'lmagan kod yordamida aniqlangan xabarni aniq bir shaklda dekodlash uchun, hech kod boshqa (uzoq) kodning boshlanishi bo'lishi shart; Bu holat "Fano" deb ataladi
2) birinchi yechimdagi kabi, G harfining eng qisqa kodidan boshlangan variantlarni ko'rib chiqamiz; bizning holatimizda T = 1 kodi B va S harflari kodining boshidir, shuning uchun Fano holati qoniqtirilmaydi, bu kod mos emas
3) D = 11 kodi boshqa kodning boshlanishi (B harfining kodi), shuning uchun bu ham noto'g'ri variant
4) kodning uchinchi varianti, G = 111, allaqachon ma'lum bo'lgan kodning boshlanishi emas; Bundan tashqari, mavjud kodlarning hech biri kodning 111 boshlanishidir; shuning uchun fano holati bajariladi
5) shuning uchun to'g'ri javob 3 ga teng.

Qulay formatda bepul elektron kitobni yuklab oling va o'qing:

Kompyuter faniga imtihonni yuklab olish, A9 vazifasi, Polyakov K. - fileskachat.com, tez va bepul yuklab olish.