процессор с максимально возможной производительностью для быстрого преобразования фурье

Формула изобретения

1. Процессор с максимально возможной производительностью для быстрого преобразования Фурье, содержащий блок постоянной памяти коэффициентов, первый арифметический блок, первый, второй и третий формирователи адреса, первый коммутатор адреса, отличающийся тем, что введены блок управления, блок оперативного запоминающего устройства (ОЗУ), второй арифметический блок, четвертый и пятый блоки формирования адреса, второй коммутатор адреса, при этом информационный вход каждого из формирователей адреса подключен к шине входных данных, являющейся информационным входом процессора, тактовый вход первого и второго формирователей адреса соединен с первым выходом блока управления, второй выход которого соединен с тактовым входом третьего, четвертого и пятого формирователей адреса; информационный выход первого и второго формирователей адреса подключен соответственно к первому и второму входам первого коммутатора адреса, тактовый вход которого соединен с третьим выходом блока управления и этот выход также соединен с первыми тактовыми входами первого и второго арифметических блоков и тактовым входом второго коммутатора адреса, к первому и второму информационным входам которого подключены информационные выходы третьего и четвертого формирователей адреса; управляющий выход третьего формирователя адреса соединен с третьим входом блока управления, первый и второй входы которого соединены с вторым и третьим управляющими выходами первого формирователя адреса, а четвертый вход - с источником напряжения тактовой частоты; информационный выход пятого формирователя адреса подключен к входу блока постоянной памяти коэффициентов, информационный выход которого подключен к второму входу первого и второго арифметических блоков, выходы которых объединены, подключены к третьему информационному входу блока ОЗУ и являются при этом информационным выходом устройства; выход первого коммутатора адреса соединен с первым информационным входом блока ОЗУ и является при этом адресным выходом устройства; выход второго коммутатора адреса соединен с вторым информационным входом блока ОЗУ, первый, второй и третий тактовые входы которого соединены соответственно с четвертым, пятым и шестым выходами блока управления, седьмой и восьмой выходы которого подключены к второму тактовому входу соответственно первого и второго арифметических блоков, к первому информационному входу которых подключен информационный выход блока ОЗУ.

2. Процессор по п.1, отличающийся тем, что блок управления содержит постоянное запоминающее устройство (ПЗУ), регистр, первый и второй логические элементы НЕ, первый-четвертый логические элементы И, при этом первый, второй и третий адресные входы ПЗУ являются соответственно первым, вторым и третьим входом блока, четвертым тактовым входом которого является вход записи регистра, который объединен с входом первого и второго логических элементов НЕ и вторыми входами первого и второго логических элементов И, причем выходы первого и второго логических элементов НЕ подключены к вторым входам соответственно третьего и четвертого логических элементов И; информационные выходы регистра подключены к ПЗУ, выход которого соединен с информационным входом регистра, первый выход которого соединен с первым входом первого логического элемента И, выход которого является первым выходом блока, второй выход регистра соединен с первым входом второго логического элемента И, выход которого является вторым выходом блока, третий, четвертый, пятый и шестой выходы регистра являются соответственно третьим-шестым выходами блока, седьмой выход регистра соединен с первым входом третьего логического элемента И, выход которого является седьмым выходом блока, восьмой выход регистра соединен с первым входом четвертого логического элемента И, выход которого является восьмым выходом блока.

3. Процессор по п.1, отличающийся тем, что блок ОЗУ содержит третий и четвертый коммутаторы адреса, третий и четвертый логические элементы НЕ, пятый-восьмой логические элементы И, первый и второй банки ОЗУ, демультиплексор данных и первый мультиплексор данных, при этом первый вход третьего коммутатора адреса и второй вход четвертого коммутатора адреса объединены и являются первым информационным входом блока, второй вход третьего коммутатора адреса и первый вход четвертого коммутатора адреса объединены и являются вторым информационным входом блока, выход третьего коммутатора адреса подключен к первому информационному входу первого банка ОЗУ, а выход четвертого коммутатора адреса - к первому информационному входу второго банка ОЗУ; первые входы пятого и шестого логических элементов И объединены и являются первым тактовым входом блока; первые входы седьмого и восьмого логических элементов И объединены и являются вторым тактовым входом блока; тактовые входы третьего и четвертого коммутаторов адреса, демультиплексора данных и первого мультиплексора данных, вторые тактовые входы логических элементов И, причем шестого и восьмого - соответственно через третий и четвертый логические элементы НЕ, объединены и являются третьим тактовым входом блока; выход пятого логического элемента И соединен с первым тактовым входом первого банка ОЗУ, второй тактовый вход которого соединен с выходом восьмого логического элемента И, выход шестого логического элемента И соединен с первым тактовым входом второго банка ОЗУ, второй тактовый вход которого соединен с выходом седьмого логического элемента И; первый выход демультиплексора данных подключен к второму информационному входу первого банка ОЗУ и второму информационному входу первого мультиплексора данных, а второй выход - к второму информационному входу второго банка ОЗУ и первому информационному входу первого мультиплексора данных, при этом вход демультиплексора данных является третьим информационным входом блока, выход первого мультиплексора данных - выходом блока.

