1.3.3. Основные характеристики кодов, выбор оптимальной значности кода

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

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

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

а) каждому сообщению поставить в соответствие определенный уровень напряжения, при этом основание кода т = 1000, а длина кодовой комбинации (слова) принимает минимальное значение n=1;

б) можно воспользоваться двоичным (бинарным) сигналом с т=2, но тогда потребуется комбинация длины n = 10 (2¹⁰ = 1024), так что некоторые комбинации здесь не использованы. Возможны и промежуточные варианты. Поэтому целесообразно поставить вопрос об определении оптимальной пары значений т (значности кода) и n (длины кодового слова).

В качестве критерия оптимальности примем минимум произведения числа требуемых символов (уровней) m на длину кодовой комбинации n, необходимой для представления заданного числа сообщений N. В общем случае, если значность кода m, то для передачи N сообщений, потребуется комбинация длиной n, причем должно выполняться неравенство mⁿN. Отсюда

Тогда можно записать

А указанное условие минимума принимает вид

или т = е. Как видно для задачи о передаче N сообщений, наиболее экономное представление множества сообщений соответствует m = 2, 3.

Таким образом, код с основанием m = 2 (двоичный) оказывается не только удобным вследствие легкости формирования бинарных сигналов (низкий и высокий уровень напряжения), но и одним из наиболее экономных.

Примером двоичного кода является запись натурального числа А в позиционной двоичной системе счисления, осуществляемая по следующему правилу:

Здесь символы a₁, a₂,…a_n принимают значения 0 или 1, n - число разрядов в коде. Предполагается, что символ a_n, расположенный в старшем разряде кодовой комбинации, имеет наибольший вес 2^n-1, тогда как вес символа a₁ в младшем разряде является минимальным и равен 2⁰=1.

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

Рассмотренный код относится к арифметическим кодам, на которые распространяются арифметические операции сложения, вычитания, умножения, деления.

Примером кода, отличного от арифметического, является код Грея, обладающий тем ценным свойством, что любые 2 соседние кодовые комбинации отличаются лишь значением одного разряда. Он используется при построении различных преобразователей аналог-код, что позволяет свести к ЕМР ошибку неоднозначности при считывании информации.

1.3.4. Помехозащищенное кодирование

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

К. Шеннон доказал, что если скорость передачи информации через канал с помехами не превышает его пропускной способности, то всегда можно построить такой код, при котором вероятность безошибочного декодирования будет сколь угодно близка к единице. Под пропускной способностью канала понимается максимально возможная для данного канала скорость передачи информации C [бит/c], которую находят по соотношению Хартли–Шеннона

где F_k - полоса частот канала в Гц; Р_с и P_пом — средние мощности полезного сигнала и помехи.

(Сравните пропускная способность канала в отсутствие шума, установленная законом Хартли, определяется в виде: , где N – число уровней кодирования (2 в двоичной системе)).

Идея построения корректирующих двоичных кодов предложена Р. В. Хеммингом. Для ее пояснения введем понятие кодового расстояния между двумя числами, закодированными в двоичном коде. Кодовое расстояние двух чисел A₁ и A₂ есть количество единиц в их сумме по модулю 2 (операция поразрядного исключающего ИЛИ). Попросту говоря, это количество отличающихся двоичных разрядов в указанных кодовых комбинациях.

Пусть восемь кодовых комбинаций для 3-разрядного двоичного кода являются разрешенными (допустимыми), тогда кодовое расстояние между соседними комбинациями d = 1. Например соседней кодовой комбинацией нуля (000) является восемь (100).Так как в данном случае отсутствует какой-либо признак, позволяющий судить о появлении ошибки в кодовой комбинации, то такой код не является помехозащищенным.

