Исследование временных характеристик работы кодера кода Рида-Соломона в частотной области в зависимости от типа ДПФ параметров кода

Действительно, ()()\, где , и

Если умножение происходит в поле F, то , где ,

Следствие 4.5.1. Два многочлена степени m над полем F можно перемножить, выполняя не более умножений чисел в поле F.

Например, для m=3 (с учетом, что char GF()=2) имеем:

\\=

\

где t\ (так что при вычислении по модулю многочлена надо делать редукцию по модулю ); согласно утверждению 4.5.1:

\

\

\

Для вычисления , , опять воспользуемся утверждением 4.5.1. Имеем

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

Для коэффициентов при, согласно (10) - (12)

,

,

,

,

,

,

,

Если произведение вычисляется в кольце F(так что ), то формулы (10) - (12) принимают вид:

?, (10а)

, ?

,

.

Вычисление вектора гдеа - циркулянт, первая строка которого задается вектором , равносильно вычислению в F произведения , где

 и .

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

Утверждение 4.5.2. Для ДПФ простой длины n всегда существует такая перестановка строк и столбцов матрицы Фурье, что она может быть превращена в окаймленный циркулянт.

Этот результат принадлежит Рейдеру. Мы подробно проиллюстрируем соответствующий алгоритм в следующем пункте, посвященному БПФ длины 17, а сейчас вернемся к БПФ длины 5.

Прежде всего избавимся от единичного окаймления матрицы Фурье:

= )

В столбцах и строках матрицы, стоящей в правой части равенства выполним перестановку . Если выполним такую же перестановку координат у векторов d и его спектра А, получаем

) (14)

Циркулярная матрица для БПФ длины 5 получается, если задать нумерацию ненулевого элемента поля GF(5) с образующей 3: 1 (mod5), 33 (mod5), 4 (mod5), 2 (mod5): .

Этим задача свелась, согласно утверждения 4.5.2, к вычислению многочлена c(x)=d(x) w(x) mod(x-1), где d(x)= или, иначе, циклической свертки с=с

Для вычисления этой циклической свертки длины 4, перепишем формулы (13) в более удобном для организации экономного вычисления виде:

, ;

(15)

Этот алгоритм содержит 9 умножений и 17 сложений. Но если появляются какие-то условия на коэффициенты или, то число вычислений уменьшается. Например, если =0 или 1, то число умножений равно только 5. В нашем случае и так как - ядро БПФ длины 5, то=1. Учитывая это, из формул (13) - (14) окончательно приходим к следующему алгоритму:

, , , , , , , , , , , . (16)

Так что алгоритм БПФ длины 5 в поле в нашем случае содержит 5 умножений и 11 сложений.

4.6 Быстрое преобразование Фурье длины 17

17-точечное ДПФ с ядром задается равенством

(17)

В =.

Для уменьшения числа умножений, как и для 5-точечного ДПФ, воспользуемся переходом к циклической свертке с последующей редукцией по следствию из утверждения 4.5.1. Сначала воспользуемся алгоритмом Рейдера для перехода к циркулянту. Так как 5 является примитивным элементом поля GF(17), то имеем:

Таким образом, без учета в нумерации одиночного окаймления, к циклической свертке приводит, например, такая перестановка строки столбцов матрицы Фурье в (17) (соответствующих координат преобразуемого вектора а и спектра А), которая дается второй строкой этой таблицы: единичное окаймление остается на месте, а первая строка циркулянта соответственно имеет вид:

получаем,

, (18)

где , - вектор, полученный из спектра А указанной перестановкой координат, а - вектор столбец, определяемый вторым равенством в (18).

Согласно утверждению 4.5.2, задача вычисления (18) эквивалентна задаче вычисления циклической свертки

(19)

Вычислять свертку (19) будем следующим образом. Пусть (так что ) и пусть

Так что

,

,

Сначала будем полагать переменную х параметром и найдем циклическую свертку по модулю . Обозначая , согласно равенствам (15) имеем:

(20)

В поле для элемента выполняется тождества:

; ;

(21)

Эти тождества позволяют упростить вычисления величин, входящих в (20). Например,

Aлгоритм вычисления R(x)=r(x) для произвольного многочлена содержит 4 умножения и 12 сложений. А именно, воспользуемся равенством (12) и учтем, что в поле согласно второму из тождеств в (20) выполняется равенство , char=2. Имеем:

При табличной реализации умножения необходимо иметь только один массив длины 256 произведений всех элементов поля на элемент . Алгоритм:

(22)

Для остальных 5 умножений вида R(x)=r(x) b(x) число умножений не уменьшается, равно 9, и алгоритм, согласно (12), можно записать в виде:

Алгоритм: , , , , , ,

, , , , , , (23)

, , , , , , , , .

Так как суммы коэффициентов , естественно, вычисляются заранее и вводятся в алгоритм фиксированными константами, то всего имеем 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. Циклические подгруппы мультипликативной группы поля

В основе несистематического кодирования укороченных РС-кодов лежит дискретное преобразование Фурье (ДПФ) на группе, образуемой ненулевыми элементами поля.

Кодовое слово задается как ДПФ информационного вектора 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, кодирование кодом Рида-Соломона в частотной области.

Проведенные вычислительные эксперименты показали практическую эффективность перехода от ДПФ к трехмерному преобразованию: если на вычисление ДПФ длины 255 затрачивается примерно 300-350 мс машинного времени, то трехмерное преобразование занимает от 20 до 35 мс. При этом на вычисление БПФ длины 255 затрачивается всего 13-17 мс.

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

Языком реализации выбран Borland Delphi Enterprise 2007.

Список использованной литературы

1. Берлекэмп Э.Р. Алгебраическая теория кодирования. М.: Мир, 1971

2. Nussbaumer H.J. Fast Fourier Transform and Convolution Algorithms. - Springer-Verlag: Berlin, Heidelberg, New York, 1981.

3. Помехоустойчивое кодирование и надежность ЭВМ. М.: Наука, 1987.

4. Макмеллан Дж.Х., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983.

5. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

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

7. Золотарев В.В. Помехоустойчивое кодирование. Методы и алгоритмы:

справочник / В.В. Золотарев, Г.В. Овечкин. - М.: Горячая линия -

Телеком, 2004. - 126 с.

8. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.

9. Лидл Р., Нидеррайтер Г. Конечные поля, т. 1. М.: Мир, 1988

10. Волошина В.Н., Руднева И.В. Надежное хранение информации с помощью кодов Рида-Соломона: Препр. Владивосток: ИАПУ ДВНЦ АН СССР, 1987, 13 с.

11. Волошина В.Н., Герасимов В.В., Руднева И.В., Программно-технологическая система хранения информации с повышенной надежностью: Препр. Владивосток: ИАПУ ДВО АН СССР, 1989, 22 с.

Размещено на Allbest.ru