4. Процессор по п.1, отличающийся тем, что арифметический блок содержит пятый логический элемент НЕ, девятый и десятый логические элементы И, пять регистров хранения данных, четыре умножителя, три вычитателя, три сумматора и второй мультиплексор данных, при этом вход пятого логического элемента НЕ, второй вход десятого логического элемента И, первый тактовый вход второго мультиплексора объединены и являются первым тактовым входом блока, причем выход пятого логического элемента НЕ соединен с вторым входом девятого логического элемента И; первый вход девятого и десятого логических элементов И, второй тактовый вход второго мультиплексора объединены и являются вторым тактовым входом блока; выход девятого логического элемента И соединен с тактовым входом первого, четвертого и пятого регистров хранения данных, а выход десятого логического элемента И - с тактовым входом второго и третьего регистров хранения данных; информационные входы первого и второго регистров хранения данных объединены и являются первым информационным входом блока, а информационный вход третьего регистра хранения данных - вторым информационным входом блока; первый выход первого регистра хранения данных подключен к первому входу соответственно второго сумматора и второго вычитателя, а второй выход - к первому входу соответственно третьего сумматора и третьего вычитателя, первый выход второго регистра хранения данных подключен к первому входу соответственно первого и третьего перемножителей, а второй выход - к первому входу соответственно второго и четвертого перемножителей, первый выход третьего регистра хранения данных подключен к второму входу соответственно первого и четвертого перемножителей, а второй выход - к второму входу второго и третьего перемножителей; выходы первого и второго перемножителей соединены соответственно с первым и вторым входом первого вычитателя, выход которого подключен к второму входу соответственно второго сумматора и второго вычитателя, выходы третьего и четвертого перемножителей соединены соответственно с первым и вторым входом первого сумматора, выход которого подключен к второму входу соответственно третьего сумматора и третьего вычитателя; выходы второго и третьего сумматоров соединены соответственно с первым и вторым информационным входами четверного регистра хранения данных, выходы второго и третьего вычитателей соединены соответственно с первым и вторым информационным входами пятого регистра хранения данных; выходы четвертого и пятого регистров хранения данных подключены соответственно к первому и второму информационному входу второго мультиплексора, выход которого является выходом блока.

Описание изобретения к патенту

Изобретение относится к вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов, в частности устройствах, выполняющих быстрое преобразование Фурье (БПФ) массивов произвольной размерности N=2^r.

Из множества аналогичных устройств наиболее близким по технической сущности к изобретению является процессор для быстрого преобразования Фурье, содержащий первый и второй блоки постоянной памяти коэффициентов, блок памяти, арифметический блок, первый-третий формирователи адреса, первый и второй элементы И, элемент ИЛИ, счетчик, коммутатор, дешифратор, первый-десятый регистры, при этом информационный вход первого формирователя адреса подключен к первому информационному входу коммутатора, выход которого подключен к адресному входу блока памяти, информационный выход, вход которого является информационным выходом процессора, подключен к информационным входам регистров с первого по четвертый, выходы которых подключены к входам соответственно реальной и мнимой частей первого операнда и входам реальной и мнимой частей второго операнда арифметического блока, входы реальной и мнимой частей коэффициента которого подключены к выходам соответственно пятого и шестого регистров, информационные входы которых подключены к выходу первого блока постоянной памяти коэффициентов, адресный вход которого подключен к информационному выходу второго формирователя адреса, информационный вход которого соединен с информационными входами первого и третьего формирователей адреса и является информационным входом процессора, тактовым входом которого являются соединенные между собой первые входы первого и второго элементов И, выходы которых соответственно подключены: первого - к тактовым входам первого, второго и третьего формирователей адреса, второго - к первому входу дешифратора и счетному входу счетчика, информационный выход которого подключен к адресному входу второго блока постоянной памяти коэффициентов, выходы с первого по пятый которого соответственно подключены к входу управления записью-считыванием блока памяти, управляющему входу коммутатора, второму входу первого элемента И, второму входу дешифратора и входу начала вычислений арифметического блока; выходы реальной и мнимой частей первого и реальной и мнимой частей второго результатов процессора подключены к информационным входам соответственно седьмого, восьмого, девятого и десятого регистров, выходы которых подключены к информационному входу-выходу блока памяти; шестой выход второго блока постоянной памяти коэффициентов подключен к тактовому входу арифметического блока и третьему входу дешифратора, первый выход которого подключен к тактовым входам регистров с первого по шестой, входы обнуления которых соединены с первым входом элемента ИЛИ и подключены к первому установочному выходу первого формирователя адреса, тактовый выход которого подключен к второму входу второго элемента И; входы разрешения записи первого, второго, пятого и шестого регистров подключены к седьмому выходу второго блока постоянной памяти коэффициентов, восьмой выход которого подключен к входам разрешения записи третьего и четвертого регистров; входы разрешения выдачи регистров с седьмого по десятый подключены к девятому выходу второго блока постоянной памяти коэффициентов, десятый выход которого подключен к входу обнуления арифметического блока и второму входу элемента ИЛИ, выход которого подключен к входу обнуления счетчика; второй выход дешифратора подключен к тактовому входу арифметического блока и тактовым входам регистров с седьмого по десятый; информационный выход третьего формирователя адреса подключен к второму информационному входу коммутатора [SU 1633426, 5 G 06 F 15/332, 1991].

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

Сущность изобретения заключается в следующем.

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

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

