Какое наименьшее количество двоичных знаков потребуется для кодирования слова колобок

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

1 вариант 1. Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова. Показать больше

1 вариант 1. Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов? 2. Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов? 3. По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ? 4. Для кодирования букв О, Ч, Б, А, К решили использовать двоичное пред Спрятать

• Похожие публикации
• Поделиться
• Код вставки
• Добавить в избранное
• Комментарии

Обработка информации. Вариант 1.

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

Пройдите тест до конца, чтобы получить оценку. Время прохождения — 20 минут
Система оценки: 5 балльная

Список вопросов теста

Вопрос 1

Светодиодная панель содержит пять излучающих элементов, каждый из которых может светиться или красным, или жёл­тым, или синим цветом. Сколько различных сигналов можно закодировать с помощью панели (все излучающие элементы должны гореть, порядок цветов имеет значение)?

Вопрос 2

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, О, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 001, И — 01, С — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОБОК?

Вопрос 3

Даны двоичные коды для 5 букв латинского алфавита:

Выясните, какое сообщение (какой набор букв) закодировано с помощью этих кодов двоичной строкой

Запишите набор заглавных букв без пробелов

Вопрос 4

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномер­ный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б и В использовали та­кие кодовые слова: А — О, Б — 10, В — 110.
Какими кодовыми словами могут быть закодированы буквы Г и Д? Код должен удовлетворять свойству однозначного де­кодирования. Если можно использовать разные варианты ко­довых слов, укажите кратчайшие из них.

В ответе запишите два числа через запятую.

Вопрос 5

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

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

Проверочная работа по теме «Измерение информации» (10 класс)

1) По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, О, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 001, И — 01, С — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОБОК?

2) По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А — 0, Б — 101, В — 110.

Какова наименьшая возможная суммарная длина всех кодовых букв?

3) Получено сообщение, информационный объем которого равен 32 битам. Чему равен этот объем в байтах?

4) Сколько мегабайт информации содержит сообщение объемом 2 23 бит?

5) У племени «чичевоков» в алфавите 24 буквы и 8 цифр. Знаков препинания и арифметических знаков нет. Какое минимальное количество двоичных разрядов им необходимо для кодирования всех символов? Учтите, что слова надо отделять друг от друга!

6) Сколько информации несет сообщение о том, что в понедельник, на 6 уроке, будет контрольная работа? (Каждый день у детей по 7 уроков)

7) В велокроссе участвуют 900 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая номер участника с использованием минимально возможного количества бит, одинакового для всех спортсменов. Какой объем памяти будет использован устройством, когда промежуточный финиш прошли 880 велосипедистов? (ответ дайте в байтах)

Необратимые алгоритмы сжатия.

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

Развивающие: способствовать развитию познавательных интересов учащихся.

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

1. Организационный момент.

2. Актуализация знаний.

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

Задание 5 № 9185

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

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

Нельзя использовать кодовые слова, которые начинаются с 0 или с 10. 11 также не можем использовать, поскольку тогда мы больше не сможем взять никакое другое кодовое слово, а нам их нужно пять. Поэтому берём трёхзначное 110. 111 опять же не можем использовать, потому что понадобиться ещё одно кодовое слово, а вместе с этим не останется больше свободных. Теперь осталось взять всего два слова и это будут 1110 и 1111. Итого имеем 0, 10, 110, 1110 и 1111 — 14 символов.

Задание 5 № 9293

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

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

Условие Фано — никакое кодовое слово не может быть началом другого кодового слова. Так как уже имеется кодовое слово 1, то никакое другое не может начинаться с 1. Только с 0. Также не может начинаться с 01, поскольку у нас уже есть 01. То есть любое новое кодовое слово будет начинаться с 00. Но это не может быть 00, так как иначе мы не сможем взять больше ни одного кодового слова, поскольку все более длинные слова начинаются либо с 1, либо с 00, либо с 01. Мы можем взять либо 000, либо 001. Но не оба сразу, поскольку опять же в таком случае мы больше не сможем взять ни одного нового кода. Тогда возьмём 001. И так как нам осталось всего два кода, то можем взять 0000 и 0001. Итого имеем: 1, 01, 001, 0000, 0001. Всего 14 символов.

Задание 5 № 15790

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Следующую буква должна кодироваться как 11, поскольку 10 мы взять не можем. 100 взять не можем из-за Г, значит, следующая буква должна быть закодирована кодом 101. Следующая буква должна кодироваться как 000, поскольку 00 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 001. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно 2 + 3 + 3 + 3 + 3 = 14.

