Синтез кодеков циклических кодов Хэмминга

В соответствии с [1-5,8] параметры кодов Хэмминга определяются равенством n=2^l-1 двоичных символов, k=2^l-1-l двоичных символов, l – количество проверочных символов. В общем виде циклический код Хэмминга может быть записан так: (n,k)=(2^l, 2^l-1-l).

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

Циклические коды Хэмминга могут быть построены с использованием как порождающей G_k,n(x), так и проверочной H_l,n(x) матриц. Характерной особенностью проверочных матриц кодов Хэмминга с d₀=3 и d₀=4 является то, что столбцы матриц представляют собой различные ненулевые комбинации (последовательности или кодовые слова) содержащие l двоичных символов (разрядов). Проверочные матрицы кодов Хэмминга обладают следующими свойствами:

1) ненулевые символы строк H_l,n(x) определяют позиции информационных символов, участвующие в формировании проверочных символов;

2) число логических «l» в каждом столбце H_l,n(x), т. е. вес столбца (w_{столбца}), должно быть больше или равно d₀-1;

3) при перестановке столбцов H_l,n(x) корректирующие свойства кода не меняются: код имеет минимальный вес (w_к) не менее d₀, т. е. w_к ≥ d₀, тогда и только тогда, когда каждое множество из (w_к-1) столбцов матрицы H_l,n(x) линейно независимы;

4) сумма по модулю два любых столбцов матрицы H_l,n(x), соответствующие информационным символам, должны давать вес (w_∑) не менее d₀-1, т. е. w_∑ ≥ d₀-1;

5) при сложении строк матрицы H_l,n(x) и при умножении строк матрицы H_l,n(x) на ненулевые элементы, корректирующие свойства кода не меняются.

Циклические коды Хэмминга могут быть декодированы с использованием как мажоритарного, так и синдромного алгоритмов декодирования. В свою очередь мажоритарный алгоритм декодирования может быть реализован с формированием системы как раздельных ортогональных (согласованных) проверок (ортогональных проверочных уравнений), так и с формированием системы связанных проверок. Далее рассмотрим сущность данных алгоритмов декодирования и выполним синтез кодеков, реализующих данные алгоритмы декодирования при использовании коротких кодов Хэмминга, а именно кодов с параметрами (n,k,d₀)=(7,4,3) и (n,k,d₀)=(7,3,4).