Допустим, что лишь четыре из восьми кодовых комбинаций считаются разрешенными, например это комбинации 001, 010, 100 и 111. Тогда кодовое расстояние d = 2, причем искажение символа в одном из разрядов приводит к получению запрещенной кодовой комбинации (000, 011, 101 или 110), что легко выявляется при проверке. Полученный таким образом двоичный код называют кодом с обнаружением одиночной ошибки. Здесь присутствует выигрыш, состоящий в том что одиночная ошибка обнаруживается, и проигрыш в том что при той же разрядности слова уменьшилось число информационных разрядов (n=2). Т.е. теперь можно закодировать лишь числа от 0 (00) до 3 (11).

Для d = 3 в качестве разрешенных кодовых комбинаций можно принять, например, 010 и 101. При этом обеспечивается возможность не только обнаружения, но и исправления одиночной ошибки. Действительно, получение запрещенной кодовой комбинации 110 указывает на наличие ошибки, для исправления которой необходимо перейти к ближайшей из разрешенных кодовых комбинаций (в данном случае — 010). Данный код позволяет обнаруживать и двойные ошибки, так как при одновременном искажении символов в двух разрядах кодовой комбинации последняя также попадает в число запрещенных за счет еще большего проигрыша в длине слова несущего полезную информацию (1 разряд).

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

Где t_обн – число обнаруживаемых ошибок; t_испр – число исправляемых ошибок. Если код позволяет только обнаруживать ошибки, не исправляя их, то d_min=t_обн+1. Для кода, исправляющего все обнаруженные ошибки, d_min=2t_испр+1.

Наиболее вероятными являются ошибки единичной кратности. Их и следует обнаруживать и исправлять в первую очередь.

Простейшим из помехозащищенных кодов является код с проверкой на четность (d = 2), который используется при вводе и хранении информации в ЭВМ (часто при записи и извлечении из ОЗУ). В данном случае к кодовой комбинации, состоящей из n информационных разрядов а_n, а_n-1, .... а₁, добавляется один дополнительный (проверочный) разряд a₀ так, что кодовая комбинация принимает вид

Значение проверочного разряда а₀ вычисляют сложением по модулю 2 значений всех информационных разрядов:

Иначе говоря, а₀ = 0, если общее количество единиц в информационных разрядах кодовой комбинации является четным числом, или а₀ = 1, если это число нечетно. Но тогда при отсутствии ошибки кодовая комбинация всегда содержит четное число единиц и, следовательно, сумма

должна принимать нулевое значение (r = 0). Если в результате проверки установлено, что контрольная сумма (1.46) принимает значение r = 1, то это указывает на наличие одиночной ошибки в принятой кодовой комбинации. Недостатком данного кода является отсутствие возможности автоматической коррекции ошибок.

Примером корректирующего кода, позволяющего обнаружить и исправить одиночную ошибку (d = 3), является код Хемминга, идея построения которого заключается в следующем. Допустим, что кодовая комбинация содержит n информационных и k проверочных разрядов, причем значение каждого проверочного разряда определяется суммированием по модулю 2 определенного числа информационных разрядов. После приема кодовой комбинации производят k проверок, заключающихся в вычислении контрольных сумм r₁, r₂, … r_k для определенных наборов значений из всех (n + k) разрядов. Если записать результаты данных проверок справа налево, то получим k-разрядное контрольное число r = (r_k, r_k-1, … r₁), которое и указывает номер искаженного разряда в двоичной системе счисления. Отсутствию ошибки в кодовой комбинации соответствует контрольное число r, составленное только из нулей.

Таблица 1.1. Результаты расчета количества контрольных разрядов в коде Хемминга

n	k	n+k	R=k/(n+k)
1	2	3	0,67
2	3	5	0,6
3	3	6	0,5
4	3	7	0,43
5	4	9	0,44
6	4	10	0,4
7	4	11	0,36
8	4	12	0,33
16	5	21	0,24

Это число должно описывать (n + k + 1) различных событий, включая отсутствие ошибки или искажение одного из (n + k) разрядов. Так как в k двоичных разрядах можно записать лишь 2^k различных контрольных чисел, то обязательным является выполнение условия

