СПЛАЙН-ИНТЕРПОЛЯТОР Российский патент 1999 года по МПК G06F17/17 

Описание патента на изобретение RU2143131C1

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

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

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

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

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

где fmax(3) - максимум третьей производной функции f(x);
h - расстояние между отсчетами функции f(x).

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

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

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

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

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

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

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

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

Значения un5 вычисляются по следующей формуле (см. [4] на с. 200):

где vn = 2sin( π n/N); 1/N = h; f(xk) - дискретный отсчет функции f(x), h - шаг дискретизации функции f(x).

Причем для получения коэффициентов gn целесообразно использовать алгоритм быстрого преобразования Фурье (БПФ) для повышения быстродействия устройства (см. [5] на с. 633-693 и с. 394-432).

Реализация (2) - (5) в виде устройства позволяет вычислять функции f(X) ∈ C6 с точностью (определяемой погрешностью интерполяции), равной (см. [3] на с. 187):
μ < 0(h6f(6)max

).
Известно, что точность глобального сплайна выше, чем локального, так как в этом случае при интерполяции используется весь массив дискретных отсчетов функции. Точность локального сплайна определяется величиной [1, 2].


что лучше по сравнению с прототипом (см. выражение (1)). Следовательно, точность заявленного устройства выше, чем (6) и (1).

Заявленное устройство поясняется чертежами, на которых:
на фиг. 1 приведена структурная схема заявленного устройства;
на фиг. 2 представлена структурная схема блока формирования параметров сплайна;
на фиг. 3 приведен вариант построения устройства, реализующего блок управления и блок быстрого преобразования Фурье;
на фиг. 4 показан один из возможных вариантов построения блока обратного быстрого преобразования Фурье;
на фиг. 5 показан вариант реализации второго блока памяти;
на фиг. 6 представлен один из возможных вариантов реализации элемента задержки;
на фиг. 7 показан вариант реализации блока возведения в четвертую степень.

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

Блок формирования параметров сплайна 9, показанный на фиг. 2, состоит из первого 91, второго 911, третьего 912 и четвертого 916 умножителей, первого 93, второго 94, третьего 95, четвертого 918, пятого 919 и шестого 920 сумматоров, первого 96, второго 97, третьего 98, четвертого 99 и пятого 910 блоков возведения в четвертую степень, первого 913, второго 914, третьего 915, четвертого 917 и пятого 912 элементов задержки и блока преобразования в дополнительный код 92. Первая группа входов первого умножителя 91 является шестой группой входов 9.6 блока формирования параметров сплайна 9, вторая группа входов является пятой группой входов 9.5 блока формирования параметров сплайна 9, а выходы соединены со входами блока преобразования в дополнительный код 92, первыми группами информационных входов первого 93 и второго 94 сумматоров и входами первого блока возведения в четвертую степень 96. Выходы последнего соединены с информационными входами четвертого элемента задержки 917, первыми группами входов второго 911 и третьего 912 умножителей. Вторые входы третьего умножителя 912 объединены со второй группой входов четвертого умножителя 916 и являются первой группой входов 9.1 блока формирования параметров сплайна 9, а выходы соединены с первой группой информационных входов четвертого сумматора 918. Вторая группа информационных входов последнего соединена с выходами второго элемента задержки 914, а выходы являются одиннадцатой группой выходов 9.11 блока формирования параметров сплайна 9. Вторая группа информационных входов первого сумматора 93 является третьей группой входов 9.3 блока формирования параметров сплайна 9, а выходы соединены со входами второго блока возведения в четвертую степень 97. Выходы последнего соединены с информационными входами первого элемента задержки 913, выходы которого соединены со второй группой информационных входов пятого сумматора 919. Первая группа входов пятого сумматора 919 соединена с выходами второго умножителя 911, вторая группа входов которого является второй группой входов 9.2 блока формирования параметров сплайна 9. Вторая группа информационных входов второго сумматора 94 объединена со второй группой информационных входов третьего сумматора 95 и является четвертой группой входов 9.4 блока формирования параметров сплайна 4. Выходы второго сумматора 94 соединены со входами третьего блока возведения в четвертую степень 98, выходы которого соединены с информационными входами второго элемента задержки 914. Первая группа информационных входов третьего сумматора 95 объединена со входами пятого блока возведения в четвертую степень 910 и выходами блока преобразования в дополнительный код 92. Выходы третьего сумматора 95 соединены со входами четвертого блока возведения в четвертую степень 99, выходы которого соединены с информационными входами третьего элемента задержки 915. Выходы последнего соединены с первой группой информационных входов шестого сумматора 920, вторая группа информационных входов которого соединена с выходами четвертого умножителя 916 и третьей группой информационных входов пятого сумматора 919, а выходы являются девятой группой выходов 9.9 блока формирования параметров сплайна 9. Выходы пятого блока возведения в четвертую степень 910 соединены с первой группой входов четвертого умножителя 916 и информационными входами пятого элемента задержки 921. Выходы последнего являются восьмой группой выходов 9.8 блока формирования параметров сплайна 9. Управляющий вход первого элемента задержки 913 объединен с управляющими входами второго 914, третьего 915, четвертого 917 и пятого 921 элементов задержки, управляющими входами первого 93, второго 94, третьего 95, четвертого 918, пятого 919 и шестого 920 сумматоров и одновременно является седьмым входом 9.7 блока формирования параметров сплайна 9. Выходы пятого сумматора 919 являются десятой группой выходов 9.10 блока формирования параметров сплайна 9. Выходы четвертого элемента задержки 917 являются двенадцатой группой выходов 9.12 блока формирования параметров сплайна 9.

Заявленное устройство работает следующим образом.

В исходном состоянии на первую установочную шину 19 подается код числа M, где M соответствует задаваемому количеству точек интерполяции функции f(x) между соседними узлами интерполяции. На тактовую шину 22 поступают тактовые импульсы типа меандр. На установочной шине 21 присутствует код числа 0, на установочной шине 24 - код числа - 5, на установочной шине 25 - код числа 10, на установочной шине 26 - код числа 2, на установочной шине 27 - код числа 1. В первом блоке памяти 1 записаны значения τo таким образом, что в ячейке с адресом M хранится значение τo , равное 1/(1+M). В третьем блоке памяти 5 хранятся значения 1/un5.

Перед началом работы счетчик 2 устанавливается в нулевое состояние подачей на его вход сброса по шине 18 импульса положительной полярности. При этом код числа 0 воздействует на вход 6 блока управления 3, в результате чего устройство удерживается в исходном состоянии.

С подачей на шину запуска 20 импульса положительной полярности в счетчик 2 записывается код числа M. Код числа M с выхода счетчика 2 поступает на вход 6 блока управления 3. На информационную шину 6 подаются отсчеты функции f(xk), которые поступают в блок быстрого преобразования Фурье (БПФ) 4. Под воздействием тактовых импульсов, поступающих по тактовой шине 22, и управляющих сигналов, поступающих с группы выходов 2 блока управления 3, в блоке БПФ 4 происходит вычисление значений Fk. Указанные величины поступают на первую группу входов умножителя 6.

Под воздействием управляющих сигналов, поступающих с группы выходов 2 блока управления 3 на адресные входы третьего блока памяти 5, на информационных выходах последнего формируются значения 1/uk5. Данные величины подаются на вторую группу входов четвертого умножителя 6. В результате выполнения операций умножения на выходе четвертого умножителя 6 формируются значения Fk/uk5. Последние поступают в блок обратного быстрого преобразования Фурье (ОБПФ). 7.

В блоке ОБПФ 7 происходит вычисление значений коэффициентов сплайна (1/24)•g-2, (1/24)•g-1, (1/224)•g0, (1/24)•g1, (1/24)•g2 в соответствии с выражением (4). Полученные значения коэффициентов сплайна с выхода блока ОБПФ 7 переписываются во второй блок памяти 8 под воздействием импульсов, поступающих на управляющий вход последнего с выхода 3 блока управления 3.

Далее под воздействием информационных сигналов, поступающих с выходов блоков 1 и 2, сигналов, подаваемых на установочную шину 21 устройства, и управляющих сигналов (с выхода 4 блока управления 3), в блоке формирования параметров сплайна 9 происходит вычисление значений τ4, [(1+τ)4-5τ4], [(τ+2)4-5(τ+1)4+10τ4], [(2-τ)4-5(1-τ)4], (1-τ)4. Полученные величины поступают на вторые группы входов умножителей 10, 11, 12, 13, 14. На первые группы входов последних подаются соответствующие значения (1/24)•g2, (1/24)•g1, (1/24)•g0, (1/24)•g-1, (1/24)•-2 с информационных выходов второго блока памяти 8.

В результате выполнения операций умножения на выходах умножителей 10, 11, 12, 13, 14 формируются произведения (1/24)•gn+2•τ4, (1/24)•gn+1[(1+τ)4-5τ4], (1/24)•gn[(τ+2)4-5(τ+1)4+10τ4], (1/24)•gn-1[(2-τ)4-5(1-τ)4], (1/24)•gn-2(1-τ)4 . Последние поступают на соответствующие группы информационных входов сумматора 15.

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

Полученное значение функции f(x) записывается в регистр 16 при помощи единичного импульса, поступающего с выхода 5 блока управления 3 на вход записи регистра 16.

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

Далее алгоритм работы устройства аналогичен. В блоке формирования параметров сплайна 9 формируются значения параметров сплайна, а в блоках 10-15 вычисляются значения функции f(x), которые записываются в регистр 16. Данная операция повторяется для значений τ равных τo (M-1), затем τo (M-2) и т.д. до тех пор, пока содержимое счетчика 2 не станет равным нулю. При этом код числа 0 с выхода счетчика 2 поступает на вход 6 блока управления 3 и останавливает работу устройства. На этом работа устройства по вычислению значений функции f(x) завершается. Устройство готово к новому циклу работы.

Входящие в структурную схему заявляемого устройства элементы известны и описаны, например, в [6] . Так, в указанном источнике описаны принципы построения и примеры реализации:
счетчика 2 на с. 85-86 (можно реализовать на микросхеме К155ИЕ5);
блоков памяти 1, 5 на с. 171-174 (можно реализовать на микросхеме К155ПР6);
регистра 16 на с. 104-105 (можно реализовать на микросхеме К155ИР13 - с. 111 рис. 1.78);
Принцип работы умножителей 6, 10-14 известен и описан в [7]. Могут быть реализованы на микросхемах SN54284 и SN54285 (с. 305, рис. 6.3.12) или на микросхеме ADSP1016 (см. [8] на с. 502, табл. 7.4).

Принцип работы сумматора 15 известен и описан в [9] на с. 184-198. Полный сумматор описан в [10] на с. 152, рис. 1.112, с. 153, рис. 1.113. Можно реализовать на элементах ИСКЛ. ИЛИ - К155ЛП5, И - К155ЛИ1, ИЛИ - из ИЛИ-НЕ К155ЛЕ4 и НЕ К155ЛН1.

Один из возможных вариантов построения второго блока памяти 8 показан на фиг. 5. Блок памяти 8 состоит из пяти последовательно соединенных регистров 81, 82, 83, 84, 85. Входы записи регистров блока 8 объединены и подключены к управляющему входу блока 8. Информационные входы первого регистра 81 являются информационными входами блока памяти 8. Выходы каждого из пяти регистров являются соответствующими выходными информационными шинами блока памяти 8. Регистры можно реализовать на микросхеме К155ИР13.

Совокупность блоков 3 и 4 может быть реализована на цифровом процессоре обработки сигналов (ЦПОС) TMS32010 с дополнительными элементами, как показано на фиг. 3 (входы и выходы устройства, представленного на фиг. 3, полностью соответствуют входам и выходам группы блоков, обведенных прерывистой линией на фиг. 1). При этом блок БПФ 4 реализован на ЦПОС (блок 29), оперативном запоминающем стройстве (ОЗУ) 31 и элементах 30, 32, 34, 35. Блок управления 3 реализован на ЦПОС 29 и элементах 33, 37, 38, 39, 40. Принцип действия TNS32010 подробно рассмотрен в [11] на с. 51-102. Сам процессор изображен на с. 75, рис. 3.1.

Принцип действия элемента 33 известен и описан в [6] на с. 130 - 136, рис. 1.97. Может быть реализован на микросхемах К155ИД7, К531ИД7.

Счетчик 30 - реверсивный, 16-разрядный. Принцип работы известен и описан в [6] на с. 85 - 93 и с. 91 рис. 1.67. Может быть реализован на микросхеме К155ИЕ7. Порядок соединения четырех счетчиков описан в этой же книге на с. 92 - 93.

Принцип действия ОЗУ 31 известен и описан в [12] на с. 145 - 148. Можно реализовать на микросхеме IDT 7186-70 (описана в [11] на с. 50).

Принцип работы элементов И-НЕ 35 и 36, ИЛИ-НЕ 32 и 34 известен и описан в [13] на с. 510, рис. 8.5.

Принцип работы блока сравнения 28 известен и описан в [14] на с. 234-257. Можно реализовать на микросхемах К561ИП2 (см. [12] с. 114, рис. 4.12 б).

Принцип построения и пример реализации элементов И 37 - 40 описаны в [6] на с. 35 рис. 1.19а (можно реализовать на микросхеме К155ЛИ1).

Принцип БПФ и ОБПФ известен и описан в [5]. Пример реализации БПФ на ЦПОС TMS32010 приведен в [11] на с. 259, а на с. 260 приведен расчет необходимой для этого памяти.

Устройство, реализующее блоки 3, 4 и приведенное на фиг. 3, работает следующим образом. В исходном состоянии на вход 1 устройства (фиг. 3) и соответственно на вход CLCIN ЦПОС 29 поступают импульсы типа меандр по тактовой шине 22 сплайн-интерполятора (фиг. 1). На вход 7 поступает код числа 0 (с установочной шины 21 сплайн-интерполятора). На вход 6 подается код числа 0 (с выхода счетчика 2 сплайн-интерполятора). В результате выполнения операции сравнения в блоке 28 на выходе последнего формируется сигнал низкого уровня. Данный сигнал подается на вход ЦПОС 29. При этом на выводах стробирующих сигналов устанавливается высокий уровень, а шина данных D0-D15 устанавливается в высокоимпедансное состояние. Счетчик команд ЦПОС 29 и адресная шина очищаются, прерывания запрещены.

При поступлении на вход 6 устройства (фиг. 3) кода числа, отличного от нуля (что соответствует подаче на шину запуска 20 устройства фиг. 1 единичного импульса), на выходе блока сравнения 28 формируется сигнал высокого уровня, поступающий на вход ЦПОС 29. В результате под воздействием тактовых импульсов, поступающих на вход 1 устройства (фиг. 3) ЦПОС 29 на своих выходах D0-D15, A0-A11 формирует необходимые сигналы. Так, сигнал с выхода ЦПОС 29 через элементы 32 и 34 поступает на счетчик 30. Здесь формируется адрес и в ОЗУ 31 записывается очередной отсчет f(xk) интерполируемой функции, поступающий на вход 8 устройства (фиг. 3). При поступлении всех отсчетов f(xk) интерполируемой функции устройство (фиг. 3) осуществляет вычисление БПФ. Полученные значения Fk ЦПОС 29 по шине данных последовательно передает на вход блока умножения 6 (выход 9). При этом ЦПОС 29 на выходах A0-A11 передает по шине управления (выход 2) адрес для блока памяти 5. Сигналы, разрешающие запись в блок памяти 8 значений коэффициентов сплайна (выход 3) подаются со входа 1 устройства (фиг. 3) через элемент И 40, открываемый высоким потенциалом, формируемым на выходе 2 блока 33. Сигналы, управляющие работой блоков 9 и 15 сплайн-интерполятора (фиг. 1), подаются со входа 1 устройства (фиг. 3) через элемент И 38, открываемый высоким потенциалом, формируемым на выходе 3 блока 33. Сигналы, управляющие работой блоков 2 и 16 сплайн-интерполятора (фиг. 1), подаются со входа 1 устройства (фиг. 3) через элемент И 37, открываемый высоким потенциалом, формируемым на выходе 4 блока 33. Кроме того, по шине управления (выход 2) устройства (фиг. 3) поступают сигналы управления, необходимые для блока ОБПФ 7:
со входа 1 устройства (фиг. 3) через элемент И 39, открываемый высоким потенциалом, формируемым на выходе 5 блока 33 - для подачи на вход CLCIN ЦПОС 41 (фиг. 4);
с выхода блока сравнения 28 - для подачи на вход ЦПОС 41 (фиг. 4).

