Унифицированная реконфигурируемая схема коммутации быстрого преобразования фурье и способ её формирования

Группа изобретений относится к области цифровой обработки сигналов. Техническим результатом является создание унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) с меньшими аппаратными затратами. Устройство коммутации БПФ для входных отсчетов содержит вычислительных узлов «бабочка» и +1 массивов, состоящих из элементов памяти для хранения входных, выходных и промежуточных отсчетов. 2 н. и 6 з.п. ф-лы, 7 ил.

 

Изобретение относится к области цифровой обработки сигналов, а именно к унифицированным реконфигурируемым схемам коммутации быстрого преобразования Фурье (БПФ) и способам их формирования. Быстрое преобразование Фурье является алгоритмом быстрого вычисления дискретного преобразования Фурье (ДПФ) и может применяться как для программной, так и для аппаратной реализации в устройствах вычисления БПФ ввиду гораздо меньшего количества умножителей и сумматоров по сравнению с ДПФ. Преобразование Фурье, как одно из главных преобразований для цифровой обработки сигналов, используется практически во всех областях современной техники. Многие цифровые стандарты связи, телевидения, измерительная аппаратура и т.д. подразумевают использование БПФ.

Хорошо известны две схемы вычисления БПФ: с прореживанием по частоте и с прореживанием по времени. По количеству математических операций (количеству аппаратных умножителей и сумматоров при аппаратной реализации) обе схемы одинаковы. Отличие в различном порядке либо входных (временных) отсчетов, либо выходных (частотных) отсчетов. Существует прямой порядок и порядок с инверсией адресов. БПФ вычисляют конвейерно по стадиям. Основным вычислительным узлом схемы БПФ является операция «бабочка», включающая в себя две комплексных операции умножения и суммирования. Также схема БПФ включает в себя блоки памяти и схему коммутации между ячейками блоков памяти различных стадий. Существует большое количество схем коммутации с оптимизацией по объему памяти, аппаратным затратам, быстродействию. Слабым местом в схеме коммутации является доступ к памяти ввиду того, что операция «бабочка» подразумевает вычитывание значений их разных адресов памяти, и после вычисления результата запись его в разные адреса. Адреса зависят от выбранной схемы коммутации и стадии вычисления БПФ. В классической схеме коммутации вычитывание значений и запись результатов осуществляют по-разному от стадии к стадии, что требует больших аппаратных затрат для вычисления адресов. К тому же, из однопортовой памяти, как правило, нельзя считать данные одновременно с двух адресов в один такт работы, что делает невозможным применение одного блока памяти для одной операции «бабочка».

Зачастую не требуется большое число отсчетов для БПФ. Например, устройство БПФ, построенное по классической схеме коммутации, рассчитано на максимум 2048 отсчетов для преобразования, однако требуется только 1024 для ускорения вычислений или уменьшения задержки. В этом случае применяют половину массивов памяти, а в остальной половине должны быть нули, тогда они не будут мешать вычислению. В случае применения унифицированной схемы коммутации БПФ, заявленной в изобретении, простое обнуление «ненужных» отсчетов не приведет к правильному результату.

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

Известно (патент US6507860) высокоскоростное устройство выполнения БПФ за счет распараллеливания вычисления на каждой стадии конвейера.

Недостатком данного устройства заключается в том, что в нем за основу взята классическая схема коммутации от стадии к стадии, таким образом, данное устройство включает в себя сложную систему мультиплексоров для одновременного доступа в различные блоки памяти, при этом система мультиплексоров отличается от стадии к стадии. Таким образом, для работы данного устройства необходимы большие аппаратные затраты.

Наиболее близкой к заявленному изобретению является схема коммутации быстрого преобразования Фурье, описанная в патенте CN103106180, в которой применяют единую (унифицированную) схему коммутации узлов «бабочки» в разных стадиях конвейера. Данная схема выбрана в качестве прототипа заявленного изобретения.

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

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