Блок управления содержит постоянное запоминающее устройство (ПЗУ), регистр, первый и второй логические элементы НЕ, первый-четвертый логические элементы И, при этом первый, второй и третий адресные входы ПЗУ являются соответственно первым, вторым и третьим входом блока, четвертым тактовым входом которого является вход записи регистра, который объединен с входом первого и второго логических элементов НЕ и вторыми входами первого и второго логических элементов И, причем выходы первого и второго логических элементов НЕ подключены к вторым входам соответственно третьего и четвертого логических элементов И; информационные выходы регистра подключены к ПЗУ, выход которого соединен с информационным входом регистра, первый выход которого соединен с первым входом первого логического элемента И, выход которого является первым выходом блока, второй выход регистра соединен с первым входом второго логического элемента И, выход которого является вторым выходом блока, третий, четвертый, пятый и шестой выходы регистра являются соответственно третьим-шестым выходами блока, седьмой выход регистра соединен с первым входом третьего логического элемента И, выход которого является седьмым выходом блока, восьмой выход регистра соединен с первым входом четвертого логического элемента И, выход которого является восьмым выходом блока.

Блок ОЗУ содержит третий и четвертый коммутаторы адреса, третий и четвертый логические элементы НЕ, пятый-восьмой логические элементы И, первый и второй банки ОЗУ, демультиплексор данных и первый мультиплексор данных, при этом первый вход третьего коммутатора адреса и второй вход четвертого коммутатора адреса объединены и являются первым информационным входом блока, второй вход третьего коммутатора адреса и первый вход четвертого коммутатора адреса объединены и являются вторым информационным входом блока, выход третьего коммутатора адреса подключен к первому информационному входу первого банка ОЗУ, а выход четвертого коммутатора адреса - к первому информационному входу второго банка ОЗУ; первые входы пятого и шестого логических элементов И объединены и являются первым тактовым входом блока; первые входы седьмого и восьмого логических элементов И объединены и являются вторым тактовым входом блока; тактовые входы третьего и четвертого коммутаторов адреса, демультиплексора данных и первого мультиплексора данных, вторые тактовые входы логических элементов И, причем шестого и восьмого - соответственно через третий и четвертый логические элементы НЕ, объединены и являются третьим тактовым входом блока; выход пятого логического элемента И соединен с первым тактовым входом первого банка ОЗУ, второй тактовый вход которого соединен с выходом восьмого логического элемента И, выход шестого логического элемента И соединен с первым тактовым входом второго банка ОЗУ, второй тактовый вход которого соединен с выходом седьмого логического элемента И; первый выход демультиплексора данных подключен к второму информационному входу первого банка ОЗУ и второму информационному входу первого мультиплексора данных, а второй выход - к второму информационному входу второго банка ОЗУ и первому информационному входу первого мультиплексора данных, при этом вход демультиплексора данных является третьим информационным входом блока, выход первого мультиплексора данных - выходом блока.

Арифметический блок содержит пятый логический элемент НЕ, девятый и десятый логические элементы И, пять регистров хранения данных, четыре умножителя, три вычитателя, три сумматора и второй мультиплексор данных, при этом вход пятого логического элемента НЕ, второй вход десятого логического элемента И, первый тактовый вход второго мультиплексора объединены и являются первым тактовым входом блока, причем выход пятого логического элемента НЕ соединен с вторым входом девятого логического элемента И; первый вход девятого и десятого логических элементов И, второй тактовый вход второго мультиплексора объединены и являются вторым тактовым входом блока; выход девятого логического элемента И соединен с тактовым входом первого, четвертого и пятого регистров хранения данных, а выход десятого логического элемента И - с тактовым входом второго и третьего регистров хранения данных; информационные входы первого и второго регистров хранения данных объединены и являются первым информационным входом блока, а информационный вход третьего регистра хранения данных - вторым информационным входом блока; первый выход первого регистра хранения данных подключен к первому входу соответственно второго сумматора и второго вычитателя, а второй выход - к первому входу соответственно третьего сумматора и третьего вычитателя, первый выход второго регистра хранения данных подключен к первому входу соответственно первого и третьего перемножителей, а второй выход - к первому входу соответственно второго и четвертого перемножителей, первый выход третьего регистра хранения данных подключен к второму входу соответственно первого и четвертого перемножителей, а второй выход - к второму входу второго и третьего перемножителей; выходы первого и второго перемножителей соединены соответственно с первым и вторым входом первого вычитателя, выход которого подключен к второму входу соответственно второго сумматора и второго вычитателя, выходы третьего и четвертого перемножителей соединены соответственно с первым и вторым входом первого сумматора, выход которого подключен к второму входу соответственно третьего сумматора и третьего вычитателя; выходы второго и третьего сумматоров соединены соответственно с первым и вторым информационным входами четверного регистра хранения данных, выходы второго и третьего вычитателей соединены соответственно с первым и вторым информационным входами пятого регистра хранения данных; выходы четвертого и пятого регистров хранения данных подключены соответственно к первому и второму информационному входу второго мультиплексора, выход которого является выходом блока.

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

Изобретение поясняется чертежами, на которых представлены: фиг.1 - функциональная схема заявленного процессора для БПФ; фиг.2 - структурная схема блока управления; фиг.3 - структурная схема блока ОЗУ; фиг.4 - структурная схема арифметического блока; фиг.5 - временная диаграмма работы заявленного процессора для БПФ.

