Синдромное декодирование кода Хемминга, исправляющего одиночные ошибки

 

Коды Хемминга бывают двоичными и недвоичными. Двоичные коды включают класс кодов со свойствами:

(n, k) = (2 ^m - 1, 2 ^m - 1 - m),                           (3.23)

где m –целое положительное число; при m =3 имеем код (7, 4).

Проверочная матрица таких кодов проста, содержит (n - k) строк и   n линейно независимых столбцов-векторов с (n - k) = m элементами. Она легко приводится к систематической форме (3.17) и соответствующей порождающей матрице из уравнения (3.16).

Однако, при m >1 можно найти 3 столбца из, которые при сложении дают нуль. Следовательно, для ( n, k) кода Хемминга d_min =3.

Для иллюстрации синдромного декодирования кода Хемминга, исправляющего одиночные ошибки, рассмотрим проверочную матрицу:

                                                      (3.24)

где  - вектор- строка из (n - k) символов.

В этом случае уравнение синдрома (3.22) имеет вид:

 .                                                    (3.25)

При наличии одиночной ошибки в кодовом слове из n символов, например, в j -й позиции, последовательность ошибок состоит из нулей за исключением единицы в j -й позиции, и тогда

                                           (3.26)

Поэтому при одиночной ошибке в j -й позиции принимаемого кодового слова формируется ненулевой синдром, равный j -й вектор-строке проверочной матрицы.

Если необходимо обнаружить все одиночные ошибки, то все вектор-строки проверочной матрицы должны быть различными. При этом вектор, содержащий все нули, должен быть исключен, поскольку нулевой синдром означает отсутствие ошибок. Так как имеется 2 ^{n - k} различных последовательностей длиной (n-k), то проверочная матрица содержит 2 ^{n - k}- 1 строк.

Таким образом, n  и   k  в (3.25) связаны между собой соотношением:

 

n = 2 ^{n - k} – 1,                                                  (3.27)

где (n – k) – количество проверочных символов.

 

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

Решение.

Для этого кода с (n – k) проверочными символами согласно (3.27) имеется 2³ − 1=7 последовательностей длиной 3 (исключая нулевую), которые являются столбцами проверочной матрицы. Для систематического (7,4) кода первые четыре столбца этой матрицы содержат более одной двоичной единицы.

Одна из возможных двоичных проверочных матриц систематического кода в транспонированной форме (3.18), соответствующая порождающей матрице (3.13),  имеет вид:

                      (3.28)

Для заданной порождающей матрицы (3.13) и информационной последовательности, например, соответствует кодовое слово:                         .                                                  

Если ошибка передана в пятой позиции, то принимаемая последовательность и синдром имеют следующий вид:

;

 ,                      (3.29)

где первый символ синдрома равен:

z₁∙0+z₂∙1+z₃∙1+z₄∙1+z₅ ∙1+z₆∙0+z₇ ∙0= z₂+z₃+z₄ + z₅= (0+1+1+1)mod2=1.

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

Если ошибки переданы во второй и пятой позициях, то вектор ошибки равен, а принятая последовательность. Ей соответствует синдром:, ошибочно указывающий на то, что ошибка произошла в седьмой позиции. Причина этого ошибочного решения заключается в том, что код, формируемый матрицей (3.13), имеет расстояние 3 и не способен исправлять двойные ошибки. Для исправления таких ошибок необходимо иметь расстояние d_min = 5. Однако, этот код обнаруживает наличие ошибок.

Циклические коды

Циклические коды (ЦК) относятся к подклассу линейных блоковых кодов и наиболее просты в реализации. Если некоторое кодовое слово принадлежит ЦК, то его циклические перестановки также принадлежат ЦК. Иными словами, (n − 1) кодовых слов ЦК могут быть сформированы в кодеке путем циклического сдвига одного кодового слова, т.е. на регистрах сдвига и сумматорах по модулю 2.

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

Кодовое слово C = [ c_{n -1} c_{n -2} … c ₁ c ₀ ] циклического кода с n элементами связывают с полиномом C (p) степени ≤ (n −1):

C (p) = c_{n -1} ∙ p^{n -1} + c_{n -2} ∙ p^{n -2} + …+ c ₁ ∙ p + c ₀,                    (3.30)

где для двоичного кода коэффициенты с _i  являются нулем или единицей.

