Студопедия — Декодирование РС–кодов в частотной области
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Декодирование РС–кодов в частотной области






 

При декодировании РС–кодов в качестве синдрома может быть использовано «пустое» для всех слов РС–кода спектральное окно шириной s. Действительно, если наблюдение свободно от ошибок, то внутри окна будут отсутствовать ненулевые спектральные компоненты. Следовательно, появление ненулевых компонент ДПФ вектора указывает на то, что некоторые символы переданного слова РС–кода были искажены, так что конкретный образец этих компонент может быть использован для исправления ошибок.

В дальнейшем будем полагать, что , так что

и «нулевое окно» охватывает частоты . Тогда спектральные компоненты наблюдения (в полиномиальной форме ) внутри нулевого окна определяются вектором ошибки (или, что эквивалентно, полиномом ошибки ):

.

Таким образом, первой операцией, выполняемой при декодировании в частотной области, является вычисление компонент синдрома в виде прямого ДПФ компонент наблюдения на частотах, лежащих внутри нулевого окна:

. (9.8)

Все последующие шаги направлены на экстраполяцию спектра ошибок, определенного в пределах нулевого окна, на всю частотную область. Это оказывается возможным, если только фактическое число ошибочных символов n не превосходит исправляющей способности РС–кода: .

Пусть обозначают позиции ненулевых символов в векторе ошибок:

.

Поскольку – примитивный элемент поля и его мультипликативный порядок равен , то степени примитивного элемента можно использовать для маркировки позиции в –мерном векторе ошибок . Назовем локатором ошибок i –ю степень примитивного элемента поля для любого i, входящего во множество позиций ошибочных символов и построим полином локаторов ошибок переменной x степени n вида

. (9.9)

Очевидно, что все величины, обратные локаторам ошибок , являются корнями полинома . С другой стороны, подстановка в выражение (9.9) для дает компоненты обратного ДПФ последовательности коэффициентов полинома локаторов ошибок:

.

Поскольку для любого i, при котором , то при всех , тогда на основании теоремы о свертке 9.2.1

,

или, учитывая, что , получаем

, (9.10)

в котором знак «минус» может быть опущен в случае полей . Полученный результат имеет чрезвычайную важность, показывая, что компоненты ДПФ вектора ошибок образуют линейную рекуррентную последовательность памяти n, величина которой в точности равна числу ошибочных символов. Следовательно, как только значения n и коэффициентов полинома локаторов ошибок станут известными, а память n не превысит исправляющей способности t, т.е. половины ширины нулевого окна, то из значения синдрома может быть восстановлен весь спектр ошибок.

Теорема 9.4.1. Величина памяти n рекурсии спектральных компонент вектора ошибок, где n – истинное число ошибочных символов, как минимум, равна единице.

В зависимости от кратности исправляемых ошибок используются различные алгоритмы определения коэффициентов многочлена локаторов . В том случае, когда РС–код ориентирован на исправление ошибок большой кратности, эффективным оказывается метод Берлекэмпа–Месси. Суть его состоит в сведении данной задачи к нахождению коэффициентов многочлена, который задает линейный регистр сдвига минимальной длины с обратной связью, генерирующий известную последовательность компонентов синдрома. Если же БЧХ–код рассчитан на исправление ошибок малой кратности, то используется метод Питерсона–Горенстейна–Цирлера, основу которого составляет следующая теорема.

Составим матрицу размерности вида

.

Теорема 9.4.2. Матрица является вырожденной, если ее порядок , и невырожденной, если , где n – фактическое число ошибочных символов.

На основании приведенных результатов приходим к следующей процедуре декодирования:

1. Вычисление компонентов синдрома с помощью прямого ДПФ (9.8) вектора наблюдений в пределах нулевого окна;

2. Составление матрицы , начиная с и уменьшая значение m на единицу всякий раз, когда оказывается вырожденной. Если же – не вырождена, то становится известным величина n.

3. При известном значении n с помощью рекурсии (9.10) составляется линейная система из n уравнений с неизвестными:

(9.11)

в которой используются вычисленные на первом этапе компоненты синдрома , где , и которая в матричной форме представляется как

,

где и . Решение системы уравнений (9.11)

,

дает коэффициенты полинома локаторов ошибок, т.е. коэффициенты рекурсии спектра ошибок.

