В. Основные идеи БПФ.

Способы разделения последовательности отсчетов на части. Рассмотрим сначала выполняемое по формуле

при где целое число.

При вычислении ДПФ методом БПФ исходная -точечная последовательность разделяется на части. Разделяя -точечную последовательность на две части, в каждой из которых остается отсчетов, можно определить отдельно их ДПФ. Формулы, вывод которых будет в дальнейшем указан, позволяют выразить общее ДПФ всей -точечной последовательности отсчетов через ДПФ одной и другой из ее частей. Каждая из выделенных -точечных последовательностей в свою очередь может быть разделена на две части, в которых будет уже по отсчетов. Применяя еще раз указанные формулы, можно выразить ДПФ одной и другой -точечной последовательности через соответствующие пары -точечных последовательностей. Продолжая дальнейшее разделение отсчетов на части, придем в конечном счете к представлению ДПФ четырехточечных последовательностей в функции от ДПФ двухточечных последовательностей. Таким образом, оказывается возможным выразить ДПФ всей первоначально заданной последовательности N отсчетов в функции от ДПФ только двухточечных отсчетов выбранных надлежащим способом.

Этот метод вычисления ДПФ, названный БПФ, позволяет намного уменьшить время вычисления по сравнению со временем, которое занимает обычное определение ДПФ. Экономия времени тем больше, чем больше величина оказывается эффективным при больших значениях для которых время вычисления ДПФ оказывается на несколько порядков меньшим, чем при обычном выполнении ДПФ. Так, при объем вычислений уже сокращается примерно на два порядка. В некоторых же случаях возникает необходимость в обработке последовательностей с очень бошьшими когда эффективность БПФ многократно увеличивается. Сошлемся для примера на упомянутый в книге [88] случай использования БПФ при определении спектра мощности сигнала, когда и более.

Для пояснения идеи БПФ рассмотрим в дальнейшем простейшие примеры, ограничивая N всего лишь восемью отсчетами. Так же выполняются все действия и при больших значениях

Имея в виду алгоритм БПФ последовательности отсчетов, говорят об алгоритме БПФ с основанием 2. Такие алгоритмы БПФ, чаше всего применяющиеся, будут описаны нами в первую очередь. Вообще же БПФ может выполняться для последовательностей N отсчетов и при представлении виде где и к — целые числа, но (соответственно говорят об алгоритмах БПФ с основанием Дополнительные замечания по этому поводу будут сделаны в разделе Ж.

Укажем, как производится разделение последовательности отсчетов на части. Рассмотрим разделение -точечной последовательности на две

-точечные. При разделении последних на более мелкие части выполняются аналогичные действия.

Один из применяемых способов выполнения БПФ основан на том, что производится прореживание по времени, т.е. по точкам . С тем чтобы пояснить его, обратимся к рис. 3.6, а. В верхней части рисунка показаны все N заданных значений При прореживании по времени берутся с пропуском через один отсчет. Таким образом получаются изображенная в следующем ряду слева -точечная последовательность отсчетов для бывших четных и изображенная в этом ряду справа -точечная последовательность отсчетов для бывших нечетных Введем для первых из этих отсчетов обозначение и для вторых из них обозначение нумеруя их в каждом случае заново подряд. При зтом

На рис. 3.6, а в нижней его части показано, как таким же образом осуществляется прореживание одной из полученных -точечных

Рис. 2.6

последовательностей с получением -точечных. Так же производится прореживание и второй из полученных -точечных последовательностей, что на рисунке не изображено.

При другом из принятых способов разделения -точечной последовательности отсчетов на части прореживание по времени не производится. Берутся первые отсчетов и следующие за ними отсчетов, каждые из которых образуют по -точечной последовательности. Для них опять вводим соответственно обозначения причем на этот раз

При таком способе разделения -точечной последовательности на части основные формулы БПФ имеют иной вид, чем при ранее указанном способе. При этом, как будет показано, в ходе выполнения БПФ производится прореживание по частоте аналогичное описанному нами ранее прореживанию по времени Поэтому данный алгоритм БПФ называют алгоритмом БПФ с прореживанием по частоте.

На рис. 3.6, б показано, что при зтом способе выполнения БПФ в соответствии с формулами (3.64) и (3.65) разделяется по -точечная последовательность отсчетов на две -точечные и как происходит дальнейшее разделение на части одной из полученных -точечных последовательностей.