2.5. Классификация помехоустойчивых кодов.

Параметры и характеристики помехоустойчивых кодов

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

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

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

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

Остановимся кратко на других классификационных особенностях помехоустойчивых кодов.

Помехоустойчивые коды делятся на блочные и непрерывные.

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

Непрерывные или рекуррентные коды образуют последовательность символов, не разделяемую на отдельные кодовые комбинации. Кодирование и декодирование непрерывно совершаются над последовательностью символов без деления их на блоки. Формирование проверочных символов ведётся по рекуррентным (возвратным) правилам, поэтому непрерывные коды часто называют рекуррентными или цепными.

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

Блочные коды делятся на равномерные и неравномерные. В равномерных кодах, в отличие от неравномерных, все кодовые комбинации содержат одинаковое число символов (разрядов) – n. Равномерные коды в основном и применяются для передачи и хранения данных в АСОИиУ.

Почти все блочные коды принадлежат к разделимым кодам, в которых n – разрядные кодовые комбинации состоят из двух частей: информационной и проверочной. Их символы всегда занимают одни и те же позиции, т.е. располагаются в определённых (фиксированных) разрядах. Разновидностью разделимых кодов являются систематические коды, в которых первые m символов кодовых комбинаций являются информационными, а за ними располагаются k=(n–m) проверочных символов. Разделимые коды получили условное обозначение – (n, m) – коды.

В неразделимых кодах деление на информационные и проверочные символы отсутствует. К таким кодам относятся, в частности, равновесные коды, например, код «2 из 5» рассмотренный в Примере 2.3.

Линейные коды образуют наиболее обширную группу (n, m)– разделимых кодов. Особенностью этих кодов является то, что проверочные (контрольные) символы образуются с помощью определенных линейных операций над информационными. Кроме того, любая разрешённая кодовая комбинация может быть получена в результате линейной операции над набором q линейно независимых кодовых комбинаций. В частности, суммирование по модулю 2 двух и более разрешённых комбинаций также дает разрешённую кодовую комбинацию. Поскольку теоретической основой получения таких комбинаций является математический аппарат линейной алгебры, то коды и называют линейными. Использование для формирования и анализа кодов аппарата линейной алгебры, в которой важное значение имеет понятие "группа", породило и другое название для этих кодов – групповые.

Линейные (групповые) получили наибольшее применение в системах передачи и хранения дискретной информации.

Нелинейные коды указанными выше свойствами не обладают и применяются значительно реже в специальных случаях. Нелинейными, в частности, являются уже упоминавшиеся неразделимые равновесные коды (Пример 2.3). Эти коды обычно используются в несимметричных каналах, в которых вероятность ошибки типа переход (конверсия) 1 → 0 значительно больше вероятности перехода 0 → 1 или наоборот. В таких каналах очень маловероятно, чтобы в одном блоке символов были переходы обоих типов и поэтому почти все ошибки приводят к изменению числа единичных символов в блоке, и, следовательно, обнаруживаются.

К числу основных параметров помехоустойчивых кодов относятся следующие:

1) m – число информационных символов (разрядов) кодовой комбинации,

2) k – число проверочных (контрольных) символов кодовой комбинации,

3) n=m+k – общее число символов (разрядов) кодовой комбинации,

4) R – избыточность кода,

5) M – мощность кода,

6) w – вес кодовой комбинации,

7) d – кратность ошибки,

8) D – кодовое расстояние,

9) D_min – минимальное кодовое расстояние.

Приведем краткие смысловые пояснения параметров 4–9, что касается параметров 1–3, то они, видимо, в этом не нуждаются.

Избыточность помехоустойчивого кода оценивается коэффициентом избыточности:

. (2.6)

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

Мощность кода М – это число разрешенных кодовых комбинаций, которая при m информационных разрядах в кодовых комбинациях определяется как . Очевидно, что общее число кодовых комбинаций N, мощность кода М и число запрещенных кодовых комбинаций связаны соотношением:

,

а отношение числа разрешенных (рабочих) комбинаций к общему числу кодовых комбинаций составляет:

. (2.7)

Вес кодовой комбинации w – это число единичных символов, содержащихся в данной кодовой комбинации. Например, для кодовой комбинации ее вес w(A_i)=3, а для комбинации A_j=0100– w(A_j)=1.

