Изобретение относится к вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов, в частности устройствах, выполняющих быстрое преобразование Фурье (БПФ) массивов произвольной размерности N=2r.
Из множества аналогичных устройств наиболее близким по технической сущности к изобретению является процессор для быстрого преобразования Фурье, содержащий первый и второй блоки постоянной памяти коэффициентов, блок памяти, арифметический блок, первый-третий формирователи адреса, первый и второй элементы И, элемент ИЛИ, счетчик, коммутатор, дешифратор, первый-десятый регистры, при этом информационный вход первого формирователя адреса подключен к первому информационному входу коммутатора, выход которого подключен к адресному входу блока памяти, информационный выход, вход которого является информационным выходом процессора, подключен к информационным входам регистров с первого по четвертый, выходы которых подключены к входам соответственно реальной и мнимой частей первого операнда и входам реальной и мнимой частей второго операнда арифметического блока, входы реальной и мнимой частей коэффициента которого подключены к выходам соответственно пятого и шестого регистров, информационные входы которых подключены к выходу первого блока постоянной памяти коэффициентов, адресный вход которого подключен к информационному выходу второго формирователя адреса, информационный вход которого соединен с информационными входами первого и третьего формирователей адреса и является информационным входом процессора, тактовым входом которого являются соединенные между собой первые входы первого и второго элементов И, выходы которых соответственно подключены: первого - к тактовым входам первого, второго и третьего формирователей адреса, второго - к первому входу дешифратора и счетному входу счетчика, информационный выход которого подключен к адресному входу второго блока постоянной памяти коэффициентов, выходы с первого по пятый которого соответственно подключены к входу управления записью-считыванием блока памяти, управляющему входу коммутатора, второму входу первого элемента И, второму входу дешифратора и входу начала вычислений арифметического блока; выходы реальной и мнимой частей первого и реальной и мнимой частей второго результатов процессора подключены к информационным входам соответственно седьмого, восьмого, девятого и десятого регистров, выходы которых подключены к информационному входу-выходу блока памяти; шестой выход второго блока постоянной памяти коэффициентов подключен к тактовому входу арифметического блока и третьему входу дешифратора, первый выход которого подключен к тактовым входам регистров с первого по шестой, входы обнуления которых соединены с первым входом элемента ИЛИ и подключены к первому установочному выходу первого формирователя адреса, тактовый выход которого подключен к второму входу второго элемента И; входы разрешения записи первого, второго, пятого и шестого регистров подключены к седьмому выходу второго блока постоянной памяти коэффициентов, восьмой выход которого подключен к входам разрешения записи третьего и четвертого регистров; входы разрешения выдачи регистров с седьмого по десятый подключены к девятому выходу второго блока постоянной памяти коэффициентов, десятый выход которого подключен к входу обнуления арифметического блока и второму входу элемента ИЛИ, выход которого подключен к входу обнуления счетчика; второй выход дешифратора подключен к тактовому входу арифметического блока и тактовым входам регистров с седьмого по десятый; информационный выход третьего формирователя адреса подключен к второму информационному входу коммутатора [SU 1633426, 5 G 06 F 15/332, 1991].
Причиной, препятствующей достижению указанного ниже технического результата при использовании известного процессора для БПФ, является то, что при выбранной элементной базе реализации максимальное значение его быстродействия принципиально ограничено необходимостью последовательного обращения к памяти при вычислениях.
Сущность изобретения заключается в следующем.
Технический результат, достигаемый при осуществлении изобретения, выражается в обеспечении потенциально возможного максимального быстродействия процессора для БПФ при заданном выборе элементной базы его реализации.
Это достигается тем, что в известный процессор для БПФ, содержащий блок постоянной памяти коэффициентов, первый арифметический блок, первый, второй и третий формирователи адреса, первый коммутатор адреса, согласно изобретению введены блок управления, блок оперативного запоминающего устройства (ОЗУ), второй арифметический блок, четвертый и пятый блоки формирования адреса, второй коммутатор адреса, при этом информационный вход каждого из формирователей адреса подключен к шине входных данных, являющейся информационным входом устройства, тактовый вход первого и второго формирователей адреса соединен с первым выходом блока управления, второй выход которого соединен с тактовым входом третьего, четвертого и пятого формирователей адреса; информационный выход первого и второго формирователей адреса подключен соответственно к первому и второму входам первого коммутатора адреса, тактовый вход которого соединен с третьим выходом блока управления и этот выход также соединен с первыми тактовыми входами первого и второго арифметических блоков и тактовым входом второго коммутатора адреса, к первому и второму информационным входам которого подключены информационные выходы третьего и четвертого формирователей адреса; управляющий выход третьего формирователя адреса соединен с третьим входом блока управления, первый и второй входы которого соединены с вторым и третьим управляющими выходами первого формирователя адреса, а четвертый вход - с источником напряжения тактовой частоты; информационный выход пятого формирователя адреса подключен к входу блока постоянной памяти коэффициентов, информационный выход которого подключен к второму входу первого и второго арифметических блоков, выходы которых объединены, подключены к третьему информационному входу блока ОЗУ и являются при этом информационным выходом устройства; выход первого коммутатора адреса соединен с первым информационным входом блока ОЗУ и является при этом адресным выходом устройства; выход второго коммутатора адреса соединен с вторым информационным входом блока ОЗУ, первый, второй и третий тактовые входы которого соединены соответственно с четвертым, пятым и шестым выходами блока управления, седьмой и восьмой выходы которого подключены к второму тактовому входу соответственно первого и второго арифметических блоков, к первому информационному входу которых подключен информационный выход блока ОЗУ.
Блок управления содержит постоянное запоминающее устройство (ПЗУ), регистр, первый и второй логические элементы НЕ, первый-четвертый логические элементы И, при этом первый, второй и третий адресные входы ПЗУ являются соответственно первым, вторым и третьим входом блока, четвертым тактовым входом которого является вход записи регистра, который объединен с входом первого и второго логических элементов НЕ и вторыми входами первого и второго логических элементов И, причем выходы первого и второго логических элементов НЕ подключены к вторым входам соответственно третьего и четвертого логических элементов И; информационные выходы регистра подключены к ПЗУ, выход которого соединен с информационным входом регистра, первый выход которого соединен с первым входом первого логического элемента И, выход которого является первым выходом блока, второй выход регистра соединен с первым входом второго логического элемента И, выход которого является вторым выходом блока, третий, четвертый, пятый и шестой выходы регистра являются соответственно третьим-шестым выходами блока, седьмой выход регистра соединен с первым входом третьего логического элемента И, выход которого является седьмым выходом блока, восьмой выход регистра соединен с первым входом четвертого логического элемента И, выход которого является восьмым выходом блока.
Блок ОЗУ содержит третий и четвертый коммутаторы адреса, третий и четвертый логические элементы НЕ, пятый-восьмой логические элементы И, первый и второй банки ОЗУ, демультиплексор данных и первый мультиплексор данных, при этом первый вход третьего коммутатора адреса и второй вход четвертого коммутатора адреса объединены и являются первым информационным входом блока, второй вход третьего коммутатора адреса и первый вход четвертого коммутатора адреса объединены и являются вторым информационным входом блока, выход третьего коммутатора адреса подключен к первому информационному входу первого банка ОЗУ, а выход четвертого коммутатора адреса - к первому информационному входу второго банка ОЗУ; первые входы пятого и шестого логических элементов И объединены и являются первым тактовым входом блока; первые входы седьмого и восьмого логических элементов И объединены и являются вторым тактовым входом блока; тактовые входы третьего и четвертого коммутаторов адреса, демультиплексора данных и первого мультиплексора данных, вторые тактовые входы логических элементов И, причем шестого и восьмого - соответственно через третий и четвертый логические элементы НЕ, объединены и являются третьим тактовым входом блока; выход пятого логического элемента И соединен с первым тактовым входом первого банка ОЗУ, второй тактовый вход которого соединен с выходом восьмого логического элемента И, выход шестого логического элемента И соединен с первым тактовым входом второго банка ОЗУ, второй тактовый вход которого соединен с выходом седьмого логического элемента И; первый выход демультиплексора данных подключен к второму информационному входу первого банка ОЗУ и второму информационному входу первого мультиплексора данных, а второй выход - к второму информационному входу второго банка ОЗУ и первому информационному входу первого мультиплексора данных, при этом вход демультиплексора данных является третьим информационным входом блока, выход первого мультиплексора данных - выходом блока.
Арифметический блок содержит пятый логический элемент НЕ, девятый и десятый логические элементы И, пять регистров хранения данных, четыре умножителя, три вычитателя, три сумматора и второй мультиплексор данных, при этом вход пятого логического элемента НЕ, второй вход десятого логического элемента И, первый тактовый вход второго мультиплексора объединены и являются первым тактовым входом блока, причем выход пятого логического элемента НЕ соединен с вторым входом девятого логического элемента И; первый вход девятого и десятого логических элементов И, второй тактовый вход второго мультиплексора объединены и являются вторым тактовым входом блока; выход девятого логического элемента И соединен с тактовым входом первого, четвертого и пятого регистров хранения данных, а выход десятого логического элемента И - с тактовым входом второго и третьего регистров хранения данных; информационные входы первого и второго регистров хранения данных объединены и являются первым информационным входом блока, а информационный вход третьего регистра хранения данных - вторым информационным входом блока; первый выход первого регистра хранения данных подключен к первому входу соответственно второго сумматора и второго вычитателя, а второй выход - к первому входу соответственно третьего сумматора и третьего вычитателя, первый выход второго регистра хранения данных подключен к первому входу соответственно первого и третьего перемножителей, а второй выход - к первому входу соответственно второго и четвертого перемножителей, первый выход третьего регистра хранения данных подключен к второму входу соответственно первого и четвертого перемножителей, а второй выход - к второму входу второго и третьего перемножителей; выходы первого и второго перемножителей соединены соответственно с первым и вторым входом первого вычитателя, выход которого подключен к второму входу соответственно второго сумматора и второго вычитателя, выходы третьего и четвертого перемножителей соединены соответственно с первым и вторым входом первого сумматора, выход которого подключен к второму входу соответственно третьего сумматора и третьего вычитателя; выходы второго и третьего сумматоров соединены соответственно с первым и вторым информационным входами четверного регистра хранения данных, выходы второго и третьего вычитателей соединены соответственно с первым и вторым информационным входами пятого регистра хранения данных; выходы четвертого и пятого регистров хранения данных подключены соответственно к первому и второму информационному входу второго мультиплексора, выход которого является выходом блока.
Введение в процессор дополнительных блоков памяти обеспечивает параллельную работу элементов первого арифметического блока, выполняющего базовую операцию БПФ - "бабочку", а введение второго арифметического блока обеспечивает конвейеризацию операций "считывание-операция-запись", вследствие чего достигается максимально возможная производительность процессора в целом.
Изобретение поясняется чертежами, на которых представлены: фиг.1 - функциональная схема заявленного процессора для БПФ; фиг.2 - структурная схема блока управления; фиг.3 - структурная схема блока ОЗУ; фиг.4 - структурная схема арифметического блока; фиг.5 - временная диаграмма работы заявленного процессора для БПФ.
Процессор с максимально возможной производительностью для быстрого преобразования Фурье (фиг.1) содержит первый-пятый (11-15) формирователи адреса, первый 21 и второй 22 коммутаторы адреса, блок 3 оперативного запоминающего устройства (ОЗУ), блок 4 постоянной памяти коэффициентов, первый 51 и второй 52 арифметические блоки, блок 6 управления. Информационный вход каждого из формирователей адреса подключен к шине входных данных 34, являющейся информационным входом процессора. Тактовый вход первого 11 и второго 12 формирователей адреса соединен с первым выходом 24 блока 6 управления, второй выход 25 которого соединен с тактовым входом третьего 13, четвертого 14 и пятого 15 формирователей адреса. Информационные выходы первого 11 и второго 12 формирователей адреса подключены соответственно к первому и второму входам первого 21 коммутатора адреса, тактовый вход которого соединен с третьим выходом 26 блока 6 управления и этот выход также соединен с первым тактовым входом первого 51 и второго 52 арифметических блоков и тактовым входом второго 22 коммутатора адреса, к первому и второму информационным входам которого подключены информационные выходы соответственно третьего 13 и четвертого 14 формирователей адреса. Управляющий выход третьего 13 формирователя адреса соединен с третьим входом 22 блока 6 управления, первый 20 и второй 21 входы которого соединены соответственно с вторым и третьим управляющими выходами первого 11 формирователя адреса, а четвертый вход 23 - с генератором тактовых импульсов (на схеме не показан). Информационный выход пятого 15 формирователя адреса подключен к входу блока 4 постоянной памяти коэффициентов, информационный выход которого подключен к второму входу первого 51 и второго 52 арифметических блоков, выходы которых объединены, подключены к третьему информационному входу блока 3 ОЗУ и являются при этом информационным выходом 19 процессора. Выход первого коммутатора адреса 21 соединен с первым информационным входом блока 3 ОЗУ и является при этом адресным выходом 33 процессора; выход второго коммутатора адреса 22 соединен с вторым информационным входом блока 3 ОЗУ, первый, второй и третий тактовые входы которого соединены соответственно с четвертым 27, пятым 28 и шестым 29 выходами блока 6 управления, седьмой 30 и восьмой 31 выходы которого подключены к второму тактовому входу соответственно первого 51 и второго 52 арифметических блоков, к первому информационному входу которых подключен информационный выход 18 блока 3 ОЗУ.
Блок 6 управления (фиг.2) содержит постоянное запоминающее устройство (ПЗУ) 7, регистр 8, первый 91 и второй 92 логические элементы НЕ, первый-четвертый (101-104) логические элементы И. Первый, второй и третий адресные входы ПЗУ 7, являющиеся первым, вторым и третьим входом блока, соединены соответственно с вторым и третьим управляющими выходами первого формирователя адреса 11 и управляющим выходом третьего формирователя адреса 13. Четвертым тактовым входом блока, соединенным с генератором тактовых импульсов, является вход записи регистра 8, который объединен с входом первого 91 и второго 92 логических элементов НЕ, вторыми входами первого 101 и второго 102 логических элементов И. Выходы первого 91 и второго 92 логических элементов НЕ подключены к вторым входам соответственно третьего 103 и четвертого 104 логических элементов И. Информационные выходы регистра 8 подключены к ПЗУ 7, выход которого соединен с информационным входом регистра 8. Его первый выход соединен с первым входом первого логического элемента И 101, выход которого является первым выходом блока, подключенным к тактовому входу первого 11 и второго 12, формирователей адреса. Второй выход регистра 8 соединен с первым входом второго логического элемента И 102, выход которого является вторым выходом блока, подключенным к тактовому входу третьего 13, четвертого 14 и пятого 15 формирователей адреса. Третий выход регистра 8, являющийся третьим выходом блока, соединен с тактовым входом первого 21 и второго 22 коммутаторов адреса, первому тактовому входу первого 51 и второго 52 арифметических блоков. Четвертый, пятый и шестой выходы регистра 8, являющиеся четвертым, пятым и шестым выходами блока, соединены соответственно с первым, вторым и третьим тактовыми входами блока 3 ОЗУ (фиг.1). Седьмой выход регистра 8 соединен с первым входом третьего логического элемента И 103, выход которого является седьмым выходом блока, подключенным к второму тактовому входу первого арифметического блока 51. Восьмой выход регистра 8 соединен с первым входом четвертого логического элемента И 104, выход которого является восьмым выходом блока, подключенным к второму тактовому входу второго арифметического блока 52. Блок 3 ОЗУ (фиг.3) содержит третий 23 и четвертый 24. коммутаторы адреса, третий 93 и четвертый 94 логические элементы НЕ, пятый-восьмой (105-108) логические элементы И, первый 111 и второй 112 банки ОЗУ, демультиплексор данных 12 и первый мультиплексор данных 131. Первый вход третьего коммутатора адреса 23 и второй вход четвертого коммутатора адреса 24 объединены и являются первым информационным входом блока, подключенным к информационному выходу второго 22 коммутатора адреса (фиг.1). Второй вход третьего коммутатора адреса 23 и первый вход четвертого коммутатора адреса 24 объединены и являются вторым информационным входом блока, подключенным к выходу первого 21 коммутатора адреса. Выход третьего коммутатора адреса 23 подключен к первому информационному входу первого банка ОЗУ 111, а выход четвертого коммутатора адреса 24 - к первому информационному входу второго банка ОЗУ 112. Первые входы пятого 105 и шестого 106 логических элементов И объединены и являются первым тактовым входом блока, подключенным к четвертому выходу блока 6 управления. Первые входы седьмого 107 и восьмого 108 логических элементов И объединены и являются вторым тактовым входом блока, подключенным к пятому выходу блока 6 управления. Тактовые входы третьего 23 и четвертого 24 коммутаторов адреса, демультиплексора 12 данных и первого мультиплексора данных 131, вторые тактовые входы логических элементов И, причем шестого 106 и восьмого 108 - соответственно через третий 93 и четвертый 94 логические элементы НЕ, объединены и являются третьим тактовым входом блока, подключенным к шестому выходу блока 6 управления. Выход пятого логического элемента И 105 соединен с первым тактовым входом первого банка ОЗУ 111, второй тактовый вход которого соединен с выходом восьмого логического элемента И 108. Выход шестого логического элемента И 106 соединен с первым тактовым входом второго банка ОЗУ 112, второй тактовый вход которого соединен с выходом седьмого логического элемента И 107. Первый выход демультиплексора данных 12 подключен к второму информационному входу первого банка ОЗУ 111 и второму информационному входу первого мультиплексора данных 131, а второй выход - к второму информационному входу второго банка ОЗУ 112 и первому информационному входу первого мультиплексора данных 131, при этом вход демультиплексора данных 12 является третьим информационным входом блока, подключенным к объединенному выходу первого 51 и второго 52 арифметических блоков, а выход первого мультиплексора данных 131 - выходом блока 3 ОЗУ. Арифметический блок (фиг.4) содержит пятый логический элемент НЕ 95, девятый 109 и десятый 1010 логические элементы И, первый-пятый (141-145) регистры хранения данных, первый-четвертый (151-154) умножители, первый-третий (161-163) вычитатели, первый-третий (171-173) сумматоры и второй мультиплексор данных 132. Вход пятого логического элемента НЕ 95, второй вход девятого логического элемента И 109, первый тактовый вход второго мультиплексора данных 132 объединены и являются первым тактовым входом блока, подключенным к третьему выходу блока 6 управления (фиг.1). Выход пятого логического элемента НЕ 95 соединен с вторым входом десятого логического элемента И 1010. Первый вход девятого 109 и десятого 1010 логических элементов И, второй тактовый вход второго мультиплексора данных 132 объединены и являются вторым тактовым входом блока, подключенным к 7 и 8 выходам блока 6 управления соответственно. Выход девятого логического элемента И 109 соединен с тактовым входом первого 141, четвертого 144 и пятого 145 регистров хранения данных, а выход десятого логического элемента И 109 - с тактовым входом второго 142 и третьего 143 регистров хранения данных. Информационные входы первого 141 и второго 142 регистров хранения данных объединены и являются первым информационным входом блока, подключенным к выходу блока 3 ОЗУ, а информационный вход третьего регистра хранения данных 143 - вторым информационным входом блока, подключенным к выходу блока 4 постоянной памяти (фиг.1). Первый выход первого регистра хранения данных 141 подключен к первому входу соответственно второго сумматора 172 и второго вычитателя 162, а второй выход - к первому входу соответственно третьего сумматора 173 и третьего вычитателя 163. Первый выход второго регистра хранения данных 142 подключен к первому входу соответственно первого 151 и третьего 153 перемножителей, а второй выход - к первому входу соответственно второго 152 и четвертого 154 перемножителей. Первый выход третьего регистра хранения данных 143 подключен к второму входу соответственно первого 151 и четвертого 154 перемножителей, а второй выход - к второму входу второго 152 и третьего 153 перемножителей. Выходы первого 151 и второго 152 перемножителей соединены соответственно с первым и вторым входом первого вычитателя 161, выход которого подключен к второму входу соответственно второго сумматора 172 и второго вычитателя 162, выходы третьего 153 и четвертого 154 перемножителей соединены соответственно с первым и вторым входом первого сумматора 171, выход которого подключен к второму входу соответственно третьего сумматора 173 и третьего вычитателя 163. Выходы второго 172 и третьего 173 сумматоров соединены соответственно с первым и вторым информационным входами четверного регистра хранения данных 144, выходы второго 162 и третьего 163 вычитателей соединены соответственно с первым и вторым информационным входами пятого регистра хранения данных 145. Выходы четвертого 144 и пятого 145 регистров хранения данных подключены соответственно к первому и второму информационному входу второго мультиплексора данных 132, выход которого является выходом арифметического блока.
Описанный процессор для БПФ работает в соответствии с временной диаграммой (фиг.5). В исходном состоянии, как и после окончания вычисления БПФ, формирователи адресов 11-15 установлены в нулевое состояние. В начале каждой итерации по шине 35 входных данных на формирователи адреса 11-15 извне поступают операнды
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] - смещение.
Первый формирователь адреса 11 выдает сигнал разрешения работы 21 высокого логического уровня на блок 6 управления. Сигнал разрешения работы 21 выдается на время всего преобразования. По завершении преобразования этот сигнал снимается. По сигналу разрешения работы 21 начинается вычисление БПФ. Блок 6 управления выполнен по принципу конечного автомата и работает следующим образом. На его четвертый вход (фиг.2, фиг.5) поступают тактовые импульсы 23. По переднему фронту импульса сигнала тактовой частоты 23 регистр 8 защелкивает информацию с выхода данных ПЗУ 7. С выхода регистра 8 информация поступает на адресный вход ПЗУ 7 и в соответствии с логическими уровнями сигналов 20, 21 и 22 определяет, что будет загружено в регистр 8 по следующему импульсу сигнала тактовой частоты 23 (следующее состояние конечного автомата). Сигнал выбора 26 между элементами а и b выдается напрямую с регистра 8. Его логический уровень меняется каждый период тактовой частоты 23. Низкий логический уровень этого сигнала соответствует передаче элемента а из блока ОЗУ 3 в первый арифметический блок 51 по сигналу 30 высокого логического уровня и во второй арифметический блок 52 по сигналу 31 высокого логического уровня. Высокий логический уровень сигнала выбора 26 соответствует передаче элемента b из блока ОЗУ 3 в первый арифметический блок 51 по сигналу 30 высокого логического уровня и во второй арифметический блок 52 по сигналу 31 высокого логического уровня. Сигнал чтения 27 из блока ОЗУ 3 выдается напрямую с регистра 8. Высокий логический уровень этого сигнала соответствует чтению из блока ОЗУ 3. Сигнал записи 28 в блок ОЗУ 3 выдается напрямую с регистра 8. Высокий логический уровень этого сигнала соответствует записи в блок ОЗУ 3. Сигнал переключения 29 банков ОЗУ выдаются напрямую с регистра 8. Низкий логический уровень этого сигнала соответствует чтению данных из первого банка ОЗУ 111 и записи данных во второй банк ОЗУ 112. Высокий логический уровень этого сигнала соответствует чтению данных из второго банка ОЗУ 112 и записи данных в первый банк ОЗУ 111. Сигналы 24 и 25 стробируются тактовыми импульсами с помощью первого 101 и второго 102 логических элементов И соответственно. По импульсам высокого логического уровня этих сигналов длительностью в половину периода тактовой частоты формирователи адреса формируют адреса следующих элементов матриц. Сигналы 30 и 31 стробируются инверсными тактовыми импульсами с помощью логических цепочек соответственно 91-103 и 92-104. По импульсам высокого логического уровня сигналов 30 и 31 длительностью в половину периода тактовой частоты элементы а, b и q запоминаются в регистрах хранения данных 14 арифметических блоков 51 и 52.
Первый формирователь адреса выдает также адрес первого элемента матрицы F на первый вход первого коммутатора адреса 21. Второй формирователь адреса 12 выдает адрес первого элемента матрицы G на второй вход второго коммутатора адреса 21. Третий формирователь адреса 13 выдает адрес первого элемента матрицы А на первый вход второго коммутатора адреса 22. Четвертый формирователь адреса 14 выдает адрес первого элемента матрицы В на второй вход второго коммутатора адреса 22. Пятый формирователь адреса 15 выдает адрес первого элемента матрицы Q на вход блока постоянной памяти 4. Блок 6 управления низким логическим уровнем сигнала 26 переключает коммутаторы адреса 21 и 22 на выдачу адресов элементов матриц F и А соответственно, а первый 51 и второй 52 арифметические блоки - на прием элемента матрицы А. Также блок 6 управления выдает сигнал чтения 27 на блок ОЗУ 3 и сигнал выбора 30 первого арифметического блока 51. Блок ОЗУ 3 по сигналу 27 выдает элемент матрицы А. Первое арифметическое устройство 51 по сигналу 30 запоминает элемент матрицы А.
Блок ОЗУ 3 (фиг.3) может работать в двух режимах в зависимости от уровня сигнала 29 переключения банков ОЗУ, поступающего из блока 6 управления. Если сигнал 29 имеет низкий логический уровень, то адреса элементов а и b по шине 32 через третий коммутатор адреса 23 поступают на первый банк ОЗУ 111. Адреса элементов f и g по шине 33 через четвертый коммутатор адреса 24 поступают на второй банк ОЗУ 112. Сигнал чтения 27 из блока ОЗУ 3 через пятый элемент И 105 поступает на первый банк ОЗУ 111. Сигнал записи 28 в блок ОЗУ 3 через седьмой элемент И 107 поступает на второй банк ОЗУ 112. При высоком уровне сигнала 27 данные из первого банка ОЗУ 111 через первый мультиплексор данных 131 поступают на шину 18. При высоком логическом уровне сигнала 28 данные с шины 19 через демультиплексор данных 12 записываются во второй банк ОЗУ 112. Если сигнал 29 имеет высокий логический уровень, то адреса элементов а и b по шине 32 через четвертый коммутатор адреса 24 поступают на второй банк ОЗУ 112. Адреса элементов f и g по шине 33 через третий коммутатор адреса 23 поступают на первый банк ОЗУ 111. Сигнал чтения 27 через шестой элемент И 106 поступает на второй банк ОЗУ 112. Сигнал записи 28 в блок ОЗУ 3 через восьмой элемент И 108 поступает на первый банк ОЗУ 111. При высоком логическом уровне сигнала 27 данные из второго банка ОЗУ 112 через первый мультиплексор данных 131 поступают на шину 18. При высоком логическом уровне сигнала 28 данные из арифметических блоков 5 по шине 19 через демультиплексор данных 12 записываются в первый банк ОЗУ 111.
Арифметический блок 5 (фиг.4) работает следующим образом.
Элементы а и b из блока ОЗУ 3 последовательно поступают по шине 18, а константы q - по шине из блока 4 постоянной памяти коэффициентов. Если сигнал выбора 26 между числами а и b имеет низкий логический уровень, то по приходу импульса высокого логического уровня сигнала выбора 30(31) арифметического блока элемент а защелкивается в первом регистре хранения данных 141 и подсчитанный в предыдущей операции элемент f из четвертого регистра хранения данных 144 через второй мультиплексор данных 132 поступает на шину 19. Если сигнал выбора 26 между числами а и b имеет высокий логический уровень, то по приходу импульса высокого логического уровня сигнала выбора 30(31) арифметического блока элемент b защелкивается во втором регистре хранения данных 142, константа q защелкивается в третьем регистре хранения данных 143 и подсчитанный в предыдущей операции элемент g из пятого регистра хранения данных 145 через второй мультиплексор данных 132 поступает на шину 19. С выхода второго регистра хранения данных 142 действительная часть элемента b (Re(b)) поступает на первый 152 и третий 154 умножители, а мнимая часть элемента b (Im(b)) поступает на второй 151 и четвертый 154 умножители. С выхода третьего регистра хранения данных 143 действительная часть константы q (Re(q)) поступает на первый 151 и четвертый 154 умножители, а мнимая часть константы q (Im(q)) поступает на второй 152 и третий 153 умножители. С выхода первого умножителя 151 произведение Re(b)*Re(q) поступает на первый вычитатель 161, на второй вход которого поступает произведение Im(b)*Im(q) с выхода второго умножителя 152. С выхода третьего умножителя 153 произведение Re(b)*Im(q) поступает на первый сумматор 171, на второй вход которого поступает произведение bn(b)*Re(q) с выхода четвертого умножителя 154. С выхода первого вычитателя 161 разность Re(b)*Re(q)-Im(b)*Im(q) поступает на второй сумматор 172, где складывается с действительной частью элемента a (Re(a)), образуя действительную часть элемента f (Re(f)=Re(a)+Re(b)*Re(q)-Im(b)*Im(q)), и на вход второго вычитателя 162, где вычитается из действительной части элемента a (Re(a)), образуя действительную часть элемента g (Re(g)=Re(a)-Re(b)*Re(q)-Im(b)*Im(q)). С выхода первого сумматора 171 сумма Re(b)*Im(q)+Im(b)*Re(q) поступает на третий сумматор 173, где складывается с мнимой частью элемента a (Im(a)), образуя мнимую часть элемента f (Im(f)=Im(a)+Re(b)*bn(q)+Im(b)*Re(q)), и на вход третьего вычитателя 163, где вычитается из мнимой части элемента a (Im(a)), образуя мнимую часть элемента g (Im(g)=Im(a)-Re(b)*Im(q)-Im(b)*Re(q)). Одновременно с защелкиванием следующего элемента а в первом регистре хранения данных 141 вычисленные элементы f и g защелкиваются в четвертом 144 и пятом 145 регистрах хранения данных соответственно.
На следующем такте блок 6 управления высоким логическим уровнем сигнала 26 переключает коммутаторы адреса 21 и 22 на выдачу адреса элементов матриц G и В соответственно, а арифметические блоки 51 и 52 - на прием элементов матриц В и Q. Эти элементы также запоминаются в первом арифметическом блоке 51 по импульсу высокого логического уровня сигнала 30. После этого блок 6 управления выдает импульс высокого логического уровня 25 на формирователи адреса 13, 14 и 15, по которому они формируют адрес следующих элементов матриц А, В и Q.
Далее происходит аналогичная загрузка данных во второй арифметический блок 52. Во время дальнейших циклов загрузки данных в арифметические блоки 51 и 52 блок 6 управления дополнительно выдает импульс высокого логического уровня 24 на формирователи адреса 11 и 12 и сигнал записи 28 в блок ОЗУ 3, по которому происходит запись элементов матриц F и G во второй банк ОЗУ 112. Приход импульса высокого логического уровня сигнала конца итерации 22 с третьего формирователя адреса 13 запрещает блоку 6 управления выдачу тактовых импульсов 25 на формирователи адреса 13, 14 и 15. При этом выгрузка данных из арифметических блоков 51 и 52 продолжается. При приходе импульса высокого логического уровня сигнала конца итерации 20 с первого формирователя адреса 11 блок 6 управления сигналом 29 переключает первый 111 и второй 112 банки ОЗУ в блоке ОЗУ 3 и начинает новую итерацию. Таким образом, на одну итерацию затрачивается количество тактов, равное числу исходных данных плюс 4 такта. Длительность такта, в свою очередь, определяется минимальным временем чтения (записи) одного элемента из блока ОЗУ 3.
Вычисление матричного БПФ с прореживанием по времени описывается следующим выражением:
где р=2m-1, t=2-r-m, m=1, 2, 3...r, длина исходного массива N=2r;
операция 
представляет собой поэлементное умножение столбцов матрицы В на вектор столбец Q.
Весовые коэффициенты представляются следующим выражением:
Q1=cos(2π(i-1)/N)-j*sin(2π(i-1)/N)
где i=1, 2, 3...N/2; 
Рассмотрим варианты вычисления матричного БПФ на примере массива размерностью N=2r, при r=4. Количество итераций: r=4.
1 итерация: m=1, t=8, p=1
В первом банке ОЗУ 111 имеем массив, состоящий из матриц 
и 
:
В блоке постоянной памяти коэффициентов 4 имеем матрицу 
:
Элементы (a1, b1, q1), (а3, b3, q1), (a5, b5, q1) и (a7, b7, q1) будут последовательно переданы первому арифметическому блоку 51.
Элементы (а2, b2, q1), (a4, b4, q1), (a6, b6, q1) и (a8, b8, q1) будут последовательно переданы второму арифметическому блоку 52.
После окончания итерации во втором банке ОЗУ 112 имеем:
2 итерация: m=2, p=2, t=4
В начале итерации во втором банке ОЗУ 112 имеем массив, состоящий из матриц 
и 
В блоке постоянной памяти коэффициентов 4 имеем матрицу 
:
Элементы (a1, b1, q1), (а3, b3, q1), (a5, b5, q2) и (а7, b7, q2) будут последовательно переданы первому арифметическому блоку 51.
Элементы (а2, b2, q1), (a4, b4, q1), (а6, b6, q2) и (a8, b8, q2) будут последовательно переданы второму арифметическому блоку 52.
После окончания итерации в первом банке ОЗУ 111 имеем:
3 итерация: m=3, p=4, t=2
В начале итерации в первом банке ОЗУ 111 имеем массив, состоящий из матриц 
и 
В блоке постоянной памяти коэффициентов 4 имеем матрицу 
:
Элементы (a1, b1, q1), (а3, b3, q5), (a5, b5, q3) и (а7, b7, q7) будут последовательно переданы первому арифметическому блоку 51.
Элементы (а2, b2, q1), (a4, b4, q3), (a6, b6, q5) и (a8, b8, q7) будут последовательно переданы второму арифметическому блоку 52.
После окончания итерации во втором банке ОЗУ 112 имеем:
4 итерация: m=4, p=8, t=1
В начале итерации во втором банке ОЗУ 112 имеем массив, состоящий из матриц 
и 
.
В блоке постоянной памяти коэффициентов 4 имеем матрицу 
:
Элементы (a1, b1, q1), (а3, b3, q3), (а5, b5, q2) и (а7, b7, q4) будут последовательно переданы первому арифметическому блоку 51.
Элементы (а2, b2, q5), (a4, b4, q7), (а6, b6, q6) и (a8, b8, q8) будут последовательно переданы второму арифметическому блоку 52.
После окончания итерации в первом банке ОЗУ 111 имеем:
В итоге в первом банке ОЗУ 111 записались искомые составляющие комплексного спектра входного сигнала, причем потенциально максимальная скорость вычислений достигается за счет параллельного выполнения операций чтения-записи в первый 111 и второй 112 банки ОЗУ и параллельным выполнением арифметических операций в первом 51 и втором 52 арифметических блоках.
Количество операций "бабочка" в одной итерации и количество итераций определяются размерностью N. По окончании записи последнего элемента последней итерации в блок ОЗУ 3 первый формирователь адреса 11 снимает сигнал разрешения работы 21. При этом блок 6 управления устанавливается в исходное состояние. Результаты вычислений находятся в блоке ОЗУ 3 (если r четное, то в первом банке ОЗУ 111, если r нечетное, то во втором банке ОЗУ 112) и по шинам 33 (адрес) и 19 (данные) поступают потребителю информации.
| название | год | авторы | номер документа |
|---|---|---|---|
| Процессор быстрого преобразования Фурье | 1988 |
|
SU1667101A1 |
| Процессор быстрых дискретных преобразований | 1989 |
|
SU1725227A1 |
| Устройство для контроля памяти | 1983 |
|
SU1280459A1 |
| Устройство для формирования адресов операндов процессора быстрого преобразования Фурье | 1982 |
|
SU1056207A1 |
| АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ | 1991 |
|
RU2015550C1 |
| Устройство для вычисления матрицы функций | 1987 |
|
SU1439618A1 |
| Устройство для регистрации информации | 1985 |
|
SU1304170A1 |
| Микропрограммный процессор | 1982 |
|
SU1070557A1 |
| Устройство для воспроизведения аналогового сигнала | 1988 |
|
SU1524175A1 |
| Процессор для обработки массивов данных | 1985 |
|
SU1293737A1 |
Изобретение относится к вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов, в частности устройствах, выполняющих БПФ массивов произвольной размерности N=2r. Техническим результатом является потенциально возможное максимальное быстродействие процессора для БПФ при заданном выборе элементной базы его реализации. Процессор содержит пять формирователей адреса, два коммутатора адреса, блок постоянной памяти коэффициентов, блок оперативного запоминающего устройства (ОЗУ), два арифметических блока, блок управления. 3 з.п. ф-лы, 5 ил.
| Устройство для реализации быстрого преобразования фурье | 1975 |
|
SU590750A1 |
| Процессор быстрого преобразования Фурье | 1988 |
|
SU1667101A1 |
| US 6317770 B1, 13.11.2001 | |||
| Топчак-трактор для канатной вспашки | 1923 |
|
SU2002A1 |
| ЩИТОВОЙ ДЛЯ ВОДОЕМОВ ЗАТВОР | 1922 |
|
SU2000A1 |
