интерполятор

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

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

2. Устройство по п.1, отличающееся тем, что блок управления выполнен содержащим первый и второй элементы сравнения, второй счетчик, первый и второй элементы И и RS-триггер, S-вход которого объединен со входом обнуления второго счетчика, первым входом блока управления и первым выходом блока управления, R-вход соединен с выходом второго элемента сравнения и вторым выходом блока управления, а выход - с первым входом второго элемента И, второй вход которого соединен со вторым входом блока управления, а выход является пятым выходом блока управления и соединен с первым входом первого элемента И и счетным входом второго счетчика, информационные выходы которого являются третьей группой выходов блока управления и соединены с первой группой входов второго блока сравнения и первой группой входов первого блока сравнения, вторая группа входов которого является первой установочной шиной блока управления, а выход соединен со вторым входом первого элемента И, выход которого является четвертым выходом блока управления, вторая установочная шина которого соединена со второй группой входов второго блока сравнения.

Описание изобретения к патенту

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

Известные устройства (АС СССР N 1405074, G 06 F 15/353, от 27.10.1986, АС СССР N 1686461, G 06 F 15/353, от 13.02.1989) позволяют воспроизводить широкий класс функциональных зависимостей, но обладают низкой точностью.

Наиболее близким к заявляемому устройству по своей технической сущности является интерполятор (АС СССР N 1405074, G 06 F 15/353, от 27.10.1986), выбранный в качестве устройства-прототипа.

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

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



где

максимум третьей производной функции f(x);

h - расстояние между отсчетами функции f(x).

Причем эта точность обеспечивается для функций, имеющих непрерывную третью производную (f(x)C³) или выше. При интерполяции функций, имеющих непрерывную четвертую производную (f(x)C⁴) и выше не полностью учитывается информация о гладкости функций, вследствие чего прототип не обеспечивает более высокой точности.

Целью изобретения является разработка устройства, обеспечивающего более высокую точность интерполяции функций, имеющих непрерывную четвертую производную (f(x)C⁴) и выше.

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

Блок управления содержит первый и второй элементы сравнения, второй счетчик, первый и второй элементы И и RS-триггер, S-вход RS-триггера объединен со входом обнуления второго счетчика, первым входом блока управления и первым выходом блока управления. R-вход соединен с выходом второго элемента сравнения и вторым выходом блока управления. Выход RS-триггера соединен с первым входом второго элемента И. Второй вход второго элемента И соединен со вторым входом блока управления. Выход второго элемента И является пятым выходом блока управления и соединен с первым входом первого элемента И и счетным входом второго счетчика. Информационные выходы второго счетчика являются третьей группой выходов блока управления и соединены с первой группой входов второго блока сравнения и первой группой входов первого блока сравнения. Вторая группа входов первого блока сравнения является первой установочной шиной блока управления. Выход первого блока сравнения соединен со вторым входом первого элемента И. Выход первого элемента И является четвертым выходом блока управления. Вторая установочная шина блока управления соединена со второй группой входов второго блока сравнения.

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

Заявленное устройство поясняется чертежами, приведенными на фиг. 1, где приведена структурная схема заявленного устройства.

Интерполятор, показанный на фиг. 1, состоит из входной информационной шины 1, шины запуска 2, тактовой шины 3, счетчика 4, преобразователя в дополнительный код 5, умножителей 6, 7, 10, 15, 17, 19, блока памяти 8, коммутатора 9, элементов задержки 11, 12, 14, блока вычитания 13, регистров 16, 18, 20, 25, блока управления 21, установочных шин 22 и 23, сумматора 24.

Блок управления 21, показанный также на фиг. 1, состоит из RS-триггера 26, элементов И 27, 29, счетчика 28, блоков сравнения 30 и 31.