Процессор с максимально возможной производительностью для быстрого преобразования Фурье (фиг.1) содержит первый-пятый (1₁-1₅) формирователи адреса, первый 2 ₁ и второй 2₂ коммутаторы адреса, блок 3 оперативного запоминающего устройства (ОЗУ), блок 4 постоянной памяти коэффициентов, первый 5₁ и второй 5₂ арифметические блоки, блок 6 управления. Информационный вход каждого из формирователей адреса подключен к шине входных данных 34, являющейся информационным входом процессора. Тактовый вход первого 1₁ и второго 1₂ формирователей адреса соединен с первым выходом 24 блока 6 управления, второй выход 25 которого соединен с тактовым входом третьего 1₃, четвертого 1₄ и пятого 1₅ формирователей адреса. Информационные выходы первого 1₁ и второго 1₂ формирователей адреса подключены соответственно к первому и второму входам первого 2₁ коммутатора адреса, тактовый вход которого соединен с третьим выходом 26 блока 6 управления и этот выход также соединен с первым тактовым входом первого 5₁ и второго 5₂ арифметических блоков и тактовым входом второго 2₂ коммутатора адреса, к первому и второму информационным входам которого подключены информационные выходы соответственно третьего 1₃ и четвертого 1₄ формирователей адреса. Управляющий выход третьего 1₃ формирователя адреса соединен с третьим входом 22 блока 6 управления, первый 20 и второй 21 входы которого соединены соответственно с вторым и третьим управляющими выходами первого 1₁ формирователя адреса, а четвертый вход 23 - с генератором тактовых импульсов (на схеме не показан). Информационный выход пятого 1₅ формирователя адреса подключен к входу блока 4 постоянной памяти коэффициентов, информационный выход которого подключен к второму входу первого 5₁ и второго 5₂ арифметических блоков, выходы которых объединены, подключены к третьему информационному входу блока 3 ОЗУ и являются при этом информационным выходом 19 процессора. Выход первого коммутатора адреса 2₁ соединен с первым информационным входом блока 3 ОЗУ и является при этом адресным выходом 33 процессора; выход второго коммутатора адреса 2₂ соединен с вторым информационным входом блока 3 ОЗУ, первый, второй и третий тактовые входы которого соединены соответственно с четвертым 27, пятым 28 и шестым 29 выходами блока 6 управления, седьмой 30 и восьмой 31 выходы которого подключены к второму тактовому входу соответственно первого 5 ₁ и второго 5₂ арифметических блоков, к первому информационному входу которых подключен информационный выход 18 блока 3 ОЗУ.

