RUS ENG

< Кодовые каникулы
21.03.2018 16:00 Давность: 212 days
Категория: Семинар

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

проф. С.В. Федоренко (ГУАП)


Излагается малоизвестный метод вычисления ДПФ над полем комплексных чисел (DUHAMEL-HOLLMANN, 1984) с линейной мультипликативной сложностью. Возможно, это единственный метод вычисления ДПФ с линейной мультипликативной сложностью. Предпринимается попытка построить алгоритм вычисления ДПФ над конечным полем с линейной мультипликативной сложностью, использующий идеи DUHAMEL-HOLLMANN и автора. Предлагается почти новый алгоритм вычисления ДПФ длины 2^2^l-1, и рассказывается о проблемах построения алгоритма для произвольной длины.