Задание 1 — Решение заданий ЕГЭ по информатике

Ко­ди­ро­ва­ние и де­ко­ди­ро­ва­ние информации

Кодирование в различных системах счисления 

№1. Для ко­ди­ро­ва­ния букв О, В, Д, П, А ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ВО­ДО­ПАД таким спо­со­бом и ре­зуль­тат за­пи­сать вось­ме­рич­ным кодом, то по­лу­чит­ся

1) 22162

2) 1020342

3) 2131453

4) 34017

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010. Те­перь разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел в де­ся­тич­ный код, затем в вось­ме­рич­ный (вось­ме­рич­ное предств­ле­ние сов­па­да­ет с де­ся­тич­ным при раз­би­е­нии трой­ка­ми)

010 010 001 110 010 — 22162.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

№2. Для ко­ди­ро­ва­ния букв Д, X, Р, О, В ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ХО­РО­ВОД таким спо­со­бом и ре­зуль­тат за­пи­сать вось­ме­рич­ным кодом, то по­лу­чит­ся

1) 12334

2) 2434541

3) 36714

4) 1323430

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ХО­РО­ВОД — 011110111001100. Те­перь разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел в де­ся­тич­ный код, затем в вось­ме­рич­ный (вось­ме­рич­ное предств­ле­ние сов­па­да­ет с де­ся­тич­ным при раз­би­е­нии трой­ка­ми)

011 110 111 001 100 — 36714.

Пра­виль­ный отвте ука­зан под но­ме­ром 3.

№3. Для ко­ди­ро­ва­ния букв О, К, Г, Д, Р ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ГО­РО­ДОК таким спо­со­бом и ре­зуль­тат за­пи­сать вось­ме­рич­ным кодом, то по­лу­чит­ся

1) 2040301

2) 16024

3) 1030402

4) 42061

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ГО­РО­ДОК — 100010000110001. Те­перь разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел в де­ся­тич­ный код, затем в вось­ме­рич­ный (вось­ме­рич­ное предств­ле­ние сов­па­да­ет с де­ся­тич­ным при раз­би­е­нии трой­ка­ми)

100 010 000 110 001 — 42061.

Пра­виль­ный отвте ука­зан под но­ме­ром 4.

№4. Для ко­ди­ро­ва­ния букв X, Е, Л, О, Д ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ЛЕ­ДО­ХОД таким спо­со­бом и ре­зуль­тат за­пи­сать шест­на­дца­те­рич­ным кодом, то по­лу­чит­ся

1) 999С

2) 3254145

3) 123F

4) 2143034

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ЛЕ­ДО­ХОД — 1001100110011100. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел cна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный.

1001 1001 1001 1100 — 9 9 9 12 — 999С.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

№5. Для ко­ди­ро­ва­ния букв И, Д, Т, О, X ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ТИ­ХО­ХОД таким спо­со­бом и ре­зуль­тат за­пи­сать шест­на­дца­те­рич­ным кодом, то по­лу­чит­ся

1) CD89

2) 89CD

3) 3154542

4) 2043431

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ТИ­ХО­ХОД — 1000100111001101. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел cна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный.

1000 1001 1100 1101 — 8 9 12 13 — 89СD.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

№6. Для ко­ди­ро­ва­ния букв Р, С, Н, О, Г ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв НО­СО­РОГ таким спо­со­бом и ре­зуль­тат за­пи­сать вось­ме­рич­ным кодом, то по­лу­чит­ся

1) 3424145

2) 2313034

3) 55634

4) 33100

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: НО­СО­РОГ — 101101110011100. Те­перь разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел в де­ся­тич­ный код (при пред­став­ле­нии дво­ич­ны­ми трой­ка­ми вось­ме­рич­ный код сов­па­да­ет с де­ся­тич­ным)

101 101 110 011 100 — 55634.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

№7. Для ко­ди­ро­ва­ния букв Е, П, Н, Ч, Ь ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ПЕ­ЧЕ­НЬЕ таким спо­со­бом и ре­зуль­тат за­пи­сать вось­ме­рич­ным кодом, то по­лу­чит­ся

1) 1030240

2) 12017

3) 2141351

4) 23120

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ПЕ­ЧЕ­НЬЕ — 010011001010000.

010 011 001 010 000 — 23120.

Пра­виль­ный ответ ука­зан под но­ме­ром 4.

№8. Для ко­ди­ро­ва­ния букв О, Ч, Б, А, К ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв КА­БА­ЧОК таким спо­со­бом и ре­зуль­тат за­пи­сать шест­на­дца­те­рич­ным кодом, то по­лу­чит­ся

1) 5434215

2) 9DA4

3) ABCD

4) 4323104

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: КА­БА­ЧОК — 1001110110100100. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел сна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный:

1001 1101 1010 0100 — 9 13 10 4 — 9DA4.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

№9. Для ко­ди­ро­ва­ния букв Р, И, К, П, А ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ПА­ПРИ­КА таким спо­со­бом и ре­зуль­тат за­пи­сать шест­на­дца­те­рич­ным кодом, то по­лу­чит­ся

1) Е634

2) А1В2

3) А45412А

4) 3430124

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ПА­ПРИ­КА — 1110011000110100. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел сна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный:

1110 0110 0011 0100 — 14 6 3 4 — E634.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

№10. Для ко­ди­ро­ва­ния букв О, Л, А, 3, К ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). Если за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв ЗА­КОЛ­КА таким спо­со­бом и ре­зуль­тат за­пи­сать шест­на­дца­те­рич­ным кодом, то по­лу­чит­ся

1) 4351253

2) 9876

3) Е832

4) 3240143

По­яс­не­ние.

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ЗА­КОЛ­КА — 1110100000110010. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел сна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный:

1110 1000 0011 0010 — 14 8 3 2 — E832.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

    Расшифровка сообщений

№1. Для 5 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв — из двух бит, для не­ко­то­рых — из трех). Эти коды пред­став­ле­ны в таб­ли­це:

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1100000100110

1) baade

2) badde

3) bacde

4) bacdb

По­яс­не­ние.

Мы видим, что вы­пол­ня­ет­ся усло­вие Фано: ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова, по­это­му од­но­знач­но можем рас­ко­ди­ро­вать со­об­ще­ние с на­ча­ла.

Разобьём код слева на­пра­во по дан­ным таб­ли­цы и пе­ре­ведём его в буквы:

110 000 01 001 10 — b a c d e.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

№2. Для 5 букв латинского алфавита заданы их двоичные коды (для не­ко­то­рых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

a             b             c              d             e

100         110         011         01           10

Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:

1) cbade

2) acdeb

3) acbed

4) bacde

Пояснение.

Мы видим, что условия Фано и обратное условие Фано не выполняются, значит код можно раскодировать неоднозначно.

Будем пробовать разные варианты, отбрасывая те, в которых получаются повторяющиеся буквы:

1) 100 011 01 10 110

Первая буква определяется однозначно, её код 100: a.

Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.

Такой вариант удовлетворет условию, значит, окончательно получили ответ: acdeb.

Правильный ответ указан под номером 2.

№3. Для 6 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв из двух бит, для не­ко­то­рых – из трех). Эти коды пред­став­ле­ны в таб­ли­це:

Опре­де­ли­те, какая по­сле­до­ва­тель­ность из 6 букв за­ко­ди­ро­ва­на дво­ич­ной стро­кой 011111000101100.

1) DEFBAC

2) ABDEFC

3) DECAFB

4) EFCABD

По­яс­не­ние.

Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.

Будем про­бо­вать раз­ные ва­ри­ан­ты, от­бра­сы­вая те, в ко­то­рых по­лу­ча­ют­ся по­вто­ря­ю­щи­е­ся буквы:

1) 011 11 100 0101100

Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 011: D.

Вто­рая буква также опре­де­лит­ся од­но­знач­но  — E.

Пусть тре­тья буква B, тогда сле­ду­ю­щая на­чи­на­ет­ся с кода 010, но таких букв в таб­ли­це нет, зна­чит пред­по­ло­же­ние не верно.

2) 011 11 10 00 101 100

Тре­тья буква — С, потом — A. Мы хотим по­лу­чить ещё две буквы, чтобы в сумме их было 6, тогда сле­ду­ю­щая буква — F, и по­след­няя  — B.

Окон­ча­тель­но по­лу­чи­ли ответ: DECAFB.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

№4. Для ко­ди­ро­ва­ния со­об­ще­ния, со­сто­я­ще­го толь­ко из букв О, К, Л, М и Б, ис­поль­зу­ет­ся не­рав­но­мер­ный по длине дво­ич­ный код:

Какое (толь­ко одно!) из че­ты­рех по­лу­чен­ных со­об­ще­ний было пе­ре­да­но без оши­бок и может быть рас­ко­ди­ро­ва­но:

1) 110001001001110

2) 10000011000111010

3) 110001001101001

4) 1000110001100010

По­яс­не­ние.

Разобьём каж­дый ответ на по­сим­воль­ный код и найдём нуж­ный ва­ри­ант:

Ва­ри­ант 1: 11 00 010 01 00 11 10 — при таком раз­би­е­нии по­след­няя часть кода не может быть рас­ко­ди­ро­ва­на, а если раз­бить по-дру­го­му 11 00 01 00 10011, то со­об­ще­ние также не­де­ко­ди­ру­е­мо.

В ва­ри­ан­тах 2 и 4 не­воз­мож­но рас­ко­ди­ро­вать на­ча­ло кода.

Ва­ри­ант 3: 11 00 01 00 11 01 00 1  — при таком раз­би­е­нии по­след­няя часть кода не может быть рас­ко­ди­ро­ва­на. Разобьём по-дру­го­му: 11 00 01 00 11 010 01 — такой ва­ри­ант раз­би­е­ния может быть рас­ко­ди­ро­ван.

.Пра­виль­ный ответ ука­зан под но­ме­ром 3.

№5. Для пе­ре­да­чи чисел по ка­на­лу с по­ме­ха­ми ис­поль­зу­ет­ся код про­вер­ки чет­но­сти. Каж­дая его цифра за­пи­сы­ва­ет­ся в дво­ич­ном пред­став­ле­нии, с до­бав­ле­ни­ем ве­ду­щих нулей до длины 4, и к по­лу­чив­шей­ся по­сле­до­ва­тель­но­сти до­пи­сы­ва­ет­ся сумма её эле­мен­тов по мо­ду­лю 2 (на­при­мер, если пе­ре­даём 23, то по­лу­чим по­сле­до­ва­тель­ность 0010100110). Опре­де­ли­те, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110?

1) 6543

2) 62926

3) 62612

4) 3456

По­яс­не­ние.

Из при­ме­ра видно, что 2 знака ко­ди­ру­ют­ся 10 дво­ич­ны­ми раз­ря­да­ми (би­та­ми), на каж­дую цифру от­во­дит­ся 5 бит. В усло­вии ска­за­но, что каж­дая цифра за­пи­сы­ва­ет­ся кодом дли­ной 4 знака, зна­чит, пятую цифру можно от­ки­нуть.

Разобьём дво­ич­ную за­пись на груп­пы по 5 зна­ков: 01100 01010 01001 00110. От­бра­сы­ва­ем по­сле­юд­нюю цифру в каж­дой пятёрке и первео­дим в де­ся­тич­ную за­пись:

0110 0101 0100 0011 — 6 5 4 3.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

