Кодирование сообщений. 
Электроэнергетика: информационное обеспечение систем управления

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

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

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

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

Пусть имеется N возможных равновероятных состояний системы, причем до получения сообщения неизвестно, в каком из них она находится, т. е. состояние системы неопределенно. При этом чем больше N, тем больше и неопределенность. Действительно, например при N=2 система может находиться в одном из двух состояний, следовательно, неопределенность невелика: с вероятностью р = 0,5 можно утверждать, что система находится в каком-либо из двух состояний. При jV= 20 неопределенность значительно больше, так как вероятность правильно указать состояние системы составляет всего р = 1/20 = 0,05.

При поступлении сообщения о том, в каком состоянии находится система, получаемая информация полностью снимает неопределенность. Введем понятие о максимальном количестве информации / (АО, т. е. о таком количестве, которое содержится в сообщении, полностью снимающем неопределенность при N возможных состояниях системы.

Естественно принять, что количество информации / (N) тем больше, чем больше была предшествующая неопределенность, т. е. чем больше N, поскольку информация снимает эту неопределенность.

Рассмотрим два частных случая. При N = 1 нет никакой неопределенности в состоянии системы, поскольку заранее известно, что она находится в единственно возможном состоянии. Следовательно, сообщение об этом состоянии вообще не несет информации, т. е. / (1) = 0.

При N = 2 неопределенность зависит от вероятности пребывания системы в том или ином состоянии. Для начала будем считать оба состояния равновероятными. Поскольку необходимая информация может быть представлена двоичным словом, имеющим длину L = 1 и указывающим на одно из двух возможных состояний 0 или 1, то для N = 2 количество информации /(2) = 1. Это количество информации принято за единицу измерения и называется битом (от сокращения английских слов binary digit — двоичная информация, двоичный разряд), а все остальное количество I (N) выражается в виде некоторого числа таких единиц. Таким образом, бит — количество информации в сообщении, сокращающем незнание вдвое, при этом величина / (ДО в битах показывает, сколько надо задать вопросов, на которые ответ дается в виде «да» (1) или «нет» (0), чтобы однозначно определить любое из N возможных состояний. Естественно, при N > 2 количество информации больше 1.

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

Пусть некоторый объект находится в одном из 16 равновероятных состояний. Поставим в соответствие каждому состоянию определенное сообщение, так что N разных сообщений полностью описывают все возможные состояния. Обозначим эти сообщения 16 буквами: а б в г д е ж з иклмнопр При таком способе обозначения каждого сообщения требуется 16 разных букв (или каких-либо других различных символов). Разумеется, это не единственный способ записи (обозначения) сообщений. Таких способов может быть сколько угодно много. Например, эти же сообщения можно обозначить, используя всего четыре символа — цифры 1, 2, 3, 4 в виде цифровых комбинаций (последовательностей) и ни разу не повторившись:

а б… в г д е ж…з и к л м н о п р

//… 12… 13… 14… 21… 22… 23… 24… 31… 32… 33… 34… 41… 42… 43… 44

Если через h обозначить число используемых символов, то при первом способе И = 16 и слово состоит из одного символа, т. е. длина слова L_] = 1, а при втором — И = 4 и L₂ = 2. При первом способе каждый полученный символ сокращает незнание в 16 раз, так как определяет один из 16 возможных вариантов, при втором — в четыре раза.

Нетрудно видеть, что количество символов в сообщении L связано с N и И выражением N= h^L, откуда.

Величина L называется аддитивной мерой информации, или количественной мерой неопределенности Хартли — по имени американского инженера, впервые предложившего оценивать по формуле (3) степень неопределенности опыта с N различными исходами. Применительно к задаче кодирования величина L показывает, какое количество символов должно содержать слово, чтобы однозначно определить любое из N состояний. Например, для представления информации о напряжении в сети 500 кВ с точностью 0,1 кВ в десятичной системе счисления (10 различных символов) достаточна длина слова 1 = 4. Это означает, что величина U= 510,2 кВ будет представлена в квантах четырехразрядным числом 5102.

Носителем информации является совокупность различных сигналов. В азбуке Морзе, к примеру, это точка, тире, пауза. Наиболее проста в технической реализации система с двоичными сигналами (есть ток — нет тока, да — нет, 1—0). Увеличение числа разных элементарных сигналов позволяет сделать их комбинации более сжатыми, но вместе с тем усложняет и удорожает систему передачи, поэтому в технических системах используется малое число элементарных сигналов. В АСУ, базирующихся на ПВК, элементарные сигналы должны соответствовать двоичной системе счисления (0 и 1).

Допустим, что некоторый алфавит состоит из букв, цифр, символов, общее число которых равно N. Поставим важную задачу выбора системы его кодирования с тем, чтобы, во-первых, легко распознать каждую букву (каждый элемент) этого алфавита и, во-вторых, при заданной частоте двоичных сигналов иметь наибольшую скорость передачи информации. Итак, код должен обеспечить однозначное декодирование. Например, коды элементов, а — 1, б — 10, в — 101 не удовлетворяют указанному требованию, так как сообщение 101 101 не расшифровывается однозначно. Воспользовавшись принципом азбуки Морзе, можно ввести вместо паузы разграничительный признак, например 00, и тогда декодирование станет однозначным. Но это соответствует кодированию вида, а — 100, б — 1000, в — 10 100, приводящему к увеличению общего времени передачи сообщения. При этом сообщение предстанет в виде 100 010 010 100.

Существуют равномерные и неравномерные коды. В равномерном коде обозначения всех элементов алфавита имеют одно и то же число символов, т. е. вес слова кода имеют одну и ту же длину или разрядность. Например, а — 10, б — 01, в — 11. Этот способ кодирования наиболее просто реализуется в ПВК. Однозначное декодирование легко осуществляется, поскольку каждый элемент алфавита кодируется одинаковым числом символов.

Найдем соотношение между длиной L двоичного слова и количеством N кодируемых элементов алфавита. При L = 1 имеем 2 варианта — 0 и 1, т. е. можно закодировать 2 элемента алфавита, например: а -* 0, b -* 0. При L = 2 имеем 4 кодовые комбинации 00; 01; 10; 11, позволяющие закодировать 4 элемента алфавита. Нетрудно видеть, что N= 2 откуда.

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

а,…а₂…а,…а₄…а₅…а₆…а₇…а₈

001…010…011… 100… 101… 110… 111…000.

Если при этом по формуле (4) получается дробное число L, то длина слова должна быть выбрана равной ближайшему большему целому числу.

Рассмотрим русский алфавит, состоящий из 33 элементов (32, буквы без «ё» и интервал между словами как элемент алфавита). В этом случае L = log₂ 33 = 5,04. Поскольку число символов может быть только целым, то длина L равномерного кода должна равняться шести.

В вычислительной технике применяют равномерные коды длиной в 8 бит. Кодовая комбинация в 8 битов называется байтом; 1 байт достаточен для кодирования алфавита из 256 элементов.

Несмотря на удобство технической реализации равномерного кода, в некоторых случаях от него приходится отказываться, так как он не всегда может обеспечить достаточную плотность информации во времени при передаче сообщений по каналу связи. К таким случаям, когда равномерный код становится неэффективным, можно отнести следующие: 1) (V * 2^к, где к — целое число. Например, в алфавите из 32 элементов код имеет длину L = 5, однако уже в алфавите из 33 элементов код имеет длину L = 6, хотя для определения одного элемента алфавита из 33 элементов достаточно 5,04 бита информации; 2) N = 2*, но вероятность появления отдельных элементов алфавита в тексте различна. В этом случае кодирование наиболее вероятных элементов алфавита осуществляется короткими кодовыми комбинациями, а менее вероятных — более длинными. Среднестатистическая длина кодовой комбинации может при этом уменьшаться.

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