откуда можно найти требуемое значение k для заданного числа n. (см. табл. 1)

Результаты проверок r₁, r₂, … r_k в коде Хемминга вычисляются в соответствии с проверочными уравнениями (1.48).

Первое уравнение включает в себя те разряды кодовой комбинации, в номерах которых в двоичной форме записи стоит единица в младшем разряде (при 2⁰). Второе представляет собой сумму по модулю 2 всех разрядов, в двоичных номерах которых стоит единица на позиции 2¹, т. е. в предпоследнем разряде. Третье составлено как сумма по модулю 2 тех разрядов, в двоичных номерах которых имеется единица на третьем месте, считая с конца (т. е. при 2²), и т. д.

Анализ уравнений (1.48) показывает, что разряды a₁, a₂, a₄…входят только по одному разу в каждое из этих уравнений. Поэтому именно эти разряды удобно принять в качестве проверочных. Приравнивая проверочные уравнения к нулю при отсутствии ошибок, т. е. Полагая r₁=r₂=…=r_k=0, можно найти требуемые значения проверочных разрядов:

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

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

При построении циклического кода удобно представить кодовую комбинацию в виде полинома:

,

где х — фиктивная переменная, заменяющая собой число 2 — основание системы счисления. Так, например, от комбинации А = (1011)₂ = 12³+02² + 12¹ + 12⁰ можно перейти к полиному А (х) = 1х³ + 0х² + 1х¹ + 1х⁰ = х³ + х + 1. Над полиномами можно производить любые алгебраические операции, как и над двоичными числами. Исключение составляет сложение, которое должно производиться только по модулю 2: 0хⁱ + 0хⁱ = 0хⁱ; 0хⁱ + 1хⁱ = 1хⁱ; 1хⁱ + 0хⁱ = 1хⁱ; 1хⁱ + 1хⁱ = 0хⁱ. Как следствие, –1хⁱ = 1хⁱ, т. е. вычитание заменяется сложением.

Циклические коды образуются путем умножения комбинации исходного кода, выраженной в виде полинома А(х) степени (n – 1), на образующий полином G(x) степени k (в соответствии с указанным правилом, разрешенными считаются лишь те кодовые комбинации, которые делятся без остатка на полином G(x)). В качестве образующего полинома G(x) обычно выбирают какой-либо неприводимый полином от аргумента х, т. е. такой, который не может быть представлен в виде произведения сомножителей — полиномов с вещественными коэффициентами. К неприводимым полиномам относятся: G(х) = х + 1; G (х) = х² + х + 1; G(х) = х³ + х² + 1; G(х) = х³ + х + 1; G (х) = х⁴ + х³ + 1 и т. д. Степень k образующего полинома G(x) задается исходя из требования к корректирующей способности кода. Так, если циклический код должен обеспечивать обнаружение и исправление одиночной ошибки, то для определения значения k можно воспользоваться условием (1.47).

Характерное свойство циклических кодов — при циклической перестановке символов кодовой комбинации получается другая комбинация этого же кода. Например, если A₁ = (1011)₂ - комбинация циклического кода, то A₂ = (0111)₂ — также комбинация этого кода.

Пример. Для кодовой комбинации А = (1001); имеем A(x)=x³+1. Так как п = 4, то для кода с обнаружением и исправлением одиночной ошибки, с учетом (1.47), принимаем k = 3. Выбираем G (х) = х³ + х² + 1. Перемножая полиномы А (х) и G (х), получаем F (х) = А (х) G (х) = х⁶ + х⁵ + х² + 1, т. е. комбинация циклического кода принимает вид F = (1100101)₂.

Декодирование циклического кода сводится к делению кодовых комбинаций на образующий полином G(x). Если полученный при этом остаток R (х) отличен от нуля, то это указывает на наличие ошибки, которая должна выявляться с помощью специальной логической схемы.