№6. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 5 букв А, И, К, О, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код с та­ки­ми ко­до­вы­ми сло­ва­ми:

А — 0, И — 00, К — 10, О — 110, Т — 111.

Среди при­ведённых ниже слов ука­жи­те такое, код ко­то­ро­го можно де­ко­ди­ро­вать толь­ко одним спо­со­бом. Если таких слов не­сколь­ко, ука­жи­те пер­вое по ал­фа­ви­ту.

1) КАА

2) ИКОТА

3) КОТ

4) ни одно из со­об­ще­ний не под­хо­дит

По­яс­не­ние.

За­ко­ди­ру­ем каж­дое слово.

КАА — 1000

ИКОТА — 00101110

КОТ — 10110111

Слово КАА можно де­ко­ди­ро­вать как КИ

Слово ИКОТА можно де­ко­ди­ро­вать как АА­КО­ТА

Слово КОТ никак нель­зя де­ко­ди­ро­вать по-дру­го­му.

Сле­до­ва­тель­но, ответ 3.

№7. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 5 букв А, И, К, О, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код с та­ки­ми ко­до­вы­ми сло­ва­ми:

А — 0, И — 00, К — 10, О — 110, Т — 111.

Среди при­ведённых ниже слов ука­жи­те такое, код ко­то­ро­го можно де­ко­ди­ро­вать толь­ко одним спо­со­бом. Если таких слов не­сколь­ко, ука­жи­те пер­вое по ал­фа­ви­ту.

1) КИОТ

2) КООТ

3) ТААК

4) ни одно из со­об­ще­ний не под­хо­дит

По­яс­не­ние.

За­ко­ди­ру­ем каж­дое слово.

КИОТ — 1000110111

КООТ — 10110110111

ТААК — 1110010

Слово КИОТ можно де­ко­ди­ро­вать как КAA…

Слово ТААК можно де­ко­ди­ро­вать как TИ…

Слово КООТ никак нель­зя де­ко­ди­ро­вать по дру­го­му.

Сле­до­ва­тель­но, ответ 2.

№8. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:

П — 11111, О — 11000, Р — 00100, Т — 00011.

Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трёх по­зи­ци­ях.

Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 00000, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).

11011 11100 00011 11000 01110

00111 11100 11110 11000 00000

1) ПОТОП

2) РОТОР

3) ТОПОР

4) ни одно из со­об­ще­ний не при­ня­то кор­рект­но

По­яс­не­ние.

Длина обоих со­об­ще­ний крат­на пяти.

Ана­ли­зи­руя пер­вое со­об­ще­ние «11011 11100 00011 11000 01110», при­хо­дим к вы­во­ду, что оно при­ня­то не­кор­рект­но, по­сколь­ку нет та­ко­го слова, ко­то­рое бы от­ли­ча­лось от слова «01110» толь­ко в одной по­зи­ции.

Рас­смот­рим вто­рое со­об­ще­ние. Учи­ты­вая, что каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции, его воз­мож­но рас­шиф­ро­вать толь­ко как «ТОПОР».

№9. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:

П — 00000, О — 00111, Р — 11011, Т — 11100.

Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трёх по­зи­ци­ях.

Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 11111, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).

11011 10111 11101 00111 10001

10000 10111 11101 00111 00001

1) ПОТОП

2) РОТОР

3) ТОПОР

4) ни одно из со­об­ще­ний не при­ня­то кор­рект­но

По­яс­не­ние.

Длина обоих со­об­ще­ний крат­на пяти.

Ана­ли­зи­руя пер­вое со­об­ще­ние «11011 10111 11101 00111 10001», при­хо­дим к вы­во­ду, что оно при­ня­то не­кор­рект­но, по­сколь­ку нет та­ко­го слова, ко­то­рое бы от­ли­ча­лось от слова «10001» толь­ко в одной по­зи­ции.

Рас­смот­рим вто­рое со­об­ще­ние. Учи­ты­вая, что каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции, его воз­мож­но рас­шиф­ро­вать толь­ко как «ПОТОП».

№10. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы — П, О, Р, Т. Для ко­ди­ро­ва­ния букв ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова:

П — 00000, О — 00111, Р — 11011, Т — 11100.

Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трёх по­зи­ци­ях.

Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех (в пред­по­ло­же­нии, что пе­ре­да­ва­е­мые биты могут ис­ка­жать­ся, но не про­па­да­ют). За­ко­ди­ро­ван­ное со­об­ще­ние счи­та­ет­ся при­ня­тым кор­рект­но, если его длина крат­на 5 и каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции; при этом счи­та­ет­ся, что пятёрка ко­ди­ру­ет со­от­вет­ству­ю­щую букву. На­при­мер, если при­ня­та пя­тер­ка 11111, то счи­та­ет­ся, что пе­ре­да­ва­лась буква Р.

Среди при­ведённых ниже со­об­ще­ний най­ди­те то, ко­то­рое при­ня­то кор­рект­но, и ука­жи­те его рас­шиф­ров­ку (про­бе­лы не­су­ще­ствен­ны).

11011 10111 11101 00111 10001

10000 10111 11101 00111 00001

1) ПОТОП

2) РОТОР

3) ТОПОР

4) ни одно из со­об­ще­ний не при­ня­то кор­рект­но

По­яс­не­ние.

Длина обоих со­об­ще­ний крат­на пяти.

Ана­ли­зи­руя пер­вое со­об­ще­ние «11011 10111 11101 00111 10001», при­хо­дим к вы­во­ду, что оно при­ня­то не­кор­рект­но, по­сколь­ку нет та­ко­го слова, ко­то­рое бы от­ли­ча­лось от слова «10001» толь­ко в одной по­зи­ции.

Рас­смот­рим вто­рое со­об­ще­ние. Учи­ты­вая, что каж­дая пятёрка от­ли­ча­ет­ся от не­ко­то­ро­го ко­до­во­го слова не более чем в одной по­зи­ции, его воз­мож­но рас­шиф­ро­вать толь­ко как «ПОТОП».

№11. Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми:

А — 11010, Б — 00110, В — 10101.

При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся ‘х’).

По­лу­че­но со­об­ще­ние 00111 11110 11000 10111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1) БААх

2) БААВ

3) хААх

4) хххх

По­яс­не­ние.

Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 00111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей. Вто­рое слово: 11110 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Тре­тье слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Четвёртое слово: 10111 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей.

Таким об­ра­зом, ответ: БААВ.

    Передача информации и выбор кода

№1. Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?

1) 0001

2) 000

3) 11

4) 101

По­яс­не­ние.

Для того, чтобы со­об­ще­ние, за­пи­сан­ное с по­мо­щью не­рав­но­мер­но­го по длине кода, од­но­знач­но рас­ко­ди­ро­ва­лось, тре­бу­ет­ся, чтобы ни­ка­кой код не был на­ча­лом дру­го­го (более длин­но­го) кода.

Рас­смот­рим ва­ри­ан­ты для буквы Г, на­чи­ная с са­мо­го ко­рот­ко­го.

3) Г=11: код буквы A яв­ля­ет­ся на­ча­лом этого кода, по­это­му этот ва­ри­ант не под­хо­дит.

4) Код Г=101 не под­хо­дит по ана­ло­гич­ной при­чи­не.

2) Код Г=000 не со­па­да­ет с на­ча­лом ни од­но­го кода,сле­до­ва­тель­но это и есть пра­виль­ный ответ.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

№2. Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=0, Б=100, В=101. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?

1) 1

2) 11

3) 01

4) 010

По­яс­не­ние.

Для того, чтобы со­об­ще­ние, за­пи­сан­ное с по­мо­щью не­рав­но­мер­но­го по длине кода, од­но­знач­но рас­ко­ди­ро­ва­лось, тре­бу­ет­ся, чтобы ни­ка­кой код не был на­ча­лом дру­го­го (более длин­но­го) кода.

Рас­смот­рим ва­ри­ан­ты для буквы Г, на­чи­ная с са­мо­го ко­рот­ко­го.

1) Г=1: код буквы Г яв­ля­ет­ся на­ча­лом кода буквы В=101 и Б=100, по­это­му этот ва­ри­ант не под­хо­дит.

2) Код Г=11 не со­па­да­ет с на­ча­лом ни од­но­го кода,сле­до­ва­тель­но это и есть пра­виль­ный ответ.

В ва­ри­ан­тах 3) и 4) код буквы А=0 яв­ля­ет­ся на­ча­лом кода буквы Г, по­это­му они не под­хо­дят.

№3. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111.

Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му можно было де­ко­ди­ро­вать од­но­знач­но? Коды осталь­ных букв ме­нять­ся не долж­ны. Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

1) это не­воз­мож­но

2) для буквы В – 000

3) для буквы Б – 0

4) для буквы Г – 11

По­яс­не­ние.

Мы видим, что вы­пол­ня­ет­ся усло­вие Фано: ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова, по­это­му од­но­знач­но можем рас­ко­ди­ро­вать со­об­ще­ние с на­ча­ла.

Чтобы со­кра­тить код одной буквы, не­об­хо­ди­мо вы­пол­не­ние усло­вия Фано в новом коде.

Ва­ри­ант 3 не под­хо­дит, по­то­му что 0 яв­ля­ет­ся на­ча­лом кода 0001.

Ва­ри­ант 4 не под­хо­дит, по­то­му что код 1 яв­ля­ет­ся на­ча­лом кода 111.

Ва­ри­ант 2 под­хо­дит, так как не на­ру­ша­ет усло­вия Фано.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

№4. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность. Вот этот код: А–011, Б–000, В–11, Г–001, Д–10. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му можно было де­ко­ди­ро­вать од­но­знач­но? Коды осталь­ных букв ме­нять­ся не долж­ны. Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

1) это не­воз­мож­но

2) для буквы А – 01

3) для буквы Б – 00

4) для буквы Г – 00

По­яс­не­ние.

Мы видим, что вы­пол­ня­ет­ся усло­вие Фано: ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова, по­это­му од­но­знач­но можем рас­ко­ди­ро­вать со­об­ще­ние с на­ча­ла.

Чтобы со­кра­тить код одной буквы, не­об­хо­ди­мо вы­пол­не­ние усло­вия Фано в новом коде.

Ва­ри­ант 3 не под­хо­дит, по­то­му что 00 яв­ля­ет­ся на­ча­лом кода 001.

Ва­ри­ант 4 не под­хо­дит, по­то­му что код 00 яв­ля­ет­ся на­ча­лом кода 000.

Ва­ри­ант 2 под­хо­дит, так как не на­ру­ша­ет усло­вия Фано.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

№5. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му можно было де­ко­ди­ро­вать од­но­знач­но? Коды осталь­ных букв ме­нять­ся не долж­ны. Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

1) для буквы Д – 11

2) это не­воз­мож­но

3) для буквы Г – 10

4) для буквы Д – 10

По­яс­не­ние.

Мы видим, что вы­пол­ня­ет­ся усло­вие Фано: ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова, по­это­му од­но­знач­но можем рас­ко­ди­ро­вать со­об­ще­ние с на­ча­ла.

Чтобы со­кра­тить код одной буквы, не­об­хо­ди­мо вы­пол­не­ние усло­вия Фано в новом коде.

Ва­ри­ант 3 не под­хо­дит, по­то­му что 10 яв­ля­ет­ся на­ча­лом кода 100.

Ва­ри­ант 4 не под­хо­дит, по­то­му что код 10 яв­ля­ет­ся на­ча­лом кода 100 и 101.

Ва­ри­ант 1 под­хо­дит, так как не на­ру­ша­ет усло­вия Фано.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

№6. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать дво­ич­ную по­сле­до­ва­тель­ность, по­яв­ля­ю­щу­ю­ся на приёмной сто­ро­не ка­на­ла связи. Для букв А, Б, В и Г ис­поль­зо­ва­ли такие ко­до­вые слова: А–111, Б–110, В–100, Г–101.

Ука­жи­те, каким ко­до­вым сло­вом может быть за­ко­ди­ро­ва­на буква Д. Код дол­жен удо­вле­тво­рять свой­ству од­но­знач­но­го де­ко­ди­ро­ва­ния. Если можно ис­поль­зо­вать более од­но­го ко­до­во­го слова, ука­жи­те крат­чай­шее из них.

1) 0

2) 01

3) 00

4) 000

По­яс­не­ние.

Мы видим, что вы­пол­ня­ет­ся усло­вие Фано: ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова, по­это­му од­но­знач­но можем рас­ко­ди­ро­вать со­об­ще­ние с на­ча­ла.

Чтобы за­ко­ди­ро­вать Д, не­об­хо­ди­мо вы­пол­не­ние усло­вия Фано в новом коде.

Каж­дый из этих ва­ри­ан­тов может быть новым сло­вом, т. к. не яв­ля­ет­ся на­ча­лом ни од­но­го из ко­до­вых слов. По­это­му вы­би­ра­ем самое ко­рот­кое — 0.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

№7. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать дво­ич­ную по­сле­до­ва­тель­ность, по­яв­ля­ю­щу­ю­ся на приёмной сто­ро­не ка­на­ла связи. Для букв А, Б, В и Г ис­поль­зо­ва­ли такие ко­до­вые слова: А — 100, Б — 101, В — 111, Г — 110.

Ука­жи­те, каким ко­до­вым сло­вом из пе­ре­чис­лен­ных ниже может быть за­ко­ди­ро­ва­на буква Д. Код дол­жен удо­вле­тво­рять свой­ству од­но­знач­но­го де­ко­ди­ро­ва­ния. Если можно ис­поль­зо­вать более од­но­го ко­до­во­го слова, ука­жи­те крат­чай­шее из них.

1) 000

2) 10

3) 11

4) 1111

По­яс­не­ние.

Для того, чтобы со­об­ще­ние, за­пи­сан­ное с по­мо­щью не­рав­но­мер­но­го по длине кода, од­но­знач­но рас­ко­ди­ро­ва­лось, тре­бу­ет­ся, чтобы ни­ка­кой код не был на­ча­лом дру­го­го (более длин­но­го) кода.

Рас­смот­рим ва­ри­ан­ты для буквы Д, на­чи­ная с са­мо­го ко­рот­ко­го.

1) Д=10: код буквы Д яв­ля­ет­ся на­ча­лом кода буквы Б=101, по­это­му этот ва­ри­ант не под­хо­дит.

2) Д=11: код буквы Д яв­ля­ет­ся на­ча­лом кода буквы В=111, Д=110, по­это­му этот ва­ри­ант не под­хо­дит.

3) Д=000: код буквы Д не яв­ля­ет­ся на­ча­лом дру­го­го кода, сле­до­ва­тель­но, это пра­виль­ный ответ.

4) Д=1111: код буквы Д яв­ля­ет­ся на­ча­лом кода буквы В=111, по­это­му этот ва­ри­ант не под­хо­дит.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

№8. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать дво­ич­ную по­сле­до­ва­тель­ность, по­яв­ля­ю­щу­ю­ся на приёмной сто­ро­не ка­на­ла связи. Для букв А, Б, В и Г ис­поль­зо­ва­ли такие ко­до­вые слова: А — 001, Б — 010, В— 000, Г — 011.

Ука­жи­те, каким ко­до­вым сло­вом из пе­ре­чис­лен­ных ниже может быть за­ко­ди­ро­ва­на буква Д.

Код дол­жен удо­вле­тво­рять свой­ству од­но­знач­но­го де­ко­ди­ро­ва­ния. Если можно ис­поль­зо­вать более од­но­го ко­до­во­го слова, ука­жи­те крат­чай­шее из них.

1) 00

2) 01

3) 101

4) 0000

По­яс­не­ние.

Для того, чтобы со­об­ще­ние, за­пи­сан­ное с по­мо­щью не­рав­но­мер­но­го по длине кода, од­но­знач­но рас­ко­ди­ро­ва­лось, тре­бу­ет­ся, чтобы ни­ка­кой код не был на­ча­лом дру­го­го (более длин­но­го) кода.

Рас­смот­рим ва­ри­ан­ты для буквы Д, на­чи­ная с са­мо­го ко­рот­ко­го.

1) Д=00: код буквы Д яв­ля­ет­ся на­ча­лом кода буквы В=000, по­это­му этот ва­ри­ант не под­хо­дит.

2) Д=01: код буквы Д яв­ля­ет­ся на­ча­лом кода буквы Б=010, Г=011, по­это­му этот ва­ри­ант не под­хо­дит.

3) Д=101: код буквы Д не яв­ля­ет­ся на­ча­лом дру­го­го кода, сле­до­ва­тель­но, это пра­виль­ный ответ.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

№9. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать дво­ич­ную по­сле­до­ва­тель­ность, по­яв­ля­ю­щу­ю­ся на приёмной сто­ро­не ка­на­ла связи. Для букв А, Б, В и Г ис­поль­зо­ва­ли такие ко­до­вые слова: А — 111, Б — 110, В — 101, Г — 100.

Ука­жи­те, каким ко­до­вым сло­вом из пе­ре­чис­лен­ных ниже может быть за­ко­ди­ро­ва­на буква Д. Код дол­жен удо­вле­тво­рять свой­ству од­но­знач­но­го де­ко­ди­ро­ва­ния. Если можно ис­поль­зо­вать более од­но­го ко­до­во­го слова, ука­жи­те крат­чай­шее из них.

1) 1

2) 0

3) 01

4) 10

По­яс­не­ние.

Для того, чтобы со­об­ще­ние, за­пи­сан­ное с по­мо­щью не­рав­но­мер­но­го по длине кода, од­но­знач­но рас­ко­ди­ро­ва­лось, тре­бу­ет­ся, чтобы ни­ка­кой код не был на­ча­лом дру­го­го (более длин­но­го) кода. Рас­смот­рим ва­ри­ан­ты для буквы Д, на­чи­ная с са­мо­го ко­рот­ко­го.

1) Д=1: код буквы Д яв­ля­ет­ся на­ча­лом всех пред­став­лен­ных кодов букв, по­это­му этот ва­ри­ант не под­хо­дит.

2) Д=0: код буквы Д не яв­ля­ет­ся на­ча­лом дру­го­го кода, по­это­му этот ва­ри­ант под­хо­дит.

3) Д=01: код буквы Д не яв­ля­ет­ся на­ча­лом дру­го­го кода, по­это­му этот ва­ри­ант под­хо­дит.

4) Д=10: код буквы Д яв­ля­ет­ся на­ча­лом кодов букв В и Г, сле­до­ва­тель­но, этот ва­ри­ант не под­хо­дит.

Таким об­ра­зом, под­хо­дят два ва­ри­ан­та: 0 и 01. 0 ко­ро­че, чем 01.

Пра­виль­ный ответ ука­зан под но­ме­ром 2.

№10. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы: E, H, O, T. Для ко­ди­ро­ва­ния букв E, H, O ис­поль­зу­ют­ся 5-би­то­вые ко­до­вые слова: E — 00000, H — 00111, O — 11011.

Для этого на­бо­ра ко­до­вых слов вы­пол­не­но такое свой­ство: любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трех по­зи­ци­ях.

Это свой­ство важно для рас­шиф­ров­ки со­об­ще­ний при на­ли­чии помех. Какое из пе­ре­чис­лен­ных ниже ко­до­вых слов можно ис­поль­зо­вать для буквы T, чтобы ука­зан­ное свой­ство вы­пол­ня­лось для всех четырёх ко­до­вых слов?

1) 11111

2) 11100

3) 00011

4) не под­ходт ни одно из ука­зан­ных выше слов

По­яс­не­ние.

Поль­зу­ясь пра­ви­лом «любые два слова из на­бо­ра от­ли­ча­ют­ся не менее чем в трех по­зи­ци­ях» про­ве­рим все воз­мож­ные ва­ри­ан­ты.

Число 11111 от­ли­ча­ет­ся от ко­до­во­го слова 00111 толь­ко в двух по­зи­ци­ях.

Число 11100 от­ли­ча­ет­ся от ко­до­во­го слова 00000 — в трех по­зи­ци­ях, от 00111 — в че­ты­рех по­зи­ци­ях, 11011 — в трех по­зи­ци­ях.

Пра­виль­ный ва­ри­ант от­ве­та вто­рой.

Для кодирования букв решили использовать двоичное представление – как решать

Формулировка задания: Для кодирования букв решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв таким способом и результат записать восьмеричным кодом, то получится…

Задание входит в ЕГЭ по информатике для 11 класса под номером 5 (Кодирование и декодирование информации).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится

1. 22162
2. 1020342
3. 2131453
4. 34017

Решение:

Закодируем последовательность букв ВОДОПАД посимвольно с помощью заданного двоичного представления (с сохранением одного незначащего нуля в случае одноразрядного представления):

В = 01

О = 00

Д = 10

О = 00

П = 11

А = 100

Д = 10

Значит закодированная последовательность будет равна:

Чтобы перевести последовательность в восьмеричный код, разобьем ее на группы по 3 символа:

И переведем каждую группу символов из двоичной системы в восьмеричную:

010₂ = 2₈

010₂ = 2₈

001₂ = 1₈

110₂ = 6₈

010₂ = 2₈

Таким образом, в результате получилось восьмеричное число 22162, это ответ номер 1.

Ответ: 1

Поделитесь статьей с одноклассниками «Для кодирования букв решили использовать двоичное представление – как решать».

При копировании материалов с сайта ссылка на источник обязательна. Уважайте труд людей, которые вам помогают.
Нашли ошибку? Выделите текст и нажмите Ctrl + Enter.

для кодирования букв о к г д р решили использовать двоичное представление чисел 0 1 2 3 и 4

Не могу написать проверку на високосный/не високосный год для февраля. Пыталась вводить и без проверки, но даже так февраль не выводится. Вот условие: … Напишите программу, которая запрашивает день, месяц, год и осуществляет проверку на корректный ввод данных (даты). Необходимо учитывать количество дней согласно месяцу, високосный/не високосный год. Значение года – четырехзначное положительное число. При вводе некорректных данных – сообщение. Если же дата введена верно, вывести на экран с названием месяца. Например, 9 июля 2021 г. int day, month, year; cout << «Введите день, месяц и год: «; cin >> day >> month >> year; if (year > 0) { if (month <= 12 && month >= 1) { if (day <= 31) { if (day >= 1 || day == 31) switch (month) { case 1: cout << day << » января » << year; break; case 3: cout << day << » марта » << year; break; case 5: cout << day << » мая » << year; break; case 7: cout << day << » июля » << year; break; case 8: cout << day << » августа » << year; break; case 10: cout << day << » октября » << year; break; case 12: cout << day << » декабря » << year; break; default: cout << «Неверный день.»; } else if (day >= 1 || day == 30) switch (month) { case 4: cout << day << » апреля » << year; break; case 6: cout << day << » июня » << year; break; case 9: cout << day << » сентября » << year; break; case 11: cout << day << » ноября » << year; break; default: cout << «Неверный день.»; } else if (day >= 1 || day == 29 && year %4 ==0 && year%100 !=0) switch (month) { case 2: cout << day << » февраля » << year; break; default: cout << «Неверный день.»; } } else cout << «Неверный день.»; } else cout << «Неверный месяц.»; } else cout << «Неверный год.»;