Последовательно соединены умножитель 15, сумматор 24 и регистр 25. Информационные выходы регистра 25 являются выходной шиной интерполятора. Информационные входы счетчика 4 соединены со входной информационной шиной 1 интерполятора. Информационные выходы счетчика 4 соединены с адресными входами блока памяти 8. Первый вход блока управления 21 соединен с шиной запуска 2 интерполятора. Второй вход - с тактовой шиной 3 интерполятора. Первый выход блока управления 21 соединен со входом обнуления регистра 25 и входом обнуления счетчика 4. Второй выход блока управления 21 соединен со входом управления регистра 25. Группа входов уменьшаемого блока вычитания 13 через элемент задержки 11 соединена с выходами умножителя 7. Первая и вторая группы входов последнего поразрядно объединены и соединены с выходами преобразователя в дополнительный код 5. Группа входов вычитаемого блока вычитания 13 соединена с выходами умножителя 10. Первая группа входов умножителя 10 соединена с выходами умножителя 6, первая и вторая группы входов которого поразрядно объединены и соединены со входами преобразователя в дополнительный код 5 и входной информационной шиной 1 интерполятора. Выходы блока вычитания 13 соединены с первой группой входов умножителя 17. Вторая группа входов умножителя 17 через регистр 18 соединена со второй группой выходов коммутатора 9. Выходы умножителя 17 соединены со второй группой информационных входов сумматора 24. Третья группа информационных входов сумматора 24 соединена с выходами умножителя 19. Первая группа входов умножителя 19 через элемент задержки 14 объединена со входами элемента задержки 11. Вторая группа входов умножителя 19 через регистр 20 объединена с третьей группой выходов коммутатора 9. Группа информационных входов коммутатора 9 соединена с выходами блока памяти 8. Группа адресных входов коммутатора 9 соединена с третьей группой выходов блока управления 21. Первая установочная шина блока управления 21 является первой установочной шиной 22 интерполятора и соединена со второй группой входов умножителя 10. Первая группа входов умножителя 10 через элемент задержки 12 соединена с первой группой входов умножителя 15. Вторая группа входов умножителя 15 через регистр 16 соединена с первой группой выходов коммутатора 9. Вторая группа входов умножителя 6 объединена с его первой группой входов. Вторая группа входов умножителя 7 объединена с его первой группой входов. Счетный вход счетчика 4 объединен с управляющими входами регистров 16, 18, 20 и с четвертым выходом блока управления 21. Пятый выход блока управления 21 соединен со входами управления элементов задержки 11, 12, 14, управляющим входом блока вычитания 13 и управляющим входом сумматора 24. Вторая установочная шина блока управления 21 является второй установочной шиной 23 интерполятора.

Блок управления 21 содержит RS-триггер 26, элементы И 27 и 29, счетчик 28, элементы сравнения 30 и 31. S-вход RS-триггера 26 объединен со входом обнуления счетчика 28, первым входом блока управления 21 и первым выходом блока управления 21. R-вход соединен с выходом элемента сравнения 31 и вторым выходом блока управления 21. Выход RS-триггера 26 соединен с первым входом элемента И 29. Второй вход элемента И 29 соединен со вторым входом блока управления 21. Выход элемента И 29 является пятым выходом блока управления 21 и соединен с первым входом элемента И 27 и счетным входом счетчика 28. Информационные выходы счетчика 28 являются третьей группой выходов блока управления 21 и соединены с первой группой входов блока сравнения 31 и первой группой входов блока сравнения 31. Вторая группа входов блока сравнения 30 является первой установочной шиной блока управления 21. Выход блока сравнения 30 соединен со вторым входом первого элемента И 27. Выход первого элемента И 27 является четвертым выходом блока управления 21. Вторая установочная шина блока управления 21 соединена со второй группой входов блока сравнения 31.

Входящие в структурную схему заявляемого устройства элементы известны и описаны, например, в книге В.Л. Шило. Популярные цифровые микросхемы. Справочник. -М. : Радио и связь, 1988. Так, в указанном источнике описаны принципы построения и примеры реализации:

счетчиков 4, 28 на с.85-86 (можно реализовать на микросхеме К155ИЕ5);

блока памяти 8 на с.171-174 (можно реализовать на микросхеме К155ПР6);

элементов И 27, 29 на с.35 рис. 1.19а (можно реализовать на микросхеме К155ЛИ1);

регистров 16, 18, 20, 25 на с.104-105 (можно реализовать на микросхеме К155ИР13- с. 111 рис. 1.78);

RS-триггера 26 на с.62-67 (можно реализовать на микросхеме К155ЛЕ1 - с. 63 рис. 1.42).

Принцип работы умножителей 6, 7, 10, 15, 17, 19 известен и описан в книге: М. А. Карцев, В.А. Брик. Вычислительные системы и синхронная арифметика. -М.: Радио и связь, 1981, с.163 - 221. Могут быть реализованы на микросхемах SN54284 и SN54285, с.305, рис. 6.3.12 или на микросхеме ADSP1016 (С. Кун. Матричные процессоры на СБИС: Пер. с англ. -М.: Мир, 1991, с.502, табл. 7.4).

В книге В.Л. Шило. Популярные цифровые микросхемы. Справочник. 2-е изд., испр., -Челябинск: Металлургия, 1989 описан принцип работы элементов задержки 11, 12, 14 на с.181 - 187 (можно реализовать на микросхемах К564АГ1, с. 285 рис. 2.83а), а порядок сопряжения К564 с ТТЛ описан в книге: Цифровые интегральные микросхемы: Справочник/ П.П. Мальцев, Н.С. Долидзе и др. - М.: Радио и связь, 1994, с. 101 - 103.

Принцип работы блоков сравнения 30, 31 известен и описан в книге Ю.В. Гаврилов, А.Н. Пучко. Арифметические устройства быстродействующих ЭЦВМ. -М.: Советское радио, 1970, с.234-257. Можно реализовать на микросхемах К561ИП2 (В. Н. Вениаминов, О.Н. Лебедев, А.И. Мирошниченко. Микросхемы и их применение. Справочное пособие. 3-е изд. перераб. и дополн. - М.: Радио и связь, 1989, с.114, рис. 4, 12 б).

Принципы работы сумматора 24 и блока вычитания 13 известны и описаны в книге: Д. Гивоне, Р. Россе. Микропроцессоры и микрокомпьютеры: Вводный курс: Пер. с англ. -М.: Мир, 1983, с. 184-198. Полный сумматор описан в книге В.Л. Шило. Популярные цифровые микросхемы. Справочник. 2-е изд., испр., - Челябинск: Металлургия, 1989. с.152, рис. 1.112, с. 153, рис. 1.113. Блок вычитания на основе полных сумматоров приведен в книге Д. Гивоне, Р. Россе. Микропроцессоры и микрокомпьютеры: Вводный курс: Пер. с англ. -М.: Мир, 1983, с. 190, рис. 5.38. Можно реализовать на элементах ИСКЛ. ИЛИ - К155ЛП5, И - К155ЛИ1, ИЛИ - из ИЛИ-НЕ К155ЛЕ4 и НЕ К155ЛН1.

Принцип реализации преобразователя в дополнительный код 5 известен и описан в книге Л.М. Гольденберг. Импульсные и цифровые устройства. М.: Связь, 1973, с. 462 - 468. Можно реализовать на микросхеме К155ЛАЗ.

Принцип реализации коммутатора 9 известен и описан в книге В.Л. Шило. Популярные цифровые микросхемы. Справочник. 2-е изд., испр., - Челябинск: Металлургия, 1989, с. 220. Может быть реализован на микросхеме К561КТ3.

Реализация заявляемого устройства объясняется следующим образом. Из статей: Желудев В.А. Локальная сплайн-аппроксимация на равномерной сетке// Журнал вычислительной математики и математической физики, 1987, т. 27, N 9, с. 1296 - 1310 и Желудев В.А. Восстановление функций и их производных по сеточным данным с погрешностью при помощи локальных сплайнов// Журнал вычислительной математики и математической физики, 1987, т. 27, N 1, с. 22-34 известно, что выражение для вычисления производной сплайна можно записать



где

h - шаг между отсчетами функции f(x);

B - сплайн степени m-1.

число сочетаний из m по i:





x = h(N + ), [0,1].

При S = 0 выражение (2) упрощается. В этом случае для квадратичного сплайна (m-1 = 2):





Из статей: Желудев В.А. Локальная сплайн-аппроксимация на равномерной сетке// Журнал вычислительной математики и математической физики, 1987, т. 27, N 9, с. 1296 - 1310 и Желудев В.А. Восстановление функций и их производных по сеточным данным с погрешностью при помощи локальных сплайнов// Журнал вычислительной математики и математической физики, 1987, т. 27, N 1, с. 22-34 известно, что значение B-сплайна b³_h(x) отлично от нуля на участке (0, 3h) и на различных интервалах наблюдения определяется следующим образом



-3(h)²]=h²[(+1)²-3²]/(2h³)=[(+1)²-3²]/(2h),



Из (3) имеем



Учтем симметрию B-сплайна относительно точки hm/2 (упомянутые выше статьи). Тогда получим квадратичный сплайн минимального шаблона



где

g³_n определяется (4).

