Коррелятор

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах, применяемых для цифровой обработки сигналов, работающих в реальном масштабе времени , например в геофизике, медицине . Цель изобретения - повышение быстродействия.Коррелятор выполняет вычисление корреляционной функции М-разрядной входной последовательности X(i) с одноразрядными корреляционными коэффициентами а(1). Специфическая организация вычислительных ячеек позволяет повысить частоту поступления входных сигналов для их последующей обработки. 2 ил. S (Л

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

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

РЕСПУБЛИН (l9) (И) А1 (д() 4 G 06 F 15/336

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3848797/24-24 (22) 24.01.85 (46) 15.03.88. Бюл. У 10 (7 1) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.И. Лозинский, Ю.С. Каневский (SU), Роман Выжиковски (PL) и А,В. Выжиковска (SU) (53) 681.32(088,8) (56) Ме Cabe и др. "pew algorithus

ahd architectures for VLSI GEC,—

Journal of Science Technology, v. 48, У 2, 1988, стр. 66-75. (54) КОРРЕЛЯТОР (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах, применяемых для цифровой обработки сигналов, работающих в реальном масштабе времени, например в геофизике, медицине. Цель изобретения — новьапение быстродействия. Коррелятор выполняет вычисление корреляционной функции

И-разрядной входной последовательности X(i) с одноразрядными корреляционными коэффициентами а(). Специфическая органиэация вычислительных ячеек позволяет повысить частоту поступления входных сигналов для их последующей обработки, 2 ил.

1381539

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

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

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

На фиг. 1 обозначено: — данные„ не входящие в результат; р — длина преобразованной последовательности, Коррелятор (фиг. 1) содержит матрицу из вычислительных ячеек 1,1.1.—

1,i. j (i = 1„2,.,М вЂ” номер строки, 1, 2,...,N — номер столбца), информационный вход 2, в каждой ячейке матрицы1 первый выход 3, второй вход 4, второй выход 5 (кроме ячеек последней строки), третий вход 6 (вход 6 ячеек первой строки являет"R входом задания нуля коррелятора), третий выход 7 (кроме ячеек последней строки), четвертый вход 8 (входы

8 ячеек первой строки является входам запрета формирования суммы кор1 релятора),. четверть и выход 9 резуль-тата.

Вычислительная ячейка (фиг. содержит первый элемент 10 задержки, элемент И 11, второй элeìåíò 1". задержки, сумматор 13, третий, четвертый и пятый элементы 1,. 15 и 16 задержки.

Коррелятор выполняет вычислени-. корреляционной функции И-разрядной входной последовательности X(i) с одноразрядными корреляционными коэффициентами а(1) по формуле у(Р) = a(i ) (i + р), (1) где у(р) — р-й вычислительный результат;

N — количество корреляционных коэффициентов.

Рассмотрим работу коррелятора, Для наглядности будет опи:.àí случай И = 4, M = 6.

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

Все тактируемые элементы 10, 12, 14, 15 и 16 задержки всех ячеек 1 управляются одним и тем же сигналом.

11а фиг. 1 и 2 условно не изображены

-,aêòèðóKLt(Hå входы ячеек 1 и всех тактируемых элементов 10, 12, 14, 15 и 16 задержки.

Входные данные X(i ) и коэффициенты a(i) поступают на входы коррелятора., как показано на фиг. 1.

Так как направление передачи входных данных совпадает с направлением передачи результата, то нет несбходимости проводить предварительное обнуление тактируемьж элементов

10, 12, 14,. 15 и 6 задержки, Вычисления, IIpовг димые в каждой ячейк»- 1. описаны с момента, когда в этой ячейке начинаются полезные вычисления,.

Ирием информации в тактируемые элементы 10, 12, 14, 15 и 16 задержки пе>шествляется в на .але каждого такта.

В пер чычис яе ,0 и - ни-:..-1 (ВоМ гакте в ячейке 1. (. 1. ñÿ одноразрядное произве0)х (О), где х (0) — самый разряд х(0).

:- ро, такте в я .»йке 1. 1. 1.

Lñü а(0)х (1); г ячейкс:. а(0)х (О) ., лапп пн

BLi В >Lë roc J я р

1, 1

В пятом такте в ячейке 1,1.1. вычисл -ется а(0)х"(4); ь ячейке

i.1,2 - а(0)х (3): в ячейке 1.1.3 .-(О х- (2); в ячейке 1.1.4 — а(С)х"(1), ч ячейке 1.1.5 — а(0)х (О); в ячей8 третьем такте в ячейке 1.1.1.

1 вычисляется а(0)х ь. 2); в ячейке

1 1,.: — а(О)х (1); в ячейке 1.1.3 ,10 а 0)х (С); в ячейке 1.2.1

a(i)x (i).

- = n

В че -вертом такте в ячейке 1. 1.1, вычисляется а(0)х (3); в ячейке

1,2 - а(0)х (2); в ячейке 1,1.3

:-(0):. (1); в ячейке 1. 1. 4 — а(0)х (0); я ейке 1 2. 1-+a(1)х (1+1) в:

t 3

1 1 ячейке, . 2 2 —,Я а(i)х (i)+Сz (0)

l »0 (О) перенос, возникшии в ячеи ь.е 2-го стопбца обрабатывающей, пер-вы» разряд;л входных чисел при вычисленv»r y(0).

1381539

< ке 1, 2, 1 — a(i )x- (i+2); в ячей1ео ! ке 1. 2. 2 — a (i ) x (i+1) + С /1; в ячейке 1. 2.3 — .с a(i)x (i) +

+ С, /0); в ячейке 1.3.1 г

a(i)x (i) .

В шестом такте в ячейке 1. 1. 1.

1 вычисляется a(0)x (5); в ячейке

1. 1.2 — а(0)х (4); в ячейке 1. 1.3,— а(0)х (3); в ячейке 1. 1.4 — a(0)x (2); в ячейке 1. 1.5 — а(0)х (1); в ячейке 1.1.6 — a(0)x (0); в ячейке 1.2.1

a(i)x (i+3); в ячейке 1.2.2

i" "о

1 ,(а(i)х (i+2); в ячейке 1.2.3

-о

1 20

a(i)x (г+1)+С (1); в ячейке 1.2.41=0 2

a(i)x (i)+C (0); в ячейке 1.3. 1

*о

2 ,Е ай)х (i+1); . в ячейке 1.3. 2—

*о

Яa(i)x (i)+C (О), 1е 0

В восьмом такте в ячейке вычисляется а(0)х (7); в яче

1. 1.2 — a(0)x (6) е в ячейке

a(0)x 5); в ячейке 1.1.4 в ячейке 1.1.5 — а(0)х (3);

1.1.6 — a(0)x (2); в ячейке 1

1.1.1. йке

3 а(0)х (4); в ячейке .2.1

В седьмом такте в ячейке 1. 1. 1. вычисляется a(0)x !(6); в ячейке 30

1.1.2 — a(0)x (5); в ячейке 1.1.3 а(0}х (4); в ячейке 1. 1.4 — а(0)х4 (3); в ячейке 1.1.5 — а(0)х (2); в ячейке

1. 1.6 — a(0)x (1); в ячейке 1.2. 1 ( a(i)x (i+4); в ячейке 1,2.2—

-о

1 (Я.а(г)х (1+3)+Сг (3); в ячейке

) о

1.2.3 — Хa(i)х (i12)+C (2); в ячейФ

40 ке 1 ..2.4 - a(i) x (i+1)+Cz (1); в, = о ячейке 1. 2. 5-,Яа(д ) х (i )+C, (0); в

1 ° Ф

1хО

1 ке 1. 3. 1 —,Я a(i ) х (i+2); в ячейке 45 ка

1

1.3,2 — a(i)x (i+1)+C> в ячейке

1кО

1.3.3 —,Е.a(i)x (i)+((0); в ячей4=0 3

50 ке 1.4.1 — у (О) =: a(i)x (i) .

)=о

a(i ) х (i+5); в ячейке 1. 2. 2

Ka(i)x (i+4)+С (4); в ячейке 1.2.3

a(i)x (i+3)+C (3); в ячейке

i-o г

1. 2.4 - а(i)х (i+2)+C (2); в

i -- О г и . 4 ячейке 1.2.5 - a(i)x (i+1)+C (1) е= О

1 в ячейке 1.2.6 -Я а() )х (i)iC>(p) .

) =()

1 в ячейке 1.3.1 — а(i)x (i+3) в

)=о

1 ячейке 1.3.2 - a(i)x (i+2)+С (2); в

i x()

3= Ф

1 ячейке 1.3.3 - а(г)х (i+1)+C> (1);

)кО в ячейке 1.3.4 - a(i)x (i)+С (О);

