интерполятор
Классы МПК: | G06F17/17 вычисление функций приближенными методами, например интерполяцией или экстраполяцией, сглаживанием, методом наименьших квадратов |
Автор(ы): | Агиевич С.Н., Смирнов П.Л., Подымов В.А., Малышев С.Р. |
Патентообладатель(и): | Военная академия связи |
Приоритеты: |
подача заявки:
1997-01-23 публикация патента:
10.10.1998 |
Изобретение относится к вычислительной технике. Технический результат изобретения заключается в обеспечении более высокой точности интерполяции функций, имеющих непрерывную четвертую производную и выше. Устройство включает входную информационную шину, шину запуска, тактовую шину, счетчик, преобразователь в дополнительный код, шесть умножителей, блок памяти, коммутатор, три элемента задержки, блок вычитания, четыре регистра, две установочные шины, сумматор и блок управления, состоящий из RS-триггера, двух элементов И, двух блоков сравнения. 1 з.п.ф-лы, 1 ил.
Рисунок 1
Формула изобретения
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), выбранный в качестве устройства-прототипа. Устройство-прототип содержит накапливающий сумматор, умножитель, первый и второй блоки памяти, коммутатор, преобразователь в дополнительный код, счетчик и регистр, выход которого соединен с первым информационным входом коммутатора, причем выход первого разряда регистра соединен с управляющим входом коммутатора, второй информационный вход которого соединен с выходом преобразователя в дополнительный код, вход которого соединен с выходом регистра, информационный вход которого является входом младших разрядов аргумента интерполятора, вход старших разрядов которого соединен с входом установки начального значения счетчика, выход которого соединен с адресным входом первого блока памяти, выход умножителя соединен с информационным входом накапливающего сумматора, выход которого является выходом интерполятора, входы занесения данных счетчика и регистра и вход сброса накапливающего сумматора соединены с входом начальной установки интерполятора, счетный вход счетчика и вход синхронизации накапливающего сумматора соединены с входом тактирования интерполятора, выход второго блока памяти соединен с входом первого сомножителя умножителя, вход второго сомножителя которого соединен с выходом первого блока памяти, а выход коммутатора соединен с адресным входом второго блока памяти. Известное техническое решение обладает недостаточной точностью интерполяции, которая характеризуется погрешностью интерполяции, равной![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-2t.gif)
где
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-3t.gif)
h - расстояние между отсчетами функции f(x). Причем эта точность обеспечивается для функций, имеющих непрерывную третью производную (f(x)
![интерполятор, патент № 2120137](/images/patents/351/2120137/8712.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/8712.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/8712.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-4t.gif)
счетчиков 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 известно, что выражение для вычисления производной сплайна можно записать
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-5t.gif)
где
h - шаг между отсчетами функции f(x);
B - сплайн степени m-1.
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-6t.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-7t.gif)
число сочетаний из m по i:
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-8t.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-9t.gif)
x = h(N +
![интерполятор, патент № 2120137](/images/patents/351/2120131/964.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120131/964.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/8712.gif)
При S = 0 выражение (2) упрощается. В этом случае для квадратичного сплайна (m-1 = 2):
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-10t.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-11t.gif)
Из статей: Желудев В.А. Локальная сплайн-аппроксимация на равномерной сетке// Журнал вычислительной математики и математической физики, 1987, т. 27, N 9, с. 1296 - 1310 и Желудев В.А. Восстановление функций и их производных по сеточным данным с погрешностью при помощи локальных сплайнов// Журнал вычислительной математики и математической физики, 1987, т. 27, N 1, с. 22-34 известно, что значение B-сплайна b3h(x) отлично от нуля на участке (0, 3h) и на различных интервалах наблюдения определяется следующим образом
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-12t.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-13t.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120131/964.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120131/964.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120131/964.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120131/964.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120131/964.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-14t.gif)
Из (3) имеем
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-15t.gif)
Учтем симметрию B-сплайна относительно точки h
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-16t.gif)
где
g3n определяется (4). Реализация (5) в виде устройства позволяет вычислять функции f(x)
![интерполятор, патент № 2120137](/images/patents/351/2120034/949.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-17t.gif)
что лучше не менее чем на 5% по сравнению с прототипом. Точность последнего определяется из выражения (1). Пусть xi - число, образованное K старшими разрядами аргумента x, где 2
![интерполятор, патент № 2120137](/images/patents/351/2120019/8773.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120019/8773.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120019/8773.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120019/8773.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-18t.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120137/2120137-19t.gif)
где
f(xi-1), f(xi), f(xi+1) - значения функции в узловых точках. Работа интерполятора на основе выражения (5) и фиг. 1 осуществляется следующим образом. Перед началом работы в блок памяти 8 записываются значения 0,5
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
В исходном состоянии на шину 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 увеличивается на единицу, принимая значение xi+1. Последнее поступает на адресные входы блока памяти 8, определяя номер ячейки, содержимое которой 0,5
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/183.gif)
![интерполятор, патент № 2120137](/images/patents/351/2120023/916.gif)
Класс G06F17/17 вычисление функций приближенными методами, например интерполяцией или экстраполяцией, сглаживанием, методом наименьших квадратов