Все о тюнинге авто

Учебно-методический центр языковой подготовки автф кц. Циклические коды Определяющим свойством циклического кода является

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра РЭС

реферат на тему:

«Циклические коды. Коды БЧХ»

МИНСК, 2009

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

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

Многочлен g(x) называется порождающим.

Как следует из определения, в циклическом коде кодовые слова представляются в виде многочленов


где n - длина кода; - коэффициенты из поля GF(q).

Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным.
Пример. Если кодовое слово циклического кода

то соответствующий ему многочлен

Например, если код построен над полем GF(q)=GF(2 3), которое является расширением GF(2) по модулю неприводимого многочлена f(z)=z 3 +z+1, а элементы этого поля имеют вид, представленный в таблице 1,

то коэффициенты

принимают значения элементов этого поля и поэтому они сами отображаются в виде многочленов следующего вида
где m - степень многочлена, по которому получено расширение поля GF(2);\ a i - коэффициенты, принимающие значение элементов GF(2), т.е. 0 и 1. Такой код называется q-ным.

Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=q m -1 на GF(q).

Если длина кода меньше длины примитивного кода, то код называется укороченным или непримитивным.

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

Результатом деления двучлена x n +1 на многочлен g(x) является проверочный многочлен h(x).

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

Многочлен ошибок степени не более (n-1) определяется из выражения

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

Ненулевые коэффициенты в е(x) занимают позиции, которые соответствуют ошибкам.

Пример.

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


или

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

(см. таблицу 2).

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

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

Допустим, что длина кода n=7, то результат приводим по mod x 7 +1.

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

Пример.

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

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

и

При построении матрицы H (n,k) старший коэффициент многочлена h(x) располагается справа.

Пример. Для циклического (7,4)-кода с порождающим многочленом g(x)=x 3 +x+1 матрицы G (n,k) и H (n,k) имеют вид:

где

Для систематического циклического кода матрица G (n,k) определяется из выражения

где I k - единичная матрица; R k,r - прямоугольная матрица. Строки матрицы R k,r определяются из выражений или где a i (x) - значение i-той строки матрицы I k ; i - номер строки матрицы R k,r .

Пример. Матрица G (n,k) для (7,4)-кода на основе порождающего многочлена g(x)=x 3 +x+1, строится в следующей последовательности


или

Определяется R 4,3 , используя

так как

Аналогичным способом определяется

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

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

Эти свойства используются при построении кодов кодирующих и декодирующих устройств, а также при обнаружении и исправлении ошибок.

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

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

При декодировании принятой л-разрядной кодовой комбинации опять производится деление на порождающий (производящий, образующий) полином.

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

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

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

Таблица 2.6

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

Увеличивая разность (п - т), можно не только нарастить число исправляемых бит s, но и обнаружить множественные ошибки. Проценты обнаруживаемых множественных ошибок приведены в табл. 2.7.

Таблица 2.7

Проценты обнаруживаемых множественных ошибок

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов). Запись комбинации в виде полинома используется для того, чтобы отобразить формализованным способом операцию циклического сдвига исходной кодовой комбинации. Так, «-элементную кодовую комбинацию можно описать полиномом (п - 1) степени:

где a„_j = {0, 1}, причем а„_, = 0 соответствуют нулевым элементам комбинации, д„_, = 1 - ненулевым; i - номер разряда кодовой комбинации.

Представим полиномы для конкретных 4-элементных комбинаций:

Операции сложения и вычитания являются эквивалентными и ассоциативными и выполняются по модулю 2:

Примеры выполнения операций:

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

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

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

Допустим, задана исходная кодовая комбинация и соответствующий ей полином:

Умножим а(х) на х:

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

