Progress-servis55.ru

Новости из мира ПК
3 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Синдром ошибки циклического кода

Определение места ошибки в КК циклического кода

Выбор образующего полинома

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

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

Непроводимыми называются такие полиномы, которые делятся без остатка только на 1 и сами на себя.

Кроме того, среди непроводимых полиномов, отбирают так называемые примитивные.

Примитивным считается полином степени r, если он обеспечивает максимальное число непроводимых полиномов той же степени r. Таких остатков должно быть не менее 2 r -1/

Примитивные полиномы выбираются из специальных таблиц.

МККТТ рекомендует V.41 – P(x)= x 16 +x 12 + x 5 +1 — «Аккорд 1200»

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

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

Остаток при этом представляет собой разницу между искаженным и исправленным разрядами. Единицы в остатке стоят на местах искаженных разрядов в «подогнанной» циклическими сдвигами КК.

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

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

Алгоритм оптимального декодирования на основе анализа веса

1. Принятая КК делится на образующий полином

2. Если остаток нулевой, то КК выдается получателю. Если не нулевой, то выполняют п.3

3. Подсчитывается вес остатка; если w≤ tu , то принятая КК складывается по модулю 2 с полученным остатком, если w> tu ,то выполняется п.4

4. Производим циклический сдвиг КК влево на один разряд. Делим полученную в результате сдвига КК на образующий полином. Если вес остатка w≤ tu, то складываем остаток с КК и полученную КК сдвигаем вправо на один разряд – будет исправленная КК. Если w> tu, то выполняется п.5

5. Повторяем п.4 до тех пор, пока не будет w≤ tu. КК, полученная в результате последнего циклического сдвига влево, суммируется с последним остатком. Далее выполняется п.6

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

Пусть передаем КК 1001110 кода (7,4), образующий полином Р(х)=1011 (х 3 +х+1). Пусть в принятой КК искажен 4 разряд. d=3, т.е. код исправляет однократную ошибку tu=1, т.е. приняли мы КК →1000110. Попытаемся обнаружить и исправить эту ошибку

1. Делим принятую КК на Р(х):

1000110 1011

1011 101

1111

1000

1011

Получим остаток 11, его вес равен 2> tu=1

2. Производим сдвиг полученной КК влево на 1 разряд

0001101 1011

1011

110 — вес остатка 2> tu=1

3. Еще сдвигаем влево КК

0001101→0011010 делим на Р(х)

0011010

1011 1011

1100

111 — вес остатка 3> tu=1

4. Еще сдвигаем влево КК

0011010→0110100 делим на Р(х)

0110100 1011

1011

1100

1011

1110

101 — вес остатка 2> tu=1

5. Еще сдвигаем влево КК

0110100→1101000, делим на Р(х)

1101000 1011

1011

1100

1011

1110

1011

1010

1011

1 — вес остатка w= tu =1

6. Складываем последнее делимое с остатком

1101000

1101001

7. Сдвинем эту КК вправо на 4 разряда, т.к. мы сдвигаем исходную КК влево на 4 разряда:

Получим исправленную КК – сравним с переданной: 1001110

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 9231 — | 7433 — или читать все.

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

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

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

Ознакомимся с принципами построения циклических кодов на примере кода (7,4). Образуем порождающую матрицу этого кода из комбинаций, содержащих по три единицы. Учтем, что единицы в комбинациях не должны чередоваться с нулями через равные промежутки, так как при суммировании результирующая комбинация по условию замкнутости должна иметь не менее трех единиц. Этим требованиям отвечают только два варианта циклических комбинаций: 0001101 и 0001011. Таким образом, существуют только две матрицы циклического кода (7,4):

Рассмотрим первый вариант циклического кода (7,4). Кодовую комбинацию 0001101 удобно представлять в виде комбинации 1101 с приписанными в старших разрядах тремя нулями. Будем называть комбинацию 1101 порождающей (образующей). Циклический сдвиг кодовой комбинация на один разряд влево можно рассматривать как умножение порождающей комбинации на комбинации 10, 100 и 1000. Полученные таким образом комбинации, естественно, делятся на порождающую без остатка. Не вошедшие в порождающую матрицу разрешенные комбинации можно получить суммированием комбинаций, вошедших в матрицу. Один из возможных вариантов получения всех
15 разрешенных комбинаций сводится к следующему. В качестве 1-й разрешенной комбинации возьмем, например, первую комбинацию из порождающей матрицы: 0001101. Поочередно сдвигая эту комбинацию влево на один разряд, будем иметь еще шесть разрешенных комбинаций. Седьмая комбинация при этом будет такой: 1000110. Просуммировав 1-ю и 2-ю комбинации из порождающей матрицы, получим 8-ю разрешенную комбинацию. Циклическим сдвигом этой комбинации получаем еще шесть разрешенных комбинаций. Наконец. 15-ю комбинацию получаем путем суммирования (по модулю 2) всех комбинаций порождающей матрицы, за исключением 3-й.

Читать еще:  New objava добавление объявления да

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

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

