Устройство для реализации быстрогопРЕОбРАзОВАНия фуРьЕ Советский патент 1981 года по МПК G06F17/14 

Изобретение относится к вычислительной технике и может быть исполь зовано для решения задач цифровой обработки информации.

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

Недостаток такого устройства низкое быстродействие при вычислении двухмерного преобразования Фурь

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

Недостатком известного устройст является низкое быстродействие и большие аппаратурные затраты.

Цель изобретения - повышение быстродействия устройства и уменьшение аппаратурных затрат.

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

управления, причем первый, второй и третий выходы блока управления соединены,соответственно, со входами постоянной памяти, арифметическОго блока и оперативной пгмягк, первая и вторая группы входов арифметического блока соединены,соответственно с группами выходов постоянной и оперативной памяти, блок управления соде|ЯЕит регистр, первую и вторую хруппы элементов И, первый и второй коммутаторы, узел задания режима, первый и второй счетчики, сумматор, регистр хранения адреса и

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

выход которого подключен ко входу

регистра, вторые выхода первого и второго счетчиков соединены с первыми кодами, соответственно niapsoro и второго коммутаторов, вторые вход KOTopfcax соединены с выsoяa м элементов И соответственно, первой и второй групп, выходы коммутаторов являются выходами устройства, выход сумматора соединен через узел обращения кода адреса с выходом устройства и через регистр хранения адреса со своим вторым входом.

На фиг. 1 приведена блок-схема ycTpovlcTBa; на фиг. 2 - блок управления .

Устройство содержит. постоянную паклть 1, оперативную память 2, блок 3 угфавления, арифметический блок 4 регистр 5, узел 6 задания режима, счетчики 7.и 8, группы-элементов И 9 и 10, комментаторы 11 и 12 сумматор 13, регистр 14 хранения адреса, узел 15 обршдения кода адреса.

Коммутаторы 11- и 12 могут быть выполнены на базе селекторов на три канала. Первые входы селекторов первого и второго коммутаторов соединяются с инверсными выходами младших разрядов счетчиков 7 и 8 соответственно. Второй вход j-ro селектора соединен с j-ым разрядом, а третий вход j-ro селектора с (j--f-l разрядов соответствующего счетчика.

Управлякядие входы J-x селекторов соединены с J и (j+l) разрядом регистра .

Счетчики выполнены с отделяег зым вентилем младших разрядов.

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

Информация в двоично-инверсном порядке заносится в память 2 (отдельно действительная и мнимые части), в память 1 записаны значения четверти периода косинуса. По кодги-х адресов, вырабатываемьох блоком 3 управления,информация выбирается из памяти 2 и заносится в арифметический блок 4, где происходит вычисление коэффициентов Фурье. Результат вычислений снова заносится в память 2 на место выбранной информации по адресам, вырабатываег лм блоком управления.

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

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

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

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

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

Единица в последнем разряде счетчика 8 соответствует окончанию вычислений БПФ по столбцам (строкам). Узел задания режима подключает первый выход второго счетчика к входу регистра 5, а его третий выход к входу первого счетчика.

Тактовые импульсы подаются на вход счетчика 8 и начинается вычисление БПФ по строкам (столбцам). На первом выходе устройства у формируются адреса строк (столбцов), а на выходе у, адреса операндов, выбираеьих из памяти 2.

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

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

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

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

и третий выходы блока управления соединены, cooтвeтcтвeннo со входс1ми постоянной памяти, арифметического блока и оперативной памяти, первая и вторая группы входов арифметического блока соединены,соответственно, с группами выходов постоянной и оперативной памяти, отличающееся тем, что, с целью увеличения быстродействия и уменьшения аппаратурных затрат, блок управления содержит регистр, первую и вторую группы элементов И, первый и второй коммутаторы, узел задания режима, первый и второй счетчики, сумматор, регистр хранения адреса и узел обращения кода адреса, причем первый и второй выходы узла задания режима соединены с первыми входами элементов и соответственно первой и второй групп, вторые входы которых подключены к первому выходу регистра, второй и третий выходы которого подключены, соответственно, к первым входам сумматора и узла задания режима, третий и четвертый выходы которого подключены, соответственно, ко входам первого и второго счетчиков, первые выходы которых соединены соответственно, со пторым и третьим входами узла згщания режима, пятый выход к -торого подключён ко входу регистра, выходы первого и второго счетчиков соединены с первыми входами соответственно первого и второго ко№1 утаторов, вторые входы которых соединены

с выходами элементов И,соответственнс

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

Источники информа ции, принятые во внимание при экспертизе

1. Авторское свидетельство СССР №467356, кл. G 06 F 15/34, 1975.

2. Аврорин А.В. и др. Система для цифрового восстановления голографических изображений в реальном времени эксперимента, Автометрия, 1978, № 4 (прототип) .

Уг

9at. t