Реализация (5) в виде устройства позволяет вычислять функции f(x)C⁴ с точностью, определяемой погрешностью, меньшей или равной (Желудев В.А. Восстановление функций и их производных по сеточным данным// Журнал вычислительной математики и математической физики, 1987, т. 27, N 1, с. 24).

что лучше не менее чем на 5% по сравнению с прототипом. Точность последнего определяется из выражения (1).

Пусть x_i - число, образованное K старшими разрядами аргумента x, где 2 Km-1; m - длина двоичного кода числа x. Число x_i представляет собой номер узловой точки. Пусть x - - число, образованное m-K младшими разрядами аргумента так, что x = x_i + x2^-k, 0 x 1. Тогда по формуле (5) интерполяции квадратичными сплайнами минимального шаблона имеем





где

f(x_i-1), f(x_i), f(x_i+1) - значения функции в узловых точках.

Работа интерполятора на основе выражения (5) и фиг. 1 осуществляется следующим образом.

Перед началом работы в блок памяти 8 записываются значения 0,5g³_n-1 , 0,5g³_n , 0,5g³_n+1 со сдвигом адреса так, что j-му значению кода адреса соответствует значение 0,5g³_j-2 .

В исходном состоянии на шину 3 подаются тактовые импульсы типа меандр, на первой установочной шине 22 присутствует код числа 3, а на второй установочной шине 23 - код числа 5. На информационную шину 1 интерполятора подается код значения переменной x.

С подачей на шину 2 импульса положительной полярности обнуляется регистр 25, в счетчик 4 записывается код старших разрядов переменной x. Одновременно обнуляется счетчик 28, а RS-триггер 26 устанавливается в единичное состояние, при котором на его выходе формируется уровень логической "1". Последний подается на первый вход элемента И 29, разрешая прохождение через него тактовых импульсов. Кроме того, код числа 0 с выхода счетчика 28 поступает на первую группу входов блока сравнения 30. На другую группу его входов поступает код числа 3 с первой установочной шины 22. В результате выполнения операции сравнения на выходе блока 30 формируется сигнал с единичным уровнем. Следует отметить, что временному положению передних фронтов тактовых импульсов далее будут соответствовать новые такты работы устройства.

На первом такте работы устройства тактовый импульс с выхода элемента И 29 подается на счетный вход счетчика 4 через элемент И 27, открытый подаваемым на его вход единичным уровнем с выхода блока сравнения 30. При этом содержимое счетчика 4 увеличивается на единицу, принимая значение x_i+1. Последнее поступает на адресные входы блока памяти 8, определяя номер ячейки, содержимое которой 0,5g³_n-1 подается на вход коммутатора 9. В связи с тем что на управляющие входы коммутатора 9 поступает код числа 1 с выходов счетчика 28, значение 0,5g³_n-1 записывается в регистр 16.

В следующих двух тактах работы аналогичным образом в регистры 18 и 19 записываются значения соответственно 0,5g³_n и 0,5g³_n+1. При этом в конце третьего такта работы устройства содержимое счетчика 28 совпадает с кодом числа, подаваемым на установочную шину 22. В результате на выходе блока сравнения 30 формируется нулевой уровень, закрывающий элемент И 27 и приводящий к остановке счетчика.

Одновременно с этим в течение описанных выше тактов работы устройства младшие разряды кода переменной (значение x) поступают на входы умножителя 6 и через блок преобразования в дополнительный код 5- на входы умножителя 7. На выходах умножителей 6 и 7 формируются значения соответственно x² и (1 - x)² . Данные величины поступают соответственно на первую группу входов умножителя 10 и на вход элемента задержки 11. На вторую группу входов умножителя 10 подается код числа 3 с первой установочной шины 22. На выходе умножителя 10 формируется значение 3x², которое поступает на вход вычитаемого блока вычитания 13. На вход уменьшаемого блока 13 подается задержанное значение (1 - x)² . В результате выполнения операции вычитания на выходе блока 13 формируется значение (1 - x)² - 3x². Последнее поступает на первую группу входов блока умножения 17. Одновременно с этим на первые группы входов блоков умножения 15 и 19 подаются задержанные элементами задержки 12 и 14 значения соответственно x² с выхода умножителя 6 и (1 - x)² с выхода умножителя 7.

На четвертом такте работы устройства в умножителях 15, 17, 19 вычитаются произведения соответственно 0,5g³_n-1x², 0,5g³_n[(1-x)²-3x²], 0,5g³_n+1(1-x)². . Результаты вычислений подаются на входы сумматора 24. НА предшествующих тактах результаты вычислений в блоках 15, 17, 19 не учитываются в последующем алгоритме работы устройства.

На пятом такте работы устройства в блоке 24 происходит суммирование полученных произведений, что соответствует формированию значения функции f(x). При этом в конце пятого такта работы устройства содержимое счетчика 28 совпадает с кодом числа, подаваемым на вторую установочную шину 23. В результате на выходе блока сравнения 31 формируется единичный уровень. Последний поступает на вход записи регистра 25. Вычислительное значение функции f(x) с выхода сумматора 24 записывается в регистр 25. Кроме того, единичный уровень с выхода блока сравнения 31 подается на R-вход RS-триггера 26, переводя его в нулевое состояние. В результате нулевой уровень с выхода RS-триггера 26 закрывает элемент И 29 и препятствует тем самым прохождению тактовых импульсов через элемент И 29. На этом работа устройства по вычислению значения функции f(x) завершается. Устройство готово к новому циклу работы.