В литературе при рассмотрении теории циклических кодов для удобства кодовые комбинации обычно записываются условно в виде многочленов. С каждой комбинацией сопоставляется соответствующий степенной многочлен, сформированный по следующему правилу: единица в i-м разряде комбинации обозначается как x i-1 , отсутствие в многочлене элемента x k-1 означает, что в k-м разряде комбинации стоит нуль. Например, порождающие многочлены рассмотренных вариантов циклического кода (7,4) 1101 и 1011 записываются условно так: х 3 +х 2 +1 и х 3 +х+1, кодовой комбинации 10000000 эквивалентен многочлен х 7 .

Построение циклического кода должно начинаться с выбора необходимого порождающего многочлена. В литературе приведены таблицы возможных порождающих многочленов с указанием корректирующих возможностей кодов при использовании этих многочленов. Так, при трех проверочных разрядах порождающие (неприводимые) многочлены имеют два вида: х 3 +х+1 (1011) и х 3 +х 2 +1 (1101); для четырех проверочных разрядов имеется три неприводимых многочлена: х 4 +х+1 (10011), х 4 +х 3 +1 (11001),
х 4 +х 3 +х 2 +х+1 (11111).

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

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

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

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

Декодирование систематических циклических кодов

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

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

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

Алгоритм первый. Декодируемая комбинация делится на порождающую. Если остаток после деления соответствует синдрому ошибки в младшем разряде, символ исправляется в этом разряде. Если получается иной синдром ошибки, декодируемая комбинация сдвигается на один разряд влево и процедура деления и определения остатка повторяется. Этот цикл (сдвиг — деление) повторяется до тех пор, пока полученный остаток не совпадет с синдромом ошибки в младшем разряде. При совпадении исправляется ошибка в младшем разряде, после чего комбинации сдвигается в обратную сторону в исходное состояние (если было проведено m делений, то производится сдвиг вправо на m-1 разрядов).

Читать еще:  Как создать игру на javascript

Алгоритм второй. Возможность применения этого метода основана на следующем. При делении комбинации с ошибкой на порождающую комбинацию остаток от деления образуется за счет того, что вектор ошибки не делится на порождающую комбинацию. Кроме того, вектор х n+k-1 , деленный на порождающий многочлен, дает остаток с единицей в
k-м разряде и нулями в остальных разрядах. Например, в коде (7,4) многочлен х 7 (комбинация 10000000) дает остаток 001, многочлен х 8 – остаток 010 и т.д. С другой стороны, разрешенная комбинация, сдвинутая влево на любое число разрядов без перестановки старших разрядов (сдвиг при этом сводится к дописанию справа соответствующего количества нулей), также делится на порождающую без остатка. Указанные факторы позволяют применить следующую процедуру исправления ошибок.

1. Пришедшая комбинация делится на порождающую.

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

3. Если остаток отличен от нуля, он сравнивается с синдромом, соответствующим ошибке в старшем разряде.

4. Если при сравнении происходит совпадение, принимается решение о наличии ошибки в старшем разряде и производится исправление.

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

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

Решение. 1. Делим полученную комбинацию на порождающую:

2. Поскольку синдром ошибки в младшем разряде равен 001, т.е. не совпадает в полученным, сдвигаем полученную комбинацию на 1 разряд влево в снова производим деление:

3. Так как остаток снова не равен 001, сдвигаем принятую комбинацию еще на разряд влево и делим:

4. Еще раз повторяем сдвиг и деление:

5. Исправляем символ в младшем разряде сдвинутой комбинация:

6. Сдвигаем комбинацию в обратном направлении (вправо) на три разряда: 1011000.

7. Отсекаем три младших (проверочных) разряда и передаем потребителю информации комбинацию 1011.

Пример. Используется тот же код, что и в предыдущем примере. Получена комбинация 1001000. Необходимо произвести декодирование по 2-му алгоритму.

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

Таким образом, синдром ошибки в 7-м разряде равен 101. Делим полученную комбинацию на порождающую:

=101 – синдром ошибки в 7-м разряде

При делении до получения остатка 101 потребовалось дописать два нуля, что эквивалентно сдвигу комбинации на два разряда влево, следовательно, ошибка в принятой комбинации имеет место в 5-м разряде (7-2=5). Суммируя вектор ошибки в 5-м разряде с полученной комбинацией, исправляем:

Вычисление синдрома и исправление ошибок в циклических кодах

Вычисление синдрома для циклических кодов является довольно простой процедурой.

Пусть U(x) и r(х) ‑ полиномы, соответствующие переданному кодовому слову и принятой последовательности.

Разделив r(x) на g(x), получим

r(x) = q(x)× g(x) + s(x), (3.73)

где — q(x) — частное от деления, s(x) — остаток от деления.

Если r(x) является кодовым полиномом, то он делится на g(x) без остатка, то есть s(x) = 0.

Следовательно, s(x)¹ 0 является условием наличия ошибки в принятой последовательности, то есть синдромом принятой последовательности.

Синдром s(x) имеет в общем случае вид