!МАКСИМУМ БАЛЛОВ! Выделите основную информацию, которую бы Вы вынесли на главную страницу сайта «Компьютерные курсы для школьников». Зарисуйте структу … ру главной страницы подобного сайта буду крайне благодарна

№9. Напишите программу, которая вводит два целых числа и находит их произведение, не используя операцию умножения. Учтите, что числа могут быть отрица … тельными. Входные данные Входная строка содержит два целых числа. Выходные данные Программа должна вывести произведение введённых чисел

Помогите решить задание на пайтон Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 26, запись которых в троичной сис … теме счисления оканчивается на 22?

задание с предикатом ,,,,,,,

Помогите решить это задание на Python, пожалуйста Значение выражения 3435 + 73 − 1 − X записали в системе счисления с основанием 7, при этом в записи … оказалось 12 цифр 6. При каком минимальном целом положительном X это возможно?

люди, кто разбирается в HTML-разметке и KompoZer, помогите, пожалуйста [прикрепляю номер на картинке, чтобы было удобнее]

Приведите 4 примера математических моделей каких-либо процессов. Опишите данные модели!

Диофантово уравнение Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x им … еет наименьшее неотрицательное значение, и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите −1. Входные данные Входные данные — натуральные числа a, b и c. Числа заданы на одной строке через пробел и не превышают 109. Выходные данные Выведите ответ на задачу. Примеры Ввод 1 2 3 Вывод 1 1 Ввод 2 2 2 Вывод 0 1 Решите на c++

Срочно, на ПИТОНЕ Разложение на чётнопростые В этой задаче рассматриваются только чётные целые числа. Чётное натуральное число n будем называть чётноп … ростым числом, если его нельзя представить в виде произведения двух чётных чисел. Например, числа 2 и 6 — чётнопростые. Очевидно, что каждое число либо является чётнопростым, либо разлагается в произведение чётнопростых. Но такое разложение на чётнопростые не всегда единственно. Входные данные Дано чётное натуральное n≤109. Выходные данные Если число n чётнопростое, выведите слово prime. Если это число единственным образом разлагается в произведение двух и более чётнопростых, то выведите слово single, а в следующей строке выведите разложение этого числа на чётнопростые множители. Если число допускает несколько различных разложений на чётнопростые, то выведите слово many, а в следующих двух строках выведите два каких-нибудь различных разложения числа на чётнопростые множители.

Решение задач

Разбор решения задач по теме «Информация. Кодирование информации»

A1 вариант 1

Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 720 бит. Какова длина сообщения в символах?

1) 90

2) 45

3) 180

4) 720

Решение:

При переходе от 16 битной к 8 битной кодировке, размер сообщения в битах уменьшится вдвое. Раз оно уменьшилось на 720 бит, то длина сообщения в символах кодировки КОИ-8 составила 720 символов.

Ответ: 4.

A1 вариант2

В кодировке Unicode на каждый символ отводится два байта. Определите информационный объем слова из двадцати четырех символов в этой кодировке.

1) 384 бита;

2) 192 бита;

3) 256 бит;

4) 48 бит.

Решение:

24 * 2байта=48 байтов=384 бита

Ответ: №1

A1 вариант 3

Считая, что каждый символ кодируется 16 битами, оцените информационный объем следующей Пушкинской фразы в кодировке Unicode:

Привычка свыше нам дана: Замена счастию она.

1) 44 бита;

2) 704 бита;

3) 44 байта;

4) 704 байта.

Решение

Данное предложение содержит 44 символа (включая точку и двоеточие), то есть в кодировке Unicode оно содержит 88 байт или 704 бита.

Ответ: № 2

A11(A13)

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ВАГБ и записать результат шестнадцатеричным кодом, то получится:

1) 8D

2) CADB

3) 813

4) 2031.

Решение:

Пользуясь кодовой таблицей,

Запишем ВАГБ=100011012=8D16

Ответ:

1) 8D.

В7

Скорость передачи данных через ADSL-соединение равна 128000 бит/c. Через данное соединение передают файл размером 625 Кбайт. Определите время передачи файла в секундах.

Решение: 1) Переводим размер файла в биты: 625 килобайт * 1024 * 8 = 5120000 бит.

2) Определяем время передачи файла 51200000 / 128000 = 40 секунд

Ответ – 40.

Кодирование и декодирование информации. ЕГЭ — Информатика и ИКТ

Задание:

1) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится: 
1) 132₁₆     2) D2₁₆     3) 3102₁₆     4) 2D₁₆ 

Решение и ответ:

Из условия соответственно:
А — 00
Б — 01
В — 10
Г — 11
ГБАВ = 11010010 — переведем данную двоичную запись в шестнадцатеричную систему и получим D2
Ответ: 2

2) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБВА и записать результат шестнадцатеричным кодом, то получится:

1) 138₁₆    2) DBCA₁₆    3) D8₁₆    4) 3120₁₆

Решение и ответ:

По условию:
А = 00
Б = 01
В = 10
Г = 11
Значит:
ГБВА = 11011000 в двоичной системе. Переведем в шестнадцатеричную и получим D8
Ответ: 3

3) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти  коды представлены в таблице:
  a        b       c       d        e
000    110    01    001    10
Определите, какой набор букв закодирован двоичной строкой 1100000100110    
1) baade    2) badde    3) bacde    4) bacdb

Решение и ответ:

Первая буква — b, так как стоит двоичный код 110
Вторая буква — a, так как стоит двоичный код 000
Третья буква — с, так как стоит двоичный код 01
Четвертая буква — d, так как стоит двоичный код 001
Пятая буква — e, так как стоит двоичный код 10
Итог: bacde, что соответствует варианту под номером 3.
Ответ: 3

4) Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:
1) 175423       2) 115612      3) 62577    4) 12376

Решение и ответ:

По условию:
А = 1000
Б = 1001
В = 1010
Г = 1011
БГАВ = 1001101110001010, теперь слудует перевести данное число из двоичной в восьмеричную, и получить ответ.
1001101110001010₂ = 115612₈

Ответ: 2

5) 

Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится:
1) А52₁₆    2) 4С8₁₆    3) 15D₁₆    4) DE5₁₆

Решение и ответ:

По условию: Соответственно
A = 100
B = 101
C = 110
D = 111
СDAB = 110111100101, переведем двоичное число в шестнадцатеричную:
110111100101₂ = DE5₁₆
Ответ: 4

6) Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится:
1) 84613₈    2) 105233₈    3) 12345₈    4) 776325₈

Решение и ответ:

По условию: соответственно
K = 1000
L = 1001
M = 1010
N = 1011
KMLN = 1000101010011011, переведем в восьмеричное число:

1000101010011011₂ = 105233₈

Ответ: 2

7) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

  а        b         с       d       е
100    110     011    01    10
Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:
1) cbade    2) acdeb    3) acbed    4) bacde

Решение и ответ:

Запишем двоичный код в виде битов: Методом перебора возможных вариантов, чтобы не повторялись буквы.
Получается: 100 011 01 10 110
Следовательно: acdeb
Ответ: 2

8) Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
 А       В        С       D       Е        F
00     100     10     011    11     101
Определите, какая последовательность из 6 букв закодирована двоичной строкой 011111000101100.
1) DEFBAC        2) ABDEFC        3) DECAFB        4) EFCABD

Решение и ответ:

Решим методом перебора, так как буквы в ответах не повторяются, значит и коды не должны повторяться:

Получаем:
 011 11 10 00 101 100
Соответственно: DECAFB
Ответ: 3

9) Для кодирования букв А, В, С, D используются четырехразрядные последовательные двоичные числа, начинающиеся с 1 (от 1001 до 1100 соответственно). Если таким способом закодировать последовательность символов CADB и записать результат в шестнадцатеричном коде, то получится:
1) AF52₁₆    2) 4CB8₁₆       3) F15D₁₆       4) В9СА₁₆

Решение и ответ: соответственно..
A — 1001
B — 1010
C — 1011
D — 1100
Значит: CADB = 1011100111001010, переведем 1011100111001010 из двоичной в шестнадцатеричную:
 1011 1001 1100 1010₂= B9CA₁₆, что соответствует четвертому варианту.
Ответ: 4

10) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
 А      Б     В      Г
00     11    010    011
Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится:
1) CDADBC₁₆    2) A7C4₁₆           3) 412710₁₆     4) 4С7А₁₆

Решение и ответ: 

ВГАГБВ = 0100110001111010, переведем в шестнадцатеричную:
0100 1100 0111 1010₂ = 4C7A₁₆

Ответ: 4

11) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
 А      Б      В         Г
00     11    010    011
Если таким способом закодировать последовательность символов ГАВБВГ и записать результат в шестнадцатеричном коде, то получится:
1) 62D3₁₆    2) 3D26₁₆           3) 31326₁₆     4) 62133₁₆

Решение и ответ:
ГАВБВГ = 0110001011010011_{2  —}  Переведем в шестнадцатеричную систему:
0110 0010 1101 0011₂ = 62D3₁₆

Ответ: 1

12)  Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине 

двоичный код:
 А       Б       В       Г
00     11    010    011
Если таким способом закодировать последовательность символов ГБВАВГ и записать результат в шестнадцатеричном 

коде, то получится:
1) 71013₁₆    2) DBCACD₁₆           3) 31A7₁₆     4) 7A13₁₆

Решение и ответ: 
ГБВАВГ = 0111101000010011₂  — переведем в шестнадцатеричную.
0111 1010 0001 0011₂ = 7A13₁₆
Ответ: 4

13) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
 А      Б      В         Г
00     11    010    011
Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:
1) DACBDC₁₆    2) AD26₁₆           3) 621310₁₆     4) 62DA₁₆
Решение и ответ: соответственно..

ГАВБГВ = 0110001011011010₂, переведем в шестнадцатеричную:
0110 0010 1101 1010₂ = 62DA₁₆
Ответ: 4

14)    Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код:
 A         B     C      D       E
000     11    01    001    10
Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:
1) 110000010011110
2) 110000011011110      
3) 110001001001110
4) 110000001011110

Решение и ответ:

Возьмем первый код: 
11 000 001 001 11 10 = BADDBE
Второй код: 
11 000 001 10 11 110 = с ошибкой в конце.
Третий код:
11 000 10 01 001 110 = с ошибкой в конце.
Четвертый код:
11 000 000 10 11 110 = с ошибкой в конце.
Ответ: 1

15) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное 

кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение 

данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид. 
1) AD34     2) 43DA     3) 101334     4) CADBCD 
Решение и ответ:

ВАГБГВ = 0100001111011010₂, переведем в шестнадцатеричную систему:
0100 0011 1101 1010₂ = 43DA₁₆
Ответ: 2

16) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 
1) 0001     2) 000     3) 11     4) 101 
Решение и ответ: 
Для того, чтобы сообщение раскодировалось, требуется, чтобы ни один код не был началом другого — более длинного кода.

1, 3 и 4 варианты не подходят, являются началом других кодов.
2 вариант — не является началом других кодов.
Ответ: 2

17) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 

1) 1     2) 11     3) 01     4) 010 

Аналогично заданию номер 16.

Ответ: 2

18) Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.
1) 57414     2) 53414     3) 53412     4) 53012 
 
Решение и ответ:
После кодирования мы получаем данный код:

101011100001010₂, переведем данный код в восьмеричную:
101 011 100 001 010₂ = 53412₈

Ответ: 3

19) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное 

кодирование: А-0, Б-11, В-100, Г-011. Через канал связи передается сообщение: ГБАВАВГ. Закодируйте сообщение 

данным кодом. Полученную двоичную последовательность переведите в восьмеричный код. 
1) DBACACD     2) 75043     3) 7A23     4) 3304043 
Решение и ответ: Соответственно:
ГБАВАВГ = 0111101000100011₂, переведем в восьмеричную систему.
0 111 101 000 100 011₂ = 75043₈, первый нолик не значащий.
Ответ: 2

20) Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только 

буквы А, Б и В, которые кодируются следующими кодовыми словами:

A — 11010, Б — 00110, В — 10101.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому  если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б — только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка(она обозначается‘x’).

Получено сообщение 00111 11110 11000 10111. Декодируйте это сообщение — выберите правильный  вариант.

1) БААx
2) БААВ
3) xxxx
4) xAAx

Решение:
1) 00111 = Б, так как 1 ошибка в последней цифре.
2) 11110 = A, так как 1 ошибка в третьей цифре.
3) 11000 = А, так как 1 ошибка в четвертой цифре.
4) 10111 = В, так как 1 ошибка в четвертой цифре

00111 11110 11000 10111 = БААВ.
Ответ: 2

11. Какие коды используются в вычислительной технике для кодирования букв русского алфавита?

Windows-1251 — набор символов и кодировка, являющаяся стандартной 8-битной кодировкой для всех русских версий Microsoft Windows.

UTF-8 – распространённая кодировка символов Юникода, совместимая с 8-битными форматами передачи текста. Нашла широкое применение в операционных системах и веб-пространстве.

КОИ-8 – восьмибитовая ASCII-совместимая кодовая страница, разработанная для кодирования букв кириллических алфавитов.

ISO 8859-5 – 8-битная кодовая страница из семейства кодовых страниц стандарта ISO-8859 для представления кириллицы.

14. Как кодируется графическая информация, если изображение черно-белое? цветное?

В процессе кодирования изображения производится его пространственная дискретизация. Пространственную дискретизацию изображения можно сравнить с построением изображения из мозаики. Изображение разбивается на отдельные маленькие фрагменты (точки), причем каждому фрагменту присваивается значение его цвета, то есть код цвета (красный, зеленый, синий и так далее). Для черно-белого изображения информационный объем одной точки равен одному биту (либо черная, либо белая – либо 1, либо 0).

Контрольные вопросы (развернутые ответы)

4. Основные результаты теории кодирования.

Кодирование преследует несколько целей. Первая из них заключается в том, чтобы представить сообщения в такой системе символов, которая обеспечивала бы простоту и надежность аппаратной реализации информационных устройств и их необходимую эффективность. Вторая цель кодирования состоит в том, чтобы обеспечить наилучшее согласование свойств источника сообщений со свойствами канала связи. Путем такого согласования добиваются выигрыша во времени передачи, то есть повышения эффективности системы. Наконец, при наличии помех кодирование может обеспечить достаточно высокую достоверность передачи или обработки информации. В процессе хранения данных и передачи информации по сетям связи неизбежно возникают ошибки. Так в простых (примитивных) кодах ошибка в приеме хотя бы одного элемента кодовой комбинации приводит к неправильной регистрации передаваемого сообщения. Корректирующие коды позволяют обнаруживать и устранять ошибки в кодовых комбинациях. Кодирование, обеспечивающее изменение структуры сигналов, ни в какой мере не должно изменять количество информации, заключенном в первоначальном сообщении.

8. Основные теоремы теории кодирования и их следствия.

Коды Хэмминга – наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления. Коды Хэмминга являются самоконтролирующимися кодами, то есть кодами, позволяющими автоматически обнаруживать ошибки при передаче данных. Для их построения достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру этого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок. При этом невозможно узнать, в каком именно разряде произошла ошибка, и, следовательно, нет возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, в четырёх или вообще в четном количестве разрядов. Впрочем, двойные, а тем более четырёхкратные ошибки полагаются маловероятными.

Коды Рида — Соломона – недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами). Коды Рида — Соломона являются важным частным случаем БЧХ-кода.

Коды Боуза — Чоудхури — Хоквингхема (БЧХ-коды) – в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибо. Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием.

Теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии (мера неопределённости или непредсказуемости информации) Шеннона. Теорема Шеннона об источнике шифрования показывает, что (когда в потоке независимо и одинаково распределенных случайных переменных данные стремятся к бесконечности) невозможно сжать данные настолько, что оценка кода (среднее число бит на символ) меньше чем энтропия Шеннона исходных данных, без потери точности информации. Тем не менее можно получить код, близкий к энтропии Шеннона без значительных потерь.

Урок 14. кодирование текстовой информации — Информатика — 10 класс

Информатика, 10 класс. Урок № 14.

Тема — Кодирование текстовой информации

Цели и задачи урока:

— познакомиться со способами кодирования и декодирования текстовой информации с помощью кодовых таблиц и компьютера;

— познакомиться со способом определения информационного объема текстового сообщения;

— познакомиться с алгоритмом Хаффмана.

Вся информация в компьютере хранится в двоичном коде. Поэтому надо научиться преобразовывать символы в двоичный код.

Формула Хартли определяет количество информации в зависимости от количества возможных вариантов:

N=2ⁱ, где

N — это количество вариантов,

i — это количество бит, не обходимых для кодирования.

Если же мы преобразуем эту формулу и примем за N — количество символов в используемом алфавите (назовем это мощностью алфавита), то мы поймем, сколько памяти потребуется для кодирования одного символа.

N=2ⁱ, где N — кол-во возможных вариантов

i — кол-во бит, потребуемых для кодирования

Итак, если в нашем алфавите будет присутствовать только 32 символа, то каждый из них займет только 5 бит.

И тогда каждому символу мы дадим уникальный двоичный код. Такую таблицу мы будем назвать кодировочной.

Первая широко используемая кодировочная таблица была создана в США и называлась ASCII, что в переводе означало American standard code for information interchange. Как вы видите, в таблице присутствуют не только латинские буквы, но и цифры, и даже действия. Каждому символу отводится 7 бит, а значит, всего было закодировано 128 символов.

Но так как этого количества было недостаточно, стали создаваться другие таблицы, в которых можно было закодировать и другие символы. Например, таблица Windows-1251, которая, по сути, являлась изменением таблицы ASCII, в которую добавили буквы кириллицы. Таких таблиц было создано множество: MS-DOS, КОИ-8, ISO, Mac и другие:

Проблема использования таких различных таблиц приводила к тому, что текст, написанный на одном компьютере, мог некорректно читаться на другом. Например:

Поэтому была разработана международная таблица кодировки Unicode, включающая в себя как символы английского, русского, немецкого, арабского и других языков. На каждый символ в такой таблице отводится 16 бит, то есть она позволяет кодировать 65536 символов. Однако использование такой таблицы сильно «утяжеляет» текст. Поэтому существуют различные алгоритмы неравномерной кодировки текста, например, алгоритм Хаффмана.

АЛГОРИТМ ХАФФМАНА

Идея алгоритма Хаффмана основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код.

Пусть нам дано сообщение aaabcbeeffaabfffedbac.

Чтобы узнать наиболее выгодный префиксный код для такого сообщения, надо узнать частоту появления каждого символа в сообщении.

Шаг 1.

Подсчитайте и внесите в таблицу частоту появления каждого символа в сообщении:

У вас должно получиться:

Шаг 2.

Расположите буквы в порядке возрастания их частоты.

Шаг 3.

Теперь возьмем два символа с наименьшей чистотой и представим их листьями в дереве, частота которого будет равна сумме частот этих листьев.

Символы d и c превращаются в ветку дерева:

Шаг 4.

Проделываем эти шаги до тех пор, пока не получится дерево, содержащее все символы.

Итак, сортируем таблицу:

Шаг 5.

Объединяем символ e и символ cd в ветку дерева:

d

C

Шаг 6.

Сортируем:

Шаг 7.

Шаг 8.

Сортируем:

Шаг 9.

Шаг 10.

Сортируем:

Шаг 11.

Шаг 12.

Получился префиксный код. Теперь осталось расставить 1 и 0. Пусть каждая правая ветвь обозначает 1, а левая — 0.

Шаг 13.

Составляем код буквы, идя по ветке дерева от буквы к основанию дерева.

Тогда код для каждой буквы будет:

Задание №1

Закодируйте ASCII кодом слово MOSCOW.

Решение:

Составим таблицу и поместим туда слово MOSCOW. Используя таблицу ASCII кодов, закодируем все буквы слова:

ОТВЕТ: 100110110011111010011100001110011111110111

Задание №2

Используя табличный код Windows1251, закодируйте слово КОМПЬЮТЕР.

Решение:

Ответ: 234206204239252254242197208

Задание №3

Используя алгоритма Хаффмана, закодируйте сообщение: Россия

Решение:

Давайте все левые ветви обозначим «1», а правые – «0»

Таким образом: С — 0, Р — 101, О — 100, И — 111, Я — 110

ОТВЕТ: 10110000111110

Кодировок символов для начинающих

Во-первых, какое мне дело?

Если вы используете что-либо, кроме самого основного текста на английском языке, люди не смогут прочитать созданный вами контент. если вы не укажете, какую кодировку символов вы использовали.

Например, вы можете сделать так, чтобы текст выглядел так:

, но на самом деле он может отображаться так:

Отсутствие информации о кодировке символов не только портит удобочитаемость отображаемого текста, но также может означать, что ваши данные не могут быть найдены поисковой системой или надежно обрабатывается машинами другими способами.

Так что за кодировка символов?

Слова и предложения в тексте состоят из знаков . Примеры символов включают латинскую букву á, китайскую идеограмму 請 или символ деванагари ह.

Возможно, вы не сможете увидеть некоторые символы на этой странице, потому что у вас нет необходимых шрифтов. Если вы нажмете на то место, где вы ожидали увидеть персонажа, вы перейдете к графической версии. Эта страница закодирована в UTF-8.

Персонажи, необходимые для определенной цели, сгруппированы в набор символов (также называемый репертуаром ). (Чтобы однозначно обозначать символы, каждый символ связан с числом, называемым кодовой точкой .)

Символы хранятся в компьютере как один или несколько байтов .

В принципе, вы можете визуализировать это, предположив, что все символы хранятся в компьютерах с использованием специального кода, как шифры, используемые в шпионаже.Кодировка символов предоставляет ключ для разблокировки (т. Е. Взлома) кода. Это набор соответствий между байтами в компьютере и символами в наборе символов. Без ключа данные выглядят как мусор.

Вводящий в заблуждение термин кодировка часто используется для обозначения того, что в действительности является кодировкой символов. Вам следует помните об этом использовании, но всегда старайтесь использовать термины кодировки символов.

Итак, когда вы вводите текст с клавиатуры или каким-либо другим способом, кодировка символов сопоставляет выбранные вами символы с конкретными байтами в памяти компьютера, а затем для отображения текста считывает байты обратно в символы.

К сожалению, существует множество различных наборов символов и кодировок символов, т.е. много разных способов сопоставления байтов, кодовые точки и символы. В разделе «Дополнительная информация» для тех, кому интересно, чуть подробнее.

Однако в большинстве случаев вам не нужно знать подробности. Вам просто нужно убедиться, что вы прислушиваетесь к советам раздел Как это влияет на меня? ниже.

Как в это вписываются шрифты?

Шрифт — это набор определений глифов, т. Е.определения форм, используемых для отображения символов.

Как только ваш браузер или приложение определит, с какими символами имеет дело, оно будет искать в шрифте глифы, которые можно использовать для отображения. или распечатайте эти символы. (Конечно, если информация о кодировке была неправильной, она будет искать глифы для неправильных символов.)

Данный шрифт обычно покрывает один набор символов или, в случае большого набора символов, например Unicode, только подмножество всех персонажей в наборе.Если в вашем шрифте нет глифа для определенного символа, некоторые браузеры или программные приложения будут искать отсутствующие глифы в других шрифты в вашей системе (это будет означать, что глиф будет отличаться от окружающего текста, как записка с требованием выкупа). В противном случае вы обычно вместо этого вы увидите квадратную рамку, вопросительный знак или какой-либо другой символ. Например:

Как это повлияет на меня?

Как автор или разработчик контента, в настоящее время вы всегда должны выбирать UTF-8 кодировка символов для вашего контента или данных.Эта кодировка Unicode — хороший выбор, потому что вы можете использовать односимвольную кодировку для обработки любого символа, который вам может понадобиться. Это значительно упрощает работу. Использование Unicode во всей вашей системе также устраняет необходимость отслеживать и преобразовывать между различными кодировками символов.

Авторы контента должны узнать, как объявить персонажа кодировка, используемая для формата документа, с которым они работают.

Обратите внимание, что просто объявление другой кодировки на вашей странице не изменит байты; вам также нужно сохранить текст в этой кодировке.

Как автор контента, вам необходимо проверить, в какой кодировке ваш редактор или скрипты сохраняют текст и как сохранять текст в UTF-8. (В наши дни это обычно используется по умолчанию.) Вам также может потребоваться проверить, что ваш сервер обслуживает документы с правильным HTTP декларации.

Разработчикам необходимо убедиться, что различные части системы могут взаимодействовать друг с другом, понимать, какие кодировки символов используются и поддерживают все необходимые кодировки и символы.(В идеале вы должны использовать UTF-8 повсюду и избавиться от этой проблемы.)

По ссылкам ниже можно найти дополнительную информацию по этим темам.

Этот раздел предоставляет небольшую дополнительную информацию о сопоставлении байтов, кодовых точек и символов для тех, кому это интересно. Не стесняйтесь просто перейти к разделу Дополнительная литература.

Обратите внимание, что номера кодовых точек обычно выражаются в шестнадцатеричной системе счисления, т.е. основание 16. Например, 233 в шестнадцатеричной форме — это E9.Значения кодовой точки Unicode обычно записываются в форме U + 00E9.

В наборе кодированных символов под названием ISO 8859-1 (также известном как Latin1) значение десятичной кодовой точки для буквы é равно 233. Однако в ISO 8859-5, та же кодовая точка представляет кириллический символ щ.

Эти наборы символов содержат менее 256 символов и напрямую сопоставляют кодовые точки с байтовыми значениями, поэтому кодовая точка со значением 233 представлена ​​одним байтом со значением 233.Обратите внимание, что только контекст определяет, представляет ли этот байт либо é, либо щ.

Есть и другие способы обработки символов из ряда сценариев. Например, с помощью набора символов Unicode вы можете представить оба символа в одном наборе. Фактически, Unicode содержит в одном наборе, вероятно, все символы, которые вам когда-либо понадобятся. Хотя буква é по-прежнему представлена ​​значением кодовой точки 233, кириллический символ щ теперь имеет значение кодовой точки 1097.

С другой стороны, 1097 слишком большое число, чтобы его можно было представить одним байт*. Итак, если вы используете кодировку символов для текста Unicode под названием UTF-8, щ будет представлен двумя байтами. Тем не менее значение кодовой точки не просто выводится из значения двух байтов, соединенных вместе — требуется более сложное декодирование.

Другой Юникод символы отображаются в один, три или четыре байта в кодировке UTF-8.

Кроме того, обратите внимание, что буква é также представлена ​​двумя байтами в UTF-8, а не одним байтом, используемым в ISO 8859-1. (Только символы ASCII кодируются одним байтом в UTF-8.)

UTF-8 — это наиболее широко используемый способ представления текста Unicode на веб-страницах, и вы всегда должны использовать UTF-8 при создании веб-страниц и баз данных. Но, в принципе, UTF-8 — лишь один из возможных способов кодирования. Символы Юникода. Другими словами, одна кодовая точка в наборе символов Unicode может фактически отображаться в разные последовательности байтов, в зависимости от какая кодировка использовалась для документа.Кодовые точки Unicode могут быть сопоставлены с байтами с использованием любой из кодировок, называемых UTF-8, UTF-16 или UTF-32. Символ деванагари क с кодовой точкой 2325 (что составляет 915 в шестнадцатеричной системе счисления) будет представлен двумя байтов при использовании кодировки UTF-16 (09 15), трех байтов с UTF-8 (E0 A4 95) или четырех байтов с UTF-32 (00 00 09 15).

Могут быть и другие сложности помимо описанных в этом разделе (например, порядок байтов и escape-последовательности), но детали описанное здесь показывает, почему важно, чтобы приложение, с которым вы работаете, знало, какая кодировка символов подходит для ваших данных, и знает, как обрабатывать эту кодировку.

Выбор и применение кодировки символов

Целевая аудитория: Кодировщики HTML (использующие редакторы или сценарии), разработчики сценариев (PHP, JSP и т. Д.), Кодировщики CSS, менеджеры веб-проектов и все, кто плохо знаком с кодировками символов и нуждается в введении в то, как выбирать и применять кодировки символов.

Какую кодировку символов я должен использовать для своего контента и как применить ее к моему контенту?

Контент состоит из последовательности символов.Символы представляют буквы алфавита, знаки препинания и т. Д. Но содержимое хранится в компьютере как последовательность байтов, которые являются числовыми значениями. Иногда для представления одного символа используется более одного байта. Как и коды, используемые в шпионаже, способ преобразования последовательности байтов в символы зависит от того, какой ключ использовался для кодирования текста. В этом контексте этот ключ называется кодировкой символов .

Эта статья предлагает простые советы о том, какую кодировку символов использовать для вашего контента и как ее применять, т. Е.как на самом деле создать документ в этой кодировке.

Если вам нужно лучше понять, что такое символы и кодировки символов, см. Статью Кодировки символов для начинающих .

Выберите UTF-8 для всего содержимого и подумайте о преобразовании любого содержимого из устаревших кодировок в UTF-8.

Если вы действительно не можете использовать кодировку Unicode, убедитесь, что браузер поддерживает выбранную вами кодировку страницы, и что эта кодировка не входит в список кодировок, которых следует избегать в соответствии с последними спецификациями.

Проверьте, повлияют ли на ваш выбор настройки HTTP-сервера.

Помимо объявления кодировки документа внутри документа и / или на сервере, вам необходимо сохранить текст в этой кодировке, чтобы применить его к вашему контенту.

Разработчикам также необходимо убедиться, что различные части системы могут взаимодействовать друг с другом.

Применение кодировки к вашему контенту

Авторы контента должны объявить кодировку символов своих страниц, используя один из методов, описанных в Объявление кодировок символов в HTML .

Однако важно понимать, что простое объявление кодировки внутри документа или на сервере фактически не изменит байты; вам нужно сохранить текст в этой кодировке , чтобы применить его к вашему контенту. (Объявление просто помогает браузеру интерпретировать последовательности байтов, в которых хранится текст.)

При необходимости настройте UTF-8 по умолчанию для новых документов в редакторе. На рисунке ниже показано, как это сделать в настройках редактора, такого как Dreamweaver.

Для получения информации о «Форме нормализации Unicode» см. Нормализация в HTML и CSS . Для получения информации о «Подпись Unicode (BOM)» см. Метка порядка байтов (BOM) в HTML .

Вам также может потребоваться проверить, что ваш сервер обслуживает документы с правильными декларациями HTTP, поскольку в противном случае он переопределит информацию в документе (см. Ниже).

Разработчикам также необходимо убедиться, что различные части системы могут взаимодействовать друг с другом.Веб-страницы должны иметь возможность беспрепятственно взаимодействовать с серверными скриптами, базами данных и т. Д. Все они, конечно, лучше всего работают и с UTF-8. Разработчики могут найти подробный набор вещей, которые следует учитывать, в статье Переход на Unicode .

Зачем использовать UTF-8?

HTML-страница может быть только в одной кодировке. Вы не можете кодировать разные части документа в разных кодировках.

Кодировка на основе Unicode, такая как UTF-8, может поддерживать множество языков и может содержать страницы и формы на любом сочетании этих языков.Его использование также устраняет необходимость в логике на стороне сервера для индивидуального определения кодировки символов для каждой обслуживаемой страницы или каждой входящей отправки формы. Это значительно упрощает работу с многоязычным сайтом или приложением.

Кодировка Unicode также позволяет смешивать на одной странице намного больше языков, чем любой другой выбор кодировки.

Поддержка данной кодировки, даже кодировки Unicode, не обязательно означает, что пользовательский агент будет правильно отображать текст.Многочисленные скрипты, такие как арабский и индийский, требуют дополнительных правил для преобразования последовательности символов в памяти в соответствующую последовательность глифов шрифта для отображения.

В наши дни барьеры для использования Unicode очень низки. Фактически, в январе 2012 года Google сообщил, что более 60% Интернета в их выборке из нескольких миллиардов страниц теперь используют UTF-8. Добавьте к этому цифру для веб-страниц только с ASCII (поскольку ASCII является подмножеством UTF-8), и эта цифра возрастет примерно до 80%.

Существует три различных кодировки символов Unicode: UTF-8, UTF-16 и UTF-32.Из этих трех только UTF-8 следует использовать для веб-содержимого. Спецификация HTML5 гласит: «Авторам рекомендуется использовать UTF-8. Средства проверки соответствия могут посоветовать авторам не использовать устаревшие кодировки. Инструменты разработки должны по умолчанию использовать UTF-8 для вновь создаваемых документов».

Обратите внимание, в частности, что все символы ASCII в UTF-8 используют точно те же байты, что и кодировка ASCII, что часто способствует совместимости и обратной совместимости.

Принимая во внимание HTTP-заголовок

Любое объявление кодировки символов в заголовке HTTP переопределит объявления внутри страницы.Если заголовок HTTP объявляет кодировку, отличную от той, которую вы хотите использовать для своего контента, это вызовет проблему, если вы не сможете изменить настройки сервера.

Вы можете не контролировать объявления, которые идут с заголовком HTTP, и, возможно, вам придется обратиться за помощью к людям, которые управляют сервером. С другой стороны, иногда есть способы исправить что-то на сервере, если у вас ограниченный доступ к файлам настройки сервера или если вы создаете страницы с помощью языков сценариев.Например, см. Установка параметра кодировки HTTP для получения дополнительной информации о том, как изменить информацию о кодировке либо локально для набора файлов на сервере, либо для контента, созданного с использованием языка сценариев.

