Коды Хэмминга

Общие сведения

К кодам Хэмминга относится семейство групповых систематических линейных блочных помехоустойчивых кодов с параметрами (n; k). Число проверочных символов r = n-k. Для этих кодов выполняется равенство 2^r= 2^n-k=1+n или n=2^n-k-1= 2^r-1. Кодами Хэмминга являются коды (3;1), (7;4),(15;11), (31;26). Кодовое расстояние кодов Хэмминга d₀=3 и, соответственно, они могут гарантированно обнаруживать две ошибки и исправлять одну ошибку. Для построения кода Хэмминга нет необходимости задавать все 2^k разрешенные кодовые комбинации. Достаточно выбрать определенным образом k исходных разрешенных кодовых комбинаций и затем путем их посимвольного суммирования по модулю два в различных сочетаниях получить остальные (2^k-k) разрешенные последовательности. Вышеуказанные исходные кодовые комбинации называют базисными. При их выборе должны выполняться следующие условия:

а) исходные (базисные) кодовые последовательности должны выбираться различными;

б) нулевая кодовая последовательность (состоящая из одних нулей) не должна выбираться;

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

Примечание: Линейно-независимыми являются ненулевые комбинации А₁, А₂…,А_k, если выполняется условие где с_i=0 или 1, причем хотя бы один из коэффициентов с_i≠0

г) вес (число единиц) каждой исходной кодовой последовательности должен быть не менее d₀;

д) вес проверочной части исходной кодовой последовательности должен быть не менее d₀-1;

е) расстояние Хэмминга d в любых парах исходных кодовых последовательностей должно быть не менее d₀;

ж) минимальный вес исходной кодовой последовательности должен быть равен кодовому расстоянию d₀.

Порождающая матрица

Обычно набор из k линейно независимых кодовых последовательностей, формирующих СЛБ (n; k)-код, записывают в виде матрицы, называемой производящей или порождающей (генерирующей) матрицей, обозначаемой как G_k,n. Матрица G_k,n содержит k строк и n столбцов, так как ее размерность (ранг) – (k n) определяется параметрами кода n, k и r. В общем виде порождающая матрица может быть записана так:

G_k,n = ,

где буквами а обозначены информационные символы, а буквами b – проверочные.

Для кодирования с помощью матрицы G_k,n ее приводят к каноническому приведенно-ступенчатому виду. Каноническая матрица G_k,n содержит две подматрицы: информационную − рангом (k k) и проверочную − рангом (k r). Информационную подматрицу представляют в виде единичной квадратной матрицы I_k, у которой по главной диагонали стоят единицы, а все остальные элементы − нули. Единичная матрица I_k имеет вид:

I_k = I_k,k= (10)

Используя матрицу (10), можно сформировать любую кодовую комбинацию простого (безызбыточного) k – разрядного кода. Возможное число комбинаций равно 2^k.

Для составления канонической матрицы G_k,n к информационной единичной матрице I_k приписывают справа проверочную подматрицу G^*, формируемую с учетом требований, предъявляемых к исходным базисным комбинациям помехоустойчивого кода. При этом необходимо учитывать следующие свойства СЛБК: чем больше логических «1» в приписываемых строках проверочной подматрицы, тем большей корректирующей способностью обладает разрабатываемый код и тем сложнее его реализация. В качестве примера построим каноническую порождающую матрицу для кода Хэмминга (7;4;3), в котором число информационных символов k=4, общее число символов n =7.

Информационная единичная подматрица этого кода имеет вид:

I_k= I_4,4= (11)

Допишем к каждой строке матрицы символы проверочной подматрицы, причем вес приписываемой строки должен быть не менее d₀-1=3-1=2, т.е. необходимо к каждой строке дописать по две «1». В этом случае вес каждой строки матрицы G_k,n будет равен W_стр= d₀=3. Число столбцов в матрице G_k,n окажется равным n=4+2=6, что не соответствует заданному коду, и, кроме того, расстояние Хэмминга в любых парах базисных слов d =2, что менее требуемого d₀=3. Поэтому в проверочную часть каждой строки дописываем еще один (третий) символ «0» или «1». Окончательно матрица G_k,n примет вид:

(12)

Поскольку базисные исходные комбинации могут быть выбраны произвольным образом, то можно построить множество матриц G_k,n с одним и тем же кодовым расстоянием. Так, для кода Хэмминга (7;4;3) существует 29 вариантов порождающих матриц вида (5.5). Коды, обладающие одними и теми же параметрами (n;k;d₀), но задаваемые различными порождающими матрицами, получили название эквивалентных кодов. В этих кодах различная зависимость проверочных символов от информационных.

Формирование кодовых комбинаций с использованием порождающей матрицы

Имея каноническую порождающую матрицу G_k,n и исходный информационный блок А_k из k двоичных символов, разрешенную кодовую комбинацию А можно получить путем умножения информационного блока А_k на матрицу G_k,n:

А = А_k∙ G_k,n (13)

Пример 7 Закодировать кодом Хэмминга (7;4) информационную последовательность А_k=0101 с использованием порождающей матрицы (12). Воспользуемся выражением (13):

А = А_k G=

Для нахождения значения первого (старшего) разряда в кодовой комбинации поразрядно умножаем входную информационную последовательность А_k на первый столбец матрицы G_4,7 и полученные символы суммируем по модулю два:

Полученный символ совпадает с символом первого разряда входной последовательности А_k, поскольку в G_4,7 информационная подматрица единичная. Аналогично второй, третий и четвертый символы повторяют соответствующие символы входной последовательности А_k. Поэтому достаточно рассчитать только проверочные символы кодового слова. Найдем пятый символ, для чего А_k умножим на пятый столбец матрицы (12) и полученные символы просуммируем по модулю два:

Аналогично рассчитаем шестой и седьмой символы кодового слова:

и

В итоге получаем семиразрядную кодовую последовательность, первые четыре символа которой совпадают с информационными: А=0101010.

Рассмотренный способ формирования кодовых последовательностей довольно сложен. Более простую процедуру кодирования и декодирования линейных (n; k) кодов дает применение проверочной матрицы Н_r,n.

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

Для систематического линейного блочного кода проверочную матрицу Н_r,n, содержащую r строк и n столбцов, можно построить на основе приведено-ступенчатой порождающей матрицы G_k,n путем транспонирования ее проверочной подматрицы G^* и последующего дописывания единичной проверочной подматрицы I_r. Транспонирование подматрицы G^* проводится следующим образом: каждая из строк проверочной подматрицы G^* записывается последовательно в виде соответствующего столбца проверочной матрицы: т.е. первая строка записывается в виде первого столбца, вторая строка в виде второго столбца и т.д. В результате получают проверочную подматрицу Н^* проверочной матрицы Н_r,n. Подматрица Н^* имеет ранг (r k). К ней дописывается единичная проверочная подматрица I_r с рангом (r r). В итоге проверочная матрица Н_r,n имеет ранг (r n).

Каждой порождающей матрице СЛБК соответствует своя проверочная матрица. Во всех случаях должно выполняться условие:

G H^T=0 (14)

где H^T − транспонированная проверочная матрица.

Это свойство проверочной матрицы используется при декодировании СЛБК.

Для (7;4)-кода Хэмминга, задаваемого порождающей матрицей (5.5), приведено- ступенчатая проверочная матрица имеет вид:

(15)

Формирование кодовых комбинаций с использованием проверочной матрицы

Каждая из r строк проверочной матрицы Н_r,n определяет правила формирования одного из проверочных символов разрешенной кодовой комбинации. На то, какой именно формируется символ и из какой строки подматрицы Н^* его получают, указывает единица в столбце единичной подматрицы I_r. Конкретное значение проверочного символа («0» или «1») определяется путем суммирования по модулю два тех информационных символов входной комбинации А_k, номера которых совпадают с ненулевыми (единичными) позициями соответствующей строки проверочной подматрицы Н^*. Таким образом формируются проверочные уравнения для любого конкретного СЛБК. Система проверочных уравнений для (7;4)- кода с проверочной матрицей (15) имеет вид:

(16)

Пример 8 Закодировать кодом (7;4) информационную последовательность А_k =0101, что и в примере 9, с использованием проверочной матрицы (15). Для нахождения проверочных символов воспользуемся системой проверочных уравнений (16):

В итоге получаем кодовую последовательность А=0101010, совпадающую с результатом примера 9

Проверочная матрица не только задает правила кодирования линейного кода, но и определяет схему кодирующего устройства. Электрическая структурная схема кодирующего устройства для кода, задаваемого проверочной матрицей (15), приведена на рисунке 4. Разрешенная кодовая комбинация кода Хэмминга формируется за один такт после поступления входных информационных символов.

Рисунок 4 − Электрическая структурная схема кодера линейного кода (7;4)

---

Дата добавления: 2015-08-13