20. Циклические коды. Порождающий многочлен циклического кода, проверочный многочлен;

Синдром циклического кода, теорема о синдроме циклического кода.

Пример (могут просить написать):

Запись элементов из в виде многочленов (описание циклических кодов как идеалов в кольце многочленов): Можно записать элементы поля в виде многочленов и тогда рассматривать циклические коды как иделы в кольце многочленов. — сопоставление.

Для многочленов, степень которых меньше или равна n-1, соответствие взаимно однозначное.

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

Опр. Идеал. Правый (левый) идеал – такое подкольцо кольца, умножение всех элементов которого справа(слева) на элемент кольца принадлежит идеалу. Если верны оба утверждения, множество называется двусторонним идеалом. Если операция коммутативна, используется понятие идеал.

Доказательство утверждения: a) . Т.к в кольце К где результат циклического сдвига. Т.к. С- цикличен, то и , то

б) .

из свойства «а» для идеалов следует, что , но тогда из свойства «б» следует, что . При умножении одного многочлена на другой получим сумму указанных произведений, каждое из которых принадлежит I. Но так как I замкнуто по сложению, получим что произведение 2-х многочленов, один из которых принадлежит кольцу К, а второй подкольцу I лежит в I. . Из данного включения следует, что является подкольцом и идеалом кольца К. что и требовалось показать.

Порождающий и проверочный многочлен циклического кода.

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

Утверждение «О многочлене »:

Доказательство: поделим многочлен на многочлен с остатком. Получим:

Опр.: Многочлен циклического кода С, описанный выше, называется порождающим многочленом данного кода.

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

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

Замечание: Т.к. все порождающие многочлены одного кода отличаются друг от друга на константу, то и все проверочные многочлены отличаются на константу. Обычно, в качестве проверочного многочлена выбирают тот, у которого коэффициент при старшем члене равен 1.

Требование к порождающему полиному при кодировании – его вес не должен быть меньше минимального кодового расстояния

В теории информации циклические коды часто записываются как и k соответствует числу информационных символов, а m- проверочных

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

несистематическое кодирование осуществляется путём умножения кодируемого вектора на g(x): c(x) = u(x)g(x) – векторы сначала переписываются в виде соответствующих полиномов, а затем перемножаются, после чего записывается вектор, соответствующий ответу

систематическое кодирование осуществляется путём «дописывания» к кодируемому слову остатка от деления на g(x), deg(g(x)) = n-k, то есть .

Обнаружение ошибок кодирования (при передаче в канале с помехами)

Будем рассматривать несистематическое кодирование. Пусть мы получили сообщение

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

Если а(х) С, то а(х)*h(x)≠0;

a(x)*h(x)=b(x)*g(x)*h(x)=b(x)(x n +1)=0 mod(x n +1);

Теорема «О порождающей матрице циклического кода»: Пусть С – циклический код над с длинной кодового слова и порождающим многочленом . Тогда в качестве порождающей матрицы кода С можно взять матрицу вида:

Доказательство: Для доказательства теоремы необходимо и достаточно показать, что вектора:

, , являются базисом кода С.

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

; ;

Покажем, что элементы — линейно независимы. Рассмотрим линейную комбинацию:

Теорема «О проверочной матрице циклического кода»: Пусть циклический код С с длинной кодового слова и проверочным многочленом , . Тогда в качестве проверочной матрицы кода С можно взять матрицу вида:

М атрица будет являться одной из проверочных матриц для кода С. Из соображений размерности получим: . Легко заметить, что последнее строк матрицы линейно независимы, поэтому предыдущие строки можно отбросить и получить в качестве проверочной матрицы матрицу Н из условия теоремы.

Источник

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

Что это такое

Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.

Рассмотрим операции с многочленами подробнее.

Полиномиальная арифметика

Для тех, кто это подзабыл, приведем пример на деление.

Пример 1

