Устройство для калмановской фильтрации

 

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

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

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

РЕСПУБЛИК

J (51)5 Н 03 Н 21/00

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

Н A BTОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4326g64/24-24 (22) 10.11.87 (46) 15.05.90. Бюл. М 18 (71) Киевский политехнический институт им. 50-летия Великой октябрьской социалистической революции (72) Ю.с. Каневский и Н.F. Куц (53) 62-50(088.8) (56) Лебедев Е.К., Мясников В.И., Старыгин С.В. Программная и аппаратная реализация фильтра Калмана. Йошкар-Ола, 1985, Рук. деп. во ВНИИТИ, N 2737-85дп.

ÄÄSUÄÄ 1564711 А1

2 (54) УстРойство для кдлидновской

ФИЛЬТРАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах, работающих в реальном масштабе времени при создании информационно-поисковых систем, систем обработки данных и изображений. Цель изобретения - повышение быстродействия. Устройство калмановской фильтрации содержит блоки 1, 4 и 9 памяти произведений, первый блок

2 сумматоров, первый блок 3 регист3 156471 ров, первый регистр 5, второй блок 6 сумматоров, второй блок 7 регистров, блок 8 вычитателей, третий блок 10 сумматоров, третий блок ll регистров, блок 12 сдвиговых регистров, второй регистр 13, блок 14 синхронизации. Цель изобретения достигается за счет введения регистров 5, 13 и блока 12 сдвиговых регистров.

1 з.п. Ф-лы, 2 ил.

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

15 обработки данных и изображений.

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

На Фиг. 1 представлена структурная

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

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

8 вычитателей, третий блок 9 памяти

ЗО произведений, третий блок 10 сумматоров, третий блок 11 регистров,1 блок l2 сдвиговых регистров, второй ре".гистр 13, блок 14 синхронизации.

Блок 1ч синхронизации содержит ге- З5 нератор 15 тактовых импульсов, счет . чик 16 тактовых импульсов, генератор .

17, инвертор 18.

Реализация алгоритма фильтрации

40 осуществляется в соответствии с выражением:

Х(К + 1) = ф(К) Х(К)+К(К) 6Y(K)-Н(К)<

45 .Ф(к)х(к)1 = х (к) + к(к) (к)— — Н(к)Х+(К)) = Х (К) + K(K)D(K)

- х (к) + с(к), . (1) где Х(К). — N — мерный вектор оценки

50 параметров процесса на

К-том шаге, определяемый из описания процесса;

Ф(К) tNxN3- мерная переходная матрица, значения которой

- 55 также определены;

Н(К)-(Ихй) вЂ, мерная матрица наблюдения;, K(K)-(NxM 3 — мерная матрица коэффициентов усиления, рассчитанная для каждого шага вычислений, исходя из априорных статистических данных о процессе;

Y(K) — М вЂ” мерный вектор измерения, определяемый из описания процесса.

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

При умножении матриц на вектор используется метод Пеледу-Лиу, заключающийся в последовательном формировании сумм частичных произведений элементов матрицы на одноименные разряды элементов вектора. Поэтому шаг работы устройства содержит числотактов r,,равное разрядности операндов вектора оценок Х(К), Для обеспечения правильной работы устройства необходимо равенство разрядности элементов векторов Y(K) и Х(К), На адресные входы блока 1 постоянной памяти параллельно поступают одноименные разряды всех N элементов вектора оценок Х(К), начиная с младших. На выходе устройства параллельно получаем одноименные разряды всех элементов вектора Х(К + 1), начиная с младших.

В блоках 1, 4,. 9 памяти произведений записаны не непосредственные зна-, чения соответственно элементов матриц

Ф(К), Н(К) и К(К), а все возможные суммы частичных произведений строк этих матриц на столбец, образованный одноименными разрядами элементов векторов соответственно Х(К), Х (К) и Р(к) .

Для представления i-й суммы частичных произведений требуется r<=

= leg N+n> выходных разрядов блока 1 постоянной памяти, где п1- разряд5 15647 ность элементов матрицы Ф(К), а так как таких сумм N, то разрядность блока 1 составляет S = Nr . Количество

1 выходных разрядов блоков 4 и 9, ис5 ходя из тех же предположении, составляет S2 = (log N + пд)М = Mr и

S = flog gf + и Ч = Nr> °

Так как разрядность операндов матриц ф(К), Н(К) и К(К) не влияет на описание принципа работы устройства, считаем, что г„= r = г = r..Ïóñòü прием во все регистры выполняется по переднему фронту синхроимпульсов, поступающего на их синхровходы, установка в нуль выполняется отрицательным значением на входе установки в нуль регистров блоков 3, 7, 11, а сдвиг - отрицательным значением .на входе управления сдвигом, так как 20 регистры блока 12 работают только в режиме сдвига, считаем, что сдвиг выполняется по переднему фронту синхроимпульса., 25

Обозначим через Х „(1), Х „(2), ° ° °

Х (г ) вектора размерности N, эле с о менты которых образованы одноименными разрядами элементов .вектора оценк() « ) к о) 30 последовательно поступают на адресный вход блока

