Как вычислить синдром ошибки

Вычисление
синдрома для циклических кодов является
довольно простой процедурой.

Пусть
U(x)
и r(х)
‑
полиномы, соответствующие переданному
кодовому слову и принятой последовательности.

Разделив
r(x)
на g(x),
получим

r(x)
= q(x)
g(x)
+ s(x),
(1.73)

где
— q(x)
— частное от деления, s(x)
— остаток от деления.

Если
r(x)
является кодовым полиномом, то он делится
на g(x)
без остатка, то есть s(x)
= 0.

Следовательно,
s(x)

0
является условием наличия ошибки в
принятой последовательности, то есть
синдромом принятой последовательности.

Синдром
s(x)
имеет в общем случае вид

S(x)
= S₀
+ S₁

x + … + S_n-
k-1 
x^n-k-1
. (1.74)

Очевидно,
что схема вычисления синдрома является
схемой деления, подобной схемам
кодирования рис. 1.10 или 1.11 .

При
наличии в принятой последовательности
r

хотя бы одной ошибки вектор синдрома S
будет иметь, по крайней мере, один
нулевой элемент, при этом факт наличия
ошибки легко обнаружить, объединив по
ИЛИ
выходы всех ячеек регистра синдрома.

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

Пусть

e(x)
= e₀
+ e₁

x
+ e₂

x²
+ … + e_n-1

x
^n-1
(1.75)

— полином
вектора ошибки.

Тогда
полином принятой последовательности

r(x)
= U(x)
+ e(x).
(1.76)

Прибавим
в этом выражении слева и справа U(x),
а также учтем, что

r(x)
= q(x)
g(x) + S(x), U(x) = m(x)
g(x), (1.77)

тогда

,
(1.78)

то
есть синдромный
полином S(x)
есть
остаток от
деления полинома ошибки e(x)
на порождающий полином g(x).

Отсюда следует, что по синдрому S(x)
можно однозначно определить вектор
ошибки e(x), а следовательно,
исправить эту ошибку.

На рис. 1.14 приведена схема синдромного
декодера с исправлением однократной
ошибки для циклического (7,4)-кода.
По своей структуре она подобна схеме,
приведенной на рис. 1.6, с той лишь разницей,
что вычисление синдрома принятой
последовательности производится здесь
не умножением на проверочную матрицу,
а делением на порождающий полином. При
этом она сохраняет и недостаток, присущий
всем синдромным декодерам: необходимость
иметь запоминающее устройство, ставящее
в соответствие множеству возможных
синдромов S множество векторов
ошибок e. Цикличность структуры
кода в этом случае не учитывается.

Рис.
1.14

1.3.4. Неалгебраические методы декодирования циклических кодов

Все
методы декодирования линейных блочных
кодов можно разбить на две группы:
алгебраические
и неалгебраические.

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

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

Одним
из неалгебраических методов является
декодирование с использованием алгоритма
Меггитта,
пригодного для исправления как одиночных,
так и l-кратных
ошибок (на практике l

3).

При
декодировании в соответствии с алгоритмом
Меггитта также вычисляется синдром
принятой последовательности S(x),
однако используется он иначе, нежели в
рассмотренных ранее синдромных декодерах.

Идея,
лежащая в основе декодера Меггитта,
очень проста и основывается на следующих
свойствах циклических кодов:

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

—
если S(x)
— синдромный многочлен, соответствующий
многочлену ошибок е(x),

то xS(x)
mod
g(x)
— синдромный многочлен, соответствующий
x
e(x) mod (xⁿ
+ 1).

Равенство
а(x)
= b(x) mod p(x)
читается как “а(x),
сравнимо с b(x)
по модулю р(x)”
и означает, что а(x)
и b(x)
имеют одинаковые остатки от деления на
полином p(x).

Таким
образом, второе
условие
означает, что если
комбинация ошибок циклически сдвинута
на одну позицию вправо, то для получения
нового синдрома нужно сдвинуть содержимое
регистра сдвига с обратными связями,
содержащего S(x),

также на одну позицию вправо.

Следовательно,
основным
элементом декодера Меггитта является
сдвиговый регистр. Структурная схема
декодера Меггитта для циклических кодов
произвольной длины приведена
на рис. 1.15.

