2.8. Условия построения кодов с заданной исправляющей способностью, показатели качества корректирующих кодов

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

Пусть известен объем алфавита источника N. Необходимое количество информационных символов k = log₂ N.

Пусть также известно полное число ошибок N_e, которое необходимо исправить.

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

Полное число ошибочных комбинаций, подлежащих исправлению, равно N_e · 2^k = N_e · N. Так как количество ошибочных комбинаций равно N₀ – N, то код обеспечивает исправление не более N₀ – N комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде

N·N_e £ N₀ – N,

откуда получим

N₀ ³ (1 + N_e) ·N (2.6)

или

N £ 2 ^m/ (1+ N_e). (2.7)

Выражение (2.7) определяет условие для выбора значности кода m.

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

В этом случае зависимость (2.7) примет вид

N = 2 ^k £ 2 ^m/ (1+ m). (2.8)

При выполнении условия (2.8) код должен также удовлетворять условию

d_мин ³ 3. (2.9)

Любой корректирующий код характеризуется рядом показателей: длиной m, основанием B, количеством информационных символов k или избыточных символов r = m – k, полным числом всех возможных кодовых комбинаций
N₀ = B^m (для двоичных кодов N₀ = 2^m), числом разрешенных кодовых комбинаций (мощностью кода) N, весом кодовой комбинации W, весом вектора ошибки W_e, кодовым расстоянием d и пр.

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

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

Для оценки избыточности кода пользуются понятием коэффициента избыточности

где r – количество избыточных символов в кодовой комбинации.

2.9. Систематические корректирующие коды

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

1. В число исходных комбинаций не должна входить нулевая.

2. Кодовое расстояние между любыми парами исходных комбинаций не должно быть меньше d_мин.

3. Каждая исходная комбинация, как и любая ненулевая разрешенная комбинация, должна содержать количество единиц не менее d_мин.

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

Исходные комбинации могут быть получены из матрицы, состоящей из k строк и m столбцов:

. (2.11 )

Здесь символы первых k столбцов являются информационными и последних r столбцов – проверочными. Матрицу M_m,k называют производящей. Производящая матрица M_m,k может быть представлена двумя подматрицами – информационной U_k и проверочной Hp:

, (2.12)

где

.

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

.

При этом проверочная подматрица Н_p должна строиться с соблюдением следующих условий:

1. Количество единиц в строке должно быть не менее (d_мин – 1).

2. Сумма по модулю два двух любых строк должна содержать не менее (d_мин – 2) единиц.

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

.

Затем к ней справа приписывается единичная матрица.

. (2.13)

Алгоритм определения проверочных символов по информационным с помощью матрицы (2.13) следующий. Позиции, занимаемые единицами в первой строке подматрицы H ^I, определяют информационные разряды, которые должны участвовать в формировании первого проверочного разряда кодовой комбинации. Позиции единиц во второй строке подматрицы H ^I определяют информационные разряды, участвующие в формировании второго проверочного разряда и т. д. Пусть, например, производящая матрица кода (7,4) имеет вид

.

Проверочная подматрица:

.

Транспонированная подматрица по отношению к Н_p:

.

Приписывая справа единичную матрицу, получим проверочную матрицу

.

Кодовые комбинации должны содержать r = m – k =7 – 4 = 3 проверочных символа. Подматрица H ^I указывает на то, что проверочные символы должны определяться равенствами:

Тогда для сообщения, представляемого, например, кодовой комбинацией 0011 (a₁ = 1, a₂ = 1, a₃ = 0, a₄ = 0), проверочные символы будут:

Следовательно, полная кодовая комбинация будет иметь вид 0011011.

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

Состав контрольных равенств легко определяется из проверочной матрицы Н. В состав первого контрольного равенства должны входить символы, позиции которых заняты единицами в первой строке матрицы Н. В состав второго контрольного равенства должны входить символы, позиции которых заняты единицами во второй строке матрицы H, и т.д.

Так, для рассмотренного примера с кодом (7,4) эти равенства будут иметь вид:

В результате r таких проверок будет получено r-разрядное двоичное число (синдром), которое будет равно нулю при отсутствии ошибок и отлично от нуля в случае наличия ошибок.

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

Пусть в рассматриваемом примере с кодом (7,4) произошла ошибка в первом разряде кодовой комбинации (искажен символ a₁). Тогда проверочные операции дадут следующий результат:

S₁ = 0, S₂ = 1; S₃ = 0.

Таким образом, при ошибке в первом разряде кодовой комбинации будет получен синдром 010. В случае ошибки во втором разряде будет получен синдром 101 и т.д.

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