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

Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации двоичных символов в передаваемом сообщении могут быть получены путем операции циклического сдвига некоторого исходного слова: Обычно кодовые комбинации циклического кода рассматривают не в виде последовательности нолей и единиц, а в виде полинома некоторой степени . Любое число в любой позиционной системе счисления можно представить в общем виде как: где х - основание системы счисления; а - цифры данной системы счисления; п-1, п-2,... - показатель степени, в которую возводится основание, и одновременно порядковые номера, которые занимают разряды. Для двоичной системы х=2, а а либо «О», либо «1». Например, двоичную комбинацию 01001 можно записать в виде полинома от аргумента х: При записи кодовой комбинации в виде многочлена единица в 1-м разряде записывается членом х", а ноль вообще не записывается. Представление кодовых комбинаций в виде многочленов позволяет установить однозначное соответствие между ними и свести действия над комбинациями к действию над многочленами. Так, сложение двоичных многочленов сводится к сложению по модулю 2 коэффициентов при равных степенях переменной. Например, Умножение производится по обычному правилу умножения степенных функций, однако полученные коэффициенты при данной степени складываются по модулю 2. Например, Деление также осуществляется как обычное деление многочленов; при этом операция вычитания заменяется операцией сложения по модулю 2: Как было отмечено выше, коды названы циклическими потому, что циклический сдвиг а п ^ а л Л,..., а 2 ,а 1 ,а д1 а п1 разрешенной комбинации а п (, а п _ 2 ,...,а 1 ,а 0 также является разрешенной комбинацией. Такая циклическая перестановка при использовании представлений в виде полиномов образуется в результате умножения данного полинома на х. Если У(х)=а пЛ х п1 + а п2 х п " 2 +... + а { х+а 0 , то У(х)х = а п] х п + а п 2 х п " 1 +... + а х х 2 + а^х. Чтобы степень многочлена не превышала п-1, член х" заменяется единицей, поэтому: Например, имеем кодовую комбинацию 1101110->х в +х 5 +х 3 +.х г -1-х. Сдвинем ее на один разряд. Получим: Что то же самое, что и умножения исходного полинома на х: Теория построения циклических кодов базируется на разделах высшей алгебры, изучающей свойства двоичных многочленов. Особую роль в этой теории играют так называемые неприводимые многочлены, т. е. полиномы, которые не могут быть представлены в виде произведения многочленов низших степеней. Такой много- член делится только на самого себя и на единицу. Из высшей алгебры известно, что на неприводимый многочлен делится без остатка двучлен х"+1. В теории кодирования неприводимое многочлены называются образующими полиномами, поскольку они «образуют» разрешенные кодовые комбинации (неприводимые полиномы табулированы, см. табл. 8.4) (9]. Идея построения циклического кода сводится к тому, что полином, представляющий информационную часть кодовой комбинации, нужно преобразовать в полином степени не более п-1, который без остатка делится на образующий полином Р(х). Существенно при этом, что степень последнего соответствует числу разрядов проверочной части кодовой комбинации. В циклических кодах все разрешенные комбинации, представленные в виде полиномов, обладают одним признаком: делимостью без остатка на образующий полином Р(х). Построение разрешенной кодовой комбинации сводится к следующему: 1. Представляем информационную часть кодовой комбинации длиной к в виде полинома О(х). 2. Умножаем О(х) на одночлен У и получаем 0(х)х г, т. е. производим сдвиг ¿-разрядной кодовой комбинации на г разрядов. 3. Делим многочлен О (х)х" на образующий полином Р(х), степень которого равна г. В результате умножения О(х) на х г степень каждого одночлена, входящего в О(х), повышается на г. При делении произведения х г О[х) на образующий полином степени г получается частное С(х) такой же степени, что и 0{х). Результаты этих операций можно представить в виде: (8.28) где Щх) -остаток от деления 0(х)х г на Р(х). Поскольку С(х) имеет такую же степень, что и 0{х), то С(х) представляет собой кодовую комбинацию того же ¿-разрядного кода. Степень остатка не может быть, очевидно, больше степени образующего полинома, т. е. его наивысшая степень равна г-1. Следовательно, наибольшее число разрядов остатка не превышает г. Умножив обе части (8.28) на Р(х), ползшим: (8.29) (знак вычитания заменяется знаком сложения по модулю 2). Очевидно, что F(x) делится на Р(х) без остатка. Полином F(x) представляет собой разрешенную кодовую комбинацию циклического кода. Из (8.29) следует, что разрешенную кодовую комбинации циклического кода можно получить двумя способами: умножением кодовой комбинации простого кода С(х) на образующий полином Р(х) или умножением кодовой комбинации 0{х) простого кода на одночлен х г к добавлением к этому произведению остатка Р(х), полученного в результате деления произведения на образующий полином Р(х). При первом способе кодирования информационные и проверочные разряды не отделены друг от друга (код получается неразделимым). Это затрудняет практическую реализацию процесса декодирования. При втором способе получается разделимый код: информационные разряды занимают старшие позиции, остальные п-к разряды являются проверочными. Этот способ кодирования широко применяется на практике. Пример 3. Дана кодовая комбинация 0111. Построим циклический код с d o = 3. Решение. На первом этапе исходя из требуемого d o = 3 определим длину кода л и количество проверочных элементов к. Для этого воспользуемся таблицей 8.6.1. Для заданной четырехразрядной кодовой комбинации N-16. Тогда для d = 3 из соотношения 16(табл. 8.3) находим п - 7, соответственно, к = п - т - = 7 - 4 = 3. Следовательно, необходим код (7,4). По таблице образующих полиномов (табл. 8.4) при к = 3 определяем Р(х) = х 3 + х 2 + 1. Далее: 1) для сообщения 0111 имеем О(х) = х 2 + х + 1; 2) умножаем 0(х) на х 3 (так как г = 3): О(х) х 3 = (х 2 -I- х + 1) х 3 = х 5 + х 4 + х 3 ; 3) делим (Э(х)х 3 на Р(х): 4) получаем: ^(х) = О (х) х 3 0 Я (х) = х 5 + х 4 + х 3 + 1. Этот полином соответствует кодовой комбинации: Все указанные операции можно производить и над двоичными числами: Таблица 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001. Построим теперь разрешенную кодовую комбинацию первым способом: F(x)=C(x)P(x). Произведем умножение, представляя полиномы двоичными числами: Видно, что в полученной кодовой комбинации нельзя выделить информационные и проверочные разряды. Обнаружение ошибок при циклическом кодировании сводится к делению принятой кодовой комбинации на тот же образующий полином, который использовался при кодировании (его вид должен быть известен на приеме). Если ошибок в принятой кодовой комбинации нет (или они такие, что данную передаваемую кодовую комбинацию превращают в другую разрешенную), то деление на образующий полином будет выполнено без остатка. Если при делении получится остаток, то это и свидетельствует о наличии ошибки. Пример 4. В качестве разрешенной кодовой комбинации возьмем кодовую комбинацию, полученную в предыдущем примере: Р(х)=х 5 +х 4 + х 3 + 1, а Р(х) = х 3 + х 2 +1, или в двоичном виде Е(0,1) = 0111001; Р(0,1) = 1101. Допустим, что в информационной части произошла ошибка в старшем (7-м) разряде (разряды счита- ем справа налево). Принятая кодовая комбинация имеет вид 1111001. Произведем операцию обнаружения ошибки: Наличие остатка 110 свидетельствует об ошибке. Циклические коды находят большое применение в системах передачи информации. Например, в широко распространенном модемном протоколе \7.42 для кодирования кодовых групп используется образующий полином д(Х)= X 16 + X" -2 + X 5 + 1, что эквивалентно коду 1 0001 0000 0010 0001, а также образующий полином более высокого порядка д(Х) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X 4 + X 2 + 1. 8.6.

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

