БПФ по основанию 4, Алгоритм расчета Опции

[Fair]

Помогите пожалуйста решить задачку.
Необходимо рассчитать БПФ по основанию 4 с прореживанием по времени для 16 отсчетов.
В книге DIGITAL SIGNAL PROCESSING APPLICATIONS описан только алгоритм Radix4 для 64 точечного БПФ с прореживанием по частоте.
Как я понимаю, в моем случае, на первом этапе требуется рассчитать 4-е четырехточечные бабочки. Поворотные множители во всех бабочках будут одинаковы, но какие именно.
На втором этапе, имеем 1 группу из 4-х бабочек. Поворотные множители в каждой бабочке отличаются, и снова возникает вопрос, какие они именно.
Заранее спасибо.

[GinGreen]

Помогите пожалуйста решить задачку.
Необходимо рассчитать БПФ по основанию 4 с прореживанием по времени для 16 отсчетов.
В книге DIGITAL SIGNAL PROCESSING APPLICATIONS описан только алгоритм Radix4 для 64 точечного БПФ с прореживанием по частоте.
Как я понимаю, в моем случае, на первом этапе требуется рассчитать 4-е четырехточечные бабочки. Поворотные множители во всех бабочках будут одинаковы, но какие именно.
На втором этапе, имеем 1 группу из 4-х бабочек. Поворотные множители в каждой бабочке отличаются, и снова возникает вопрос, какие они именно.
Заранее спасибо.

Добрый день.
Для начала замечу, что прореживание по времени и прорежевание по частоте отличаются, по сути, только порядком прохода по схеме(например если прореживание по времени - прямой проход по схеме , то прореживание по частоте - обратный по той же самой схеме; вход меняется с выходом и стрелка бабочки изменяет направление на противоположное).
Гораздо важнее применяете Вы двоично инверсные перестановки или нет(здесь разница существенная).

Используйте обычные бабочки(два входа два выхода). Здесь всё просто.

Сообщение отредактировал GinGreen - Dec 23 2006, 14:34

[shasik]

Помогите пожалуйста решить задачку.
Необходимо рассчитать БПФ по основанию 4 с прореживанием по времени для 16 отсчетов.
В книге DIGITAL SIGNAL PROCESSING APPLICATIONS описан только алгоритм Radix4 для 64 точечного БПФ с прореживанием по частоте.
Как я понимаю, в моем случае, на первом этапе требуется рассчитать 4-е четырехточечные бабочки. Поворотные множители во всех бабочках будут одинаковы, но какие именно.
На втором этапе, имеем 1 группу из 4-х бабочек. Поворотные множители в каждой бабочке отличаются, и снова возникает вопрос, какие они именно.
Заранее спасибо.

Книга такая где-то у меня была, но искать как-то сложно ввиду праздников. Рисунка не помню.Но логика такая. Рассмотрим БПФ по основанию 2 (чтобы понятнее было). БПФ сигнала длиной N получается путем нехитрых операций (бабочка) над двумя БПФ длиной N/2. Вопрос как нарисовать граф вычислительного процесса для БПФ длиной N/2, если имеется граф для длины N? Ответ: выкидываем полностью последний этап графа для N/2, а также удаляем верх или низ оставшегося графа. Нарисуй, попробуй поймешь. Очевидные проблемы: двоично-инверсный порядок отсчетов. Если нужно получить БПФ длиной N/2, то на входы графа, полученного после двух операций удаления, поступает сигнал длиной N/2, который и тасуют.
Вопрос: а причем здесь БПФ по основанию 4? А все просто: БПФ длиной 64 по основанию 4 получается из 4-х БПФ длиной 16. Другими словами, чтобы получить БПФ длиной 16 необходимо из соответсвующего графа удалить последнюю операцию и стереть 3/4 оставшегося графа. На вход того что осталось подается не кусок длиной 16 двоично-инверсного сигнала длиной 64, а просто двоично-инверсный сигнал длиной 16. Надеюсь ясно. Если не понятно написано, то просто необходимо еще немного выпить и прочитать еще раз.