Главная Обратная связь

Дисциплины:






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



Пусть x1, x2, ..., xk означают слово из k информационных битов на входе кодера, кодируемое в кодовое слово C размерности n битов:

вход кодера: X=[x1, x2, ...,xk]

выход кодера: C=[c1, c2, ..., cn]

Пусть задана специальная порождающая матрица Gn,k,

задающая блочный код (n,k).

Строки матрицы Gn,k должны быть линейно независимы.

Тогда разрешенная кодовая комбинация C, соответствующая кодируемому слову X:

C=x1g1 + x2g2 + ... + xkgk.

Систематическая (каноническая) форма порождающей матрицы G размером kxn :

Порождающая матрица систематического кода создает линейный блочный код, в котором первые k битов любого кодового слова идентичны информационным битам, а остальные r=n-k битов любого кодового слова являются линейными комбинациями k информационных битов.

Проверочная матрица Hn,k имеет rxn элементов, причем справедливо:

CxHT = 0.

Это выражение используется для проверки полученной кодовой комбинации. Если равенство нулю не выполняется, то получаем матрицу-строку ||c1, c2, ..., cr||, называемую синдромом ошибки.

Код Хэмминга. Корректирующая и обнаруживающая способности. Правила выбора соотношения между длиной кодового слова и числом информационных битов. Формирование порождающей и проверочной матриц кода Хэмминга. Толкование синдрома ошибки

Рассмотрим код Хэмминга с кодовым расстоянием d=3, позволяющий исправлять одиночные ошибки (d=2qmax+1).

Число разрешенных кодовых комбинаций для кода с d=3, для кода Хэмминга строго равно 2n/(n+1). Первые k разрядов кодовых комбинаций кода используются в качестве информационных и их число равно

k = log2(2n/(n+1)] = n – log2(n+1).

Данное уравнение имеет целочисленные решения k = 0, 1, 4, 11, 26, которые и определяют соответствующие коды Хэмминга: (3,1)-код, (7,4)-код, (15,11)-код и т.д. (всегда n=2w‑1).

 

Проверочная матрица Hкода Хэмминга (r=n-k строк и n столбцов): для двоичного (n,k)-кода n=2w-1 столбцов состоят из всех возможных двоичных векторов с r=n-k элементами, исключая вектор со всеми нулевыми элементами.

Проверочная матрица H для (7,4)-кода: Порождающая матрица G

Легко проверить, что GxHT = 0 (нулевая матрица размером kxrэлементов).

 

Пример. Проверим работу кода при передаче сообщения X=1011. Передаваемая кодовая комбинация будет сформирована в виде линейной комбинации (сложения по модулю 2) строк № 1, 3, 4 матрицы G7,4:

 

Предположим, что на передаваемое кодовое слово Cвоздействовала ошибка 0000100, что привело к получению на приемной стороне слова C'=1011110.



 

Тогда при перемножении C' на проверочную матрицу HTполучаемматрицу-строку синдрома ошибки, которая соответствует тому столбцу проверочной матрицыH с номером бита, содержащего ошибку.

Сравнивая полученный синдром со строками HT, получаем, что ошибочен бит № 5 слева.

 

 

Декодер Хэмминга может работать в двух взаимоисключающих режимах:

- режим исправления (коррекции) ошибок (т.к. dmin=3, то он позволяет исправлять одиночные ошибки);

- режим обнаружения ошибок (т.к. dmin=3, то он обнаруживает ошибки кратности q£2). Если синдром не равен 0, то декодер выдает сигнал ошибки.

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

Расширенный код Хэмминга. Режимы работы декодера, корректирующая и обнаруживающая способности. Формирование кодового слова. Формирование проверочной матрицы расширенного кода Хэмминга. Толкование синдрома ошибки

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

- длины кодов увеличиваются с 2w-1 до 2w, что удобно с точки зрения передачи и хранения информации;

- минимальное расстояние dmin расширенных кодов Хэмминга равно 4, что дает возможность обнаруживать (!) 3-кратные ошибки.

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

Рассмотрим расширение (7,4,3)-кода Хэмминга.

Каждый кодовый вектор Ca получается из кодового вектораc путем добавления дополнительного разряда проверки на четностьCa = (c1, ..., c7, c8), где .

Проверочная матрица H(8,4)-кода получается из проверочной матрицы (7,4)-кода в два приема:

- к матрице (7,4)-кода дописывается нулевой столбец;

- полученная матрица дополняется строкой, полностью состоящей из одних единиц.

Получаем:

.

 

При синдромном декодировании

s' = CHT,

причем все компоненты s' должны быть равны 0.

При одиночной ошибке s'(4) = 1. По значению синдрома (младшие 3 бита) находим и исправляем (инвертируем) ошибочный бит.

При двойной ошибке компонента s'(4)= 0, а синдром отличен от нуля. В отличие от стандартного кода Хемминга такая ситуация ужеобнаруживается, но не исправляется (передается запрос на повторную передачу слова и т.п.).

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

- для исправления однократных и обнаружения двукратных ошибок;

- для обнаружения трехкратных ошибок.





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...