Поставленный технический результат достигнут путем создания унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) для входных отсчетов, содержащая вычислительных узлов «бабочка» и + 1 массивов, состоящих из элементов памяти для хранения входных, выходных и промежуточных отсчетов, при этом входов схемы подключены к входам элементов памяти нулевого массива с 0-го по -й соответственно, выход нулевого элемента памяти нулевого массива подключен к первому входу нулевого узла «бабочка» первой стадии, выход -го элемента памяти нулевого массива подключен ко второму входу нулевого узла «бабочка» первой стадии, первый выход которого подключен к входу нулевого элемента памяти первого массива, а второй выход подключен к входу первого элемента памяти первого массива, при этом выход первого элемента памяти нулевого массива подключен к первому входу первого узла «бабочка» первой стадии, а ко второму входу подключен выход -го элемента памяти нулевого массива, при этом первый выход первого узла «бабочка» первой стадии подключен к входу 2-го элемента памяти первого массива, а второй выход подключен к входу 3-его элемента памяти первого массива и так далее, при этом выход -го элемента памяти нулевого массива подключен к первому входу последнего -го узла «бабочка» первой стадии, ко второму входу которого подключен выход последнего -го элемента памяти нулевого массива, при этом первый выход последнего -го узла «бабочка» первой стадии подключен к входу предпоследнего -го элемента памяти первого массива, а второй выход подключен к входу последнего -го элемента памяти первого массива, схема коммутации между элементами памяти первого и второго, второго и последующих массивов аналогична вплоть до последнего -ого, выходного массива элементов памяти, выходы которых являются выходами схемы.

В предпочтительном варианте осуществления схемы она унифицирована, а именно, одинакова для каждой стадии вычисления БПФ.

В предпочтительном варианте осуществления схемы узел «бабочка» состоит из двух сумматоров и комплексного умножителя с режимом единичного умножения, при этом первый вход узла «бабочка» соединен с первыми входами двух сумматоров, при этом выход первого сумматора является первым выходом узла «бабочка», а второй вход соединен со вторым входом узла «бабочка», который также соединен с входом умножителя на -1, выход которого соединен со вторым входом второго сумматора, выход которого соединен с входом комплексного умножителя с режимом единичного умножения, а его выход является вторым выходом узла «бабочка».

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

Поставленный технический результат достигнут также путем создания способа формирования унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) для входных отсчетов, содержащей вычислительных узлов «бабочка» и + 1 массивов, состоящих из элементов памяти для хранения входных, выходных и промежуточных отсчетов, при этом входов схемы подключают к входам элементов памяти нулевого массива с 0-го по -й соответственно, выход нулевого элемента памяти нулевого массива подключают к первому входу нулевого узла «бабочка» первой стадии, выход -го элемента памяти нулевого массива подключают ко второму входу нулевого узла «бабочка» первой стадии, первый выход которого подключают к входу нулевого элемента памяти первого массива, а второй выход подключают к входу первого элемента памяти первого массива, при этом выход первого элемента памяти нулевого массива подключают к первому входу первого узла «бабочка» первой стадии, а ко второму входу подключают выход -го элемента памяти нулевого массива, при этом первый выход первого узла «бабочка» первой стадии подключают к входу 2-го элемента памяти первого массива, а второй выход подключают к входу 3-его элемента памяти первого массива и так далее, при этом выход -го элемента памяти нулевого массива подключают к первому входу последнего -го узла «бабочка» первой стадии, ко второму входу которого подключают выход последнего -го элемента памяти нулевого массива, при этом первый выход последнего -го узла «бабочка» первой стадии подключают к входу предпоследнего -го элемента памяти первого массива, а второй выход подключают к входу последнего -го элемента памяти первого массива, схема коммутации между элементами памяти первого и второго, второго и последующих массивов аналогична вплоть до последнего -го, выходного массива элементов памяти, выходы которых являются выходами схемы.

В предпочтительном варианте осуществления способ унифицирован, а именно, одинаков для каждой стадии вычисления БПФ.

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

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

Для лучшего понимания заявленного изобретения далее приводится его подробное описание с соответствующими графическими материалами.

Фиг. 1. Традиционная схема вычисления БПФ с прореживанием по частоте, выполненная согласно уровню техники.

Фиг. 2. Схема базовой операции «бабочка», выполненная согласно уровню техники: А) структурная схема; Б) функциональная схема.

Фиг. 3. Унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по частоте, при N=8, выполненная согласно изобретению.

Фиг. 4. Традиционная схема вычисления БПФ с прореживанием по частоте, при N=16, выполненная согласно уровню техники.

Фиг. 5. Унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по частоте, при N=16, выполненная согласно изобретению.

Фиг. 6. Традиционная схема вычисления БПФ с прореживанием по времени, при N=16, выполненная согласно уровню техники.