Рис.
1.15

Декодер
работает следующим образом. Перед
началом работы содержимое всех разрядов
регистров равно нулю. Принимаемая
последовательность r
в
течение первых n
тактов вводится в буферный регистр и
одновременно с этим в (n—k)-разрядном
сдвиговом регистре с обратными связями
производится ее деление на порождающий
полином g(x).

Через
n
тактов
в буферном регистре оказывается принятое
слово r
,
a в регистре синдрома — остаток от
деления вектора ошибки на порождающий
полином.

Вычисленный
синдром сравнивается со всеми табличными
синдромами, и в случае совпадения с
одним из них старший разряд буферного
регистра исправляется путем прибавления
к его значению единицы.

После
этого синдромный и буферный регистры
один раз циклически сдвигаются. Это
реализует умножение S(x)
на
x
и деление на g(x).
Содержимое ячеек синдромного регистра
теперь равно остатку от деления xS(x)
на g(x)
или синдрому ошибки x
е(x) mod (Хⁿ
+ 1).

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

Рассмотрим
работу декодера Меггитта для циклического
(7,4)-кода,
исправляющего одиночную ошибку. Схема
декодера изображена на рис. 1.16.

Рис.
1.16

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

Полином
ошибки в старшем разряде для (7,4)-кода
Хемминга имеет вид е₆
(x)
= x⁶,
соответствующий ему синдромный полином
S₆
(x)
= 1 + x³
(
S
= (101)),
детектор ошибки настроен на это значение
синдрома.

Пусть,
например, передана последовательность
U
= (1001011),
ей соответствует кодовый полином U(x)
= 1 + x³
+ x⁵
+ x⁶.
Произошла ошибка в третьей позиции е(x)
= x³,
принятый вектор имеет вид r
= (1000011),
его полином r(x)
= 1 + x⁵
+ x⁶.

Kогда
принятая последовательность полностью
входит в буферный регистр, в регистре
синдрома оказывается синдром,
соответствующий ошибке е(x)
= x³
S₃
= (110).
Поскольку он не совпадает с табличным
для е₆,
на выходе детектора ошибок будет 0
и исправления не происходит.

Далее
производятся однократный циклический
сдвиг принятой последовательности в
буферном регистре, однократное деление
синдрома x∙S₃
на порождающий полином в регистре с
обратными связями и проверка на совпадение
синдрома с заданным.

Последовательность
состояний регистров декодера в процессе
декодирования показана на рис. 1.17.

Рис.
1.17

Т
аким
образом, исправление ошибки в декодере
Меггитта осуществляется за 2n
тактов: в течение n
тактов производится ввод принятой
последовательности в буферный регистр,
в течение l
тактов
— исправление ошибки, и еще в течение
n
— l
— восстановление
буферного регистра в исходное состояние
с исправленным словом. Простота декодера
достигается увеличением времени
декодирования.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #

  10.06.2015684.82 Кб17P4.pdf

• #
• #
• #
• #

Время на прочтение
6 мин

Количество просмотров 62K

Код Хэмминга – не цель этой статьи. Я лишь хочу на его примере познакомить вас с самими принципами кодирования. Но здесь не будет строгих определений, математических формулировок и т.д. Эта просто неплохой трамплин для понимания более сложных блочных кодов.

Самый, пожалуй, известный код Хэмминга (7,4). Что значат эти цифры? Вторая – число бит информационного слова — то, что мы хотим передать в целости и сохранности. А первое – размер кодового слова: информация удобренная избыточностью. Кстати термины «информационное слово» и «кодовое слово», употребляются во всех 7-ми книгах по теории помехоустойчивого кодирования, которые мне довелось бегло пролистать.

Такой код исправляет 1 ошибку. И не важно где она возникла. Избыточность несёт в себе 3 бита информации, этого достаточно, чтобы указать на одно из 7 положений ошибки или показать, что её нет. То есть ровно 8 вариантов ответов мы ждём. А 8 = 2^3, вот как всё совпало.

Чтобы получить кодовое слово, нужно информационное слово представить в виде полинома и умножить его на порождающий полином g(x). Любое число, переведя в двоичный вид, можно представить в виде полинома. Это может показаться странным и у не подготовленного читателя сразу встаёт только один вопрос «да зачем же так усложнять?». Уверяю вас, он отпадёт сам собой, когда мы получим первые результаты.