Под кратностью ошибок d понимают число искаженных разрядов (символов) кодовой комбинации. В двоичных каналах ошибки представляют собой переходы (или конверсии) верного символа «1» в «0» (10) или наоборот – 01. Если ошибка пришлась всего на один разряд кодовой комбинации, т.е. d=1, то ее называют одинарной, если же ошибки пришлись на два или более разрядов кодовой комбинации, т.е. , ошибки именуются многократными.

Кодовым расстоянием D между двумя кодовыми комбинациями называется количество разрядов, которыми эти комбинации отличаются. Например, для кодовых комбинаций А₁=01011 и А₂=10010 кодовое расстояние D(А₁, А₂)=3, так как А₁ и А₂ отличаются символами в трех разрядах – первом, втором, и пятом. Для нахождения кодового расстояния между кодовыми комбинациями А_i и А_j достаточно сложить по модулю 2 эти комбинации. Вес w полученной суммы (число единичных символов в сумме) равен кодовому расстоянию:

D(А_i, А_j)=w(). (2.8)

Для рассмотренного выше примера имеем:

Отметим, что кодовое расстояние между некоторой кодовой комбинацией А_i и комбинацией «все нули» равно весу комбинации А_i – то есть w(А_i).

Кодовые расстояния между различными комбинациями некоторого конкретного кода могут существенно отличаться. Так, в частности, для m – разрядного простого кода D для различных пар комбинаций изменяется в диапазоне от 1 до m.

Минимальным кодовым расстоянием D_min (или расстоянием Хэмминга) называется минимальное из кодовых расстояний между любыми двумя разрешенными комбинациями кода, т.е.

D_min=min. (2.9)

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

Для кода, содержащего в числе разрешенных кодовую комбинацию «все нули», при учете (2.8) и (2.9) D_min равно наименьшему из весов кодовых слов:

. (2.10)

Минимальное кодовое расстояние является основным параметром, характеризующим обнаруживающие и корректирующие способности кода.

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

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

В общем случае, когда требуется обнаруживать ошибки произвольной кратности d₀ достаточно, чтобы минимальное кодовое расстояние кода удовлетворяло условию:

D_min d₀ + 1. (2.11)

В этом случае никакие d₀ ошибок не могут перевести одну разрешённую кодовую комбинацию в другую разрешённую. Таким образом, ус­ловие обнаружения ошибок кратности d₀ можно записать в виде:

d₀ D_min – 1. (2.12)

Следует отметить, что соотношение (2.12) устанавливает лишь гарантирован­ное минимальное число обнаруживаемых ошибок при за­данном D_min и не ограничивает возможность обнаружения некоторых ошибок большей кратности. Например, код с проверкой на чётность (как и код с проверкой на нечетность) с D_min = 2 позво­ляет обнаруживать не только одинарные ошибки, но и ошибки любой нечётной кратности в пределах d₀ < n.

Для возможности исправления ошибок кратности d_u и менее, необходимо, чтобы искаженная d_u ошибками кодовая комбинация не только не совпадала с какой-либо разрешенной, но и оставалась ближе по кодовому расстоянию к истинной, чем к любой другой разрешенной комбинации. От истинной комбинации искаженная отстоит на расстояние d_u, а от любой другой разрешенной комбинации она должна отстоять не менее чем на d_u+1. Следовательно, если все разрешенные кодовые комбинации разнести между собой на кодовое расстояние

(2.13)

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

Из (2.11) и (2.3) следует, что если код способен исправлять ошибки кратности d_u, то кратность ошибок, которые он может обнаружить d_o=2d_u.

Если потребовать, чтобы код исправлял d_u и одновременно обнаруживал ошибок, то

(2.14)

При построении корректирующего кода одним из основных вопросов является определение его избыточности, т.е. числа проверочных символов k, обеспечивающих требуемое значение минимального кодового расстояния d при фиксированном значении числа информационных символов m. Аналитическое выражение для зависимости k=n–m=f(m,d) до настоящего времени не получено. Существуют лишь крайние оценки этой зависимости, в пределах которых находится искомая величина k. В качестве нижней оценки (границы) используется граница Хэмминга:

, (2.15)

где – кратность ошибок, исправляемых кодом,

n=m+k – общее число символов в кодовом слове.

Верхняя оценка избыточности корректирующего кода определяется границей Варшамова-Гильберта:

. (2.16)