Коррелятор

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах, пpимeняe 6lПC для цифровой обработки сигналов, работающих в реальном масштабе времени, например в геофизике, медицине. Цель изобретения - повьшение быстродействия . Коррелятор содержит матрицу из вычислительных ячеек 1.1.1-1.i.j (i 1,2М- номер строки, j 1, 2,..., N - номер столбца), входы 2, 4, 6, 8, выходы 3, 5, 7 9 Ю кая.оо ел со сд результат Фиг.1

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

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

РЕСПУБЛИН

„;80„„1357975 (5g 4 G 06 F 15/336

" а . -ааИ . Л" «а °: ф(а%"а а С а ма

"3

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

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

by о„,, о с

di . P -! оо

4 -! + о .+ 1

+ !!-о !! оо ок-! о ос о, !!y

+ о

+ 1

+О

Порядок следаА! им корреляисюн ны.г «оеар(!!ис!и

mad с соаосдео! слмующин Фв неннын сдйпо! о t n! око «!

° 0 оо

+о с!

i!y ом!

t оа оо

+с!

1, н-а о

: ю-и!

" !!»!сс!А !*)!со !с .+ с с с

- 4ЖсЖ»«iy! + +!

" "сс! !с!!4» +++

I I I I l I

III.. III . lit

I l l I1 I l l l

1а ББ ФББ . 4ББ ас» ЯЕ . Уе У " » " ! " + пм кхм гл ч д и

Иар ааи аааааааии аа а ааааааа ааааааааа «а ааааа о соотоетстЬукчцим арвненнын аЖигоч,ащмооФ

+ -Юяч!е,не Фс!дои!ее Б

pezyn!mam

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3848794/24-24 (22) 24.01.85 (46) 07.12.87. Бюп. М 45 (7 1) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) P.Âûæèêoâñêè, Ю.С.Каневский и В.И.Лозинский (53) 681.32(088.8) (56) Мс.СаЪе, В.Arembepola и др. New

algorithms and architectures for

VLSI. — GEC Journal of Science and

Technology. 1982, V. 48, Р 2, р. 6675 ° . (54) KOPPEJIHTOP (57) Изобретение относится к вычислительной технике и может быть исполь. зовано в специализированных вычислительных устройствах, применяемых для цифровой обработки сигналов, работающих в реальном масштабе времени, на.пример в геофизике, медицине. Цель изобретения — повышение быстродействия. Коррелятор содержит матрицу из вычислительных ячеек 1. 1. 1-1.i,J (i= 1,2,..., М вЂ” номер строки, j = 1, 2,..., N — - номер столбца), входы 2, 4, 6, 8, выходы 3, 5, 7, 9, 10 каж1357975 дой вычислительной ячейки. Корреля- где у(р) — р-й вычисленный результат ю

Э тор выполняет вычисление корреляци- N — - количество корреляционных коэффионной функции М-разрядной входной циентов. Специфическая органиэация последовательности x(i) с одноразряд- вычислительных ячеек позволяет повы- . ными корреляционными коэффициентами сить частоту поступления входных сиг.— налов для их последующей обработки.

a(i) по формуле у(р) = .Е a(i)x(i+p) 2 ил. .о

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

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

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

Коррелятор (фиг.1) содержит матри,цу из вычислительных ячеек 1.1,11,i.j (i = 1,2, ° .., М вЂ” номер строки, 20

1,2,..., N — - номер столбца), информационный вход 2, первый выход 3 каждои вычислительной ячейки, второй вход 4 каждой ..вычислительной ячейки

25 (вход 4 ячеек первой строки является входом задания корреляционных коэффициентов коррелятора), второй выход 5 каждой вычислительной ячейки, кроме ячеек последней строки, третий вход 6 каждой вычислительной ячейки (вход 6 ячеек первой строки является входом задания нуля коррелятора), третий выход 7 каждой вычислительной ячейки, кроме ячеек последней строки, четвертый вход 8 каждой вычислительной 35 ячейки (вход 8 ячеек первой строки является входом запрета формирования суммы коррелятора), пятый выход 9 каждой вычислительной ячейки, кроме ячеек последней строки, и выход 10 ре-4б зультата.

Вычислительная ячейка (фиг. 2) содержит первый элемент 11 задержки, элемент И 12, второй элемент 13 задержки, сумматор 14, дополнительный элемент И 15, пятый 16 задержки, третий 17 и четвертый 18 элементы задержки.

Коррелятор выполняет вычисление корреляционной функции М-разрядной входной последовательности x(i) с одноразрядными корреляционными коэффициентами а(х) по формуле

И-1 у(р) = a(i)x(i + р), (1)

i=-О где у(р). — р-й вычисленный результат, N — количество корреляционных коэффициентов.

Коррелятор работает следующим образом.

Входные данные x(i), поступив на первый вход 2 коррелятора, в процессе вычисления передаются во все вычислительные ячейки, в которых они необходимы для вычисления выражения (1).

Все элементы 11 13, 16, 17 и 18 задержки всех вычислительных ячеек

1.1.1-1.i.j.óïðàâëÿþòñÿ одним и тем же тактовым сигналом, входы которого не показаны.

В начальный момент времени все элементы 11, 13, 17 н 18 задержки, обнулены. В элементе 16 задержки записана логическая "1". Входные данные

x(i) и коэффициенты a(i) поступают на первый и второй входы коррелятора (фиг.1) . В первом столбце коррелятора вычисляется .у(о), во втором— у(1), в третьем — у(2), в четвертому(3) ф в пятом -. y(4) г

1357975

45 (+1) = >x «+1) a(t) = a(1t-1)шоЖ);

