Декодирование по синдрому

При синдромном декодировании нет необходимости хранить в памяти декодера все разрешенные комбинации. Достаточно знать правила, по которым формируются разрешенные кодовые комбинации в кодере, и проверять, удовлетворяет ли принятая декодером комбинация этим правилам.

При декодировании систематических линейных блочных кодов проверяют выполнение условия (14) Н^Т=0. Если принята неразрешенная комбинация, это произведение будет отлично от нуля.

При декодировании циклических линейных кодов используется их свойство делиться без остатка на порождающий полином g(х), т.е. проверяется выполнение условия (24) h(x)∙g(x)=0. Если принята неразрешенная комбинация, остаток от деления R(x) будет не равен нулю.

В обоих случаях полученный результат представляет собой совокупность нулевых и ненулевых символов, называемую синдромом ошибки S (термин "синдром" заимствован из медицины, где он обозначает сочетание симптомов, характерных для определенного заболевания). Число разрядов синдрома S равно числу проверочных символов r. По виду синдрома с помощью специальных таблиц можно определить номер искаженного при передаче символа.

Декодирование систематических линейных блочных кодов Хэмминга синдромным способом

Для декодирования по синдрому принятую декодером последовательность символов А^* умножают на транспонированную проверочную матрицу Н^Т (транспонирование необходимо для изменения ранга матрицы с [ r ] на [ ]). Если полученный в результате перемножения синдром S= А^*∙ Н^Т равен нулю, декодер принимает решение о безошибочном приеме и выдает на выход k -разрядную последовательность информационных символов. На практике она может отличаться от поступившей на вход кодера. Это происходит в тех случаях, когда переданная разрешенная комбинация переходит в другую разрешенную. Если синдром S= А^* ∙ Н^Т не равен нулю, декодер обнаруживает наличие ошибки, по виду синдрома определяет соответствующий вектор ошибки Е и корректирует принятую последовательность символов.

Для кодов Хэмминга, исправляющих одну ошибку, векторы ошибки Е_i представляют собой n -разрядные комбинации, содержащие по (n-1) нулевых символов и одному ненулевому (единичному). Этот единичный разряд и указывает номер неверно принятого символа в кодовой комбинации. Нулевому синдрому соответствует нулевой вектор ошибки. Для кодов Хэмминга синдромы единичных ошибок совпадают со строками транспонированной проверочной матрицы .

Рассмотрим метод синдромного декодирования подробнее. Транспонируем проверочную матрицу _3,7 (5.8) путем преобразования каждой из ее строк в соответствующий столбец матрицы :

_3,7 = (29)

Составим таблицу 5 соответствия синдромов и векторов ошибок, используя матрицу Н^Т_7,3 (29). Первой строке матрицы соответствует ошибка в первом разряде принятой комбинации, второй строке − ошибка во втором разряде и т.д.

Таблица 5 − Таблица соответствия синдромов и векторов ошибки кода Хэмминга (7;4)

Синдром S	Вектор ошибки Е
s1	s2	s3
			1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1

Вначале рассчитаем синдром для разрешенной кодовой комбинации А=0101010, сформированной с использованием проверочной матрицы (15) в примере 8:

Для расчета первого разряда синдрома s ₁ поразрядно умножаем принятую комбинацию А на первый столбец матрицы и полученные символы суммируем по модулю два:

Аналогично рассчитываем разряды s₂ и s₃, умножая комбинацию А соответственно на второй и третий столбцы матрицы (29):

;

.

В итоге имеем S = s1s2s3=000. Нулевой синдром свидетельствует об отсутствии ошибки (вектор ошибки Е=0000000). Введем в комбинацию А одну ошибку, например, в четвертый разряд: А^* =010 0 010. Рассчитаем синдром ^* вышеуказанным способом:

;

;

В итоге ^*= Получен ненулевой синдром, свидетельствующий о наличии ошибок в принятой комбинации. По таблице 5 определяем вектор ошибки, соответствующий синдрому 111: Е=0001000. Поскольку ошибочная комбинация А^* представляет собой сумму верного слова А и ошибки (А^*=А ), то скорректированное слово

. (30)

Проведем коррекцию А^'=А^* .

Как видим, удалось исправить одну ошибку. На выход декодера выдается k -разрядная комбинация

Введем в комбинацию А две ошибки: А^**= 01 10 010. Рассчитаем синдром S^**= Синдрому 001 в таблице 7.1 соответствует вектор ошибки 0000001. Используя (7.2), корректируем ошибку: А^''=A .

На выход декодера выдается ошибочная комбинация Несмотря на то, что двукратная ошибка кодом обнаружена, скорректировать ее не удалось, так как код с d₀ =3 обеспечивает t_исп=1. Для увеличения кратности t_исп и t_обн необходимо увеличивать d₀, но при этом увеличится число разрядов n и уменьшится скорость передачи кода R =

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

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

