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

 

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

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

r = n - k. (4.2)

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

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

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

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

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

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

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

N₀ = 2ⁿ. (4.3)

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

N_k = 2^k. (4.4)

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

N_з = N₀ – N_k = 2ⁿ - 2^k, (4.5)

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

N₀ /N_k = 2ⁿ /2^k = 2^n-k = 2^r, (4.6)

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

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

χ = r/n = (n-k)/n = 1 – k/n = 1 – log₂ N_k / log₂ N₀, (4.7)

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

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

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

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

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

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

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

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

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

x_i = 01011 имеет W = 3, x_j = 10010 имеет W = 2.

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

x_i x_j = 11001 → d(x_j, x_j) = 3. (4.10)

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

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

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

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

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

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

d_mln ≥ g₀ + 1. (4.11)

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

g₀ ≤ d_min – 1. (4.12)

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

d_min ≥ 2 ∙ g_u + 1. (4.13)

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

g_u ≤ (d_min – 1)/2. (4.14)

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

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

, (4.15)

^{где ;}

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

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

(4.16)

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

^{. (4.17)}

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

^{. (4.18)}

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

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

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

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

или

r ≥ 2 ∙ (d_min - 1) – log₂ d_min, (4.20)

при n ≥ 2 ∙ d_min – 1.

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

^{, (4.21)}

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

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

^{. (4.22)}

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

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

^{. (4.23)}

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

r ≥ log ₂ (n + 1 ) для d_min = 3;

r ≥ log ₂ ( 2 ∙ n) для d_min = 4.

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

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

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