ВходСодержится ли в циклическом префиксе полезная информация. Циклические коды
Циклические коды названы так потому, что в них часть комбинаций кода либо все комбинации могут быть получены путем циклического сдвига одной или нескольких комбинаций кода. Циклический сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец комбинации. Циклические коды, практически, все относятся к систематическим кодам, в них контрольные и информационные разряды расположены на строго определенных местах. Кроме того, коды относятся к числу блочных кодов. Каждый блок (одна буква является частным случаем блока) кодируется самостоятельно.
Идея построения циклических кодов базируется на использовании неприводимых в поле двоичных чисел многочленов. Неприводимыми называются многочлены, которые не могут быть представлены в виде произведения многочленов низших степеней с коэффициентами из того же поля, так же, как простые числа не могут быть представлены произведением других чисел. Иными словами неприводимые многочлены делятся без остатка только на себя или на единицу.
Неприводимые многочлены в теории циклических кодов играет роль образующих многочленов. Если заданную кодовую комбинацию умножить на выбранный неприводимый многочлен, то получим циклический код, корректирующие способности которого определяются неприводимым многочленом.
Предположим, требуется закодировать одну из комбинаций четырехзначного двоичного кода. Предположим также, что эта комбинация G(x) = x 3 + x 2 + 1 ® 1011. Пока не обосновывая свой выбор, берем из таблицы неприводимых многочленов в качестве образующего многочлен P(x) = x 3 + x + 1 ® 1011. Затем умножим G(x) на одночлен той же степени, что и образующий многочлен. От умножения многочлена на одночлен степени n степень каждого члена многочлена повысится на n , что эквивалентно приписыванию n нулей со стороны младших разрядов многочлена. Так как степень выбранного неприводимого многочлена равна трем, то исходная информационная комбинация умножается на одночлен трех степеней
G(x) x n = (x 3 + x 2 + 1 ) x 3 =x 6 + x 5 + x 3 = 1101000.
Это делается для того, чтобы впоследствии в месте этих нулей можно было бы записать корректирующие разряды.
Значение корректирующих разрядов находят по результатам от деления G(x) x n на P(x) :
x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1
x 6 +0+x 4 +x 3
x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2
x 4 + x 3 +x 2 +0
x 4 + 0 +x 2 +x
x 3 +0+x+0
x 3 +0+x+1
Таким образом,
или в общем виде
где Q(x) ¾ частное, а R(x) ¾ остаток от деления G(x)×x n на P(x).
Так как в двоичной арифметике 1 Å 1 = 0, а значит, -1 = 1, то можно при сложении двоичных чисел переносить слагаемые из одной части в другую без изменения знака (если это удобно), поэтому равенство вида a Å b = 0 можно записать и как a = b , и как a - b = 0. Все три равенства в данном случае означают, что либо a и b равны 0, либо a и b равны 1, т.е. имеют одинаковую четность.
Таким образом, выражение (5.1) можно записать как
F(x)=Q(x) P(x)= G(x) x n +R(x),
что в случае нашего примера даст
F(x)= (x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1) x 3 + 1,
F(x)= 1111 1011 = 1101000 + 001 = 1101001.
Многочлен 1101001 и есть искомая комбинация, где 1101‑ информационная часть, а 001 ‑ контрольные символы. Заметим, что искомую комбинацию мы получили бы и как в результате умножения одной из комбинаций полного четырехзначного двоичного кода (в данном случае 1111) на образующий многочлен, так и умножением заданной комбинации на одночлен, имеющий ту же степень, что и выбранный образующий многочлен (в нашем случае таким образом была получена комбинация 1101000) с последующим добавлением к полученному произведению остатка от деления этого произведения на образующий многочлен (в нашем примере остаток имеет вид 001).
И тут решающую роль играют свойства образующего многочлена P(x) . Методика построения циклического кода такова, что образующий многочлен принимает участие в образовании каждой кодовой комбинации, поэтому любой многочлен циклического кода делится на образующий без остатка. Но без остатка делятся только те многочлены, которые принадлежат данному коду, т. е. образующий многочлен позволяет выбрать разрешенные комбинации из всех возможных. Если же при делении циклического кода на образующий многочлен будет получен остаток, то значит либо в коде произошла ошибка, либо это комбинация какого-то другого кода (запрещенная комбинация). По остатку и обнаруживается наличие запрещенной комбинации, т. е. обнаруживается ошибка. Остатки от деления многочленов являются опознавателями ошибок циклических кодов.
С другой стороны, остатки от деления единицы с нулями на образующий многочлен используются для построения циклических кодов.
При делении единицы с нулями на образующий многочлен следует помнить, что длина остатка должна быть не меньше числа контрольных разрядов, поэтому в случае нехватки разрядов в остатке к остатку приписывают справа необходимое число нулей.
01100 11111+
начиная с восьмого, остатки будут повторяться.
Остатки от деления используются для построения образующих матриц, которые, благодаря своей наглядности и удобству получения производных комбинаций, получили широкое распространение для построения циклических кодов. Построение образующей матрицы сводится к составлению единичной транспонированной и дополнительной матрицы, элементы которой представляют собой остатки от деления единицы с нулями на образующий многочлен P(x) . Напомним, что единичная транспонированная матрица представляет собой квадратную матрицу, все элементы которой ‑ нули, кроме элементов расположенных по диагонали справа налево сверху вниз (в нетранспонированной матрице диагональ с единичными элементами расположена слева направо сверху вниз). Элементы дополнительной матрицы приписываются справа от единичной транспонированной матрицы. Использоваться могут лишь те остатки, вес которых W ³ d 0 - 1, где d 0 ‑ минимальное кодовое расстояние. Длина остатков должна быть не менее количества контрольных разрядов, а число остатков должно равняться числу информационных разрядов.
Строки образующей матрицы представляют собой первые комбинации исходного кода. Остальные комбинации кода получаются в результате суммирования по модулю 2 всевозможных сочетаний строк образующей матрицы.
Пример.
Построить полную образующую матрицу циклического кода, обнаруживающего все одиночные и двойные ошибки при передаче 10-разрядных двоичных комбинаций.
Решение.
По таблице 5.12 выбираем ближайшее значение k ³ 10 .
Таблица 5.12 – Соотношения между информационными и проверочными символами для кода длиной до 16 разрядов
| n | k | ρ | n | k | ρ |
Согласно таблице таким значением будет k = 11, при этом r = 4, а
n = 15. Также выбираем образующий многочлен x 4 + x 3 +1.
Полную образующую матрицу строим из единичной транспонированной матрицы в канонической форме и дополнительной матрицы, соответствующей проверочным разрядам.
Транспонированная матрица для k = 11 имеет вид:
Дополнительная матрица может быть построена по остаткам деления комбинации в виде единицы с нулями (последней строки единичной транспонированной матрицы) на выбранный образующий многочлен.
Полная образующая матрица будет иметь вид:
Описанный выше метод построения образующих матриц не является единственным. Образующая матрица может быть построена в результате непосредственного умножения элементов единичной матрицы на образующий многочлен. Это часто бывает удобнее, чем нахождение остатков от деления. Полученные коды ничем не отличаются от кодов, построенных по образующим матрицам, в которых дополнительная матрица состоит из остатков от деления единицы с нулями на образующий многочлен.
Образующая матрица может быть построена так же путем циклического сдвига комбинации, полученной в результате умножения строки единичной матрицы ранга k на образующий многочлен.
Ошибки в циклических кодах обнаруживаются при помощи остатков от деления полученной комбинации на образующий многочлен. Остатки от деления являются опознавателями ошибок, но не указывают непосредственно на место ошибки в циклическом коде.
Идея исправления ошибок базируется на том, что ошибочная комбинация после определенного числа циклических сдвигов “подгоняется” под остаток таким образом, что в сумме с остатком она дает исправленную кодовую комбинацию. Остаток при этом представляет собой не что иное, как разницу между искаженными и правильными символами, единицы в остатке стоят как раз на местах искаженных разрядов в подогнанной циклическими сдвигами комбинации. Подгоняют искаженную комбинацию до тех пор, пока число единиц в остатке не будет равно числу ошибок в коде. При этом, естественно, число единиц может быть либо равно числу ошибок s, исправляемых данным кодом (код исправляет 3 ошибки и в искаженной комбинации 3 ошибки), либо меньше s (код исправляет 3 ошибки, а в принятой комбинации 1 ошибка).
Место ошибки в кодовой комбинации не имеет значения. Если k ³ (n / 2) , то после определенного количества сдвигов все ошибки окажутся в зоне “разового” действия образующего многочлена, т. е. достаточно получить один остаток, вес которого W £ s , и этого уже будет достаточно для исправления искаженной комбинации.
Подробно процесс исправления ошибок рассматривается ниже на примерах построения конкретных кодов.
Это подкласс линейных кодов, обладающих гем свойством, что циклическая перестановка символов в кодированном блоке дает другой возможный кодированный блок того же кода. Циклические коды основаны на применении идей алгебраической теории полей Галуа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, на выходе кодера представляют собой проверочные символы, которые вместе с информационными битами составляют единое кодовое слово. Применение перемежителя позволяет предотвратить появление последовательностей коррелированных ошибок при декодировании турбокодов, что немаловажно при использовании традиционного в обработке рекурентного способа декодирования. В зависимости от выбора компонентного кода турбокоды делятся на сверточные турбокоды и блоковые коды-произведения.
Циклические коды являются разновидностью линейных групповых кодов и относятся к систематическим кодам. Первоначально были созданы для упрощения процедуры декодирования. Однако высокая эффективность к обнаружению ошибок таких кодов обеспечила их широкое применение на практике. Двоичный вектор циклического кода удобно рассматривать не как комбинацию нулей и единиц, а в виде полинома некоторой степени
где х - основание системы счисления, коэффициенты, принадлежащие множеству в случае двоичной системы счисления.
Пример. Двоичный вектор может быть представлен в виде полинома следующим образом:
Представление двоичных векторов в виде полиномов позволяет свести действие над векторами к действиям над многочленами. При этом:
сложение многочленов сводится к сумме по модулю 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. Для исправления ошибки осуществляем следующие действия. Принятый вектор записываем в виде полинома: затем делим на
Полученный в результате деления остаток содержит три единицы, что больше, чем корректирующая способность кода. Поэтому делаем циклический сдвиг влево на один разряд принятого кодового вектора. В результате имеем
Осуществляем деление на
Полученный остаток содержит две единицы, что больше, чем корректирующая способность кода. Поэтому делаем еще один циклический сдвиг влево на один разряд принятого кодового вектора. В результате имеем
Осуществляем деление на
Полученный остаток снова содержит две единицы, поэтому делаем еще один циклический сдвиг влево на один разряд и получаем Делим на
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
кафедра РЭС
реферат на тему:
«Циклические коды. Коды БЧХ»
МИНСК, 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 , используя
так какАналогичным способом определяется
Простейший циклический код с позволяет обнаруживать одиночные ошибки и ошибки нечетной кратности. Образующий полином этого кода имеет вид Среди неприводимых многочленов, входящих в разложение данный полином является многочленом наименьшей степени Таким образом, при любом числе информационных разрядов необходим только один проверочный разряд. Значение символа этого разряда обеспечивает четность числа единиц в любой разрешенной кодовой комбинации. Полученный циклический код с проверкой на четность способен обнаруживать не только одиночные ошибки в отдельных разрядах, но и ошибки в любом нечетном числе разрядов.
Пример. Построить циклический код для Поскольку образующий полином является полиномом 1-й степени, число проверочных разрядов Следовательно, Для построения циклического кода строим производящую матрицу
Для построения дополнительной матрицы находим остатки от деления поаледней строки единичной транспонированной матрицы, дополненной нулями, на выбранный полином:
Таким образом, дополнительная матрица С, к имеет вид
Теперь строим производящую матрицу
Строки данной матрицы являются тремя первыми комбинациями кода. Остальные из разрешенных комбинаций могут быть получены суммированием по модулю два всевозможных сочетаний строк матрицы Полученные разрушенные кодовые комбинации приведены в табл. 39.
Таблица 39 (см. скан)
Известный интерес представляет рассмотрение следующего простейшего кода с образованного с помощью неприводимого полинома второй степени
Общий вид производящей матрицы циклического кода, образованного полиномом отличается структурой дополнительной матрицы имеющей два столбца.
Легко убедиться, что при делении на данный образующий многочлен одночленов, выражающих строки
единичной матрицы (для нахождения дополнительной матрицы образуется. три вида остатков: 11, 01 и 10. Следовательно, вес каждой комбинации полученного -кода будет не менее двух. Минимальное кодовое расстояние между двумя любыми комбинациями также равно двум. Но такими же величинами характеризуется и простейший код с одной проверкой на четность, образованный двучленом первой степени Однако корректирующая способность обоих кодов неодинакова. Рассматриваемый код имеет большую избыточность и позволяет обнаруживать не только любые ошибки нечетной кратности, но и любые парные смежные ошибки, а также все ошибки, разделенные одним неискаженным элементом .