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

Свез Советских Соцнавктнческмх реснублмкОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ТИЛЬСТВУ и 1 8 О 9198(22) Заяеяено 17.05.79 Р 1) 2765999/18-24 С 06 Г 15/332 с присоедимеммем заявки Но(23) Приоритет ГосуаарстееыА комтет СССР во аманзобретеАоткрытА(088,8) Дата опубликования описания 28, 02, 81(72) Авторы изобретения А.Н. Карташевнч н В.В. Николаевский Научно-исследовательский институт прикладныхфизических проблем при Белорусскомгосударственном университете им. В.И. Ленина .(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к вычислительной технике и может быть использовано для решения задач цифровой обработки информации.Известно устройство, содержащее регистры реальной и мнимой частей комплексного весового коэффициента, регистр вещественной части числа, первый н второй сумматоры с запоминанием переноса н три логических блока 1 .Недостаток такого устройства " низкое быстродействие прн вычислении двухмерного преобразования фурье.Наиболее близким по технической 1 З сущности к данному является уст" ройство, содержащее арифметический блок, блок комплексных. тригонометрических констант, блок сверхоперативной памяти, блок прямого доступа 2.20Недостатком известного устройства является низкое быстродействие и большие аппаратурные затраты.Цель изобретения - повышение быстродействия устройства и умень шение аппаратурных затрат,Поставленная цель достигается тем, что устройство, содержащееоперативную память, постоянную память, арифметический блок и блок 30 управления, причем первый, второйи третий выходы блока управлениясоединены, соответственно, со входамипостоянной памяти, арифметическогоблока и оперативной памяти, перваяи вторая группы входов арифметического блока соединены,соответственно с группами выходов постояннойи оперативной памяти, блок управления содержит регистр, первую нвторую группы элементов и, первый нвторой коммутаторы, узел заданиярежима, первый и второй счетчики,суюетор, регистр хранения адреса иузел обращения кода адреса, причем-первый и второй выходы узла заданиярежима соединены с первыми входамиэлементов И,соответственно, первойн второй групп, вторые входы которыхподключены к первому выходу регистра,второй и третий выходы которого подключены,соотйетственно, к первымвходам сумматора н .узла задания резима, третий н четвертый выходы которого подключены соответственно, ковходам первого и второго счетчиков,первые выходы которых соединены, соответственно,со вторым и третьимвходами узла задания режима, пятыйвыход которого подключен ко входурегистра, вторые выходы первого ивторого счетчиков соединены с первыми .ходами, соответственно, первогои второго коммутаторов, вторые входыкоторых соединены с выходами эле"кентов И,соответственно, первой ивторой групп, выходы коммутаторовявляются выходами устройства, выходсумматора соединен через узел обращения кола адреса с выходом устройства и через регистр хранения адреса со своим вторым входом.На фиг. 1 приведена блок-схемаустройства; на фиг. 2 - блок управления.Устройство содержит. постояннуюпамять 1, оперативную память 2,блок 3 управления, арифметическийблок 4 регистр 5, узел б заданиярежима счетчики .и 8, группы элементов И 9 и 10, комкутаторы 11 и 12,сумматор 13, регистр 14 храненияадреса, узел 15 обращения кода адреса.Коммутаторы 11 и 12 могут бытьвыпо."нены на базе селекторов натри канала. Первые входы селекторовпервого и второго коммутаторовсоединяются с инверсными выходамимладших разрядов счетчиков 7 и 8,соответственно. Второй вход )-го се"лектора соединен с )-ым разрядом,а третий вход )-го селектора с;(+1)разрядов соответствующего счетчика.управляющие входы 3-х селекторовсоединены с 3 и (,)+1) разрядом регистра,счетчики выполнены с отделяемымвентилем младших разрядов.Вторые инверсные выхОды регистра5, начиная ао второго разряда,соединены а первыми входами сумматора вобратном порядке, т.е. младший разряд регистра соединен со старшимразрядом сумматора и т,дУстройство работает следующимобразом.Информация в двоичнО-ИНВЕРСНОМпорядке заносится в память 2 (отдельно действительная и мнимые части), н память 1 записаны значениячетверти периода косинуса. По кодамадресов, вырабатываемых блоком 3Управления, информация выбирается из,памяти 1 и 2 и заносится в арифметический блок 4, где происходит вычисление коэффициентов фурье, Результат вычислений снова заносится впамять 2 на место выбранной информа"ции по адресам, вырабатываемым блоком управления.Для вычисления БПФ от двумерногомассива данных необходимо вначалевыполнить БПФ по строкам (или постолбцам), а затем по столбцам (илипо строкам) данных.При начале вычислений двумерногоБПФ узел задания режима подает так",овые импульсы на вход первого счетчика, первый выход которого через узел задания режима подключается ко входу второго счетчика и входу регистра, второй счетчик фор.мирует номер (столбца) строки, а первый счетчик - номера операндов, :выбираемых для вычисления строки (столбца).При этом на управляющий вход разделительного вентиля первого счетчика подаются импульсы управления.Высокий потенциал соответствует формированию иа выходе у адресов, выбираемых иэ памяти 2, а низкий - формированию адресов, по которым информация заносится после вычислений наместо выбранной. Одновременно навыходе у формируются адреса значенийсинуса и косинуса, выбираемых иэпамяти 1.После завершения итерации вычисления БПФ единица иэ последнего разряда первого счетчика заносится в регистр, где происходит сдвиг информации на единицу, и начинается следующая итерация вычислений. Когда регистр 5 заполняется единицами (выполнено вычисление БПФ одного столбца или строки), регистр обнуляется,а единица с его последнего разрядачерез узел 6 задания режима попадаетна счет второго счетчика 8, в котором формируется адрес следующегостолбца (строки) и начинается следующий цикл вычислений БНФ го столбцам(строкам).Единица в последнем разряде счетчика 8 соответствует окончанию вычислений БПФ по столбцам (строкам),узел задания режима подключает первый выход второго счетчика к входурегистра 5, а его третий выход -к входу первого счетчика.Тактовые импульсы подаются навход счетчика 8 и начинается вычисление БПФ по строкам (столбцам).На первом выходе устройства у формируются.адреса строк (столбцов),а на выходе у - адреса операндов,выбираемых иэ памяти 2.Формирование адресов при реализации одномерного БПФ соответствуетформированию адресов при вычисленииБПФ по одному столбцу (строке),Предлагаемое .Устройство позволяет вычислять как одномерное, таки двумерное БПФ, значительно сократить время вычисления и аппаратурныезатраты при реализации двумерного БПФ,формула изобретенияУстройство для реализации быстрого преобразования Фурье, содержащее оперативную память, постоянную память, арифметический блок и блок управления, причем первый, второйи третий выходы блока управлениясоединены, соответственно,со входамипостоянной памяти, арифметическогоблока и оперативной памяти, перваяи вторая группы входов арифметического блока соединены, соответственно,с группами выходов постоянной и оперативной памяти, о т л и ч а ю щ ее с я тем, что, с целью увеличениябыстродействия и уменьшения аппаратурных затрат, блок управления со-держит регистр, первую и вторуюгруппы элементов И, первый и второйкоммутаторы, узел задания режима,первый и второй счетчики, сумматор,регистр хранения адреса и узел обращения кода адреса, причем первыйи второй выходы узла задания режима.соединены с первыми входами элементов И,соответственно, первой и второйгрупп, вторые входы которых подключены к первому выходу регистра, второй 26и третий выходы которого подключены,соответственно, к первым входам сумматора и узла задания режима, третийи четвертый выходы которого подключены,соответственно, ко входам первогои второго счетчиков, первые выходыкоторых соединены, соответственно, совторым и третьим входами узла заданиярежима, пятый выход кторого подключен ко входу регистра, вторыевыходы первого и второго счетчиковсоединены с первыми входами,соответственно,первого и второго коммутаторов, вторые входы которых соединеныс выходами элементов И,соответственно,первой и второй групп, выходы коммутаторов являются выходами устройства,выход сумматора соединен через узелобращения кода адреса с выходомустройства н через регистр хранения адреса со своим вторым входом.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРВ 46735 б, кл. 6 Об Г 15/34, 1975.2. Аврорин А.В. и др. Системадля цифрового восстановления голографических изображений в реальномвремени эксперимента, "Автометрняф,1978, Р 4 (прототип),809198 Заказ 413/60 Тираж 75 б Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-ЗЬ, Уаушская наб., д. 4/5