Исследование временных характеристик работы кодера кода Рида-Соломона в частотной области в зависимости от типа ДПФ параметров кода
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
b>Утверждение 4.5.1. Два двучлена и , , , , , можно перемножить, выполняя не более трех умножений чисел в поле F.
Действительно, ()()?, где , и
Если умножение происходит в поле 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)
В =.
Для уменьшения числа умножений, как и для 5-точечного ДПФ, воспользуемся переходом к циклической свертке с последующей редукцией по следствию из утверждения 4.5.1. Сначала воспользуемся алгоритмом Рейдера для перехода к циркулянту. Так как 5 является примитивным элементом поля GF(17), то имеем:
i1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16N=55 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1
Таким образом, без учета в нумерации одиночного окаймления, к циклической свертке приводит, например, такая перестановка строки столбцов матрицы Фурье в (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)
, , , , , , , , .
Так как суммы коэффициентов , естественн