Блок 6 управления (фиг.2) содержит постоянное запоминающее устройство (ПЗУ) 7, регистр 8, первый 9₁ и второй 9₂ логические элементы НЕ, первый-четвертый (10₁-10₄) логические элементы И. Первый, второй и третий адресные входы ПЗУ 7, являющиеся первым, вторым и третьим входом блока, соединены соответственно с вторым и третьим управляющими выходами первого формирователя адреса 1₁ и управляющим выходом третьего формирователя адреса 1₃ . Четвертым тактовым входом блока, соединенным с генератором тактовых импульсов, является вход записи регистра 8, который объединен с входом первого 9₁ и второго 9₂ логических элементов НЕ, вторыми входами первого 10₁ и второго 10₂ логических элементов И. Выходы первого 9₁ и второго 9₂ логических элементов НЕ подключены к вторым входам соответственно третьего 10₃ и четвертого 10₄ логических элементов И. Информационные выходы регистра 8 подключены к ПЗУ 7, выход которого соединен с информационным входом регистра 8. Его первый выход соединен с первым входом первого логического элемента И 10₁ , выход которого является первым выходом блока, подключенным к тактовому входу первого 1₁ и второго 1₂ , формирователей адреса. Второй выход регистра 8 соединен с первым входом второго логического элемента И 10₂, выход которого является вторым выходом блока, подключенным к тактовому входу третьего 1₃, четвертого 1₄ и пятого 1 ₅ формирователей адреса. Третий выход регистра 8, являющийся третьим выходом блока, соединен с тактовым входом первого 2 ₁ и второго 2₂ коммутаторов адреса, первому тактовому входу первого 5₁ и второго 5₂ арифметических блоков. Четвертый, пятый и шестой выходы регистра 8, являющиеся четвертым, пятым и шестым выходами блока, соединены соответственно с первым, вторым и третьим тактовыми входами блока 3 ОЗУ (фиг.1). Седьмой выход регистра 8 соединен с первым входом третьего логического элемента И 10₃, выход которого является седьмым выходом блока, подключенным к второму тактовому входу первого арифметического блока 5₁. Восьмой выход регистра 8 соединен с первым входом четвертого логического элемента И 10₄, выход которого является восьмым выходом блока, подключенным к второму тактовому входу второго арифметического блока 5₂. Блок 3 ОЗУ (фиг.3) содержит третий 2 ₃ и четвертый 2₄. коммутаторы адреса, третий 9₃ и четвертый 9₄ логические элементы НЕ, пятый-восьмой (10₅-10₈) логические элементы И, первый 11₁ и второй 11₂ банки ОЗУ, демультиплексор данных 12 и первый мультиплексор данных 13₁. Первый вход третьего коммутатора адреса 2₃ и второй вход четвертого коммутатора адреса 2₄ объединены и являются первым информационным входом блока, подключенным к информационному выходу второго 2₂ коммутатора адреса (фиг.1). Второй вход третьего коммутатора адреса 2₃ и первый вход четвертого коммутатора адреса 2₄ объединены и являются вторым информационным входом блока, подключенным к выходу первого 2₁ коммутатора адреса. Выход третьего коммутатора адреса 2₃ подключен к первому информационному входу первого банка ОЗУ 11₁, а выход четвертого коммутатора адреса 2₄ - к первому информационному входу второго банка ОЗУ 11₂. Первые входы пятого 10₅ и шестого 10₆ логических элементов И объединены и являются первым тактовым входом блока, подключенным к четвертому выходу блока 6 управления. Первые входы седьмого 10₇ и восьмого 10₈ логических элементов И объединены и являются вторым тактовым входом блока, подключенным к пятому выходу блока 6 управления. Тактовые входы третьего 2₃ и четвертого 2₄ коммутаторов адреса, демультиплексора 12 данных и первого мультиплексора данных 13₁, вторые тактовые входы логических элементов И, причем шестого 10 ₆ и восьмого 10₈ - соответственно через третий 9₃ и четвертый 9₄ логические элементы НЕ, объединены и являются третьим тактовым входом блока, подключенным к шестому выходу блока 6 управления. Выход пятого логического элемента И 10₅ соединен с первым тактовым входом первого банка ОЗУ 11₁, второй тактовый вход которого соединен с выходом восьмого логического элемента И 10₈. Выход шестого логического элемента И 10₆ соединен с первым тактовым входом второго банка ОЗУ 11₂, второй тактовый вход которого соединен с выходом седьмого логического элемента И 10₇. Первый выход демультиплексора данных 12 подключен к второму информационному входу первого банка ОЗУ 11₁ и второму информационному входу первого мультиплексора данных 13₁, а второй выход - к второму информационному входу второго банка ОЗУ 11₂ и первому информационному входу первого мультиплексора данных 13₁, при этом вход демультиплексора данных 12 является третьим информационным входом блока, подключенным к объединенному выходу первого 5₁ и второго 5 ₂ арифметических блоков, а выход первого мультиплексора данных 13₁ - выходом блока 3 ОЗУ. Арифметический блок (фиг.4) содержит пятый логический элемент НЕ 9₅, девятый 10₉ и десятый 10₁₀ логические элементы И, первый-пятый (14₁-14₅) регистры хранения данных, первый-четвертый (15₁-15₄) умножители, первый-третий (16₁-16₃) вычитатели, первый-третий (17₁-17₃) сумматоры и второй мультиплексор данных 13₂. Вход пятого логического элемента НЕ 9 ₅, второй вход девятого логического элемента И 10₉ , первый тактовый вход второго мультиплексора данных 13₂ объединены и являются первым тактовым входом блока, подключенным к третьему выходу блока 6 управления (фиг.1). Выход пятого логического элемента НЕ 9₅ соединен с вторым входом десятого логического элемента И 10₁₀. Первый вход девятого 10₉ и десятого 10₁₀ логических элементов И, второй тактовый вход второго мультиплексора данных 13₂ объединены и являются вторым тактовым входом блока, подключенным к 7 и 8 выходам блока 6 управления соответственно. Выход девятого логического элемента И 10₉ соединен с тактовым входом первого 14₁, четвертого 14₄ и пятого 14₅ регистров хранения данных, а выход десятого логического элемента И 10₉ - с тактовым входом второго 14₂ и третьего 14₃ регистров хранения данных. Информационные входы первого 14₁ и второго 14₂ регистров хранения данных объединены и являются первым информационным входом блока, подключенным к выходу блока 3 ОЗУ, а информационный вход третьего регистра хранения данных 14₃ - вторым информационным входом блока, подключенным к выходу блока 4 постоянной памяти (фиг.1). Первый выход первого регистра хранения данных 14 ₁ подключен к первому входу соответственно второго сумматора 17₂ и второго вычитателя 16₂, а второй выход - к первому входу соответственно третьего сумматора 17 ₃ и третьего вычитателя 16₃. Первый выход второго регистра хранения данных 14₂ подключен к первому входу соответственно первого 15₁ и третьего 15₃ перемножителей, а второй выход - к первому входу соответственно второго 15₂ и четвертого 15₄ перемножителей. Первый выход третьего регистра хранения данных 14₃ подключен к второму входу соответственно первого 15₁ и четвертого 15₄ перемножителей, а второй выход - к второму входу второго 15₂ и третьего 15₃ перемножителей. Выходы первого 15₁ и второго 15 ₂ перемножителей соединены соответственно с первым и вторым входом первого вычитателя 16₁, выход которого подключен к второму входу соответственно второго сумматора 17₂ и второго вычитателя 16₂, выходы третьего 15 ₃ и четвертого 15₄ перемножителей соединены соответственно с первым и вторым входом первого сумматора 17 ₁, выход которого подключен к второму входу соответственно третьего сумматора 17₃ и третьего вычитателя 16 ₃. Выходы второго 17₂ и третьего 17₃ сумматоров соединены соответственно с первым и вторым информационным входами четверного регистра хранения данных 14₄, выходы второго 16₂ и третьего 16₃ вычитателей соединены соответственно с первым и вторым информационным входами пятого регистра хранения данных 14₅. Выходы четвертого 14₄ и пятого 14₅ регистров хранения данных подключены соответственно к первому и второму информационному входу второго мультиплексора данных 13₂, выход которого является выходом арифметического блока.

