Исследование временных характеристик работы кодера кода Рида-Соломона в частотной области в зависимости от типа ДПФ параметров кода
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
о, вычисляются заранее и вводятся в алгоритм фиксированными константами, то всего имеем 9 умножений и 17 сложений. Для входящих в (20) коэффициентов, величины
соответственно равны:
Полное число сложений и умножений для этой реализации равно соответственно 129 и 61. Для полного БПФ по длине 255 имеем 1935 сложений и 1255 умножений.
4.7 БПФ-укороченные коды Рида-Соломона
В 4.2 было дано спектральное описание циклического кода. Согласно этому описанию, кодовое слово находится спектре кодового слова информационного вектора, содержащего подряд идущих нулей. При таком подходе код способен исправлять не более ошибок. Были построены эффективные алгоритмы вычисления ДПФ длин 3, 5, 17 над полем и быстрый алгоритм вычисления ДПФ длины 255.
На практике, однако, не всегда возможно (или целесообразно) применять кодовые слова длины 255 над . Одним из путей уменьшения требуемых вычислительных ресурсов и снижения времени обработки данных при кодировании и декодировании применение так укороченных РС-кодов.
-укороченный РС-код представляет собой подпространство полного кода. При этом все кодовые слова длины укороченного кода заканчиваются нулями. Такой код можно записать . Работают с ним так же, как и с полным кодом, просто он имеет не , а информационных позиций.
Алгоритмы кодирования при прямом способе укорочения РС-кода совпадают с алгоритмами для полного кода. Поэтому временные характеристики несистематического кодера, основанного на спектральной технологии кодирования остаются такими же, как и для полного кода. Объясняется это тем, что при несистематическом кодировании, когда к информационному вектору применяется быстрое преобразование Фурье (БПФ), весь массив данных (все 255 координат) обрабатываются одновременно и вычисления проводятся сразу для нескольких групп точек. При этом обнуляемые позиции кодового слова равномерно распределяются по всему трехмерному кубу, реализующему БПФ, и автоматически включаются в вычисления на полной длине кодового слова. Поэтому целесообразно сделать укорочение кодового слова таким образом, чтобы сократить вычисления в алгоритмах БПФ.
4.8 Несистематические БПФ-укорочения
Порядок мультипликативной группы поля является составным числом n=255=3*5*17. Группа является циклической и порождается примитивным элементом ?; она содержит 255 элементов: . Эта группа имеет циклические подгруппы порядка (делят ).
В таблице 1 приведены циклические подгруппы мультипликативной группы поля .
Таблица 1. Циклические подгруппы мультипликативной группы поля
Порядок подгруппыПорождающий элементПодгруппа3515175185
В основе несистематического кодирования укороченных РС-кодов лежит дискретное преобразование Фурье (ДПФ) на группе, образуемой ненулевыми элементами поля.
Кодовое слово задается как ДПФ информационного вектора cинформационными символами и нулями, где , а в качестве примитивного элемента выбран корень неприводимого многочлена .
Aлгоритм трехмерного ДПФ позволяет вычислить элементы кодового вектора по формуле:
(24)
Рассмотрим преобразование Фурье длины в поле . Элементами этого преобразование должны быть элементы подгруппы, образованной примитивным элементом (в соответствии с таблицей 1). Перекодируем укороченный вектор (вектор длины 51) в полный вектор (длины 255) таким образом, чтобы все координаты , для которых , были нулевыми. Практически это означает, что мы разместим укороченный вектор только в одной плоскости БПФ-куба там, где . Тогда формулу (24) можно переписать в виде:
(25)
А это означает переход к ДПФ с ядром для вектора . Преобразование Фурье вычисляется как значение многочлена в точках поля: , что эквивалентно работе в подгруппе с ядром : .
Очевидно, что для реализации БПФ-укорочения длины 85 с порождающим элементом из формулы (24) необходимо исключить суммирование по , что достигается путем размещения укороченного вектора в плоскости БПФ-куба там, где . Это означает переход к ДПФ с ядром для мультипликативной подгруппы порядка 85 с шагом 3.
(26)
Проводя аналогичные рассуждения можно построить формулы вычисления ДПФ для всех циклических подгрупп, указанных в таблице 1. Эти БПФ-укорочения можно применить для кодирования укороченными кодами Рида-Соломона над полем длин n=85,51,17,15,5,3.
Заключение
На основании китайской теоремы об остатках получен результат, существенно понижающий вычислительную сложность ДПФ. Приведены формулы для трехмерного преобразования Фурье поле . Построены алгоритмы быстрого преобразование Фурье (БПФ) длин 3, 5 и 17 на основе алгоритма Рейдера и алгоритма Винограда вычисления циклической свертки. Показана эквивалентность между вычислением ДПФ простой длины и вычислением циклической свертки.
На основании трехмерного преобразования Фурье построены укороченные преобразования длин 15, 51, 85, которые рационально применять, когда не требуется кодировать слова длины 255. Показана эквивалентность между укорочением преобразования и переходом на соответствующую ему подгруппу мультипликативной группы поля.
В приложении представлен программный комплекс, реализующий построение поля основные операции в этом поле, вычисление значения произвольного многочлена в любой точке поле, вычисление ДПФ, ОДПФ, трехмерного преобразования Фурье и БПФ длин 255,85,51,15,17,5,3, кодирование кодом Рида-Соломона в частот