Важным свойством циклических кодов является то, что все они строятся с помощью образующего полинома
Приведем методику построения циклического кода. Образующий полином
принимает участие в образовании каждой кодовой комбинации, поэтому комбинация кода делится на образующий полином без остатка. Однако без остатка делятся только те многочлены
(комбинации), которые принадлежат данному коду, т. е. образующий полином позволяет выбрать разрешенные кодовые комбинации из всех возможных. Если же при делении принятой кодовой комбинации циклического кода на образующий многочлен будет получен остаток, значит, имеет место ошибка. Таким образом, остатки от деления принятой комбинации на образующий полином являются опознавателями ошибок циклических кодов. Но данные остатки еще не указывают непосредственно на место ошибки в кодовой комбинации.
В циклических кодах идея исправления ошибок основывается на следующем. Ошибочная комбинация после
– определенного числа циклических сдвигов «подгоняется» под остаток таким образом, чтобы в сумме с остатком она давала бы исправленную комбинацию. Остаток при этом представляет собой разницу между искаженными и правильными символами, а единицы в остатке стоят на местах искаженных разрядов в «подогнанной» циклическими сдвигами комбинации. «Подгоняют» искаженную комбинацию до тех пор, пока число единиц в остатке не будет равно числу ошибок в коде. При этом, естественно, число единиц может быть равно числу ошибок
исправляемых данйым кодом (код исправляет три ошибки и в искаженной комбинации три ошибки) или меньше (код исправляет три ошибки, в принятой комбинации — одна ошибка).
1) Принятую комбинацию делят на образующий полином;
2) Подсчитывают количество единиц в остатке (вес остатка
допустимое число исправляемых данным кодом ошибок, принятую комбинацию складывают по модулю два с полученным остатком. Сумма дает исправленную комбинацию. Если
3) производят циклический сдвиг принятой комбинации влево на один разряд. Комбинацию, полученную в результате циклического сдвига, делят на образующий полином
Если в результате повторного деления
4) производят циклический сдвиг вправо на один разряд комбинации, полученной в результате суммирования последнего делимого с последним остатком. Полученная комбинация уже не содержит ошибок. Если после первого циклического Сдвига и последующего деления остаток получается таким, что его вес
5) повторяют операцию п. 3 до тех пор, пока не будет достигнуто
. В этом случае комбинацию, полученную в результате последнего циклического сдвига, суммируют с остатком от деления этой комбинации на образующий многочлен, а затем
6) производят циклический сдвиг вправо ровно на столько разрядов, на сколько сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получим исправленную комбинацию.
Пример. При передаче комбинаций 1001110 циклического кода, исправляющего одиночные ошибки
полученного с помощью образующего полинома
произошла ошибка в четвертом разряде. Принятая комбинация имеет вид 1000110. Процесс исправления ошибки следующий.
1. Делим принятую комбинацию на образующий полином:
2. Сравниваем вес полученного остатка
с числом исправляемых ошибок
3. Производим циклический сдвиг принятой комбинации на один разряд влево и деление на
4. Повторяем п. 3 до тех пор, пока не будет получено
5. Складываю по модулю два последнее делимое о последним остатком:
6. Производим циклический сдвиг комбинации, полученной в результате суммирования последнего делимого с последним остатком, вправо на четыре разряда (так как перед этим мы четырежды сдвигали принятую комбинацию влево):
Широкое распространение получил класс линейных кодов, которые называются циклическими. Название этих кодов происходит от их основного свойства: если кодовая комбинация
принадлежит циклическому коду, то комбинации
и т. д., полученные циклической перестановкой элементов, также принадлежат этому коду.
Общим свойством всех разрешенных кодовых комбинаций циклических кодов (как полиномов) является их делимость без остатка на некоторый выбранный полином, называемый производящим. Синдромом ошибки в этих кодах является наличие остатка от деления принятой кодовой комбинации на этот полином. Описание циклических кодов и их построение обычно проводят с помощью многочленов (полиномов). Цифры двоичного кода можно рассматривать как коэффициенты многочлена переменной х.
Поскольку любое число в произвольной системе счисления можно записать в виде
— основание системы счисления,
Отсюда видно, что кодовая комбинация длиной
описывается многочленом степени
. Однако запись кодовой комбинации в виде многочлена не всегда определяет длину кодовой комбинации
. Например, при
Кодовые комбинации циклического кода описываются полиномами, обладающими определенными свойствами. Последние определяются свойствами и операциями той алгебраической системы к которой принадлежит множество полиномов. В частности, в этой алгебраической системе, которая носит название поля Галуа (GF(x)), действие над коэффициентами полиномов (сложение, умножение) производится по модулю 2. Умножение полиномов должно производится по модулю некоторого полинома
Эти два условия определяют замкнутость указанных операций: их применение не приводит к кодовым комбинациям, длина которые больше длины заданного кода
Таким образом, степень полученного полинома
Умножение полиномов производится по модулю
Это означает, что в качестве результата умножения принимается остаток от деления обычного произведения полиномов на полином
Напомним, что умножение чисел по модулю q сводится к тому, что обычное произведение этих чисел делится на q и записывается остаток. Например,
имеет в остатке 3 Это число и является результатом умножения по модулю 5
Указанная операция над многочленами не приводит к появлению полинома с большей степенью, чем заданная длина кода.
Рассмотрим код с
не принадлежит коду с
Рассмотрим умножение по модулю
. При этом полином
должен иметь степень
и является результатом произведения полиномов
Он именуется вычетом по многочлену
Для того чтобы полиномы, отображающие кодовые комбинации циклического кода, имели нужные свойства, необходимо выполнение двух условий:
2) двучлен вида
должен делиться на
без остатка (имеется в виду обычная операция деления).
Такие полиномы в циклических кодах играют роль порождающих (производящих) полиномов; с их помощью строится заданный циклический код.
Поскольку неприводимый многочлен не может быть представлен в виде произведения многочленов более низших степеней, то проверить это можно простой подстановкой в него корней
. Например, имеем
можно разложить на множители, то это означает, что уравнение
. Прямой подстановкой этих корней можно убедиться, что в обоих случаях
т. е. этот полином неприводим. Существенно, что степень образующего многочлена
совпадает с числом проверочных разрядов
В циклических кодах разрешенными кодовыми комбинациями являются те, которые имеют нулевой вычет по модулю
т. е. делятся на образующий полином без остатка. Из всех возможных полиномов степени
только 2 полиномов
Они и образуют множество разрешенных кодовых комбинаций циклического кода.
Циклические коды являются блочными, равномерными и линейными Линейность кодов вытекает из того, что если кодовые слова принадлежат циклическому коду, то их линейная комбинация будет также принадлежать циклическому коду, т. е. обязательно делиться без остатка на образующий полином.
По сравнению с обычными линейными кодами (см. разд. 7 1) на разрешенные кодовые комбинации циклического кода накладывается дополнительное ограничение: делимость без остатка на порождающий полином. Это свойство существенно упрощает аппаратурную реализацию кода.
Обнаружение ошибок в циклическом коде производится делением принятой кодовой комбинации на кодовую комбинацию образующего полинома (вид его должен быть известен на приеме). Остаток от деления
играет роль синдрома. Если
то считается, что произошли ошибки. Если
Возможность исправления одиночной ошибки связана с выбором образующего полинома
Точно так же, как и в обычных линейных кодах вид синдрома в циклических кодах зависит от места, где произошла ошибка. В данном случае в качестве синдромов рассматриваются различные остатки
от деления полинома ошибки на образующий полином
Среди множества полиномов
существуют так называемые примитивные полиномы, для которых существует зависимость
. Это означает, что при возникновении ошибки в одном из
разрядов кодовой комбинации число различных остатков также будет равно
. Например, образующий полином
различных остатков, а образующий полином
только пять различных остатков.
Циклические коды являются разновидностью линейных групповых кодов и относятся к систематическим кодам. Первоначально были созданы для упрощения процедуры декодирования. Однако высокая эффективность к обнаружению ошибок таких кодов обеспечила их широкое применение на практике. Двоичный вектор циклического кода удобно рассматривать не как комбинацию нулей и единиц, а в виде полинома некоторой степени
где х — основание системы счисления,
коэффициенты, принадлежащие множеству
Пример. Двоичный вектор
Представление двоичных векторов в виде полиномов позволяет свести действие над векторами к действиям над многочленами. При этом:
сложение многочленов сводится к сумме по модулю 2 коэффициентов при равных степенях переменной
Пример. Найти сумму многочленов
Найти произведение многочленов
Выполнить деление многочленов
Основным свойством циклических кодов является следующее: если вектор принадлежит циклическому коду, то любой вектор, полученный из рассматриваемого с помощью циклических сдвигов, также принадлежит циклическому коду.
Идея построения циклических кодов базируется на понятии неприводимого многочлена. Многочлен называется неприводимым, если он делится только на самого себя и на единицу, и не делится ни на какой другой многочлен. Иными словами, неприводимый многочлен нельзя представить в виде произведения многочленов низших степеней. На неприводимый многочлен без остатка делится многочлен
. Неприводимые многочлены играют в теории циклических кодов роль образующих полиномов. Виды неприводимых многочленов различных степеней приведены в
Примеры неприводимых многочленов:
Векторы циклического кода строятся в соответствий со следующими правилами. Пусть
— любой двоичный вектор некоторого натурального кода;
— одночлен степени
неприводимый полином степени
Тогда любой вектор
Таким образом, любой вектор циклического кода может быть образован умножением некоторого вектора натурального двоичного кода на одночлен степени
с добавлением к полученному произведению
При построении циклических кодов указанным способом расположение информационных разрядов в каждом векторе кода строго упорядочено — они занимают
старших разрядов вектора кода, а остальные
Пример. Вектор натурального двоичного кода имеет вид
В результате деления полинома
Циклический код, как и всякий систематический код, удобно задавать в матричном виде с помощью порождающей матрицы
— транспонированная единичная йатрица формата
— матрица проверочных разрядов, образованная остатком
Зададим порождающую матрицу
циклического кода длиной
информационными разрядами и порождающим полиномом
Очевидно, заготовка для порождающей матрицы имеет вид
Для нахождения строк проверочных разрядов матрицы
Длина вектора циклического кода
В результате получаем порождающую матрицу С:
Любой вектрр циклического кода получается как сумма по моду
Пример. Построить все векторы циклического кода, заданного порождающей матрицей
Код представлен в табл. 13.5.
Необходимо отметить, что каждый циклический код, заданный некоторой порождающей матрицей, можно представить в нескольких вариантах, отличающихся друг от друга длиной
и количеством информационных разрядов
(при одинаковых обнаруживающих способностях). Эти варианты так называемых укороченных циклических кодов получаются вычеркиванием последних строк и такого же количества столбцов слева в порождающей матрице
циклического кода. При этом число проверочных разрядов остается неизменным, а длина кода и число его информационных разрядов уменьшаются соответственно на величину, равную числу вычеркнутых строк и столбцов порождающей матрицы.
Пример, Циклический код задан своей порождающей матрицей
Вычеркнем из шесть последних строк и шесть первых слева столбцов. Получим порождающую матрицу
Характеристики (в смысле обнаружения ошибок) полученного кода такие же, как и циклического кода, представленного порождающей матрицей
Построение циклических кодов с заданными параметрами связано с выбором образующего неприводимого полинома. Образующий полином выбирается исходя из следующего условия: степень полинома должна быть равна числу проверочных разрядов циклического кода.
На практике часто возникает задача построения циклического кода заданной мощности и заданной обнаруживающей и корректирующей способностей.
Рекомендации для построения кода следующие:
1. Так как мощность
3. По справочникам находятся все неприводимые полиномы степени
4. Для одного из непроводимых многочленов (следует выбирать многочлен с максимальным числом членов) степени
строится порождающая матрица циклического кода. Каждый вектор
— полином информационного вектора порождающей матрицы;
— остаток от деления
5. Построенная порождающая матрица проверяется на выполнение следующих условий:
а) вес в смысле Хэмминга любого вектора
порождающей матрицы должен удовлетворять соотношению
б) вес в смысле Хэмминга проверочного вектора, являющегося суммой по модулю 2 любых двух проверочных векторов
6. Если порождающая матрица циклического кода удовлетворяет всем приведенным условиям, то выписываются все векторы циклического кода и определяется
в соответствии с известными правилами для линейных групповых кодов. Если код не соответствует требованиям, то выбирается другой порождающий полином той же степени
Построим циклический код мощностью 16 и корректирующей с по собностью
I. В соответствии с первым пунктом рекомендаций по построению циклических кодов, определяем значение
Там как код корректирует однократные ошибки, то
определяем значение по
3» По справочникам находим все неприводимые полиномы степени
4. Выбираем в качестве образующего полином
Каждый информационный вектор из матрицы
Определяем полностью все векторы порождающей матрицы, используя формулу
Так как длина вектора циклического кода
(см. формат порождающей матрицы
Аналогично находим все остальные векторы порождающей мат рицы
В результате получена порождающая матрица С? циклического кода
5. Полученная порождающая матрица удовлетворяет всем необходимым условиям. Поэтому строим циклический код полностью (табл. 13.6). Как следует из таблицы, код имеет
Замечания. При использовании неприводимого полинома
Обнаружение ошибок с помощью циклических кодов производится следующим образом. Любой вектор циклического кода делится на образующий полином без остатка. Поэтому критерием наличия ошибки в векторе циклического кода является появление ненулевого остатка от деления вектора циклического кода на образующий полином. Ненулевой остаток является опознавателем ошибки в векторе циклического кода, однако его вид не указывает на место расположения ошибки в кодовом векторе. Исправление ошибок базируется на следующем алгоритме:
1. Принятый кодовый вектор разделить на образующий полином.
2. Подсчитать число единиц в полученном остатке.
Если число единиц не превышает корректирующей способности кода, то принятый вектор сложить по модулю 2 с полученным остатком. Результат суммирования даст исправленный кодовый вектор. Если число единиц остатка больше корректирующей способности кода, то осуществить циклический сдвиг искаженного вектора влево на один разряд, а затем произвести деление на образующий полином. Если полученный остаток содержит единиц не больше корректирующей способности циклического кода, то произвести суммирование сдвинутого циклически вектора с остатком. Результат суммирования сдвинуть циклически на один разряд вправо. Полученный вектор уже не содержит ошибок и является вектором циклического кода.
3. Если после первого циклического сдвига и последующего деления остаток содержит единиц больше, чем корректирующая способность кода, то повторять процедуру
Пусть циклический код задан своей порождающей матрицей С и образующим полиномом
в 3, т. е. корректирует ошибки кратности
Пусть вместо вектора 0001101 принят вектор 0011101. Для исправления ошибки осуществляем следующие действия. Принятый вектор записываем в виде полинома:
затем делим на
Полученный в результате деления остаток
содержит три единицы, что больше, чем корректирующая способность кода. Поэтому делаем циклический сдвиг влево на один разряд принятого кодового вектора. В результате имеем
Осуществляем деление на
содержит две единицы, что больше, чем корректирующая способность кода. Поэтому делаем еще один циклический сдвиг влево на один разряд принятого кодового вектора. В результате имеем
Полученный остаток снова содержит две единицы, поэтому делаем еще один циклический сдвиг влево на один разряд и получаем
содержит одну единицу, что равно корректирующей способности кода. Осуществляем суммирование вектора 110100) о последним остатком;
и сдвигаем циклически полученный вектор на три разряда вправо. Имеем
Определим необнаруживаемые циклическими кодами ошибки. Представим векторы одиночных ошибок (длина вектора ошибки равна длине вектора циклического кода) в виде единичной транспонированной матрицы
— длина циклического кода. К такой матрице допишем справа матрицу от деления каждого вектора ошибок (представленного полиномом) на образующий полином циклического кода заданной степени
Дописываемая матрица называется матрицей остатков и содержит
столбцов. В итоге получим матрицу ошибок
Рассмотрим ее построение на конкретном примере. Пусть циклический код задан порождающей матрицей
Тогда матрица ошибок М имеет вид
Матрицу остатков, являющуюся частью матрицы М, разобьем на две части: первая содержит остатки от деления одночленов
вторая — остатки от деления одночленов
на порождающий полином. Очевидно, в первой части матрицы остатков сами одночлены
может быть построена чисто формально без проведения вычислений. Как следует из матрицы
каждому вектору одиночной ошибки соответствует свой остаток. Очевидно, приводимый циклический код обнаруживает все однократные ошибки, так как матрица
имеет ненулевые остатки. Обнаруживаются также и двухкратные ошибки. В этом легко убедиться, сложив по модулю 2 любые два вектора из
Получится ненулевой остаток (остаток вектора двухкратной ошибки равен сумме по модулю 2 остатков слагаемых векторов одиночной ошибки). Для случая трехкратных ошибок нужно сложить по три вектора из
В этом случае не обнаруживаются комбинации ошибок, возникающие в разрядах
Из общего количества 35 трехкратных ошибок не обнаруживается всего лишь 7 ошибок, Аналогично, четырехкратных необнаруживаемых ошибок будет также
Наконец, рассматриваемым циклическим кодом не обнаруживается единственная семикратная ошибка
Аналогичный линейный групповой код, заданный порождающей матрицей
очевидно имеет матрицу ошибок
полностью аналогичную матрице одиночных ошибок циклического кода. Следовательно, в плане необнаруживаемых ошибок приведенные два кода полностью эквивалентны.
Принципы обнаружения и исправления ошибок в принятой кодовой комбинации циклического кода
Переданная кодовая комбинация двоичного циклического кода, представленная полиномом F(x), из-за искажений единичных элементов в каналах связи может быть принята с ошибками и иметь вид некоторого полинома Н(х). Если просуммировать по mod2 одноименные разряды F(х) и Н(х), то получим
где Е(х) – полином ошибок.
Разрядность полинома ошибок такая же, как и разрядность комбинации F(х) циклического кода. При этом ненулевые разряды в Е(х) указывают на ошибочные элементы в принятой кодовой комбинации Н(х). При отсутствии ошибок полином Е(х) состоит из одних нулей.
Принимая во внимание вышеприведенные обозначения, принятую кодовую комбинацию можно представить следующим образом:
Для обнаружения ошибок в принятой кодовой комбинации Н(х) следует разделить Н(х) на порождающий многочлен Р(х). Результат деления укажет на наличие или отсутствие ошибки в принятой кодовой комбинации Н(х). Если деление дает нулевой остаток, то ошибки отсутствуют или не обнаружены. Если же в результате деления полинома Н(х) на порождающий многочлен Р(х) остаток R’(х) отличен от нуля , то это означает что принятая кодовая комбинация Н(х) содержит ошибки (рис 2).
Рис.2. Схема выявления ошибок в принятой кодовой комбинации H(x)
Вид ненулевого остатка R’(x), называемого синдромом ошибки S(х), имеет однозначное соответствие с ошибочным разрядом и видом полинома однократной ошибки Е(х) для всех кодовых комбинаций Н(х) циклического кода. Например, для циклического кода (9,5) при заданном порождающем многочлене P(x)= x4 + x + 1 остаток R’(x) всегда будет иметь вид S(х)=0011, если ошибка возникла в пятом разряде входной кодовой комбинации, т.е. в младшем информационном разряде, независимо от вида переданной кодовой комбинации F(х).
Следует отметить, что остаток R’(x), получаемый при делении полинома Н(х), на порождающий многочлен Р(х), имеет такой же вид, как и остаток от деления Е(х) на Р(х), поскольку полином F(х) делится на Р(х) без остатка.
Кратность обнаруживаемых ошибок в принятой кодовой комбинации циклического кода определяется минимальным кодовым расстоянием dmin этого кода. Для циклического кода (9,5) значение dmin=3, что обеспечивает гарантированное обнаружение всех однократных и двукратных ошибок. Кроме того, код позволяет обнаруживать часть ошибок более высокой кратности, начиная с веса, равного dmin и более. Код не обнаруживает ошибки, если полином ошибки имеет вид разрешенной кодовой комбинации.
Номер такта, на котором в регистре-делителе возникает “особая” кодовая комбинация, указывает место ошибочного разряда в принятой кодовой комбинации Н(х). При считывании этой комбинации из буферного регистра ошибочный разряд должен быть исправлен (инвертирован).
Циклический код (9,5) гарантированно исправляет только однократные ошибки. Ошибки более высокой кратности код (9,5) не исправляет.
Заметим также, что деление полинома Н(х) на многочлен Р(х) и считывание информации из буферного регистра после 9го такта целесообразно осуществлять под действием “быстрых” тактовых импульсов. Это позволит без задержки принять из канала связи и обработать следующую кодовую комбинацию Н(х).
1. Структурная схема кодирующего и декодирующего устройства ( циклич. Коды ).
• Исходным кодом для циклического кодирования
является двоичный код на все сочетания. Число
его комбинаций M=2m. При этом число разрядов
m исходного кода определяет число
информационных символов.
• При описании циклического кода наиболее
удобной является запись его двоичной
комбинации в виде многочлена F(x) некоторой
фиктивной переменной x:
где bk-1 ÷ b0 – контрольные символы; bn-1 ÷ bk информационные символы.
• Строки матрицы контрольных символов Rm,k ,
соответствуют остаткам Rj(x).
• В целом строки образующей матрицы Fm,n
представляют собой кодовые полиномы Fj(x),
определяемые по алгоритму
F(x)= xk G(x) + R(x)
Таблица 2
№ варианта
Принятый циклический код
17
1010000001
18
1010000000
19
1010000010
20
1010111111
21
1011100110
22
1010101010
23
1010110011
24
1010111000
25
1011001011
26
1011011110
27
1011110100
28
1010011001
29
1011100001
30
1011101111
Проверочная матрица
• Циклический код можно описать не только
посредством образующей матрицы, но и с помощью
проверочной матрицы Hk,n. Чаще всего на практике
применяется циклическая форма этой матрицы.
Первая строка такой матрицы зависит от вида
проверочного полинома H(x), а остальные строки
получают, циклически сдвигая вправо первую
строку.
• Вид первой строки проверочной матрицы в
циклической форме связан с видом проверочного
полинома следующим образом. Полином H(x)
представляют в виде кодовой комбинации. Запись
этой комбинации в обратном порядке и
приписывание к ней справа k −1 нулевых символов
дает первую строку проверочной матрицы Hk,n .
• Старшая степень образующего полинома
определяет число контрольных символов.
Например, выбирая для исходного
четырехразрядного кода в качестве образующего
полинома неприводимый многочлен
P(x) = x3 + x + 1, получим для циклического кода
число контрольных символов k=3 и длину
кодового слова n=4+3=7. Полином
называется проверочным или генераторным
полиномом. Высшая степень проверочного
полинома равна числу информационных
разрядов кода m.
Построение циклического кода
• Старшая степень образующего полинома равна
числу контрольных символов. Поэтому первым
шагом при выборе образующего полинома
является определение числа контрольных
разрядов. Это число выбирают на основании
оценок Хемминга:
при d нечетном
при d четном
Пример
• Задание. Построить 9-разрядный циклический
код числа(30)10 и осуществить декодирование
его при безошибочной передаче и при
искажении в седьмом разряде, используя
образующий полином P(x) = x3+x2+1.
a) Так как используется образующий полином 3-ей
степени, то количество проверочных разрядов
k =3.
b) Число информационных разрядов исходя из
заданной 9-значности кода:
m = n – k = 9 – 3 = 6.
Задание для самостоятельной работы
• Написать программу кодирования сообщений с
помощью циклического корректирующего кода.
• Входные данные:
a) Значность кода n и количество
информационных разрядов m;
b) Коэффициенты образующего полинома степени
n-m;
c) Сообщение длиной m двоичных разрядов;
• Выходные данные: кодовая
последовательность (m информационных,
потом n-m корректирующих разрядов) для
входного сообщения.
Соответствия искаженных разрядов и
остатков от деления кодового полинома
на образующий P(x) = x3+x2+1
Разряды
Остаток
7
110
6
011
5
111
4
101
3
100
2
010
1
001
Построение циклического кода
• Построение циклического кода производится,
исходя из разрядности m исходного кода и
требуемой от циклического кода
корректирующей способности, задаваемой в
виде числа обнаруживаемых r и числа
исправляемых s ошибок.
• По сути дела построение кода сводится к выбору
образующего полинома P(x) и составлению
образующей матрицы. Корректирующая
способность зависит от кодового расстояния d.
Пример
• Составим проверочную матрицу для условий
старого примера, когда n=7, m=4, k=3 и
P(x) = x3+x+1. Проверочный полином:
Тогда первая строка проверочной матрицы
примет вид 1110100, а в целом проверочная
матрица будет иметь форму
Таблица 1
№ варианта
Передаваемое число
Искаженные при передаче разряды
1
32
4; 1
2
33
5; 2
3
34
6; 3
4
35
7; 1
5
36
4; 2
6
37
5; 3
7
38
6; 1
8
39
7; 2
9
40
4; 3
10
41
5; 1
11
42
6; 2
12
43
7; 3
13
44
4; 1
14
45
5; 2
15
46
6; 3
16
47
7; 1
Пример
• Соотношения для проверок на четность и
уравнения для формирования контрольных
символов принимают вид
d1=b6⊕b5⊕b4⊕b2=0; b2=b6⊕b5⊕b4
d2=b5⊕b4⊕b3⊕b1=0; b1=b5⊕b4⊕b3
d3=b4⊕b3⊕b2⊕b0=0; b0=b4⊕b3⊕b2
• Сущность операции умножения по модулю (xn +1)
состоит в том, что многочлены F(x) и H(x)
перемножаются по обычным правилам с
приведением подобных членов по модулю 2. Если
старшая степень произведения не превышает (n −1),
то оно является результатом умножения по модулю
(xn +1) . В противном случае многочлен
произведения делится на двучлен (xn +1) и
получившийся при этом остаток является
результатом умножения по модулю (xn +1) .
• На названных выше двух свойствах основано
обнаружение и исправление ошибок при передаче
циклических кодов по каналам связи. Эти же
свойства лежат в основе построения циклических
последовательностей и технической реализации
кодирующих устройств.
Пример
c) Построение информационного полинома.
Определяем двоичный код передаваемого числа
(30)10=(011110)2 для m = 6.
Тогда информационный полином
G(x) = x4+x3+x2+x.
d) Определение проверочной комбинации.
Она определяется как остаток от деления по
модулю 2 сдвинутого на k = 3 разряда влево
информационного полинома G(x) на образующий
полином P(x). Деление по модулю 2 предполагает
последовательные сдвиги и поразрядное сложение
по модулю 2, т.е. проверку на неравнозначность,
что соответствует 0 при равенстве одноименных
разрядов и 1 при их отличии.
Пример
• Информационный полином G(x) в первых шести
(m=6) разрядах F(x) определяет передаваемое
число:
G(x) = 0∙x5+1∙x4+1∙x3+ 1∙x2+1∙x1+0∙x0 =
=1∙24 + 1∙23 + 1∙22 + 1∙21 =30
• При искаженной передаче в 7 разряде кодовая
комбинация будет иметь вид F(x) =010110011.
• Кодовые комбинации F(x) циклического кода
помимо общих для групповых кодов
ограничений удовлетворяют следующим двум
условиям:
1.
, т.е. без остатка делятся на
образующий полином;
2. F(x) ⋅ H(x) = 0 по mod(xn +1),
т.е. при умножении на проверочный полином
дают тождественный нуль по модулю двучлена
(xn +1).
Пример
• Если требуется закодировать в циклическом
коде, исправляющем однократные ошибки (s=1),
исходные четырехразрядные двоичные слова
(m=4), то минимальное кодовое расстояние
d ≥ 2s+1=3 и с использованием оценки Хэмминга
получим
или с учетом m=4 : 2k ≥1+m+k
• Этому неравенству удовлетворяет наименьшее
значение k=3. Тогда общая длина кодовой
комбинации n=m+k=7.
Таблица 1
№ варианта
Передаваемое число
Искаженные при передаче разряды
17
48
4; 2
18
49
5; 3
19
50
6; 1
20
51
7; 2
21
52
6; 3
22
53
5; 1
23
54
6; 2
24
55
7; 3
25
56
5; 1
26
57
6; 2
27
58
6; 1
28
59
7; 2
29
60
6; 3
30
61
7; 1
• С помощью образующей матрицы могут быть
получены все M= 2m кодовых комбинаций
циклического кода путем суммирования строк
матрицы F4,7 по модулю 2 в различных сочетаниях.
• Образующую матрицу циклического кода можно
также построить другим способом. Процесс
построения формализуется следующим образом.
Исходя из числа информационных разрядов m,
составляется единичная матрица Im. К ней справа
приписывают матрицу контрольных символов Rm,k ,
которая находится с помощью следующего
формального приема. Единица с рядом нулей
делится на образующий полином и выписываются m
промежуточных остатков деления. Эти остатки,
записанные в обратном порядке, образуют матрицу
контрольных символов.
Построение циклического кода
• Образующий полином следует искать по таблицам
разложения двучлена (xn +1) на неприводимые
сомножители. Полином P(x) должен удовлетворять двум
условиям :
a) степень полинома равна k;
b) число ненулевых членов больше или равно d.
• Выбранный полином необходимо проверить на
соответствие требуемой корректирующей способности. С
этой целью единица с нулями делится на образующий
полином. Полученные остатки должны удовлетворять
следующим условиям :
a) число различных остатков больше или равно m;
b) вес или число единиц каждого остатка больше или равно
(d-1);
c) остатки должны отличаться друг от друга не менее чем в
(d-2) разрядах.
Пример
• Особенность кодовых полиномов, используемых
при циклических кодах в том, что полученный
полином F(x) делится без остатка на
образующий полином P(x). Если у принятого
полинома после его проверки остаток
отсутствует, то значит кодовая комбинация
принята без искажений. Ненулевой остаток
указывает на наличие ошибок и их места. Для
полинома P(x) = x3+x2+1 одиночные ошибки в
разрядах приводят к образованию остатков в
соответствии с Таблицей 3.
Таблица 2
№ варианта
Принятый циклический код
1
1000000101
2
1000001011
3
1000010111
4
1000010110
5
1000110111
6
1000001010
7
1001110000
8
1000111100
9
1001000000
10
1001001011
11
1001011101
12
1001001000
13
1001000001
14
1000101100
15
1001110111
16
1001111001
Пример
• Разложение двучлена степени n=7:
x7+1= (x+1)(x3+x+1)(x3+x2+1). В качестве
образующего можно выбрать любой из
неприводимых многочленов третьей степени,
так как каждый из них имеет по три (d=3)
ненулевых члена. Выберем полином
P(x) = x3+x+1. Остатки от деления единицы с
нулями на выбранный полином удовлетворяют
перечисленным выше требованиям. Таким
образом, полином P(x) = x3+x+1 обеспечивает
при построении циклического кода (7,4) кодовое
расстояние d=3.
Циклический код. Пример
работы алгоритма.
• Наиболее целесообразно циклический код
представлять в виде разделимого (n, m) кода.
Тогда алгоритм кодирования определяется
выражением
F(x)= xk G(x) + R(x), где R(x) – остаток от деления
произведения xk G(x) на образующий полином
P(x), а именно
,
где Rem ⎯ обозначение остатка от деления.
Пример
Выписывая остатки снизу вверх (в обратном
порядке), получим матрицу контрольных
символов R4,3 и образующую матрицу F4,7:
и
Задание для выполнения
• Используя образующий полином P(x) = x3+x2+1
сформируйте 9-разрядный циклический код
(Таблица 1).
• Осуществите его декодирование при
неискаженном получении сообщения.
• Осуществите декодирование при искажениях в
указанном разряде.
• Определите (Таблица 2) десятичное значение
передаваемого числа по принятой кодовой
комбинации циклического кода с образующим
полиномом P(x) = x3+x2+1.
• Построение циклического кода базируется на
использовании так называемого образующего или
порождающего полинома P(x) .
• В качестве образующего обычно выбирается
неприводимый многочлен, т.е. такой, который
делится только сам на себя и на единицу.
• Доказано, что полином P(x) порождает циклический
код длиной n, если он является сомножителем в
разложении двучлена ( xn +1) на неприводимые
многочлены.
• Не исключен выбор в качестве образующего
полинома произведения двух или более
неприводимых многочленов этого разложения. Но
тогда циклический код будет обладать худшими
параметрами с точки зрения мощности множества
кодовых комбинаций.
• Множество кодовых комбинаций называется
циклическим кодом, если циклический сдвиг
любой комбинации этого множества на любое
число разрядов влево или вправо приводит к
комбинации из данного множества.
• Циклические коды относятся к числу групповых
кодов, у которых каждая комбинация кодируется
самостоятельно в виде блока длиной n. Блок
содержит m информационных и k контрольных
символов. Длина кодовой комбинации n=m+k.
• Если в комбинации кода можно определенно
указать позиции, занимаемые информационными и
контрольными символами, то код называется
систематическим или разделимым, в противном
случае — несистематическим или неразделимым.