Есть массивы $%X$% длиной $%N$% и $%Y$% длиной $%M$%, $%M\lt N$%. Требуется вычислить новый массив $%Z$% длиной $%N-M$%, элементы которого равны: $$Z_i=\sum_{k=0}^{M-1}X_{i+k}Y_k$$ Индексация элементов массива начинается с нуля.
Для выполнения данной операции "напрямую" требуется $%(N-M)M$% операций, поэтому я произвожу вычисления следующим образом:

  • массив $%Y$% дополняется нулями до длины $%N$%
  • массив $%Y$% инвертируется: $$Y^I_0=Y_0, Y^I_i=Y_{N-i}$$

Теперь $%Z$% равно цикличной свертке последовательностей (массивов) $%X$% и $%Y^I$%. А свертку можно вычислить при помощи преобразования Фурье:

  • $%W_X=ДПФ(X)$%, где ДПФ - дискретное преобразование Фурье
  • $%W_Y=ДПФ(Y^I)$%
  • $%(W_Z)_i=(W_X)_i(W_Y)_i$%
  • $%Z=ОПФ(W_Z)$%, где ОПФ - обратное дискретное преобразование Фурье
  • массив $%Z$% обрезается до длины $%N-M$%

В таком варианте для вычислений требуется порядка $%N\log N$% операций, но расширение меньшего массива до размера большего кажется излишними вычислительными затратами.
Вопрос: можно ли произвести данные вычисления, работая с массивом $%Y$% оригинального размера (т.е., не дополняя его нулями)?

задан 23 Мар '14 0:23

Мне кажется, наличие нулей можно просто учесть при вычислениях с ДПФ. Соответствующие отрезки в цикле будут просто пропускаться. Это как-то немного сократит число выполняемых операций. То есть для практики никакого "ущерба" не будет, а для теории дополнение массивов нулями ни к каким неудобствам не ведёт.

(23 Мар '14 0:43) falcao

Да, это значительно упростит вычисление прямого ДПФ(Y). Но я надеюсь найти алгоритм, работающий с массивами оригинального размера на всех этапах.
В данный момент пытаюсь найти решения для частных случаев, когда N кратно M, но я только начинаю изучать преобразование Фурье, и для меня это, пока что, слишком сложно.

(23 Мар '14 0:58) chameleon
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×17
×4

задан
23 Мар '14 0:23

показан
614 раз

обновлен
23 Мар '14 0:58

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru