Вход

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

Реферат по радиоэлектронике
Дата добавления: 20 июня 2009
Язык реферата: Русский
Word, rtf, 1 Мб
Реферат можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу

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



кафедра РЭС










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


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












МИНСК, 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 формируется синдром , от которого срабатывает БДК. В результате исправляется вторая ошибка в кодовом слове.

Коды Рида-Соломона (РС)

Коды РС являются недвоичными циклическими кодами, символы кодовых слов которых берутся из конечного поля GF(q). Здесь q степень некоторого простого числа, например q=2m.

Допустим, что РС-код построен над GF(8), которое является расширением поля GF(2) по модулю примитивного многочлена f(z)=z3+z+1. В этом случае символы кодовых слов кода будут иметь значения, представленные в таблице 2.


Таблица 2

000

0

0

011

z+1

?3

001

1

?0

110

z2+z

?4

010

z

?1

111

z2+z+1

?5

100

z2

?2

101

z2+1

?6


Кодовые слова РС-кода отображаются в виде многочленов
,
где N - длина кода; Vi - q-ичные коэффициенты (символы кодовых слов), которые могут принимать любое значение из GF(q).

Эти коэффициенты как это следует из таблицы, также отображаются многочленами с двоичными коэффициентами . Коды РС являются максимальными, т.к. при длине кода N и информационной последовательности k они обладают наибольшим кодовым расстоянием d=N-k+1.

Порождающим многочленом g(x) РС-кода является делитель двучлена xN+1 степени меньшей N с коэффициентами из GF(q) при условии, что элементы этого поля являются корнями g(x). Здесь - примитивный элемент GF(q).

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

Степень g(x) равна d-1=N-k=R.

В РС-кодах принадлежность кодовых слов данному коду определяется выполнением d-1 уравнений в соответствии с выражением (*), где Vi - символы-коэффициенты из GF(q); z0, z1... zN-1 - ненулевые элементы GF(q).

Элементы z0, z1... zN-1 называются локаторами, т.е. указывающими на номер позиции символа кодового слова.

Например, указателем i - позиции является локатор zi или элемент ?i GF(q).

Так как все локаторы должны быть различны и причем ненулевыми, то их число в GF(q) равно q-1. Следовательно, такое количество символов должно быть в кодовых словах кода.Поэтому обычно длина РС-кода определяется из выражения N=q-1.

Пример. Допустим, что длина РС-кода равна N, кодовое расстояние d=3, то в соответствии с (*) проверочными уравнениями будут


Свойства РС-кодов.

1. Циклический сдвиг кодовых слов, символы которых принимают значение из GF(q), порождает новые кодовые слова этого же кода.

2. Сумма по mod2 двух и более кодовых слов дает кодовое слово, принадлежащее этому же коду.

3. Кодовое расстояние РС-кода определяется не по двоичным элементам, а по q-ичным символам.

4. В РС-коде, исправляющем tu ошибок порождающий многочлен определяется из выражения . Обычно m0 принимают равным 1. Однако, с помощью разумного выбора значения m0, иногда можно упростить схему кодера.

5. Корректирующие способности РС-кода определяются его кодовым расстоянием.

где T0 и Tu - длина пакетов, в которых обнаруживаются и исправляются ошибки.

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

Пример. Требуется сформировать кодовое слово РС-кода над GF(23), соответствующее двоичной информационной последовательности a(1,0)=000000011100101.

Так как m=3, то каждый q-ичный символ кода состоит из трех двоичных элементов. Поэтому с учетом таблицы 6 a(x)=?3x2+ ?2x+?6.

Определяем параметры кода. N=q-1=7; k=5; R=2; d=N-k+1=3;
.

Кодовое слово формируется в соответствии с выражением. ,
где . 

В результате или в двоичной форме V(1,0)=000.000.011.100.101.101.101.


ЛИТЕРАТУРА


  1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

  2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с.

  3. Цапенко М.П. Измерительные информационные системы. - . – М.: Энергоатом издат, 2005. - 440с.

  4. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

  5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.


© Рефератбанк, 2002 - 2018