Теория кодирования

Число знаков (сигналов) равномерного кода определяется по формуле:

k  ≥ Log 2 N, где k - число сигналов, N – число символов в алфавите.

Примером равномерного алфавитного  кодирования является телеграфный  код Бодо, пришедший на сумму азбуке Морзе. Исходный алфавит должен содержать  не более 32 – х символов.

k  = Log 2 32 = 5.

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

 В русском алфавите 34 букв (с пробелом). Поэтому пришлось  объединить в один знак буквы  у – ё, ь – ъ,. После такого  сжатия N = 32. Знак препинания, либо отсутствует, либо заменяется буквенными аббревиатурами; такими как «ТЧК», «ЗПТ» и др.

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

1. Прописные и строчные буквы  латинского алфавита, всего 26 х 2 =

52 шт.

2. Прописные и строчные буквы русского алфавита : 33 х 2 = 66 шт.
3. Цифры от 0 до 9 – всего 10 шт.
4. Знаки математических операций, знаки препинания, специальные    

символы, всего 20 шт.

Общее число символов N = 148.

Длина кодовой цепочки : k >Log2148> 7,21. Длина кода выражается целым числом, поэтому берется k = 8.

Такой способ кодирования  принят в компьютерных системах, любому символу ставится в соответствие код из 8 двоичных разрядов (8 бит). Эта  последовательность сохраняется и  обрабатывается как единое целое (т.е. отсутствует доступ к отдельному биту) – по этой причине разрядность  устройств компьютера, предназначенных  для хранения или обработки информации, кратна 8. Совокупность восьми связанных  бит получила название байт, а представление  указанным образом символов –  байтовым кодированием.

Байт наряду с битом может использоваться как единица измерения количества информации в сообщении.

1 байт – соответствует  количеству информации в одном  знаке алфавита при их равновероятном  распределении.

Этот способ измерения  количества информации называется объемным.

Байт принят в качестве единицы количества информации в  международной системе единиц СИ.

1 байт = 8 бит.

1 Кбайт = 210 байт = 1024 байт  – килобайт

1 Мбайт = 220 байт = 1024 Кбайт  – мегабайт

1 Гбайт = 230 байт = 1024 Мбайт – гигабайт

1 Тбайт = 240 байт = 1024 Гбайт  – терабайт

Использование 8 – битных цепочек позволяет закодировать 256 символов, что превышает оцененное  выше N, следовательно, дает возможность употребить оставшуюся часть кодовой таблиц для представления дополнительных символов.

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

Первым таким международным стандартам, который применялся на больших вычислительных машинах, был EBCDIC (Extended Binary Coded Decimal Interchange Code) – расширенная двоичная кодировка десятичного кода обмена.

В персональных компьютерах  и телекоммуникационных системах применяется  международной байтовый код ASCII (American Standard Code for Information Interchange – стандартный американский код обмена информацией).

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

Вторая часть кодовой  таблицы – она считается расширением  основной – охватывает коды в интервале  от 128 до 255 (первый бит всех кодов 1). Она используется для представления  символов национальных алфавитов (например, русского), а также символов псевдографики. Для этой части также имеются стандарты, например, для символов русского языка это КОИ – 8, КОИ – 7 и др.

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

В настоящее время появился и находит все более широкое  применение еще один международный  стандарт кодировки – Unicode. Его особенность в том, что в нем использовано 16 – битное кодирование, т.е для представления каждого символа отводится 2 байта. Такая длина кода обеспечивает включения в первичный алфавит 65536 знаков. Это, в свою очередь, позволяет создать и использовать единую для всех распространенных алфавитом кодовую таблицу.

Алфавитное кодирование  с неравной длительностью элементарных сигналов. Код Морзе.

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

Пусть t – длительность импульса соответствует точке, тогда:

3 t – соответствие тире

3 t – пауза между буквами

t – длительность паузы между точками, точкой и тире, между тире

6 t – длительность паузы между словами и т.д

Свой код Морзе разработал в 1838 г., т.е. задолго до исследований относительной частоты появления  различных букв в текстах. При  составлении кодов Морзе для  букв русского алфавита учет относительной  частоты букв не производился, что, естественно, повысило его избыточность.

