Основные понятия и определения
В технике особую роль приобрели преобразования дискретной информации, так как многочисленные исследования показали, что в реальных условиях непрерывный сигнал без потерь для качественных характеристик функционирования системы может быть заменен дискретным сигналом. Дискретные представления информации все более широко распространяются при передаче и обработки информации. Формой представления информации является сообщение.
Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации.
Декодирование – это операция восстановления принятого сообщения. Один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (так, китайские иероглифы обозначают целые слова и понятия).
Код - система соответствия между элементами сообщений и кодовыми комбинациями.
Кодер - устройство, осуществляющее кодирование.
Декодер - устройство, осуществляющее обратную операцию, т.е. преобразование кодовой комбинации в сообщение.
Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {xi}, где i = 1, 2,..., m. Количество элементов кода - m называется его основанием. Для двоичного кода xi = {0, 1} и m = 2. Конечная последовательность символов данного алфавита называется кодовой комбинацией (кодовым словом). Число элементов в кодовой комбинации - n называется значностью (длиной комбинации). Число различных кодовых комбинаций (N = mn) называется объемом или мощностью кода.
Каждая комбинация записывается в виде последовательности, составленной из некоторых условных символов – элементов кодовой комбинации. В качестве элементов кодовой комбинации могут использоваться буквы (A, B, C, …) и цифры (0, 1, 2, …).
В технических информационных устройствах элементами могут служить одиночные импульсы постоянного тока (видеоимпульсы), переменного тока (радиоимпульсы), пауза между импульсами. Эти элементы различаются по какому-либо одному или нескольким кодовым (импульсным признакам). В качестве кодовых признаков применяются такие параметры, как величина, полярность, время, фаза, частота. Каждому сообщению однозначно соответствует определенная кодовая комбинация. Код позволяет записать все сообщения на некотором общем для данного набора сообщений языке.
Оценка кодов обычно производится по их основным характеристикам, выражающим различные количественные и качественные показатели. Эти характеристики используются при выборе кодов, предназначенных для передачи, хранения и обработки информации: длина кода; основание кода; мощность кода; полное число кодовых комбинаций; число информационных символов; число проверочных символов; избыточность кода; скорость передачи; вес кодовой комбинации; кодовое расстояние d0; весовая характеристика кода; вероятность необнаруженной ошибки; оптимальность кода; коэффициент ложных переходов.
Среднее число символов, приходящихся на единицу сообщения, должно быть минимальным. При отсутствии помех это требование приводит к выигрышу во времени при передаче сообщения или к сокращению объёма памяти запоминающего устройства при хранении. Такое кодирование называется безызбыточным или оптимальным; • кодирование должно обеспечивать заданную достоверность при передаче либо хранении информации. Однако это требует избыточности в представлении сообщения, и такое кодирование называется избыточным или помехоустойчивым. Помехоустойчивость кодов достигается введением избыточности в кодовые комбинации (вводят дополнительные разряды). Если, например, для кодирования всех символов внешнего алфавита достаточно иметь m-разрядный первичный код, то для обеспечения помехоустойчивости к его "in" разрядам добавляют "к" избыточных разрядов. При этом длина результирующей КК становится равной n=m+k. Коды, не обладающие избыточностью, не способны обнаруживать и тем более исправлять ошибки. Таким образом, от способа кодирования сообщения зависят и время его передачи, и достоверность. Для разрешения противоречия в системах передачи дискретных сообщений (данных) используют два алфавита: один имеет достаточно большой объём, применяется для представления сообщения на языке источника и получателя информации и называется внешним алфавитом; второй используют непосредственно для передачи информации по каналу, он содержит небольшое число символов и называется внутренним алфавитом. Чем меньше символов содержит внутренний алфавит, тем легче их различать в условиях помех. Проблемы помехоустойчивого кодирования решаются специальными методами.
Классификация кодов
Коды можно классифицировать по различным признакам:
1. По основанию (количеству символов в алфавите): бинарные (двоичные m=2) и небинарные
2. По длине кодовых комбинаций (слов):
Равномерные - если все кодовые комбинации имеют одинаковую длину;
Неравномерные - если длина кодовой комбинации не постоянна.
3. По способу передачи:
последовательные и параллельные;
блочные - данные сначала помещаются в буфер, а потом передаются в канал и бинарные непрерывные.
4. По помехоустойчивости:
простые (примитивные, полные) - для передачи информации используют все возможные кодовые комбинации (без избыточности);
корректирующие (помехозащищенные) - для передачи сообщений используют не все, а только часть (разрешенных) кодовых комбинаций.
5. В зависимости от назначения и применения условно можно выделить следующие типы кодов:
Внутренние коды - это коды, используемые внутри устройств. Это машинные коды, а также коды, базирующиеся на использовании позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Наиболее распространенным кодом в ЭВМ является двоичный код, который позволяет просто реализовать аппаратно устройства для хранения, обработки и передачи данных в двоичном коде. Он обеспечивает высокую надежность устройств и простоту выполнения операций над данными в двоичном коде. Двоичные данные, объединенные в группы по 4, образуют шестнадцатеричный код, который хорошо согласуется с архитектурой ЭВМ, работающей с данными кратными байту (8 бит).
Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code).
В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).
При кодировании информации для передачи по каналам связи, в том числе внутри аппаратных трактах, используются коды, обеспечивающие максимальную скорость передачи информации, за счет ее сжатия и устранения избыточности (например: коды Хаффмана и Шеннона-Фано), и коды обеспечивающие достоверность передачи данных, за счет введения избыточности в передаваемые сообщения (например: групповые коды, Хэмминга, циклические и их разновидности).
Коды для специальных применений - это коды, предназначенные для решения специальных задач передачи и обработки данных. Примерами таких кодов является циклический код Грея, который широко используется в АЦП угловых и линейных перемещений. Коды Фибоначчи используются для построения быстродействующих и помехоустойчивых АЦП.
Также коды могут иметь разное назначение и в соответствии с этим подразделяются на телеграфные, телемеханические, телевизионные и т.д.
Цели кодирования
Цели кодирования:
1. Повышение эффективности передачи данных, за счет достижения максимальной скорости передачи данных.
2. Повышение помехоустойчивости при передаче данных.
В соответствии с этими целями теория кодирования развивается в двух основных направлениях:
1. Теория экономичного (эффективного, оптимального) кодирования занимается поиском кодов, позволяющих в каналах без помех повысить эффективность передачи информации за счет устранения избыточности источника и наилучшего согласования скорости передачи данных с пропускной способностью канала связи.
2. Теория помехоустойчивого кодирования занимается поиском кодов, повышающих достоверность передачи информации в каналах с помехами.
Дискретное двоичное представление информации обычно имеет некоторую избыточность. Часто в информации присутствуют последовательности одинаковых битов или их групп. Объём информации имеет большое значение не только для хранения, но также непосредственно влияет на скорость передачи информации по компьютерным сетям. Поэтому были разработаны специальные методы (алгоритмы) сжатия информации (data compression), с помощью которых можно существенно уменьшить ее объём. Существуют как универсальные алгоритмы, так и специализированные.
Основными техническими характеристиками процессов сжатия и результатов их работы являются:
степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;
скорость сжатия – время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;
качество сжатия – величина, показывающая, насколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму.
Все способы сжатия можно разделить на две категории: обратимое и необратимое сжатие.
Необратимое сжатие – такое преобразование входного потока информации, при котором выходной поток, основанный на определенном формате информации, представляет собой объект, достаточно похожий по внешним характеристикам на входной поток, однако отличается от него объемом.
Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (до сжатия и после), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия информации растровых графических файлов, видео и звука. При таком подходе используется свойство структуры данного формата файла и возможность представить информацию приблизительно схожую по качеству для восприятия человеком. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходная информация в процессе сжатия изменяется.
Обратимое сжатие всегда приводит к снижению объема выходного потока информации без изменения его информативности, т.е. без потери информационной структуры.
Из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой и только после процесса распаковки информация пригодна для использования в соответствии с их внутренним форматом.
Способы обратимого сжатия информации
Сжатие способом кодирования серий (RLE).
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем – это кодирование серий последовательностей (Run Length Encoding – RLE).
Алгоритм Хаффмана.
Сжимая файл по алгоритму Хаффмана, первое, что необходимо сделать – прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII.
Арифметическое кодирование.
Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов и является наиболее оптимальным, т.к. достигается теоретическая граница степени сжатия.
Двухступенчатое кодирование. Алгоритм Лемпеля-Зива.
Гораздо большей степени сжатия можно добиться при выделении из входного потока повторяющихся цепочек блоков, и кодирования ссылок на эти цепочки с построением хеш-таблиц от первого до n-го уровня с последующим.