4. С помощью рекурсии (9.10) восстанавливается весь спектр ошибок

.

5. Осуществляется обратное ДПФ

,

для получения оценки вектора ошибок .

6. Вычитание (суммирование в случае ) оценки из вектора наблюдений дает оценку принятого кодового слова: .

С практической точки рациональный путь нахождения значений памяти и коэффициентов рекурсии предоставляет алгоритм Берлекэмпа–Месси, основой которого служит структура обычного регистра сдвига с линейной обратной связью (LFSR), генерирующего линейную рекуррентную последовательность , представленная на рис. 9.2. При начальной загрузке данная схема формирует на выходе остальные элементы согласно соотношению

.

 
 

Алгоритм Берлекэмпа–Месси представляет собой итеративную процедуру, начинающуюся со значения и начальной загрузки . На j –м шаге итераций алгоритм берет следующий по порядку компонент синдрома и строит LFSR минимальной длины, генерирующий последовательность . Если регистр, построенный на предыдущем шаге итераций, способен сформировать указанную последовательность, алгоритм прямо переходит к следующему шагу итераций. В противном случае, перед переходом осуществляется пересчет коэффициентов и, если необходимо, увеличивается значение памяти.

Процедура декодирования завершается одним из трех возможных исходов:

· если фактическое число ошибок не превышает исправляющей способности кода , то процедура завершается правильным декодированием;

· если фактическое число ошибок превосходит исправляющую способность кода t (), а наблюдение расположено на расстоянии меньшем t от некоторого другого кодового слова , то принимается решение о приеме этого ошибочного слова без возможности установления этой ситуации (неправильное декодирование);

· Если , но отсутствует кодовое слово на расстоянии меньшем t от наблюдения, то декодер (учитывая, что значение синдрома не нулевое и отсутствует возможность ассоциирования наблюдения с тем или иным кодовым словом) сигнализирует, что произошла обнаруживаемая, но не исправляемая ошибка (обнаружение ошибки).

Геометрическая интерпретация указанных трех ситуаций представлена на рис. 9.3, на котором вектора и отвечают истинному и ложному кодовым словам соответственно, а индексация вектора наблюдений произведена в соответствии с порядком приведенных выше исходов декодирования.

Пример 9.4.1. Рассмотрим (7,3) РС–код из примера 9.1.1, использующий конструкцию поля , которое строится на основе примитивного полинома (см. примет 8.2.5), т.е. с помощью примитивного элемента, удовлетворяющего соотношению . Расстояние кода и, значит, код исправляет любые ошибки кратности один и два. Пусть вектор наблюдения задан в виде , так что .

Первоначально вычислим значения компонентов синдрома с помощью прямого ДПФ (9.8) вектора наблюдений в пределах нулевого окна, т.е. на частотах , где :

,

.

Составим матрицу размерности (2´2):

,

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

Таким образом, линейная система состоит только из одного уравнения вида: , так что , откуда . В итоге приходим к рекурсии вида , которая начинается с , т.е. . Восстановив с помощью рекурсии весь спектр ошибки, первые четыре компонента которого совпадают с компонентами синдрома, осуществляем обратное ДПФ, которое приводит к следующему результату

Так, например:

.

Таким образом, оценка вектора ошибки содержит единственный ненулевой элемент z на четвертой позиции (при начале индексации с нуля) и нулевые элементы на всех остальных. Так что на выходе декодера появится решение о приеме сигнала или в виде полинома . Не составляет труда убедиться, что полученный вектор является словом РС–кода (например, проверить, что его синдром равен нулю):

,

.

Пример 9.4.2. В условиях предыдущего примера предположим, что вектор наблюдения , так что . Тогда компоненты синдрома принимают следующие значения и , так что матрица

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







Дата добавления: 2015-04-19; просмотров: 696. Нарушение авторских прав; Мы поможем в написании вашей работы!



Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

Эффективность управления. Общие понятия о сущности и критериях эффективности. Эффективность управления – это экономическая категория, отражающая вклад управленческой деятельности в конечный результат работы организации...

Мотивационная сфера личности, ее структура. Потребности и мотивы. Потребности и мотивы, их роль в организации деятельности...

Классификация ИС по признаку структурированности задач Так как основное назначение ИС – автоматизировать информационные процессы для решения определенных задач, то одна из основных классификаций – это классификация ИС по степени структурированности задач...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия