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

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

Если А = {a₁, …, a_m} единичные элементы первичного кода, а В – проверочный элемент, то для обеспечения четного числа единиц необходимо, чтобы

b = a₁ Å a₂ Å … Å a_m,

или

a₁ Å a₂ Å … Å a_m Å b = 0,

где Å – сумма по модулю два.

Например для m=4 код с проверкой на четность будет иметь вид:

Такой код имеет d₀=2 и значит, он не может исправить ни одной ошибки. Такой код может обнаружить одну ошибку.

К простейшим помехоустойчивым линейным блочным кодам относится также код Хэмминга, позволяющий исправить одну ошибку и имеющий d₀=3. Этот код строится следующим образом (для примера рассмотрим код (7,4)). К 4-м информационным битам а₁а₂а₃а₄ добавляем три проверочных бита b₁b₂b₃, задавая их равенствами вида:

a₁ Å a₂ Å a₃ = b₁,

a₂ Å a₃ Å a₄ = b₂,

a₁ Å a₂ Å a₄ = b₃.

(при формировании этих правил каждый информационный элемент а_i (i=1,2,3,4) должен участвовать как минимум в (r-1) проверках на четность из общего их числа r).

Если будут выполняться эти правила, то это будет свидетельствовать об отсутствии ошибки. Невыполнение первого и третьего равенства свидетельствует об ошибочном приёме а₁, первого и второго - об ошибке а₃,первого, второго и третьего - об ошибке а₂, второго и третьего - об ошибке а₄. Представленное выше правило формирования проверочных элементов b₁b₂b₃ кода Хэмминга позволяет путём проверки на чётность каждой кодовой комбинации определить порядковый номер искажённого элемента. Результат проверки на чётность удобно представить r=3 разрядным проверочным двоичным числом, называемым синдромом ошибки (S₁,S₂,S₃):

s₁ = a₁ Å a₂ Å a₃ Å b₁,

s₂ = a₂ Å a₃ Å a₄ Å b₂,

s₃ = a₁ Å a₂ Å a₄ Å b₃.

Имеется всего восемь возможных синдромов ошибки: один – для случая отсутствия ошибки s=(0,0,0) и семь для каждой из ошибок (по числу позиций кода n=7). Каждая из ошибок имеет свой единственный синдром. По этому синдрому можно обнаружить ошибку и указать ее позицию: s₁s₂s₃: 000, 001, 010, 011, 100, 101, 110, 111.

Пример:

Первичный код а = (а₁а₂а₃а₄) = 0001, тогда

b₁ = a₁ Å a₂ Å a₃ = 0,

b₂ = a₂ Å a₃ Å a₄ = 1,

b₃ = a₁ Å a₂ Å a₄ = 1.

Отсюда код Хэмминга

а₁а₂а₃а₄b₁b₂b₃ = 0001011.

Этот код передается по каналу и происходит искажение одного (пусть а₂ символа).

.

Вычисляем синдром s= s₁s₂s₃.

,

,

.

Синдромом 111 можно закодировать ошибку а₂. Нетрудно видеть, что если код Хэмминга принят правильно, то синдром s=000, т.е. отсутствуют ошибки.

Если бы ошибка была в а₄, то синдром s=011. Схемная реализация кодеров и декодеров линейного блочного кода Хэмминга показана на рисунке 1.22.

Рис.1.22.

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

Последовательность кодовых комбинаций первичного m разрядного кода сообщения можно записать в виде матрицы

.

Чтобы не записывать все кодовые комбинации этой матрицы можно записать единичную матрицу размером m´m.

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

.

Вообще N_p = 2^m и уменьшение на единицу связано с отсутствием комбинации 000…0.

Для задания избыточного кода необходимо построить образующую матрицу M_n,m, левая часть которой есть единичная матрица I_m первичного кода, а правая R_r,m – матрица проверочных элементов. Размерность такой матрицы n´m.

.

Теперь на основе образующей матрицы М можно построить проверочную матрицу Н размерностью n´r, левая часть которой это транспонированная матрица проверочных элементов, а правая – единичная матрица

.

Единицы в строках матрицы Н будут стоять на позициях элементов, участвующих в проверке на четность при формировании соответствующих b_i (i = 1, 2, …, r). Таким образом, если задана образующая матрица М, то построив по ней проверочную матрицу, можно найти правила формирования проверочных групп элементов. Такой матричных подход удобен при построении линейных блочных кодов с большим числом разрядов m и r.