Элемент…Пробел…О…Е…А…И…Н …Ф…Э Вероятность…0,146… 0,094… 0,071… 0,069… 0,064… 0,057 …0,003 … 0,002.

Наиболее вероятным элементам присвоим самые короткие кодовые комбинации. Поэтому предварительно элементы алфавита ранжируются в порядке убывания их вероятностей (см. пример алфавита из пяти элементов в табл. 2).

Поскольку при составлении таблицы кодов необходимо обеспечить однозначное декодирование без применения разделительных сигналов, то ни одно кодовое обозначение не должно совпадать с началом другого более длинного кодового обозначения. Например, если 101 — обозначение какого-либо элемента алфавита, то не могут встречаться коды 1,10, 10 110 и т. д. для других элементов.

Связь между вероятностями сообщений (появления того или иного элемента алфавита) и среднестатистической длиной двоичного слова выражается по формуле.

где /, — длина кодовой комбинации /'-го элемента.

Неравномерное кодирование преследует цель уменьшить среднестатистическую длину слова Т_ср. Чем меньше L_cp, тем лучше система кодирования.

Рассмотрим кодирование для алфавита из пяти элементов с учетом требования различимости по началу (табл. I). Для предложенного примера неравномерное кодирование в виде «пирамиды» с минимальной длиной L_min = 1 и максимальной L_mm = 5 обеспечивает среднестатистическую длину слова Д-р = 2,3 вместо длины слова 3 в равномерном коде.

Таблица 1.

Сравнение различных систем кодировки.