Главная страница  |  Описание сайта  |  Контакты
СПЛАЙН-ИНТЕРПОЛЯТОР
СПЛАЙН-ИНТЕРПОЛЯТОР

СПЛАЙН-ИНТЕРПОЛЯТОР

Патент Российской Федерации
Суть изобретения: Изобретение относится к автоматике и вычислительной технике. Техническим результатом изобретения является обеспечение более высокой точности интерполяции при вычислении функций, имеющих непрерывную четвертую производную. Устройство включает три блока памяти, четыре умножителя, сумматор, регистр, блок управления, счетчик, блок быстрого преобразования Фурье, блок обратного быстрого преобразования Фурье и блок формирования параметров сплайна. Повышение точности интерполяции достигается за счет учета априорной информации о гладкости функции и использования всего массива дискретных отсчетов функции. 1 з.п. ф-лы, 6 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2140099
Класс(ы) патента: G06F17/17
Номер заявки: 98106417/09
Дата подачи заявки: 08.04.1998
Дата публикации: 20.10.1999
Заявитель(и): Военная академия связи
Автор(ы): Агиевич С.Н.; Дворников С.В.; Малышев С.Р.; Подымов В.А.; Смирнов П.Л.
Патентообладатель(и): Военная академия связи
Описание изобретения: Изобретение относится к автоматике и вычислительной технике, в частности к полиноминальным и сплайн-интерполяторам, и может быть использовано в автоматических системах управления для воспроизведения нелинейных зависимостей одной переменной.
Известные устройства (AC СССР N 1405074, G 06 F 15/353 от 27.10.1986, AC СССР N 1686461, G 06 F 15/353 от 13.02.1989) позволяют воспроизводить широкий класс функциональных зависимостей, но обладают низкой точностью.
Наиболее близким к заявляемому устройству по своей технической сущности является "Сплайн-интерполятор" (AC СССР N 1686461, G 06 F 15/353 от 13.02.1989), выбранный в качестве устройства-прототипа.
Устройство-прототип содержит первый и второй счетчики, первый и второй блоки памяти, первый, второй, третий и четвертый блоки умножения, сумматор, регистр результата, блок управления, причем вход пуска интерполятора подключен к первому входу блока управления, синхровход интерполятора подключен к второму входу блока управления, первый выход которого соединен с входами сброса первого, второго счетчиков и регистра результата, второй выход соединен с суммирующим входом первого счетчика, выход первого счетчика соединен с первым адресным входом первого блока памяти, выход которого соединен с первыми информационными входами первого, второго, третьего, четвертого блоков умножения, вторые информационные входы которых соединены с выходом второго блока памяти, выходы первого, второго, третьего, четвертого блоков умножения соединены соответственно с первым, вторым, третьим, четвертым входами сумматора, выход которого соединен с первым информационным входом регистра результата, выход которого является выходом интерполятора, первый и второй управляющие входы первого, второго, третьего, четвертого блоков умножения соединены соответственно с третьим и четвертым выходами блока управления, пятый, шестой, седьмой, восьмой, девятый, десятый и одиннадцатый выходы которого соединены соответственно с первым управляющим входом регистра результата, с вычитающим входом первого счетчика, с управляющим входом первого блока памяти, с управляющим входом второго блока памяти, с входом записи второго счетчика, с вычитающим входом второго счетчика, с вторым управляющим входом регистра результата, второй информационный вход которого соединен с выходом второго блока памяти, вход количества значений функции внутри интервала интерполятора соединен с информационным входом второго счетчика и с вторым адресным входом первого блока памяти, третий адресный вход которого соединен с выходом первого счетчика и с третьим входом блока управления, четвертый вход которого соединен с третьим адресным входом первого блока памяти и с выходом второго счетчика, вход значения функции интерполятора соединен с информационным входом второго блока памяти.
Известное техническое решение обладает недостаточной точностью интерполяции, которая характеризуется погрешностью интерполяции, равной [1, 2]

