Файл: Каверкин, И. Я. Анализ и синтез измерительных систем.pdf

Количественное значение числа определяется следующим ря­ дом:

W = É ö;ßi-

Обычно ߣ- выражается как степень:

■

При этом at является изображением цифр в данной системе счисления и принимает значения от 0 до q—1. __

Рассмотрим десятичную систему: q — 10, цифры 0,9;

N = ап 10" + а„_і ІО"—1 + . . . -f- аг ІО1 +

+ ао 10° + а_і 1 0 -Ч - . . . + ß-m 10_m.

Здесь n цифр с положительными индексами соответствуют це­ лой, а т цифр с отрицательными индексами — дробной части числа.

Для двоичной системы имеем: q --■=2, цифры 0,1; N = ап2п +

Р an_j2'1-1 + . . . f йі22' + а02° — целое число.

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

В тех случаях когда целесообразно сохранить преимущества двоичной системы и удобство десятичной, обращаются к так назы­ ваемым двоично-десятичным кодам. При этом каждая цифра деся­ тичного числа записывается в виде четырехразрядного двоичного числа, называемого тетрадой. Чаще всего используется код 8—4— —2— 1 с весами 8, 4, 2 и 1 в соответствующих разрядах. В двоично­ десятичном коде число 24, например, запишется как 0010 0100, а

число 81 — как 1000 0001.

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

Возникает проблема создания эффективного кода, обеспечиваю­ щего возможность представления требуемого массива данных с ми­ нимальной затратой ресурсов. Иногда (этот случай рассмотрен в [26]) в качестве критерия эффективности кода выбирают произ­ ведение различных символов q и количества разрядов для выра­ жения любого числа. Оказывается, что эффективность кода при этом зависит не только от основания, но и от значения представляе­ мого числа. Рассмотрим таблицу, в которой (в числителе) приве­

37

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

Даже беглый анализ данной таблицы показывает, что определе­ ние (выбор) оптимального кода при принятом критерии требует уточнения постановки задачи. Если требуется минимизировать произведение q (я -}- 1) (я -f 1 — число разрядов) для фиксиро­ ванного числа, то данный подход позволяет получить искомое зна­ чение q. Если же речь идет о совокупности чисел, то оптимизация должна производиться по вероятностному критерию, например среднему значению произведения. Результат, естественно, будет иным. Возможно, наконец, что требуется учесть какие-либо огра­ ничения: по максимальному допустимому значению разрядов и т. п. Тогда процедура выбора оптимального кода должна строиться с учетом подобных ограничений.

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

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

Предположим, что имеется память в виде запоминающего устрой­ ства (ЗУ) на М 2 адресов, причем допускается непосредственное обращение к любому адресу памяти. Емкость адресной ячейки па­ мяти, выражаемая количеством разрядов используемых символов,

38

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

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

Рассмотрим для пояснения сказанного в качестве примера по­ буквенное кодирование с помощью равномерного двоичного восьми­ разрядного кода [37]. Каждая буква русского алфавита и араб­ ская цифра в этом случае представляется восьмиразрядным числом в двоичном коде. Структура одной ячейки памяти и, соответственно, кодовой комбинации может быть представлена таким образом:

Признак начала слова -> Контроль ->• Признак буквы -►

_> 24 -> 23 -> 22 -> 21 -> 2°

Единица в крайней позиции слева характеризует начало фазы или заглавную букву в обычном написании. В следующую разряд­ ную позицию записывается 0 или 1 так, чтобы общее количество единиц в кодовой комбинации сохранялось четным. Это обеспечи­ вает возможность контроля и устранения ошибок. Единица в третьей разрядной позиции является признаком буквы, а нуль — признаком цифры или знака препинания. Пятиразрядное число (4—8-й разряды) соответствует порядковому номеру буквы или од­ ного символа. Ниже приводятся примеры кодовых комбинаций от­ дельных букв и цифр.

в00100010

г 01100011 9 00001010

я00111111

Длина кода любого сообщения, состоящего из k символов (букв, цифр), в данном случае равна I = 8k.

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

39

Равномерные коды удобны простотой декодирования, поскольку нет необходимости в использовании разделительных знаков. Однако при использовании равномерных кодов не удается использовать априорную информацию о статистических характеристиках множе­ ства элементов информации. Учитывая статистические свойства кодируемого множества элементов информации, можно уменьшить (решить задачу минимизации) среднее число двоичных символов, требующихся для выражения одного элемента информации или, точнее, одного символа исходного алфавита, что обеспечивает умень­ шение (минимизацию) необходимого объема памяти. Коды, в ко­ торых кодовые комбинации, выражающие символы исходного ал­ фавита, имеют различную длину, носят название неравномерных. Очевидно, что символам, характеризующимся малой вероятностью появления, целесообразно ставить в соответствие более длинные кодовые комбинации, а символам с большой вероятностью — ко­ роткие. Доказано, что сообщения, составленные из символов не­ которого алфавита, можно закодировать так, что среднее число двоичных символов, выражающих символы исходного алфавита, будет сколь угодно близко к энтропии сообщений, но не меньше.

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

Разработкой эффективных кодов применительно к различным задачам обработки информации занималось большое число специа­ листов. Широко используются эффективные коды Шеннона—Фано и Хаффмена. Алгоритмы получения этих кодов неоднократно из­ лагались (см., например, [26]), и мы их приводить не будем. Отме­ тим, однако, что принцип неравномерного кодирования требует рассмотрения одного важного аспекта, связанного с декодирова­ нием. Именно, должна быть решена проблема разделения кодовых комбинаций, соответствующих символам исходного алфавита, по­ скольку использование разделительных знаков ведет, по существу, к потере эффекта устранения избыточности.

Указанная проблема решается с помощью такого построения эффективных кодов, когда ни одна кодовая комбинация не совпа­ дает с началом более длинной комбинации. Подобные коды назы­ ваются префиксными. К их числу относятся и упомянутые коды Шеннона—Фано и Хаффмена.

Изложенное позволяет составить лишь самое общее представ­ ление о принципах формализации информации в целях обеспечения

40