Напомним также модульную арифметику многочленов. Многочлены называются сравнимыми по модулю многочлена p(x), если их разность делится на p(x) нацело. Поэтому для получения f(x)(mod p(x)) вам нужно просто разделить f(x) на p(x) и взять остаток от деления. Заметим, что если степень f(x) меньше степени p(x), то результатом будет просто f(x)

Пример 2

Замечательным свойством полиномиального представления кодов является возможность осуществить циклический сдвиг на одну позицию вправо простым умножением кодового многочлена степени n-1 на многочлен «x» и нахождения остатка от деления на x n + 1.

Пример 3

Порождающий многочлен

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

Tеорема

Пример 4

Соответствующее кодовое слово[011010111100010]. Итак, сообщение [0110110] кодировано в слово [011010111100010].

Алгоритм декодирования

Пример 4 (прод.)

Для кодового слова синдром, как известно, равен 0. В данном случае это не так, посланное слово было искажено помехой. В соответствии с описанной процедурой декодирования будем вычислять s i (x) = x i (x 2 + x 6 + x 8 )(mod g(x)) для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной двум (число ошибок t = 2 ).

s 1 = xs(x)(mod g(x)) = (x 3 + x 7 + x 9 )(mod g(x)) = x 3 + x 4 + x 5 + x 6 + x 7

s 2 = x 2 s(x)(mod g(x)) = (x 4 + x 8 + x 10 )(mod g(x)) = 1 + x + x 2 + x 5

s 3 = x 3 s(x)(mod g(x)) = (x 5 + x 9 + x 11 )(mod g(x)) = x + x 2 + x 3 + x 6

s 4 = x 4 s(x)(mod g(x)) = (x 6 + x 10 + x 12 )(mod g(x)) = x 2 + x 3 + x 4 + x 7

s 5 = x 5 s(x)(mod g(x)) = (x 7 + x 11 + x 13 )(mod g(x)) = 1 + x 3 + x 5 + x 6 + x 7

s 6 = x 6 s(x)(mod g(x)) = (x 8 + x 12 + x 14 )(mod g(x)) = x + 1

Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким

(x + x 2 + x 4 + x 6 + x 7 + x 8 + x 10 + x 13 ) + (x 10 + x 9 ) =

x + x 2 + x 4 + x 6 + x 7 + x 8 + x 9 + x 13

Этот многочлен соответствует вектору [011010111100010]. Чтобы восстановить само сообщение нам надо разделить кодовое слово на ПМ g(x) и получить

значит сообщение было [0110110].

IV. Размерность, порождающая и проверочная матрицы

c 1 (x) c 2 (x) = a 1 (x)g(x)a 2 (x)h(x) = a 1 (x)a 2 (x)f(x) = 0 (mod f(x)),

Рассмотрим два вектора:

и их произведение (вернее, соответствующих многочленов)

для каких-то c i из F. Свободный член произведения

т.к x n = 1 (mod f(x)). Теперь c 0 можно записать как скалярное произведение

где b’ теперь вектор, связанный с x n-t b(x). По отношению к b(x), b’ это вектор, полученный циклическим сдвигом b на t+1 позиций влево с последующим изменением порядка координат на противоположный.

Коэффициент при x 2 будет a (b 2 b 1 b 0 ). Этот вектор b’ получен из b сдвигом на 3 ( = 2 + 1) позиции влево (это ставит все координаты на старые места) и изменением порядка координат с последней на первую. b-вектор в коэффициенте при x получается из b сдвигом на 2 ( = 1 + 1) позиции влево, что дает (b 2 b 0 b 1 ) и изменением порядка следования (b 1 b 0 b 2 ).

Порождающая матрица для C’

Перепишем колонки G’ в обратном порядке, получим порождающую матрицу для C perp (она же проверочная для исходного кода)

Нетрудно проверить, что GH T = 0.

Заметим, что h R (x) = x k h(1/x), где k = deg h(x). Суммируя все вышесказанное, получим следующее.

V. Синдромы и охота на ошибки