Описанный процессор для БПФ работает в соответствии с временной диаграммой (фиг.5). В исходном состоянии, как и после окончания вычисления БПФ, формирователи адресов 1₁-1₅ установлены в нулевое состояние. В начале каждой итерации по шине 35 входных данных на формирователи адреса 1₁-1₅ извне поступают операнды

A[a](p,t), B[b](p,t), Q[q](p,t), F[f](p,t) и G[g](p,1),

где р - количество строк в матрице;

t - количество элементов в строке;

А, В, Q, F и G - начальный адрес матриц А, В, Q, F и G соответственно;

[a], [b], [q], [f] и [g] - смещение.

Первый формирователь адреса 1₁ выдает сигнал разрешения работы 21 высокого логического уровня на блок 6 управления. Сигнал разрешения работы 21 выдается на время всего преобразования. По завершении преобразования этот сигнал снимается. По сигналу разрешения работы 21 начинается вычисление БПФ. Блок 6 управления выполнен по принципу конечного автомата и работает следующим образом. На его четвертый вход (фиг.2, фиг.5) поступают тактовые импульсы 23. По переднему фронту импульса сигнала тактовой частоты 23 регистр 8 защелкивает информацию с выхода данных ПЗУ 7. С выхода регистра 8 информация поступает на адресный вход ПЗУ 7 и в соответствии с логическими уровнями сигналов 20, 21 и 22 определяет, что будет загружено в регистр 8 по следующему импульсу сигнала тактовой частоты 23 (следующее состояние конечного автомата). Сигнал выбора 26 между элементами а и b выдается напрямую с регистра 8. Его логический уровень меняется каждый период тактовой частоты 23. Низкий логический уровень этого сигнала соответствует передаче элемента а из блока ОЗУ 3 в первый арифметический блок 5 ₁ по сигналу 30 высокого логического уровня и во второй арифметический блок 5₂ по сигналу 31 высокого логического уровня. Высокий логический уровень сигнала выбора 26 соответствует передаче элемента b из блока ОЗУ 3 в первый арифметический блок 5₁ по сигналу 30 высокого логического уровня и во второй арифметический блок 5₂ по сигналу 31 высокого логического уровня. Сигнал чтения 27 из блока ОЗУ 3 выдается напрямую с регистра 8. Высокий логический уровень этого сигнала соответствует чтению из блока ОЗУ 3. Сигнал записи 28 в блок ОЗУ 3 выдается напрямую с регистра 8. Высокий логический уровень этого сигнала соответствует записи в блок ОЗУ 3. Сигнал переключения 29 банков ОЗУ выдаются напрямую с регистра 8. Низкий логический уровень этого сигнала соответствует чтению данных из первого банка ОЗУ 11₁ и записи данных во второй банк ОЗУ 11 ₂. Высокий логический уровень этого сигнала соответствует чтению данных из второго банка ОЗУ 11₂ и записи данных в первый банк ОЗУ 11₁. Сигналы 24 и 25 стробируются тактовыми импульсами с помощью первого 10₁ и второго 10₂ логических элементов И соответственно. По импульсам высокого логического уровня этих сигналов длительностью в половину периода тактовой частоты формирователи адреса формируют адреса следующих элементов матриц. Сигналы 30 и 31 стробируются инверсными тактовыми импульсами с помощью логических цепочек соответственно 9₁-10₃ и 9₂-10₄. По импульсам высокого логического уровня сигналов 30 и 31 длительностью в половину периода тактовой частоты элементы а, b и q запоминаются в регистрах хранения данных 14 арифметических блоков 5₁ и 5₂.

Первый формирователь адреса выдает также адрес первого элемента матрицы F на первый вход первого коммутатора адреса 2₁. Второй формирователь адреса 1₂ выдает адрес первого элемента матрицы G на второй вход второго коммутатора адреса 2₁. Третий формирователь адреса 1₃ выдает адрес первого элемента матрицы А на первый вход второго коммутатора адреса 2₂. Четвертый формирователь адреса 1₄ выдает адрес первого элемента матрицы В на второй вход второго коммутатора адреса 2₂. Пятый формирователь адреса 1₅ выдает адрес первого элемента матрицы Q на вход блока постоянной памяти 4. Блок 6 управления низким логическим уровнем сигнала 26 переключает коммутаторы адреса 2₁ и 2₂ на выдачу адресов элементов матриц F и А соответственно, а первый 5₁ и второй 5₂ арифметические блоки - на прием элемента матрицы А. Также блок 6 управления выдает сигнал чтения 27 на блок ОЗУ 3 и сигнал выбора 30 первого арифметического блока 5₁ . Блок ОЗУ 3 по сигналу 27 выдает элемент матрицы А. Первое арифметическое устройство 5₁ по сигналу 30 запоминает элемент матрицы А.

