Файл: Анализ методов кодирования данных (Общие сведения и понятия в информатике).pdf

В вычислительной технике существует своя (внутренняя) система кодирования — она называется двоичным кодированием и основана на представлении данных последовательностью всего двух знаков: 0 и 1. Эти знаки называются двоичными цифрами, по-английски —binarydigit, или, сокращенно,bit (бит).

1.4. Понятие избыточность информации и необходимость ее сжатия

Характерной особенностью большинства «классических» типов информации, с которыми работают люди, является их избыточность. В русском языке существуют слова, однозначно прочитываемые в случае «потери» некоторых букв. Например, С_НТ_БРЬ, МОС_, Д_Р_ВО. Кроме того, имея текст на русском языке с «потерянными» буквами, человек, достаточно хорошо владеющий русским языком, может однозначно восстановить его. Например, вы без труда прочитаете предложение с пропущенными буквами Дм_т_ий Ива_ов__ Менд_ле_в – в_л_ки_рус_кий х_мик. Однако если это предложение будет читать иностранец, едва знающий русский язык и русскую историю, то он не сможет его понять. Мы, носители русского языка, можем с лёгкостью восстановить окончания, пропущенные буквы в слогах, подобрать подходящие слова.

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

Например, сумма чисел 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40 записывается так:

2+4+6+……37+38+40

Эта сумма составлена из всех чётных чисел от 2 до 40. Используя математическую нотацию, эту сумму можно записать намного короче:

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

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

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

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

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

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

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

Вообще, степень избыточности естественной информации достаточно велика. Клод Шеннон, исследовав избыточность литературного английского языка, установил, что она составляет около 50%. Это означает, что если в английском тексте наугад стереть около половины букв, то по оставшимся буквам человек, знающий английский язык, почти наверняка сможет восстановить текст.

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

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

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

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

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

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

Сжатие данных полностью основано на кодирование данных.

Глава 2. КОДИРОВАНИЕ В ЭВМ

2.1. Кодирование данных в вычислительной технике

Существует два принципиально отличных способа представления информации: непрерывный и дискретный.

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

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

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

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

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

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

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

Рассмотрим такую, казалось бы, “неарифметическую” величину, как цвет, обычно представляемую в компьютере как совокупность интенсивности трех базовых цветов RGB. Тем не менее, записанные вместе, все три интенсивности образуют единое “длинное” число, которое формально вполне можно принять за номер цвета.

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

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

Таким образом, проблема кодирования информации для компьютера естественным образом распадается на две составляющие:

кодирование чисел и способ кодирования, который сводит информацию данного вида к числам.

Независимо от того, как изображает исходные данные пользователь (числа или строки символов), они преобразуются в последовательности двоичных цифр 0 и 1.

Двоичная цифра называется битом. Группа из n бит позволяет

представить 2ⁿ комбинаций от 00...00 до 11...11. Представление данных группой из восьми бит называется байтом. С помощью одного байта можно закодировать 2⁸ =256 различных комбинаций.

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

Биты в байте нумеруются справа налево, начиная с нуля. Четыре соседних бита в байте называются тетрадой.

Единица данных, кратная байту и равная разрядности регистров процессора ЭВМ, называется машинным словом.

Машинное слово является основной единицей данных, которой оперирует процессор ЭВМ. Длина слова может составлять 1, 2, 4, 8 и более байт.

Для представления больших объемов информации используются производные от байта крупные единицы измерения: килобайт (Кбайт), мегабайт (Мбайт), гигабайт (Гбайт). При этом выполняются следующие соотношения:

1 Кбайт = 210 = 1024 байт; 1 Мбайт = 220 = 1 048 576 байт; 1 Гбайт = 230 = 1 073 741 824 байт.

Процесс обработки информации в ЭВМ сопровождается преобразованием чисел из одной системы счисления в другую.

Система счисления — это способ наименования и представления чисел с помощью символов, имеющих определенные количественные значения. В зависимости от способа представления чисел системы счисления делятся на непозиционные и позиционные.

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

Двоичная система счисления имеет набор цифр {0,1} и p =2.