Е (1), F(2),...,,F (r ) — значения сумм частичных произведений 1-й строки матрицы ф(К) на вектора соответственно Х (1), Х,,(2),..., Х „(r„); жуточные результаты умножения матрицы ф(К) на вектор .Х(К);

X"„(1), Х „(2),..., Х „(r ) - вектора размерности N, образованные одноимен- . ными разрядами элементов вектора экстраполяции Х+(К), которые поступают в качестве адреса на входы блока 4 и регистра

H;(l), Н;(2),..., Н.;(r ) - значе-, ния суммы частичных произведений i-й строки матрицы Н(К) на вектор X „(1)

Х (2),..., Х (r ), образованный одноименными разрядами Вектора зкстрапо ляции Х (К);

H > (1), Н "(2) Н . (г ) — промежуточные результаты умйажения матрицы Н(К) на вектор Х (К);

11 (1), Ь„(2)..., h (r,) — вектор 55 разрядности И, оЪразованный одноименными разрядами элементов вектора

D(K) = Н(К) ° Х" (К);

11 6 у (1), у „(2),...,у „(г, ) — вектора размерности М, образованные одноименными разрядами вектора измерений Y(K);

С! (1), С (2),..., С (г,) - промежуточные результаты умйожения матрицы К(К) на вектор D(K);

В (1?, В -(2),..., В;(г,) — промежуточные результаты вычисления вектора X "(К + 1).

Рассмотрим работу устройства на

К-м шаге.

В исходном состоянии счетчик 16 тактовых импульсов обнулен. Регистры блока 3 сигналом с первого выхода блока 14 синхронизации устанавливаются в нулевое состояние, по входу задания шага работы устройства поступает код номера страницы К, и образует старшие разряды адреса для блоков

1, 4, 9 памяти.

На младшие разряды адресного входа блока 1 поступает вектор X„(1), образованный младшими разрядами (1-м) всех N элементов вектора Х(К).

Из блока 1 считывается значение

F (1) (j = I,N) » представляющее собой сумму частичных прозведений

j -й строки матрицы ф(К) на вектор

Х „(1), F (1) суммируется в j -м сумматоре блока 2 с нулевым содержанием

j -го регистра блока 3 и поступает на вход этого регистра. Считаем исходное состояние первым тактом первым полутактом работы устройства.

В первом такте во втором полутакте состояние счетчика 16 тактов

00...1, передним фронтом синхроимпульса в j -й регистр блока 3 принимается Г„(i).

Во втором такте в первом полутакте состояние счетчика 16 тактовых импульсов 00...10. 8 j -м регистре блока 3 по нулевому значению на входе управления сдвигом осуществляется сдвиг содержимого Е;(1) на один разряд вправо. В (го + .1)-м разряде jro регистра блока 3 (j = 1, N) получаем значение младшего разряда всех элементов вектора Х (К) - вектор

X„(1). В блоке 7 регистр i-й (i

1, М) сигналом с второго выхода генератора 17 блока 14 синхронизации устанавливается в нулевое состояние.

Из блока 4 считывается значение Н .(1) по адресу Х „(1), которое является суммой частичных произведений"i-й строки матрицы Н(К) на вектор Х (1) и, суммируясь в сумматоре 6. с ну1564711 левым содержанием регистра 7.i, поступает на вход регистра 7. i. На адресные входы блока 1 поступает векtop Х „(2), образованный вторыми разРядами вектора оценок X(K). Из блока

5 считывается значение У .(2) и суммируется в сумматоре 2,) с содержи ° J мым ro-ðàçðÿäoâ регистра 3.j, F(1)

«.2- . Ыа входе регистра 3.j получаем

F (2) = Р (2) + У (1) 2

Во втором такте, во втором полу,гакте состояние счетчика 16 тактовых импульсов 00...11.

В регистры. З,j, 7.:j, 5 соответственно принимаются F (2), Н,(1), X (1), В третьем такте в первом .палутакге состояния счетчика 16 00...100. 20

В регистрах 7,. i, З,.j по нулевому зна. ению на входе управления сдвигом существляется сдвиг содержимого соотетственно Н.,(1) и Р .(2) на один разяд вправо. 25

В (r + 1)-м.разрядах регистров 7,i l) 3.j получаем соответственно значения младшего разряда произведения атрицы Н(К) на вектор Х (К) - вектор

