Способы декодирования с исправлением ошибок. Декодеры Меггита.

Декодирование циклического кода в режиме исправления ошибок можно осуществлять различными способами. Ниже излагаются два способа, являющиеся наиболее простыми. В основу первого способа положено использование таблицы синдромов (декодирования), в которой каждому многочлену или образцу ошибок ei(x), соответствует определенный синдром Si(x), представляющий остаток от деления принятого слова ai(x) и соответствующего ему ei(x) на g(x). Процедура декодирования следующая. Принятое слово ai(x) делится на g(x), оперделяется Si(x) и соответствующий ему многочлен ei(x), а затем ai(x)суммируется с ei(x). В результате получаем исправленное кодовое слово, т.е. bi(x)= ai(x)+ ei(x).

В состав декодера входят: вычислитель синдрома (ВС), два регистра сдвига R1 и R2 и постоянное запоминающее устройство (ПЗУ), которое содержит слова длины n, соответствующие многочленам ошибок ei(x).

Принятое слово ai(x) поступает на вход вычислителя синдрома, где осуществляется деление его на g(x) и формирование Si(x), и одновременно на вход регистра сдвига, где ai(x) накапливается. Синдром Si(x) используется в качестве адреса, по которому из ПЗУ в регистр R1 записывается ei(x), соответствующий синдрому Si(x). Перечисленные операции завершаются за n тактов. В течение последующих n тактов происходит поэлементное суммирование содержимого R1 и R2, т.е операция bi(x)= ai(x)+ ei(x), и исправление ошибок.

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

1. Синдром Si(x), соответствующий принятому слову равен остатку от деления ai(x) на g(x), а также остатку от деления соответствующего многочлена ошибок ei(x) на g(x), т.е.

2. Если Si(x) соответствует ai(x) и ei(x), то xSi(x) является синдромом, который соответствует и или

3. При исправлении ошибок используются синдромы образцов ошибок только с ненулевыми коэффициентами в старшем разряде.

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

Для исправления ошибок, принадлежащих данному классу эквивалентности, нужно произвести n циклических сдвигов.

Декодер циклического кода с таким исправлением ошибок предложил Меггит.

Пример. Рассмотрим схему и работу декодера Меггита циклического (15,7)-кода, обеспечивающего исправление одиночных и двойных ошибок,с g(x)= x8+ x7+ x6+ x4+1.

 

 

Блок декодеров настраивается на 15 синдромов, которые представлены в таблице и соответствуют классам эквивалентности с образцами ошибок в старшем разряде.

Вариант ошибки e(x) Синдром S(x) Вариант ошибки e(x) Синдром S(x)
x14 x14+ x6
x14+ x13 x14+ x5
x14+ x12 x14+ x4
x14+ x11 x14+ x3
x14+ x10 x14+ x2
x14+ x9 x14+ x1
x14+ x8 x14+ x0
x14+ x7    

Допустим, что ошибки в 3 и 5 разрядах, т.е. им соответствует многочлен ошибки e(x)= x12+ x10.

При поступлении на вход декодера искаженного кодового слова регистр и в вычислителе формирует синдром

Блок декодеров не реагирует на этот синдром.

Затем происходит сдвиг кодового слвоа в RG, а в ВС формируется новый синдром

Блок декодеров и в этом случае не срабатывает.

При следуеющем сдвиге кодового слова в RG первый искаженный разряд занимает старшую позицию в RG, а в ВС формируется синдром

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

Следующий сдвиг приводит к формированию синдрома

Этот синдром соответствует многочлену ошибки e(x)= x13+ x0, т.к. первый искаженный разряд по обратной связи должен занимать младшую позицию RG.

На синдром S(13,0) , блок декодеров не реагирует.

При следующем сдвиге кодового слова в RG второй искаженный разряд занимает старшую позицию в RG, а в ВС формируется синдром

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

.