Особенности практического применения способов кодирования. Способы декодирования с обнаружением ошибок (63825)

Посмотреть архив целиком

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



кафедра РЭС



















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



«Особенности практического применения способов кодирования. Способы декодирования с обнаружением ошибок»























МИНСК, 2009


Задача кодирования заключается в формировании по информационным словам a(x) кодовых слов (x) циклического (n,k)-кода, который по своей структуре может быть несистематическим и систематическим.

Формирование кодовых слов несистематического кода заключается в умножении многочлена a(x), отображающего информационную последовательность длины k, на порождающий многочлен, т.е. (x)=a(x)(g(x). Формирование кодовых слов систематического кода заключается в преобразовании информационной последовательности a(x) в соответствии с выражением (x)=a(x)xr+r(x).

Проверочная последовательность r(x) определяется двумя способами:
при использовании "классического" способа кодирования ;
при использовании способа кодирования, рекомендованного МККТТ ,
где x(1)r-1 - единичный многочлен степени (r-1).

Указанные выше математические операции выполняют кодеры несистематического и систематического кодов.


Способы декодирования с обнаружением ошибок


Процедура декодирования циклического кода с обнаружением ошибок, по аналогии с процессом кодирования, использует два способа:
- при кодировании "классическим" способом декодирование основано на использовании свойства делимости без остатка кодового многочлена (x) циклического (n,k)-кода на порождающий многочлен g(x). Поэтому алгоритм декодирования включает в себя деление принятого кодового слова, описываемого многочленом на g(x), вычисление и анализ остатка r(x). Если r(x)=0, то принятое кодовое слово считается неискаженным. Если r(x)0, то принятое кодовое слово стирается и формируется сигнал "ошибка".
- при кодировании способом МККТТ декодирование основано на свойстве получения определенного контрольного остатка R0(x) при делении принятого кодового многочлена (x) на порождающий многочлен. Поэтому, если полученный при делении остаток , то принятое кодовое слово считается неискаженным. Если остаток , то принятое кодовое слово стирается и формируется сигнал "ошибка". Значение контрольного остатка определяется из выражения .


Способы декодирования с исправлением ошибок и схемная реализация декодирующих устройств


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

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

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

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

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

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

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

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

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

Простейшим является декодер Меггитта. В состав декодера входят: вычислитель синдрома, осуществляющий деление кодового слова на g(x) и формирование соответствующего синдрома; блок декодеров (ДК), который настроен на синдромы всех образцов исправляемых ошибок с ненулевыми старшими разрядами; регистр сдвига RG.

При поступлении на вход схемы кодового слова его символы заполняют регистр RG, а в вычислителе формируется соответствующий синдром Si(x). Вычисленный синдром сравнивается со всеми табличными синдромами, заложенными в схему блока ДК, и в случае совпадения с одним из них на его выходе формируется сигнал, который исправляет ошибочный символ, находящийся в старшем разряде регистра. После этого содержимое вычислителя и RG циклически сдвигается на один шаг. Этот сдвиг реализует операции и . Если новый синдром совпадает с одним из табличных синдромов, то это означает, что произошла ошибка во втором по старшинству символе кодового слова, который, перейдя в старший разряд RG, исправляется. Затем производится новый циклический сдвиг на одну позицию и новая проверка на совпадение синдромов. После повторения этого процесса n раз в RG будет сформировано исправленное кодовое слово. Введение обратной связи для RG не обязательно, так как в процессе исправления ошибок символы кодового слова поступают на выход декодера.

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












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

Таблица 1

е(х)

S(x)

е(х)

S(x)

1

x14

x7+ x6+x5+ x3

9

x14+ x6


2

x14+ x13

x7+ x4+x3+ x2

10

x14+ x5

x7+ x6+x3

3

x14+ x12

x7+ x6+x4+ x

11

x14+ x4

x7+ x6+x5+ x4+x3

4

x14+ x11


12

x14+ x3

x7+ x6+x5

5

x14+ x10


13

x14+ x2

x7+ x6+x5+ x3+x2

6

x14+ x9


14

x14+ x1

x7+ x6+x5+ x3+x

7

x14+ x8


15

x14+ x0

x7+ x6+x5+ x3+0

8

x14+ x7






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

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

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

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

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

При следующем сдвиге кодового слова в RG первый искаженный разряд занимает старшую позицию в RG, а в BC формируется синдром , от которого срабатывает БДК. В результате исправляется первая ошибка.

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

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

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

При следующем сдвиге кодового слова в RG второй искаженный разряд занимает старшую позицию в RG, а в BC формируется синдром , от которого срабатывает БДК. В результате исправляется вторая ошибка в кодовом слове.


Случайные файлы

Файл
177680.rtf
GURIEVSK.DOC
89677.rtf
ref-14265.doc
53348.doc




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.