Устройство для вычисления корреляционной функции

 

Изобретение относится к области гидроакустики, связи, вычислительной техники и может быть и спользовано при обработке сигналов,.представленных в цифровой форме. Цель изобретения - повышение точности. Устройство содержит два блока 1,7 дискретного преобразования Фурье, блок 2 разделения спектров, согласованный фильтр 3,два блока 4,5 комплексного перемножения спектров, блок.6 смешивания спектров, блок 8 формирования выходного массива , блок 9 памяти коэффициентов,блок 10 управления согласованной фильтрацией и генератор 11 тактовых импульсов . Цель изобретения достигается введением двух блоков комплексного перемножения спектров, позволяет сократить в устройстве количество вычислительных затрат в два раза по сравнению с известным устройством при вычислении корреляционной функции удвоенной точности. 2 ил. фиа/

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

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

РЕСПУБЛИН

А1 (19) (1!) (5D4 G 06 F

ЪСГ Р :.*>." К Т

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

113 " 1З

ЬКЬЛМО Р. ".А

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К А8ТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4058084/24-24 . (22) 20.03.86 (46) 15.11.87. Бюл. Ф 42 (72) В.А.Сапрыкин, О.А.Артамонов, Ю.В.Городничев, Е.Н.Одинцов и А.В.Смирнов (53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 800995, кл. G 06 F 15/332, 1981.

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

В 1251106, кл. G 06 F 15/332, 04.01.85. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОРРЕЛЯЦИОННОЙ ФУНКЦИИ (57) Изобретение относится к области гидроакустики, связи, вычислительной техники и может быть использовано при обработке сигналов, представленных в цифровой форме. Цель изобретения— повышение точности. Устройство содержит два блока 1,7 дискретного преобразования Фурье, блок 2 разделения спектров, согласованный фильтр З,два блока 4,5 комплексного перемножения спектров, блок 6 смешивания спектров, блок 8 формирования выходного массива, блок 9 памяти коэффициентов, блок

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

1 1352501

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

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

10 увеличения вычислительных затрат.

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

Устройство (фиг. 1) содержит первый блок 1 дискретного преобразования Фурье, блок 2 разделения спектров, согласованный фильтр 3, первый

20 и нторой блоки 4 и 5 комплексного перемножения спектров, блок 6 смешивания спектров, второй блок 7 дискретного преобразования Фурье, блок

8 формирования выходного массива, блок 9 памяти коэффициентов, блок

1О управления согласованной фильтрацией, генератор 11 тактовых импульсов.

Блок формирования выходного массива (фиг. 2) содержит счетчик 12, элемент НЕ 13, первый и второй сумматоры 14 и 15, элемент И 1б, блок

17 памяти.

Устройство реализует следующий алгоритм вычисления корреляционной функции повышенной точности С „„(m) С„„(п) П„„() С„„() C„„(7)

15 с (к)

sÄÄ (K)

s„„, (к) 25 к(к) 30 х (к)

Y(K) у (к) Х(п), Y(n) Z(n) 40 с (к), s„"„(ê), s „„, (к), Y (к), Y„ (К) — комплексно сопряженные значения функций С(К), Я„„ (К), S (1:), Y(K) „Y (K);

FГ 1, F (1 — прямое и обратное преобразования Фурье;

N — длина сигналов, спектров, функций, корреля50 ции в отсчетах; — логическое значение с„„() =Г л.чс„, (-))л А.чс„„, (-.)); в„„() = с„„(-) + jc„„, (i) в„„() =- F Г с(к)) = г (с (K)j (1) G (к) =.s (ê) + js (к))

sÄÄ (K) = х(к) Y (к);

s„„, (к) = х(к) ъ, (к);

„Эк и Т1К

У, (К) = Y(K) е = Y(K) f cos

2 функция корреляции сигнялов Х(гп), Y(m) c отсчетами, следующими во нремени вдвое чаще входных; комплексный результат обратного преобразования Фурье над смесью спек1ров S« (K) и хЧ функция корреляции сигналов X(n) У(п); функция корреляции сигнала Х(п) и сигнала

Y(n), сдвинутых во времени на пол-отсчета; смесь спектров S„"„ (К) .

° s„"„(к); взаимный спектр сигналон X(n), Y(n); взаимный спектр сигнала Х(п) и сигнала Y(n) сдвинутых во времени на пол-отсчета; смесь спектров, результат преобразования Фурье над входной комплексной последовательностью Z(n); спектр сигнала Х(п); спектр сигнала Y(n); спектр сигнала Y(n) сдвинутого во времени на пол-отсчета; исследуемые сигналы; комплексная входная последовательность сигналон X(n), Y(n); т к