Циклические коды относятся к числу блоковых систематических кодов, в которых каждая комбинация кодируется самостоятельно (в виде блока) таким образом, что информационные k и контрольные т символы всегда нах

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

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

Циклические коды -- это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды Хэмминга, но в целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, возникающих при передаче кодовых комбинаций по каналу связи. Циклический код относится к систематическим блочным (n, k)-кодам, в которых k первых разрядов представляют собой комбинацию первичного кода, а последующие (n ? k) разрядов являются проверочными.

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

Многочлен (полином), который можно представить в виде произведения многочленов низших степеней, называют приводимым (в данном поле), в противном случае -- неприводимым. Неприводимые многочлены играют роль, сходную с простыми числами в теории чисел. Неприводимые многочлены Р (Х) можно записать в виде десятичных или двоичных чисел либо в виде алгебраического многочлена.

Процесс циклического кодирования

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

В качестве информационных символов k для построения циклических кодов берут комбинации двоичного кода на все сочетания. В общем случае, если заданную кодовую комбинацию Q(x) умножить на образующий многочлен Р(х), получиться циклический код, обладающий теми или иными корректирующими свойствами в зависимости от выбора Р(х). Однако в этом коде контрольные символы m будут располагаться в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно значительно упростить, если контрольные символы приписать в конце, то есть после информационных символов. Для этой цели целесообразно воспользоваться следующим методом:

Умножаем кодовую комбинацию G(x), которую нужно закодировать, на одночлен Х m , имеющий ту же степень, что и образующий многочлен Р(х);

Делим произведение G(x)Х m на образующий многочлен Р(х m):

где Q(x) - частное от деления; R(x) - остаток.

Умножая выражение (2.1) на Р(х) и перенося R(x) в другую часть равенства без перемены знака на обратный, получаем:

Таким образом, согласно равенству (2.2), циклический код, то есть закодированное сообщение F(x), можно образовать двумя способами:

Умножение одной кодовой комбинаций двоичного кода на все сочетания на образующий полином Р(х);

Умножением заданной кодовой комбинации G(x) на одиночный многочлен Х m , имеющий туже степень, что и образующий многочлен Р(х), с добавлением остатка R(x), полученного после деления произведения G(x)Х m на образующий многочлен Р(х).

Кодирование сообщения

Требуется закодировать кодовую комбинацию 1100, что соответствует G(x)=х 3 +х 2 с помощью Р(х)=х 3 +х+1.

Умножаем G(x) на Х m , который имеет третью степень, получим:

Разделив произведение G(x)Х m на образующий многочлен Р(х m), согласно (2.1) получим:

или в двоичной эквиваленте:

Таким образом, в результате получаем частное Q(x) той же степени, что и G(x):

Q(x)=x 3 +x 2 +x>1110

и остаток:

В итоге комбинация двоичного кода, закодированная циклическим кодом, согласно (2.2) примет вид:

F(x)=1110 1011=1100010

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

Получение остатка свидетельствует о наличие ошибки. Остаток от деления в циклических кодах играет роль синдрома.

Например, переданная кодовая комбинация F(x)=1100010, построенная с помощью образующего полинома Р(х)=1011. Под воздействием помехи кодовая комбинация трансформировалась в комбинацию F"(x)=1000010

Делим принятую комбинацию на образующий полином

Наличие остатка R(x)=001 свидетельствует об ошибке. Однако он не указывает непосредственно на место ошибки в комбинации. Для определения ошибки существует несколько методов, основанных на анализе синдрома.

Определим место нахождения ошибки, для этого единицу с произвольным количеством нулей делим на Р(х)=1011.

Ошибка произошла в элементе с номером:

Количество остатков -2>4-2=2

То есть,ошибка во втором элементе.

Соответствующий этому слову, от формальной переменной x . Видно, что это соответствие не просто взаимнооднозначное, но и изоморфное . Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации пары слов и , равен линейной комбинации полиномов этих слов

Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n-1 над полем

Алгебраическое описание

Если кодовое слово, получающееся циклическим сдвигом на один разряд вправо из слова , то ему соответствующий полином c 1 (x ) получается из предыдущего умножением на x:

Пользуясь тем, что ,

Сдвиг вправо и влево соответственно на j разрядов:

Если m (x ) - произвольный полином над полем G F (q ) и c (x ) - кодовое слово циклического (n ,k ) кода, то m (x )c (x )m o d (x n − 1) тоже кодовое слово этого кода.

Порождающий полином