Фиг. 7. Унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по времени, при N=16, выполненная согласно изобретению.

Рассмотрим принцип функционирования заявленного изобретения. Быстрое преобразование Фурье (БПФ) основано на дискретном преобразовании Фурье, которому соответствует следующий алгоритм вычисления:

(1)

где – -ый отсчет входной последовательности, ,

– -ый отсчет выходного спектра,,

– количество отсчетов,

– коэффициенты ДПФ.

Традиционная известная из уровня техники схема вычисления БПФ с прореживанием по частоте показана на Фиг. 1. Входные отсчеты по порядку записывают в массив 101 элементов памяти, далее по конвейеру выполняют вычисление с помощью базового вычислительного элемента 102 операции «бабочка». Количество стадий Stage0, Stage1, Stage2 конвейера определяют значением . Количество отсчетов выбирают кратным степени двойки. Схема коммутации на каждой стадии различна, в некоторых вершинах стоит умножитель 103 на поворотный множитель Базовая операция «бабочка» представлена на Фиг. 2-А. Более подробно работа данного узла «бабочка» представлена на функциональной схеме Фиг. 2-Б. В состав узла «бабочка» входит два сумматора 201, в нижнем ребре «бабочки» имеется умножитель 103 на поворотный множитель. Операция «бабочка» выполняется в соответствии со следующим выражением:

, (2)

где и – пара входных отсчетов; и – пара выходных комплексных отсчетов; – комплексный поворотный множитель.

Рассмотрим более подробно функционирование заявленной унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье и способа ее формирования (Фиг. 1-7).

Схема коммутации, представленная на Фиг. 1, на каждой стадии различна, поэтому для каждой стадии необходим свой неунифицированный дешифратор адреса. Для лучшего понимания черные кружки обозначены цифрами, это вклад каждого первоначального отсчета в последующие стадии и участие в операции «бабочка». Видно, что вклад отсчетов в последнюю стадию, то есть в выходные отсчеты по номеру имеют полностью обратную нумерацию, если считать сверху вниз.

Лучший вариант (отраженный в формуле изобретения) выполнения заявленной унифицированной реконфигурируемой схемы коммутации БПФ представлен на Фиг. 3. Узел 102 операции «бабочка» схематично стал несимметричен, при этом работа узла по-прежнему эквивалентна схеме, представленной на Фиг. 2-Б и выражению (2). Видно, что схема коммутации на каждой стадии Stage0, Stage1, Stage2 остается одинаковой. Вклад (номер над черными кружками) первоначального отсчета в последующие стадии отличается от традиционной известной из уровня техники схемы, представленной на Фиг. 1, однако в конечной стадии вклад в выходные отсчеты аналогичен вкладу схемы, представленной на Фиг. 1. Алгоритмически схемы, представленные на Фиг. 1 и 3 эквивалентны, все вычисления на каждой стадии совпадают, отличие состоит лишь в адресах записи/чтения из элементов (ячеек) массива 101 памяти.

Аналогичным образом можно построить схему для любого количества отсчетов N. На Фиг 4. представлена традиционная известная из уровня техники схема коммутации БПФ с прореживанием по частоте (N=16), а на Фиг. 5 - ее аналог, выполненный согласно изобретению - унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по частоте (N=16). Исходя из заявленной унифицированной реконфигурируемой схемы коммутации (N=8,16) и выражения (2) для общего случая (любого N) можно написать итеративное выражение:

(3)

где – значение (входной отсчет или промежуточное значение, вычисленное узлом «бабочка») считываемое из -го элемента памяти -ой стадии конвейера; – значение (вычисленное узлом «бабочка») записываемое в -ый элемент памяти -ой стадии конвейера; – комплексный поворотный множитель, соответствующий выражению (2).

Зачастую требуется меньшее количество отсчетов для преобразования БПФ, а именно, . , при этом, если использовать традиционную известную из уровня техники схему коммутации БПФ с прореживанием по частоте, необходимо использовать первые элементов памяти для отсчетов, в остальных должны быть записаны нули. При том нетрудно заметить, что поворачивающие коэффициенты останутся прежними, так как , при . Таким образом, в заявленной унифицированной реконфигурируемой схеме коммутации БПФ (Фиг. 3) нет необходимости менять поворачивающие коэффициенты для реконфигурирования схемы по количеству отсчетов. Все что следует сделать, это:

- обнулить все неиспользуемые отсчеты во входном массиве 101 элементов памяти;

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

- для выбрать равными единице все поворачивающие коэффициенты 103 нулевой и первой стадий Stage0, Stage1. И так далее, каждый раз при уменьшении первоначального количества отсчетов в два раза, количество стадий с единичными поворачивающими коэффициентами увеличивается на один.

Согласно заявленному методу можно построить схему коммутации БПФ с прореживанием по времени, традиционная известная из уровня техники схема которой представлена на Фиг. 5. Традиционные схемы коммутации БПФ с прореживанием по частоте и по времени структурно идентичны, и отличаются лишь направлением вычисления, например, если за основу взята схема с прореживанием по частоте (вычисления производятся слева-направо), то с прореживанием по времени можно структурно применить эту же схему если представить вычисления справа-налево, то есть отобразить схему зеркально. Операция «бабочка» при этом немного отличается. Аналогично можно отобразить заявленную унифицированную реконфигурируемую схему коммутации БПФ с прореживанием по частоте для построения унифицированной реконфигурируемой схемы коммутации БПФ с прореживанием по времени, как показано на Фиг. 7.

Заявленное изобретение предназначено для разработки устройств вычисления БПФ. Заявленное изобретение представляет собой унифицированную (единую) схему коммутации значений из памяти для базовых узлов вычислений операции «бабочка» для всех стадий конвейера. Ввиду того, что схема коммутации едина, можно построить различные устройства с оптимизацией по ресурсам и используемой памяти, быстродействию и т.д. Например, в случае жестких требований по аппаратным затратам, можно, пренебрегая быстродействием, использовать два массива элементов памяти для всех стадий вычислений. Один массив для входных отсчетов, другой для выходных отсчетов, эти же массивы памяти используют для промежуточных вычислений (стадий в случае конвейерной структуры). При этом ввиду единой схемы коммутации, нет необходимости ее перенастраивать с каждым тактом, что дополнительно уменьшает аппаратные затраты.

Заявленная реконфигурируемая унифицированная схема коммутации БПФ имеет следующие преимущества. Реконфигурируемая унифицированная схема содержит:

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

- элементы памяти для хранения входных и выходных (а также промежуточных результатов операции «бабочка») отсчетов,

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

Устройство выполнения БПФ на основе заявленной реконфигурируемой унифицированной схемы может применяться для различных целей:

- для уменьшения аппаратных затрат - последовательная схема, итерационная, требующая один узел «бабочка» и два массива памяти объема отсчетов, при этом доступ к памяти является безконфликтным;

- для максимальной производительности - полностью параллельная схема, конвейерная, требующая узлов «бабочка» и элементов памяти (один элемент для хранения одного отсчета);

- для целевых задач – последовательно параллельная схема, итерационная, требующая несколько узлов «бабочка» не более , работающих параллельно и два массива памяти объема отсчетов.

Хотя описанный выше вариант выполнения изобретения был изложен с целью иллюстрации заявленного изобретения, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла заявленного изобретения, раскрытого в прилагаемой формуле изобретения.

1. Унифицированная реконфигурируемая схема коммутации быстрого преобразования Фурье (БПФ) для входных отсчетов, содержащая вычислительных узлов «бабочка» и +1 массивов, состоящих из элементов памяти для хранения входных, выходных и промежуточных отсчетов, при этом входов схемы подключены к входам элементов памяти нулевого массива с 0-го по -й соответственно, выход нулевого элемента памяти нулевого массива подключен к первому входу нулевого узла «бабочка» первой стадии, выход -го элемента памяти нулевого массива подключен ко второму входу нулевого узла «бабочка» первой стадии, первый выход которого подключен к входу нулевого элемента памяти первого массива, а второй выход подключен к входу первого элемента памяти первого массива, при этом выход первого элемента памяти нулевого массива подключен к первому входу первого узла «бабочка» первой стадии, а ко второму входу подключен выход -го элемента памяти нулевого массива, при этом первый выход первого узла «бабочка» первой стадии подключен к входу 2-го элемента памяти первого массива, а второй выход подключен к входу 3-го элемента памяти первого массива и так далее, при этом выход -го элемента памяти нулевого массива подключен к первому входу последнего -го узла «бабочка» первой стадии, ко второму входу которого подключен выход последнего -го элемента памяти нулевого массива, при этом первый выход последнего -го узла «бабочка» первой стадии подключен к входу предпоследнего -го элемента памяти первого массива, а второй выход подключен к входу последнего -го элемента памяти первого массива, схема коммутации между элементами памяти первого и второго, второго и последующих массивов аналогична вплоть до последнего -го, выходного массива элементов памяти, выходы которых являются выходами схемы.

