Устройство для вычисления дискретного преобразования Фурье Советский патент 1992 года по МПК G06F15/332 

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

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

На фиг. 1 представлена функциональная схема устройства для вычисления дискретного преобразования Фурье (ДПФ); на фиг. 2 -временные зависимости основных сигналов.

Устройство для вычисления ДПФ содержит информационный вход 1, модулятор 2 линейной дельта-модуляции, регистр 3 сдвига, буферный регистр 4, первый и второй блоки постоянной памяти 5 и 6, первый и второй сумматоры 7 и 8, первый и второй

мультиплексоры 9 и 10, первый и второй блоки ключей 11 и 12, первый и второй блоки памяти 13 и 14, генератор 15 тактовых импульсов, первый, второй и третий счетчики 16,17 и 18, выход 19 реальной части результата, выход 20 мнимой части результата, вход 21 задания константы устройства.

Информационный вход модулятора 2 является информационным входом 1 устройства, выход модулятора 2 соединен с информационным входом регистра 3 сдвига, выход которого соединен с информационным входом буферного регистра 4. Выходами 19 реальной и выходами 20 мнимой частей результата являются выходы соответственно первого 11 и второго 12 блока ключей. Выход генератора 15 тактовых импульсов подключен к входам управления записью считыванием первого 13 и второго 14

sj

ю SJ

блоков памяти, тактовому входу третьего счетчика 18, тактовому входу первого счетчика 16, информационный выход которого подключен к первым адресным входам первого 5 и второго 6 блоков постоянной памяти и адресным входам первого 13 и второго 1.4 блоков памяти, информационные входы которых подключены к выходам соответственно первого 9 и второго 10 мультиплексоров. Выход переноса первого счетчика 16 подключен к тактовому входу буферного регистра 4 и к тактовому входу второго счетчика 17, информационный выход которого подключен к вторым адресным входам первого 5 и второго 6 блоков постоянной памяти. Выход переноса второго счетчика 17 подключен к управляющим входам первого 11 и второго 12 блока ключей и управляющим входам первого 9 и второго 10 мультиплексоров, первые информационные входы которых подключены к входу 21 задания константы устройства. Выход переноса третьего счетчика 18 подключен к тактовому входу регистра 3 сдвига и входу синхронизации модулятора 2 линейной дельта-модуляции. Выход буферного регистра 4 подключен к третьим адресным входам первого 5 и второго 6 блоков постоянной памяти, выходы которых подключены к первым входам соответственно первого 7 и второго 8 сумматоров, выходы которых подключены к информационным входам соответственно первого 11 и второго 12 блока ключей и вторым информационным входам соответственно первого 9 и второго 10 мультиплексоров, выходы первого 13 и второго 14 блоков памяти подключены к вторым входам соответственно первого 7 и второго 8 сумматоров.

На фиг. 2 показаны следующие сигналы: а - импульсы тактового генератора 15; б- импульсы на выходе переноса третьего счетчика 18; в - дельта-последовательность на выходе модулятора 2 линейной дельта- модуляции; г,д- импульсы на выходах переносов счетчиков .1.6 и 17 соответственно; е, ж - сигналы на выходах 19 и 20 соответственно действительной и мнимой частей ДПФ.

Устройство для вычисления ДПФ работает следующим образом.

Алгоритм работы устройства ДПФ массива отсчетов входного сигнала, полученного при частоте дискретизации Тд , равной частоте дискретизации входного сигнала с линейной дельта-модуляцией, записывается в следующем виде:

/С1 м Ао -лХСт-Дт Щ кехрН тк)

где Af (М.Тд)1 - разрешение по частоте; (@/Тд) - число отсчетов; @- интервал реализации.

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

Легенд}.

1 1

Тогда ДПФ (1) записывается в следующем виде:

XO |f|1e|(X)exPHl rnK), (2) где К, т, ,М.

Для получения алгоритма функционирования предлагаемого устройства заменим