Очевидно, что схема вычисления синдрома является схемой деления, подобной схемам кодирования рис. 3.10 или 3.11 .

При наличии в принятой последовательности r хотя бы одной ошибки вектор синдрома S будет иметь, по крайней мере, один нулевой элемент, при этом факт наличия ошибки легко обнаружить, объединив по ИЛИ выходы всех ячеек регистра синдрома.

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

— полином вектора ошибки.

Тогда полином принятой последовательности

Прибавим в этом выражении слева и справа U(x), а также учтем, что

r(x) = q(x)× g(x) + S(x), U(x) = m(x)× g(x), (3.77)

, (3.78)

то есть синдромный полином S(x) есть остаток от деления полинома ошибки e(x) на порождающий полином g(x).

Отсюда следует, что по синдрому S(x) можно однозначно определить вектор ошибки e(x), а следовательно, исправить эту ошибку.

На рис. 3.14 приведена схема синдромного декодера с исправлением однократной ошибки для циклического (7,4)-кода. По своей структуре она подобна схеме, приведенной на рис. 3.6, с той лишь разницей, что вычисление синдрома принятой последовательности производится здесь не умножением на проверочную матрицу, а делением на порождающий полином. При этом она сохраняет и недостаток, присущий всем синдромным декодерам: необходимость иметь запоминающее устройство, ставящее в соответствие множеству возможных синдромов S множество векторов ошибок e. Цикличность структуры кода в этом случае не учитывается.

Читать еще:  Java runtime exec

|следующая лекция ==>
Кодирование с использованием циклических кодов|Неалгебраические методы декодирования циклических кодов

Дата добавления: 2014-01-07 ; Просмотров: 1576 ; Нарушение авторских прав?

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Циклические коды, исправляющие кратные ошибки

Циклические коды, исправляющие кратные ошибки, обычно называются кодами БЧХ (от фамилий авторов: Боуз, Чоудхури, Хоквенгем). Хорошие корректирующие свойства и простота построения кодирующих к декодирующих устройств (особенно при необходимости обнаруживать ошибки) обеспечили кодам БЧХ широкое практическое применение. Согласно ГОСТ 17422-72, основанному на рекомендации МККТТ V×41, в системах передачи данных с решающей обратной связью предписывается использовать циклические коды со следующими параметрами: n=140, 260, 500 и 980, порождающий многочлен х 16 +х 12 +х 5 +1.

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

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

1. Принятая комбинация делится на порождающую.

2. Определяется количество q единиц в остатке:

а) если q≤p, где p — максимальное количество ошибок, исправляемых данным кодом, то ошибок в информационных разрядах нет;

б) если q>p, ошибки есть в информационных разрядах. В этом случае к остатку приписывается необходимое количество нулей, деление продолжается, подсчитывается количество нулей в новом остатке, и при необходимости аналогичная процедура повторяется до получения остатка с количеством единиц p=q.

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

Пример. Применен код БЧХ 15,5, способный исправлять почти все ошибки тройной кратности. Порождающий многочлен кода записывается так: р(х)=х 10 +х 8 +х 5 +х 4 +х 3 +х+1, что эквивалентно комбинации 10100110111. Требуется декодировать принятую комбинацию 100001101110101.

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

и сдвигаем на три разряда вправо: 101001101110000. Ошибки исправлены. В соответствии с видом синдрома ошибки имели место в 1, 4 и 6-м разрядах сдвинутой комбинации, т.е. в 1, 3 и 13-м разрядах принятой комбинации.

Указанная методика пригодна, например, для кода (15,7), исправляющего одиночные и двойные ошибки. В коде (15,5), исправляющем и тройные ошибки, данная методика позволяет исправлять почти все тройные ошибки (не исправляются тройные ошибки только в случае их расположения в следующих разрядах: ai, ai+5, ai+10, где i≤1¸5).

[1] стр. 247-255. [2] стр. 285-289. [3] стр. 149-154.

1. Являются ли циклические коды групповыми?

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

3. Какими свойствами должен обладать порождающий многочлен циклического кода?

4. Как проще всего определять синдромы ошибок в циклических кодах.

1. Записать все разрешенные комбинации циклического кода (7,4) с порождающим многочленом 1011.

2. Записать все разрешенные комбинации циклического кода (7,4) с порождающей комбинацией 1101.

3. Задан циклический код (7,4) с порождающей комбинацией 1011. Записать синдромы всех исправляемых кодом ошибок. Декодировать полученную комбинацию 1011111.

4. Получена комбинация 1111010, закодированная циклическим кодом (7,4) с порождающей комбинацией 1101. Код используется для обнаружения одиночных и двойных ошибок. Указать возможные варианты ошибок в полученной комбинации.

5. Используется код БЧХ с порождающим многочленом

х 10 +х 8 +х 5 +х 4 +х 3 +х+1

Закодировать комбинацию 11111, ввести в закодированную комбинацию три ошибки и исправить их по указанной методике.

Сверточные коды

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

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

Дата добавления: 2016-06-24 ; просмотров: 1050 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Ссылка на основную публикацию
Adblock
detector