Рефетека.ру / Коммуникации и связь

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

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


кафедра РЭС


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


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


МИНСК, 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.

ЛИТЕРАТУРА


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

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

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

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

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

Похожие работы:

  1. • Многофункциональный контроллер ВЗУ
  2. • Многофункциональный контроллер ВЗУ
  3. • Теории электрической связи: Расчет приемника, оптимальная ...
  4. • Проектирование устройства передачи данных по ...
  5. • Проектирование системы передачи цифровых данных
  6. • Разработка устройства кодирования-декодирования 32-х ...
  7. • Основные мероприятия по повышению эффективности ...
  8. • Теория информации
  9. • Программный кодер-декодер для циклических (n,k ...
  10. • Обмен информацией. Передатчик и приемник
  11. • Модель радиотехнической передачи информации. Источник ...
  12. • Многоканальная система передачи информации
  13. • Технология цифровой связи
  14. • Штриховое кодирование: виды и области применения
  15. • Развитие умений декодирования невербальной информации у ...
  16. • Практическое кодирования по Хэммингу
  17. • Теория электрической связи
  18. • Эскизное проектирование радиоэлектронной системы ...
  19. • Основы кодирования
Рефетека ру refoteka@gmail.com