порядок суммирования в (2). Область изменения значений индексов суммирования на плоскости (к, I), как следует из (2), ограничена прямыми , , . Поэтому при изменении порядка суммирования индекс I

будет меняться от 1 до М, а индекс К от I до М, На основании этого получим

Хф- -S i.f.(x)exp(), (3)

к 1 к iIVI

Действительную и мнимую части (3) преобразуем следующим образом:

Яе(

5т

ImLMzr)J 2«г

-i- 1

1M

м м м

COS -ft™ к - i - 1

. ff M

ШК iMf--

е.(хт--(. ef Ч )(.

,(5

где Crm Srm - суммы соответствующих величин.

Разделив действительную и мнимую части ДПФ (4) и (5) на Р частей, получим следующие алгоритмы:

м

«er QjV|| g c-ft)

р- &+7)-Й +

toCxfgH-rzrZH .m

9 0 i 9 1

Приведенные алгоритмы реализуются в устройстве следующим способом. Входной сигнал {erfy кодируется одним битом в виде ) /2- UCxrЈ {0.1}. Тогда для фиксированного индекса m значения действительной и мнимой частей ДПФ по (6) и (7) вычисляются при помощи р суммирований частичных сумм

Re

л--

°lm fm)

(

(« iml

e(. UL

(x) ,, m)

адресуемых -

Si

i. ij+f

шагами квантования

(.

fl + l-Efc-M

постоянной памяти соответствует

q +1, М (q +i)i ,P-1, которые затем

для заданного т накапливаются в памяти. Значения элементов последовательности

(ftj.. 0, р - 1записаны в блоке 5 постоянной памяти, причем первые адресные входы блока 5 соответствуют индексу т, вторые входы - индексу q, третьи входы блока 5

М Р

следовательным значениям шагов квантования входного сигнала {Lpxty. Запись в блок 5 производится подряд по группам значений mq, начиная с нулевой группы, для которой и заканчивая группой/для которой . В каждой отдельной группе (при фиксированных значениях индексов m и q значения б Re(m) q считываются из блока

М

5 постоянной памяти при помощи - значений шагов квантования {Lrx }, поступаю- щих на третьи входы блока 5 памяти. Число входов блока 5 памяти равно r IOQ2M+

+IOQ2P+

М

, а используемый объем памяти М

ячеек.

Аналогично производится запись значений элементов последовательности {д т (т)™} в блоке 6 постоянной памяти.

Перед началом работы необходимо занести нулевые значения в блоки 13 и 14 памяти и установить счетчики 16, 17, .18 в начальное нулевое состояние (цепи сброса на чертеже не показаны).

Вычисление массиваДПФХ(тгт),.М

производится раздельно для .действительной и мнимой частей блоками 5, 7, 9, 11, 13 и 6, 8, 10, 12, 14. Различия в функционировании указанных блоков отсутствуют, поэтому рассмотрим реализацию вычислений массива отсчетов действительной части ДПФ, которые производятся в режиме реального времени следующим образом. .

Тактовый генератор 15 генерирует непрерывную последовательность импульсов (см. фиг. 2 ,а) с частотой, кратной частоте

35

40

45

50

55

(

Sk поступают на первые, вторые и третьи адресные входы блока 5 постоянной памяти, в результате чего за интервал времени МТД с выхода блока 5 памяти считывается Р

групп по М значений 5ке(гг , каждое на протяжении интервала времени

д

Сигнал с выхода генератора 15 тактовых импульсов (см. фиг. 2,а) является также управляющим для блока 13 памяти: при высоком уровне этого сигнала производится чтение из блока 13 записанного в нем значения сигнала, а при низком уровне -запись в блок 13. Поэтому, с учетом установки начальных значений в интервале времени (to, ti) нулевое значение сигнала из 1-й ячейки блока 13 подается на вход сумматора 7, на другой вход которого поступает сигнал с выхода блока 5 постоянной памяти. В результате этого сумматор 7 выполняет операцию суммирования содержимого 1-й ячейки

блока 13 со значением ( .. причем

М

первый интервал времени-Тд имеет инР

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

20

10

15

мате линейной дельта-модуляции, f-рТд . Импульсы (см. фиг. 2,а) поступают на счетчик 1.8 с коэффициентом пересчета р. Импульсы с выхода переноса счетчика 18 с частотой, равной частоте дискретизации Тд 1 (см. фиг. 2,6) поступают на тактовые входы модулятора 2 линейной дельта-модуляции и регистра 3 сдвига. Модулятор 2 преобразует поступающий с информационного входа 1 входной аналоговый сигнал X(t) в дельта-кодовую последовательность {Lrx }, l 0 (см. фиг. 2, в), которая по импульсам (см. фиг. 2,6) записывается и сдвигается в регистре 3 сдвига. Импульсы (см.фиг2,а) с выхода тактового генератора 15 поступают также на счетчик 16, имеющий коэффициент пересчета М. Импульсы (см. фиг. 2,г) с выхода переноса счетчика 16 следуют с частотой f

vv т.е. один импульс на - периодов частоты дискретизации входного сигнала . По этим импульсам последовательность из

- шагов Р

м,(XV ,

квантования входного сигнала

М

М

{Uw}. l q у + 1, (q 4-1) фиксируется

в буферном регистре 4, где q - состояние счетчика .17, имеющего, коэффициент пересчета р (см. фиг. 2,д).

Обозначим кодовое слово из последовательМ

ности значений , i q - + 1,(q + 1)

РР

че

,00)

,м

pes{Sk . k /(-). Значения сигналов m, q и

(

Sk поступают на первые, вторые и третьи адресные входы блока 5 постоянной памяти, в результате чего за интервал времени МТД с выхода блока 5 памяти считывается Р

групп по М значений 5ке(гг , каждое на протяжении интервала времени

д

5

0

5

Сигнал с выхода генератора 15 тактовых импульсов (см. фиг. 2,а) является также управляющим для блока 13 памяти: при высоком уровне этого сигнала производится чтение из блока 13 записанного в нем значения сигнала, а при низком уровне -запись в блок 13. Поэтому, с учетом установки начальных значений в интервале времени (to, ti) нулевое значение сигнала из 1-й ячейки блока 13 подается на вход сумматора 7, на другой вход которого поступает сигнал с выхода блока 5 постоянной памяти. В результате этого сумматор 7 выполняет операцию суммирования содержимого 1-й ячейки

блока 13 со значением ( .. причем

М

первый интервал времени-Тд имеет инР

деке , который определяется значением

кода на разрядных выходах счетчика 17 (см. фиг, 2,д).

Импульс переноса счетчика 17 появляМется в q-P-1-м интервале времени -ргТд,

поэтому из-за отсутствия в данном периоде времени - Тд сигнала (см. фиг. 2, д) с выхода переноса счетчика 17 () в интервале времени (to. 12} блок 11 ключей находится в закрытом состоянии, а мультиплексор 9 передает сигнал с выхода сумматора 7 на информационный вход блока 15 памяти и в интервале времени:(ti, tz), производится запись значения сигнала из сумматора 7 в 1-ю ячейку блока 13 Аналогичные операции производятся : для интервалов времени (t2,j41 и т. д., в результате чего в ячейках ,М блока 13 памяти записывается соответствующее значение сигнала

RK,

пг

(гтр.,

k 1, т 1, т.е. для i 1,-

В следующем Тд М

периоде времени значение кода на разрядных выходах

счетчика 17 увеличивается на единицу () и поэтому в интервалы времени (t0, ta), (t2,14) и т.д. указанного периода происходит накопление значений сигналов:

Rk. m Rk-1. m+ 5Re(m)(q). . ,M,

т.е. + 1,.

В результате такого накопления после

Тд М (Р-1)-го периода времени ---- (для )

в ячейках блока 13 памяти накоплено значение сигнала, равное сумме (Р-1)-го слагаемых вида д Re(m) q по (8).

Тд М

В Р-м периоде времени на выходе переноса счетчика 17 появляется импульс (см. фиг. 2,6)(), в результате чего открывается блок 11 ключей, а мультиплексор 9 переводится в положение, при котором информационный вход блока 13 подключаются к входу 21 задания константы устройства, сигнал на котором равен нулю. Поэтому в интервалы времени (t0, ti), (t2, тз) и т.д. выходной сигнал блока 13 суммируется с последним, Р-м, слагаемым 5ре(м/ согласно (6) и через открытый блок 11 ключей поступает на выход 19 (действительной) части результата вычислений, т.е. на выходе 19 формируется в данном периоде времени

-- последовательность элементов действительной части массива ДПФ (6) (j ),

,M. (сигнал, фиг. 2 е). В интервалы времени (ti,..ta), (ta, 14) и т.д., т.е. при низком уровне сигнала (см. фиг. 2, а), блок 13 пере- водится в режим записи, и в ячейки ,М записывается нулевое значение сигнала, в результате чего устройство приводится в исходное состояние.

Аналогично производится вычисление массива отсчетов мнимой части ДПФ, Выдача массива (Щ), (сигнал, фиг. 2,

ж) на выход 20 производится в Р-м интерваТд М ле времени одновременно с формированием массива действительной части ДПФ ( -j-т ) на выходе 19, что обеспечивает

формирование значений массива мнимой части согласно (7).

Таким образом, для вычисления в пред- лагаемом устройстве ДПФ входной последовательности, представленной в формате линейной дельта-модуляции, за счет использования одновременной обработки

Л Л

группы из - шагов квантования, используется только М.Р арифметических операций суммирования, что позволяет увеличить частоту дискретизации входного сигнала в

М

- раз по сравнению с прототипом, где вычисление ДПФ такого же размера требует М указанных операций.

Блок 5 постоянной памяти может быть

реализован на основе постоянного запоминающего устройства, число адресных входов которого равно r log2M+ 1од2Р+ - , а

разрядность представления значений бРе(т)™ определяется от требуемой точно сти представления результата ДПФ 1. Например, при выборе М 128, имеем

выигрыш в быстродействии - 4 при объеме используемой памяти блока 5, равной Q2 .25.2 - 2 , что реализуется на восьми микросхемах типа КР556РТ16.

Таким образом, введение в известное устройство регистров, в каждый вычислительный блок - комбинационного сумматора, в блок управления - счетчика позволяет достичь поставленной цели. Вычисление массива действительной и мнимой частей ДПФ входного сигнала с линейной дельтамодуляцией осуществляется при помощи существенно меньшего, чем в прототипе, числа арифметических операций сложения РМ против М2 в прототипе, что позволяет

М соответственно в -

раз увеличить частоту

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

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

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

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

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

входам соответственно первого и второго мультиплексоров, выходы первого и второго блоков памяти подключены к вторым входам соответственно первого и второго сумматоров, выход генератора тактовых

импульсов подключен к тактовому входу третьего счетчика, выход переноса первого счетчика подключен к тактовому входу буферного регистра.

Изобретение относится к специализированным средствам вычислительной техники и может быть использовано в аппаратуре, осуществляющей спектральную обработку сигналов с дельта-модуляцией в реальном.масштабе времени. Цель изобретения - повышение быстродействия. Устройство содержит модулятор 2, регистр 3 сдвига, буферный регистр 4, блоки 5 и 6 постоянной памяти, сумматоры 7 и 8, мультиплексоры 9 и 10, блоки ключей 11 и 12, блоки 13 и 14 памяти, генератор 15 тактовых импульсов и счетчики 16-18. Использование оригинального алгоритма вычисления ДПФ позволяет сократить количество арифметических операций сложения, что и приводит к достижению указанной цели. 2 ил.