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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

кафедра РЭС

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

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

МИНСК, 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 , используя

так как

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

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

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

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

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