Устройство для вычисления корреляционной функции Советский патент 1987 года по МПК G06F17/15 

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

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

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

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

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

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

С,, (га) ,, ()Л ,,, (t);

DXV (). C,v С) + JC,,, (L)-.

В,, (1-) Р Ч G(K)1 ); (1)

G(K) -.S, (K) + ,, (K)-,

8„, (К) х(к)-уЧк);

s,, (к) х(к) Y(K)r j -

N jiV

Y (K) Y(K)-e Y(K) cos -

- . TiK -. -J,sin---,

x(K) + jY(K) z(K) ;

Z(K) F Z(n), , ,. Z(n) X(n) + jY(n) ,

D,v ()

0

KV,

(t) С)

5

)

S,, (К)

«V1

(К)

5

Z(K)

0

Х(К) Y(K)

Y, (К)

5 Х(п). Y(n) Z(n)

функция корреляции сигналов X(m), Y(m) с отсчетами,следующими во времени вдвое чаще входных;

комплексный результат обратного преобразования Фурье над смесью спектров S (К) и

XYI

(К);

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

и s;,, (К);

-взаимный спектр сигналов Х(п), Y(n);

-взаимный спектр сигнала Х(п) и сигнала Y(n), сдвинутых во времени

на пол-отсчета;

-смесь спектров, результат преобразования Фурье над входной комплексной последовательностью Z(n);

-спектр сигнала Х(п);

-спектр сигнала Y(n);

-спектр сигнала Y(n), сдвинутого во времени на пол-отсчета;

-исследуемые сигналы;

-комплексная входная последовательность сигналов Х(п), Y(n);

С(К), S (К), S,, (К), Y(K), X, (к) - комплексно сопряженные значения функций С(К), S (К), S (1C), Y(K),Y(K);

FC-l , F - прямое и обратное преобразования ФypfJe|

N - длина сигналов, спектров, функций, корреляций в отсчетах;

А - логическое значекие младшего адресного разряда адреса блока памяти выходного массива;

Л - инверсное значение А ;

п - 0;1,2,... - порядковые номера отсчетов сигналов;

3 1352501

К О,1,2,...jN-1 - порядковые но-Формулы (1)-(5) приведены с точмера отсчетов спектров;ностью до постоянного множителя, что

f О,1,2,...,N-1 - порядковые но-не отражается на результатах вычислемера отсчетов функций корреляции С ,ний из-за линейности преобразования

С„, ; Фурье.

m О,1,2,,.,2N-1 - порядковые но-Для вычисления функции корреляции: мера отсчетов функции корреляции повьшенной точности.F ) S (К);

Приведем соотношения, необходимыею

для обоснования функционирования уст-Г С(7)1 Х(К) Y (К); (6) ройства.

Свойства парности и обратного пре-S (К) , Х(К) Y (К). образования Фурье:

„, . aTTViK15 Свойство смещения для преобразоваХ(К) F Х(п) 5 Х(п) е ;ния Фурье:

о. 2lfKQ

. uJTnK F X(n-a)3 Х(К) e ;

X(n) (K) 1 X(n) e ;(2)

K 0202 ГяК

F X(n-a)Q X(K) cos ----- N

X(n) F 4F(X(n)l.- j sin---- (7)

Свойство симметрии спектрадеист- В , „ (2) видно.

вительнои последовательности функция корреляции вычисляется

, . , ,-.- Vна основе обратного преобразования

Xt.K) - FLX(,n;J,U;фурье от взаимного спектра S (К).

„.. При замене спектра S,, (К) на комплекгде ХСп) - действительная последова-„ ,, i /тт-ч

сно-сопряженный спектр S (К) обраттельность-, л.

ное преобразование Фурье заменяется

хПы-КЧ - хГк1 к - 1 7- -прямым.

