Особенности практического применения способов кодирования. Способы декодирования с обнаружением ошибок
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
кафедра РЭС
реферат на тему:
«Особенности практического применения способов кодирования. Способы декодирования с обнаружением ошибок»
МИНСК, 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, то принятое
кодовое слово стирается и формируется
сигнал "ошибка".
- при кодировании
способом МККТТ декодирование основано
на свойстве получения определенного
контрольного остатка R>0>(x)
при делении принятого кодового многочлена
(x) на порождающий многочлен. Поэтому,
если полученный при делении остаток
,
то принятое кодовое слово считается
неискаженным. Если остаток
,
то принятое кодовое слово стирается и
формируется сигнал "ошибка".
Значение контрольного остатка определяется
из выражения
.
Способы декодирования с исправлением ошибок и схемная реализация декодирующих устройств
Декодирование циклического кода в режиме исправления ошибок можно осуществлять различными способами. Ниже излагаются два способа, являющиеся наиболее простыми.
В основу первого способа положено
использование таблицы синдромов
(декодирования), в которой каждому
многочлену или образцу ошибок e>i>(x),
соответствует определенный синдром
S>i>(x),
представляющий остаток от деления
принятого кодового слова
и
соответствующего ему e>i>(x)
на g(x). Процедура декодирования следующая.
Принятое кодовое слово
делится
на g(x), определяется S>i>(x)
и соответствующий ему многочлен e>i>(x),
а затем
суммируется
с e>i>(x). В
результате получаем исправленное
кодовое слово, т.е.
.
В состав декодера входят:
вычислитель синдрома (ВС), два регистра
сдвига RG1 и RG2, постоянное запоминающее
устройство (ПЗУ), которое содержит
слова
длины n, соответствующие многочленам
ошибок e>i>(x).
Принятое кодовое слово
поступает
на вход вычислителя синдрома, где
осуществляется деление его на g(x) и
формирование S>i>(x),
и одновременно - на вход RG2, где
накапливается.
Синдром S>i>(x)
используется в качестве адреса, по
которому из ПЗУ в регистр RG1 записывается
e>i>(x),
соответствующий синдрому S>i>(x).
Перечисленные операции завершаются за
n тактов. В течение последующих n тактов
происходит поэлементное суммирование
содержимого RG2 и RG1, т.е. операция
,
и исправление. ошибок.
В основе второго способа исправления ошибок, позволяющего значительно сократить объем используемых табличных синдромов и существенно упростить схему декодера, лежат следующие положения:
1. Синдром S>i>(x),
соответствующий принятому кодовому
слову равен остатку от деления
на
g(x), а также остатку от деления
соответствующего многочлена ошибок
ei(x) на g(x), т.е.
.
2. Если S>i>(x)
соответствует
и
e>i>(x), то x(
S>i>(x) является
синдромом, который соответствует
и
или
.
3. При исправлении ошибок используются синдромы образцов ошибок только с ненулевым коэффициентом в старшем разряде.
Поэтому при реализации этого способа множество всех образцов ошибок разбивается на классы эквивалентности. Каждый класс представляет циклический сдвиг одного образца ошибок, а синдром этого класса соответствует образцу ошибок с ненулевым старшим разрядом. Если вычисленный синдром принадлежит одному из классов эквивалентности образцов исправляемых ошибок, то старший символ кодового слова исправляется. Затем принятое слово и синдром циклически сдвигается, а процесс нахождения в предыдущей по старшинству позиции повторяется.
Для исправления ошибок, принадлежащих данному классу эквивалентности, нужно произвести n циклических сдвигов.
Простейшим является декодер
Меггитта. В состав декодера входят:
вычислитель синдрома, осуществляющий
деление кодового слова
на
g(x) и формирование соответствующего
синдрома; блок декодеров (ДК), который
настроен на синдромы всех образцов
исправляемых ошибок с ненулевыми
старшими разрядами; регистр сдвига RG.
При поступлении на вход схемы
кодового слова
его
символы заполняют регистр RG, а в
вычислителе формируется соответствующий
синдром S>i>(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 - длина кода; V>i>
- 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 уравнений в соответствии с выражением
(*),
где V>i> -
символы-коэффициенты из GF(q); z>0>,
z>1>... z>N-1>
- ненулевые элементы GF(q).
Элементы z>0>, z>1>... z>N-1> называются локаторами, т.е. указывающими на номер позиции символа кодового слова.
Например, указателем i - позиции является локатор zi или элемент i GF(q).
Так как все локаторы должны быть различны и причем ненулевыми, то их число в GF(q) равно q-1. Следовательно, такое количество символов должно быть в кодовых словах кода.Поэтому обычно длина РС-кода определяется из выражения N=q-1.
Пример. Допустим,
что длина РС-кода равна N, кодовое
расстояние d=3, то в соответствии с (*)
проверочными уравнениями будут
Свойства РС-кодов.
1. Циклический сдвиг кодовых слов, символы которых принимают значение из GF(q), порождает новые кодовые слова этого же кода.
2. Сумма по mod2 двух и более кодовых слов дает кодовое слово, принадлежащее этому же коду.
3. Кодовое расстояние РС-кода определяется не по двоичным элементам, а по q-ичным символам.
4. В РС-коде, исправляющем t>u>
ошибок порождающий многочлен определяется
из выражения
.
Обычно m>0>
принимают равным 1. Однако, с помощью
разумного выбора значения m>0>,
иногда можно упростить схему кодера.
5. Корректирующие способности
РС-кода определяются его кодовым
расстоянием.
где
T>0> и T>u>
- длина пакетов, в которых обнаруживаются
и исправляются ошибки.
Обнаружение ошибок в кодовых
словах состоит в проверке условий ((),
т.е. определении синдрома
,
элементы которого определяются из
выражения
.
Пример. Требуется сформировать кодовое слово РС-кода над 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 с.