Rьы (t) = Rв (") 3

В вычислительной ячейке 1 выполняются следующие преобразования вход- ных и выходных данных: а „. (С+1) = à,„(t); х (t+1)

x „(t); c,, „„(t+1) = у (t)R,„„(t-1.) x х с (t) Ч у (t) R,„(t-1) х,„(t) х

10 х а „(С) v с,„(t) х 1„(t) a „(); у)(i+1) = у (t)R (t-1) Q+) с,„(t) {+) О+ х,„().а,„(С); R „„(t) = R,Ä(t-1), где j — номер ячейки 1 в столбце, х „(t) — j-й разряд входного данного

Ьх

x(t), поступивший на первый вход 2 ячейки 1 в момент вре-20 мени t;

a (t) †корреляционн коэффициент, 5« поступивший на второй вход 4 ячейки 1 в момент времени t с (t) — перенос из младшего разряда, 25

8х поступивший на третий вход 6 ячейки 1 в момент времени

t(c<, (с) = О);

R (t — 1)- сигнал запрета формирования ех суммы, поступивший на четвер- -) тый вход 8 ячейки 1 в момент времени (t-1); у ?(t) — состояние четвертого выхода

10 ячейки 1 в момент времени t;

35 х (t+1) — j-й разряд входного данььа ного x(i), поступивший на первый выход 3 ячейки 1 в момент времени (t+1); а (1+1) — корреляционный коэффици- 40 ент, поступивший на второй выход 5 ячейки 1 в момент" времени (t+1), при этом с >„„(t+ 1) перенос B старший .paз» 50 ряд, поступивший на третий выход 7 ячейки 1 в момент времени (t+1), при этом с у„(t+1) с (t+1);

R 8ык (t) — сигнал запрета формирования суммы, поступивший на пятый . выход 9 ячейки 1 в момент времени t при этом

+ — сумма по модулю 2.

Сигналы запрета формирования суммы подаются на столбцы в такой последовательности: в 14 такте — 3-й столбец, в 15 такте — 1-.й столбец, в

16 такте — 4-й столбец, в 17 такте

2-й столбец, в 18 такте — 5-й столбец, в 19 такте — 3-й столбец, в 20 такте — 1-й столбец и т.д.

Порядок поступления сигнала запрета формирования суммы.

I. Период поступления сигнала запрета формирования суммы равен N.

II. Наличие сигнала запрета формирования суммы соответствует логическому нулю.