4 в ячейке 1.4. 1 — y (1)

=2 а(з. ) х (i+1); в ячейке 1. 4. 2

)»0

1 у (0) = .,а(i)хг (i)+С4(0) .

В девятом такте в ячейке 1.1.1. вычисляется а(0)х (8); в ячейке 1.1.2 а(О)х (7); в ячейке 1.1.3 — a(0)x (6); в ячейке 1. 1.4 — a(0)x (S); в ячей4 ке 1.1.5 — a(0)x (4); в ячейке 1.1.65 а(0) х (3); в ячейке 1. 2. 1

a(i)x (i+6); в ячейке 1.2.2 (1 а(1)х (i+5)+C (5); в ячейке 1.2.31

Гa(i)х (i+4)+C (4); в ячейке 1.2.4f x(i)x ((е))ей (3)) е ячейке 1.2.5(Е. a(i)x (г+2)+С (2); в ячейке 1.2.6 и . 4

1=0 е

«3» а(г )х (i )x (1+! )+С (1); в ячейке

1

1.3.1. a(i)х (i+4); в ячейке 1.3.2.)еО

1 1 a(i)x (i+3)+C (3); в ячейке =а

1.,3. 3. - a (i ) x (i+2)+C (2); в к О ячейке 1.3. 4 —.Я а(i)х (г+1)+С (1);

3 в ячейке 1.3.5 -„Е а(г)х (i)+C, (О), 5 ° 4