Блок ОЗУ 3 (фиг.3) может работать в двух режимах в зависимости от уровня сигнала 29 переключения банков ОЗУ, поступающего из блока 6 управления. Если сигнал 29 имеет низкий логический уровень, то адреса элементов а и b по шине 32 через третий коммутатор адреса 2₃ поступают на первый банк ОЗУ 11₁ . Адреса элементов f и g по шине 33 через четвертый коммутатор адреса 2₄ поступают на второй банк ОЗУ 11₂ . Сигнал чтения 27 из блока ОЗУ 3 через пятый элемент И 10 ₅ поступает на первый банк ОЗУ 11₁. Сигнал записи 28 в блок ОЗУ 3 через седьмой элемент И 10₇ поступает на второй банк ОЗУ 11₂. При высоком уровне сигнала 27 данные из первого банка ОЗУ 11₁ через первый мультиплексор данных 13₁ поступают на шину 18. При высоком логическом уровне сигнала 28 данные с шины 19 через демультиплексор данных 12 записываются во второй банк ОЗУ 11₂. Если сигнал 29 имеет высокий логический уровень, то адреса элементов а и b по шине 32 через четвертый коммутатор адреса 2₄ поступают на второй банк ОЗУ 11₂. Адреса элементов f и g по шине 33 через третий коммутатор адреса 2₃ поступают на первый банк ОЗУ 11₁. Сигнал чтения 27 через шестой элемент И 10₆ поступает на второй банк ОЗУ 11₂. Сигнал записи 28 в блок ОЗУ 3 через восьмой элемент И 10₈ поступает на первый банк ОЗУ 11 ₁. При высоком логическом уровне сигнала 27 данные из второго банка ОЗУ 11₂ через первый мультиплексор данных 13 ₁ поступают на шину 18. При высоком логическом уровне сигнала 28 данные из арифметических блоков 5 по шине 19 через демультиплексор данных 12 записываются в первый банк ОЗУ 11₁.

Арифметический блок 5 (фиг.4) работает следующим образом.

Элементы а и b из блока ОЗУ 3 последовательно поступают по шине 18, а константы q - по шине из блока 4 постоянной памяти коэффициентов. Если сигнал выбора 26 между числами а и b имеет низкий логический уровень, то по приходу импульса высокого логического уровня сигнала выбора 30(31) арифметического блока элемент а защелкивается в первом регистре хранения данных 14₁ и подсчитанный в предыдущей операции элемент f из четвертого регистра хранения данных 144 через второй мультиплексор данных 13₂ поступает на шину 19. Если сигнал выбора 26 между числами а и b имеет высокий логический уровень, то по приходу импульса высокого логического уровня сигнала выбора 30(31) арифметического блока элемент b защелкивается во втором регистре хранения данных 14₂, константа q защелкивается в третьем регистре хранения данных 14₃ и подсчитанный в предыдущей операции элемент g из пятого регистра хранения данных 14₅ через второй мультиплексор данных 13₂ поступает на шину 19. С выхода второго регистра хранения данных 14₂ действительная часть элемента b (Re(b)) поступает на первый 15 ₂ и третий 15₄ умножители, а мнимая часть элемента b (Im(b)) поступает на второй 15₁ и четвертый 15 ₄ умножители. С выхода третьего регистра хранения данных 14₃ действительная часть константы q (Re(q)) поступает на первый 15₁ и четвертый 15₄ умножители, а мнимая часть константы q (Im(q)) поступает на второй 15 ₂ и третий 15₃ умножители. С выхода первого умножителя 15₁ произведение Re(b)*Re(q) поступает на первый вычитатель 16₁, на второй вход которого поступает произведение Im(b)*Im(q) с выхода второго умножителя 15₂. С выхода третьего умножителя 15₃ произведение Re(b)*Im(q) поступает на первый сумматор 17₁, на второй вход которого поступает произведение bn(b)*Re(q) с выхода четвертого умножителя 15₄. С выхода первого вычитателя 16 ₁ разность Re(b)*Re(q)-Im(b)*Im(q) поступает на второй сумматор 17₂, где складывается с действительной частью элемента a (Re(a)), образуя действительную часть элемента f (Re(f)=Re(a)+Re(b)*Re(q)-Im(b)*Im(q)), и на вход второго вычитателя 16₂, где вычитается из действительной части элемента a (Re(a)), образуя действительную часть элемента g (Re(g)=Re(a)-Re(b)*Re(q)-Im(b)*Im(q)). С выхода первого сумматора 17₁ сумма Re(b)*Im(q)+Im(b)*Re(q) поступает на третий сумматор 17₃, где складывается с мнимой частью элемента a (Im(a)), образуя мнимую часть элемента f (Im(f)=Im(a)+Re(b)*bn(q)+Im(b)*Re(q)), и на вход третьего вычитателя 16₃, где вычитается из мнимой части элемента a (Im(a)), образуя мнимую часть элемента g (Im(g)=Im(a)-Re(b)*Im(q)-Im(b)*Re(q)). Одновременно с защелкиванием следующего элемента а в первом регистре хранения данных 14₁ вычисленные элементы f и g защелкиваются в четвертом 14₄ и пятом 14₅ регистрах хранения данных соответственно.

На следующем такте блок 6 управления высоким логическим уровнем сигнала 26 переключает коммутаторы адреса 2₁ и 2₂ на выдачу адреса элементов матриц G и В соответственно, а арифметические блоки 5₁ и 5₂ - на прием элементов матриц В и Q. Эти элементы также запоминаются в первом арифметическом блоке 5₁ по импульсу высокого логического уровня сигнала 30. После этого блок 6 управления выдает импульс высокого логического уровня 25 на формирователи адреса 1₃, 1₄ и 1 ₅, по которому они формируют адрес следующих элементов матриц А, В и Q.

