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

 

Изобретение относится к радиотехнике и вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов. Цель изобретения - повышение быстродействия . Поставленная цель достигается за счет того, что устройство содержит два регистра сдвига, два счетчика , блок управления, два сумматора, два блока сдвига, элемент И, два блока сравнения, блок счетчиков, два блока элементов И, элемент ИЛИ, блок регистров. Причем блок управления содержит шесть элементов НЕ, шестнадцать элементов И, три RS-триггера, десять элементов ИЛИ, дешифратор и генератор тактовых импульсов. Устройство формирует на каждом шаге алгоритма тблько те адреса., которые нужны для вычисления искомых отсчетов дискретного спектра сигнала. Благодаря этому процессор не выполняет операции с ненужньми отсчетами. 7 ип. КЛ с

СО1ОЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

Н9> @U <1Н

А1 (594G 06 F 15 332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

t сХ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (2 l ) 3809289/24-24 (22) 06,08.84 (46) 23.12.86. Бвл. У 47 (71) Кировский политехнический институт (72) В.П. Медведев и В.У. Сысоев (53) 681.32 (088.8) (56) Ярославский Л.П. Усеченные алгоритмы быстрых преобразований ФурьеУолша. - Радиотехника, 1977, 11 10.

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

У 922763, кл. С 06 F 15/332, 1980. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

АДРЕСОВ ПРОЦЕССОРА УСЕЧЕННОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к радиотехнике и вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов ° Цель изобретения — повышение быстродействия. Поставленная цель достигается за счет того, что устройство содержит два регистра сдвига, два счетчика, блок управления, два сумматора, два блока сдвига, элемент И, два блока сравнения, блок счетчиков, два блока элементов И, элемент ИЛИ, блок регистров. Причем блок управления содержит шесть элементов НЕ, шестнадцать элементов И, три RS-триггера, десять элементов ИЛИ, дешифратор и генератор тактовых импульсов. Устройство формирует на каждом шаге алгоритма только те адреса., которые нужны для вычисления искомых отсчетов дискретного спектра сигнала. Благодаря этому процессор не выполняет операции с ненужными отсчетами. 2 ил.

1278883 2 где

1 =0,2 -I.

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

Целью изобретения является повышение быстродейс вия.

Для пояснения сущности изобретения сравним обычный и усеченный алгоритмы БПФ. В случае, когда число отсчетов сигнала равно степени двух, т.е. N 2, дискретный спектр сигнала может быть вычислен sa r шагов по рекуррентным формулам. х „(р)х; (p)+x (р+2 ) 47"

l х;„(р+2 ) =х (р) -х (р+2 ) И где 1 — номер шага

X;,X, — входные и выходные данные для II-го шага;

1!

p p+g. — номера отсчетов в массивах входных и выходных данных;

Ю вЂ” тригонометрический коэффициент, причем ехр (2ii l/N) В приведенных формулах

1 -1 р=ш+Х. 2 и Е=ш.2, Так как периодическая дискретная функция k с периодом N достаточно сформировать массив тригонометрических коэффициентов и отсчетов. При х этом И соответствует k-му отсчету в массиве.

На фиг. приведен пример направленной граф-схемы алгоритма БПФ для случая И 2 . На этой схеме вершины

Э графа (точки) соответствуют отсчетам данных. На каждом шаге алгоритма линии без стрелок соответствуют простой передаче данных, линии со стрелками соответствуют передаче с предварительным умножением на тригонометрический коэффициент. Знак "+" или "-" возле вершины графа указывает ва операцию, с помощью которой получен соответствующий отсчет. Ниже граф-схемы алгоритма БПФ указаны для каждого шага i значения, которые принимают переменные m и 1. В рассматриваемом примере для определения дискретного спектра сигнала требуется выполнить 12 операций комплексного умножения.

35.

В усеченном алгоритме БПФ требуется найти М (М < J) отсчетов дискретного спектра сигнала с номерами

b,, b,,b где b — целые числа из интервала (О, N †). При этом достаточно на каждом шаге преобразования определить только те отсчеты, которые требуются на следующем шаге.

На фиг. I зачернены вершины графсхемы алгоритма ЕПФ, соответствующие отсчетам данных, которые необходимо определить на каждом шаге для вычисления отсчетов дискретного спектра сигнала с номерами 3 и 7. Таким образом, зачерненные вершины графа образуют граф-схему усеченного алгоритма БПФ для случая, когда М = 2, b

3, = 7 °

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

m = (Ь,)moo 2, где j = 1, 2 ... М.

В рассматриваемом примере для вычисления искомых отсчетов спектра требуется выполнить 8 операций комплексного умножения, т.е. на одну треть меньше, чем при использовании обычного алгоритма БПФ. Выигрыш достигается тем, что данное устройство для формирования адресов процессора усеченного БПФ формирует на каждом шаге алгоритма только те адреса, которые нужны для вычисления искомых отсчетов дискретного спектра сигнала. Благодаря этому процессор не выполняет операции с ненужными отсчетами.

На. фиг. 1 представлен алгоритм усеченного БПФ; на фиг. 2 — блок-схема устройства; на фиг. 3 — блок-схема блока регистров, блока элементов

И, блока счетчиков и блока фиксации нуля; на фиг. 4 — алгоритмы работы устройства; на фиг. 5 — временные диаграммы; на фиг, 6 — схема блока управления; на фиг. 7 — схема логического узла.

Устройство (фиг. 2) содержит регистры 1 и 2 сдвига, счетчики 3 и 4, сдвигатели 5 и 6, элемент И 7, сумматоры 8 и 9 блоки 10 и 11 сравнения, блок l 2 регистров,,блок 13 элементов И, блок 14 счетчиков, блок 15 фиксации нуля и блок 16 управления, выходы 17-22 блока управления, входы

23-26 блока управления, выход 27

1278883

=2, Ь,= 3, Ь = 7. На диаграмме приведены сигналы СС, формируемые внутри блока 16 управления (БУ.), сигналы РI Р2, PÇ и Р4 Hà его входах и сигналы Уl, У2, УЗ, У4. У5, УЬ на

его выходах. Приведены также сигналы на прямых выходах разрядов Ргl, Рг2, Счl, Сч2. В соответствии с рассматриваемым пруером Ргl и Рг2

10 трехразрядные, а Сч1 и Сч2 — двухразрядные.

Устройство для формирования адресов процессора усеченного БПФ работает следующим образом.

l5 После запуска БУ он формирует сигнал Уl, который устанавливает Рг) и Рг2 в режим параллельной записи информации, и сигнал У5, который записывает в Prl и Рг2 код 001. При

