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

29.06.2020

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

Комбинация циклического кода;

Также комбинация циклического кода.

При рассмотрении циклических кодов двоичные числа представляют в виде многочлена, степень которого (п - 1), п - длина кодовой комбинации.

Например, комбинация 1001111 (п= 7) будет представлена многочленом

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

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

Построение комбинаций циклического кода возможно путем умножения исходной комбинации А (х ) на образующий полином G (x )с приведением подобных членов по модулю 2:

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

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

Часто в качестве полинома, на который осуществляется деление, берется полином G (x )= +1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.

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

Число разрядов регистра выбирается равным степени образующего полинома.

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

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

Рисунок 17 - Схема кодирующего регистра

В табл. 4 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011.п= 7, k =4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.

Таблица 4

Свойства циклического кода :

1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G (x )=x+ 1, то код обнаруживает одиночные ошибки и все нечетные;

2) циклический код с G (x )= (x+ 1)G (x ) обнаруживает все одиночные, двойные и тройные ошибки;

3) циклический код с образующим полиномом G (x ) степени r = n - k обнаруживает все групповые ошибки длительностью в r символов.

Контрольные вопросы

Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации двоичных символов в передаваемом сообщении могут быть получены путем операции циклического сдвига некоторого исходного слова: Обычно кодовые комбинации циклического кода рассматривают не в виде последовательности нолей и единиц, а в виде полинома некоторой степени . Любое число в любой позиционной системе счисления можно представить в общем виде как: где х - основание системы счисления; а - цифры данной системы счисления; п-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.

Соответствующий этому слову, от формальной переменной 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 …

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

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

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

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

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

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

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

Теорема 1

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

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

Теорема 2

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

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

Полиномы линейно независимы, иначе 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) код

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

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

Так, например, 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 .

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

См. также

Ссылки

Wikimedia Foundation . 2010 .

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

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

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

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

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

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

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

Циклические коды относятся к числу блоковых систематических кодов, в которых каждая комбинация кодируется самостоятельно (в виде блока) таким образом, что информационные 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

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