Определение Порождающим полиномом циклического (n ,k ) кода C называется такой ненулевой полином из C , степень которого наименьшая и коэффициент при старшей степени g r = 1 .

Теорема 1

Если C - циклический (n ,k ) код и g (x ) - его порождающий полином, тогда степень g (x ) равна r = n − k и каждое кодовое слово может быть единственным образом представлено в виде

c (x ) = m (x )g (x ) ,

где степень m (x ) меньше или равна k − 1 .

Теорема 2

g (x ) - порождающий полином циклического (n ,k ) кода является делителем двучлена x n − 1

Следствия: таким образом в качестве порождающего полинома можно выбирать любой полином, делитель x n − 1 . Степень выбранного полинома будет определять количество проверочных символов r , число информационных символов k = n − r .

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

Полиномы линейно независимы, иначе m (x )g (x ) = 0 при ненулевом m (x ) , что невозможно.

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

, где G является порождающей матрицей , m (x ) - информационным полиномом.

Матрицу G можно записать в символьной форме:

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

Для каждого кодового слова циклического кода справедливо . Поэтому проверочную матрицу можно записать как:

Кодирование

Несистематическое

При несистематическом кодирование кодовое слово получается в виде произведения информационного полинома на порождающий

c (x ) = m (x )g (x ) .

Оно может быть реализовано при помощи перемножителей полиномов.

Систематическое

При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного

Пусть информационное слово образует старшие степени кодового слова, тогда

c (x ) = x r m (x ) + s (x ),r = n − k

Тогда из условия , следует

Это уравнение и задает правило систематичекого кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров(МЛФ)

Примеры

Двоичный (7,4,3) код

В качестве делителя x 7 − 1 выберем порождающий полином третьей степени g (x ) = x 3 + x + 1 , тогда полученный код будет иметь длину n = 7 , число проверочных символов (степень порождающего полинома) r = 3 , число информационных символов k = 4 , минимальное расстояние d = 3 .

Порождающая матрица кода:

где первая строка представляет собой запись полинома g (x ) коэффициентами по возрастанию степени. Остальные строки - циклические сдвиги первой строки.

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

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

Так, например, 3-ий столбец получается , или в векторной записи .

Легко убедиться, что G H T = 0 .

Двоичный (15,7,5) БЧХ код

В качестве порождающего полинома g (x ) можно выбрать произведение двух делителей x 15 − 1 ^

g (x ) = g 1 (x )g 2 (x ) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома m (x ) со степенью k − 1 таким образом:

c (x ) = m (x )g (x ) .

Например, информационному слову соответствует полином m (x ) = x 6 + x 5 + x 4 + 1 , тогда кодовое слово c (x ) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , или в векторном виде

См. также

Ссылки

Wikimedia Foundation . 2010 .

Циклические формы в музыке
Цикличные граничные условия

Смотреть что такое "Циклические коды" в других словарях:

укороченные циклические коды - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN shortened cyclic codes …

Коды Рида-Соломона - недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код Рида Соломона является … Википедия

коды Голея - Семейство совершенных линейных блоковых кодов с исправлением ошибок. Наиболее полезным является двоичный код Голея. Известен также троичный код Голея. Коды Голея можно рассматривать как циклические коды. … … Справочник технического переводчика

Коды, исправляющие ошибки

Коды исправляющие ошибки - Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия

Исправляющие ошибки Коды - Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия

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

где х - основание системы счисления, коэффициенты, принадлежащие множеству в случае двоичной системы счисления.

Пример. Двоичный вектор может быть представлен в виде полинома следующим образом:

Представление двоичных векторов в виде полиномов позволяет свести действие над векторами к действиям над многочленами. При этом:

сложение многочленов сводится к сумме по модулю 2 коэффициентов при равных степенях переменной

умножение производится по обычному правилу умножения степенных функций, однако полученные коэффициенты при данной степени складываются по модулю 2;

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

Пример. Найти сумму многочленов

Найти произведение многочленов

Выполнить деление многочленов

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

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

Примеры неприводимых многочленов:

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

где остаток от деления

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

Пример. Вектор натурального двоичного кода имеет вид Образовать из негр вектор циклического кода при условии, что образующий полином имеет вид

Представим вектор в виде полинома