X (.N KJ - Х(.к;, к - l,z,..., 2 Обозначив S(K) U(K) + JV(K),

V,.. имеем: .

. 35. 2 Пп«

Вычисление преобразования ФурьеN-I , комплексной последовательности: С (Тг) F 8,у (К) У S (К) е

Z(n) Х(п) + jY(n);гм 2ЖпК

и„, (К) COS --- Z(K) F CZ(n)l ZI Z(n)

N--1 -4-- .40 -f- I U,,

e

N

- V,, (K) sin ,

N a-iTnK

X(K) + JY(K),(4). -J-N.gC,, (c) , (K)(K)e

где n 0,1,2,...N-1; К 0,1,2,...,. .

N-1-.v r TT v 21ГпК

n U, (К) cos --- Соотношения для разделения спект- °

„ , . . ..

- V(K) - sin --;;;--1- (8

Z(K) Х(К) + JY(K);;

ХГК -rzfKl + 7 fN-Kn- С) соотношений (8) видно, что А.к; - L i(,K; + л (,и 1.э; функцию корреляции можно вычислить

Y(K) j Z() - Z(K)1, ° соотношениям (1), т.е.:

C(t) FLS/, (K),v(K)li

где к 1,2,3,... --- - 1.С,,, (Т) FlS,%, (К)1 F ts,(K)3;

и„, (К) COS --f- I U,,

N

- V,, (K) sin ,

N

513525016

S (К) X(K)-Y(K);(9) также формулы (4), (5) и (10), получаем алгоритмы разделения спектров: 8„, (К) Х(К) Y(K).

5 А(К) A,(N-K) R(K) + R(N-K); Одновременное вычисление двух

функций корреляции С (г) и С, (т) В (К) В/N-K) Q(K) - Q(N-K); входных последовательностей Х(п),

Y(n) основывается на использовании А(К) А(N-K) Q(K) + Q(N-K); алгоритмов разделения и смепгавания .10 ,

спектров и свойстве смещения для пре- -By(К) В(N-K) R(K) - R(N-K), (11) образования Фурье..

Введем обозначения:где К 1,2,... (2

Х(К) А(К) + jB(K);15 а для центрированных сигналов соответственно:

Y(K) АЛЮ + JB, (К);„N

В(0) В;(-|-) В(0) )0;

Y, (К) А, (К) + JB, (К);.

Z(K) Х(К) . JY(K) R(K) . JQ(K); ° .° Ф (-|-)0

В согласованном фильтре 3 произво- G(K) S (К) + jS (К) дится умножение спектра Y(K) на коэф,ЗГК . ITK „

, фициенты cos --- и sin --- . В ре L(K) + JM(K);25 N N

зультате получается спектр Y(K), со- S, (К) и (К) + (К);ответствующий спектру сигнала Y(n),

если бы тот был представлен отсчета- 5ку,(К) и,, (К) + jVn(K), (10) ми, взятыми на половину интервала

30 дискретизации позже, чем имеющиеся

где К 0,1,2,..,N-1; п 0,1,2,..,, отсчеты, тогда получим N-1;.

Z(K) - F Х(а) + jY(n) .55К

А/К) + JB,(K) Lcos -|- В соответствии с формулой (4) 5

смесь спектров Z(K) Х(К) + JY(K) j gi 1 . .. вычисляется за один проход алгоритмаN . i

быстрого преобразования Фурье. Учиты-уу

вая чтоfaK как коэффициент cos --- и

лп JlK д, , , , . . J sin --- при функционировании устроиZ(K) R(K) + JQ(K) Х(К) + JY(K) N

ства не изменяются, то их значения -- А(К) + JB(K) 4- j AY (К) + ) вычисляются заранее и вводятся в па.-мять согласованного фильтра 3.

AJ.K) + .JB(K) JA/K) - Ву(К) g Спектры S (К) и S (К) получа- ются в результате комплексного пере- А/К) - В(К) + jrA/K) + B(K)J, множения спектров Х(К) и Y(K) , X(K)

и Y (К) в блоках 4 и 5 по алгоритму: имеем:

.„ S (К) Х(К) ); R(K) А(К) В(К); Q(K)Ay(K) +

S.,. (К) ХШ Y (К) .. (13)

BJK).. ХУ1,

Спектры Sj (к) и (К)являгатся

По формуле (5) производим разде- gg взаимными спектрами сигналов X,Y и ление спектра Z(K) R(K) + JQ(K) X, Y, по которым в соответствии с на спектры Х(К) А (К) + jB(K) и формулами (2) и (6) вычисляются зна- Y(K) А(К) jB(K). Используя чения корреляционных функций С (т) свойство симметрии спектров (3), а и С, (Т).

7 1352501 S