К примеру информационное слово 1010, значение каждого его разряда это коэффициент в полиноме:

Во многих книгах пишут наоборот x+x^3. Не поддавайтесь на провокацию, это вносит только путаницу, ведь в записи числа 2-ичного, 16-ричного, младшие разряды идут справа, и сдвиги мы делаем влево/вправо ориентируясь на это. А теперь давайте умножим этот полином на порождающий полином. Порождающий полином специально для Хэмминга (7,4), встречайте: g(x)=x^3+x+1. Откуда он взялся? Ну пока считайте что он дан человечеству свыше, богами (объясню позже).

Если нужно складывать коэффициенты, то делаем по модулю 2: операция сложения заменяется на логическое исключающее или (XOR), то есть x^4+x^4=0. И в конечном итоге результат перемножения как видите из 4х членов. В двоичном виде это 1001110. Итак, получили кодовое слово, которое будем передавать на сторону по зашумлённому каналу. Замете, что перемножив информационное слово (1010) на порождающий полином (1011) как обычные числа – получим другой результат 1101110. Этого нам не надо, требуется именно «полиномиальное» перемножение. Программная реализация такого умножения очень простая. Нам потребуется 2 операции XOR и 2 сдвига влево (1й из которых на один разряд, второй на два, в соответствии с g(x)=1011):

Давайте теперь специально внесём ошибку в полученное кодовое слово. Например в 3-й разряд. Получиться повреждённое слово: 1000110.

Как расшифровать сообщение и исправить ошибку? Разумеется надо «полиномиально» разделить кодовое слово на g(x). Тут я уже не буду писать иксы. Помните что вычитание по модулю 2 — это то же самое что сложение, что в свою очередь, тоже самое что исключающее или. Поехали:

В программной реализации опять же ничего сверх сложного. Делитель (1011) сдвигаем влево до самого конца на 3 разряда. И начинаем удалять (не без помощи XOR) самые левые единицы в делимом (100110), на его младшие разряды даже не смотрим. Делимое поэтапно уменьшается 100110 -> 0011110 -> 0001000 -> 0000011, когда в 4м и левее разрядах не остаётся единиц, мы останавливаемся.

Нацело разделить не получилось, значит у нас есть ошибка (ну конечно же). Результат деления в таком случае нам без надобности. Остаток от деления является синдром, его размер равен размеру избыточности, поэтому мы дописали там ноль. В данном случае содержание синдрома нам никак не помогает найти местоположение повреждения. А жаль. Но если мы возьмём любое другое информационное слово, к примеру 1100. Точно так же перемножим его на g(x), получим 1110100, внесём ошибку в тот же самый разряд 1111100. Разделим на g(x) и получим в остатке тот же самый синдром 011. И я гарантирую вам, что к такому синдрому мы придём в обще для всех кодовых слов с ошибкой в 3-м разряде. Вывод напрашивается сам собой: можно составить таблицу синдромов для всех 7 ошибок, делая каждую из них специально и считая синдром.

В результате собираем список синдромов, и то на какую болезнь он указывает:

Теперь у нас всё есть. Нашли синдром, исправили ошибку, ещё раз поделили в данном случае 1001110 на 1011 и получили в частном наше долгожданное информационное слово 1010. В остатке после исправления уже будет 000. Таблица синдромов имеет право на жизнь в случае маленьких кодов. Но для кодов, исправляющих несколько ошибок – там список синдромов разрастается как чума. Поэтому рассмотрим метод «вылавливания ошибок» не имея на руках таблицы.

Внимательный читатель заметит, что первые 3 синдрома вполне однозначно указывают на положение ошибки. Это касается только тех синдромов, где одна единица. Кол-во единиц в синдроме называют его «весом». Опять вернёмся к злосчастной ошибке в 3м разряде. Там, как вы помните был синдром 011, его вес 2, нам не повезло. Сделаем финт ушами — циклический сдвиг кодового слова вправо. Остаток от деления 0100011 / 1011 будет равен 100, это «хороший синдром», указывает что ошибка во втором разряде. Но поскольку мы сделали один сдвиг, значит и ошибка сдвинулась на 1. Вот собственно и вся хитрость. Даже в случае жуткого невезения, когда ошибка в 6м разряде, вы, обливаясь потом, после 3 мучительных делений, но всё таки находите ошибку – это победа, лишь потому, что вы не использовали таблицу синдромов.