где deg(r i (x)) i (x) = 0. Then

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

x 3 = (1)(x 3 + x + 1) + (1+ x)
x 4 = (x)(x 3 + x + 1) + (x + x 2 )
x 5 = (x 2 + 1)(x 3 + x + 1) + (1 + x + x 2 )
x 6 = (x 3 + x + 1)(x 3 + x + 1) + (1 + x 2 ).

Порождающая матрицаЗаметим, что строки R как раз остатки от деления.

Если разделить r(x) на g(x), то получим

r(x) = (x 3 + 1)g(x) + (x + x 2 ),

Так как n = 7 все ошибки веса 1 имеют циклический сдвиг на шесть 0’s и 6 > k = 4, исправляются все единичные ошибки..

Пример : g(x) = 1 + x 4 + x 6 + x 7 + x 8 порождает бинарный (15,7)-циклический код. Если минимальное расстояние 5(так), то t = 2. Некоторые (по меньшей мере) веса 2 маски ошибок могут содержать сдвиги не менее 7 0й и могут бытьотловлены. Если мы получили

r = (1100 1110 1100 010)

r(x) = (x + x 2 + x 4 + x 5 )g(x) + (1 + x 2 + x 5 + x 7 ).

Источник

Проверочный многочлен циклического кода

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

4.1 Основные понятия

Таблица 3

Таблица 4

(x) S(x) 1 R_g(x)[1] X R_g(x)[x] X 2 R_g(x)[x2] · · · · · · X+1 R_g(x)[x+1] X 2 +1 R_g(x)[x2+1] · · · · · ·

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

Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по mod 2, а затем по mod x n +1, если степень результата превышает степень (n-1).
Примеры.

Допустим, что длина кода n=7, то результат приводим по mod x 7 +1. При построении и декодировании циклических кодов в результате деления многочленов обычно необходимо иметь не частное, а остаток от деления.
Поэтому рекомендуется более простой способ деления, используя не многочлены, а только его коэффициенты (вариант 2 в примере). Пример. 1.
2.

4.2 Матричное задание кодов

4.4 Способы кодирования

4.5 Способы декодирования с обнаружением ошибок

Процедура декодирования циклического кода с обнаружением ошибок, по аналогии с процессом кодирования, использует два способа:
— при кодировании «классическим» способом декодирование основано на использовании свойства делимости без остатка кодового многочлена u (x) циклического (n,k)-кода на порождающий многочлен g(x). Поэтому алгоритм декодирования включает в себя деление принятого кодового слова, описываемого многочленом на g(x), вычисление и анализ остатка r(x). Если r(x)=0, то принятое кодовое слово считается неискаженным. Если r(x) № 0, то принятое кодовое слово стирается и формируется сигнал «ошибка».
— при кодировании способом МККТТ декодирование основано на свойстве получения определенного контрольного остатка R(x) при делении принятого кодового многочлена u (x) на порождающий многочлен. Поэтому, если полученный при делении остаток , то принятое кодовое слово считается неискаженным. Если остаток , то принятое кодовое слово стирается и формируется сигнал «ошибка».
Значение контрольного остатка определяется из выражения .

4.6 Способы декодирования с исправлением ошибок и схемная реализация декодирующих устройств

Таблица 5

4.7 Коды Рида-Соломона (РС)

Источник

Помехоустойчивое кодирование. Часть 1: код Хэмминга

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

Самый, пожалуй, известный код Хэмминга (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 — это то же самое что сложение, что в свою очередь, тоже самое что исключающее или. Поехали:

Нацело разделить не получилось, значит у нас есть ошибка (ну конечно же). Результат деления в таком случае нам без надобности. Остаток от деления является синдром, его размер равен размеру избыточности, поэтому мы дописали там ноль. В данном случае содержание синдрома нам никак не помогает найти местоположение повреждения. А жаль. Но если мы возьмём любое другое информационное слово, к примеру 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

Источник