2. Схема по п. 1, о т л и ч а ю щ а я с я тем, что она унифицирована, а именно, одинакова для каждой стадии вычисления БПФ.

3. Схема по п. 1, о т л и ч а ю щ а я с я тем, что узел «бабочка» состоит из двух сумматоров и комплексного умножителя с режимом единичного умножения, при этом первый вход узла «бабочка» соединен с первыми входами двух сумматоров, при этом выход первого сумматора является первым выходом узла «бабочка», а второй вход соединен со вторым входом узла «бабочка», который также соединен с входом умножителя на -1, выход которого соединен со вторым входом второго сумматора, выход которого соединен с входом комплексного умножителя с режимом единичного умножения, а его выход является вторым выходом узла «бабочка».

4. Схема по п. 3, о т л и ч а ю щ а я с я тем, что все комплексные умножители выполнены с возможностью переключения в режим единичного умножения, при этом для обеспечения реконфигурируемости схемы под меньшее число отсчетов комплексные умножители в узлах бабочки нулевой стадии выполнены с возможностью переключения в режим единичного умножения, а для обеспечения реконфигурируемости схемы под число отсчетов и меньше, количество стадий с умножителями в режиме единичного умножения равно необходимому количеству делений первоначального числа отсчетов на два.

5. Способ формирования унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) для входных отсчетов, содержащей вычислительных узлов «бабочка» и + 1 массивов, состоящих из элементов памяти для хранения входных, выходных и промежуточных отсчетов, при этом входов схемы подключают к входам элементов памяти нулевого массива с 0-го по -й соответственно, выход нулевого элемента памяти нулевого массива подключают к первому входу нулевого узла «бабочка» первой стадии, выход -го элемента памяти нулевого массива подключают ко второму входу нулевого узла «бабочка» первой стадии, первый выход которого подключают к входу нулевого элемента памяти первого массива, а второй выход подключают к входу первого элемента памяти первого массива, при этом выход первого элемента памяти нулевого массива подключают к первому входу первого узла «бабочка» первой стадии, а ко второму входу подключают выход -го элемента памяти нулевого массива, при этом первый выход первого узла «бабочка» первой стадии подключают к входу 2-го элемента памяти первого массива, а второй выход подключают к входу 3-его элемента памяти первого массива и так далее, при этом выход -го элемента памяти нулевого массива подключают к первому входу последнего -го узла «бабочка» первой стадии, ко второму входу которого подключают выход последнего -го элемента памяти нулевого массива, при этом первый выход последнего -го узла «бабочка» первой стадии подключают к входу предпоследнего -го элемента памяти первого массива, а второй выход подключают к входу последнего -го элемента памяти первого массива, схема коммутации между элементами памяти первого и второго, второго и последующих массивов аналогична вплоть до последнего -го, выходного массива элементов памяти, выходы которых являются выходами схемы.

6. Способ по п. 5, отличающийся тем, что он унифицирован, а именно одинаков для каждой стадии вычисления БПФ.

7. Способ по п. 5, отличающийся тем, что узел «бабочка» состоит из двух сумматоров и комплексного умножителя с режимом единичного умножения, при этом первый вход узла «бабочка» соединяют с первыми входами двух сумматоров, при этом выход первого сумматора является первым выходом узла «бабочка», а второй вход соединяют со вторым входом узла «бабочка», который также соединяют с входом умножителя на -1, выход которого соединяют со вторым входом второго сумматора, выход которого соединяют с входом комплексного умножителя с режимом единичного умножения, а его выход является вторым выходом узла «бабочка».

8. Способ по п. 7, отличающийся тем, что все комплексные умножители выполнены с возможностью переключения в режим единичного умножения, при этом для обеспечения реконфигурируемости схемы под меньшее число отсчетов комплексные умножители в узлах бабочки нулевой стадии выполнены с возможностью переключения в режим единичного умножения, а для обеспечения реконфигурируемости схемы под число отсчетов и меньше, количество стадий с умножителями в режиме единичного умножения равно необходимому количеству делений первоначального числа отсчетов на два.