Задание 5 № 15817

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Следующую буква должна кодироваться как 011, поскольку 01 мы взять не можем, иначе код для буквы А не будет удовлетворять условию Фано. 10 из-за Г взять не можем, тогда следующая буква будет кодироваться как 100. Следующая буква должна кодироваться как 110, поскольку 11 взять не можем, иначе не останется кодовых слов для оставшейся буквы, которые удовлетворяют условию Фано. Значит, последняя буква будет кодироваться как 111. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова МАГИЯ равно

3 + 3 + 3 + 3 + 3 = 15.

Задание 5 № 15915

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Для трёх букв кодовые слова уже известны, осталось подобрать для оставшихся четырёх букв такие кодовые слова, которые обеспечат наименьшее количество двоичных знаков для кодирования слова ГРАММ.

Закодируем букву М кодовым словом 00, поскольку буква М повторяется в слове ГРАММ два раза. Для буквы Г возьмём кодовое слово 110. Кодовое слово 111 взять не можем, поскольку для остальных букв не останется кодовых слов, удовлетворяющих условию Фано. Оставшиеся две буквы закодируем кодовыми словами длины 4.

Таким образом, наименьшее количество двоичных знаков, которые потребуются для кодирования слова ГРАММ, равно 3 + 4 + 3 + 2 + 2 = 14.

Задание 5 № 15942

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Для трёх букв кодовые слова уже известны, осталось подобрать для оставшихся четырёх букв такие кодовые слова, которые обеспечат наименьшее количество двоичных знаков для кодирования слова ГРАММ.

Закодируем букву М кодовым словом 11, поскольку буква М повторяется в слове ГРАММ два раза. Для буквы Р возьмём кодовое слово 011. Кодовое слово 100 взять не можем, поскольку для остальных букв не останется кодовых слов, удовлетворяющих условию Фано, поэтому оставшиеся две буквы закодируем кодовыми словами длины 4.

Таким образом, наименьшее количество двоичных знаков, которые потребуются для кодирования слова ГРАММ, равно 3 + 3 + 3 + 2 + 2 = 13

Задание 5 № 16380

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, О, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 001, И — 01, С — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОБОК?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Букву О закодируем кодовым словом 000, поскольку буква О повторяется в слове КОЛОБОК 3 раза. Букву К закодируем кодовым словом 110, поскольку буква К повторяется в слове КОЛОБОК 2 раза. Буквы Б и Л закодируем кодовыми словами 1110 и 1111 соответственно. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова КОЛОБОК равно 3 + 3 + 4 + 3 + 4 + 3 + 3 = 23.

Задание 5 № 16434

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г — 110, И — 01, Т — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Букву А закодируем кодовым словом 000, поскольку буква А повторяется в слове БАРАБАН 3 раза. Букву Б закодируем кодовым словом 001, поскольку буква Б повторяется в слове БАРАБАН 2 раза. Буквы Р и Н закодируем кодовыми словами 1110 и 1111 соответственно. Тогда наименьшее количество двоичных знаков, которые потребуются для кодирования слова БАРАБАН равно 3 + 3 + 4 + 3 + 3 + 3 + 4 = 23.

Изучение нового материала.

Алгоритмы сжатия данных, рассмотренные в лекции 1 (“Информатика” № 17/2007), обладали важным свойством — они сжимали данные так, что после декодирования исходное сообщение восстанавливалось в первоначальном виде. Такие алгоритмы называют обратимыми, или алгоритмами сжатия без потери информации. Однако такое буквальное воспроизведение исходной информации важно, как правило, лишь для текстовых сообщений. Если же речь идет о звуковой или видеоинформации, то при разработке алгоритмов сжатия можно учесть особенности человеческого восприятия звука и изображения.

Рассмотрим сначала методы сжатия графических данных. Одним из наиболее применяемых методов и фактически признанным сегодня стандартом сжатия является алгоритм, созданный Группой экспертов по фотоизображениям. Он получил название JPEG по первым буквам английского названия этой организации: Joint Photographic Experts Group.

Алгоритм JPEG основан на учете целого ряда особенностей зрительного аппарата человека. Во-первых, как мы уже рассказывали в учебнике 10-го класса, человеческое зрение обладает некоторой инерцией, т.е. изображение исчезает не мгновенно, а на некоторое время сохраняется. Именно этот эффект привел в свое время к созданию кинематографа. Именно этот эффект позволяет осуществлять дискретизацию изображения с последующей его оцифровкой. Во-вторых, чувствительность человеческого глаза к зеленому цвету почти в 4 раза выше, чем к красному, и почти в 10 раз выше, чем к синему. Значит, и для передачи информации о красной и синей составляющих можно использовать меньший объем памяти.

