Пристрій для виконання швидкого перетворення фур’є

Изобретение относится к вычислительной технике и может быть использовано для цифровой обработки сигналов, спектрального и корреляционного анализа различных процессов. Известно устройство для быстрого преобразования Фурье, которое содержит умножитель, регистр числа, регистр коэффициента, два регистра результата, сумматор - вычитатель, четыре мультиплексора, два регистра адреса, блок памяти весовых коэффициентов, блок памяти встроенных функций, блок регистровой памяти, регистры старших и младших разрядов операнда, блок сдвига, шифратор порядка, регистр порядка, семь мультиплексоров, три трехстабильных ключа, блок сравнения, синхронизатор[Каневский Ю.С. и др. Устройство для быстрого преобразования Фурье. Авт.св. № 1524066]. Недостатком данного устройства является низкое быстродействие и большие аппаратурные затраты, так как вычисления производятся в формате плавающей запятой при использовании всего одного умножителя. Более высокое быстродействие имеет устройство для вычисления коэффициентов Фурье, содержащее четыре блока умножения, шесть суммирующих блоков, шесть входных регистров, два промежуточных регистра, четыре блока сдвигов и блок управления [Волошин Р.Д., Востриковец Н.С., Коротич Н.И. Устройство для вычисления коэффициентов Фурье. Авт.св. СССР № 736112, кл. G 06 F 15/332]. Недостатком данного устройства является малая точность при использовании его в процессорах быстрого преобразования Фурье, обрабатывающих массивы двоичных чисел с фиксированной запятой. Низкая точность результатов связана с возникновением при сдвиге операндов и быстром накоплении систематических ошибок округления, нарушающих четность и нечетность соответственно действительной и мнимой частей спектров. Известен процессор быстрого преобразования Фурье, содержащей М/2 коммутаторов, причем выход і-го (і = 1,3,5....) арифметического блока соединен с выходом К-го (К = і + 1/2) коммутатора, выход которого подключен к- входу 0+1)-го арифметического блока, выход т-го (т = 2,4,6...) арифметического блока соединен со вторым 1-го(I = т/2)умножителя, выход которого соединен со входом (m + 1)-гo арифметического блока, причем управляющие входы М/2 коммутаторов соединены с выходом счетчика, при этом в 1-м (і = 1, М) арифметического блока второй выход входного коммутатора подключен ко вторым входам сумматора и вычитателя [Бахтиаров Г.Д., Орлов Ю.Н. Процессор быстрого преобразования Фурье. Авт.св. СССР № 928362, кл. G 06 F 15/332]. Недостаток данного процессора - большие аппаратурные затраты. Наиболее близким к изобретению является устройство для выполнения быстрого преобразования Фурье, содержащее блок оперативной памяти, арифметический блок, блок хранения весовых коэффициентов, счетчик адресов операнда дешифратор номера итерации, формирователь адресов весовых коэффициентов, счетчик номера итерации, причем первый вход блока оперативной памяти является входом устройства, а первый выход блока оперативной памяти соединен с первым входом арифметического блока, первый выход которого соединен со вторым входом блока оперативной памяти, первый вход счетчика адресов операндов соединен со вторым выходом блока оперативной памяти, первый выход счетчиков адресов операндов соединен с третьим входом блока оперативной памяти и первым входом формирователя адресов весовых коэффициентов, второй вход которого соединен с выходом дешифратора номера итерации и вторым входом счетчика адресов операндов, второй выход которого соединен с входом счетчика номера итерации, выход которого соединен со входом дешифратора номера итерации, выход формирователя адресов весовых коэффициентов соединен с первым входом блока хранения весовых коэффициентов, выход которого соединен со вторым входом арифметического блока, второй выход которого соединен со вторым входом блока хранения весовых коэффициентов. [Немшиков H.H., Титов М.А. Устройство для выполнения быстрого преобразования Фурье. Авт.св. СССР № 877555, кл. G 06 F 15/332 (прототип)]. Недостатком известного устройства является низкое быстродействие. Это связано с тем, что обработку операндов по базовой операции алгоритма БПФ выполняет один арифметический блок. В основу изобретения поставлена задача повышения быстродействия при реализации алгоритма БПФ, для чего устройство для выполнения быстрого преобразования Фурье совершенствуется путем обеспечения условий одновременной реализации двух или четырех базовых операций алгоритма за счет введения в устройство дополнительных арифметических блоков. Для решения этой задачи в устройство для выполнения быстрого преобразования Фурье, содержащее блок оперативной памяти, блок хранения весовых коэффициентов, формирователь адреса операндов, формирователь адреса весовых коэффициентов, арифметический блок и счетчик номера итерации, причем второй информационный вход и первый выход блока оперативной памяти соединены соответственно с выходом и первым входом первого арифметического блока, второй вход которого соединен с первым выходом блока хранения весовых коэффициентов, управляющий вход которого соединен с выходом формирователя адреса весовых коэффициентов, первый выход формирователя адреса операндов соединен со вторым управляющим входом блока, оперативной памяти, дополнительно введены второй арифметический блок, блок суммирования операндов, блок управления сдвигами, счетчик с обратным переносом и блок управления операциями, причем информационным входом и выходом запуска устройства является соответственно информационный вход блока суммирования операндов и первый вход блока управления операциями, десятый выход которого является выходом признака окончания работы устройства, первый и девятый выходы блока управления операциями соединены со входами счетчика номера итерации, выход которого соединен со вторым входом блока управления операциями, второй, третий и пятый выходы которого соединены соответственно с первым, вторым и третьим управляющими входами блока суммирования операндов, второй и первый выходы которого соединены соответственно с первым управляющим входом блока управления сдвигами и первым информационным входом блока оперативной памяти, первый управляющий вход которого соединен с выходом счетчика с обратным переносом, вход которого соединен с четвертым выходом блока управления операциями, шестой, седьмой и восьмой выходы которого соединены соответственно со вторым, третьим и четвертым входами формирователей адреса операндов и весовых коэффициентов, первые входы которых подключены ко второму выходу блока управления операциями, восьмой выход которого подключен ко второму управляющему входу блока управления сдвигами, выход которого соединен с третьими входами первого и второго арифметических блоков, второй выход формирователя адреса операндов соединен с третьим управляющим входом блока оперативной памяти, второй и первый входы второго арифметического блока соединены соответственно с первым выходом блока хранения весовых коэффициентов и вторым выходом блока оперативной памяти, третий информационный вход которого соединен с выходом второго арифметического блока, первый и второй информационные входы блока управления сдвигами соединены с выходами соответственно первого и второго арифметических блоков. Соответственный анализ с прототипом показывает, что заявляемое устройство для выполнения быстрого преобразования Фурье отличается тем, что для блоков оперативной памяти и хранения весовых коэффициентов заданного объема подключается параллельно функционирующих два или четыре арифметических блока, обрабатывающих двоичные числа в формате фиксированной запятой, что обеспечивает высокое быстродействие обработки операндов с достаточной для практического использования точностью результатов обработки входных данных. Таким образом, заявляемое устройство соответствует критерию изобретения "новизна". Сравнение заявляемого решения не только с прототипом, но и с другими техническими решениями в данной области техники, не позволило выявить в них признаки, отличающие заявляемое решение от прототипа, что позволяет сделать вывод о соответствии критерию "существенные отличия". На фиг.1 и 2 представлены функциональные схемы устройства для выполнения быстрого преобразования Фурье, содержащие соответственно два и четыре арифметических блока; на фиг.3 направленный граф алгоритме ВПФ с разрежением по времени; не фиг.4 - временная диаграмма работы устройства; на фиг.5 - графики экспериментальной оценки точности реализации алгоритма ВПФ в формате двоичных числе С фиксированной запятой; на фиг.6 - график значений весовых коэффициентов,- на фиг.7 график значений округлений. Устройство (фиг.1 и 2) содержит: блок суммирования операндов 1, счетчик с обратным переносом 2, блок оперативной памяти 3, блок управления сдвигами 4, арифметические блоки 5, 5-1; 5-2; 5-3; 5-4: соответственно первый, второй, третий и четвертый арифметические блоки, блок хранения весовых коэффициентов 6, формирователь адреса операндов 7, формирователь адреса весовых коэффициентов 8, блок управления операциями 9, счетчик номера итерации 10. Информационным входом устройства (фиг.1) является информационный вход блока суммирования операндов 1, входом запуска и выходом признака окончания работы устройства является соответственно первый вход и десятый выход блока управления операциями 9. Первый и второй выходы блока суммирования операндов 1 соединены соответственно с первым информационным входом блока оперативной памяти 3 и первым информационным входом блока управления сдвигами 4, второй и третий информационные входы которого соединены с выходами соответственно первого и второго арифметических блоков 5, а также подключены ко второму и третьему информационным входам блока оперативной памяти 3, первый и второй выходы которого соединены с первыми информационными входами соответственно первого и второго арифметических блоков 5, вторые информационные входы которых соединены с выходом блока хранения весовых коэффициентов 6, третьи информационные входы арифметических блоков 5 подключены к выходу блока управления сдвигами 4. Первый и девятый выходы блока управления операциями 9 соединены со входами счетчика номера итерации 10, выход которого соединен со вторым входом блока управления операциями 9, второй, шестой, седьмой и восьмой выходы которого соединены соответственно с первым, вторым, третьим и четвертым входами формирователя адреса операндов 8 и формирователя адреса весовых коэффициентов 8, выход которого соединен с адресным входом блока хранения весовых коэффициентов 6. Первый, второй и третий управляющие входы блока суммирования операндов 1 подключены ко второму, третьему и пятому выходам блока управления операциями 9, четвертый выход которого соединен со входом счетчика с обратным переносом 2, выход которого соединен с первым адресным входом блока оперативной памяти 3, второй и третий адресные входы которого соединены соответственно с первым и вторым выходами формирователя адреса операндов 7 Устройство для выполнения быстрого преобразователя Фурье, содержащие четыре арифметических блока 5, изображено на фиг.2 и содержит все блоки и связи между ними, как это показано на фиг.1 и описано ниже. Дополнительные связи устройства, представленного на фиг.2, следующие. Первые информационные входы третьего и четвертого арифметических блоков 5-2, 5-4 соединены соответственно с третьим и четвертым выходами блока оперативной памяти 3, четвертый и пятый входы которого соединены с выходами соответственно третьего и четвертого арифметических блоков 5 и подключены соответственно к четвертому и пятому информационным входам блока управления сдвигами 4, выход которого подключен к третьим информационным входам третьего и четвертого арифметических блоков 5, вторые информационные входы которых подключены ко второму выходу блока 6 хранения весовых коэффициентов. Устройство для выполнения быстрого преобразования Фурье ВПФ вычисляет дискретное преобразование Фурье по алгоритму с разрешением по времени и двоично-инверсным порядком следования отсчетов на входе. В настоящее время разработано большое количество вариантов алгоритма БПФ, направленные графы которых приведены в книге Рабинер Л., Гоулц Б. Теория и применение цифровой обработки сигналов. М., Мир, 1978. Направленный граф алгоритма БПФ, реализуемого устройства, приведен на фиг.3. Устройство для выполнения быстрого преобразования Фурье имеет два (фиг.1) или четыре (фиг.2) параллельно работающих арифметических блоков 5, которые преобразовывают операнды по базовой операции: где N – 2n - длина массива операндов; і = 1,2.....n - номер очередного этапа преобразования операндов; Р = 0, (N/2-1) - номер весового (поворачивающего) коэффициента. Таблица весовых коэффициентов W NP хранится в блоке памяти 6 и обеспечивает реализацию алгоритма БПФ массивов операндов длиной N£Nm; Nm - верхнее, значение длины массивов. Введем обозначения: Высокое быстродействие преобразования операндов по базовой операции (3) достигается в формате двоичных чисел с фиксированной запятой. Примером высокопроизводительного арифметического блока 5 может быть устройство для вычисления преобразования Фурье по авт.св. СССР № 736112,1980. Для обеспечения высокой точности в указанном устройстве по авт.св. № 736112 следует перед выходом чисел ai(k); ai(l); bi(k); bi(l) округлять таким образом, чтобы исключить возникновение и накопление систематических ошибок. Предлагаемое устройство для выполнения быстрого преобразования Фурье может содержать два (фиг.1) или четыре (фиг.2) параллельно функционирующих арифметических блоков 5, реализующих базовую операцию (3) для различных операндов А(k; A(I) и поворачивании коэффициентов W NP = = (Up-j*Vp). Два арифметических блока устройства по функциональной схеме фиг.1 обрабатывают одновременно две пары операндов для которых угол поворота и весовых коэффициентах различаются на 90°. Используя формулы приведения для тригонометрических функций, базовая операция БПФ (3) для операндов (А1; А2) и (А1; A4) с весовыми коэффициентами соответственно (W NP; W NP+N/4) и (W Np+N/4 = -(Vp +j *Up) принимает вид: Арифметические блоки 5, реализующие соотношения соответственно (4а) и (4б), имеют одинаковое устройство. Обеспечение различий алгоритмов (4а) и (4б) осуществляется различием подключения входов и выходов блоков, как показано на фиг.4а и фиг.4б соответственно. Так как номер весовой функции р =0,1,2.....(N/4-1) соответствует углу поворота 0° £j(р) 0,5, а также при D= 0,5 при условии округления в сторону нечетных чисел. Экспериментальные исследования точности реализации алгоритма БПФ на ЭВМ типа ДЭК-3, ЕС-1840 на реальных и модельных сигналах показали, что при N £4096 отсчетов d выг < 0,05% < < d вх (оцифрование с помощью 12-14 разрядных АЦП). Результаты экспериментальных исследований приведены на фиг.7 при различных методах округления промежуточных результатов. Экспериментальные исследования показывают, что 16-ти разрядные процессоры и специальные платы БПФ позволят с высокой скоростью вычислять преобразования Фурье при обработке сигналов различной физической природы. При оценке точности вычисления преобразования Фурье округление операндов в базовых операциях БПФ операнды масштабировались следующим образом; операнды масштабируются на входе базовой операции с округлением методом усечения; операнды масштабируются на выходе базовой операции с округлением методом усечения; операнды масштабируются на выходе базовой операции с округлением в сторону нечетных чисел, как описано выше. Этот метод обеспечивает высокую точность целочисленной реализации алгоритма БПФ. Быстродействие устройства определяется временем вычисления преобразования Фурье. Положительный эффект от использования предлагаемого устройства для выполнения быстрого преобразования Фурье заключается в том, что одновременно производится обработка двух или четырех пар операндов по базовой операции алгоритма, а в известном устройстве только одна пара операндов. Использование описанного выше метода округления промежуточного результата в сторону нечетных чисел позволяет вычислять преобразования Фурье в формате чисел с фиксированной запятой и точностью, которая во много раз выше точности оцифрования входной информации, если разрядность процессора всего на 2-4 единицы выше разрядности АЦП. Таким образом, введение блока суммирования операндов, блока управления сдвигами и увеличение количества арифметических блоков повышает производительность устройства в два-четыре раза с одновременным обеспечением условий высокоточной реализации алгоритма БПФ в формате чисел с фиксированной запятой.