Устройство для калмановской фильтрации Советский патент 1990 года по МПК H03H21/00 

(21)432696V24-2A

(22)10.11.87

) 15.05.90. Бюл. № 18

(71)Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции

(72)Ю.С. Каневский и Н.Е. Куц (53) 62-50(088.8)

(56) Лебедев Е.К., Мясников В.И., Старыгин С.В. Программная и аппаратная реализация фильтра Калмана. Йошкар-Ола, 1985, Рук. деп. во ВНИИТИ, № 2737-85Дп.

«

(5k) УСТРОЙСТВО ДЛЯ КАЛМАНОВСКОЙ ФИЛЬТРАЦИИ

(57) Изобретение относится к вычислительной технике и может быть использовано в устройствах, работающих в реальном масштабе времени при создании информационно-поисковых систем, систем обработки данных и изображений. Цель изобретения - повышение быстродействия. Устройство калмановс- кой фильтрации содержит блоки 1, 4 и 9 памяти произведений, первый блок 2 сумматоров, первый блок 3 регист3156 1711

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

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

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

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

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

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

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

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

х(к + 1) KK)X(K)+K(K)-ЈY(K)-H(K)

хФ(К)Х(К)3 Х(К) + К(К) Y(K) - - Н(К)Х(К) Х(К) + K(K)D(K) ,

Х(К) + С(К),(1)

где Х(К). - N - мерный вектор оценки

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

Ф(К) - мерная переходная мат рица, значения которо также определены;

H(K) - мерная матрица наблюдения;,

0

0

5

0

5

0

K(K) - мерная матрица коэффициентов усиления, рассчитанная для каждого шага вычислений, исходя из априорных статистических данных о процессе;

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

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

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

Для представления i-й суммы частичных произведений требуется г выходных разрядов блока 1 постоянной памяти, где п,- разряд515

ность элементов матрицы 4(К), а так как таких сумм N, то разрядность блока 1 составляет S Nr . Количество выходных разрядов блоков 4 и 9, исходя из тех же предположений, составляет S2 ( + n2)M Мг2 и 5Э + Nr3 .

Так как разрядность операндов матриц ф(К), Н(К) и К(К) не влияет на описание принципа работы устройства, считаем, что г г2 г3 г..Пусть прием во все регистры выполняется по переднему фронту синхроимпульсов, поступающего на их синхровходы, уста- новка в нуль выполняется отрицательным значением на входе установки в нуль регистров блоков 3, 7, 11, а сдвиг - отрицательным значением на входе управления сдвигом, так как регистры блока 12 работают только в режиме сдвига, считаем, что сдвиг выполняется по переднему фронту синхроимпульса. ,

Обозначим через Хк(1), Хк(2),... X (го) вектора размерности N, элементы которых образованы одноименными разрядами элементов вектора оценки Х(К), Хк(1), Хк(2),..., Хк(г0), последовательно поступают на адресный вход бло ка 1;

Fj(1), Fj(2),...,Fj(r0) - значения сумм частичных произведений j-и строки матрицы 44К) на вектора соответственно Хк(1), Хк(2),..., Xk(r0);

Fj(1), Fj(2),...,Fj(rc) - промежуточные результаты умножения матрицы ф(К) на вектор Х(К);

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

Hid), Н,(2),..., H-.(rJ - значения суммы частичных произведений 1-й строки матрицы Н(К) на вектор Х(1), Х(2),..., Х(г0) , образованный одноименными разрядами вектора экстрапо- ляции Х(К);

Н .(1), Н| (2)Н -(г0) - промежуточные результаты умножения матрицы Н(К) на вектор Х(К);

VJ), V2),... hK(r0) - вектор разрядности М, образованный- одноименными разрядами элементов вектора D(K) Н(к).-Х(К);

5 0

5

0

0 с

«

5

5

16

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

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

Bj(1), Bj(2),..., Bj(re) -промежуточные результаты вычисления вектора Х(К + 1).

Рассмотрим работу устройства на К-м шаге.

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