„(1) и вектор Х"(r), вектор Х (1) ЗО из регистра 5 переписывается в реистр 13 по сигналу с выхода инверора 18 блока 14. Отрицательным знаением с третьего выхода дешифратоа блока 14 синхронизации регистры

2.j (j = 1, N) устанавливаются в ну евое значение, вектор h„(1) постуПает на вход вычитателя 8, туда же

Поступают младшие (первые) разряды асех элементов вектора измерений 4О

У(К), образуя вектор у „(1). В вычитателе 8 получаем H поразрядных разностей С1 к(1). = у (1) h1(1).

Векторы й„(1) образуют значения младшего разряда элементов вектора

О = у(К) — Н(К)Х+(К) и поступают на адресные входы блока 9„ Значение

С:(1), (j = 1, N) проходит через сумматор 10 1 и суммируется с нулевым содержанием регистра 11.j и содержимым регистра 13 - Х (I), разряды ко горого поступают в цепь переноса в младший разряд сумматоров 10.j . Получаем В (1) =.Хк (1) + С (1), которое

Поступает на вход регистра 11.j Работа остальных узлов устройства ана-. логична первому и третьему тактам.

На входе регистра 3„j получаем вектор F (3) регистра 7,i — H ;(2) = H (1) 2 + H,(2) регистра 5 - Х+(2).

В третьем такте во втором полутакте состояние счетчика 16 00...101. В регистре 3„j, 7. i, 5 и 11. i принимаем соответственно F (3), Н,(2), Х«(2), В;(1) .

В четвертом такте в первом полутакте состояние счетчика 16 00...110.

В регистре 11.1 выполняется сдвиг содержимого регистра 11,j на один разразряд вправо - В ° (1) 2 - значения в

Ф (г,+ 1)-м разрядах регистров 11.1 образуют вектор Х, (1) и равны младшим разрядам вектора оценки Х(К + 1), вектор Х к„,(1) поступает на вход устройства и на входы регистров 12,j ..

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

В четвертом такте ао втором полутакте состояние счетчика 16 00...111, в сдвиговые регистры 12 принимается вектор Х,;(1) и считывается вектор

Х „(5), который поступает на адресный вход блока 1. В регистры 3,j, 7,i, 5 и 11,j принимаются соответственно

Г,(4), H,(3), X+(3) и В„-(2).

Далее работа устройства аналогична приведенным выше тактам.

Таким образом, за счет введения регистров 5 и 15 время выполнения одного шага алгоритма Калмана удалось сократить до Т„ = tr, а использование входа переноса в младший разряд блока 10 сумматоров позволило исключить последний сумматор в прототипе, что дает возможность повысить быстродействие устройства.

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

1. Устройство для калмановской

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

1564711

7вчаюйм наумом

vemvve

moemult

/дж/Я

Аиюг 22

Ar483

lw Ы74

АвММ

Фиа 2

Составитель В. Башкиров

Редактор И. Бандура Техред Л.Сердюкова Корректор 3, Лончакова

Заказ 1165 Тираж 648 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 191 разрядностью каждого из выходов, равной сумме разрядностей операнда переходной матрицы системы и логарифма по основанию два от размерности вектора состояния, блок вычитателей, соединенный первым входом с информационным входом устройства, вторым входом - с первым выходом второго блока регистров, информационный вход 1р которого соединен с выходом второго блока сумматоров, а второй выход— с входом второго блока сумматоров, подключенного группой входов к группе выходов второго блока памяти про- 15 изведений, с разрядностью каждого из выходов, равной сумме разрядностей операнда переходной матрицы сис-. темы и логарифма по основанию два от размерности вектора состояния, третий 20 блок регистров, соединенный информационным входом с выходом, а выходом " с входом третьего блока сумматоров, подключенного группой входов к группе выходов третьего блока памяти про- изведений, с разрядностью каждого входа, равной сумме разряднос-.ей операнда переходной матрицы системы и логарифма по основанию два от размерности вектора состояния, выход блока вычитателей соединен с адресным входом третьего блока памяти про-. изведений, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, введены два ре- 35 гистра и блок сдвиговых регистров, первый выход первого блока регистров через последовательно соединенные первый и второй регистры подключен к входу переноса третьего блока сумматоров, второй выход третьего блока регистров, .являющийся выходом устройства, через блок сдвиговых регистров соединен с адресным входом первого блока памяти произведений, первый, второй и третий выходы блока синхронизации подключены к входам сброса соответственно первого, второго и третьего блоков регистров, соединенных входами синхронизации и входами управления сдвигом с входом синхронизации. первого регистра и четвертым выходом синхронизации, пятый выход которого подключен к входам синхронизации второго регистра и блока сдвиговых регистров.

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