Для вывода алгоритма смешиванияРазделение спектров Z(K) на спектспектров SK,(K), S,, (К) в спектрры Х.(К) и Y(K) для К О, 1

G(K) L(K) + JM(K), обеспечивающе-N .. /,ч ол

го за один проход вьтолнения процес- Г ° Формуле (11, блок 2):

са быстрого преобразования Фурье Z(K) R(K) + JQ(K);

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

рассмотрим выражения:Х(К) - А (К) + jB (К);

C,,,(r),.(K);МЮ R(K) . R(N-K);

СхуС) (К) :(К) А(К) + JB,(K);

,(К) Q(K) - Q(N-K);

D,(T) C,(r) + JC, ()

A/K) Q(K) + Q(

F S (K) + JF (K)

-B/K) R(K) - R(N-K) , (18)

,(K) + JS, (K)l. (14) , , , , N

где К 0,1,2,..., --- - 1,

Б итоге получаем алгоритм смешивания

спектровпричем для К О N - К .

G(K) S (К) + 8 (К) , (15) Получение спектра Y,(K) путем пе- ремножения спектра Y(K) на спектр

i IK Используя, свойство симметрии спектров 25 фильтра 3 е N .

. (3) и обозначения (10), алгоритм сме- Значения коэффициентов фильтра шивания спектров примет вид:, N v

для К 0,1,..., (-«- - 1) вычислены

.

G (К) L(K) + jM(K);заранее и введены в память согласо

30 ванного фильтра 3 заранее (блок 3)

сЧк) и,, - jv, -I- ,,, - jv,,J

Y (К) Y(K) cos -|- - j sin 1, U, (K) -b V,,, (K) + jLU,,,(K) - « .NN

(19)

35 где К 0,1,2,... (-- - 1)

. - n

2

L(K) и„(К) + V,, (K);

Получение взаимных спектров 5 j,K) , L(N-K) (K) - , (K) ;SJJ CK) путем комплексного перемнодг жения спектров по алгоритму (13): М(К) и,, (К) - ); (16)

S.y (К) Х(К) Y(K); M(N-K) U,, (К) + V (К);

NNЗЖУ, (К) Х(К) Y;(K) , (20)

L(0) L(-) М(0) М(-) О,

где К - 0,1,2,..., -7J1 (блоки 4

N

где К 1,2,..., (-j- - 1).и 5).

Вычисление смеси спектров S (К)

Таким образом, для нахождения зна- « xv-t К « алгоритму (15) (работа чений функции корреляции повьшенной ° смешивания спектров): точности в соответствии с алгоритмом , /ч / (1) необходимо выполнить следующие - ь.к; jMk ;

вычисления. .„«- / ч . /,%

S(K) + jS, (К);

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

L(K) и(К) 4- VXY, (К); Z(K) (n) + jY(n) X(K)+jY(K).

(17) L(N-K) U(K) - V, (K);

- - j sin

- - 1)

. - n

2

М(К) и,.,, (к) - V (к);.

N - К --- для К О.

1352501 0

Выход генератора 11, частота которого 2F, соединен с входом счет- (21) чика 12, который формирует адреса

