Циклические коды, исправляющие кратные ошибки
Циклические коды, исправляющие кратные ошибки, обычно называются кодами БЧХ (от фамилий авторов: Боуз, Чоудхури, Хоквенгем). Хорошие корректирующие свойства и простота построения кодирующих к декодирующих устройств (особенно при необходимости обнаруживать ошибки) обеспечили кодам БЧХ широкое практическое применение. Согласно ГОСТ 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.
Производим деление:
100001101110101 / 10100110111
Å 10100110111
==10000000001
Å 10100110111
==10011011001
Å 10100110111
==11110111000
Å 10100110111
=10100011110
Å 10100110111
=====101001
В остатке три единицы, следовательно, на этом деление прекращаем. В процессе деления к делимой комбинации было дописано три нуля, поэтому для исправления ошибки декодируемую комбинацию сдвигаем на три разряда влево, суммируем с остатком:
Å 101001
001101110000101
и сдвигаем на три разряда вправо: 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-01-18; просмотров: 1182;