Сдвиг исходной комбинации на / тактов можно представить следующим образом: а(х) ? У - а„(х" - 1), т.е. умножением а(х) нах" и взятием остатка по модулю (х" - 1). Взятие остатка необходимо при получении многочлена степени, большей или равной п.

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

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

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

С, = 0 или Cj = 1 («О», если результирующая степень полинома Р(х)-х‘ не превосходит (л - 1), или «1» - если превосходит).

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

Порождающий полином должен удовлетворять следующим требованиям:

  • Р(х) должен быть ненулевым;
  • вес Р(х ) не должен быть меньше минимального кодового расстояния: V(P(x)) > d mm ;
  • Р(х) должен иметь максимальную степень к (к - число избыточных элементов в коде);
  • Р(х) должен быть делителем полинома (х" - 1).

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

Для определения степени порождающего полинома можно воспользоваться выражением г > log 2 (и + 1), где п - размер передаваемого пакета за один раз, т.е. длина строящегося циклического кода.

Примеры порождающих полиномов приведены в табл. 2.8.

Таблица 2.8

Примеры порождающих полиномов

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

Пусть заданы полином Р(х) = а г _ { х г + а г _ 2 х г ~ 1 + ... + 1, определяющий корректирующую способность кода, и число проверочных разрядов к, а также исходная комбинация простого от-элементного кода и информационные разряды в виде многочлена А т (х).

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

  • 1. Представляем исходную кодовую комбинацию в виде многочлена А т (х). Умножаем многочлен исходной кодовой комбинации на х г: А т (х ) х г. Степень порождающего полинома г равна значению старшего разряда исходной кодовой комбинации.
  • 2. Определяем проверочные разряды, дополняющие исходную информационную комбинацию до разрешенной, как остаток от деления полученного в предыдущем пункте произведения на порождающий

полином:

Остаток деления обозначим как R(x).

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

кода определится как = А т (х) ? x r + R(x).

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

Алгоритм определения ошибки следующий.

Пусть заданы «-элементные комбинации (п = к + т).

  • 1. Выявляем факт наличия ошибки. Получаем остаток от деления принятой комбинации А п -(х) на порождающий полином Р(х): А (х)
  • --- = Rq(x). Наличие остатка R 0 (x) при (Л 0 (х) ф 0) свидетельствует Р(х)

об ошибке.

2. Делим полученный полином #(х) = Л„_, (х) 0 Rq (х) на образующий Р г (х): Ш-1 = R(x), где R(x) - текущий остаток.

3. Сравниваем ЛДх) и R(x). Если они равны, то ошибка произошла в старшем разряде. Если нет, то увеличиваем степень принятого полинома на х и снова делим:

4. Сравниваем полученный остаток с Rq(x). Если они равны, то ошибка произошла во втором разряде. Если они не равны, то умножаем Щх) х 2 и повторяем эти операции до тех пор, пока не получим

R(x) = ад.

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

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

Многие важнейшие помехоустойчивые коды систем связи, -

в частности циклические, основаны на структурах конечных Арифметика

полей Галуа. Полем называется множество элементов, которые конечного поля

звания операций взяты в кавычки, потому что они не всегда являются общепринятыми арифметическими операциями. В поле всегда имеется нулевой элемент (0), или нуль, и единичный элемент (1), или единица. Если число q элементов поля ограничено, то поле называется конечным полем , или конечным полем Галуа , и обозначается GF(q) y где q - порядок поля. Наименьшим полем Галуа является двухэлементное иоле GF(2), состоящее всего из двух элементов 1 и 0. Для того чтобы

1 Эварист Галуа (Evariste Galois, 1811 - 1832) - французский математик, заложил основы современной алгебры.

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

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

Для операций сложения и умножения выполняются обычные математические правила ассоциативности - а + (Ь + с) = (а + Ь) + с, коммутативности - а + b = b + а и а b = b а и дистрибутивности - а (Ь + с) = а b + а с.

Для каждого элемента поля а должны существовать обратный элемент по сложению (-а) и, если а не равно нулю, обратный элемент по умножению (й ’).

Поле должно содержать аддитивную единицу - элемент 0, такой, что а + 0 = а для любого элемента поля а.

Поле должно содержать мультипликативную единицу - элемент 1, такой, что аЛ = а для любого элемента поля а.

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

Фактически все наборы, образованные циклической перестановкой кодовой комбинации, также являются кодовыми комбинациями. Так, например, циклические перестановки комбинации 1000101 будут также кодовыми комбинациями 0001011, 0010110, 0101100 и т.д. Это свойство позволяет в значительной степени упростить кодирующее и декодирующее устройства, особенно при обнаружении ошибок и исправлении одиночной ошибки. Внимание к циклическим кодам обусловлено тем, что присущие им высокие корректирующие свойства реализуют на основе сравнительно простых алгебраических методов. В то же время для декодирования произвольного линейного блокового кода чаще применяют табличные методы, требующие большой объем памяти декодера.

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

В циклическом коде кодовые слова представляют многочленами (полиномами)

где п - длина кода; A i - коэффициенты поля Галуа (значений кодовой комбинации).

Например, для кодовой комбинации 101101 полиномиальная запись имеет вид

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

Код Хемминга . Возможности исправления ошибок в коде Хемминга связаны с минимальным кодовым расстоянием d 0 . Исправляются все ошибки кратности q = cnt(d 0 - l)/2 (здесь cnt означает «целая часть») и обнаруживаются ошибки кратности d 0 - 1. Так, при контроле на нечетность d Q = 2 и обнаруживаются одиночные ошибки. В коде Хемминга d 0 = 3. Дополнительно к информационным разрядам вводится L = log 2 Q избыточных контролирующих разрядов, где Q - число информационных разрядов. Параметр L округляется до ближайшего большего целого значения. L-разрядный контролирующий код есть инвертированный результат поразрядного сложения (сложения по модулю 2) номеров тех информационных разрядов, значения которых равны единице.

Пример 7.7

Пусть имеем основной код 100110, т.е. Q = 6. Определим дополнительный код.

Решение

Находим, что L = 3 и дополнительный код равен

где П - символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь с основным кодом будет передан и дополнительный. В приемнике вновь рассчитывают дополнительный код и сравнивают с переданным. Фиксируется код сравнения, и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100010, го рассчитанный дополнительный код равен инверсии от 010Ш10 = 100, т.е. 011, что означает ошибку в 3-м разряде.

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

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

Турбокоды. Избыточные коды могут применяться как самостоятельно, так и в виде некоторого объединения нескольких кодов, когда наборы символов одного избыточного кода рассматриваются как элементарные информационные символы другого избыточного кода. Такое объединение стали называть каскадным кодом. Огромным достоинством каскадных кодов является то, что их применение позволяет упростить кодер и особенно декодер по сравнению с аналогичными устройствами некаскадных кодов той же длины и избыточности. Каскадное кодирование привело к созданию турбокодов. Турбокодом называют параллельную структуру сигнала, состоящую из двух или большего числа систематических кодов. Основной принцип их построения - использование нескольких параллельно работающих компонентных кодеров. В качестве компонентных можно использовать как блочные, так и сверточные коды, коды Хемминга, PC-код, БЧХ и др. Использование перфорации (выкалывания) позволяет увеличить относительную скорость турбокода, адаптировав его исправляющую способность к статистическим характеристикам канала связи. Принцип формирования турбокода состоит в следующем: входной сигнал х, состоящий из К бит, подается параллельно на N перемежителей. Каждый из последних представляет собой устройство, осуществляющее перестановку элементов в блоке из К бит в псевдослучайном порядке. Выходной сигнал с перемежителей - символы с измененным порядком следования - поступает на соответствующие элементарные кодеры. Двоичные последовательности х р i = 1,2,..., JV, на выходе кодера представляют собой проверочные символы, которые вместе с информационными битами составляют единое кодовое слово. Применение перемежителя позволяет предотвратить появление последовательностей коррелированных ошибок при декодировании турбокодов, что немаловажно при использовании традиционного в обработке рекурентного способа декодирования. В зависимости от выбора компонентного кода турбокоды делятся на сверточные турбокоды и блоковые коды-произведения.

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

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

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

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

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

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