g для записи в блок 17 памяти. Сово- считая купность выходов разрядов счетчика,, участвующих в формировании адреса, является его основньм выходом. Выход младшего разряда А счетчика 12 ,являВычисление по формуле (17) прямого 10 ется младшим разрядом адреса и допол- преобразования Фурье от спектра G(K) нительным выходом блока 8. С этого L(K) + jM(K) ( работа блока 7, на выхода тактовые сигналы частотой F выходах которого вырабатывается комп- поступают на управляющие входы 1 и

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

В блоке 8 выход А счетчика 12 соединен с входом сумматора t4. 20 С приходом всех четных тактовых сигналов (0,2,4,...) на выходе А счетчика 12 будет появлят-ся значение логического О, с приходом всех нечетных сигналов (1,3,5,...) на выходе А Q будет появляться значение логической 1.,

лексное значение D (г)

DxyCO

С,, (Г)

+ JCxv, (t). (22)

Объединение вычисленных значений корреляционных функций С (г) и Суу, (Т) в единый информационный массив С (т, содержащий 2N элементов, представляющих отсчеты корреляционной функции сигналов Х(п) и Y(n), следующие во времени с интервалом 0,5 t дискретизации входных последовательностей.

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

С„ (т) ,,

(Т) Л

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

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

Вычисления значения корреляционных функций С (f) и С (t) относятся к разным моментам времени, хотя и л швязаны к одному номеру отсчета. В выходном массиве блока 7 располагаются в двух ячейках памяти, но по одному адресу, как действительная и мнимая части вычисленной комплексной величины D (Т). При обращении к памяти по номеру отсчета Т на информационную магистраль вьщается слово двойной длины. Необходимо за одно обращение к памяти блока 7 дважды подать на информационный вход блока 17 памяти слова обычной длины и сформировать два адреса для записи этих слов в разные ячейки памяти. Первым словом будет значение действительной

части К„ СВ,„ (tr) С(Г) вторым

t у словом - значение мнимой части:

Im (г) ().

35

40

Сброс в нулевое состояние всех разрядов всех счетчиков, формирующих у,, () (23) 30 адреса происходит синхронно с приходом каждого 2N тактовых сигнала. При этом из нулевой ячейки памяти блока t будет считано слово двойной длины, содержащее значения (1::) и С у, (с ). Поскольку АО О, то на второй вход сумматора 14 будет подан логи- ческий О, а на второй вход суг-даатора 15 будет подана с выхода элемента НЕ 13 логическая 1. На выходе сумматора 14 появится значение С (О), а на выходе сумматора 15, независимо от значения С xvi (О) появится логическая 1. Элемент И 16 пропустит на выход значение С (О), которое запишется в нулевую ячейку памяти блока 17. С приходом первого тактового сигнала значение информации на первых входах сумматоров 14 и 15 не изменится, так кав: адрес считывания в блоке 7 еще не изменился. В счетчике 12 формируется адрес первой ячейки памяти блока 17, значение А 1, А, - О. Теперь на выходе сумматора 4, независимо от значения С() У дат 1, а на выходе сумматора 15 появится значение С xv, (О), которое j, пройдя элемент И 16, запише.тск в блок 17 памяти в первую ячейку. Таким образомj в выходном массиве, за45

50

55

35

30

11

писанном в блок 17 памяти в четЕ1ых ячейках, будет находиться значения ), в нечетных -

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

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

Z(K) Х(К) + jY(K),

которая с выхода блока 1 поступает на вход блока 2, который функционирует в соответствии с алгоритмом (18). Полученные составляющие спектров сигналов:

Х(К) А (К) -f JB (К);

А

Y(K) А, (К) + JB(K),

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

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

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

Х(К) А(К) + JB(K); Y(K) А(К) + JB(K),

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

Х(К) А(К) -I- JB(K); Y,(K) А (К) + JB(K).

В результате комплексного перемножения спектров по алгоритму (20) на выходе блоков 4 и 5 получаются значения взаимных спектров:

1

52501

12

S (К) Х(К)Y(K);

XV

S (К) Х(К) Y(K)

где К 0,1,2,..., ( - 1),

составляющие взаимных спектровS(К) и S ху, (К) поступают соответственно на входы блока 6, в котором по алго 0 ритму (21) формируются составляющие смеси спектров G(K)L(K) + jM(K) . Сформированный массив значений G (К) обрабатывается блоком 7 в соответствии с алгоритмом (22), результа 5 том обработки является формирование массива вычисленных значений комплексной функции, где действительная часть D (t) F CG (K) :

20 RID,, (x)l С,ЛТ);

IJD,, (tr) c,,, (t).

Отсчеты, хранящиеся в выходном масси- ве блока 7, обрабатываются блоком-8, который из N значений комплексной функции Dj (тг) формирует 2N значений действительной функции корреляции повьшенной точности (т) в соответ- ствии с алгоритмом (23).

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

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

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

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

в него введены первый и второй сумматоры, элемент И, элемент НЕ, счетчик, блок памяти и два блока комплексного перемножения спектров, первые входы обоих блоков комплексного перемножения спектров соединены с вторым выходом блока разделения спектров, первый выход которого подключен к второму входу первого блока комплексного перемножения спектров, выход согласоСоставитель Е.Хуртин Редактор Ю.Середа ТехредМ.Ходанич Корректор Н.Король

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

ВНШПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д,4/5

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

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

(pue.Z

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