где f(3)max - максимум третьей производной функции f(x);
h - расстояние между отсчетами функции f(x).
Причем, эта точность обеспечивается для функций, имеющих непрерывную третью производную (f(x) ∈ C3) или выше. При интерполяции функций, имеющих непрерывную четвертую производную (f(x) ∈ C4) не полностью учитывается информация о гладкости функций, вследствие чего прототип не обеспечивает более высокой точности.
Кроме того, в известном техническом решении для получения коэффициентов сплайна при интерполяции используют только ближайшие к интерполируемой точке отсчеты функции, а не весь имеющийся массив дискретных отсчетов функции f(x).
Целью изобретения является разработка устройства, обеспечивающего более высокую точность интерполяции периодических функций, имеющих непрерывную четвертую производную (f(x) ∈ C4) путем учета информации о гладкости и использования всего массива дискретных отсчетов функций.
Поставленная цель достигается тем, что в известный сплайн-интерполятор, содержащий первый и второй блоки памяти, первый, второй, третий и четвертый умножители, сумматор, регистр, блок управления и счетчик, группа информационных входов которого объединена с адресными входами первого блока памяти и одновременно является первой установочной шиной сплайн-интерполятора, вычитающий вход счетчика объединен со входом управления регистра и пятым выходом блока управления, а информационные выходы объединены с шестой группой входов блока управления, первый вход которого является тактовой шиной сплайн-интерполятора, а третий выход соединен со входом управления второго блока памяти, первая, вторая и третья группы выходов которого соединены с первыми группами входов соответственно первого, второго и третьего умножителей, группы выходов которых соединены соответственно с первой, второй и третьей группами информационных входов сумматора, группа выходов которого соединена с информационными входами регистра, выходы которого являются группой информационных выходов сплайн-интерполятора, дополнительно введены блок быстрого преобразования Фурье, третий блок памяти, блок обратного быстрого преобразования Фурье и блок формирования параметров сплайна. Первая группа входов блока формирования параметров сплайна соединена с информационными выходами первого блока памяти, вторая группа входов соединена с информационными выходами счетчика. Управляющий вход счетчика является шиной запуска сплайн-интерполятора, а вход обнуления - шиной обнуления сплайн-интерполятора. Седьмая группа входов блока формирования параметров сплайна является второй установочной шиной сплайн-интерполятора, четвертая, пятая и шестая группы выходов соединены со вторыми группами входов соответственно третьего, второго и первого умножителей, а третий вход объединен с управляющим входом сумматора и четвертым выходом блока управления. Седьмая группа входов блока управления является третьей установочной шиной сплайн-интерполятора, а вторая группа выходов соединена с адресными входами третьего блока памяти, входами управления блока обратного быстрого преобразования Фурье и входами управления блока быстрого преобразования Фурье. Информационные входы блока быстрого преобразования Фурье являются информационной шиной сплайн-интерполятора, а информационные выходы соединены с первой группой входов четвертого умножителя. Вторая группа входов четвертого умножителя соединена с информационными выходами третьего блока памяти, а выходы соединены с информационными входами блока обратного быстрого преобразования Фурье. Информационные выходы блока обратного быстрого преобразования Фурье соединены с информационными входами второго блока памяти.
Блок формирования параметров сплайна выполнен содержащим первый, второй, третий и четвертый умножители, преобразователь в дополнительный код, первый, второй и третий элементы задержки и блок вычитания. Первая группа входов первого умножителя является первой группой входов блока формирования параметров сплайна, вторая группа входов - второй группой входов блока формирования параметров сплайна, а выходы пораздядно объединены с первой и второй группами входов второго умножителя и входами преобразователя в дополнительный код. Выходы преобразователя в дополнительный код соединены поразрядно с первой и второй группами входов третьего умножителя. Выходы третьего умножителя соединены с информационными входами первого элемента задержки. Выходы первого элемента задержки соединены с группой входов уменьшаемого блока вычитания и информационными входами третьего элемента задержки. Выходы третьего элемента задержки являются четвертой группой выходов блока формирования параметров сплайна, а управляющий вход объединен с третьим входом блока формирования параметров сплайна и управляющими входами первого и второго элементов задержки, и управляющим входом блока вычитания. Группа входов вычитаемого блока вычитания соединена с выходами четвертого умножителя. Вторая группа входов четвертого умножителя является седьмой группой входов блока формирования параметров сплайна и одновременно является второй установочной шиной сплайн-интерполятора, а первая группа входов объединена с выходами второго умножителя и информационными входами второго элемента задержки. Выходы второго элемента задержки являются шестой группой выходов блока формирования параметров сплайна. Выходы блока вычитания являются пятой группой выходов блока формирования параметров сплайна.
Перечисленная новая совокупность существенных признаков заявленного устройства обеспечивает более высокую точность интерполяции периодических функций, имеющих непрерывную четвертую производную (f(x) ∈ C4). Это достигается путем учета априорной информации о степени гладкости функции и использования всего массива дискретных отсчетов интерполируемой функции.
Так, из [1, 2] известно, что выражение для интерполяции функции f(x) квадратичным сплайном минимального шаблона можно записать следующим образом:

где τ ∈ [-0.5, 0.5], а дискретное преобразование Фурье (ДПФ) от коэффициентов gn вычисляется по формуле [3]
Fk(gn) = F(f(xk))/u3n. (3)
Массив коэффициентов gn получается обратным преобразованием Фурье от Fk(gn):

Значения u3n вычисляются по следующей формуле (см. [4] на с. 200):
u3n = 1-v2n/8, (5)
где vn = 2sin(πn/N); 1/N = h; f(xk) - дискретный отсчет функции f(x), h - шаг дискретизации функции f(x).
Причем для получения коэффициентов gn целесообразно использовать алгоритм быстрого преобразования Фурье (БПФ) для повышения быстродействия устройства (см. [5] на с. 633-693 и с. 394-432).
Реализация (2) - (5) в виде устройства позволяет вычислять функции f(x) ∈ C4 с точностью (определяемой погрешностью интерполяции), равной (см. [3] на с. 187):
μ < 0(h4f(4)max).
Известно, что точность глобального сплайна выше, чем локального, так как в этом случае при интерполяции используется весь массив дискретных отсчетов функции. Точность локального сплайна определяется величиной [1, 2]
μ2 = 0,047·h3f(3)max. (6)
что лучше не менее, чем на 5% по сравнению с прототипом (см. выражение (1)). Следовательно, точность заявленного устройства выше, чем (6) и (1).
Заявленное устройство поясняется чертежами, на которых:
на фиг. 1 приведена структурная схема заявленного устройства;
на фиг. 2 представлена структурная схема блока формирования параметров сплайна;
на фиг. 3 приведен вариант построения устройства, реализующего блок управления и блок быстрого преобразования Фурье;
на фиг. 4 показан один из возможных вариантов построения блока быстрого преобразования Фурье;
на фиг. 5 показан вариант реализации второго блока памяти;
на фиг. 6 представлен один из возможных вариантов реализации элемента задержки.
Сплайн-интерполятор, показанный на фиг. 1, состоит из первого 1, второго 8 и третьего 5 блоков памяти, первого 10, второго 11, третьего 12 и четвертого 6 умножителей, сумматора 13, регистра 14, блока управления 3, блока быстрого преобразования Фурье 4, блока обратного быстрого преобразования Фурье 7, блока формирования параметров сплайна 9 и счетчика 2. Группа информационных входов счетчика 2 объединена с адресными входами первого блока памяти 1 и одновременно является первой установочной шиной 15 сплайн-интерполятора. Вычитающий вход счетчика 2 объединен со входом управления регистра 14 и пятым выходом блока управления 3, а информационные выходы объединены с шестой группой входов блока управления 3. Первый вход блока управления 3 является тактовой шиной 18 сплайн-интерполятора, а третий выход соединен со входом управления второго блока памяти 8. Первая, вторая и третья группы выходов второго блока памяти 8 соединены с первыми группами входов соответственно первого 10, второго 11 и третьего 12 умножителей, группы выходов которых соединены соответственно с первой, второй и третьей группами информационных входов сумматора 13. Группа выходов сумматора 13 соединена с информационными входами регистра 14. Выходы регистра 14 являются группой информационных выходов сплайн-интерполятора. Первая группа входов блока формирования параметров сплайна 9 соединена с информационными выходами первого блока памяти 1, вторая группа входов соединена с информационными выходами счетчика 2. Управляющий вход счетчика 2 является шиной запуска 16 сплайн-интерполятора, а вход обнуления - шиной обнуления 20 сплайн-интерполятора. Седьмая группа входов блока формирования параметров сплайна 9 является второй установочной шиной 21 сплайн-интерполятора, четвертая, пятая и шестая группы выходов соединены со вторыми группами входов соответственно третьего 12, второго 11 и первого 10 умножителей, а третий вход объединен с управляющим входом сумматора 13 и четвертым выходом блока управления 3. Седьмая группа входов блока управления 3 является третьей установочной шиной 17 сплайн-интерполятора, а вторая группа выходов соединена с адресными входами третьего блока памяти 5, входами управления блока обратного быстрого преобразования Фурье 7 и входами управления блока быстрого преобразования Фурье 4. Информационные входы блока обратного быстрого преобразования Фурье 4 являются информационной шиной 19 сплайн-интерполятора, а информационные выходы соединены с первой группой входов четвертого умножителя 6. Вторая группа входов четвертого умножителя 6 соединена с информационными выходами третьего блока памяти 5, а выходы соединены с информационными входами блока обратного быстрого преобразования Фурье 7. Информационные выходы блока обратного быстрого преобразования Фурье 7 соединены с информационными входами второго блока памяти 8.
Блок формирования параметров сплайна 9, показанный на фиг. 2, состоит из первого 91, второго 93, третьего 94 и четвертого 95 умножителей, преобразователя в дополнительный код 92, первого 96, второго 98 и третьего 99 элементов задержки и блока вычитания 97. Первая группа входов первого умножителя 91 является первой группой входов 9.1 блока формирования параметров сплайна 9, вторая группа входов - второй группой входов 9.2 блока формирования параметров сплайна 9, а выходы поразрядно объединены с первой и второй группами входов второго умножителя 93 и входами преобразователя в дополнительный код 92. Выходы преобразователя в дополнительный код 92 соединены поразрядно с первой и второй группами входов третьего умножителя 94. Выходы третьего умножителя 94 соединены с информационными входами первого элемента задержки 96. Выходы первого элемента задержки 96 соединены с группой входов уменьшаемого блока вычитания 97 и информационными входами третьего элемента задержки 99. Выходы третьего элемента задержки 99 являются четвертой группой выходов 9.4 блока формирования параметров сплайна 9, а управляющий вход объединен с третьим входом 9.3 блока формирования параметров сплайна 9 и управляющими входами первого 96 и второго 98 элементов задержки, и управляющим входом блока вычитания 97. Группа входов вычитаемого блока вычитания 97 соединена с выходами четвертого умножителя 95. Вторая группа входов четвертого умножителя 95 является седьмой группой входов 9.7 блока формирования параметров сплайна 9 и одновременно является второй установочной шиной 21 сплайн-интерполятора, а первая группа входов объединена с выходами второго умножителя 93 и информационными входами второго элемента задержки 98. Выходы второго элемента задержки 98 являются шестой группой выходов 9.6 блока формирования параметров сплайна 4. Выходы блока вычитания являются пятой группой выходов 9.5 блока формирования параметров сплайна 9.
Заявленное устройство работает следующим образом.
В исходном состоянии на первую установочную шину 15 подается код числа M, где M соответствует задаваемому количеству точек интерполяции функции f(x) между соседними узлами интерполяции. На тактовую шину 18 поступают тактовые импульсы типа меандр. На установочной шине 17 присутствует код числа 0, на третьей установочной шине 21 - код числа 3. В первом блоке память 1 записаны значения τ0 таким образом, что в ячейке с адресом M хранится значение τ0, равное 1/(1 + M). В третьем блоке памяти 5 хранятся значения 1/u3n.
Перед началом работы счетчик 2 устанавливается в нулевое состояние подачей на его вход сброса по шине 20 импульса положительной полярности. При этом код числа 0 воздействует на вход 6 блока управления 3, в результате чего устройство удерживается в исходном состоянии.
С подачей на шину запуска 16 импульса положительной полярности в счетчик 2 записывается код числа M. Код числа M с выхода счетчика 2 поступает на вход 6 блока управления 3. На информационную шину 6 подаются отсчеты функции f(xk), которые поступают в блок быстрого преобразования Фурье (БПФ) 4. Под действием тактовых импульсов, поступающих по тактовой шине 18, и управляющих сигналов, поступающих с группы выходов 2 блока управления 3, в блоке БПФ 4 происходит вычисление значений Fk. Указанные величины поступают на первую группу входов умножителя 6.
Под воздействием управляющих сигналов, поступающих с группы выходов 2 блока управления 3 на адресные входы третьего блока памяти 5, на информационных выходах последнего формируются значения 1/u3k. Данные величины подаются на вторую группу входов четвертого умножителя 6. В результате выполнения операций умножения на выходе четвертого умножителя 6 формируются значения Fk/u3k. Последние поступают в блок обратного быстрого преобразования Фурье (ОБПФ) 7.
В блоке ОБПФ 7 происходит вычисление значений коэффициентов сплайна (1/2) · g0, (1/2) · g1, (1/2) · g2 в соответствии с выражением (4). Полученные значения коэффициентов сплайна с выхода блока ОБПФ 7 переписываются во второй блок памяти 8 под воздействием импульсов, поступающих на управляющий вход последнего с выхода 3 блока управления 3.
Далее под воздействием информационных сигналов, поступающих с выходов блока 1 и 2, сигналов, подаваемых на установочную шину 21 устройства, и управляющих сигналов (с выхода 4 блока управления 3), в блоке формирования параметров сплайна 9 происходит вычисление значений τ2, [(1-τ)2-3τ2] и (1-τ)2. Полученные величины поступают на вторые группы входов первого 10, второго 11 и третьего 12 умножителей. На первые группы входов последних подаются соответствующие значения (1/2) · g0, (1/2) · g1, (1/2) · g2 с информационных выходов второго блока памяти 8.
В результате выполнения операций умножения на выходах умножителей 10, 11, 12 формируются произведения (1/2)·g2·τ2, (1/2)·g1[(1-τ)2-3τ2] и (1/2)·g0(1-τ)2. Последние поступают на соответствующие группы информационных входов сумматора 13.
В сумматоре 13 производится суммирование указанных произведений под воздействием сигналов, поступающих на его управляющий вход с выхода 4 блока управления 3. В результате на выходе сумматора 13 формируется значение функции f(x) в первой точке интерполяции.
Полученное значение функции f(x) записывается в регистр 14 при помощи единичного импульса, поступающего с выхода 5 блока управления 3 на вход записи регистра 14.
Кроме того, единичный импульс с выхода 5 блока управления 3 поступает на вычитающий вход счетчика 2, уменьшая его содержимое на единицу.
Далее алгоритм работы устройства аналогичен. В блоке формирования параметров сплайна 9 формируются значения параметров сплайна, а в блоках 10 - 13 вычисляются значения функции f(x), которые записываются в регистр 14. Данная операция повторяется для значений τ, равных τ0·(M-1), затем τ0·(M-2) и т. д. до тех пор, пока содержимое счетчика 2 не станет равным нулю. При этом код числа 0 с выхода счетчика 2 поступает на вход 6 блока управления 3 и останавливает работу устройства. На этом работа устройства по вычислению значений функции f(x) завершается. Устройство готово к новому циклу работы.
Входящие в структурную схему заявляемого устройства элементы известны и описаны, например, в [6] . Так, в указанном источнике описаны принципы построения и примеры реализации:
счетчика 2 на с. 85 - 86 (можно реализовать на микросхеме К155ИЕ5);
блоков памяти 7, 11 на с. 171 - 174 (можно реализовать на микросхеме К155ПР6);
регистра 14 на с. 104 - 105 (можно реализовать на микросхеме К155ИР13 - с. 111 рис. 1.78).
Принцип работы умножителей 6, 10, 11, 12 известен и описан в [7]. Могут быть реализованы на микросхемах SN54284 и SN54285 (с. 305, рис. 6.3.12) или на микросхеме ADSP1016 (см. [8] на с. 502, табл. 7.4).
Принцип работы сумматора 13 известен и описан в [9] на с. 184 - 198. Полный сумматор описан в [10] на с. 152, рис. 1.112, с. 153, рис. 1.113. Можно реализовать на элементах ИСКЛ. или - К155ЛП5, И - К155ЛИ1, ИЛИ - из ИЛИ-НЕ К155ЛЕ4 и НЕ К155ЛН1.
Один из возможных вариантов построения второго блока памяти 8 показан на фиг. 5. Второй блок памяти 8, показанный на фиг. 5, выполнен содержащим первый 81, второй 82 и третий 83 регистры, соединенные последовательно. Информационные входы первого регистра 81 являются группой информационных входов блока. Выходы первого регистра 81 являются первой группой выходов блока. Выходы второго регистра 82 являются второй группой выходов блока. Выходы третьего регистра 83 являются третьей группой выходов блока. Управляющий вход первого регистра 81 объединен с управляющими входами второго 82 и третьего 83 регистров и является управляющим входом блока. Регистры можно реализовать на микросхеме К155ИР13.
Совокупность блоков 3 и 4 может быть реализована на цифровом процессоре обработки сигналов (ЦПОС) TMS32010 с дополнительными элементами, как показано на фиг. 3 (входы и выходы устройства, представленного на фиг. 3, полностью соответствуют входам и выходам группы блоков, обведенных прерывистой линией на фиг. 1). При этом блок БПФ 4 реализован на ЦПОС (блок 26), оперативном запоминающем устройстве (ОЗУ) 28 и элементах 27, 29, 31, 32. Блок управления 3 реализован на ЦПОС 26 и элементах 30, 34, 35, 36, 37. Принцип действия TMS32010 подробно рассмотрен в [11] на с. 51 - 102. Сам процессор изображен на с. 75, рис. 3.1.
Принцип действия элемента 30 известен и описан в [6] на с. 130 - 136, рис. 1.97. Может быть реализован на микросхемах К1555ИД7, К531ИД7.
Счетчик 27 - реверсивный, 16-ти разрядный. Принцип работы известен и описан в [6] на с. 85 - 93 и с. 91 рис. 1.67. Может быть реализован на микросхеме К155ИЕ7. Порядок соединения четырех счетчиков описан в этой же книге на с. 92-93.
Принцип действия ОЗУ 28 известен и описан в [12] на с. 145 - 148. Можно реализовать на микросхеме IDT 7186-70 (описана в [11] на с. 50).
Принцип работы элементов И-НЕ 32 и 33, ИЛИ-НЕ 29 и 31 известен и описан в [13] на с. 510, рис. 8.5.
Принцип работы блока сравнения 25 известен и описан в [14] на с. 234 - 257. Можно реализовать на микросхемах К561ИП2 (см. [12] с. 114, рис. 4.12 б).
Принцип построения и пример реализации элементов И 34 - 37 описаны в [6] на с. 35, рис. 1.19а (можно реализовать на микросхемах К155ЛИ1).
Принцип БПФ и ОБПФ известен и описан в [5]. Пример реализации БПФ на ЦПОС TMS32010 приведен в [11] на с. 259, а на с. 260 приведен расчет необходимой для этого памяти.
Устройство, реализующее блоки 3, 4 и приведенное на фиг. 3, работает следующим образом. В исходном состоянии на вход 1 устройства (фиг. 3) и соответственно на вход CLCIN ЦПОС 26 поступают импульсы типа меандр по тактовой шине 16 сплайн-интерполятора (фиг. 1). На вход 7 поступает код числа 0 (с установочной шины 17 сплайн-интерполятора). На вход 6 подается код числа 0 (с выхода счетчика 2 сплайн-интерполятора). В результате выполнения операции сравнения в блоке 25 на выходе последнего формируется сигнал низкого уровня. Данный сигнал подается на вход RS ЦПОС 26. При этом на выходах стробирующих сигналов устанавливается высокий уровень, а шина данных D0-D15 устанавливается в высокоимпедансное состояние. Счетчик команд ЦПОС 26 и адресная шина очищаются, прерывания запрещены.
При поступлении на вход 6 устройства (фиг. 3) кода числа, отличного от нуля (что соответствует подаче на шину запуска 16 устройства фиг. 1 единичного импульса), на выходе блока сравнения 25 формируется сигнал высокого уровня, поступающий на вход ЦПОС 26. В результате под воздействием тактовых импульсов, поступающих на вход 1 устройства (фиг. 3) ЦПОС 26 на своих выходах D0-D15, A0 - A11 формирует необходимые сигналы. Так, сигнал с выхода ЦПОС 26 через элементы 29 и 31 поступает на счетчик 27. Здесь формируется адрес и в ОЗУ 28 записывается очередной отсчет f(xk) интерполируемой функции, поступающий на вход 8 устройства (фиг. 3). При поступлении всех отсчетов f(xk) интерполируемой функции устройство (фиг. 3) осуществляет вычисление БПФ. Полученные значения Fk ЦПОС 26 по шине данных последовательно передает на вход блока умножения 6 (выход 9). При этом ЦПОС 26 на выходах A0 - A11 передает по шине управления (выход 2) адрес для блока памяти 11. Сигналы, разрешающие запись в блок памяти 16 значений коэффициентов сплайна (выход 3) подаются со входа 1 устройства (фиг. 3) через элемент И 37, открываемый высоким потенциалом, формируемым на выходе 2 блока 30. Сигналы, управляющие работой блоков 9 и 13 сплайн-интерполятора (фиг. 1), подаются со входа 1 устройства (фиг. 3) через элемент И 35, открываемый высоким потенциалом, формируемым на выходе 3 блока 30. Сигналы, управляющие работой блоков 2 и 14 сплайн-интерполятора (фиг. 1), подаются со входа 1 устройства (фиг. 3) через элемент И 34, открываемый высоким потенциалом, формируемым на выходе 4 блока 30. Кроме того, по шине управления (выход 2) устройства (фиг. 3) поступают сигналы управления, необходимые для блока ОБПФ 7:
со входа 1 устройства (фиг. 3) через элемент И 36, открываемый высоким потенциалом, формируемым на выходе 5 блока 30 - для подачи на вход CLCIN ЦПОС 38 (фиг. 4);
с выхода блока сравнения 25 - для подачи на вход ЦПОС 38 (фиг. 4).
При поступлении на вход 6 устройства (фиг. 3) кода числа 0 (что соответствует обнулению счетчика 2) и выполнения в блоке 25 операции сравнения на выходе последнего формируется низкий потенциал. Данный потенциал подается на вход ЦПОС 26. При этом на выходах стробирующих сигналов устанавливается высокий уровень, а шина данных D0-D15 устанавливается в высокоимпедансное состояние. Счетчик команд ЦПОС 26 и адресная шина очищаются, прерывания запрещены. Кроме того, сигнал низкого уровня с выхода блока сравнения 25 по шине управления (выход 2) подается на управляющий вход блока ОБПФ 7, останавливая его работу. На выходах 3, 4, 5 устройства (фиг. 3) присутствует низкий потенциал. На этом работа устройства (фиг. 3) завершается.
Блок ОБПФ 7 может быть реализован, как показано на фиг. 4. Реализация элементов блока ОБПФ 7 аналогична реализации соответствующих элементов совокупности блоков 3 и 4 (фиг. 3). Это следует из того факта, что операция ОБПФ отличается от операции БПФ только входными данными и коэффициентами преобразования (см., например, [5]).
Блок ОБПФ 7, приведенный на фиг. 4, работает следующим образом. Под воздействием тактовых импульсов, поступающих на вход CLCIN по шине управления, ЦПОС 38 за своих выходах D0-D15, A0 - A11 формирует необходимые сигналы. Так, сигнал с выхода ЦПОС 38 через элементы 43 и 45 поступает на счетчик 39. Здесь формируется адрес и в ОЗУ 40 записывается очередное значение Fk/u3k, поступающее на информационный вход устройства (фиг. 4). При поступлении всех значений Fk/u3k устройство (фиг. 4) осуществляет вычисление ОБПФ коэффициентов gn. Полученные значения коэффициентов сплайна (1/2) · g0, (1/2) · g1, (1/2) · g2 ЦПОС 38 по шине данных последовательно передает на информационный вход блока памяти 8. При поступлении по управляющей шине на вход ЦПОС 38 нулевого потенциала на выводах стробирующих сигналов устанавливается высокий уровень, а шина данных D0 - D15 устанавливается в высокоимпедансное состояние. Счетчик команд ЦПОС 38 и адресная шина очищаются, прерывания запрещаются. На этом работа блока ОБПФ (фиг. 4) завершается.
Блок формирования параметров сплайна 9 работает следующим образом.
В исходном состоянии на входы 9.7 блока формирования параметров сплайна 9 подается код числа 3 с установочной шины 21.
На первую группу входов умножителя 91 поступает значение τ0 с выхода первого блока памяти 1, а на другую группу его входов - значение M с выхода счетчика 2. В результате выполнения операции умножения на выходах умножителя 91 формируется значение τ = M·τ0. Последнее поступает на входы преобразователя в дополнительный код 92, на выходах которого имеет величину (1-τ). Значение τ с выходов умножителя 91 одновременно поступает на первую и вторую группы входов умножителя 93, а на первую и вторую группы входов умножителя 94 - значение (1-τ). В результате выполнения операции умножения на выходах блоков 93 и 94 формируются значения соответственно τ2 и (1-τ)2. Код числа τ2 подается на выход 9.6 блока 9 через элемент задержки 98 и на первую группу входов умножителя 95. На его вторую группу входов подается код числа 3. В результате выполнения операции умножения на выходах блока 95 имеем значение 3τ2. Последнее поступает на группу входов вычитаемого блока вычитания 97. На его группу входов уменьшаемого поступает значение (1-τ)2, задержанное в блоке 96. В результате выполнения операции вычитания на выходах блока 97 формируется величина (1-τ)2-3τ2, поступающая на выход 9.9 блока 9. На выход 9.4 блока 9 подается код числа (1-τ)2, задержанный в блоках 96 и 99. Элементы задержки 96, 98 и 99 введены для того, чтобы указанные значения параметров сплайна формировались на выходах 9.4, 9.9 и 9.6 блока 9 одновременно.
Умножители 91, 93, 94 и 95 можно реализовать на микросхемах SN54284 и SN54285 или на микросхеме ADSP1016.
Преобразователь в дополнительный код 92 можно реализовать на микросхемах К155ЛА3, К155ЛП5, К155ЛЕ4 и К155ЛН1, как описано в [15] на с. 462 - 468.
Элементы задержки 96, 98 и 99 являются однотипными. Элемент задержки 99, показанный на фиг. 6, содержит n каскадно соединенных регистров. Входы первого 991 регистра являются группой информационных входов элемента задержки. Выходы каждого регистра подключены к соответствующим входам последующего регистра, кроме n-го регистра 99n, выходы которого являются группой выходов элемента задержки. Управляющие входы регистров объединены и подключены к управляющему входу блока 99. Для элементов 96 и 99n = 2. Для элемента 98n = 3. Регистры можно реализовать на микросхемах К155ИР13.
Принцип работы блока вычитания 97 известен и описан в [9] на с. 184 - 198. Блок вычитания на основе полных сумматоров приведен там же на с. 190, рис. 5.38. Можно реализовать на элементах ИСКЛ. ИЛИ - К155ЛП5, И - К155ЛИ1, ИЛИ - из ИЛИ-НЕ К155ЛЕ4 и НЕ К155ЛН1.
Литература
1. Желудев В. А. Локальная сплайн-аппроксимация на равномерной сетке. //Журнал вычислительной математики и математической физики, - 1987. - Том 27. - N 9. - с. 1296 - 1310.
2. Желудев В.А. Восстановление функций и их производных по сеточным данным с погрешностью при помощи локальных сплайнов. //Журнал вычислительной математики и математической физики, - 1987. - Том 27. - N 1. - с. 22 - 34.
3. Желудев В. А. Периодические сплайны и быстрое преобразование Фурье. //Журнал вычислительной математики и математической физики, - 1992. - Том 32. - N 2. - с. 179 - 198.
4. Желудев В.А. Локальные сглаживающие сплайны с регулирующим параметром. //Журнал вычислительной математики и математической физики, - 1991 - Том 31. - N 2. - с. 193 - 211.
5. Л. Рабинер, Б. Голд Теория и применение цифровой обработки сигналов. - М.: Мир. - 1978.
6. В. Л. Шило Популярные цифровые микросхемы. Справочник. - М.: Радио и связь, 1988.
7. М. А. Карцев, В.А. Брик Вычислительные системы и синхронная арифметика. - М.: Радио и связь, 1981.
8. С. Кун. Матричные процессоры на СБИС: Пер. с англ. - М.: Мир, 1991.
9. Д. Гивоне, Р. Россе Микропроцессоры и микрокомпьютеры: Вводный курс: Пер. с англ. - М.: Мир, 1983.
10. В. Л. Шило. Популярные цифровые микросхемы. Справочник. - М.: 2-е изд., испр., - Челябинск: Металлургия, 1989.
11. Цифровой процессор обработки сигналов TMS32010 и его применение. /Под ред. А.А. Ланнэ. - Л.: ВАС, 1990.
12. В. Н. Вениаминов, О.Н. Лебедев, А.И. Мирошниченко Микросхемы и их применение. Справочное пособие - 3-е изд. перераб. и дополн. - М.: Радио и связь, 1989.
13. Хоровиц П. , Хилл У. Искусство схемотехники: в 2-х т. Т. 1. Пер. с англ. Изд. 2-е, стереотип. - М.: Мир, 1984.
14. Ю. В. Гаврилов, А.Н. Пучко Арифметические устройства быстродействующих ЭЦВМ. - М.: Советские радио, 1970.
15. Л. М. Гольденберг Импульсные и цифровые устройства. - М.: Связь, 1973.
Формула изобретения: 1. Сплайн-интерполятор, содержащий первый и второй блоки памяти, первый, второй, третий и четвертый умножители, сумматор, регистр, блок управления и счетчик, группа информационных входов которого объединена с адресными входами первого блока памяти и одновременно является первой установочной шиной сплайн-интерполятора, вычитающий вход счетчика объединен со входом управления регистра и пятым выходом блока управления, а информационные выходы объединены с шестой группой входов блока управления, первый вход которого является тактовой шиной сплайн-интерполятора, а третий выход соединен со входом управления второго блока памяти, первая, вторая и третья группы выходов которого соединены с первыми группами входов соответственно первого, второго и третьего умножителей, группы выходов которых соединены соответственно с первой, второй и третьей группами информационных входов сумматора, группа выходов которого соединена с информационными входами регистра, выходы которого являются группой информационных выходов сплайн-интерполятора, отличающийся тем, что дополнительно введены блок быстрого преобразования Фурье, третий блок памяти, блок обратного быстрого преобразования Фурье и блок формирования параметров сплайна, первая группа входов которого соединена с информационными выходами первого блока памяти, вторая группа входов соединена с информационными выходами счетчика, управляющий вход которого является шиной запуска сплайн-интерполятора, а вход обнуления - шиной обнуления сплайн-интерполятора, седьмая группа входов блока формирования параметров сплайна является второй установочной шиной сплайн-интерполятора, четвертая, пятая и шестая группы выходов соединены со вторыми группами входов соответственно третьего, второго и первого умножителей, а третий вход объединен с управляющим входом сумматора и четвертым выходом блока управления, седьмая группа входов которого является третьей установочной шиной сплайн-интерполятора, а вторая группа выходов соединена с адресными входами третьего блока памяти, входами управления блока обратного быстрого преобразования Фурье и входами управления блока быстрого преобразования Фурье, информационные входы которого являются информационной шиной сплайн-интерполятора, а информационные выходы соединены с первой группой входов четвертого умножителя, вторая группа входов которого соединена с информационными выходами третьего блока памяти, а выходы соединены с информационными входами блока обратного быстрого преобразования Фурье, информационные выходы которого соединены с информационными входами второго блока памяти.
2. Сплайн-интерполятор по п.1, отличающийся тем, что блок формирования параметров сплайна содержит первый, второй, третий и четвертый умножители, преобразователь в дополнительный код, первый, второй и третий элементы задержки и блок вычитания, причем первая группа входов первого умножителя является первой группой входов блока формирования параметров сплайна, вторая группа входов - второй группой входов блока формирования параметров сплайна, а выходы поразрядно объединены с первой и второй группами входов второго умножителя и входами преобразователя в дополнительный код, выходы которого соединены поразрядно с первой и второй группами входов третьего умножителя, выходы которого соединены с информационными входами первого элемента задержки, выходы которого соединены с группой входов уменьшаемого блока вычитания и информационными входами третьего элемента задержки, выходы которого являются четвертой группой выходов блока формирования параметров сплайна, а управляющий вход объединен с третьим входом блока формирования параметров сплайна и управляющими входами первого и второго элементов задержки, и управляющим входом блока вычитания, группа входов вычитаемого которого соединена с выходами четвертого умножителя, вторая группа входов которого является седьмой группой входов блока формирования параметров сплайна и одновременно является второй установочной шиной сплайн-интерполятора, а первая группа входов объединена с выходами второго умножителя и информационными входами второго элемента задержки, выходы которого являются шестой группой выходов блока формирования параметров сплайна, а выходы блока вычитания являются пятой группой выходов блока формирования параметров сплайна.