Блочное двоичное кодирование

Наилучший результат (наименьшая избыточность) был получен при  кодировании по методу Хаффмана –  для русского алфавита избыточность оказалась менее 1%. При этом указывалась, что код Хаффмана улучшить невозможно. На первый взгляд это противоречие первой теореме Шеннона, утверждающей, что всегда можно предложить способ кодирования, при котором избыточность будет сколь угодно малой величиной. На самом деле это противоречие возникло из – за того, что до сих пор  мы ограничивали себя алфавитным кодированием.

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

Пусть имеется словарь  некоторого языка, содержащий п = 16000 слов (Это солидный словарный запас). Поставим в соответствие каждому слову  равномерный двоичный код. Длину  кода находится по формуле по ранее  описанной формуле:

k  ≥Log 21600 > 13,97 = 14

Следовательно, каждое слово  кодируется комбинацией из 14 нулей  и единиц. В качестве примера закодируем несколько слов:

ИНФОРМАТИКА - 10101011100110,

НАУКА   - 00000000000001,

ИНТЕРЕСНАЯ   - 00100000000010;

Тогда последовательность :

000000000000110101011100110000000000000001 будет  означать «ИНФОРМАТИКА ИНТЕРЕСНАЯ  НАУКА».

Установлено, сто средней  длине русского слова равна 5,3 буквам, а с учетом пробела между словами, она станет равной К = 6,3 буквам.

Средняя информация на знак первичного алфавита F=k/K=14/6,3= 2,222 бит, что более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировании. Для английского языка такой метод кодирования дает 2,545 бит на язык. Таким образом, кодирование слов оказывается более выгодным,, чем алфавитное.

Еще более эффективным  окажется кодирование в том случае, если сначала установить относительную  частоту появления различных  слов в текстах и затем использовать код Хаффмана. Подобные исследования провел в свое время Шеннон : по относительным  частотам 8727 наиболее употребительных  в английском языке слов он установил, что средняя, что средняя информация на знак первичного алфавита оказывается равной 2,15 бит.

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

Алфавитное, т.е. побуквенное, кодирование можно задать таблицей кодов. Фактически  кодом, кодирующей функцией, будет служить некоторая  подстановка s:

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

Вторая строка – например, кортежи из цифр 0 и 1 – двоичное их представление.

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

Обязательным условием такого кодирования является установление взаимно-однозначного соответствия между  наборами элементов первой и второй строки.

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

5. Кодирование и обработка чисел компьютером

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

Целые положительные числа (целые числа без знака);

Целые числа со знаком;

Вещественные нормализованные  числа;

Кодирование в компьютере целых положительных чисел.

Для записи числа в устройствах  компьютера выделяется фиксированное  количество двоичных разрядов. Память компьютера имеет байтовую структуру, однако, размер одной адресуемой ячейки обычно составляет несколько байт. В компьютерах IBM ячейка памяти объединяет 2 байта (16 двоичных разрядов), что называется машинным словом.

Машинное слово – комбинация связанных соседних ячеек, обрабатываемая совместно.

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

  Размер разрядной  сетки строго определен, в связи  с этим и количество чисел,  с которыми может оперировать  компьютер конечно, среди которых  можно установить наименьшее  и наибольшее число. В обычном  не машинном представлении чисел  такого понятия как «наибольшее целое число» просто не существует [6,с. 233-267].

В языках программирования (PASCAL)  для записи целых чисел без знака, отводится 2 байта, и они определены как тип Word. Тип устанавливает способ кодирования числа, количество отводимых для записи ячеек памяти (т.е разрядность числа), а также перечень допустимых операций при обработке.

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

Кодирование в  компьютере целых отрицательных  чисел

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

- знак плюс или положительное  число  нулем,

- знак минус или отрицательное  число – единиц.

Такое представление чисел  называется прямым кодом.

Под запись самого числа  остается 16-1=15 двоичных разрядов, что  обеспечивает наибольшее значение числа .

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