20 поступлении следующего импульса сигнала СС БУ формирует сигналы У2, УЗ и У5. Первый из них устанавливает

Сч2 и Счl, а также счетчики 31 в режим параллельной записи информации.

Сигнал УЗ обнуляет Счl и записывает в каждый счетчик 31 код, который получается в результате поразрядного логического умножения кода, записанного в одном из регистров блока 30

30 на код, записанный в старших r-1 разрядах Рг2. При этом в счетчиках

31 записываются коды (Ь )той2

35 где Ь вЂ” коды записанные в регистУ рах 30.

В рассматриваемом примере в счет чики 31 при этом записывается код

00. Сигнал У4 обнуляет Сч2. Так как

40 в счетчиках 31 записан О, на выходе блока 15 фиксации нуля появляется логическая единица (Р4 = 1). При этом в алгоритме выполняется переход от вершины 4 к вершине 7, что

45 соответствует формированию Уб при поступлении следующего импульса сигции 1

Сч Я вЂ” означает запись разряд

Сч;

11(Рг) — означает сдвиг содержимого

Рг влево на один разряд;

Pl, Р2, PÇ, Р4 — сигналы на входах

23-26 блока 16 управления.

У1, У2, УЗ, У4, У5, Уб — сигналы на выходах.17-22 блока 16 управления.

Для пояснения работы устройства для формирования адресов процессора усеченного БПФ воспользуемая также временными диаграммами, приведенными на фиг. 4. Временные диаграммы построены для случая, когда N =8, М=

55 адреса коэффициента, выходы 28 и 29 адреса соответственно первого и второго операндов .

На фиг. 3 приведены схемы блока

12 регистров, блока 13 элементов И, блока 14 счетчиков и блока 15 фиксации нуля. Блок 12 регистров содержит регистры 30, число которых не меньше числа искомых отсчетов дискретного спектра сигнала M. Блок 14 счетчиков содержит соответствующее число счетчиков 31. Блок 13 элементов И содержит И групп элементов И, причем число элементов И 32 в каждой группе равно разрядности регистров 30. Блок фиксации нуля включает блок элементов И, состоящий из элементов И 33, число которых равно числу счетчиков 31, и элемент ИЛИ 34.

Блок управления (фиг. 6) содержит дешифратор 35, триггеры 36-38, элементы И 39-46, элементы ИЛИ 47-52, элементы НЕ 53-55, резистор 56, конденсатор 57, логический узел 58, генератор 59 тактовых импульсов.

Логический узел (фиг. 7) содержит элементы НЕ 60-62, элементы И 63-65 с выходом 66, элементы И 67-71, элементы ИЛИ 72-75.

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

Рг) — первый регистр 1 сдвига;

Рг2 — второй регистр 2 сдвига;

Счl — первый счетчик 3

Сч2 — второй счетчик 4;

БлСч — блок 14 счетчиков;

Смl — первый сумматор 8;

См2 — второй сумматор 9;

