Устройство для выполнения быстрого преобразования фурье Советский патент 1980 года по МПК G06F17/10 G06F17/14 

1

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

Известно устройство для выполнения быстрого преобразования Фурье, содержащее регистры, сдвигатели и сумматоры 1 .

Наиболее близким техническим ре- О шением к предлагаемому изобретению является устройство для выполнения быстрого преобразования Фурье (БП1), содержащее четыре регистра, два блока сдвига, три сумматора, блок 15 постоянной памяти (ПЗУ), блок управления 2} .

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

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

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

подключены к первым входам соответотвенно первого и второго сумматоров, выходы третьего и четвертого регистров - соответственно к первому и второму входам третьего сумматора, выходы первого и второго блоков сдвига - ко вторым входам соответственно второго и первого сумматоров, выходы первого ,второго и третьего сумматоров подключены ко вуопам соответственно первого, второго и третьего регистров, выходы разрядов первого и второго регистров подключены ко входам разрядов соответственно первого и второго блоков сдвига, выходы блока памяти подключены ко входам разрядов четвертого регистра, выход блока управления подключен к управляющим входам всех регистров и блоков сдвига, а также к адресному входу блока памяти, содержит арифметико-логический 6.IJOK, состоящий из регистра сдвига, двух групп сумматоров по модулю два, группы элементов И и выходного элемента И, причем выход импульсов отсчета числа итераций блока управления под-, ключей к управлякяцему входу регистра сдвига, выходы разрядов которого подключены к первым входам соответствующих элементов И группы вторые и третьи |входы которых подключены к выходам соответствующих сумматоров .jno модулю два первой и второй групп, а выходы - к соответствующим входам выходного ;Элемента И, выход которого подключ К управляющему входу блока управле ния, первые входы сумматоров по мо дулю два первой группы подключены выходу знакового, а вторые входы выходам соответствующих информацио ных разрядов первого регистра, пер вые входы сумматоров по модулю два второй группы подключены к выходу знакового, а вторые входы - к выхо дам соответствующих информационных разрядов второго регистра. На фиг. 1 представлена функциональная схема устройства; на фиг.2 функциональная схема арифметико-ло гического блока. Устройство содержит регистры 1блрки 5,6 сдвига, сумматоры 7-9, ёлок 10 памяти (ПЗУ), блок 11 упра ления, арифметико-логический блок состоящий из сумматоров по модулю первой-), и второй-2 г групп, эле ментов Зл2. И, выходного элемента 4 И, регистра сдвига. Блок 11 управления представляет из себя счетчик, имеющий разрядность, соответствующую разрядности входного слова устройства для выполнения БПФ.и состоящий из двух частей, в дальнейшем именуемых счетчиками итераций и шагов итераций. Вычисления в предлагаемом устро стве осуществляются в соответствии с выражениями . А А + W В; В А - , где . W ev-p (-Затт/Ю) . j VT 1 N - число дискрет входного сигнал А и В - комплексные числа, которые определяются на предьщущем шаге вычислений . : . Вычисление значений X, Y осуществл ся в соответствии со следующими ре куррентными соотношениями 5; 1. .V Ь. Э.,е;-СА;.Л;, «А.-8-.дп(вД ,b;.arct(i) (,2,..., П 1 номер итерации, п - разрядность входного слова. Значения X, Y, в фиксируются в регистрах 1, 2 и 3. В блоке 10 памяти хранятся константы д . Блоки 5, б сдвига служат для умножения на При обработке реального массива входных данных может иметь место следующее соотношение 1 Структура арифметико- логического блока (АЛУ) соответствует выражеп---Ко)® 1 {Л1Чо)9П)1 Y(0), Х(0) - знаковые разряды регистров 1 и 2, Gpng вспомогательная функция : / п - Q- , I 1о n-q-v, g 1, 2, . . . , п Последняя реализована при помощи регистра сдвига с начальной установкой RO и текущим содержимым RtV-r -В.ойЧ номер итерации. Устройство работает следующим образом. По команде из блока управления осуществляется занесение в регистр 1 вещественной, в регистр 2 мнимой части числа Вив регистр 3 числа 9- 2JTCJN . При этом счетчик, блока 11 управления находится в На вход счетчика состоянии в блоке 11 управления и управляющие входы регистров 1-4 поступает одна и та же последовательность тактовых импульсов, формируемая в блоке 11 управления. На управляющий вход регистра сдвига АЛУ поступают импульсы со старшего разряда счетчика шагов итераций. Код снимаемый со счетчика итераций является кодом управления для блоков 5,6 сдвига и адресом констант для ПЗУ. Далее устройство начинает работать в соответствии с выражениями (2). Его работа заканчивается через п итераций. Если после итерации m,n выполняется условие (3), то выходной сигнал АЛУ прерывает итерационный процесс, разрешая-обнуление счетчика блока 11 управления. После окончания итерационного процесса в регистры 1 и 2 производится запись новых входных данных и процедура повторяется. Необходимо отметить, что выражение (4) может быть положено в основу реализации АЛУ как для последовательного, так и для параллельного устройства для выполнения БПФ, реализующего алгоритм (2),

Использование АЛУ позволяет повысить быстродействие устройства для выполнения БПФ приблизительно р два раза.

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

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

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

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

5 выходам соответствующ.их информационных разрядов втотэого регистра.

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

1.Патент Великобритании

№ 1350904, кл. G 06 F 15/34, 1969.

0

2.Despain A.M. Fourier Transform Computers Using CORDJC Jterationsi JEEE Trans on Computers, v.c-23, N10, 1974.

q X ,У

/

f V-,

752348

:/