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

 

Соеоз Советских

Соцмаектмческмх республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ ТИЛЬСТВУ

<18О9198 (61) Дополнительное к авт. сеид-ву (5! }м. кл.з (22) Заявяемо17.05.79 Р1) 2765999/18-24

G 06 F 15/332 с присоединением заявки ¹ (23) Г3риормтет

ГосуяавствеммыА коммтет

СССР во яма» мзобретеммА и отквытмА

Опубликовано 280281. Бюллетень Н9 8 (53} УДК 681. 3 (088.8) Дата опубликования описания 28. 02 . 81

Р2) Авторы изобретения

A,Í. Карташевнч и В.В. Николаевский

Научно-исследовательский институт прикладных физических проблем при Белорусском государственном университете им. В.И. Ленина . (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

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

Наиболее близким по технической 1З сущности к данному является устройство, содержащее арифметический блок, блок комплексных. тригонометрических констант, блок сверхопе1эативной памяти, блок прямого доступа p).20

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

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

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

-первый и второй выходы узла задания режима соединены с первыми входами элементов И,соответственно, первой и второй групп, вторые входы которых подключены к первому выходу регистра, второй и третий выходы которого подключены,.соотйетстненно, к первым входам сумматора и .узла задания режима, третий и четвертый выходы которого подключены соответственно, ко входам первого и второго счетчиков, первые выходы которых соединены, соответственно,со вторым и третьим входами узла задания режима, пятый выход которого подключен ко входу регистра, вторые выходы парного и второго с- етчиков соединены с первыми . ходами, соответственно, первого и второго коммутаторов, ВтОрые входы которых соединены с выходами элементов ?<,àooòâåòñòàåíío, первой и второй групп, выходы коммутаторов являются выходами устрОйства, ВыхОд сумматора соединен через узел обращения кода адреса с выходом устройства и через регистр хранения адреса со своим вторым входом.

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

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

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

Вторые инверсные ВЫХОды регистра

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

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

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

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

При начале вычислений двумерного

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

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

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

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

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

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

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

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

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

БПФ по одному столбцу (строке).

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

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

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

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

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

1. Авторское свидетельство СССР

В 467356, кл. 6 06 F 15/34, 1975.

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

809198

Заказ 413/60

Тираж 75б Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Oàòåèò", г. Ужгород, ул. Проектная,4

Составитель В. Вальков

Редактор И. Ковальчук Техред Т. Каточка - Корректор Г Назарова