СхСд — второй сдвигатель 6; обозначает запись информанала СС. Этот сигнал информирует. процессор о том, что на выходе См2 находится адрес Al (первого операнда, на выходах Смl — адрес А2 второго операнда и на выходах СхСд— адрес АЗ тригонометрического коэффи-. циента).

Ъ

В рассматриваемом примере в этом случае Al = 000, A2 = 001 и А3 =000.

Так как в Сч2 и записан О, а на инверсных выходах всех разрядов Сч2, кроме младшего, находится код 11, на выходе блока 11 сравнения находится логический нуль (РЗ = О). Поэтому в алгоритме выполняется переход от вершины 8 к вершине 9. Так как сигнал У2 при этом не вырабатывается, сигнал У4 добавляет к содержимому

Сч2 единицу. После этого по сигналу

Уб на выходах См!, См2 и СхСд считываются адреса Al =010, A2=0ll и А3=

=000. В следующем цикле считываются коды !00, 101, 000 и наконец, коды

110, ill и 000. При этом на выходе .блока 11 сравнения появляется логическая единица, так как с Сч2 записан код ll. Поскольку на выходе блока 10 сравнения также установлена логическая елиница (Р2 1), выполняется переход к вершине 10 блок-схемы алгоритма. Формируемый при этом сигнал У5 сдвигает содержимое Ргl и Рг2 влево на один разряд. В младший разряд Ргl записывается логический нуль, а Рг2 — логическая единица. Так как в Ргl записан не нуль, сигнал Рг1=0.

Поэтому выполняется переход к верши не 3 алгоритма. Производится новая запись кодов в счетчики 31. В рассматриваемом примере записывается код 01. При этом на выходе блока 15 фиксации нуля появляется логический нуль (Р4 О). Так как на выходе блока 10 сравнения тоже нуль (02=0), формируется сигнал УЗ, который добавляет 1 к содержимому Счl и вычитает

1 из содержимого счетчиков 31; В результате счетчики 31 обнуляются и появляется сигнал Р4 — 1. Поэтому выполняется переход к вершине 7 алгоритма и считывается адрес AI

= 001, А2 = 011 и АЗ = 010. В следующем цикле содержимое Сч2 увеличива, ется на единицу и считываются адреса,А! 101, А2 = 111 и АЗ = 010.

Затем проходит очередной сдвиг кодов в Ргl и Рг2 и новая запись в счетчик 31, На этот раз в них записывается код 11. Так как Р4=0 происходит обращение к вершине б алгоритма. После трех обращений счетчик

31 обнуляется, а в Сч! появляется код 11 ° При появлении следующего импульса сигнала СС БУ формирует Уб, и с выходов CNI, См2,- СхСд считыва— ются коды 101 111, 011. Затем происходит очередной сдвиг кодов в Рг1 и Рг2. Так как Pr! при этом обнуляется, БУ по сигналу Р4 с выхода элемента И 7 прекращает работу устрой78883 6 ства для формирования адресов процессора усеченного БПФ.

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

Устройство для формирования адресов процессора усеченного быстрого преобразования Фурье, содержащее первый регистр сдвига, первый и второй счетчики, блок управления, первый выход которого подключен к установочным входам первого и второго счетчиков, счетные входы которых подключены соответственно к второму и третьему выходам блока управления, . четвертый и пятый выходы которого подключены соответственно к тактовому входу и входу управления направлением сдвига первого регистра сдвига, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены первый и второй сумматоры, второй регистр сдвига, первый и вто25 рой сдвигатели, элемент И, первый и второй блоки сравнения, блок счетчиков, первый и второй блоки элементов И, элемент ИЛИ и блок регистров, i-й выход(.=l,r, r- разрядность) которого подключен к i-му входу »»epscro блока элементов И, -й выход которого подключен к i-му, информационному входу блока счетчиков, i-й информационный выход которого подключен к i-му входу второго блока эле35 ментов И, i é выход которого подключен к i-му входу элемента ИЛИ, выход которого подключен к первому входу блока управления, первый, второй, четвертый и пятый выходы которого подключены соответственно к установочному и счетному входам блока счетчиков и тактовому и установоч. ному входам второго регистра сдвига,,}-й (J =?,r ) разряд прямого выхода

- которого подключен к (j+r-1)-му входу первого блока элементов И и (!-1)-му входу первого блока сравнения, выход которого подключен к второму входу блока управления, тре50 тий вход которого подключен к выходу второго блока сравнения ()-1}-й вход которого подключен к j-му разряду инверсного выхода второго регистра сдвига, i-й разряд прямого

55 выхода первого регистра сдвига подключен к i-му входу первого сум матора, 1-му входу управления сдвигом первого сдвигателя, i-й выход