Далее происходит аналогичная загрузка данных во второй арифметический блок 5₂. Во время дальнейших циклов загрузки данных в арифметические блоки 5 ₁ и 5₂ блок 6 управления дополнительно выдает импульс высокого логического уровня 24 на формирователи адреса 1₁ и 1₂ и сигнал записи 28 в блок ОЗУ 3, по которому происходит запись элементов матриц F и G во второй банк ОЗУ 11₂. Приход импульса высокого логического уровня сигнала конца итерации 22 с третьего формирователя адреса 1₃ запрещает блоку 6 управления выдачу тактовых импульсов 25 на формирователи адреса 1₃, 1₄ и 1 ₅. При этом выгрузка данных из арифметических блоков 5 ₁ и 5₂ продолжается. При приходе импульса высокого логического уровня сигнала конца итерации 20 с первого формирователя адреса 1₁ блок 6 управления сигналом 29 переключает первый 11₁ и второй 11₂ банки ОЗУ в блоке ОЗУ 3 и начинает новую итерацию. Таким образом, на одну итерацию затрачивается количество тактов, равное числу исходных данных плюс 4 такта. Длительность такта, в свою очередь, определяется минимальным временем чтения (записи) одного элемента из блока ОЗУ 3.

Вычисление матричного БПФ с прореживанием по времени описывается следующим выражением:

где р=2^m-1, t=2-^r-m, m=1, 2, 3...r, длина исходного массива N=2^r;

операция представляет собой поэлементное умножение столбцов матрицы В на вектор столбец Q.

Весовые коэффициенты представляются следующим выражением:

Q₁=cos(2 (i-1)/N)-j*sin(2 (i-1)/N)

где i=1, 2, 3...N/2;

Рассмотрим варианты вычисления матричного БПФ на примере массива размерностью N=2^r, при r=4. Количество итераций: r=4.

1 итерация: m=1, t=8, p=1

В первом банке ОЗУ 11₁ имеем массив, состоящий из матриц и :

В блоке постоянной памяти коэффициентов 4 имеем матрицу :

Элементы (a₁, b₁, q ₁), (а₃, b₃, q₁), (a ₅, b₅, q₁) и (a₇, b ₇, q₁) будут последовательно переданы первому арифметическому блоку 5₁.

Элементы (а₂ , b₂, q₁), (a₄, b₄ , q₁), (a₆, b₆, q₁ ) и (a₈, b₈, q₁) будут последовательно переданы второму арифметическому блоку 5₂.

После окончания итерации во втором банке ОЗУ 112 имеем:

2 итерация: m=2, p=2, t=4

В начале итерации во втором банке ОЗУ 11 ₂ имеем массив, состоящий из матриц и

В блоке постоянной памяти коэффициентов 4 имеем матрицу :

Элементы (a₁, b₁, q ₁), (а₃, b₃, q₁), (a ₅, b₅, q₂) и (а₇, b ₇, q₂) будут последовательно переданы первому арифметическому блоку 5₁.

Элементы (а₂ , b₂, q₁), (a₄, b₄ , q₁), (а₆, b₆, q₂ ) и (a₈, b₈, q₂) будут последовательно переданы второму арифметическому блоку 5₂.

После окончания итерации в первом банке ОЗУ 11₁ имеем:

3 итерация: m=3, p=4, t=2

В начале итерации в первом банке ОЗУ 11 ₁ имеем массив, состоящий из матриц и

В блоке постоянной памяти коэффициентов 4 имеем матрицу :

Элементы (a₁, b₁, q ₁), (а₃, b₃, q₅), (a ₅, b₅, q₃) и (а₇, b ₇, q₇) будут последовательно переданы первому арифметическому блоку 5₁.

Элементы (а₂ , b₂, q₁), (a₄, b₄ , q₃), (a₆, b₆, q₅ ) и (a₈, b₈, q₇) будут последовательно переданы второму арифметическому блоку 5₂.

После окончания итерации во втором банке ОЗУ 11₂ имеем:

4 итерация: m=4, p=8, t=1

В начале итерации во втором банке ОЗУ 11 ₂ имеем массив, состоящий из матриц и .

В блоке постоянной памяти коэффициентов 4 имеем матрицу :

Элементы (a₁, b₁, q ₁), (а₃, b₃, q₃), (а ₅, b₅, q₂) и (а₇, b ₇, q₄) будут последовательно переданы первому арифметическому блоку 5₁.

Элементы (а₂ , b₂, q₅), (a₄, b₄ , q₇), (а₆, b₆, q₆ ) и (a₈, b₈, q₈) будут последовательно переданы второму арифметическому блоку 5₂.

После окончания итерации в первом банке ОЗУ 11₁ имеем:

В итоге в первом банке ОЗУ 11₁ записались искомые составляющие комплексного спектра входного сигнала, причем потенциально максимальная скорость вычислений достигается за счет параллельного выполнения операций чтения-записи в первый 11₁ и второй 11₂ банки ОЗУ и параллельным выполнением арифметических операций в первом 5₁ и втором 5₂ арифметических блоках.

Количество операций "бабочка" в одной итерации и количество итераций определяются размерностью N. По окончании записи последнего элемента последней итерации в блок ОЗУ 3 первый формирователь адреса 1 ₁ снимает сигнал разрешения работы 21. При этом блок 6 управления устанавливается в исходное состояние. Результаты вычислений находятся в блоке ОЗУ 3 (если r четное, то в первом банке ОЗУ 11₁, если r нечетное, то во втором банке ОЗУ 11 ₂) и по шинам 33 (адрес) и 19 (данные) поступают потребителю информации.