При поступлении на вход 6 устройства (фиг. 3) кода числа 0 (что соответствует обнулению счетчика 2) и выполнении в блоке 28 операции сравнения на выходе последнего формируется низкий потенциал. Данный потенциал подается на вход ЦПОС 29. При этом на выводах стробирующих сигналов устанавливается высокий уровень, а шина данных D0-D15 устанавливается в высокоимпедансное состояние. Счетчик команд ЦПОС 29 и адресная шина очищаются, прерывания запрещены. Кроме того, сигнал низкого уровня с выхода блока сравнения 28 по шине управления (выход 2) подается на управляющий вход блока ОБПФ 7, останавливая его работу. На выходах 3, 4, 5 устройства (фиг. 3) присутствует низкий потенциал. На этом работа устройства (фиг. 3) завершается.

Блок ОБПФ 7 может быть реализован, как показано на фиг. 4. Реализация элементов блока ОБПФ 7 аналогична реализации соответствующих элементов совокупности блоков 3 и 4 (фиг. 3). Это следует из того факта, что операция ОБПФ отличается от операции БПФ только входными данными и коэффициентами преобразования (см., например, [5]).

Блок ОБПФ 7, приведенный на фиг. 4, работает следующим образом. Под воздействием тактовых импульсов, поступающих на вход CLCIN по шине управления, ЦПОС 41 на своих выходах D0-D15, A0-A11 формирует необходимые сигналы. Так, сигнал с выхода ЦПОС 41 через элементы 45 и 48 поступает на счетчик 42. Здесь формируется адрес и в ОЗУ 43 записывается очередное значение Fk/uk5, поступающее на информационный вход устройства (фиг. 4). При поступлении всех значений Fk/uk3 устройство (фиг. 4) осуществляет вычисление ОБПФ коэффициентов gn. Полученные значения коэффициентов сплайна (1/24)•g-2, (1/24)•g-1, (1/24)•g0, (1/24)•g1, (1/24)•g2 ЦПОС 41 по шине данных последовательно передает на информационный вход блока памяти 8. При поступлении по управляющей шине на вход ЦПОС 41 нулевого потенциала на выводах стробирующих сигналов устанавливается высокий уровень, а шина данных D0-D15 устанавливается в высокоимпедансное состояние. Счетчик команд ЦПОС 41 и адресная шина очищаются, прерывания запрещаются. На этом работа блока ОБПФ (фиг. 4) завершается.

Блок формирования параметров сплайна 9 работает следующим образом.

В исходном состоянии на входы 9.1 блока формирования параметров сплайна 9 подается код числа - 5 с установочной шины 24. На входы 9.2 поступает код числа 10 с установочной шины 25. На входах 9.3 присутствует код числа 2 с установочной шины 26, а на входах 9.4 - код числа 1 с установочной шины 27. На вход 9.7 поступают управляющие сигналы с четвертого выхода блока управления 3.

На первую группу входов умножителя 91 поступает значение τo с выхода первого блока памяти 1, а на другую группу его входов - значение M с выхода счетчика 2. В результате выполнения операции умножения на выходах умножителя 91 формируется значение τ = M•τo . Последнее поступает на входы преобразователя в дополнительный код 92, на выходах которого имеем значение (1 - τ ). Значение τ с выходов умножителя 91 поступает также на первые группы информационных входов сумматоров 93 и 94, а на первую группу входов сумматора 95 - значение (1 - τ ). На вторые группы входов сумматоров 94 и 95 подается код числа 1, а на вторую группу входов сумматора 93 - код числа 2. Под воздействием управляющих сигналов, поступающих на вход 9.7 блока 9 на выходах сумматоров 93, 94 и 95 формируются значения соответственно (2 + τ ), (1 + τ ) и (2 - τ ). Указанные величины поступают на входы соответствующих блоков возведения в четвертую степень 97, 98 и 99. На входы блока возведения в четвертую степень 96 поступает значение τ с выходов умножителя 91. На входы блока возведения в четвертую степень 910 поступает величина (1 - τ ) с выхода преобразователя в дополнительный код 92. На выходах блоков возведения в четвертую степень 96, 97, 98, 99 и 910 имеем значения соответственно τ4, (τ+2)4, (τ+1)4, (2-τ)4 и (1-τ)4 . Величина τ4 с выходов блока возведения в четвертую степень 96 поступает на первые группы входов умножителей 911 и 912. На вторую группу входов умножителя 911 подается код числа 10, а на вторую группу входов умножителя 912 - код числа - 5. В результате выполнения операции умножения на выходах умножителей 911 и 912 формируются значения соответственно 10τ4 и -5τ4 . Последние поступают на первые группы информационных входов сумматоров соответственно 919 и 918. На вторые группы информационных входов сумматоров 918 и 919 подаются величины соответственно ( τ + 1)4 (через элемент задержки 914) и ( τ +2)4 (через элемент задержки 913). Значение (1 - τ )4 с выходов блока возведения в четвертую степень 910 поступает на первую группу входов умножителя 916, на вторую группу входов которого подается код числа - 5. В результате выполнения операции умножения на выходах умножителя 916 формируется значение - 5 (1 - τ )4. Последнее подается на вторую группу информационных входов сумматора 920. На первую группу информационных входов сумматора 920 поступает значение (2 - τ )4 с выходов блока возведения в четвертую степень 99 через элемент задержки 915. В результате выполнения операций суммирования в блоках 918, 919 и 920 на выходах последних имеем значения соответственно [(1+τ)4-5τ4], [(τ+2)4-5(τ+1)4+10τ4] и [(2-τ)4-5(1-τ)4] . Указанные величины поступают на соответствующие выходы 9.11, 9.10 и 9.9 блока формирования параметров сплайна 9. На выходы 9.12 и 9.8 блока 9 подаются значения соответственно τ4 (с выходов блока возведения в четвертую степень 96 через элемент задержки 917) и (1 - τ )4 (с выходов блока возведения в четвертую степень 910 через элемент задержки 921). Таким образом, указанные значения параметров сплайна формируются на выходах 9.8 - 9.12 блока 9 одновременно.

Умножители 91, 911, 912, 916 можно реализовать на микросхемах SN54284 и SN54285 или на микросхеме ADSP1016.

Сумматоры 93 - 95, 918 - 920 можно реализовать на К155ЛП5, К155ЛИ1, К155ЛЕ4 и НЕ К155ЛН1.

Принцип реализации преобразования в дополнительный код 92 известен и описан в [15] на с. 462-468. Можно реализовать на микросхемах К155ЛА3, К155ЛП5, К155ЛЕ4 и К155ЛН1.

Элементы задержки 913 - 915, 917, 921 являются однотипными. Их можно реализовать на микросхемах К155ИР13 в соответствии с фиг. 6. Элемент задержки 913, показанный на фиг. 6, содержит n каскадно соединенных регистров. Входы первого 9131 регистра являются группой информационных входов элемента задержки. Выходы каждого регистра подключены к соответствующим входам последующего регистра, кроме n-го регистра 913n, выходы которого являются группой выходов элемента задержки. Управляющие входы регистров объединены и подключены к управляющему входу блока 913. Для элементов 913, 914 и 915 n = 2. Для элементов 917 и 921 n = 3.