1 в ячейке 1.4.1 — у (2) = a(i)x

) еО (i+2); в ячейке 1. 4. 2 — у (1) 1381539

45

55

«

« а (г )x (i+1) +!: (1); в ячейке

=о

"4

«

1.4. 3 — уз уз (О) =,г а (г )хз (i )+

+С2 (О), «-о

В десятом такте в ячейке 1.4.4. вычисляется у (О); в ячейке 1.4.3 у (1); в ячейке 1.4.2 — у (2); в ячейке 1.4.1 — у«(3).

В одиннадцатом такте в ячейке

1.4.5 вычисляется у (О); в ячейке

1 ° 4.4 — у (1); в ячейке 1.4.3

4 у (2); в ячейке 1. 4. 2 — у (3); в ячейке 1. 4, 1 — у (4) .

В двенадцатом такте в ячейке

1.4.6 вычисляется у"(О); в ячейке

1.4.5 — у«(1); в ячейке 1.4.4

y (2); в ячейке 1.- .3 — у (3); в ячейке 1.4.2 — у (4); в ячейке

1.4. 1 — у (5).

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

Обработка нового входного массив..:

Х может начина«ься в следующем такте после поступления на первый вход коррелятора последнего данного из предыдущего массива Х. Одновременно с приходом на п«рвыи вход 2 ячейки

1 ° 1. 1 х (О) на ее eòîðîé вход должен быть подан а(О} из новой корреляционной последовательности и вычисления будут продолжены аналогич-ным образом.

В случае, когда коррелятор будет работать только с одним набором корреляционных коэффициентов, тогда тактируемые элем нты 12 задержки могут быть исключены из конструкции вычислительной ячейки 1. В этом случае корреляционные коэффициенты а(р) (р = О, 1, ..., N-1) постоянно заведены на вторые входы 4 ячеек 1 (Р+1) . 1.

Так как длина столбца коррелятора (М) соответствует требуемой разрядности чисел преобразованной последовательности, а при вычислении корреляции производится N суммирований, то количество зна «ащих разрядов чисел входной последовательности должно быть на )1о,-;.,"1 меньп«е, чем в чи5

30 слах преобразованной послед, вательнос и ()Л - ближайшее большее целое) формул а и з о б р е т е н и я

Коррелятор, содержащий матрицу из Г1 столбцов «где N — длина корреляционной последовательности) и M строк (М -разрядность чисел входной последовательности) вычислительных ячеек, каждая из которых содержит элемент И, сумматор и четыре элемента задержки, первый вход элемента И соединен с входом первого элемента задержки и является первым входом вычислительной ячейки, выход первого элемента задержки является первым выходом выч «слительной ячейки, второй вход эле.-«ента И соединен с входом второго элемента задержки и является вторым входом вычислительной ячейки, выход второго элемен та «адержки является вторым выходом вычислительной ячейки, выход элемента И соединен с первым информационным входом сумматора, вход переноса которого является третьим входом вычислительной ячейки, выход перенос и информационныи .- .,D .ñ !I сумматора соединены соответств. нно с входами тгетьего и четвертого элементов задержки, выход третьего элемента заде!.жки является третьим выходом вь«чисг«ительной ячейки, первый вход каждой

Бь«числительной ячейки llppBol столб

IIa Isaòðèïû является соответствующим информационным входом коррелятора, первые входы вы иглительных ячеек к«ж. о«о последуюшего столбца матрицы ".ñ единены соо. ветс Tpp!IHA с первыми выходами вычис III ." åëbíüãõ ячеек предыдущего столбца матри«п., вторые входы вычислительных ячеек первой строки матрицы являются входами за.дания соответствующих корреляционных коэффициентов коррелятора, третьи входы вычислите-ьных ячеек первой строки матрицеi являются входами задания нулевого явления корреля; ора, в каждом столбце матрицы вторые и третьи входы каждой последующей вычислительной ячейки столбца соединены соответственно с вторым и третьим выходами предыдущей вычислительной ячейки того же стобца, о т л и ч а ю шийся тем, что, с целью повышения быст««одействия, в каждук вычислительную я ейку матрицы введен пятый элемент задержки, вход которого соединен с выходом четвертого элемен1381539 тора. а, а) с(а) (а) та задержки, а выход является четвертым выходом вычислительной ячейки,, второй информационный вход сумматора является четвертым входом вычислительной ячейки, четвертые входы всех вычислительных ячеек первого столбца являются входами запрета формирования суммы корреля-.ора, Л мЯ к

СЛ оЬ/ахи каррелруианЮЫМ Урруд мфОР . Р... x (u)xi ) x (z)x (i)» (." x ®xx(z)x (i) x Ф" в каждой строке матрицы четвертый выход предыдущей вычислительной ячейки соединен г четвертым входом последующей вычислительной ячейки, четвертый вьвсод последней вычислительной ячейки матрицы явпяется соответствующим выходом результата корреля 7(/) u(s) 7(r) и(г) о

1381539

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

Техред М.Ходанич

Редактор М. Петрова

Корректор М. Демчик

Заказ 1186/47 Тираж 704

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

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

Подписное

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