Унифицированная реконфигурируемая схема коммутации быстрого преобразования фурье и способ её формирования
Владельцы патента RU 2700194:
Акционерное общество Научно-производственный центр "Электронные вычислительно-информационные системы" (АО НПЦ "ЭЛВИС") (RU)
Группа изобретений относится к области цифровой обработки сигналов. Техническим результатом является создание унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) с меньшими аппаратными затратами. Устройство коммутации БПФ для
Изобретение относится к области цифровой обработки сигналов, а именно к унифицированным реконфигурируемым схемам коммутации быстрого преобразования Фурье (БПФ) и способам их формирования. Быстрое преобразование Фурье является алгоритмом быстрого вычисления дискретного преобразования Фурье (ДПФ) и может применяться как для программной, так и для аппаратной реализации в устройствах вычисления БПФ ввиду гораздо меньшего количества умножителей и сумматоров по сравнению с ДПФ. Преобразование Фурье, как одно из главных преобразований для цифровой обработки сигналов, используется практически во всех областях современной техники. Многие цифровые стандарты связи, телевидения, измерительная аппаратура и т.д. подразумевают использование БПФ.
Хорошо известны две схемы вычисления БПФ: с прореживанием по частоте и с прореживанием по времени. По количеству математических операций (количеству аппаратных умножителей и сумматоров при аппаратной реализации) обе схемы одинаковы. Отличие в различном порядке либо входных (временных) отсчетов, либо выходных (частотных) отсчетов. Существует прямой порядок и порядок с инверсией адресов. БПФ вычисляют конвейерно по стадиям. Основным вычислительным узлом схемы БПФ является операция «бабочка», включающая в себя две комплексных операции умножения и суммирования. Также схема БПФ включает в себя блоки памяти и схему коммутации между ячейками блоков памяти различных стадий. Существует большое количество схем коммутации с оптимизацией по объему памяти, аппаратным затратам, быстродействию. Слабым местом в схеме коммутации является доступ к памяти ввиду того, что операция «бабочка» подразумевает вычитывание значений их разных адресов памяти, и после вычисления результата запись его в разные адреса. Адреса зависят от выбранной схемы коммутации и стадии вычисления БПФ. В классической схеме коммутации вычитывание значений и запись результатов осуществляют по-разному от стадии к стадии, что требует больших аппаратных затрат для вычисления адресов. К тому же, из однопортовой памяти, как правило, нельзя считать данные одновременно с двух адресов в один такт работы, что делает невозможным применение одного блока памяти для одной операции «бабочка».
Зачастую не требуется большое число отсчетов для БПФ. Например, устройство БПФ, построенное по классической схеме коммутации, рассчитано на максимум 2048 отсчетов для преобразования, однако требуется только 1024 для ускорения вычислений или уменьшения задержки. В этом случае применяют половину массивов памяти, а в остальной половине должны быть нули, тогда они не будут мешать вычислению. В случае применения унифицированной схемы коммутации БПФ, заявленной в изобретении, простое обнуление «ненужных» отсчетов не приведет к правильному результату.
В заявленном изобретении описана схема коммутации БПФ с прореживанием по частоте и оптимизацией аппаратных затрат на схему коммутации. Также представлен способ построения заявленной унифицированной схемы коммутации БПФ с прореживанием по времени. Для меньшего чем максимальное число отсчетов заявленная схема является реконфигурируемой, при этом ее аппаратные затраты остаются прежними, как в случае отсутствия реконфигурируемости.
Известно (патент US6507860) высокоскоростное устройство выполнения БПФ за счет распараллеливания вычисления на каждой стадии конвейера.
Недостатком данного устройства заключается в том, что в нем за основу взята классическая схема коммутации от стадии к стадии, таким образом, данное устройство включает в себя сложную систему мультиплексоров для одновременного доступа в различные блоки памяти, при этом система мультиплексоров отличается от стадии к стадии. Таким образом, для работы данного устройства необходимы большие аппаратные затраты.
Наиболее близкой к заявленному изобретению является схема коммутации быстрого преобразования Фурье, описанная в патенте CN103106180, в которой применяют единую (унифицированную) схему коммутации узлов «бабочки» в разных стадиях конвейера. Данная схема выбрана в качестве прототипа заявленного изобретения.
Недостаток схемы прототипа заключается в том, что для реконфигурирования, а именно осуществления БПФ для меньшего числа отсчетов применяют комплексные умножители на отличающиеся поворотные множители по сравнению со схемой для максимального числа отсчетов. Таким образом, для работы схемы прототипа необходимы большие аппаратные затраты.
Техническим результатом изобретения является создание унифицированной реконфигурируемой схемы коммутации БПФ и способа её формирования с меньшими аппаратными затратами, за счет использования двух массивов памяти для всех стадий вычислений, один из которых предназначен для входных отсчетов, а другой для выходных отсчетов, эти же массивы памяти используют для промежуточных вычислений (стадий в случае конвейерной структуры), а также за счет использования единой схемы коммутации, не требующей перенастройки с каждым тактом.
Поставленный технический результат достигнут путем создания унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) для
В предпочтительном варианте осуществления схемы она унифицирована, а именно, одинакова для каждой стадии вычисления БПФ.
В предпочтительном варианте осуществления схемы узел «бабочка» состоит из двух сумматоров и комплексного умножителя с режимом единичного умножения, при этом первый вход узла «бабочка» соединен с первыми входами двух сумматоров, при этом выход первого сумматора является первым выходом узла «бабочка», а второй вход соединен со вторым входом узла «бабочка», который также соединен с входом умножителя на -1, выход которого соединен со вторым входом второго сумматора, выход которого соединен с входом комплексного умножителя с режимом единичного умножения, а его выход является вторым выходом узла «бабочка».
В предпочтительном варианте осуществления схемы все комплексные умножители выполнены с возможностью переключения в режим единичного умножения, при этом для обеспечения реконфигурируемости схемы под меньшее число отсчетов
Поставленный технический результат достигнут также путем создания способа формирования унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) для
В предпочтительном варианте осуществления способ унифицирован, а именно, одинаков для каждой стадии вычисления БПФ.
В предпочтительном варианте осуществления способа узел «бабочка» состоит из двух сумматоров и комплексного умножителя с режимом единичного умножения, при этом первый вход узла «бабочка» соединяют с первыми входами двух сумматоров, при этом выход первого сумматора является первым выходом узла «бабочка», а второй вход соединяют со вторым входом узла «бабочка», который также соединяют с входом умножителя на -1, выход которого соединяют со вторым входом второго сумматора, выход которого соединяют с входом комплексного умножителя с режимом единичного умножения, а его выход является вторым выходом узла «бабочка».
В предпочтительном варианте осуществления способа все комплексные умножители выполнены с возможностью переключения в режим единичного умножения, при этом для обеспечения реконфигурируемости схемы под меньшее число отсчетов
Для лучшего понимания заявленного изобретения далее приводится его подробное описание с соответствующими графическими материалами.
Фиг. 1. Традиционная схема вычисления БПФ с прореживанием по частоте, выполненная согласно уровню техники.
Фиг. 2. Схема базовой операции «бабочка», выполненная согласно уровню техники: А) структурная схема; Б) функциональная схема.
Фиг. 3. Унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по частоте, при N=8, выполненная согласно изобретению.
Фиг. 4. Традиционная схема вычисления БПФ с прореживанием по частоте, при N=16, выполненная согласно уровню техники.
Фиг. 5. Унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по частоте, при N=16, выполненная согласно изобретению.
Фиг. 6. Традиционная схема вычисления БПФ с прореживанием по времени, при N=16, выполненная согласно уровню техники.
Фиг. 7. Унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по времени, при N=16, выполненная согласно изобретению.
Рассмотрим принцип функционирования заявленного изобретения. Быстрое преобразование Фурье (БПФ) основано на дискретном преобразовании Фурье, которому соответствует следующий алгоритм вычисления:
где
Традиционная известная из уровня техники схема вычисления БПФ с прореживанием по частоте показана на Фиг. 1. Входные отсчеты
где
Рассмотрим более подробно функционирование заявленной унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье и способа ее формирования (Фиг. 1-7).
Схема коммутации, представленная на Фиг. 1, на каждой стадии различна, поэтому для каждой стадии необходим свой неунифицированный дешифратор адреса. Для лучшего понимания черные кружки обозначены цифрами, это вклад каждого первоначального отсчета
Лучший вариант (отраженный в формуле изобретения) выполнения заявленной унифицированной реконфигурируемой схемы коммутации БПФ представлен на Фиг. 3. Узел 102 операции «бабочка» схематично стал несимметричен, при этом работа узла по-прежнему эквивалентна схеме, представленной на Фиг. 2-Б и выражению (2). Видно, что схема коммутации на каждой стадии Stage0, Stage1, Stage2 остается одинаковой. Вклад (номер над черными кружками) первоначального отсчета
Аналогичным образом можно построить схему для любого количества отсчетов N. На Фиг 4. представлена традиционная известная из уровня техники схема коммутации БПФ с прореживанием по частоте (N=16), а на Фиг. 5 - ее аналог, выполненный согласно изобретению - унифицированная реконфигурируемая схема коммутации БПФ с прореживанием по частоте (N=16). Исходя из заявленной унифицированной реконфигурируемой схемы коммутации (N=8,16) и выражения (2) для общего случая (любого N) можно написать итеративное выражение:
где
Зачастую требуется меньшее количество отсчетов для преобразования БПФ, а именно,
- обнулить все неиспользуемые отсчеты
- для
- для
Согласно заявленному методу можно построить схему коммутации БПФ с прореживанием по времени, традиционная известная из уровня техники схема которой представлена на Фиг. 5. Традиционные схемы коммутации БПФ с прореживанием по частоте и по времени структурно идентичны, и отличаются лишь направлением вычисления, например, если за основу взята схема с прореживанием по частоте (вычисления производятся слева-направо), то с прореживанием по времени можно структурно применить эту же схему если представить вычисления справа-налево, то есть отобразить схему зеркально. Операция «бабочка» при этом немного отличается. Аналогично можно отобразить заявленную унифицированную реконфигурируемую схему коммутации БПФ с прореживанием по частоте для построения унифицированной реконфигурируемой схемы коммутации БПФ с прореживанием по времени, как показано на Фиг. 7.
Заявленное изобретение предназначено для разработки устройств вычисления БПФ. Заявленное изобретение представляет собой унифицированную (единую) схему коммутации значений из памяти для базовых узлов вычислений операции «бабочка» для всех стадий конвейера. Ввиду того, что схема коммутации едина, можно построить различные устройства с оптимизацией по ресурсам и используемой памяти, быстродействию и т.д. Например, в случае жестких требований по аппаратным затратам, можно, пренебрегая быстродействием, использовать два массива элементов памяти для всех стадий вычислений. Один массив для входных отсчетов, другой для выходных отсчетов, эти же массивы памяти используют для промежуточных вычислений (стадий в случае конвейерной структуры). При этом ввиду единой схемы коммутации, нет необходимости ее перенастраивать с каждым тактом, что дополнительно уменьшает аппаратные затраты.
Заявленная реконфигурируемая унифицированная схема коммутации БПФ имеет следующие преимущества. Реконфигурируемая унифицированная схема содержит:
- узел «бабочка», состоящий из комплексного умножителя, двух сумматоров,
- элементы памяти для хранения входных и выходных (а также промежуточных результатов операции «бабочка») отсчетов,
- обладает единой коммутацией между всеми стадиями вычисления и исключает систему сложного мультиплексирования, присущую традиционной схеме.
Устройство выполнения БПФ на основе заявленной реконфигурируемой унифицированной схемы может применяться для различных целей:
- для уменьшения аппаратных затрат - последовательная схема, итерационная, требующая один узел «бабочка» и два массива памяти объема
- для максимальной производительности - полностью параллельная схема, конвейерная, требующая
- для целевых задач – последовательно параллельная схема, итерационная, требующая несколько узлов «бабочка» не более
Хотя описанный выше вариант выполнения изобретения был изложен с целью иллюстрации заявленного изобретения, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла заявленного изобретения, раскрытого в прилагаемой формуле изобретения.
1. Унифицированная реконфигурируемая схема коммутации быстрого преобразования Фурье (БПФ) для
2. Схема по п. 1, о т л и ч а ю щ а я с я тем, что она унифицирована, а именно, одинакова для каждой стадии вычисления БПФ.
3. Схема по п. 1, о т л и ч а ю щ а я с я тем, что узел «бабочка» состоит из двух сумматоров и комплексного умножителя с режимом единичного умножения, при этом первый вход узла «бабочка» соединен с первыми входами двух сумматоров, при этом выход первого сумматора является первым выходом узла «бабочка», а второй вход соединен со вторым входом узла «бабочка», который также соединен с входом умножителя на -1, выход которого соединен со вторым входом второго сумматора, выход которого соединен с входом комплексного умножителя с режимом единичного умножения, а его выход является вторым выходом узла «бабочка».
4. Схема по п. 3, о т л и ч а ю щ а я с я тем, что все комплексные умножители выполнены с возможностью переключения в режим единичного умножения, при этом для обеспечения реконфигурируемости схемы под меньшее число отсчетов
5. Способ формирования унифицированной реконфигурируемой схемы коммутации быстрого преобразования Фурье (БПФ) для
6. Способ по п. 5, отличающийся тем, что он унифицирован, а именно одинаков для каждой стадии вычисления БПФ.
7. Способ по п. 5, отличающийся тем, что узел «бабочка» состоит из двух сумматоров и комплексного умножителя с режимом единичного умножения, при этом первый вход узла «бабочка» соединяют с первыми входами двух сумматоров, при этом выход первого сумматора является первым выходом узла «бабочка», а второй вход соединяют со вторым входом узла «бабочка», который также соединяют с входом умножителя на -1, выход которого соединяют со вторым входом второго сумматора, выход которого соединяют с входом комплексного умножителя с режимом единичного умножения, а его выход является вторым выходом узла «бабочка».
8. Способ по п. 7, отличающийся тем, что все комплексные умножители выполнены с возможностью переключения в режим единичного умножения, при этом для обеспечения реконфигурируемости схемы под меньшее число отсчетов