Циклическому сдвигу кодового слова на одну позицию соответствует умножение этого полинома на р

pC (p) = c_{n -1} ∙ pⁿ + c_{n -2} ∙ p^{n -1} + …+ c ₁ ∙ p ² + c ₀ p.

 

Полученный полином при с _{n -1} =1 не может соответствовать кодовому слову по условию (3.30), так как его степень n.

Если его разделить на (pⁿ +1), то получим частное и остаток

 

                          (3.31)

С_п-1 р ^п + С_п-2 р^п-1 +…С₀ р│ P^п +1

С_п-1 р ^п + С_п-1                  С_п-1-частное

С_п-2 р ^п-1 +…С₀р+ С_п-1 - остаток

где остаток от деления равен полиному

                  C ₁ (p) = c_{n -2} ∙ p^{n -1} + c_{n -3} ∙ p^{n -2} + …+ c ₀ ∙ p + c_{n -1}.

 

Этот остаток представляет согласно (3.30) кодовое слово

  C ₁ = [ c_{n -2} c_{n -3} … c ₀ c_{n -1} ] _,

полученное сдвигом на одну позицию.

В этом случае этот остаток от деления можно записать согласно уравнению (3.31) в виде:

                       C₁ (p) = pC(p) mod (pⁿ +1),

соответственно при i циклических сдвигах 

 

C_i (p) = pⁱ C(p) mod (pⁿ +1)                   (3.32)

 

где полином C_i (p) также представляет кодовое слово C_i   ЦК.

Таким образом, умноженный на pⁱ полином C (p) ЦК удовлетворяет согласно (3.31) условию циклического сдвига:   

 

           pⁱ C (p) = Q(p) (pⁿ +1)+ C_i (p),                 (3.33)

 

где Q (p) - частное от деления полиномов;

C_i (p) - остаточный от деления полином, представляющий кодовое слово C_i ЦК.

    Известно, что полином (pⁿ +1) можно факторизовать (представить произведением сомножителей) в виде:

(pⁿ +1) = g (p) ∙ h (p),                                 (3.34)

где g (p) - порождающий полином степени (n − k) ЦК (n, k);

h (p) - проверочный полином степени k, который можно использовать для генерации дуального ЦК (n, n − k).

Покажем, что генерируемые этими полиномами ЦК удовлетворяют условию циклического сдвига (3.33).

Циклический (n, k) код будем генерировать, используя в качестве порождающего полином g (p) с двоичным коэффициентами:

            (3.35)

Пусть полином информационного сообщения

,             (3.36)

где [ x_{k -1,}   x_{k -2,} … x _1, x ₀ ] определяют k информационных бит кодового слова ЦК и соответственно 2 ^k  полиномов.

Тогда произведение полиномов

          (3.37)

формирует 2 ^k   полиномов степени  ≤( n − 1), каждому из которых соответствует кодовое слово C_m  ЦК, т.к. каждое из них удовлетворяет условию циклического сдвига (3.33).

Пример. Доказать, что произведению полиномов (3.37) соответствуют генерируемые кодовые слова C_m.

Докажем это для кодового слова C_{m =1}. Сдвиг кодового слова C ₁ в (3.37), т.е. умножение C (p) на   p   дает согласно (3.31) равенство:

                      .

Но C (p) согласно (3.37),а (pⁿ +1) согласно условию факторизации (3.34) делятся оба без остатка на g (p). Следовательно, и C ₁ (p) делится на g (p) без остатка, т.е. его можно представить как

                                                     

Следовательно, генерируемый (3.37) циклический сдвиг в кодовом слове C (p) порождает другое кодовое слово, например, C ₁ (p).

Для генератора дуального (n, n − k) ЦК можно показать аналогичное (3.37) правило генерации кодовых слов на основе полинома h (p). На практике в качестве порождающего полинома дуального ЦК используют полином, обратный к h (p) и определяемый как

 

                                                                                                  (3.38)

В теории кодирования известны различные правила (алгоритмы) построения порождающих матриц (n, k) ЦК и дуального (n, n - k) ЦК в несистематической и систематической форме по соответствующим полиномам (3.35) и (3.38).

Известно, например, что полином, соответствующий l –й строке порождающей матрицы ( n, k) ЦК в систематической форме, удовлетворяет уравнению

.                 (3.39)

 

При этом R_l (p) степени, меньшей чем ( n - k), соответствует остатку от деления полинома p^{n - l} на полином g (p) (3.35) и определяет проверочные символы l –й строки матрицы.

Пример. Построить по алгоритму (3.39) порождающую и проверочную матрицы ЦК (7,4).

Решение.

Для (n, k)  кода с n =7, k =4 полином (3.34) p ⁷ +1 можно факторизовать в виде

p ⁷ +1=(p ³ + p +1)(p ³ + p ² +1)(p +1)= g ₁ (p)∙ g ₂ (p)∙ g ₃ (p)= g ₁ (p)∙ h (p),

где проверочный полином степени k равен

h (p)= (p ³ + p ² +1) (p +1)= p ⁴ + p ² + p +1.

Полином g ₁ (p) = (p ³ + p +1) примем порождающим полиномом кода

(7, 4), а порождающим полиномом дуального кода (7, 3) является обратный проверочный полином                                                                                                          p ⁴ ∙ h (p ^-1)=1+ p ² + p ³ + p ⁴.

Найдем первую строку порождающей матрицы в систематической форме согласно (3.39), разделив полином   p^{n - l} = p ⁶ на порождающий полином g ₁ (p).           

P⁶              │ P³+P+1

P⁶+P⁴+P³      P³+P+1

                                                              P⁴+P³             

                                                         P⁴+P²+P

                                                              P³+P²+P

                                                              P³+P+1

                                                              (P²+1) - остаток R₁ (p)

Полином, соответствующий 1-й строке матрицы согласно (3.39), имеет вид p ⁶ = (p ³ + p +1)(p ³ + p +1)+ p²+1, где полиному остатка соответствует в кодовом слове три последние проверочных бита 101.

Аналогично можно найти: p ⁵ = (p ² +1) g ₁ (p)+ p ² + p +1   

   p⁴ = p g₁(p)+p²+p

p³ = g₁(p)+p+1

и порождающая матрица ЦК в систематической форме имеет вид:

,         (3.40)

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

 .         (3.41)

Вместе с тем,рассмотренный алгоритм (3.39) построения порождающей матрицы ЦК позволяет генерировать систематический ЦК  непосредственно из порождающего полинома g ₁ (p).

Если умножим полином сообщения (3.38) на p^{n - k}, то получим

 

,

который в систематическом коде представляет первые (старшие) k бит кодового слова C (p). К этому полиному необходимо добавить полином степени меньшей, чем (n - k), т.е. остаток r (p), представляющий проверочные символы кодового слова.

Таким образом, приходим к подобному (3.39) алгоритму формирования систематического кода, из порождающего полинома g (p):

 

.                   (3.42)

Согласно этому алгоритму:

1. Умножаем полином сообщения X (p) на р^{( n - k )};

2. Делим полученное произведение на полином g (p), чтобы получить остаток r (p) степени меньшей, чем (n − k);

3. Суммируем по mod 2 остаток r (p)  с полиномом произведения A (p) = р^{( n - k )}Х(р) и получаем систематический код.

Деление полинома A (p) степени (n −1) на полином степени (n − k)

g (p)= g_{n - k} (p) р^{( n - k )} + g_{n - k -1} (p) р^{( n - k -1)} +…+ g ₁ (p)+ g ₀    

можно реализовать посредством (n − k) ячеек регистра сдвига с обратной связью рис. 3.5.

 

Рис. 3.5. Схема деления полиномов A(p) на g (p).

В исходном состоянии ячейки регистра сдвига содержат нули. Коэффициенты А(р) продвигаются по тактам коэффициентами при p более высокого порядка вперед, т.е. а _{n -1}, затем а _{n -2}  и т.д.

После (n − k −1) тактов первый ненулевой выход частного равен

q ₁ =(g_{n - k})^-1∙ a_{n -1}. Далее на каждом последующем такте i для образования каждого выходного коэффициента регистра (т.е. частного q_i) мы должны, как и при обычном делении, вычесть полином g (p), умноженный на этот коэффициент q_i частного. Это вычитание реализуется обратной связью.

Если в структуре регистра положить (g_{n - k}) = g ₀ =1, то для двоичных кодов арифметические операции выполняются по mod 2 и вычитание сводится к сложению.