s1n ji и х(к) + (к) = z(K)

2(К) = F L Z(n)l;

2(n) = Х(п) + jY(n) младшего адресного разряда адреса блока памяти выходного массива; — инверсное значение Д и = О;1,2,...N-1 — порядковые номера отсчетов сигналов;

1352501

Р (С ху (i) ) = $ хУ (К) 4

F (с„„(L)5 = х(к) Y (к); (6) S„(K) =, Х(К) Y (K) .

211хъ K F Е Х(п-a)1 = Х(К) е

N-1 11

X(n) = F Е Х(К) l = Х(п) е, (2) к=о 20 2 ак

F Е Х(п-a) 1 = Х(К) (cos — ——

2_#_ак — j sin — — -)

X(n) = F t. F(X(n)1.

X(K) = F L X(n)1, (3) х (М К) X(K)х к 192Э ° ° °, 2

Вычисление преобразования Фурье от комплексной последовательности:

Z(n) = X(n) + jY(n);

2 ЙьК м-1 н

Z(K) = F Е. 2(п)1 = Z(n)e

23апк

40 к-о ху

Е U„„(K) cos

21ТпК (К) sin - — — 1;

N-I

) = F Р S„ „(K)) = кхо

1=a

1 х у

= Х(К) + j Y(K), (4),1

S (К) е

45 "хУ

23пк (U (К) cos — ——

ХУ N

= . С:: к=о

50 211 пк — V (K) sin — — - 1xv N (8) (к) = х(к) + jY(K);

Х(К) = Е Z(K) + Z (N-К) Л

Y(K) = 1 t. Z (N K) — Z(K)1, N. гдеК=1,2,3, ° .. — --1.

К = О 1 2,...,N-1 — порядковые номера отсчетов спектров;

1 = 0,1,2,..., N-1 — порядковые номера отсчетов функций корреляции С

Ху ск„, m = 0,1,2,...2N-1 — порядковые номера отсчетов функции корреляции повышенной точности.

Приведем соотношения, необходимые для обоснования функционирования устройства.

Свойства парности и обратного преобразования Фурье:

М -1

ЯТь х

Х(К) = F Х(п) = Х(п) е

Свойство симметрии спектра действительной последовательности где X(n) — действительная последовательность где п = 0,1,2,...N-1; К =0,1,2,...,.

N-1.

Соотношения для разделения спектров:

Формулы (1)-(5) приведены с точностью до постоянного множителя, что не отражается на результатах вычисле5 ний из-за линейности преобразования

Фурье.

Для вычисления функции корреляции:

Свойство смещения для преобразования Фурье:

Из соотношений (6) и (2) видно, что функция корреляции вычисляется на основе обратного преобразования

Фурье от взаимного спектра SÄÄ (K). д0 При замене спектра S, (К) на комплекх. сно-сопряженный спектр S (К) обратху ное преобразование Фурье заменяется прямым.

Обозначив S(K) = U(K) + jV(K)

3 . 211„11

М-1 и

С„ (i) = F Е S„„ (K)5 = S„„ (K) е кхо

Иэ соотношений (8) видно, что функцию корреляции можно вычислить

55 по соотношениям (1), т.е.: с„„(-.) = г(s,„(ê)1= F "Ея„„(к)1, с„,„(L) = F Т sgyq (к) ) = F С s„„, (к) 5;

1352501 б (9) также формулы (4), (5) и (10), получаем алгоритмы разделения спектров:

Б„„(К} = Х(К) Y (K) i

sÄÄ (K) = х(к),"(к).

Одновременное вычисление двух

Функций корреляции C y () H С,р„(t ) входных последовательностей X(n), Y(n) основывается на использовании алгоритмов разделения и смешивания 1р спектров и свойстве смещения для пре образования Фурье.

Введем обозначения:

+ q(N-к); — R(N-K), (11) 1,2,...

N (- ——

2 где К х(к) = A „(K) + 1в „(к); (к) = А„(к) + j в„(к);

Y, (K) = A„„(K) + jB„(K);

Z(K) = Х(К) + jY(K) = R(K) + jq(K); с (к) = s„ „(ê) + jsÄÄ, (к) =

= ь(к) + дм(к);

А (О) = А (- — ) = AÄ(0) = А ()=0

В согласованном фильтре 3 производится умножение спектра У(к) на коэфТК . У К фициенты cos — и sin — — . В ре25 N N зультате получается спектр Y,(К), соответствующий спектру сигнала Y(n), если бы тот бып представлен отсчетами, взятыми на половину интервала .1п дискретизации позже, чем имеющиеся отсчеты, тогда получим

S„»(K) = U„„,(К) + jV (К); (10) где К = 0,1,2,...N-1; и = 0,1,2,..., N-1;

К(К) = Г (X(n) + „ Y(n)) . (A„(К) + jВ,(К)) (cos — ——

4К з5 жк

j sin — — )= А (К) + jB (К).

N . Х У, В соответствии с формулой (4) смесь спектров 7.(К) = X(K) + jY(K) вычисляется за один проход алгоритма быстрого преобразования Фурье. Учитывая, что (12) ук

Так как коэффициент cos u

3iK

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

Спектры S„„ (K) и S„„, (K) ются в результате комплексного перемножения спектров Х(К) и Y(K) Х(К) и Y (К) в блоках 4 и 5 по алгоритму:

Z(K) = к(К) + jq(K) = Х(К) + jY(K) + зв„(к) + 3 (А„(к) + зв,(к))=

+;B„(K) 1А„(к) - в„(к} = — в„(к) + jfA„(K) + в„(к}1, =- А„(к)

= А„(К)

= A„(K) имеем: (к) = х(к) Y (K);

s„„, (к) = х(к) Y,"(ê) к(к) = А„(к) — в,(к); q(K)=A,(к) +

+ в (к). (13) По формуле (5) производим разделение спектра Е(К} -- R(K) + jq(K) на спектры Х(К) = А .,(К) + 1ву(K)

Y(К) = А„(К) + jВ„(К). Используя свойство симметрии спектров (3), а

S „„(K) U „„(K) 11 ху (К)

А „(К) = A„(N K} R(K) + R(N K) у в (к) = в (и-к} = О(к) — q(N к);

А„(К) = А (N-К) = q(K)

-By (K) = B (N-K) = R(K) а для центрированных сигналов соответственно: в (о) = в (- — ) = в (о) = в (— -) =0;

М N

Спектры S„, (K) H Ь„,, (К) являются взаимными спектрами сигналов Х,Y и

X Y, по которым в соответствии с

У формулами (2) и (6) вычисляются значения корреляционных функций С (7) к и С411 (Т}, 1352501 с„„(») = F (s„ „(к)1; (18) — v„„(K) l; (16) (20) 7

Для вывода алгоритма смешивания спектров S „„(К), Б,„» (К) в спектр

G (K) = L(K) + jM(K), обеспечивающего за один проход выполнения процесса быстрого преобразования Фурье вычисление двух корреляционных функций, рассмотрим выражения:

c„„, () г 8„„,(КН, П у ("") = С х»() + Зс»»у» (") F l s„(K) + дг (Б ху, {к) 1

- г(s"„„(ê) + jsÄ"Ä, (к)1. (14) В итоге получаем алгоритм смешивания спектров (К) 8хч (К) + S„„(К) . (15) Используя свойство симметрии спектров (3) и обозначения (10), алгоритм смешивания спектров примет вид: с (к) = L(K) + jM(K);

G (K) = Uxy jVxv + jlUxY1 - )Ч„„„3 =

= U„(к) + v„„, (к) + 3 (U„„, (к)—

L(K) = Ц„„(K) + V„, (К) 3 т.(и-к) = и„„(к) — v„„(K);

M(K) = U (К) — V (К);

М(И-К) = U xv» (K) + VÄv (К) 4

L(o) т() м(О) м() o, N И где К =1,2,..., (— - — 1) .

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

Нахождение смеси спектров сигналов

Z(K) = F(X(n) + jY(n)J = Х(К) + jY(K). (17) Разделение спектров Z(K) на спектры Х.(К) и Y(K) для К вЂ” О, 1, N (— — — 1) по формуле (11, блок 2):

Z(K) = R(K) + jQ(K);

Х(К) = А „(К) + jB (К), ;(к) = А„(к) + jB„(K);

) R{K) + R(N K)i

В „(к) = Q(K) — Q(N-к) А (К) = Q(K) + Q(N-K)

-В„(К) = R(K) — R(N-К), И гдеК=0,1,2,, — --1, 2О N причем для К = О N — - К =

Получение спектра Y,(К) путем перемножения спектра Y(K) на спектр

„ к

25 фильтра 3 е

Значения коэффициентов фильтра

N для K = 0,1,..., (— — —. 1) вычислены заранее и введены в память согласоЗО ванного фильтра 3 заранее (блок 3) аК .. »1K

Y (К) = Y(K) (cos — — — j sin — -1

» N N (19) N

35 где К = 0,1,2;... (— — — 1) Получение взаимных спектров S „gK), S„„ (К) путем комплексного перемнохч»

4 жения спектров по алгоритму (13):

Sxv (K) = Х(К) - Y (К)

sxv» (КЭ = x(K),"(к), 45 N где К = 0,1 2,. ° ., — — — 1 (блоки 4 и 5).

Вычисление смеси спектров $„у (К) и S„„, (К) по алгоритму (15) (работа

5О блока 6 смешивания спектров): с (к) = т.(к) + jM(K) =

= 8„„(к) + js„„„(к);

55 т.(К) = тт„„(К) + Vxv» (К); т.(и-к) = тт„„(к) — v. (ê);

1352501

К(К) = П „.„(К) — Ч„„(К);

К(И-К) =- t» „„, (K) + V„„(K), (21) N

1 считая

К = О. где К = 0,1,2, N

N Ê

2 для

Вычисление по формуле (17) прямого 10 преобразования Фурье от спектра С (К)=

=L(К) + jN(K) (работа блока 7, на выходах которого вырабатывается комплексное значение D (i) хч

D„„(i-) = с„„() + jc«(i). (22) Объединение вычисленных значений корреляционных функций С„„ () и

Сху (Т) в единый инфоРмационный мас- 20 сив C » (m, содержащий 2N элементов, представляющих отсчеты корреляционной функции сигналов X(n) и Y(n), следующие во времени с интервалом

0,5 t дискретизации входных последо- 25 вательностей.

Объединение результатов производится по алгоритму

Сху (и) Ао С хх (е) Ао хх1 е ) ЗО

Для управления работой блоков 1 и 7 и блока 10 используются тактовые сигналы, формирующиеся в блоке 8 на выходе младшего разряда А счетчи6 35 ка 12.

Принцип работы блока 8 заключается в следующем, Вычисления значения корреляционных функций С„„ (е) и С „„ (e) относят-, ся к разным моментам времени, хотя и г,,ивязаны к одному номеру отсчета.

В выходном массиве блока 7 располагаются в двух ячейках памяти, но по одному адресу, как действительная H мнимая части вычисленной комплексной величины D„„ (i). При обращении к памяти по номеру отсчета е на информационную магистраль выдается слово двойной длины. Необходимо за одно обращение к памяти блока 7 дважды подать на информационный вход блока

17 памяти слова обычной длины и сформировать два адреса для записи этих слов в разные ячейки памяти. Первым

55 словом будет значение действительной части R ЕВ (i) l = С „(С) вторым е словом — значение мнимой части: П х ч (, ) Cх, х„1 „(-. ) Выход генератора 11, частота которого = 2F, соединен с входом счетчика 12, который формирует адреса для записи в блок 17 памяти. Совокупность выходов разрядов счетчика, участвующих в формировании адреса, является его основным выходом. Выход младшего разряда А счетчика 12 является младшим разрядом адреса и дополнительным выходом блока 8. С этого выхода тактовые сигналы частотой F поступают на управляющие вхоцы 1 и

7 блоков 10 согласованного фильтра.

Импульсами с частотой F формируется и адрес считывания значений D (е) хЧ из блока 7.

В блоке 8 выход А, счетчика 12 соединен с входом сумматора 14.

С приходом всех четных тактовых сигналов (0,2,4,...) на выходе А„ счетчика 12 будет появлят:.я значение логического О, с приходом всех нечетных сигналов (1,3,5,...) на выходе

А, будет появляться значение логической

Сброс в нулевое состояние всех разрядов всех счетчиков, формирующих адреса происходит синхронно с приходом каждого 2N тактовых сигнала. При этом из нулевой ячейки памяти блока 7. будет считано слово двойной длины, содержащее значения Г „„(7-) и С „у1(е- ).

Поскольку А, =, О, то на второй вход сумматора 14 будет подан логический О, а на второй вход сумматора

15 будет подана с выхода элемента

НЕ 13 логическая 1. На выходе сумматора 14 появится значение С „„(О), а на выходе сумматора 15, независимо от значения С „, (О), появится логическая 1. Элемент И 16 пропустит на выход значение С„„ (О), которое запишется в нулевую ячейку памяти блска

17. С приходом первого тактового сигнала значение информации на первых входах сумматоров 14 и 15 не изменится, так как адрес считывания в блоке 7 еще H" изменился. В счетчике

12 формируется адрес первой ячейки памяти блока 17, значение A = 1, О., Теперь на выходе сумматора

i4, незавчсимо от значения С„„(О) будет 1, а на выходе сумматора 15 появи-.ся значение С „„,(О), которое, пройдя элемент И 16, запишется в блок 17 памяти в первую ячейку. Таким образом, в выходном массиве, за12

135?501

Z(K) = X(K) + jY(K), е хч () - Схч

Т П у () 3 С „„ (i. ) писанном в блок 17 памяти в четных ячейках, будет находиться значения

С „„(.), í vечетных — С„„, (Г) .

Устройство для вычисления корреляционной функции повышенной точности работает следующим образом.

Входные сигналы X(n) и Y(n) длиной в N отсчетов поступают в устройство по первому и второму входам блока 1. В блоке 1 в соответствии с алгоритмом (17) вычисляется смесь спектров которая с выхода блока 1 поступает на вход блока 2, который функционирует в соответствии с алгоритмом (18).

Полученные составляющие спектров сигналов:

Х(К) = А (К) + jB (К);

К(К) = А„(К) + )В„(К), поступают на блок 4, кроме того, составлЯющие спектРа Y(K) =A „(K) + 3 Вч(К) поступают на основной вход согласованного фильтра 3, на управляющий вход которого поступает адрес для выборки значений коэффициентов фильтра, вычисленных заранее и введенных в память согласованного фильтра 3.

В согласованном фильтре 3 по алгоритму (19) вычисляется спектр Y„(K) сдвинутый относительно спектра 7(К) на половину периода, что соответствует сдвигу сигнала Y(n) во времени на половину интервала дискретизации.

Таким образом, на входы блока поступают составляющие спектров:

Х(К) А х(К) + jB х(К) т(К) = А (К) + )В„(К), и на входы блока 5 поступают составляющие спектров:

X(K) = А (К) + jB „(К); с() ч (ч1(В результате комплексного перемножения спектров по алгоритму (20) на выходе блоков 4 и 5 получаются значения взаимных спектров:

S (К) = Х(К) ™(К);

$„(К) = Х(К) У (К) 5 где К = 0,1,2,..., (— — — 1), N составляющие взаимных спектров S„ч(К) и Б „,, (К) поступают соответственно на входы блока 6, в котором по алгоритму (21) формируются составляющие смеси спектров С (К) =Е(К) + ja(K) °

Сформированный массив значений

С (К) обрабатывается блоком 7 в соответствии с алгоритмом (22), результатом обработки является формирование массива вычисленных значений комплексной функции, где действительная часть П „(Т) = Р (С (K)) Отсчеты, хранящиеся в выходном масси25 ве блока 7, обрабатываются блоком 8, который из N значений комплексной функции D (i) формирует 2И значений действительной функции корреляции повышенной точности C„ (m) в соответствии с алгоритмом (23).

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

Устройство для вычисления корреля35 ционной функции, содержащее первый и второй блоки дискретного преобразования Фурье, блок памяти коэффициентов, блок разделения спектров, блок смешивания спектров, согласованный фильтр, 40 генератор тактовых импульсов и блок управления согласованной фильтрацией, причем входы реальной и мнимой частей операнда первого блока дискретного преобразования Фурье являются инфор45.мационными входами устройства, выход блока. памяти коэффициентов подключен к входам задания коэффициентов первого и второго блоков дискретного преобразования Фурье, выход первого бло50 ка дискретного преобразования Фурье соединен с информационным входом блока разделения спектров, первый выход которого подключен к информационному входу согласованного фильтра, выход

55 блока смешивания спектров соединен с информационным входом второго блока дискретного преобразования Фурье,первый выход блока управления согласоСоставитель Е.Хуртин

Редактор Ю.Середа ТехредИ.Ходанич Корректор Н.Король

Заказ 5567/49 Тираж 6/1 Подписное

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

113035, Москва, Ж-35, Раушская наб., д.4/5.Производственно-полиграфическое предприятие, r.Óæãîðoä,. ул.Проектная,4

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

5 спектра блоков, разделения и смешивания спектров, второй выход блока управления согласованной фильтрацией соединен с вторыми входами управления выбора составляющих спектра блоков разделения и смешивания спектров, вход тактирования блока управления согласованной фильтрацией и входы синхронизации первого и второго блоков дискретного преобразования Фурье объединены, о т л и ч а ю щ е е с я тем, что, С целью повышения точности, в него введены первый и второй сумматоры, элемент И, элемент НЕ, счетчик, блок памяти и два блока комплексного перемножения спектров, первые входы обоих блоков комплексного перемножения спектров соединены с вторым выходом блока разделения спектров, первый выход которого подключен к второму 2Б входу первого блока комплексного перемножения спектров, выход согласоI

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

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