Циклическую свёртку (стандартную операцию в цифровой обработке сигналов) и диадическую свёртку можно вычислить за одинаковое время O(N log N): первую, через быстрое преобразование Фурье (БПФ) и дискретное преобразование Фурье (ДПФ), вторую, через преобразование Адамара. Преобразование Адамара использует только вещественные операции "плюс-минус единица" (без комплексных чисел), поэтому вычислительно дешевле ДПФ. Из-за этого на практике диадическую свёртку через Адамара иногда используют как более...