|
Каким мне представляется профильный курс информатики: тема “Кодирование”Продолжение. См. № 5, 6/2009 Методическое пособиеВо всех авторских вариантах школьного курса информатики центральным системообразующим понятием выступает понятие информации. Фундаментальная составляющая информатики — это наука об информации и информационных процессах. Профильный курс информатики для старших классов дает бoльшие возможности для раскрытия этого фундаментального содержания, чем курс в основной школе. Тому способствует, во-первых, пропедевтика, пройденная в предыдущих классах, во-вторых, более высокий уровень математической и физической подготовки учеников. Раздел, посвященный кодированию информации, является центральным в теоретической составляющей курса. В нем находят отражение основные идеи представления и преобразования информации, которые лежат в основе информационных технологий. Понимание этих идей способствует глубинному пониманию сути ИКТ для профессионального пользователя и, что еще более важно, для будущего разработчика компьютерных систем. Более подробно, чем в основной школе, здесь пойдет речь об особенностях аналоговой и цифровой форм передачи информации. Достаточно подробно объясняется суть АЦП — аналого-цифрового преобразования сигнала. Ключевое понятие раздела — кодирование получает многостороннее разъяснение. Код — это символьная последовательность, заключающая в себе некоторую информацию. Кодирование — это процесс построения кода. Все варианты кодирования можно поделить на две группы: 1) преобразование из аналоговой формы в дискретную, символьную форму; 2) преобразование из одной символьной системы в другую. Способы второй группы кодирования зависят от цели. Здесь могут быть следующие варианты: переход от одного стандарта представления к другому; сокращение объема данных (сжатие, упаковка); засекречивание информации (шифрование) и обратная процедура — расшифровка; обеспечение контроля ошибок при передаче данных. Во всех случаях используются определенные алгоритмы кодирования, за которыми часто стоят математические модели. Учитель должен формировать системное представление учащихся о задачах кодирования и способах их решений. Занятия по информатике делятся на теоретические уроки и компьютерный практикум (безусловно, та и другая формы работы могут объединяться и в рамках одного учебного часа). В данном курсе авторы предлагают еще одну форму организации занятий — урок-исследование. Материал для такого урока содержится в §5 “Численные эксперименты по обработке звука”. Работа состоит в том, что учитель демонстрирует численные эксперименты, выполняемые в среде электронной таблицы, используя компьютер и проекционные средства. Ученики могут параллельно повторять эти же расчеты на своих ПК, но затем они получают задания на самостоятельное продолжение эксперимента. Результаты коллективно обсуждаются. В рамках раздела кодирования ученики продолжают углублять свои навыки работы с электронными таблицами и программирования на Паскале. §1. Сигнал — носитель информацииЧеловек воспринимает информацию из внешнего мира с помощью своих органов чувств. Большая часть информации принимается нами через зрение и слух. Органы слуха воспринимают звуковые сигналы, которые переносятся звуковыми волнами. Органы зрения воспринимают зрительные сигналы, природа которых — электромагнитные волны в определенном диапазоне частот. Всякий сигнал — это изменение какой-то физической величины, передающее информацию принимающему объекту (живому существу или техническому устройству). Звуковой сигнал связан с изменением давления воздуха, порожденным звуковой волной и воздействующим на орган слуха. Зрительный сигнал связан с изменением параметров электромагнитного светового излучения, воспринимаемого органами зрения. Многие века люди могли слышать звуки только на расстоянии естественной слышимости от источника, видеть объекты, находящиеся в поле зрения. Развитие науки и техники позволило человеку выйти за эти естественные границы восприятия. В течение двух последних столетий ученые и изобретатели достигли больших результатов в создании средств связи для передачи информации на расстояние. Различные технические средства связи обеспечивают передачу сигналов двух видов: аналоговых и дискретных. Синонимом слову “аналоговый” является “непрерывный”. Например, звук — это непрерывный волновой процесс, происходящий в атмосфере или другой сплошной среде. Термин “дискретный” означает “разделенный”, состоящий из отдельных частиц, элементов, квантов. Первые в истории технические средства связи предназначались для передачи текстов в дискретной форме. XIX век был великим веком технических изобретений. В 1831 году Майкл Фарадей открывает явление электромагнитной индукции. После этого начинается бурное развитие электротехники: изобретается электрический генератор, создаются средства передачи электроэнергии на расстояние. Электричество находит множество применений. Важнейшие из них: электрическое освещение и отопление, электрический двигатель, электросвязь — передача информации с помощью электричества. Идея передачи информации по проводам по тем временам казалась фантастической: появилась возможность передавать текст со скоростью переноса электрического сигнала — близкой к скорости света. Первый электромагнитный телеграф создал российский ученый Павел Львович Шиллинг в 1832 году. В 1837 году американец Сэмюэл Морзе запатентовал свою конструкцию электромагнитного телеграфного аппарата. Им же был разработан телеграфный код, известный под названием азбуки Морзе.
Телеграфное сообщение представляет собой последовательность электрических сигналов, переносимых от одного телеграфного аппарата по проводам к другому телеграфному аппарату. Эти технические обстоятельства привели С.Морзе к идее использования всего двух видов сигналов — короткого и длинного — для кодирования сообщения, передаваемого по линиям телеграфной связи. В азбуке Морзе каждая буква алфавита кодируется последовательностью коротких сигналов (точек) и длинных сигналов (тире). В таблице на рис. 1 показана азбука Морзе применительно к латинскому и русскому алфавитам.
Рис. 1. Кодовая таблица азбуки Морзе Самым знаменитым телеграфным сообщением является сигнал бедствия “SOS” (Save Our Souls — спасите наши души). Вот как он выглядит в коде азбуки Морзе: • • • — — — • • • Три точки обозначают латинскую букву S, три тире — букву О. Две паузы отделяют буквы друг от друга. Телеграфист, передававший сообщение на азбуке Морзе, “выстукивал” его с помощью телеграфного ключа: точка — короткий сигнал, тире — длинный сигнал, после каждой буквы — пауза. На принимающем аппарате сообщение записывалось на бумажной ленте в виде графических точек, тире и пробелов, которые визуально прочитывал телеграфист. Азбука Морзе является неравномерным кодом, поскольку у разных букв алфавита длина кода изменяется от одного до шести символов (точек и тире). По этой причине необходим третий символ — пауза для отделения букв друг от друга. Равномерный телеграфный код был изобретен французом Жаном Морисом Бодо в 1870 году. В нем использовалось всего два разных вида сигналов. Не важно, как их назвать: точка и тире, плюс и минус, ноль и единица. Это два отличающихся друг от друга электрических сигнала.
В кодовой таблице Бодо длина кодов всех символов алфавита одинакова и равна пяти. В таком случае не возникает проблемы отделения букв друг от друга: каждая пятерка сигналов — это знак текста. Благодаря идее Бодо удалось автоматизировать процесс передачи и печать букв. В 1901 году был создан клавишный телеграфный аппарат. Нажатие клавиши с определенной буквой вырабатывает соответствующий пятиимпульсный сигнал, который передается по линии связи. Принимающий аппарат под воздействием этого сигнала печатает ту же букву на бумажной ленте. Телеграфы Морзе и Бодо — это дискретные способы передачи информации. Следующим важным событием в технике связи стало изобретение телефона. В 1876 году американец Александер Белл получил патент на его изобретение. Годом позже Томас Алва Эдисон изобрел телефонный аппарат с угольным микрофоном, который и до сих пор можно встретить в употреблении. По телефонной связи на расстояние передается звук посредством непрерывного электрического сигнала, модулированного с частотой звуковых колебаний. В микрофоне говорящего человека создается переменное электрическое напряжение, а в наушнике слушающего оно преобразуется в звуковые колебания. Телефонная связь — это аналоговый способ передачи звука.
Благодаря открытию в 1888 г. Генрихом Герцем электромагнитных волн стало возможным изобретение радиосвязи. Почти одновременно в 1895 году Александром Поповым в России и в 1896 г. итальянцем Г.Маркони были изобретены первые радиопередатчики и радиоприемники. Современники изобретения называли радио беспроводным телефоном. Принцип передачи звука по радиосвязи заключается в переносе через пространство высокочастотных (несущих) электромагнитных волн, модулированных по амплитуде низкочастотными звуковыми колебаниями. В радиоприемнике звуковые колебания отделяются от несущей частоты и преобразуются в звук. Радиосвязь — это аналоговый способ передачи звука.
В ХХ веке с изобретением телевидения стала возможной передача на расстояние изображения. Телевизионный электромагнитный сигнал — это также аналоговый способ передачи звуковой и видеоинформации. Во второй половине ХХ века происходит переход к преимущественно дискретной форме представления информации для ее хранения, передачи и обработки. Этот процесс начался с изобретением цифровой вычислительной и измерительной техники. В настоящее время компьютерная обработка становится элементом всех систем связи: телефонной, радио и телевизионной. Развивается цифровая телефония, цифровое телевидение. Интернет как универсальная система связи основан исключительно на дискретной цифровой технологии хранения, передачи и обработки информации. Вопросы и задания 1. Что такое сигнал? 2. Обоснуйте правильность употребления фразы “сигнал светофора”. 3. Приведите примеры аналоговых сигналов в природе, передающих информацию. 4. Как вы считаете, человеческая речь — это аналоговая или дискретная форма передачи информации? 5. Перечислите основные события в истории изобретения технических средств связи. 6. Почему в последнее время цифровые технологии связи вытесняют аналоговые? §2. Кодирование текстаЧто такое кодирование Кодирование — это представление информации в виде комбинации символов. Кодирование происходит по определенным правилам. Правила кодирования зависят от назначения кода, т.е. от того, как и для чего он будет использоваться. Письменность — это способ кодирования речи на естественном языке. Письменный текст (его также называют письменной речью) предназначен для передачи информации от одного человека к другим людям как в пространстве (письмо, записка), так и во времени (книги, дневники, архивы документов и пр.). Правила, по которым люди осуществляют письменное кодирование информации, называются грамматикой языка (русского, английского, китайского и др.), а человека, умеющего читать и писать, называют грамотным человеком. Если запись речи называть кодированием, то чтение письменного текста — это его декодирование. Поскольку мы выражаем свои мысли в форме устной речи, то процесс письменного обмена информацией между людьми можно отобразить следующей схемой (см. схему).
При таком письменном способе обмена информацией в качестве носителя чаще всего используется бумага. С изобретением технических средств связи появилась возможность быстрой передачи текстов на большие расстояния. Но этот процесс требует использования дополнительного уровня кодирования. Повторим еще раз данное выше утверждение: способ кодирования зависит от назначения кода. Если код предназначен для передачи текста по технической системе связи, то он должен быть приспособлен к возможностям этой системы. Примером такого “технического” кода является азбука Морзе. Процесс передачи телеграфного сообщения с использованием азбуки Морзе можно отразить схемой:
Способы кодирования текста Кодирование текста всегда происходит по следующему правилу: каждый символ алфавита исходного текста заменяется на комбинацию символов алфавита кодирования. Для азбуки Морзе эти правила представлены в таблице на рис. 1. В таблице азбуки Морзе для кодирования 32 букв русского алфавита (буква Ё стала использоваться в письменном тексте только в середине ХХ века) применяются два символа: точка и тире. Однако при передаче слов из-за неравномерности кодов различных букв приходится применять еще пропуск между буквами: пауза во времени передачи или пробел на телеграфной ленте. Поэтому фактически алфавит телеграфного кода Морзе содержит три символа: точка, тире, пропуск. Телеграфный код Бодо является двоичным равномерным пятиразрядным кодом. На его основе в 1932 году был разработан международный телеграфный код ITA2, кодовая таблица которого представлена на рис. 2.
Рис. 2. Телеграфный код ITA2 Двоичные коды символов свернуты в формат двузначных шестнадцатеричных чисел, в которых первая цифра принимает значения 0 или 1. Есть три типа символов: буквы (letters), цифры и знаки (figures), управляющие символы (control chars). Переключение в режим ввода букв происходит по коду 1F16 (двоичная форма 1 1111). Буква A имеет код 0316 (0 0011); код буквы R — 0A16 (0 1010). Этот же код в режиме ввода цифр обозначает цифру 4. Слово “BODO” в шестнадцатеричной форме кодируется так: 19 18 09 18. Длина двоичного кода этого слова равна 20. Во второй половине ХХ века создаются и распространяются компьютеры. Для компьютерной обработки текстов потребовалось создать стандарт кодирования символов. В 1963 году был принят стандарт, который получил название ASCII — Американский стандартный код для информационного обмена. ASCII — семиразрядный двоичный код, он приведен в табл. 1.
Код символа — это его порядковый номер в кодовой таблице. Он может быть представлен в десятичной, двоичной и шестнадцатеричной системах счисления. Код в памяти компьютера — семиразрядное двоичное число. В табл. 1 код ASCII представлен в свернутой шестнадцатеричной форме. При развертывании в двоичную форму коды представляют собой семиразрядные целые двоичные числа в диапазоне от 000 00002 = 0016 = 0 до 111 11112 = 7F16 = 127. Всего 27 = 128 символов. Первые 32 символа (от 00 до 1F) называются управляющими. Они не отражаются какими-либо знаками на экране монитора или при печати, но определяют некоторые действия при выводе текста. Например, по коду 0816 (BS) происходит стирание предыдущего символа; по коду 0716 (BEL) — вывод звукового сигнала; код OD16 (CR) означает переход к началу строки (возврат каретки). Эти символы унаследованы еще от кодировки для телетайпной связи, для которой первоначально и использовался ASCII, поэтому сохранились такие архаичные термины, как “каретка”. Символы, имеющие графическое отображение, начинаются с кода 2016. Это пробел — пропуск позиции при выводе. Важным свойством таблицы ASCII является соблюдение алфавитной последовательности кодировки прописных и строчных букв, а также десятичных цифр. Это свойство чрезвычайно важно для программной обработки символьной информации, в частности, для алфавитной сортировки слов. Расширение кода ASCII. Восьмиразрядная двоичная кодировка позволяет кодировать алфавит из 28 = 256 символов. Первая половина восьмиразрядного кода совпадает с ASCII. Вторая половина состоит из символов с кодами от 128 = 8016 = 1000 00002 до 255 = FF16 = 1111 11112. Эта часть таблицы кодировки называется кодовой страницей (CP — code page). На кодовой странице размещают нелатинские алфавиты, символы псевдографики и некоторые другие знаки, не входящие в первую половину. В табл. 2, 3, 4 приведены кодовые страницы с русским алфавитом. CP866 используется в операционной системе MS DOS, CP1251 — в операционной сиcтеме Windows. Кодировка KOI8-R используется в операционной системе Unix. Ее первая половина совпадает с ASCII.
Обратите внимание на то, что не во всех кодировках соблюдается правило последовательного кодирования русского алфавита. Существуют и другие стандарты символьной кодировки, где присутствует русский алфавит. 16-разрядный стандарт UNICODE. В 1991 году был разработан шестнадцатиразрядный международный стандарт символьного кодирования Unicode, который позволяет закодировать 216 = 65 536 символов. В такую кодовую таблицу помещаются английский (латиница), русский (кириллица), греческий алфавиты, китайские иероглифы, математические символы и многое другое. Отпадает потребность в кодовых страницах. Диапазон кодов символов в шестнадцатеричной форме: от 0000 до FFFF. В начале кодовой таблицы, в области от 000016 до 007F16, содержатся символы ASCII. Под символы кириллицы выделены области знаков с кодами от 040016 до 052F16, от 2DE016 до 2DFF16, от A64016 до A69F16. Учимся программировать Рассмотрим программу на Паскале, по которой на экран будет выводиться таблица кодировки в диапазоне кодов от 20 до 255. Program Tabl_code; uses CRT; {Подключение библиотеки управления символьным выводом} var kod: byte; {Целые числа от 0 до 255} begin clrscr; {Очистка экрана символьного вывода} for kod := 20 to 255 do {Перебор кодов символов} begin if (kod mod 10 = 0) then writeln; {Перевод строки через 10 шагов} write(chr(kod):3,kod:4); {Вывод символа и его кода} end end. Оператор uses CRT подключает к программе библиотеку подпрограмм управления символьным выводом на экран монитора. Далее в программе используется процедура из этой библиотеки: clrscr — очистка экрана. Переменная типа byte занимает 1 байт памяти и принимает множество целых положительных числовых значений в диапазоне от 0 до 255. В программе используется стандартная функция chr(kod), которая в качестве результата возвращает символ, десятичный код которого равен значению переменной kod.
Значения выводятся парами: символ — код. В одной строке располагается 10 таких пар. Вся таблица разместится в 24 строках. Вопросы и задания 1. Определите понятия: код, кодирование, декодирование. 2. Приведите примеры кодирования и декодирования, о которых не говорилось в параграфе. 3. В чем разница между равномерным и неравномерным кодами? 4. Закодируйте слово COMPUTER, используя коды ITA2 и ASCII. 5. Как прочитается фраза “СПАРТАК — ЧЕМПИОН”, закодированная с использованием CP1251, если декодирование происходит по коду KOI8-R? 6. В кодировке KOI8-R было составлено письмо, начинающееся фразой: “Здравствуй, дорогой Саша!” Декодирование происходило по семиразрядному коду ASCII, в результате чего старший (восьмой) бит у всех символов был утерян. Напишите, какой текст получился в итоге. Сможет ли адресат понять содержание письма? 7. С помощью табличного процессора определите, какая именно кодовая страница используется на вашем компьютере. Например, в Excel имеется функция СИМВОЛ(код), которая возвращает символ, соответствующий данному десятичному коду. Обратная к ней функция — КОДСИМВ(символ). 8. Реализуйте на компьютере программу Tabl_code. Выполните ее. 9*. Составьте аналогичную программу, которая выводила бы двоичные коды символов. 10*. Составьте аналогичную программу, которая выводила бы шестнадцатеричные коды символов. §3. Кодирование изображения По некоторым оценкам, около 90% информации из внешнего мира человек воспринимает зрительным путем. Зрение человека — это природная способность к восприятию изображения объектов окружающего мира. Зрительная система воспринимает свет, отражаемый или излучаемый объектами наблюдения. Отражаемое изображение — это все, что мы видим при дневном или искусственном освещении. Например, читаем книгу, просматриваем иллюстрации в ней. Примерами излучаемых изображений являются изображения на экране телевизора или компьютера. С древних времен люди научились сохранять и передавать изображения в форме рисунков. В XIX веке появилась фотография. Изобретение кино братьями Люмьер в 1895 году позволило передавать движущиеся изображения. В XX веке изобретают видеомагнитофон — средство записи и передачи изображения на магнитной ленте. Приемы кодирования изображения разрабатываются с появлением цифровых технологий хранения, передачи и обработки изображений: цифровой фотографии, цифрового видео, компьютерной графики. При кодировании изображения осуществляется его пространственная дискретизация и кодирование света, исходящего от каждого дискретного элемента изображения. В компьютерных технологиях пространственная сетка дискретных элементов, из которых строится изображение на экране монитора, называется растром. Сами дискретные элементы изображения на экране называются пикселями (рис. 3). Чем гуще сетка пикселей, тем выше качество изображения, тем меньше наши глаза замечают его дискретную структуру.
Видеоинформация — это двоичный код изображения, хранящийся в памяти компьютера. Весь совокупный видеокод состоит из кодов света, излучаемого отдельными пикселями. Естественные изображения, которые мы видим вокруг себя, многоцветные. В технологиях хранения изображения используются способы получения монохроматических, т.е. одноцветных, и цветных (разноцветных) изображений. Как известно, сначала появились черно-белая фотография, черно-белое кино, а уже позже — цветная фотография и цветное кино. То же самое относится к телевидению. Первые компьютерные дисплеи имели черно-белые экраны, на современных компьютерах используются цветные мониторы. Цветом (красный, желтый, зеленый и пр.) называют субъективное восприятие человеком окрашенности света. Объективное различие света разной окрашенности заключается в разной длине световых волн. Субъективный характер восприятия цвета подтверждается, например, тем фактом, что люди, страдающие дальтонизмом, вообще не различают некоторые цвета. Кодирование монохроматического света Слово “монохроматический” означает — одноцветный. Имеется один фоновый цвет. Все изображение получается с помощью оттенков этого фонового цвета, различающихся яркостью (говорят также — прозрачностью). Например, если фоновый цвет черный, то путем его постепенного просветления можно перейти через оттенки серого к белому цвету (рис. 4). Такое непрерывное множество оттенков — от черного до белого — назовем черно-белым спектром. Из таких оттенков и получается изображение на черно-белой фотографии, на кино- и телеэкране. Все рисунки в данном учебнике исполнены в черно-белом изображении.
Рис. 4. Непрерывный черно-белый спектр Однако фоновый цвет не обязательно должен быть черным. Он может быть коричневым, синим, зеленым и др. Такое бывает на тонированных фотографиях. Существовали монохромные мониторы с коричневым или зеленым фоновым цветом. Код монохромного света обозначает уровень яркости фонового цвета. Для цифрового кодирования света в компьютере используются положительные целые двоичные числа. Размер двоичного кода в битах называется глубиной кодирования света. При дискретном цифровом кодировании непрерывный спектр оттенков базового цвета разбивается на целое число отрезков, в пределах каждого из которых яркость считается постоянной. Для естественного света количество оттенков фонового цвета бесконечно. При цифровом кодировании количество оттенков становится конечной величиной. Количество оттенков (К) и битовая глубина кодирования (b) связаны между собой по формуле: K = 2b Снова работает главная формула информатики! Реальная яркость изображения зависит от физических условий его передачи: уровня освещенности от источника света при отраженном изображении или мощности светового потока от монитора при излучаемом изображении. Если максимальную яркость принять за единицу, то величина яркости света в диапазоне от черного до белого будет изменяться от нуля до единицы. На рис. 5 показана дискретизация черно-белого спектра при b = 2. Это значит, что размер кода равен 2 битам и весь спектр разбивается на четыре уровня — 4 оттенка.
Рис. 5. Монохроматическое кодирование с глубиной 2 Естественный свет, яркость которого лежит в диапазоне от 0 до 1/4, будет представляться как черный цвет, десятичный код которого — 0, а двоичный код — 00. Далее идут два серых оттенка. Свет в диапазоне яркости от 3/4 до 1 представляется как белый, и код его: 3 = 112. Если уровень яркости выражать в процентах, то правила черно-белого кодирования при b = 2 можно отразить в таблице:
На рис. 6 показана дискретизация черно-белого спектра при b = 4. Поскольку 24 = 16, то таким способом кодируется 16 различных черно-белых оттенков. Приведены десятичные и двоичные коды. Пример. Рассмотрим модельный
пример кодирования черно-белого изображения.
Размер растра монитора — 8 х 8 пикселей. Глубина
кодирования равна двум: На экране нарисована буква “П”. Три составляющие ее отрезка окрашены в разные оттенки фонового цвета: черный, темно-серый и светло-серый. Двоичный код изображения будет таким:
Рис. 7. Дискретный рисунок Для наглядности двоичный код представлен в виде матрицы, строки которой соответствуют строкам растра на экране. На самом же деле память компьютера одномерна и весь код представляет собой цепочку нулей и единичек, расположенных в последовательных байтах памяти. Объем такой видеоинформации равен 16 байтам. Если перевести этот код в шестнадцатеричную форму, то он будет следующим: FFFF D55F CFEF CFEF CFEF CFEF FFFF FFFF При кодировании цветного изображения используются различные подходы, которые называются моделями цвета. Об этом подробно будет рассказано в разделе, посвященном технологиям компьютерной графики. Вопросы и задания 1. Дайте определение понятиям: свет, цвет, изображение. 2. Чего нельзя увидеть и что можно увидеть в абсолютной темноте? 3. Что такое растр, пиксель? 4. Чем отличается монохромное изображение от цветного? 5. Что представляет собой черно-белый спектр? 6. Какая информация заключается в компьютерном коде изображения? 7. Какой объем будет иметь видеокод изображения, выводимого на экран, при размере растра 640 х 480 и глубине кодирования 8 бит? 8. Какова глубина кодирования изображения, если объем видеокода равен 384 Кб, а размер растра — 1024 х 768? 9. Объем видеокода равен 600 Кб, глубина кодирования — 16 бит. Какой используется размер растра для вывода изображения: 640 х 480 или 1024 х 768? 10. На черно-белый “игрушечный” монитор с разрешением 8 х 8 пикселей (см. пример в параграфе) по очереди выводятся буквы: Н, А, Ш. Разработайте и запишите для каждого выводимого изображения его двоичный и шестнадцатеричный коды. Глубина кодирования равна двум. Разные элементы букв имеют разные цветовые оттенки. 11. Восстановите изображение на черно-белом “игрушечном” мониторе по шестнадцатеричному коду: F3F7 F3D7 F37F F1FF F3BF F3EF F3FB FFFF, — если глубина кодирования равна двум. §4. Технология кодирования аналогового сигналаВ §1 было введено определение понятиям “аналоговый сигнал” и “дискретный сигнал”. Световой сигнал является аналоговым, поскольку он переносится непрерывным потоком электромагнитного излучения. Звуковой сигнал переносится акустической волной, порождающей непрерывный процесс изменения давления воздуха со звуковой частотой. Для сохранения изображения и звука в цифровом формате соответствующие аналоговые сигналы должны быть закодированы, т.е. представлены в виде дискретной последовательности нулей и единичек — двоичных цифр. Процесс преобразования аналогового сигнала в дискретную цифровую форму называется аналого-цифровым преобразованием, или сокращенно — АЦП. На рис. 8 представлена схема преобразования любого аналогового сигнала естественного происхождения в дискретный цифровой код.
Из данной схемы следует, что как световой, так и звуковой сигналы первоначально преобразуются в непрерывный электрический сигнал, который и подвергается аналого-цифровому преобразованию. Оцифровка изображения происходит во время съемки на цифровые фото- и видеокамеры, а также при вводе изображения в компьютер с помощью сканера. В основе физического процесса преобразования света в электрический ток лежит явление возникновения электрического заряда в полупроводниковом приборе — фотодиоде под действием падающего на него света. Величина возникающего на фотодиоде электрического потенциала пропорциональна яркости светового потока. Эта величина изменяется непрерывно вместе с изменением яркости света. Аналого-цифровое преобразование заключается в измерении величины электрического сигнала. Результаты измерений в цифровом формате сохраняются в устройстве памяти. Пространственная дискретизация происходит благодаря использованию матрицы фотодиодов, разделяющей изображение на конечное число элементов. Кодирование звука Рассмотрим подробнее процесс АЦП на примере кодирования звука при его вводе в компьютер. При записи звука в компьютер устройством, преобразующим звуковые волны в электрический сигнал, является микрофон. Аналого-цифровое преобразование производит электронная схема, размещенная на звуковой плате (звуковой карте) компьютера, к которой подключается микрофон. Амплитуда и частота исходящего от микрофона и поступающего на звуковую плату электрического сигнала соответствует амплитудным и частотным свойствам акустического сигнала. Поэтому измерение электрического сигнала позволяет определить характеристики звуковой волны: ее частоту и амплитуду. Аналоговый сигнал — это процесс непрерывного изменения амплитуды сигнала со временем (рис. 9).
Рис. 9. Дискретизация аналогового сигнала Есть два основных параметра кодирования звука: частота дискретизации и битовая глубина кодирования. Измерение амплитуды сигнала производится через одинаковые промежутки времени. Величина такого временнoго интервала называется шагом дискретизации, который измеряется в секундах. Обозначим шаг дискретизации t (с). Тогда частота дискретизации выразится формулой: H = 1/ t (Гц) Частота измеряется в герцах. Один герц соответствует одному измерению в секунду: 1 Гц = 1 с–1. Чем выше частота дискретизации, тем более подробно числовой код будет отражать изменение амплитуды сигнала со временем. Хорошее качество записи звука получается при частотах дискретизации 44,1 кГц и выше (1 кГц = 1000 Гц). Битовая глубина кодирования (b) — это размер двоичного кода, который будет представлять в памяти компьютера амплитуду сигнала. Битовая глубина связана с числом уровней разбиения амплитуды сигнала по формуле: K = 2b Процесс дискретизации амплитуды звука называют квантованием звука. Тогда величину К можно назвать количеством уровней квантования звука (рис. 10).
Рис. 10. Квантование аналогового сигнала Значения измеряемой величины заносятся в регистр звуковой карты — специальную ячейку памяти прибора. Разрядность регистра равна b — битовой глубине кодирования. Далее эту величину также будем называть разрядностью квантования. Результат измерения представляется в регистре в виде целого двоичного числа. Измеряемая физическая величина округляется до ближайшего к ней целого значения, которое может храниться в регистре звуковой карты. На рис. 11 показано, как это происходит при трехразрядном квантовании аналогового сигнала. В графическом виде дискретизацию и квантование звука можно представить как переход от гладкой кривой к ломаной, состоящей из горизонтальных и вертикальных отрезков. Считается, что на каждом временнoм шаге значение измеряемой величины остается постоянным.
Рис. 11. Измерение переменной
физической величины В память компьютера результаты такого измерения будут записаны в виде последовательности трехразрядных двоичных чисел.
Объем записанной звуковой информации равен: 3 х 9 = 27 бит. На самом деле трехразрядная
дискретизация не используется на практике. Такой
вариант рассмотрен здесь лишь в качестве
учебного примера. Наименьший размер регистра у
реальных приборов — 8 разрядов. В таком случае
одно измеренное значение займет 1 байт памяти
компьютера, а число уровней квантования равно 28
= 256. Измерения с таким регистром будут в 32 раза
более точными, чем при трехразрядном регистре.
При 16-разрядном регистре каждая величина в
памяти займет 2 байта, а число уровней
квантования: Дискретное цифровое представление аналогового сигнала тем точнее его отражает, чем выше частота дискретизации и разрядность квантования. Теорема Найквиста – Котельникова. Человек слышит звуковые колебания приблизительно в диапазоне частот от 20 Гц до 20 кГц. Звук с частотами выше этого диапазона называется ультразвуком, звук с меньшей частотой — инфразвуком. В теории связи известна теорема Найквиста – Котельникова, согласно которой частота дискретизации АЦП должна быть не менее чем в 2 раза выше частоты аналогового сигнала. Это значит, что если мы хотим сохранить в двоичном коде информацию о звуке с частотой 20 кГц, то частота дискретизации должна быть не меньше 40 кГц. В современном стандарте цифровой звукозаписи используется частота дискретизации 44,1 кГц. Можно привести следующую образную аналогию этой теоремы. От размера ячейки рыболовной сети зависит размер рыб, которые будут в ней удерживаться. Чем меньше ячейки, тем мельче рыба удерживается сетью. Перефразированная на рыбацкий лад теорема Найквиста – Котельникова будет звучать так: длина стороны квадратной ячейки сети должна быть в два раза меньше поперечного размера самой мелкой рыбы, которую требуется поймать сетями. Например, если поперечный размер рыбы должен быть не меньше 10 см, то сторона квадратной ячейки рыболовной сети должна быть не больше 5 см. При выполнении АЦП “улавливаемые” гармоники подобны рыбам, попадающим в сети; шаг дискретизации подобен размеру ячеек сети. Подробнее о гармониках будет рассказано в следующем параграфе. Задача 1. В течение 10 секунд производилась запись звука в компьютер. Определить объем записанной информации, если частота дискретизации была равна 10 кГц, а разрядность квантования — 16 бит. Количество произведенных измерений звукового сигнала (N) при частоте дискретизации Н (Гц) за время t (с) вычисляется по формуле: N = H·t. Подставляя данные задачи, получим: N = 10 000·10 = 100 000 измерений. Разрядность квантования: 16 бит = 2 байта. Отсюда объем звуковой информации: I = 100 000·2 = 200 000 б = 200 000/1024 Кб = 195,3125 Кб Задача 2. В файле хранится записанный звук. Данные не подвергались сжатию. Объем файла равен 1 Мб. Известно, что запись производилась с частотой 22 кГц при разрядности квантования звука — 8 бит. Определить время звучания при воспроизведении звука, хранящегося в файле. Из решения предыдущей задачи следует, что объем звуковой информации (I), частота дискретизации (H), разрядность квантования (b) и время записи звука (t) связаны между собой формулой: I = H·t·b Если воспроизведение записанного звука происходит без искажения, то время воспроизведения равно времени записи. Отсюда, искомая величина вычислится по формуле: t = I/(Hb) При вычислении переведем значения I и b в байты, а значение H — в герцы: t = 1·1024·1024/(22 000·1)
Вопросы и задания 1. Назовите основные этапы технологии кодирования аналогового сигнала естественного происхождения. 2. В каких устройствах происходит кодирование света? 3. Какие технические устройства используются для кодирования звука? 4. Дайте определения понятиям: частота дискретизации, разрядность квантования, уровни квантования. 5. Определите объем цифрового кода при записи звука в течение 1 минуты, если частота дискретизации была равна 44,1 Гц, а разрядность квантования — 8 бит. 6. Определите частоту дискретизации при кодировании звука, если объем звукового файла оказался равным 500 Кб, время записи — 0,5 минуты, разрядность квантования — 16 бит. Файл получен после 50%-ного сжатия исходного кода. §5. Численные эксперименты по обработке звукаГрафик функции Y(x) — наглядное (графическое) отображение зависимости значения функции Y от значения аргумента x. График строится в пределах области определения функции (области изменения аргумента x) и области значений Y. Если у функции бесконечная область определения, то для построения графика выбирается тот ее отрезок, в пределах которого поведение функции наиболее характерно. График периодической функции, как минимум, должен отражать один период изменения значений функции. Эксперимент 1: гармонические колебания Рассмотрим способ построения графика периодической функции, описывающей гармонические колебания. Гармоническими колебаниями называются периодические изменения со временем некоторой физической величины, описываемые функциями синуса или косинуса. В общем виде они выглядят так: Y = A·sin(2 Здесь A — амплитуда колебаний; t — время (аргумент функции); v — частота колебаний, измеряемая в герцах; j — начальная фаза колебаний. Период функций sin и cos равен 2 Звуковые колебания, описываемые гармонической функцией, называются гармоническими колебаниями. Чистые музыкальные тона: до, ре, ми и др. — представляют собой гармонические звуковые колебания разной частоты. Гармонические звуковые колебания издает камертон — эталонный источник музыкального тона. Гармонические колебания совершает математический маятник. В электрическом колебательном контуре сила тока периодически изменяется по гармоническому закону. Рассмотрим способ построения графика гармонической функции в среде электронной таблицы. Покажем, как это делается, на примере табличного процессора MS Excel. Работа происходит в два этапа: 1 — табулирование функции; 2 — построение графика функции. Полученная электронная таблица представлена на рис. 12.
Рис. 12. Таблица и график гармонической функции. Параметрами функции являются частота колебаний n и амплитуда А. Эти параметры вводятся, соответственно, в ячейки С1 и С2. Значение начальной фазы j примем равным нулю. Табулирование — это построение
таблицы значений функции на некотором интервале
значений аргумента с постоянным шагом. Шаг
табулирования ( Таблица помещена в ячейки А4:В25.
В столбце А расположены значения
аргумента — времени t, в столбце В — значения функции Y=A·sin(2 В ячейку В5 заносится формула: =$C$2*SIN(2*ПИ()*$C$1*A5). По этой формуле вычисляется значение функции от аргумента, находящегося в ячейке А5. Стандартная функция ПИ() возвращает значение числа Пифагора p. Формула из ячейки В5 копируется вниз по столбцу до ячейки В25. На рис. 12 показаны результаты табулирования функции для значений n = 10 Гц, A = 1. Шаг табулирования принят равным 0,005. При частоте 10 Гц период колебаний равен 1/10 = 0,1 с. При шаге табулирования 0,005 на одном периоде укладывается 20 шагов. Это вполне достаточное количество значений для построения графика функции. Построение графика. Для графической обработки данных в табличном процессоре существует мастер построения диаграмм и графиков. Его вызов происходит через меню по командам: Вставка — Диаграммы. Дальнейшие шаги алгоритма следующие: 1 — выбрать тип диаграммы: стандартные — точечная, вид — сглаживающие линии 2 — задать диапазон данных (значений функции): в столбцах — В5:В25; закладка РЯД, значения Х: А5:А25 3 — определить заголовок: Y=A·sin(2 4 — указать, на каком листе книги разметить диаграмму. Нажмите ГОТОВО. График построен. Толщину линий, цвет фона, вид координатной сетки можно настроить отдельно, используя контекстное меню (по правой кнопке мыши), задавая нужные форматы объектов. Человек слышит звуковые колебания, в среднем, в диапазоне частот от 20 Гц до 20 кГц. Частота 10 Гц — это частота инфразвука. Некоторые животные воспринимают его на слух. Если же удвоить частоту, то будет достигнута нижняя частотная граница слышимости человека. Но тогда на временном интервале 0,1 секунды поместится два периода колебаний. Такой эксперимент легко выполнить на построенной электронной таблице. Измените значение частоты в ячейке С1 на 20, после чего будет пересчитана таблица, а график примет вид, представленный на рис. 13.
Рис. 13. График звуковых колебаний для n = 20 Гц На интервале времени 0,1 секунды уложилось 2 периода функции. Следовательно, период колебаний равен 0,05 секунды. Задания. Проведите несколько экспериментов с электронной таблицей для значений частоты: 5, 15, 30, 40 Гц. В каждом случае определите, сколько периодов колебаний укладывается в интервал 0,1 секунды. Эксперимент 2: негармонические колебанияВ разделе математики, который называется гармоническим анализом, доказано, что любую периодическую функцию Y(t) с частотой n можно представить в виде суммы гармонических (синусоидальных) функций с частотами n, 2n, 3n, 4n… Такие слагаемые называются гармониками, а представление функции в виде суммы гармоник называется ее гармоническим разложением: Y(t) = A1sin(2 Здесь А1, А2, … — амплитуды гармоник, j1, j2, …. — начальные фазы гармоник. Количество слагаемых для некоторых функций может быть конечным, но может быть и бесконечным. Пример. Построим график негармонической периодической функции, представляемой в виде суммы двух гармоник: Y(t) = A1sin(2 Начальные фазы равны нулю. Выполним расчеты для следующих значений параметров: v = 20 Гц, A1 = А2 = 1. Как это было выше, вычисления будем производить на отрезке времени от 0 до 0,1 секунды, шаг табулирования — 0,005. Для получения таблицы значений достаточно заменить содержимое ячейки В5 на следующую формулу: =$C$2*SIN(2*ПИ()*$C$1*A5)+$C$2*SIN(2*ПИ()*2*$C$1*A5) Затем скопировать эту формулу вниз по столбцу В.
Рис. 14. График негармонических колебаний Построенный график представлен на рис. 14. Из графика видно, что период колебаний равен 0,05 с, т.е. равен периоду первой гармоники. Максимальная амплитуда колебаний увеличилась и стала равна приблизительно 1,54. Задания 1. Получите график колебаний, который отличается от рассмотренных в примере тем, что амплитуда второй гармоники в два раза меньше, чем первой: A2 = A1/2. 2. Получите график колебаний,
складывающихся из трех гармоник со следующими
параметрами: A1 = 1, 3. Получите график колебаний, складывающихся из двух гармоник с параметрами: A1 = 1, v1 = 20 Гц, j1 = 0; A2 = A1, v2 = 2v1 Гц, j2 = p/2. Сравните полученный график с графиком на рис. 14. Как повлиял сдвиг фаз между гармониками на амплитуду колебаний, на период колебаний? Эксперимент 3: дискретизация и квантование звуковых колебанийВ этом эксперименте моделируется процесс аналого-цифрового преобразования. АЦП включает в себя дискретизацию сигнала по времени и квантование значений амплитуды сигнала. Дискретизация по времени определяется значением частоты дискретизации H (Гц). Шаг по времени между двумя измерениями равен 1/Н секунд. Процесс квантования амплитуды определяется параметром глубины квантования звука: b. Количество уровней квантования равно 2b. Коды, определяющие амплитуду звукового сигнала, — это целые числа в диапазоне от 0 до 2b – 1. Модель процесса квантования звукового сигнала, реализованная в электронной таблице, представлена на рис. 15. Рассматривается гармонический сигнал с частотой n = 20 Гц. Значение частоты сигнала хранится в ячейке С1. Частота дискретизации АЦП равна Н = 200 Гц (ячейка С2). Глубина квантования b = 8 бит (ячейка G2). Столбец А содержит моменты времени измерений сигнала при выполнении АЦП. В ячейке А5 — начальный момент времени t = 0. Затем время увеличивается с шагом 1/H с. В ячейке А6 записана формула: =A5+1/$C$2. Далее эта формула скопирована вниз по столбцу А. Значение амплитуды аналогового сигнала вычисляется по формуле: Y = 0,5(1+sin(2 Такое преобразование синусоиды переносит ее в область неотрицательных значений Y в интервале от 0 до 1. Это сделано для упрощения описания дальнейшего процесса квантования. В ячейку В5 занесена следующая формула: =(1+SIN(2*ПИ()*$C$1*A5))/2. Затем эта формула скопирована вниз по столбцу В. В столбце С получены коды измерений амплитуды сигнала, представленные целыми десятичными числами. При записи в память компьютера они переводятся в двоичную систему счисления. В ячейку С5 помещена формула: =ЦЕЛОЕ(B5*2^$G$2). Смысл ее следующий: поскольку Y лежит в диапазоне от 0 до 1, то значение выражения [Y·2b] будет равно целым числам в диапазоне от 0 до 2b. Здесь квадратные скобки обозначают выделение целой части числа. При построении диаграммы “Кодирование сигнала” следует выбирать тип “Гистограмма”. Дискретный вид гистограммы наглядно отражает дискретный характер кода. Таблица построена в расчете на 21 измерение сигнала. При данных значениях n и Н удалось измерить два периода колебаний сигнала. При изменениях трех параметров модели: v, Н и b — будет происходить автоматический пересчет таблицы. Например, если увеличить частоту дискретизации в 2 раза, т.е. занести в ячейку С2 число 400, то получим графики, представленные на рис. 16.
Рис. 15. Гармонический аналоговый сигнал и результаты квантования.
Рис. 16. АЦП с частотой дискретизации 400 Гц Измерения произведены на одном периоде колебаний. Дискретный код теперь более подробно описывает колебательный процесс.
Рис. 17. АЦП с глубиной квантования 16
бит Гистограмма квантования на рис. 17 получена для b = 16. Видно, что увеличился диапазон значений кода. Следовательно, кодирование дает более точную информацию о величине сигнала, чем при b = 8. Задания 1. Проведите расчеты при значениях
параметров: 2. Проведите численные эксперименты по кодированию негармонических колебаний. Функции, описывающие негармонические колебания, возьмите из заданий к эксперименту № 2. 3*. Из теоремы Найквиста —
Котельникова следует, что для восстановления по
дискретному коду гармонических колебаний с
частотой n частота дискретизации должна быть
не меньше, чем 2v, т.е. должно выполняться
условие: H 4. Составьте программу на Паскале, моделирующую процесс кодирования аналогового сигнала (без графики). Программа должна воспроизводить таблицы, которые были получены выше в среде табличного процессора. §6. Сжатие двоичного кодаЛюбая информация в компьютере представляется в форме двоичного кода. Чем больше объем этого кода, тем больше места в памяти он занимает, тем больше времени требуется для его передачи по каналам связи. Все это сказывается на производительности компьютера, на эффективности использования компьютерных сетей. Сокращение объема данных происходит путем сжатия двоичного кода. Возможны две ситуации при сжатии: 1) потеря информации в результате сжатия недопустима; 2) допустима частичная потеря информации в результате сжатия. В первом случае сжатие, или упаковка, данных производится лишь для временного их хранения на носителях или передачи по каналам связи. Для работы с этими данными требуется их распаковка, т.е. приведение к первоначальному виду. При этом ни один бит не должен быть потерян. Например, если сжатию подвергается текст, то после распаковки в нем не должен быть искажен ни один символ. Сжатая программа также должна полностью восстанавливаться, поскольку малейшее искажение приведет ее в неработоспособное состояние. Сжатие без потери информации обычно используется при создании файловых архивов. Упаковка с частичной потерей информации производится при сжатии кода изображения (графика, видео) и звука. Такая возможность связана с субъективными возможностями человеческого зрения и слуха. Исследования ученых показали, что на наше зрение более существенное воздействие оказывает яркость точки изображения (пикселя), нежели ее цветовые свойства. Поэтому объем видеокода можно сократить за счет того, что коды цвета хранить не для каждого пикселя, а через один, два и т.д. пикселей растра. Чем больше такие пропуски, тем больше сжимаются видеоданные, но при этом ухудшается качество изображения. При кодировании видеофильмов — динамичного изображения, учитывается свойство инерционности зрения. Быстро меняющиеся фрагменты фильма можно кодировать менее подробно, чем статические кадры. Труднее всего сжатию поддается звуковой код. При хорошем качестве записи его объем в несжатом виде очень большой, а избыточность относительно мала. Здесь также используются психофизиологические особенности человеческого слуха. Учитывается, к каким гармоникам естественного звука наш слух более восприимчив, а к каким — менее. Слабо воспринимаемые гармоники отфильтровываются путем математической обработки. Сжатию способствует также учет нелинейной зависимости между амплитудой звуковых колебаний и восприятием нашим ухом громкости звучания. Различные алгоритмы сжатия кодов изображения и звука используются для реализации различных форматов представления графики, видео и звука. Подробнее об этом будет рассказано в разделе, посвященном информационным технологиям. Упаковка без потери информации. Существует два подхода к решению проблемы сжатия информации без ее потери. В основе первого подхода лежит использование неравномерного символьного кода. Второй подход основан на идее выявления повторяющихся фрагментов кода. Рассмотрим способ реализации первого подхода. В восьмиразрядной таблице символьной кодировки (например, KOI-8) каждый символ кодируется восемью битами и, следовательно, занимает в памяти 1 байт. В разделе 1.2.3 нашего учебника рассказывалось о том, что частота встречаемости разных букв (знаков) в тексте разная. Там же было показано, что информационный вес символов тем больше, чем меньше его частота встречаемости. С этим обстоятельством и связана идея сжатия текста в компьютерной памяти: отказаться от кодирования всех символов кодами одинаковой длины. Символы с меньшим информационным весом, т.е. часто встречающиеся, кодировать более коротким кодом по сравнению с реже встречающимися символами. При таком подходе можно существенно сократить объем общего кода текста и, соответственно, места, занимаемого им в памяти компьютера. Мы уже рассматривали азбуку Морзе, в которой применен принцип неравномерного кода. Если точку кодировать нулем, а тире — единицей, то это будет двоичный код. Правда, возникает проблема разделения букв друг от друга. В телеграфном сообщении она решается с помощью паузы — фактически третьего знака в азбуке Морзе. Одним из простейших, но весьма эффективных способов построения двоичного неравномерного кода, не требующего специального разделителя, является алгоритм Д.Хаффмана (D.A. Huffman, 1952 г.). Вариант кодовой таблицы Хаффмана применительно к прописным буквам латинского алфавита приведен в табл. 5. В этой таблице буквы расположены в порядке убывания частоты повторяемости в тексте. Самые часто используемые в текстах буквы Е и Т имеют коды размером 3 бита. А самые редкие буквы Q и Z — 10 бит. Чем больше размер текста, закодированного таким кодом, тем меньше его информационный объем по сравнению с объемом при использовании однобайтовой кодировки. Особенностью данного кода является его так называемая префиксная структура. Это значит, что код любого символа не совпадает с началом кода всех остальных символов. Например, код буквы Е — 100. Посмотрите табл. 5. Там нет ни одного другого кода, начинающегося с этих трех символов. По этому признаку символы отделяются друг от друга алгоритмическим путем.
Пример 1. Используя код Хаффмана, закодировать следующий текст, состоящий из 29 знаков: WENEEDMORESNOWFORBETTERSKIING Используя табл. 5, закодируем строку: 011101 100 1100 100 100 11011 00011 1110 1011 100 0110 1100 1110 011101 01001 1110 1011 011100 100 001 001 100 1011 0110 110100011 1010 1010 1100 00001 После размещения этого кода в памяти побайтно он примет вид: 01110110 01100100 10011011 00011111 01011100 01101100 11100111 01010011 11010110 11100100 00100110 01011011 01101000 11101010 10110000 001 В шестнадцатеричной форме он запишется так: 76 64 9B 1F 5C 6C E7 53 D6 E4 26 5B 68 EA B0 20. Таким образом, текст, занимающий в
кодировке ASCII 29 байтов, в кодировке Хаффмана
займет 16 байтов. Коэффициентом сжатия называют
отношение размера кода в байтах после сжатия к
размеру до сжатия (т.е. в 8-битовой кодировке). В
данном примере коэффициент сжатия оказался
равным 16/29 Раскодирование (распаковка) текста производится с помощью двоичного дерева кодирования Хаффмана. Графическое изображение дерева Хаффмана, соответствующего табл. 5, представлено на рис. 18. Двоичным называется дерево, из каждой вершины которого выходят не более двух ветвей. Листьями этого дерева, расположенными на концах ветвей, являются символы алфавита. Код символа формируется из последовательности двоичных цифр, расположенных на пути от корня дерева до листа-символа. Распаковка текста происходит путем сканирования двоичного кода слева направо, начиная с первого разряда, продвигаясь от корня по соответствующим (имеющим тот же двоичный код) ветвям дерева до тех пор, пока не будет достигнута буква. После выделения в коде буквы процесс раскодирования следующей буквы начинается снова от корня двоичного дерева. Пример 2. Раскодировать следующий двоичный код, полученный по алгоритму Хаффмана (пробелами код разделен на байты): 01010001 00100101 00100011 11111100 Двигаясь по дереву Хаффмана, начиная от первого слева разряда, получим следующую расшифровку:
Получилось слово HUFFMAN. Упакованный код
занимал 4 байта, исходный код — Дерево на рис. 18 представляет сокращенный вариант кода Хаффмана. В полном объеме в нем должны быть учтены все возможные символы, встречающиеся в тексте: пробелы, знаки препинания, скобки и др.
В программах, сжимающих текст, таблицу частоты встречаемости символов строят для каждого обрабатываемого текста, а затем формируют коды разной длины типа кодов Хаффмана. В таком случае сжатие текста становится еще более эффективным, так как кодирование настраивается именно на данный текст. В теории программирования алгоритмы, находящие оптимальное решение для каждого конкретного варианта задачи, называются жадными алгоритмами. К методам сжатия путем учета числа повторений фрагментов кода относятся алгоритм RLE и алгоритмы Лемпеля — Зива. В алгоритме RLE выявляются группы идущих подряд одинаковых однобайтовых кодов. Каждая такая группа заменяется на два байта: в первом указывается число повторений (не более 127), во втором — повторяющийся байт. Такой алгоритм благодаря своей простоте работает достаточно быстро. Наибольшую эффективность он дает при сжатии графической информации, содержащей большие области равномерной закраски. В алгоритмах Лемпеля — Зива (LZ77, LZ78) выявляются повторяющиеся последовательности байтов. Их условно можно назвать словами. Если при последовательном просмотре данных обнаруживается слово, которое уже встречалось раньше, то на него формируется ссылка в виде смещения назад относительно текущей позиции и длины слова в байтах. Программная реализация таких алгоритмов сложнее, чем для метода RLE. Но зато эффект сжатия получается значительно выше1. К методам кодирования информации мы еще вернемся, когда будем рассматривать приемы защиты данных путем шифрования.
Вопросы и задания 1. В каких случаях при сжатии данных можно допускать частичную потерю информации, а в каких нельзя? 2. За счет чего коды переменной длины позволяют “сжимать” текст? 3. Закодируйте с помощью кодов Хаффмана следующий текст: HAPPYNEWYEAR. Вычислите коэффициент сжатия. 4. Расшифруйте с помощью двоичного дерева Хаффмана следующий код: 11110111 10111100 00011100 00101100 10010011 01110100 11001111 11101101 001100 5. В чем идея алгоритма сжатия RLE? Какой тип информации сжимается наилучшим образом по этому алгоритму? 6. В чем идея алгоритма сжатия Лемпеля — Зива? 7. Какие свойства зрения и слуха человека используются для сжатия графической и звуковой информации? 1 Подробнее об алгоритмах сжатия см.: Андреева Е.В., Босова Л.Л., Фалина И.Н. Математические основы информатики. М.: БИНОМ. Лаборатория знаний, 2007. И.. Г.. Семакин |
|
|
47,66 c
vt + j) или Y = A·cos(2
t)
записан в ячейке G1. 
2v.
Попробуйте проверить эту теорему на нашей
модели. Попытайтесь объяснить получаемые
результаты.