Блоки возведения в четвертую степень 96 - 910 являются однотипными. Данные блоки можно реализовать с помощью умножителей, как показано на фиг. 7, на микросхемах SN54284 и SN54285 или на микросхеме ADSP1016. Блок возведения в четвертую степень 96, показанный на фиг. 7, состоит из первого 961 и второго 962 умножителей. Первая группа входов первого умножителя 961 объединена со второй группой его входов и является группой входов блока. Группа выходов первого умножителя 961 соединена с первой и второй группами входов второго умножителя 962, группа выходов которого является группой выходов блока.

Литература
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.

Похожие патенты RU2143131C1

название год авторы номер документа
СПЛАЙН-ИНТЕРПОЛЯТОР 1998
  • Агиевич С.Н.
  • Колесников В.Б.
  • Макеев В.М.
  • Малышев С.Р.
  • Подымов В.А.
  • Смирнов П.Л.
RU2143132C1
СПЛАЙН-ИНТЕРПОЛЯТОР 1997
  • Агиевич С.Н.
  • Смирнов П.Л.
  • Подымов В.А.
  • Малышев С.Р.
RU2116669C1
СПЛАЙН-ИНТЕРПОЛЯТОР 1998
  • Агиевич С.Н.
  • Дворников С.В.
  • Малышев С.Р.
  • Подымов В.А.
  • Смирнов П.Л.
RU2140099C1
СПЛАЙН-ИНТЕРПОЛЯТОР 1997
  • Агиевич С.Н.
  • Смирнов П.Л.
  • Малышев С.Р.
  • Подымов В.А.
RU2127901C1
СПЛАЙН-ИНТЕРПОЛЯТОР 1998
  • Агиевич С.Н.
  • Смирнов П.Л.
  • Подымов В.А.
  • Малышев С.Р.
RU2140098C1
СПЛАЙН-ИНТЕРПОЛЯТОР 1997
  • Агиевич С.Н.
  • Смирнов П.Л.
  • Подымов В.А.
  • Малышев С.Р.
RU2116668C1
СПЛАЙН-ИНТЕРПОЛЯТОР 1998
  • Агиевич С.Н.
  • Малышев С.Р.
  • Мусаев А.А.
  • Подымов В.А.
  • Смирнов П.Л.
RU2132567C1
ИНТЕРПОЛЯТОР 1997
  • Агиевич С.Н.
  • Смирнов П.Л.
  • Подымов В.А.
  • Малышев С.Р.
RU2127903C1
ИНТЕРПОЛЯТОР 1998
  • Смирнов П.Л.
  • Агиевич С.Н.
  • Подымов В.А.
  • Малышев С.Р.
RU2132568C1
ИНТЕРПОЛЯТОР 1997
  • Агиевич С.Н.
  • Смирнов П.Л.
  • Подымов В.А.
  • Малышев С.Р.
RU2120137C1

Иллюстрации к изобретению RU 2 143 131 C1

Реферат патента 1999 года СПЛАЙН-ИНТЕРПОЛЯТОР

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

Формула изобретения RU 2 143 131 C1

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

Документы, цитированные в отчете о поиске Патент 1999 года RU2143131C1

Сплайн-интерполятор 1989
  • Шутко Николай Александрович
  • Шелевицкий Игорь Владимирович
  • Бедный Николай Семенович
  • Картавая Татьяна Геннадиевна
  • Денисюк Владимир Петрович
SU1686461A1
Интерполятор 1986
  • Грездов Геннадий Иванович
  • Дубовой Иван Филиппович
  • Саурин Антон Анатольевич
  • Черняк Владимир Николаевич
SU1405074A1
JP 62078678 A, 10.04.87
JP 05128269 A, 25.05.93
JP 59081763 A, 11.05.84.

RU 2 143 131 C1

Авторы

Агиевич С.Н.

Малышев С.Р.

Подымов В.А.

Смирнов П.Л.

Даты

1999-12-20Публикация

1998-05-26Подача