В результате деления полинома на полином получаем остаток . Поэтому

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

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

Зададим порождающую матрицу циклического кода длиной информационными разрядами и порождающим полиномом .

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

Для нахождения строк проверочных разрядов матрицы вычислим и запишем в виде полинома каждый вектор единичной матрицы

Длина вектора циклического кода поэтому

(см. скан)

В результате получаем порождающую матрицу С:

Любой вектрр циклического кода получается как сумма по моду векторов его порождающей матрицы. Так как циклический код является групповым, то нулевой вектор всегда приписывается циклическому коду как единичный элемент группы»

Таблица 13.5

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

Код представлен в табл. 13.5.

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

Пример, Циклический код задан своей порождающей матрицей

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

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

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

На практике часто возникает задача построения циклического кода заданной мощности и заданной обнаруживающей и корректирующей способностей.

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

2. Оптимальное число проверочных разрядов циклического кода определяется по специальным таблицам .

3. По справочникам находятся все неприводимые полиномы степени

4. Для одного из непроводимых многочленов (следует выбирать многочлен с максимальным числом членов) степени строится порождающая матрица циклического кода. Каждый вектор кода вычисляется по формуле

где - полином информационного вектора порождающей матрицы; - одночлен степени - остаток от деления

5. Построенная порождающая матрица проверяется на выполнение следующих условий:

а) вес в смысле Хэмминга любого вектора порождающей матрицы должен удовлетворять соотношению где - минимальное расстояние, в смысле Хэмминга рассматриваемого циклического кода;

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

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

Построим циклический код мощностью 16 и корректирующей с по собностью

Для определяем значение по

3» По справочникам находим все неприводимые полиномы степени Таких полиномов два:

4. Выбираем в качестве образующего полином Заготовка порождающей матрицы циклического кода имеет вид

Каждый информационный вектор из матрицы представляем полиномом

Определяем полностью все векторы порождающей матрицы, используя формулу

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

Аналогично находим все остальные векторы порождающей мат рицы

Таблица 13.6

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

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

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

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

1. Принятый кодовый вектор разделить на образующий полином.

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

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

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

Код имеет в 3, т. е. корректирует ошибки кратности Пусть вместо вектора 0001101 принят вектор 0011101. Для исправления ошибки осуществляем следующие действия. Принятый вектор записываем в виде полинома: затем делим на

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

Осуществляем деление на

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

Осуществляем деление на

Полученный остаток снова содержит две единицы, поэтому делаем еще один циклический сдвиг влево на один разряд и получаем Делим на

6. Исправление ошибок с помощью циклических кодов

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

Поскольку циклические коды являются линейными, то процесс обнаружения и исправления ошибок связан с нахождением синдрома принятого вектора. Напомним, что синдром вектора u вычисляется как произведение вектора на транспонированную проверочную матрицу кода, т. е. s u = uH T . В случае циклического кода синдром равен остатку от деления соответствующего многочлена на порождающий многочлен кода, если проверочная матрица строится определенным образом. Иными словами, если g (x ) - порождающий многочлен кода, то синдром вектора u равен остатку от деления u (x ) на g (x ). Если ошибок не было, то остаток, а следовательно, и синдром принятого вектора, равен 0.

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

1. Для принятого слова находим синдром многочлена, соответствующего принятому слову.

2. Если синдром не равен 0, то по полученному синдрому (остатку от деления) находим в таблице соответствующий ему вектор ошибок.

3. Исправляем принятое слово путем сложения по модулю 2 с вычисленным вектором ошибок.

Первый шаг, который выполняется умножением принятого слова на транспонированную проверочную матрицу, для циклических кодов очень простой, если матрица H является проверочной матрицей систематического кода. В этом случае, j -я строка транспонированной матрицы H T соответствует остатку от деления многочлена x n -1- j на порождающий многочлен кода, и синдром равен остатку от деления многочлена, соответствующего принятому слову, на порождающий многочлен кода.