В результате, структура кодера ЦК в систематической форме согласно алгоритму (3.42) имеет вид, рис. 3.6:

 

Рис.3.6. Общая структура кодера ЦК в систематической форме на основе полинома g (p).

 

Для получения на выходе ЦК в систематической форме необходимо к первым k выходным битам кодера, равным k входным информационным битам (ключи 1,2- в положении, обозначенном непрерывной линией), добавить (n − k) проверочных бит остатка r (p) от деления (ключи 1,2 переключены  в положение, обозначенное пунктирной линией).

Таким образом, кодирование и вычисление синдрома при декодировании могут быть реализованы с помощью k - разрядного либо (n − k) - разрядного регистра сдвига с обратной связью, задаваемого соответственно проверочным h (p) либо порождающим g (p) полиномом. При (n − k)< k кодер на основе g (p) проще (т.е. для больших скоростей требуется меньше ячеек регистра).

Рассмотрим примеры кодирования и декодирования ЦК.

Пример 1. Построить кодер ЦК (7,4) в систематической форме на основе полинома g (p) = p ³ +р +1.

Решение.

Структура кодера (на основе общей структуры рис. 3.6), пошаговое состояние регистров, выходное слово ЦК при сообщении «0110» представлены на рис. 3.7.

 

Вход	Шаг сдвига	Содержимое регистра
		С0	С1	С2
0	1	0	0	0
1	2	1	1	0
1	3	1	0	1
0	4	1	0	0

                           

Рис. 3.7. Кодер ЦК (7,4) на основе g (p) = p³ +р +1.

 

Пример 2. Построить кодер и декодер ЦК (7,4), задаваемого порождающим полиномом g (p) = (p ³ + p ² +1).

Решение.

На рис. 3.8 приведена структурная схема кодера ЦК (7,4), в котором используется согласно общей структуре (рис.3.6) трехразрядный регистр сдвига, задаваемый порождающим полиномом g (p) = (p ³ + p ² +1).

 

Сдвиг	Вход	Ключ	Коммутатор	R 1	R 2	R 3	Выход
1	1	С	В	1	0	0	1
2	0	С	В	0	1	0	0
3	1	С	В	0	0	1	1
4	0	С	В	1	0	0	0
5	-	0	А	0	1	0	0
6	-	0	А	0	0	1	1
7	-	0	А	0	0	0	1

Рис. 3.8. Структурная схема кодера ЦК (7,4) итаблица содержимого регистра сдвига (С- ключи замкнуты).

 

Работа кодера показана для входного слова 1010. Для первых четырех тактов сдвига в РС ключи замкнуты, а выходной переключатель - в положении В. В течение этого интервала информационная последовательность поступает на вход канального модулятора (выход кодера) и регистра сдвига. Затем ключи размыкаются (положение 0), а переключатель замыкается в положение А.

В течение следующих трех тактов на выход кодера подаются три проверочных символа, которые завершают процедуру формирования кодового слова ЦК. Информационной последовательности [1010] соответствует проверочная последовательность [011]. Полное кодовое слово на выходе кодера имеет вид: 1010011.

Схема декодера для этого ЦК приведена на рис.3.9.

Рассмотрим работу декодера, предполагая, что ошибка произошла в 4-й позиции и принимаемая последовательность имеет вид: [101 1 011]. Состояние ключей и регистров декодера для всех 14 сдвигов приведено в таблице 3.1.

 

 

Рис.3.9.  Схема декодера ЦК (7,4) в систематической форме.

 

Таблица 3.1. Состояние ключей и РС декодера ЦК (7,4).

Сдвиг	Вход	Ключ	R1	R2	R3	И	S1	S2	S3	S4	S5	S6	S7	Выход
1	1	С	1	0	0	-	1	-	-	-	-	-	-	-
2	0	С	0	1	0	-	0	1	-	-	-	-	-	-
3	1	С	0	0	1	-	1	0	1	-	-	-	-	-
4	1	С	0	0	0	-	1	1	0	1	-	-	-	-
5	0	С	0	0	0	-	0	1	1	0	1	-	-	-
6	1	С	1	0	0	-	1	0	1	1	0	1	-	-
7	1	С	1	1	0	-	1	1	0	1	1	0	1	-
8	-	0	1	1	1	0	-	1	1	0	1	1	0	1
9	-	0	0	1	1	0	-	-	1	1	0	1	1	0
10	-	0	0	0	1	0	-	-	-	1	1	0	1	1
11	-	0	1	0	0	1	-	-	-	-	1	1	0	1
12	-	0	0	1	0	0	-	-	-	-	-	1	1	0
13	-	0	1	0	1	0	-	-	-	-	-	-	1	1
14	-	0	1	1	0	0	-	-	-	-	-	-	-	1

 