I. Для N = 2i+1, i = 0,1,2... В нулевом такте (за такт до поступления первого данного) сигнал подается на вход первого столбца, в первом такте — на (N+3) /2 столбец, во втором такте — на 2 столбец, в третьем такте — на (N+5) /2 столбец, в четвертом такте — на 3 столбец, в пятом такте— на (N+7) /2 столбец, в (р+2) /2 такте (р (N/х!-1, р = 2i) — на р-й столбец, в (р+4) /2 такте — на (М+2р+1) /2 столбец, в (N-3) такте — íà (N-1) /2 столбец, в (N-2) такте — íà N-й стобец, в (N-1) такте — на (N+1) /2 столбец.

В N такте сигнал подается на 1 столбец и т.д.

Для Я = 2i, i = 0,1,2... В нулевом такте сигнал подается на вход первого и (N/2+1)-ro столбцов, во втором такте — на 2 и (N/2+2)-й столбцы, в четвертом такте — на 3 и (N/2 + 3)-й столбцы, в (р+2) /2 такте (р (N/2-1, р = 2i) — на р-й и (N/2+р) -й столбцы, в (N-2) такте — íà N/2 и N столбцы.

В N такте сигнал подается на 1 и (N/2+1)-й столбцы и т.д.

II. г(8-1)(/ modN; Т (N;

T -=

modN 1N; T N;

I2(S-1)

1,2,3...

Подставляя номер столбца S в уравнение (2), можно вычислить номер такта Т, в котором должен быть подан сигнал запрета формирования суммы на этот столбец.

Перед началом вычисления корреляции нового входного массива не нужно

|проводить обнуление всех элементов

11 13, 17 и 18 задержки. Достаточно подать сигнал запрета формирования суммы на четвертый вход 8 ячейки

1.1. 1 за такт до поступления первого

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

Так .как длина столбца коррелятора

М соответствует требуемой разрядности чисел преобразованной последователь-. ности, а при вычислении производится . N суммирований, то количество значащих разрядов чисел входной последовательности должно быть на 7 1og N t меньше, чем в числах преобразованной последовательности (3A(— ближайшее большее целое).

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

Коррелятор, содержащий матрицу изN столбцов (где N — длина корреляционной последовательности) и М строк (где М вЂ” разрядность чисел входной последовательности) вычислительных ячеек, каждая из которых состоит из элемента И, сумматора, первого, второго, третьего и четвертого элементов задержки, причем первый .вход элемента И объединен с входом первого элемента задержки и является первым

35 входом вычислительной ячейки, выход первого элемента задержки является первым выходом вычислительной ячейки, второй вход элемента И объединен с входом второго элемента задержки и является вторым входом вычислительной ячейки, выход второго элемента задержки является вторым выходом вычислительной ячейки, выход элемента

И соединен с первым входом сумматора, 4 второй вход которого является третьим входом вычислительной ячейки, первый и второй выходы сумматора соединены с входами третьего и четвертого элементов задержки соответственно, выходы которых являются третьим и четвертым выходами вычислительной ячейKH соответственно, первый вход каждой вычислительной ячейки первого столбца является соответствующим информационным входом коррелятора, первые входы вычислительных ячеек каждого последующего столбца соединены с первыми выходами вычислительных ячеек предыдущего < толбца соответственно, вторые входы всех вычислительных ячеек первой строки являются входами задания корреляционных коэффициентов коррелятора соответственно, третьи входы которых являются входами задания нуля соответственно, в каждом столбце вторые и третьи входы каждой последующей вычислительной ячейки столбца соединены с вторым и третьим выходами предыдущей вычислительной ячейки столбца соответственно, отличающийся тем, что, с целью повышения быстродейст-. вия, в каждую вычислительную ячейку введены дополнительный элемент И и пятый элемент задержки, вход которого, является четвертым входом вычислительной ячейки, выход пятого элемента задержки соединен с первым входом дополнительного элемента И и является пятым выходом вычислительной ячейки, второй вход дополнительного элемента И соединен с выходом четвертого элемента задержки, выход дополнительного элемента И,подключен к третьему входу. сумматора, четвертые входы всех вычислительных ячеек первой строки являются входами запрета формирования суммы коррелятора, в каждом столбце четвертый вход каждой последующей вычислительной ячейки столбца соединен с пятым выходом предыдущей вычислительной ячейки, четвертый выход,)-й (z = 1,2,... М, j = 1,2,...

N) ;чейки является соответствующим выходом результата коррелятора.

1357975

Составитель Е.Ефимова

Техред М. Ходанич Корректор Бутяга

Редактор О.Головач

Заказ б001/51

Тираж 671 Подписное

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

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

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