12788 которого подключен к i-му входу второго сумматора, i-й выход которого является i-м адресным выходом первого операнда устройства и подключен к (i+r)-му входу первого сумма- 5 тора, i-й выход которого является

i-м адресным выходом второго операнда устройства, выходом адреса коэффициента которого является i-й выход второго сдвигателя (J-1)-й вход управления сдвигом которого подключен к (g-1)-му разряду прямого выхода первого регистра сдвига, i-й разряд инверсного выхода которого подключен к i-му входу элемента И, t5 выход которого подключен к четвертому входу блока управления, (J-1)-й разряд выхода первого счетчика подключен к ()+г-2)-му входу первого блока сравнения, (-1)-му информационному входу второго сдвигателя и (j+r-1)-му входу второго суиматора, (J-1)-й разряд выхода второго счетчика подключен к (+г-2)-му вхо25 ду второго блока сравнения и (j-1)му информационному входу первого сдвигателя,шестой выход блока управления является выходом синхронизации устройства, блок управления со- держит десять элементов ИЛИ, шесть элементов НЕ, шестнадцать элементов И, три BS-триггера, дешифратор и генератор тактовых импульсов, выход которого подключен к первым входам элементов И с первого по шестой, к входу первого элемента НЕ, выход которого подключен к входам синхронизации первого, второго и третьего

RS-триггеров, выходы которых подключены Соответственно к первому, второму и третьему входам дешифратора, первый и второй выходы которого подключены соответственно к первому и второму входам первого элемента ИЛИ, выход которого подключен к первым входам второго и третьего элементов

ИЛИ, выходы которых подключены соответственно к В-входу первого RS-триггера и первому входу седьмого элемента И, выход которого подключен к Sвходу второго RS-триггера, третий выход дешифратора подключен к второму входу первого элемента И,первому входу четвертого элемента ИЛИ и первому входу пятого элемента ИЛИ, выход которого подключен к S-входу первого

RS-триггера, четвертый выход дешифратора подключен к второму входу эле83 8 мента И, первым входам шестого и седьмого элементов ИЛИ, первым входом восьмого и десятого элементов И, выходы которых подключены .соответственно к S-входу третьего RS-триггера, второму входу второго элемента ИЛИ и первому входу восьмого элемента ИЛИ, выход которого подключен к первому входу девятого элемента

ИЛИ, выход которого подключен к Rвходу второго BS-триггера, пятый выход дешифратора подключен к второму входу третьего элемента И и пер BblM входам одиннадцатого, двенадцатого и тринадцатого элементов И, выходы которых подключены соответственно к второму и третьему входам восьмого элемента ИЛИ и второму входу пятого элемента ИЛИ, шестой выход дешифратора подключен к второму входу седьмого элемента ИЛИ и первым входам четырнадцатого и пятнадцатого элементов И, выходы которых подключены соответственно к.третьему входу второго элемента ИЛИ и четвертому входу восьмого элемента ИЛИ, седьмой выход дешифратора подключен к второму входу четвертого элемента ИЛИ, первому входу десятого элемента ИЛИ и первому входу шестнадцатого элемента И, выход которого подключен к второму входу третьего элемента ИЛИ, третий вход которого объединен с вторым входом шестого элемента ИЛИ и подключен к восьмому выходу дешифратора, вторые входы седьмого и восьмого элементов И объединены и подключены к выходу второго элемента

НЕ, вход которого объединен с вторыми входами девятого и десятого элементов ИЛИ и подключен к выходу третьего элемента НЕ, вход которого является входом задания логической единицы устройства, выходы первого, второго и третьего элементов И являются соответственно пятым, первым и шестым выходами блока, четвертым, третьим и вторым выходами которого являются выходы соответственно четвертого, пятого и шестого элементов

И, вторые входы которых подключены к Выходам соответственно четвертого.. шестого и седьмого элементов ИЛИ, второй вход шестнадцатого элемента

И подключен к выходу четвертого элемента НЕ, вход которого является четвертым входом блока, второй вход которого подключен к вторым входам одиннадцатого и пятнадцатого элементов И, второй вход двенадцатого элемента И подключен к выходу пятого элемента НЕ, вход которого объединен с вторым входом тринадцатого элемента И и является третьим входом блоXy(<) Хф!

278883 о ка, первый вход которого подключен к вторым входам девятого и четырнадцатого элементов И и входу шестого элемента НЕ, выход которого подключен к второму входу десятого и третьему входу пятнадцатого элементов И.

1278883, 25 Рб

)2j8883 ят Л Л

PJ

Р9

Рг7

Pz2

Сч7 иа. )

I3

Л

26 айаг.б

1278883

7123OS б

Составитель А. Баранов

Техред А.Кравчук

Корректор А. Обручар

Редактор В. Иванова

Заказ 6841/49 Тираж 671

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

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

Подписное Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4