Обработка слова осуществляется за следующие 14 сдвигов:

- в течение 7 тактов идет заполнение регистров R_i и S_j;

- с 8-го такта – формирование синдрома.

На выходе схемы «И» единица появится при наличии трех единиц на входе. Поэтому для формирования единицы на выходе схемы «И» необходимо, чтобы содержимое регистра R с учетом инверторов было [100].

Это условие выполнимо при 11 сдвиге. Поэтому четвертый символ принятой последовательности инвертируется в процессе ее продвижения на выходе декодера.

Для данного кода можно построить порождающую (3.40) и проверочную (3.41) матрицы и убедиться (как и в (3.29)), что четвертой позиции будет соответствовать синдром  [100].

Таким образом, верхняя часть декодера фактически представляет собой генератор синдрома, а для построения кодера и декодера ЦК достаточно задать порождающий g (p) или проверочный h (p) полином.

Рассмотрим примеры разновидностей наиболее известных ЦК.

 

3.1.4.1. Коды Боуза – Чоудхури – Хоквингема (БЧХ )

В классе ЦК наиболее важным является подкласс БЧХ - кодов. Эти коды имеют двоичный и не двоичный алфавит и построены для широкого диапазона длин кодового блока, кодовых скоростей и исправляющих способностей.

В частности, для двоичных кодов длина кодового слова, число проверочных символов и кодовое расстояние удовлетворяют соотношениям:

 

n = 2^m − 1          

n − k £ m l                                (3.43)

d_min = 2 l + 1,

 

где l – кратность исправляемых ошибок в пределах блока; m ≥3 – произвольное целое число.

Значение k при заданных значениях n и l определить сложно. Однако для малых значений l выполняется равенство:

 

n−k = m l                                              (3.44)

При l = 1 параметры n и k  соответствуют параметрам кода Хемминга, т. е. код Хемминга является кодом БЧХ, исправляющим одиночные ошибки.

Порождающие полиномы БЧХ кодов можно конструировать из множителей полинома.  В таблице 3.2 [3] приведены коэффициенты (в восьмеричной форме) порождающих полиномов для БЧХ кодов длины

7 ≤ n ≤ 127, соответствующие значениям 3≤ m <7, где левая цифра соответствует слагаемому полинома с высшей степенью. Например, для кода (15,5) коэффициентами полинома являются 2467, что в двоичной форме соответствует 10 100 110 111. Следовательно, полином равен

    g (p)= p ¹⁰ + p ⁸ + p ⁵ + p ⁴ + p ² + p +1.

Таблица 3.2. коэффициенты порождающих полиномов для БЧХ кодов.

n        k     l                  g(p)	n        k     l                   g(p)
7     4   1                13	63  57   1              103
15     11  1                23	51   2          12471
7   2               721	45   3          1701317
5   3             2467	39  4           .
31     26 1                   45	39 5           .
21  2            3551	10 13           .
16  3        107657	7  15           .
11  5      5423325	127 120 1             211
6    7   313365047	127 113 2          41567

  Коды Голея

Коды Галея

Код Голея позволяет исправлять ошибки высокой кратности и является совершенным ЦК.

Код Голея (23, 12) может генерироваться порождающим полиномом g (p)= p ¹¹ + p ⁹ + p ⁷ + p ⁶ + p ⁵ + p +1 и исправляет все конфигурации ошибок, кратность которых не больше трех. Расширенный код (24, 12) образуется из кода (23,12) добавлением символа проверки на четность к словам кода

(23, 12). Эти коды имеют минимальное кодовое расстояние, равное 7 и 8 соответственно. Поэтому код (24,12) кроме исправления ошибок кратности 3 обеспечивает обнаружение ошибок кратности 4 при незначительном изменении кодовой скорости и является одним из наиболее известных.