Кодирование по образцу

Данный вид кодирования применяется для представления дискретного сигнала на том или ином машинном носителе.

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

Рассмотрим виды таких кодов: прямые; ASCII-коды; коды Грея; коды, учитывающие частоту символов; код Штибица.

Прямые коды

Применяются для представления в ЭВМ числовых данных и используют двоичную систему счисления.

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

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

Таблица 2

Прямые коды могут использоваться для кодирования и нечисловых данных.

Пример 1. Построить двоичные коды для символов a, b, c, d.

Пронумеруем исходные символы, начиная с нуля, и по таблице 1 сформируем двоичные коды для номеров символов. Тогда двоичные коды исходных символов примут вид:

Для получения двоичного кода постоянной длины добавим незначащие нули к кодовым комбинациям для a и b. Получим:

Пример 2. С помощью полученной таблицы закодировать сообщение (дискретный сигнал) "abba".

Результат: abba = 00010100.

ASCII-коды

Наиболее распространенным является код ASCII (American Standard Code for Information Interchange), который используется для внутреннего представления символьной информации в операционной системе MS DOS, в Блокноте операционной системы Windows’xx, а также для кодирования текстовых файлов в Интернет. Структура кода представлена в таблице (обозначения столбцов и строк выделены полужирно).

Таблица кодов содержит 16 столбцов и 16 строк; каждая строка и столбец пронумерованы в шестнадцатеричной системе счисления цифрами от 0 до F. Шестнадцатеричное представление ASCII-кода складывается из номера столбца и номера строки, в которых располагается символ. Так, например, ASCII-код символа 1 есть число 31₁₆, что по правилам перевода означает 110001₂. В двоичной системе код представляется восемью разрядами, т.е. двоичный ASCII-код символа 1 есть 00110001₂.

Данная таблица делится на две части: столбцы с номерами от 0 до 7 составляют стандарт кода – неизменяемую часть; столбцы с номерами от 8 до F являются расширением кода и используются, в частности, для кодирования символов национальных алфавитов. В столбцах с номерами 0 и 1 находятся управляющие символы, которые используются, в частности, для управления принтером. Столбцы с номерами от 2 до 7 содержат знаки препинания, арифметических действий, некоторые служебные символы, а также заглавные и строчные буквы латинского алфавита. Расширение кода включает символы псевдографики, буквы национальных алфавитов и другие символы.

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

Пример 1. С помощью таблицы ASCII-кодов закодировать сообщение "группа", используя шестнадцатеричное представление кода.

Результат: A3 E0 E3 AF AF A0 (для простоты коды символов разделены пробелами)

Коды Грея

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

Как видно, коды лексикографически (в данном случае, по значению) упорядоченных цифр 1 и 2 в случае кода Грея различаются одним двоичным разрядом, а прямые коды этих же цифр – двумя разрядами. Аналогичную картину можно наблюдать в случае пар цифр 3 и 4; 5 и 6; 7 и 8.

Для формирования кода Грея можно использовать следующую последовательность действий:

Шаг 1) код Грея для 0 и 1 равен 02 и 12, соответственно;

Шаг 2) для построения кодов Грея для десятичных чисел 2 и 3 построим таблицу, в которой для нумерации строк и столбцов использованы коды Грея для чисел 0 и 1 (обозначение строк и столбцов выделены серым фоном):

В ячейках таблицы размещены кодируемые десятичные числа, включая и уже закодированные 0 и 1. Стрелки показывают направление перемещения по ячейкам для формирования кода одного из чисел (само число указано в ячейке). Тогда код Грея для произвольного числа, размещенного в некоторой ячейке, формируется как номер строки и номер столбца для этой ячейки. Так, код Грея для числа 3 – это 102, а для числа 2 – 112. Поскольку код Грея имеет постоянную длину, сформированные ранее коды для чисел 0 и 1 пополняются незначащими нулями, т.е. код Грея для 0 – это 002, а для 1 – это 012;

Шаг 3) получив коды Грея для четырех десятичных чисел, используем их в качестве номеров строк и столбцов, чтобы сформировать кодовые комбинации для первых шестнадцати десятичных цифр:

Так, например, для получения кода числа 9 выписывают обозначения строки и столбца: соответственно, 11 и 01. Тогда получаем код: для числа 15 кодом будет комбинация 1000, для числа 11 – 1110 и т.д.

Поскольку переход от числа 15 к 0 также является одношаговым (эти числа имеют коды, соответственно, 1000 и 0000), построенный код называют также циклически одношаговым;

Шаг 4) для формирования кода Грея для множества последовательных натуральных чисел, начинающихся с нуля, в количестве 2m строят таблицу размером mxm и нумеруют строки и столбцы в соответствии с кодами Грея, построенными на предыдущих этапах для m чисел. Получают коды Грея в соответствии с рассмотренными схемами.

Следует отметить, что таблицы для кода Грея не обязательно квадратные: число строк и столбцов могут не совпадать.

Пример 1. Построить код Грея для алфавита, который используется при записи фамилии "Шеннон". При этом не различать строчные и прописные буквы.

Сформирует исходный алфавит, для которого будем строить код. Это множество символов {е, н, о, ш}. Отметим, что символы в множестве упорядочены по алфавиту. Тогда построим таблицу размером 2х2, введем обозначения строк и столбцов и разместим в ячейках символы алфавита. Получим:

Тогда коды Грея: е - 00, н - 01, о - 11, ш - 10.

Пример 2. Закодировать фамилию "Шеннон" построенным в примере 1 кодом Грея (строчные и прописные буквы не различаются).

Получаем: 10 00 01 01 11 01 (коды символов для простоты разделены пробелами).

Поиск по сайту: