Основные характеристики корректирующих кодов

 

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

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

r = n - k. (4.2)

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

- число разрешённых и запрещённых кодовых комбинаций (N0, Nk);

- избыточность кода (χ);

- минимальное кодовое расстояние (dmin);

- число обнаруживаемых или исправляемых ошибок (g0);

- корректирующие возможности кодов.

Для блочных двоичных кодов, с числом символов в блоках равным n, общее число возможных кодовых комбинаций определяется выражением

N0 = 2n. (4.3)

Число разрешённых кодовых комбинаций при наличии k информационных разрядов в первичном коде равно

Nk = 2k. (4.4)

Очевидно, что число запрещённых комбинаций равно:

Nз = N0 – Nk = 2n - 2k, (4.5)

а с учётом (4.2) отношение будет:

N0 /Nk = 2n /2k = 2n-k = 2r, (4.6)

где r – число избыточных (проверочных) разрядов в блочном коде.

Избыточностью корректирующего кода называют величину

χ = r/n = (n-k)/n = 1 – k/n = 1 – log2 Nk / log2 N0, (4.7)

откуда следует

Bk = k/n = 1 – χ. (4.8)

Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют информационные символы. В теории кодирования величину Bk называют относительной скоростью кода. Если производительность источника информации равна Н символов в секунду, то скорость передачи после кодирования этой информации окажется равной

B = H∙(k/n), (4.9)

поскольку в закодированной последовательности из каждых n символов только k символов являются информационными.

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

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

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

Количество разрядов (символов), которыми отличаются две кодовые комбинации, можно принять за кодовое расстояние между ними. Для определения этого расстояния нужно сложить две кодовые комбинации по модулю 2 и подсчитать число единиц в полученной сумме. Например, две кодовые комбинации xi = 01011 и xj = 10010 имеют расстояние d(xi, xj), равное 3, так как

xi = 01011 имеет W = 3, xj = 10010 имеет W = 2.

Заметим, что кодовое расстояние d(xj, x0) между комбинацией xj и нулевой (х0 = 00…0) называют весом W комбинации xi, т. е. вес xi равен числу «1» в ней.

xi xj = 11001 → d(xj, xj) = 3. (4.10)

Под операцией « » понимается сложение по модулю 2).

Расстояние между различными комбинациями некоторого конкретного кода могут существенно отличаться. Так, в частности, в безызбыточном первичном натуральном коде (n = k) это расстояние для различных комбинаций может изменяться от единицы до величины n, равной значности кода. Особую важность для характеристики корректирующих свойств кода имеет минимальное кодовое расстояние dmin, определяемое при попарном сравнении всех кодовых комбинаций, которое называют расстоянием Хемминга.

В безызбыточном коде все комбинации являются разрешёнными, и, следовательно, его минимальное кодовое расстояние равно единице – dmin = 1. Поэтому достаточно исказиться одному символу, чтобы вместо переданной комбинации была принята другая разрешённая комбинация. Чтобы код обладал корректирующими свойствами, необходимо ввести в него некоторую избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешёнными комбинациями не менее двух – dmin ≥ 2.

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

При применении двоичных кодов учитывают только дискретные искажения, при которых единица переходит в нуль (1 → 0) или нуль переходит в единицу (0 → 1). Переход 1→ 0 или 0 → 1 только в одном элементе кодовой комбинации называют единичной ошибкой (единичным искажением). В общем случае, под кратностью ошибки подразумевают число позиций кодовой комбинации, на которых под действием помехи одни символы оказались заменёнными на другие. Возможны двукратные (g = 2) и многократные (g > 2) искажения элементов в кодовой комбинации в пределах 0 ≤ g ≤ n.

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

dmln ≥ g0 + 1. (4.11)

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

g0 ≤ dmin1. (4.12)

Чтобы можно было исправить все ошибки кратностью gi и менее, необходимо иметь минимальное расстояние, удовлетворяющее условию:

dmin ≥ 2 ∙ gu + 1. (4.13)

В этом случае любая кодовая комбинация с числом ошибок gu отличается от каждой разрешённой комбинации не менее чем в gu + 1 позициях. Если условие (4.13) не выполнено, возможен случай, когда ошибки кратности g исказят переданную комбинацию так, что она станет ближе к одной из разрешённых комбинаций, чем к переданной или даже перейдёт в другую разрешённую комбинацию. В соответствии с этим, условие исправления всех ошибок кратностью не более gu можно записать в виде:

gu ≤ (dmin – 1)/2. (4.14)

Из (4.11) и (4.13) следует, что если код исправляет все ошибки кратностью gu, то число ошибок, которые он может обнаружить, равно g0 = 2 ∙ gu. Следует отметить, что соотношения (4.11) и (4.13) устанавливают лишь гарантированное минимальное число обнаруживаемых или исправляемых ошибок при заданном dmin и не ограничивают возможность обнаружения ошибок большей кратности. Например, простейший код с проверкой на чётность с dmin = 2 позволяет обнаруживать не только одиночные ошибки, но и любое нечётное число ошибок в пределах g0 < n.

При независимых ошибках полная вероятность ошибки кратности g, учитывающая все сочетания ошибочных символов определяется выражением [8]:

, (4.15)

где ;

– вероятность искажения одного символа.

Отсюда вероятность отсутствия ошибок в кодовой комбинации, т. е. вероятность правильного приема равна

(4.16)

и вероятность правильного корректирования ошибок равна

. (4.17)

Здесь суммирование производится по всем значениям кратности ошибок g, которые обнаруживаются и исправляются. Таким образом, вероятность некорректируемых ошибок будет равна

. (4.18)

Анализ формулы (4.18) показывает, что при малой величине P0 и небольших значениях n, наиболее вероятны ошибки малой кратности, которые необходимо корректировать в первую очередь.

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

Так, граница Плоткина даёт верхнюю границу кодового расстояния dmin при заданном числе разрядов n в кодовой комбинации и числе информационных разрядов k, и для двоичных кодов:

dmin ≤ (n ∙2 ∙ k – 1 ) ∕ (2 ∙ k -1) (4.19)

или

r ≥ 2 ∙ (dmin - 1) – log2 dmin, (4.20)

при n ≥ 2 ∙ dmin – 1.

Верхняя граница Хемминга устанавливает максимально возможное число разрешённых кодовых комбинаций (2k) любого помехоустойчивого кода при заданных значениях n и dmin:

, (4.21)

где – число сочетаний из n элементов по i элементам.

Отсюда можно получить выражение для оценки числа проверочных символов:

. (4.22)

Для значений (dmin / n) ≤ 0,3 разница между границей Хемминга и границей Плоткина сравнительно невелика.

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

. (4.23)

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

r ≥ log2 (n + 1) для dmin = 3;

r ≥ log2 (2 ∙ n) для dmin = 4.

Блочные коды с dmin = 3 и 4 в литературе обычно называют кодами Хемминга.

Все приведённые выше оценки дают представление о верхней границе числа dmin при фиксированных значениях n и k или оценку снизу числа проверочных символов r при заданных k и dmin.

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