Файл: Методы кодирования данных (История кодирования).pdf

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

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

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

Целью данной курсовой работы является изучение методов кодирования данных.

Выделим основные задачи, необходимые для решения поставленной цели:

Изучить историю кодирования;
Ознакомиться с основными понятиями;
Рассмотреть классификацию кодов;
Рассмотреть способы представления кодов;
Изучить методы кодирования данных.

Глава 1.Разнообразие методов кодирования

1.1.История кодирования

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

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

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

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

С 1845г. вошли в использование специальные кодовые книги; используя их, телеграфисты вручную совершали «компрессию» текстов (сообщений), заменяя распространенные последовательности слов наиболее короткими кодами. В то время появился контроль чётности, необходимый для проверки правильности ввода перфокарт в ЭВМ. В случае ненадёжности устройства ввода могла появиться ошибка. Для её коррекции процедуру ввода повторяли до того как высчитанная контрольная сумма не совпадёт с сохранённой на карте суммой. Данная схема совершенно неудобна и пропускает двойные ошибки.

Теоретическое решение проблемы передачи данных по зашумленным каналам первым предложил Клод Шеннон. Он написал работу «Математическая теория передачи сообщений» (1948), в которой и было изложено решение.

Практическое применение мыслей Шеннона было реализовано в деятельности Хэмминга. Учёный создал коды, которые способны исправлять ошибки и в каналах связи, и в магистралях передачи данных в ЭВМ, непосредственно между памятью и процессором. Данные коды используются и сейчас, просто они уже модифицированы.

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

1.2.Основные понятия в кодировании

Что же такое кодирование? Кодирование – создание кода и его присвоение к одиночному объекту или же группировке классификации.

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

Кодер – механизм, выполняющий кодирование.

Декодер – механизм, совершающий обратное преобразование.

Алфавит – изобилие возможных элементов (объектов) кода:

где . Число символов кода именуется основанием. Например, в случае двоичного кода , притом и .

Итоговый набор символов этого алфавита именуется кодовой комбинацией (или кодовым словом). Количество объектов в кодовом слове n именуется значностью/длиной комбинации.

Разряд кода – местонахождение знака.

Объёмом/мощностью кода N именуется количество разных кодовых слов

Если же - количество сообщений источника, то .

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

Существуют следующие алфавиты кодов:

Цифровой;
Буквенный;
Буквенно-цифровой;
Штриховой. Штрихи и пробелы – знаки кода.

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

1.3.Классификация кодов

Рассмотрим классификацию кодов в таблице 1.3.1.

По основанию	Бинарные – состоят из двух знаков.
По основанию	Небинарные
По длине кодового слова	Равномерные – кодовые слова имеют одинаковую длину.
По длине кодового слова	Неравномерные
По способу передачи	Последовательные
	Параллельные
	Блочные – изначально данные помещаются в буфер, а затем передаются в канал.
	Бинарные непрерывные
По помехоустойчивости	Простые (примитивные, полные) - для передачи информации применяют все возможные кодовые слова (без избыточности).
По помехоустойчивости	Корректирующие (помехозащищенные) - для передачи сообщений используют лишь некоторую часть (разрешенных) кодовых слов.
В зависимости от назначения и использования кодов	Внутренние коды - это коды, применяемые внутри устройств. Это машинные коды, а также коды, базирующиеся на использовании позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Наиболее распространенным кодом в ЭВМ является двоичный код, который позволяет просто реализовать аппаратно устройства для хранения, обработки и передачи данных в двоичном коде. Он обеспечивает высокую надежность устройств и простоту выполнения операций над данными в двоичном коде. Двоичные данные, объединенные в группы по 4, образуют шестнадцатеричный код, который хорошо согласуется с архитектурой ЭВМ, работающей с данными кратными байту (8 бит).
	Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code). В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.). При кодировании информации для передачи по каналам связи, в том числе внутри аппаратным трактам, используются коды, обеспечивающие максимальную скорость передачи информации, за счет ее сжатия и устранения избыточности (например: коды Хаффмана и Шеннона-Фано), и коды обеспечивающие достоверность передачи данных, за счет введения избыточности в передаваемые сообщения (например: групповые коды, Хэмминга, циклические и их разновидности).
	Коды для специальных применений - это коды, предназначенные для решения специальных задач передачи и обработки данных. Примерами таких кодов является циклический код Грея, который широко используется в АЦП угловых и линейных перемещений. Коды Фибоначчи используются для построения быстродействующих и помехоустойчивых АЦП.

Таблица 1.3.1.Классификация кодов

На основание данной классификации можно выделить следующие цели кодирования:

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

На основании данных целей выделяются два направления развития теории кодирования:

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

1.4.Способы представления кодов

Существуют различные способы представления кодов, рассмотрим наиболее часто используемые (Табл.1.4.1).

Название

Объяснение

Матричное

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

Пример:

Кодовые деревья

Кодовое дерево - связной граф, не содержащий циклов.

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

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

Для дерева неравномерного кода применяется взвешенный граф, притом на ребрах дерева задаётся вероятность переходов. Представление кода в виде кодового дерева используется, например, в кодах Хаффмена.

Рис.1.4.1.Кодовое дерево^[1]

Многочлены

Представление кодов в виде полиномов основано на подобии (изоморфизме) пространства двоичных - последовательностей и пространства полиномов степени не выше .

Код для любой системы счисления с основанием может быть представлен в виде:

где - цифры данной системы счисления (в двоичной 0 и 1);

- символическая (фиктивная) переменная, показатель степени которой соответствует номерам разрядов двоичного числа-

Например: кодовое слово 1010110 может быть представлено в виде:

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

Геометрическое

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

В общем случае n мерный куб имеет вершин, что соответствует набору кодовых комбинаций .

Рис.1.4.2. Геометрическая модель двоичного кода

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

Таблица 1.4.1.Способы представления кодов

Глава 2.Методы кодирования данных

2.1.Кодирование символьной информации

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

Процесс вывода знака на экран или же на печатающее устройство именуется декодирование – обратное преобразование.

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

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

В ASCII изначальные 128 знаков – стандартные: нумерация знаков от до . Сюда входят и цифры, и буквы латинского алфавита, и знаки препинания, и скобки, и иные знаки.

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

Для кодирования русских букв есть таблицы КОИ-8, СР-1251, СР-866, ISO, Mac.

Для русского языка принята в качестве стандарта кодировка ISO 8859-5.

Сегодня наиболее распространена кодировка СР-1251. Это кодировка MS Windows.

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

К сожалению, с течением времени стало понятно, что 256 символов – это достаточно мало. Часто в различных профессиях при создании текста необходимо употреблять символы из разных алфавитов. Потому была создана новая универсальная система кодирования текста – Unicode. В ней отдельному знаку даётся не один байт, а два. Таким образом, доступно кодов.

Наиболее часто используют кодировки Unicode UTF-8 и UTF-16:

Название кодировки	Описание
UTF-8	Знаки могут иметь длину от до байт. Используя данную кодировку можно отобразить любой знак. Данная кодировка обратно совместима с ASCII. Это рекомендованная кодировка для электронной почты и веб-страниц.
UTF-16	16-битный формат даёт возможность кодировать любые знаки переменной длины. Данная кодировка используется в основных ОС и средах разработки, таких как Microsoft Windows 2000/XP/2003/Vista/CE, Java и .NET.