Обычно перед этим необходимо проверить, действительно ли заголовок HTTP объявляет кодировку символов. Вы можете использовать средство проверки интернационализации W3C, чтобы узнать, какая кодировка символов, если таковая имеется, указана в заголовке HTTP. В качестве альтернативы, статья Проверка заголовков HTTP указывает на некоторые другие инструменты для проверки информации о кодировке, передаваемой сервером.

Информация в этом разделе относится к вещам, о которых вам обычно не нужно знать, но которые включены сюда для полноты.

Что делать, если я не могу использовать UTF-8?

Если вы действительно не можете избежать использования кодировки символов, отличной от UTF-8, вам нужно будет выбрать из ограниченного набора имен кодировки, чтобы обеспечить максимальную совместимость и максимально долгий срок читабельности вашего контента, а также минимизировать уязвимости системы безопасности.

До недавнего времени реестр IANA был местом, где можно было найти имена для кодировок.Реестр IANA обычно включает несколько имен для одной и той же кодировки. В этом случае вы должны использовать имя, обозначенное как «предпочтительный».

Новая спецификация Encoding теперь предоставляет список, который был протестирован на реальных реализациях браузеров. Вы можете найти список в таблице в разделе «Кодировки». Лучше всего использовать имена из левого столбца этой таблицы.

Обратите внимание, однако, на , что наличие имени в любом из этих источников не обязательно означает, что использовать эту кодировку можно.В следующем разделе описаны кодировки, которых следует избегать.

Избегайте этих кодировок

Спецификация HTML5 называет ряд кодировок, которых следует избегать.

Документы не должны использовать JIS_C6226-1983 , JIS_X0212-1990 , HZ-GB-2312 , JOHAB (кодовая страница Windows 1361), кодировки на основе ISO-2022 или кодировки на основе EBIC . Это связано с тем, что они позволяют кодовым точкам ASCII представлять символы, отличные от ASCII, что создает угрозу безопасности.

Документы также не должны использовать кодировки CESU-8 , UTF-7 , BOCU-1 или SCSU , поскольку они никогда не предназначались для веб-содержимого, а спецификация HTML5 запрещает браузерам их распознавать.

Спецификация также настоятельно не рекомендует использовать UTF-16 , а использование UTF-32 «особенно не рекомендуется».

Также следует избегать других кодировок символов, перечисленных в спецификации Encoding .К ним относятся кодировки Big5 и EUC-JP , которые имеют проблемы совместимости. ISO-8859-8 (кодировка на иврите для визуально упорядоченного текста) также следует избегать в пользу кодировки, которая работает с логически упорядоченным текстом (например, UTF-8 или в противном случае ISO-8859-8-i).

Кодировка , заменяющая кодировку , указанная в спецификации Encoding , на самом деле не является кодировкой; это резервный вариант, который отображает каждый октет в кодовую точку Unicode U + FFFD REPLACEMENT CHARACTER.Очевидно, что передавать данные в такой кодировке бесполезно.

Пользовательская кодировка x представляет собой однобайтовую кодировку, нижняя половина которой — ASCII, а верхняя половина отображается в область частного использования Unicode (PUA). Как и в случае с PUA в целом, лучше избегать использования этой кодировки в общедоступном Интернете, потому что это ухудшает совместимость и долгосрочное использование.

CS101 — Кодировка текста

Мы рассмотрели, как представлять числа в двоичном формате; в этом разделе мы исследуем представление текста в виде битов.Под «текстом» мы подразумеваем алфавиты и другие системы письма, которые используются везде, от обновлений статуса и текстовых сообщений до электронной почты и электронных книг.

Для начала мы можем предложить способ сопоставления букв и других символов (знаков препинания, пробела и т. Д.) С числами. Например, пусть A будет представлен как число 1, B как 2, C как 3 и так далее. В английском алфавите 26 букв, поэтому нам понадобится всего 5 бит. (2⁵ равно 32, так что у нас даже останется несколько цифр для знаков препинания.)

Упражнение: , используя схему, описанную выше, декодировать слово, представленное битами 00011 00001 10100

Если в наших текстовых сообщениях нужно различать прописные и строчные буквы, нам понадобится более 5 бит. Верхний регистр A – Z составляет 26 символов, нижний регистр a – z — это еще 26, так что всего 52. 2⁶ равно 64, так что 6 бит охватывают его, и опять же несколько символов доступны для пунктуации.

А как насчет включения в наш текст чисел ? Если мы хотим отправить текстовое сообщение «Amazon имеет 20% скидку на учебники», мы не сможем представить это «20» как 10100 в двоичном формате, потому что это будет противоречить представлению буквы «T».

Вместо этого нам нужно добавить место для стандартных десяти цифр в виде символов. Включение символов с прописными и строчными буквами означает, что нам нужно как минимум 62 символа. Технически это умещается в 6 битах, но у нас будет очень мало места для знаков препинания и символа, представляющего пробел. Так что для практических целей мы используем до 7 бит на символ. 2⁷ равно 128, так что теперь есть много места для других символов.

Простые кодировки, которые я предложил в предыдущем разделе, основаны на фиксированном числе бит на символ — 5, 6 или 7.Один из способов проиллюстрировать это как дерево — см. Этот файл:

Деревья — это часто используемая структура данных в информатике, но они немного отличаются от органических деревьев, к которым они относятся. Прежде всего, мы обычно рисуем деревья с корнем вверху, а они растут вниз по странице. Каждый раз, когда круг разделяется на два пути, мы называем это ветвью . Дерево заканчивается в нижней части ряда из листьев.

Это конкретное дерево является двоичным деревом , значение означает, что каждый узел является либо листом, либо ветвью с ровно двумя дочерними элементами. Самое приятное в двоичном дереве состоит в том, что пути от корня к листу точно соответствуют двоичным числам. Просто представьте, что ноль — это слева, в дереве, а единица — как справа. Тогда номер 01101 (например) соответствует левому-правому-правому-левому-правому, который попадает на лист с пометкой N . Расшифруйте сообщение в двоичном формате, написанном под деревом.

Вы можете сказать, что предыдущее дерево имеет фиксированную ширину, потому что каждый путь от корня к листу представляет собой ровно 5 переходов.Теперь сравните это с переменным битовым деревом в этом файле:

В этом случае разные буквы могут иметь очень разное количество представляющих их битов. Например, E — кратчайший путь, представляющий всего 3 бита. X — очень длинный путь, представляющий 10 бит. Расшифруйте слово, данное в двоичном формате в правом верхнем углу страницы.

На раздаточном материале слово напечатано с пробелами между буквами, но на самом деле в них нет необходимости. Биты 11100001001 могут быть декодированы, хотя я не подчеркивал, где заканчивается один символ и начинается следующий.Вы просто идете по тропинке на дереве, пока не приземлитесь на лист. Затем начните снова сверху для следующего бита.

Это конкретное дерево переменной ширины создано таким образом, что в целом оно сжимает английский текст на . Это работает, потому что наиболее часто используемые буквы представлены пропорционально укороченными битовыми строками. Например, давайте сравним кодировки с использованием обоих деревьев последовательности слов:

  слово: фиксированная кодировка: переменная кодировка:
   THE 100110011100100 15 бит 11100001001 11 бит
   ТРАВА 001101000100000 11010000001100
             1001010010 25 бит 01000100 22 бит
   IS 0100010010 10 бит 01110100 8 бит
   ЗЕЛЕНЫЙ 001101000100100 1101000000001
             0010001101 25 бит 0010110 20 бит
   САИД 100100000001000 010011000111
             00011 20 бит 11011 17 бит
   QUUX 100001010010100 1111100001
             10111 20 бит 111111111111
                                         1111100010 32 бита

   всего: 115 бит 110 бит  

При фиксированной кодировке каждый символ составляет ровно 5 бит, поэтому вся последовательность слов составляет 115 бит.(В этом упражнении мы не учитываем кодирование пробелов между словами.)

Сравните это с кодировкой переменных. Почти каждое слово имеет более короткое представление. Единственное исключение — «QUUX», что, конечно, не совсем английское слово. Но он представляет собой случай слова с редко используемыми буквами, и кодирование этого слова существенно увеличилось в размере с 20 до 32 бит. В целом, второе дерево по-прежнему сжимается, если вы в основном используете английские слова с часто встречающимися буквами.

Это подводит нас к наиболее популярным и влиятельным кодам с фиксированным битом. Он называется ASCII (произносится как , «ключ-задница», ), что означает Американский стандартный код для обмена информацией. Он был разработан в начале 1960-х годов и включает в себя 7-битное отображение прописных и строчных букв, цифр, различных символов и «управляющих символов». Вы можете увидеть их все в таблице на http://www.asciitable.com/

Управляющие символы находятся в диапазоне 0–31 (основание десять).У них нет визуального представления, но вместо этого они направляют устройство отображения определенным образом. Многие из них уже устарели, но, пожалуй, наиболее важным является 10₁₀ = A₁₆ = 0001010₂, символ «новой строки». Каждый раз, когда вы нажимаете клавишу ВВОД, чтобы перейти к следующей строке, этот символ вставляется в ваш документ.

Символ 32 — это пробел, а символы 33-63 содержат в основном знаки препинания. Цифры находятся в позициях с 48 по 57. Их легко распознать в двоичном формате: все они начинаются с 011, а затем младшие четыре бита соответствуют цифре.Таким образом, вы можете сразу сказать, что 0110101₂ = 35₁₆ — это цифра «5».

Диапазон 64–95 состоит в основном из прописных букв, а 96–127 — в основном из нижнего регистра. (Оба диапазона включают еще несколько знаков пунктуации и скобок.) Эти числа соответствуют битовым строкам, начинающимся с 10 для прописных букв и 11 для строчных. Остальные 5 бит определяют позицию буквы в алфавите. Таким образом, 10 01011₂ = 4B₁₆ — это одиннадцатая буква (заглавная «K»), а 11 01011₂ = 6B₁₆ — соответствующая строчная буква «k».

ASCII относительно хорошо работал в англоязычном мире, но другие страны и культуры нуждаются в других символах, акцентах, алфавитах и ​​других символах. Невозможно написать niño или cafe в кодировке ASCII, или польское имя Michał, , и это безнадежно для греческого слова ἀλήθεια, или китайского 福.

Компьютерные архитектуры в конечном итоге остановились на восьми битах в качестве наименьшего адресуемого блока памяти, известного как байт. Поскольку ASCII был 7-битным, стало возможным использовать этот восьмой бит для указания дополнительных 128 символов.

Это привело к появлению большого количества несовместимых 8-битных кодировок для разных языков. Они в основном согласились с тем, что первые 128 символов совместимы с ASCII, но в остальном это был хаос. Все это описано в разных частях данной спецификации:

То есть ISO 8859-1 был для западноевропейских языков, 8859-2 для центральноевропейских, 8859-4 для североевропейских, 8859-5 для кириллицы, 8859-7 для греческого и т. Д.Отправка документов между этими языковыми группами была сложной, и было невозможно создать единый документ, содержащий несколько языков, из несовместимых кодировок.

В качестве небольшого примера возьмем символ в позиции EC₁₆ = 236₁₀. Все эти кодировки расходятся во мнениях относительно того, каким должно быть:

• ISO 8859-1: ì — СТРОЧНАЯ ЛАТИНСКАЯ БУКВА I С ТЯЖЕЛЫМ
• ISO 8859-2: ě — СТРОЧНАЯ ЛАТИНСКАЯ БУКВА E с КАРОН
• ISO 8859-4: ė — СТРОЧНАЯ ЛАТИНСКАЯ БУКВА E с ТОЧКОЙ ВЫШЕ
• ISO 8859-5: ü — Кирилическая строчная буква МЯГКИЙ ЗНАК
• ISO 8859-7: μ — ГРЕЧЕСКАЯ СТРОЧНАЯ БУКВА MU
• Mac OS Роман: Ï — ЛАТИНСКАЯ ЗАГЛАВНАЯ БУКВА I С ДИАРЕЗИСОМ
• IBM PC: ∞ — БЕСКОНЕЧНОСТЬ

Вы все еще можете увидеть остатки этой старой несовместимой системы кодирования в меню вашего браузера.Большинство веб-страниц сегодня будет в Юникоде — мы скоро вернемся к этому, — но браузер по-прежнему поддерживает эти в основном устаревшие кодировки, поэтому он может показывать вам веб-страницы, написанные с их помощью. Обратите внимание, что даже для одного и того же языка часто доступно несколько вариантов кодирования.

Чтобы справиться с этой проблемой несовместимых кодировок в разных языковых группах, Консорциум Unicode был основан с удивительной и благородной целью разработки одной кодировки , которая содержала бы на каждые символов и символов, используемых в на каждом языке на планете.

Вы можете получить представление о разнообразии и масштабах этой цели, просмотрев таблицы кодов на веб-сайте Unicode:

Каждый из них представляет собой файл PDF, относящийся к определенному региону, языку или системе символов. В общей сложности это около ста тысяч символов.

В кодовых таблицах каждому возможному символу присваивается отдельный номер, но все еще остается вопрос, как кодировать эти числа как биты. Большинство чисел умещается в 16-битном формате, поэтому в кодовых таблицах они выражаются четырьмя шестнадцатеричными цифрами (например, 1F30 для греческой йоты с акцентом: ἰ ).Но 2¹⁶ — это 65 536, и мы сказали, что их было ближе к 100 000 символов, поэтому, очевидно, 16 бит недостаточно. Большую часть времени Unicode представлен в виде многобайтовой (переменной) кодировки под названием UTF-8. Исходные символы ASCII по-прежнему представлены в виде одного байта, но установка восьмого бита позволяет использовать умный механизм, который указывает, сколько байтов следует за ними. Вот хорошее объяснение Unicode и UTF-8 от Тома Скотта на Computerphile:

В настоящее время Unicode работает практически везде, и почти весь новый контент использует его.По-прежнему возникает случайная проблема с тем, установлены ли на вашем компьютере правильные шрифты, содержащие все необходимые символы. Иногда вместо неподдерживаемого символа появляется поле. Вот один и тот же текст, отображаемый в трех разных системах:

На приведенном выше изображении отлично видны все персонажи. В приведенном ниже не хватает нескольких символов.

Наконец, приведенная ниже система не может отображать какие-либо символы, кроме символов ASCII.

Base64 Кодирование «буквы» — Base64 Encode and Decode

  >>> импортная строка

>>> s = "Что не так с ASCII?!?!?"
>>> s.rstrip (строка. пунктуация)
"Что не так с ASCII"
  

  >>> def make_bitseq (s: str) -> str:
... если не s.isascii ():
... поднять ValueError ("Допускается только ASCII")
... return "" .join (f "{ord (i): 08b}" для i в s)

>>> make_bitseq ("биты")
'01100010 01101001 01110100 01110011'

>>> make_bitseq ("ЗАГЛАВКИ")
'01000011 01000001 01010000 01010011'

>>> make_bitseq ("25 долларов.43 ")
'00100100 00110010 00110101 00101110 00110100 00110011'

>>> make_bitseq ("~ 5")
'01111110 00110101'
  

  def n_possible_values ​​(nbits: int) -> int:
    вернуть 2 ** нбит
  

  >>> из математического импорта ceil, log

>>> def n_bits_required (nvalues: int) -> int:
... вернуть ceil (log (nvalues) / log (2))

>>> n_bits_required (256)
8
  

  >>> n_bits_required (110)
7
  

  >>> n_bits_required (128) # от 0 до 127
7
>>> n_possible_values ​​(7)
128
  

  >>> make_bitseq ("биты")
'01100010 01101001 01110100 01110011'
  

  >>> int ('11 ')
11
>>> int ('11 ', base = 10) # 10 уже по умолчанию
11
>>> int ('11 ', base = 2) # Двоичный
3
>>> int ('11 ', base = 8) # Восьмеричный
9
>>> int ('11 ', base = 16) # Шестнадцатеричный
17
  

  >>> 11
11
>>> 0b11 # Двоичный литерал
3
>>> 0o11 # Восьмеричный литерал
9
>>> 0x11 # шестнадцатеричный литерал
17
  

  $ grep -nri --include "* \. Py" -e "\ b0x" lib / python3.7
  

  >>> "резюме".кодировать ("utf-8")
b'r \ xc3 \ xa9sum \ xc3 \ xa9 '
>>> "Эль-Ниньо" .encode ("utf-8")
b'El Ni \ xc3 \ xb1o '

>>> b "r \ xc3 \ xa9sum \ xc3 \ xa9" .decode ("utf-8")
'резюме'
>>> b "Эль-Нинь \ xc3 \ xb1o" .decode ("utf-8")
'Эль-Ниньо'
  

  >>> "" .join (f "{i: 08b}" для i in (0xc3, 0xb1))
'11000011 10110001'
  

  >>> # Mac OS X High Sierra
>>> импортировать локаль
>>> locale.getpreferredencoding ()
'UTF-8'

>>> # Windows Server 2012; другие сборки Windows могут использовать UTF-16
>>> импортировать локаль
>>> locale.getpreferredencoding ()
'cp1252'
  

  >>> all (len (chr (i) .encode ("ascii")) == 1 для i в диапазоне (128))
Правда
  

  >>> ibrow = "🤨"
>>> len (ibrow)
1
>>> ibrow.encode ("utf-8")
б '\ xf0 \ x9f \ xa4 \ xa8'
>>> len (ibrow.encode ("utf-8"))
4

>>> # Calling list () для байтового объекта дает вам
>>> # десятичное значение для каждого байта
>>> список (b '\ xf0 \ x9f \ xa4 \ xa8')
[240, 159, 164, 168]
  

  >>> letter = "αβγδ"
>>> rawdata = letter.encode ("utf-8")
>>> rawdata.decode ("utf-8")
'αβγδ'
>>> rawdata.decode ("utf-16") # 😧
'뇎닎 돎듎'
  

  >>> text = "記者 鄭啟源 羅智堅"
>>> len (text.encode ("utf-8"))
26 год
>>> len (text.encode ("utf-16"))
22
  

  >>> ascii ("abcdefg")
"'abcdefg'"

>>> ascii ("халепеньо")
"'Джалепе \\ xf1o'"

>>> ascii ((1, 2, 3))
'(1, 2, 3)'

>>> ascii (0xc0ffee) # Шестнадцатеричный литерал (int)
"12648430"
  

  >>> корзина (0)
'0b0'

>>> корзина (400)
'0b110010000'

>>> bin (0xc0ffee) # Шестнадцатеричный литерал (int)
'0b110000001111111111101110'

>>> [bin (i) for i in [1, 2, 4, 8, 16]] # `int` + понимание списка
['0b1', '0b10', '0b100', '0b1000', '0b10000']
  

  >>> # Итерация целых чисел
>>> байты ((104, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100))
привет мир

>>> bytes (range (97, 123)) # Итерация целых чисел
b'abcdefghijklmnopqrstuvwxyz '

>>> bytes ("real 🐍", "utf-8") # Строка + кодировка
б'реал \ xf0 \ x9f \ x90 \ x8d '

>>> байтов (10)
б '\ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ x00 \ x00'

>>> байтов.fromhex ('c0 ff ee')
б '\ xc0 \ xff \ xee'

>>> bytes.fromhex ("72 65 61 6c 70 79 74 68 6f 6e")
b 'альпифон'
  

  >>> chr (97)
'а'

>>> chr (7048)
'ᮈ'

>>> chr (1114111)
'\ U0010ffff'

>>> chr (0x10FFFF) # Шестнадцатеричный литерал (int)
'\ U0010ffff'

>>> chr (0b01100100) # Двоичный литерал (int)
'd'
  

  >>> шестнадцатеричный (100)
'0x64'

>>> [hex (i) для i в [1, 2, 4, 8, 16]]
['0x1', '0x2', '0x4', '0x8', '0x10']

>>> [hex (i) для i в диапазоне (16)]
['0x0', '0x1', '0x2', '0x3', '0x4', '0x5', '0x6', '0x7',
 '0x8', '0x9', '0xa', '0xb', '0xc', '0xd', '0xe', '0xf']
  

  >>> int (11.0)
11

>>> int ('11 ')
11

>>> int ('11 ', основание = 2)
3

>>> int ('11 ', основание = 8)
9

>>> int ('11 ', основание = 16)
17

>>> int (0xc0ffee - 1.0)
12648429

>>> int.from_bytes (b "\ x0f", "маленький")
15

>>> int.from_bytes (b '\ xc0 \ xff \ xee', "большой")
12648430
  

  >>> ord ("а")
97

>>> ord ("ę")
281

>>> ord ("ᮈ")
7048

>>> [ord (i) вместо i в "привет, мир"]
[104, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100]
  

  >>> str ("строка строки")
'строка строки'

>>> str (5)
'5'

>>> str ([1, 2, 3, 4]) # Как [1, 2, 3, 4].__str __ (), но используйте str ()
'[1, 2, 3, 4]'

>>> str (b "\ xc2 \ xbc чашка муки", "utf-8")
Стакана муки

>>> str (0xc0ffee)
"12648430"
  

  >>> еда = "креветки и крупа"
  

  >>> алфавит = 'αβγδεζηθικλμνξοπρςστυφχψ'
>>> печать (алфавит)
αβγδεζηθικλμνξοπρςστυφχψ
  

  >>> (
... "а" ==
... "\ x61" ==
... "\ N {СТРОЧНАЯ ЛАТИНСКАЯ БУКВА A}" ==
... "\ u0061" ==
... "\ U00000061"
...)
Правда
  

  >>> "\ U00010346"
'𐍆'
  

  >>> def make_uchr (код: str):
... return chr (int (code.lstrip ("U +"). zfill (8), 16))
>>> make_uchr ("U + 10346")
'𐍆'
>>> make_uchr ("U + 0026")
'&'
  

  >>> alef = chr (1575) # Или "\ u0627"
>>> alef_hamza = chr (1571) # Или "\ u0623"
>>> алеф, алеф_хамза
('ا', 'أ')
>>> алеф.кодировать ("unicode-escape")
б '\\ u0627'
>>> alef_hamza.encode ("unicode-escape")
б '\\ u0623'
  

  >>> data = b "\ xbc чашка муки"
  

  >>> данные.декодировать ("utf-8")
Отслеживание (последний вызов последний):
  Файл "", строка 1, в 
UnicodeDecodeError: кодек utf-8 не может декодировать байт 0xbc в позиции 0: недопустимый начальный байт
  

  >>> data.decode ("латиница-1")
Стакана муки
  

  >>> импортировать unicodedata

>>> unicodedata.name ("€")
«ЗНАК ЕВРО»
>>> unicodedata.lookup («ЗНАК ЕВРО»)
'€'