А как насчёт других кодов Хэмминга? Я бы сказал кодов Хэмминга бесконечное множество: (7,4), (15,11), (31,26),… (2^m-1, 2^m-1-m). Размер избыточности – m. Все они исправляют 1 ошибку, с ростом информационного слова растёт избыточность. Помехоустойчивость слабеет, но в случае слабых помех код весьма экономный. Ну ладно, а как мне найти порождающую функцию например для (15,11)? Резонный вопрос. Есть теорема, гласящая: порождающий многочлен циклического кода g(x) делит (x^n+1) без остатка. Где n – нашем случае размер кодового слова. Кроме того порождающий полином должен быть простым (делиться только на 1 и на самого себя без остатка), а его степень равна размеру избыточности. Можно показать, что для Хэмминга (7,4):

Этот код имеет целых 2 порождающих полинома. Не будет ошибкой использовать любой из них. Для остальных «хэммингов» используйте вот эту таблицу примитивных полиномов:

Соответственно для (15,11) порождающий многочлен g(x)=x^4+x+1. Ну а теперь переходим к десерту – к матрицам. С этого обычно начинают, но мы этим закончим. Для начала преобразую g(x) в матрицу, на которую можно умножить информационное слово, получив кодовое слово. Если g = 1011, то:

Называют её «порождающей матрицей». Дадим обозначение информационному слову d = 1010, а кодовое обозначим k, тогда:

Это довольно изящная формулировка. По быстродействию ещё быстрее, чем перемножение полиномов. Там нужно было делать сдвиги, а тут уже всё сдвинуто. Вектор d указывает нам: какие строки брать в расчёт. Самая нижняя строка матрицы – нулевая, строки нумеруются снизу вверх. Да, да, всё потому что младшие разряды располагаются справа и от этого никуда не деться. Так как d=1010, то я беру 1ю и 3ю строки, произвожу над ними операцию XOR и вуаля. Но это ещё не всё, приготовьтесь удивляться, существует ещё проверочная матрица H. Теперь перемножением вектора на матрицу мы можем получить синдром и никаких делений полиномов делать не надо.

Посмотрите на проверочную матрицу и на список синдромов, который получили выше. Это ответ на вопрос откуда берётся эта матрица. Здесь я как обычно подпортил кодовое слово в 3м разряде, и получил тот самый синдром. Поскольку сама матрица – это и есть список синдромов, то мы тут же находим положение ошибки. Но в кодах, исправляющие несколько ошибок, такой метод не прокатит. Придётся вылавливать ошибки по методу, описанному выше.

Чтобы лучше понять саму природу исправления ошибок, сгенерируем в обще все 16 кодовых слов, ведь информационное слово состоит всего из 4х бит:

Посмотрите внимательно на кодовые слова, все они, отличаются друг от друга хотя бы на 3 бита. К примеру возьмёте слово 1011000, измените в нём любой бит, скажем первый, получиться 1011010. Вы не найдёте более на него похожего слова, чем 1011000. Как видите для формирования кодового слова не обязательно производить вычисления, достаточно иметь эту таблицу в памяти, если она мала. Показанное различие в 3 бита — называется минимальное «хэммингово расстояние», оно является характеристикой блокового кода, по нему судят сколько ошибок можно исправить, а именно (d-1)/2. В более общем виде код Хэмминга можно записать так (7,4,3). Отмечу только, что Хэммингово расстояние не является разностью между размерами кодового и информационного слов. Код Голея (23,12,7) исправляет 3 ошибки. Код (48, 36, 5) использовался в сотовой связи с временным разделением каналов (стандарт IS-54). Для кодов Рида-Соломона применима та же запись, но это уже недвоичные коды.

Список используемой литературы:

1. М. Вернер. Основы кодирования (Мир программирования) — 2004
2. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования (Мир связи) — 2006
3. Р. Блейхут. Теория и практика кодов, контролирующих ошибки — 1986