Пример: Рассмотрим циклический (7,1)-код, порожденный многочленом g (x ) = x 6 + x 5 + x 4 + x 3 + x 2 + x +1. Код состоит из двух слов 0000000 и 1111111 и исправляет все комбинации из 3 или менее ошибок. Образующими являются все булевы векторы длины 7 веса 0, 1, 2 и 3. Проверочная матрица строится по частному (x +1) от деления x 7 +1 на x 6 + x 5 + x 4 + x 3 + x 2 + x +1 и имеет вид

Пусть принято слово 11101101, которое соответствует многочлену x 6 + x 5 + x 4 + x 2 + 1. Остаток от деления этого многочлена на порождающий многочлен кода равен x 3 + x . Непосредственной проверкой можно убедиться, что при умножении вектора u = 1110101 на транспонированную матрицу H T , так же как и при умножении вектора 0001010 на H T получается вектор 0001010, который соответствует многочлену x 3 + x . Вектор, соответствующий многочлену x 3 + x , имеет вес 2, т. е. является образующим смежного класса. Сложив принятый вектор 11101101 с образующим 0001010, мы получим кодовое слово 1111111, т. е. ошибка будет исправлена.

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

Теорема 6.1 . (Меггит). Пусть s - синдром вектора u длины n . Синдром циклического сдвига вектора u совпадает с синдромом вектора, соответствующего полиному xs (x ).

Пример: Рассмотрим (7,4)-код Хэмминга, который является циклическим кодом, порожденным многочленом g (x ) = x 3 + x + 1. двоичный вектор 1011000 является кодовым словом, так как соответствующий многочлен x 6 + x 4 + x 3 делится на g (x ). Предположим, что при передаче этого кодового слова произошла одна ошибка в разряде, соответствующем x 4 , и принято слово u = 1001000. Синдром s принятого вектора равен 110, что соответствует многочлену x 2 + x .

Рассмотрим циклический сдвиг 0010001 вектора u . Ему соответствует многочлен x 4 + 1. Непосредственной проверкой можно убедиться, что остаток от деления многочлена x 4 + 1 на многочлен x 3 + x + 1 равен x 2 + x + 1, т. е. синдром вектора 0010001 равен 111. Остаток от деления полинома xs (x ) = x 3 + x 2 на x 3 + x + 1 также равен x 2 + x + 1.

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

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

2. Если остаток совпал с одним из синдромов таблицы, то прибавляем соответствующий вектор ошибок к принятому слову, делим полученное слово на порождающий многочлен кода; частное от деления есть искомое информационное слово. Если остаток xs (x ) не совпадает ни с одним из синдромов таблицы, умножаем s (x ) на x и делим многочлен xs (x ) на порождающий многочлен кода.

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

Пример: Рассмотрим циклический (7,4)-код Хэмминга, порожденным многочленом g (x ) = x 3 + x + 1. Соответствующая таблица декодирования с синдромами имеет следующий вид.

и предположим, что в переданном кодовом слове 0001011 произошла одна ошибка, т. е. принято, например, слово 0101011, которому соответствует многочлен x 5 + x 3 + x + 1. Остаток от деления многочлена x 5 + x 3 + x + 1 на порождающий многочлен кода g (x ) = x 3 + x + 1 равен x 2 + x + 1, т. е. синдром принятого вектора отличен от 0 и равен 111. Такого синдрома в таблице нет, и следовательно, в старшем разряде ошибок нет. Умножаем многочлен x 2 + x + 1, соответствующий синдрому 111, на x и делим полученный многочлен x 3 + x 2 + x на g (x ). Остаток от деления многочлена x 3 + x 2 + x на x 3 + x + 1 равен x 2 + 1, т. е. синдром 101, соответствующий остатку, совпадает с синдромом в сокращенной таблице декодирования. Соответственно, образующий 100000 смежного класса сдвигается на один разряд влево, и полученный вектор 0100000 складывается с принятым вектором 0101011. В результате получается слово 0001011, которое и является переданным кодовым словом, т. е. ошибка будет исправлена.

Можно упростить этот декодер. В частности, при циклическом сдвиге принятого слова многие из исправляемых конфигураций ошибок могут появиться несколько раз. Если удалить один из этих синдромов, то при соответствующем циклическом сдвиге ошибка все-таки будет найдена. Следовательно, для каждой такой пары достаточно запоминать только один синдром.