На младшие разряды адресного входа блока 1 поступает вектор Хк(1), образованный младшими разрядами (1-м) всех N элементов вектора Х(К). Из блока 1 считывается значение Fj(O (J 1,N), представляющее собой сумму частичных прозведений j-и строки матрицы ф(К) на вектор Хк(1), Fj(1) суммируется в j-м сумматоре блока 2 с нулевым содержанием j-ro регистра блока 3 и поступает на вход этого регистра. Считаем исходное состояние первым тактом первым полутактом работы устройства.

В первом такте во втором полутакте состояние счетчика 16 тактов 00...1, передним фронтом синхроимпульса в j-и регистр блока 3 принимается Fj (1) .

Во втором такте в первом полутакте состояние счетчика 16 тактовых импульсов 00...10. В j-м регистре блока 3 по нулевому значению на входе управления сдвигом осуществляется сдвиг содержимого F-(1) на один разряд вправо. В (г0 + 1)-м разряде j- го регистра блока 3 (j 1, Ю получаем значение младшего разряда всех элементов вектора Х(К) - вектор Х(1). В блоке 7 регистр 1-й (i 1, М) сигналом с второго выхода генератора 17 блока 14 синхронизации устанавливается в нулевое состояние. Из блока 4 считывается значение Н-(1) по адресу Х(1), которое является суммой частичных произведений Ч-й строки матрицы Н(К) на вектор Х(1) и, суммируясь в сумматоре 6.1 с ну7156

Левым содержанием регистра 7.i по- Јтупает на вход регистра 7-i. На адресные входы блока 1 поступает вектор Хк(2), образованный вторыми разрядами вектора оценок Х(К). Из блока считывается значение F.(2) и суммируется в сумматоре 2J с содержимым г0-разрядов регистра 3«j, F(1)x 2-1. На входе регистра 3.J получа-

feM

F(2) F.(2) + F,(1) 2-l J J j

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

В регистры 3.jj 7. j 5 соответственно принимаются F . (2), Н(1), Х(1)

В третьем такте в первом полутак- Ve состояния счетчика 1б 00...100. 3 регистрах 7.i, 3.j по нулевому значению на входе управления сдвигом осуществляется сдвиг содержимого соответственно Hj(l) и F (2) на один разряд вправо.

В (г + 1)-м разря дах регистров 7.1 /И 3.J получаем соответственно значе- йия младшего разряда произведения Матрицы Н{К) на вектор Х(К) - вектор (1Ц(1) и вектор Х(г), вектор Х(1) из регистра 5 переписывается в ре- j-истр 13 по сигналу с выхода инвертора 18 блока 1. Отрицательным зна- нием с третьего выхода дешифрато- а блока Ik синхронизации регистры I2..J (j 1, N) устанавливаются в ну- jieeo e значение, вектор Ьк(1) посту- (пает на вход вычитателя 8, туда же (поступают младшие (первые) разряды Ьсех элементов вектора измерений tf(K) , образуя вектор ук(1). В вы- митателе 8 получаем М поразрядных разностей dK(1) yk(O hK(1).

Векторы dK(1) образуют значения Младшего разряда элементов вектора DK y(K) - Н(К)Х(К) и поступают на адресные входы блока 9 Значение Cj(l), (j 1, N) проходит через сумматор Ю-j и суммируется с нулевым содержанием регистра 11 .j и содержи- мым регистра 13 - Х(1), разряды которого поступают в цепь переноса в младший разряд сумматоров 10.J. Получаем В .(1) Х(1) -4- Cj{1), которое Поступает на вход регистра . Pa- бота остальных узлов устройства аналогична первому и третьему тактам. На входе регистра 3-J получаем вектор Fj(3) регистра 7Д н .(2)

18

Н,(1)2- + Н.(2) регистра 5 - Х(2) . в третьем такте во втором полутакте состояние счетчика 16 00...101. В регистре 3.J, 7.1, 5 и 11 Л принимаем соответственно F (3), Н (2), Х(2), В (1). J

В четвертом такте в первом полутакте состояние счетчика 16 00...110. В регистре 11.j выполняется сдвиг содержимого регистра ll.j на один раз- разряд вправо - Bj(l)-2-T, значения в (Г0+ 1)-м разрядах регистров 11,j образуют вектор Хк+(1) и равны младшим разрядам вектора оценки Х(К +1), вектор X k+,(l) поступает на вход устройства и на входы регистров 12,j.

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

В четвертом такте во втором полутакте состояние счетчика 16 00...111, в сдвиговые регистры 12 принимается вектор ХК4М(1) и считывается вектор Xk(5), который поступает на адресный вход блока 1. В регистры 3.J, 7.1, Ь и 11,j принимаются соответственно

Fl(0, H .(3), Х(3) и-Bjtt).

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

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

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

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

ймаювые имлульси

1я1ннп | /гокя (

ю 15 20

30

5

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

Vf tna.

#