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

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

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

Рассмотрим простейший случай сообщений, записанных при помощи некоторых п «букв», частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р1, р2, … …, рп, где, разумеется, р1 + р2 + … + рп = 1, при котором вероятность pi проявления i-й буквы на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы. Однако строгий учет взаимной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты.

Мы будем пока рассматривать двоичные коды; обобщение полученных при этом результатов на коды, использующие произвольное число т элементарных сигналов, является, как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющих отдельное кодовое обозначение - последовательность цифр 0 и 1 - каждой «букве» сообщения. Каждому двоичному коду для п-буквенного алфавита может быть сопоставлен некоторый метод отгадывания некоторого загаданного числа х, не превосходящего п, при помощи вопросов, на которые можно ответить лишь «да» (1) или «нет» (0), что и приводит нас к двоичному коду. При заданных вероятностях р1, р2, … …, рп отдельных букв передача многобуквенного сообщения наиболее экономный код будет тот, для которого при этих именно вероятностях п значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и 1 или элементарных сигналов) оказывается наименьшим.

Прежде всего, среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p1 log p1 - p2 log p2 - … - pn log pn - энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия

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

Если вероятности р1, р2, … …, рп не все равны между собой, то Н < log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв.

2.2 Классификация назначения и способы представления кодов

Коды можно классифицировать по различным признакам:

• По основанию (количеству символов в алфавите): бинарные (двоичные m=2) и не бинарные (m № 2).
• По длине кодовых комбинаций (слов): равномерные, если все кодовые комбинации имеют одинаковую длину и неравномерные, если длина кодовой комбинации не постоянна.
• По способам передачи: последовательные и параллельные; блочные - данные сначала помещаются в буфер, а потом передаются в канал и бинарные непрерывные.
• По помехоустойчивости: простые (примитивные, полные) - для передачи информации используют все возможные кодовые комбинации (без избыточности); корректирующие (помехозащищенные) - для передачи сообщений используют не все, а только часть (разрешенных) кодовых комбинаций.

В зависимости от назначения и применения условно можно выделить следующие типы кодов:

Внутренние коды — это коды, используемые внутри устройств. Это машинные коды, а также коды, базирующиеся на использовании позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Наиболее распространенным кодом в ЭВМ является двоичный код, который позволяет просто реализовать аппаратное устройства для хранения, обработки и передачи данных в двоичном коде. Он обеспечивает высокую надежность устройств и простоту выполнения операций над данными в двоичном коде. Двоичные данные, объединенные в группы по 4, образуют шестнадцатеричный код, который хорошо согласуется с архитектурой ЭВМ, работающей с данными кратными байту (8 бит).

Коды для обмена данными и их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII — это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code). В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).

При кодировании информации для передачи по каналам связи, в том числе внутри аппаратным трактам, используются коды, обеспечивающие максимальную скорость передачи информации, за счет ее сжатия и устранения избыточности (например: коды Хаффмана и Шеннона-Фано), и коды обеспечивающие достоверность передачи данных, за счет введения избыточности в передаваемые сообщения (например: групповые коды, Хэмминга, циклические и их разновидности).

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

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

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

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

2.3 Классификация информации

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

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

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

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

Структура классификатора, как правило, должна иметь три блока:

- блок идентификации, включающий коды объектов классификации и классификационных группировок,

- блок наименований объектов и классификационных группировок на естественном языке,

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

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

3. Методы классификации информации

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

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

3.1 Иерархический метод

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

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

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