Само сжатие осуществляется алгоритмом JPEG в несколько этапов. Прежде всего производится перекодировка из RGB-модели в так называемую “YCbCr-модель”. В этой модели цвет представлен характеристиками: Y — яркость зеленого цвета, Cb — “цветоразность” зеленый–синий, Cr — “цветоразность” зеленый–красный (мы не даем точного определения понятию “цветоразность”, поскольку не планируем абсолютно точно описывать алгоритм JPEG, а интуитивное понимание этого слова есть, как мы надеемся, у каждого читателя). Затем в каждом втором столбце и в каждой второй строке таблицы пикселей, заполняющих экран, информация о Cb и Cr стирается. Иными словами, для каждого квадратика из четырех пикселей только в одном остается информация о цветоразностях (см. рис. 5).

Рис. 5. Сжатие по алгоритму JPEG

Это преобразование уменьшает объем данных в два раза: на каждые 4 пикселя вместо 12 значений передается только 6. После этого получившиеся числовые данные сжимаются еще и алгоритмом Хаффмана.

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

Рис.6. Схема восстановления характристик при декодировании

Рис. 7. График значений характеристики Cb вдоль ряда 1-2-3-4-5

Рис. 8. Сглаживание функции

Самый простой способ определения непередаваемых характеристик — вычисление среднего арифметического четырех известных значений. Однако если изобразить график изменения какой-либо восстанавливаемой характеристики (например, Cb) вдоль ряда пикселей с номерами 1, 2, 3, 4, 5, то вполне вероятно, что он в этом случае будет выглядеть так, как показано на рис. 7. Резкая смена направления в точке 3 изменения значений характеристики Cb вряд ли имела место в оригинале изображения. Математиками разработаны специальные методы, позволяющие, как говорят, сглаживать такие переходы (см. рис. 8). На математическом языке это означает, что функция, описывающая значения характеристики, не только непрерывна, но и дифференцируема, т.е. в каждой точке имеет производную. Для построения такой функции учитываются значения не только в четырех ближайших точках, но на гораздо более обширной области, а иногда и на всем множестве точек с известными значениями функции.

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

Стандартизацией алгоритмов сжатия видеоданных занимается Группа экспертов по видеоизображениям — Motion Picture Experts Group. Поэтому алгоритмы, удовлетворяющие стандартам, принятым этой группой, принято называть общим именем MPEG. Среди них и алгоритм MPEG-1 Layer 3, более известный по своему сокращенному названию МР3. На самом деле этот алгоритм предназначен для сжатия аудиоинформации. Одним из параметров, регулирующих степень сжатия, является так называемый битрейт (от англ. bitrate) — количество бит, используемых для кодирования одной секунды звука.

Звук, как известно, — это колебательный процесс. Математики научились любое сложное колебание представлять в виде суммы простых колебаний, каждое из которых описывается амплитудой, частотой и фазой. Оказывается, что некоторыми составляющими можно просто пренебречь — даже самый музыкальный слух не уловит их отсутствие. Ответственность за то, какие составляющие и в каком количестве оставить, как раз и несет битрейт. Но даже при самом большом допустимом битрейте стандарта МР3 — 320 Кбит/с — данный алгоритм обеспечивает четырехкратное сжатие информации по сравнению с форматом Audio CD при том же субъективном восприятии качества звука. На заключительном этапе к полученным данным снова применяется алгоритм Хаффмана.

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

С другой стороны, если в кадре есть быстро сменяемые участки, то их можно кодировать с более низким качеством — человек привык к тому, что он не может рассмотреть детали быстро изменяющихся объектов. При этом статичное изображение и динамично меняющееся изображение можно отделить друг от друга и применять к ним разные алгоритмы сжатия. И только после декодирования их снова соединить в одно изображение.

Назовем имена нескольких алгоритмов из семейства MPEG.

MPEG-1 использовался в первых Video CD (VCD-I).

MPEG-2 используется в DVD и Super Video CD (SVCD, VCD-II).

MJPEG — формат сжатия видеоизображений, в котором каждый кадр сжимается по алгоритму JPEG.

MPEG-4 — один из самых эффективных форматов сжатия видео.

DivX, XviD — улучшенные модификации формата MPEG-4.

Вопросы и задания

1. Какой алгоритм сжатия данных называется обратимым?

2. В чем состоит отличие обратимых алгоритмов сжатия от необратимых?

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

4. Пусть V₀ — исходный объем данных, V — объем данных после обработки их сжимающим алгоритмом. Как, на ваш взгляд, обычно меняется отношение V₀ / V при увеличении V₀: возрастает, убывает или остается примерно одним и тем же?

Итоги урока.

Домашнее задание.