Необходимые сведения из теории кодирования

В теории информации существует раздел теория кодирования, который занимается изучением отождествления сообщений с отображающими их сигналами. Без кодирования нельзя обойтись при хранении, передаче и преобразовании какой-либо информации. Для кодирования используют набор символов, который называют алфавитом кода (а₁, а₂, … , а_m).

Каждая система кодирования имеет определенное количество символов в алфавите, которые обозначают буквой m и называют основанием кода. У двоичной системы счисления количество символов в алфавите равно двум, то есть m = 2 и представляется только числами 0 и 1. У десятичной системы счисления m = 10 и представляется символами 0, 1, 2, 3, … , 9. В других системах счисления m будет другим. С помощью символов алфавита можно закодировать практически любую величину. Например, код Морзе имеет m = 2 и состоит только с точки и тире, а русский язык имеет m = 33 и состоит из букв а, б, в, …, я.

Кодовая комбинация (иногда называют кодовым словом) – это любая упорядоченная выборка из символов (А = (а₁, а₁₂, а₁₃, …, а_n)) .

Длина кодовой комбинации – количество символов в комбинации, обозначаемое буквой n.

Код – упорядоченные кодовые комбинации (А₁, А₂, А₃, …, А_n).

Объем кода (иногда называют мощность) — количество кодовых комбинаций в коде. Максимальный объем кода равен N = mⁿ.

Представление информации кодом

Для примера рассмотрим простую систему с основанием m = 2 в виде обычного реле. Как известно, в реле может быть только два сигнала – либо контакт замкнут, либо разомкнут, соответственно передать можно только два сигнала – либо 1 когда контакт реле замкнут и на объекте присутствует напряжение, или 0, если контакт разомкнут, и напряжение на объекте нет. Ниже представлена система из шести реле и возможные кодовые комбинации при различных положениях реле:

Представленную выше систему часто используют для сигнализации. Например, нормальной работа системы будет считаться тогда, когда замкнуты все реле (комбинация 111111). Если на каком-то участке произошел сбой и контакт не был замкнут, то по сигналу легко определить на каком участке произошел сбой. Например, при комбинации 110111 понятно что проблема на участке с Р4, что значительно упрощает устранение причины отказа. Также такую информацию вполне возможно представлять в бумажном виде (распечатанном, например), на перфолентах, в цифровом виде.

Длина всех рассмотренных комбинаций в этом примере равна шести, то есть n = 6 (110111,101101 и так далее).

Также в кодовых комбинациях присутствует такое понятие как вес комбинации, который равен количеству единичных символов в коде и обозначается буквой l. Для комбинации 101101 вес l = 4, 111111 вес l = 6, 110111 вес l = 5.

Классификация кодов

Для удобства использования коды классифицируют. Рассмотрим основные классификации:

• По основанию – если m>2 коды имеют название многопозиционные, а если m = 2 – двухпозиционные;
• Учитывают и длину комбинации – при n = const равномерные, а при n ≠ const, как вы уже догадались, неравномерные;

По весу комбинации – коды на сумму сочетаний (неравновесные) при l ≠ const, а также коды на одно сочетание (равновесные) при l = const. Число комбинаций равновесного кода из n по l часто обозначают как  . Из комбинаторики следует выражение:

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

У всех комбинаций присущ одинаковый вес l = 2.

Вес определенной n членной комбинации изменяющейся от 0 до n, в общем случае можно выразить биномом Ньютона:

Общее число комбинаций для n = 5:

• По способу упорядочения – число перестановок N будет равно числу вариантов упорядочения N!, для кодов 2 из 5 N = 10, соответственно 10!:
• По нечетности или четности веса – четным называют код, если четный вес имеют все комбинации кода. Если вес нечетный, то и код нечетный:

• По числу комбинаций заданной длины – в случае содержания в коде всех возможных комбинаций определенной (заданной) длины (N = 2ⁿ), он носит название кода безызбыточности или полного кода. Если же в коде содержится только часть этих комбинаций,  то он носит название кода с избыточностью или неполного кода. Избыточность используют для придания коду особых свойств, например помехозащищенности.

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

• По кодовому расстоянию – в случае постоянного кодового расстояния (d = const) между смежными комбинациями код называют переменными.

Код 2 из 5 (1.1) – двухпеременный. Расстояние между смежными комбинациями в данном коде везде равно двум. Если те же комбинации расположить в другом порядке, то можно получить четырехпеременный код:

• По арифметическим свойствам кода – комбинации такого кода можно рассматривать как числа и проводить с ними арифметические операции свойственные обычным числам.

Если у кода отсутствуют арифметические свойства – он комбинаторный. Формирование комбинаторных кодов производят по законам теории соединений (перестановок, сочетаний, размещений), которая изучается в разделе математики называемом комбинаторикой. Из рассмотренных ранее кодов к комбинаторным относят нечетные, четные, равновесные.