БВС – блок вычисления синдрома;

С – селектор;

БК – блок коррекции

Декодер работает следующим образом. Принятая последовательность символов поступает на декодер в параллельном коде. В блоке вычисления синдрома определяется синдром ошибки S и затем селектор находит соответствующий синдрому S вектор ошибки Е. В блоке коррекции сообщение корректируется путем суммирования принятой последовательности А^* и вектора ошибки Е. Проверочные разряды обычно не корректируются. На выход декодера поступают откорректированные информационные символы . На рисунке 6 цифрами над соединительными линиями показана разрядность передаваемых последовательностей символов.

Декодирование циклических кодов синдромным способом

Для определения синдрома циклического кода достаточно поделить принятую комбинацию символов на порождающий полином g(х). Остаток от деления R(х) и есть синдром: S(x) = R(x). При S(x) = 0 принято разрешенное слово, а при S(x) ≠ 0 − обнаружено наличие ошибки. При S(x) ≠ 0 по таблице соответствия синдромов и ошибочных символов находят неверный разряд е(х) и корректируют принятое слово. Имеются отличия в декодировании разделимых и неразделимых циклических кодов.

Для разделимого кода после коррекции принятой п - разрядной комбинации на выход декодера выдаются информационные символы. Для неразделимого кода откорректированную n -разрядную последовательность символов необходимо еще раз поделить на порождающий полином и частное от этого деления выдать на выход декодера. Если же при первом делении на полином g(x) остаток от деления R(x)=0, то на выход декодера выдается частное от этого первого деления.

Для составления таблицы соответствия синдромов и ошибочных символов надо в любое разрешенное кодовое слово вводить поочередно по одной ошибке в определенные разряды и выполнять деление на полином g(х). Полученные остатки и будут синдромами для соответствующих символов. В таблице 6 приведены синдромы ошибок для двух циклических кодов (7;4) с порождающими полиномами g₁(x) g₂(x).

Таблица 6 − Таблица соответствия синдромов и ошибочных символов для двух циклических кодов (7;4) с порождающими полиномами g₁(x) g₂(x).

Ошибочный символ е(х)	х^0	х^1	х^2	х^3	х^4	х^5	х^6
Синдром S(x) при g1(x)=x^3+x+1
Синдром S(x) при g2(x)=x^3+x^2+1

Пример 18 Требуется найти и исправить ошибку в принятой комбинации символов разделимого циклического кода: А^* =0100100; g(x)=x³+x+1.

Решение. 1 Переведем А^* в полином: а^*(х)=х⁵+х².

2 Разделим а^*(х) на g(x) и найдем остаток от деления R(x):

Переведем R(х) в двоичный вид с учетом числа проверочных символов: R(х)=S(х)=011.

3 По таблице 7.2 находим, что синдрому S(х)=011 соответствует ошибка в символе х³.

4 Корректируем сообщение: а^'(x)=a^*(х)

5 Переводим а^'(х) в двоичный вид и отбрасываем проверочные символы: А^' =0101100;

Электрическая структурная схема синдромного декодера циклического разделимого кода (7;4) приведена на рисунке 7. Декодирование проводится за 2∙ n тактов. В первые n тактов принятое в последовательном коде слово а^*(х), начиная со старших разрядов, записывается в буфер и одновременно поступает в генератор синдрома, где через n шагов находится остаток от деления а^*(х) на g(х). При R(х)=S(х)=0 ошибки нет или она не обнаружена (вектор ошибки е(х) =0). При R(х)=S(x)≠0 ошибка обнаружена. За вторые n тактов информация с буфера, исправляясь в сумматоре, поступает на выход. Задача селектора при этом − выдать исправляющий сигнал в тот момент, когда ошибочный символ покидает буферный регистр. Далее необходимо отбросить проверочные символы.

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

В декодере неразделимого циклического кода при обнаружении ошибки необходимо обеспечить повторное деление откорректированной n -разрядной последовательности на полином g(х).

Пример 19 Требуется найти и исправить ошибку в принятой комбинации символов неразделимого циклического кода (7;4): А^*= 1100111; g(х)=х³+х+1.

Решение.

1 Переведем А^* в полином а^*(х)=х⁶+х⁵+х²+х+1.

2 Разделим а^*(х) на g(х), найдем остаток от деления R(х) и переведем его в двоичный вид с учетом числа проверочных символов:

3 По таблице 6 находим, что синдрому 101 соответствует ошибка в символе х⁶, и корректируем ее: а^'(x)=a^*(х)

4 Для нахождения а^'_k-1(x) разделим а^'(x) на g(х):

5 Переведем а^'_k-1(x) в двоичный вид с учетом числа информационных символов: а^'_k-1(x)=х²+1 0101=A_k^'.

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