Навигация
При исправлении ошибок используются синдромы образцов ошибок только с ненулевым коэффициентом в старшем разряде
11870
знаков
2
таблицы
5
изображений
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 с.
Похожие работы
... модуляцией, можно сделать вывод, что помехоустойчивость приемника, использующего в качестве информационного параметра фазу, почти приближена к вероятности ошибки приемника Котельникова. 3. Оптимальная фильтрация. Отметим, что оптимальный приемник, является корреляционным, сигнал на его выходе представляет собой функцию корреляции принимаемого и ожидаемого сигналов, благодаря чему ...
... кодирования можно разработать устройство, которое поможет понять принцип работы метода Хэмминга. Кодер – декодер будем разрабатывать на основе ИМС К555ВЖ1. 2.1 Разработка устройства кодирования информации методом Хемминга Кодер, преобразует 32х битное слово в 38ми разрядный код Хэмминга, после чего слово хранится в памяти или передаётся по шинам и т.д. В процессе передачи или хранения в ...
... и исправления ошибок в текстах на естественных языках (назовем их автокорректорами - АК, хотя терминология ещё не сложилась) получают все большее распространение. Они используются, в частности, в пакетах WINWORD и EXCEL для проверки орфографии текстовой информации. Говоря точнее, АК производят автоматически лишь обнаружение ошибок, а собственно коррекция ведется обычно при участии человека. 1. ...
... ITU-T серии V, реализованный в обоих модемах. На этом этапе соединение устанавливается согласно Рекомендациям V.25 и V.8. Если оба модема поддерживают протокол V.34, то они переходят ко второй фазе, в ходе которой производится классификация канала связи. В течение 3 и 4 фазы происходит обучение адаптивного эквалайзера, эхокомпен-сатора и ряда других систем модема. После установления соединения ...
0 комментариев