сплайн-интерполятор

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

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

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

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

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

Известные устройства (АС СССР 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), выбранный в качестве устройства-прототипа.

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

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

(1)

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

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

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

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

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

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

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

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

(2)

где [0,1], а дискретное преобразование Фурье от коэффициентов g_n вычисляется по формуле [3]

F_k(g_n) = F_k(f(x))/u_n. (3)

Массив коэффициентов g_n получается обратным преобразованием Фурье от F_k (g_n):

(4)

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

(5)

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

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

Реализация (2) - (5) в виде устройства позволяет вычислять функции f(x) C⁷ с точностью (определяемой погрешностью интерполяции), равной (см. [3] на с. 187):

< 0(h⁷f⁽⁷⁾_max). (6)

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

(7)

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

Заявленное устройство поясняется чертежами, на которых:

На фиг. 1 приведена структурная схема заявленного устройства;

на фиг. 2 представлена структурная схема блока формирования параметров сплайна;

на фиг. 3 приведена структурная схема блока управления;

на фиг. 4 представлена структурная схема блока обратного быстрого преобразования Фурье сплайна;

на фиг. 5 показан один из возможных вариантов построения второго блока памяти;

на фиг. 6 показан вариант реализации элемента задержки;

на фиг. 7 представлен один из возможных вариантов реализации блока возведения в пятую степень.

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

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

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

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

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

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

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

В блоке обратного быстрого преобразования Фурье 7 происходит вычисление значений коэффициентов сплайна (1/120) g_-2, (1/120) g_-1, (1/120) g₀, (1/120) g₁, (1/120) g₂, (1/120) g₃ в соответствии с выражением (2). Полученные значения коэффициентов сплайна с выхода блока обратного быстрого преобразования Фурье 7 переписываются во второй блок памяти 8 под воздействием импульсов, поступающих на управляющий вход последнего с выхода 3 блока управления 3.

Далее под воздействием информационных сигналов, поступающих с выходов блоков 1 и 2, сигналов, подаваемых на пятую установочную шину 21 устройства, и управляющих сигналов (с выхода 4 блока управления 3), в блоке формирования параметров сплайна 9 происходит вычисление значений Полученные величины поступают на вторые группы входов умножителей 10, 11, 12, 13, 14, 15. На первые группы входов последних подаются соответствующие значения (1/120) g_-2, (1/120) g_-1, (1/120) g₀, (1/120) g₁, (1/120) g₂, (1/120) g₃ с информационных выходов второго блока памяти 8.

В результате выполнения операций умножения на выходах умножителей 10, 11, 12, 13, 14, 15 формируются произведения Последние поступают на соответствующие группы информационных входов сумматора 16.

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

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

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

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

Входящие в структурную схему заявляемого устройства элементы известны и описаны, например, в [6]. Так, в указанном источнике описаны принципы построения и примеры реализации:

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

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

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

Принцип работы умножителей 6, 10 - 15 известен и описан в [7]. Могут быть реализованы на микросхемах SN54284 и SN54285 (с. 305, рис. 6.3.12) или на микросхеме ADSP1016 (см. [8] на с. 502, табл. 7.4).

Принцип работы сумматора 16 известен и описан в [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, 86. Входы записи регистров блока 8 объединены и подключены к управляющему входу блока 8. Информационные входы первого регистра 81 являются информационными входами блока памяти 8. Выходы каждого из шести регистров являются соответствующими выходными информационными шинами блока памяти 8. Регистры можно реализовать на микросхеме К155ИР13.

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

В исходном состоянии на вход 9.1 блока формирования параметров сплайна 9 подается код числа 15 с установочной шины 24. На вход 9.2 поступает код числа -6 с шины 25. На входе 9.3 присутствует код числа 1 с установочной шины 26. На вход 9.6 поступают управляющие сигналы с выхода 4 блока управления 3.

На первый вход умножителя 91 поступает значение ₀ с выхода блока памяти 1, а на второй вход блока умножения 91 - значение M с выхода счетчика 2. В результате выполнения операции умножения на выходе умножителя 91 формируется значение = M₀. Последнее поступает на вход преобразователя в дополнительный код 92, на выходе которого имеем значение (1-). Значение с выхода умножителя 91 поступает также на первый вход сумматора 93, а на первый вход сумматора 94 - значение (1-). На вторые входы сумматоров 93 и 94 подается код числа 1. Под воздействием управляющих сигналов, поступающих на вход 9.6 блока 9 (с выхода 4 блока управления 3) на выходах сумматоров 93 и 94 формируются значения соответственно (1+) и (2-). Последние подаются на первые входы сумматоров 97 и 98 соответственно. На вторые входы сумматоров подается код числа 1. В результате выполнения операции суммирования на выходах сумматоров 97 и 98 формируются значения +2 и 3- соответственно. Указанные величины поступают на входы соответствующих блоков возведения в пятую степень 914 и 915. На вход блока возведения в пятую степень 95 поступает значение с выхода умножителя 91. На вход блока возведения в пятую степень 96 поступает значение +1 с выхода сумматора 93. На вход блока возведения в пятую степень 99 поступает значение 2- с выхода сумматора 94. На вход блока возведения в пятую степень 910 поступает значение 1- с выхода преобразователя в дополнительный код 92. На выходах блоков возведения в пятую степень 95, 96, 914, 915, 99 и 910 имеем значения соответственно с выхода блока возведения в пятую степень 95 поступает на первые входы умножителей 911 и 912. На второй вход умножителя 911 подается код числа 15, а на второй вход умножителя 912 - код числа -6. В результате выполнения операции умножения на выходах умножителей 911 и 912 формируются значения соответственно 15⁵ и -6⁵. Величины (+1)⁵ и (2-)⁵ подаются на первые входы умножителей 913 и 916 соответственно. На вторые входы этих умножителей подается код числа -6. В результате выполнения умножения на выходах умножителей 913 и 916 формируются значения соответственно -6(+1)⁵ и -6(2-)⁵. Значение (1-)⁵ с выхода блока возведения в пятую степень 910 поступает на первые входы умножителей 917 и 918. На второй вход умножителя 917 подается код числа -6, а на второй вход умножителя 918 - код числа 15. В результате выполнения операции умножения на выходах умножителей 917 и 918 формируются значения соответственно -6(1-)⁵ и 15(1-)⁵. С выхода умножителя 912 на первый вход сумматора 921 поступает значение -6⁵. Одновременно на второй вход сумматора 921 поступает значение (+1)⁵ с выхода блока возведения в пятую степень 96. В результате выполнения операции суммирования на выходе сумматора 921 формируется значение (+1)⁵-6⁵. Последнее через элемент задержки 926 подается на выход 9.11 блока формирования параметров сплайна 9. Величина 15⁵ с выхода умножителя 911 через задержки 919 подается на первый вход сумматора 922. Одновременно на второй вход последнего подается значение -6(+1)⁵ с выхода умножителя 913, а на третий вход - значение (+2)⁵ с выхода блока возведения в пятую степень 914. В результате выполнения операции суммирования на выходе сумматора 922 формируется величина 15⁵+(+2)⁵-6(+1)⁵. Последняя подается на выход 9.10 блока 9. С выхода умножителя 917 на первый вход сумматора 924 поступает значение -6(1-)⁵. Одновременно на второй вход сумматора 924 поступает значение (2-)⁵ с выхода блока возведения в пятую степень 99. В результате выполнения операции суммирования на выходе сумматора 924 формируется значение (2-)⁵-6(1-)⁵. Последнее через элемент задержки 927 подается на выход 9,8 блока формирования параметров сплайна 9. Величина 15(1-)⁵ с выхода умножителя 918 через элемент задержки 520 подается на первый вход сумматора 923. Одновременно на второй вход последнего подается значение -6(2-)⁵ с выхода умножителя 916, а на третий вход - значение (3-)⁵ с выхода блока возведения в пятую степень 915. В результате выполнения операции суммирования на выходе сумматора 924 формируется величина 15(1-)⁵+(3-)⁵-6(2-)⁵. Последняя подается на выход 9,10 блока 9. Значение ⁵ с выхода блока возведения в пятую степень 95 через элемент задержки 925 поступает на выход 9,12. Величина (1-)⁵ с выхода блока возведения в пятую степень 910 через элемент задержки 928 поступает на выход 9,7 блока 9. Таким образом, указанные значения параметров сплайна формируются на выходах 9,7, 9,8, 9,9, 9,10, 9,11 и 9,12 блока 9 одновременно.

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

Сумматоры 93, 94, 97, 98, 921 - 924 можно реализовать на К155ЛП5, К155ЛИ1, К155ЛЕ4 и НЕ К155ЛН1.

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

Элементы задержки 919, 920, 925 - 928 можно реализовать на микросхеме К155ИР13 в соответствии с фиг. 6. Для элементов 919, 920, 926 и 927 n = 2. Для элементов 925 и 928 n = 4.

Блоки возведения в пятую степень 95, 96, 99, 910, 914 и 915 можно реализовать с помощью умножителей, как показано на фиг. 7.

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

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

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

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

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

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

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

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

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

При поступлении на вход 6 устройства (фиг. 3) кода числа, отличного от нуля (что соответствует подаче на шину запуска 20 устройства фиг. 1 единичного импульса), на выходе блока сравнения 27 формируется сигнал высокого уровня, поступающий на вход ЦПОС 28. В результате под воздействием тактовых импульсов, поступающих на вход 1 устройства (фиг. 3) ЦПОС 28 на своих выходах DO-D15, AO-A11 формирует необходимые сигналы. Так, сигнал с выхода ЦПОС 28 через элементы 31 и 33 поступает на счетчик 29. Здесь формируется адрес и в ОЗУ 30 записывается очередной отсчет f(x_k) интерполируемой функции, поступающий на вход 8 устройства (фиг. 3). При поступлении всех отсчетов f(x_k) интерполируемой функции устройство (фиг. 3) осуществляет вычисление быстрого преобразования Фурье. Полученные значения F_k ЦПОС 28 по шине данных последовательно передает на вход блока умножения 6 (выход 9). При этом ЦПОС 28 на выходах АО-А11 передает по шине управления (выход 2) адрес для блока памяти 5. Сигналы, разрушающие запись в блок памяти 8 значений коэффициентов сплайна (выход 3) подаются со входа 1 устройства (фиг. 3) через элемент И 39, открываемый высоким потенциалом, формируемым на выходе 2 блока 32. Сигналы, управляющие работой блоков 9 и 16 сплайн-интерполятора (фиг. 1), подаются со входа 1 устройства (фиг. 3) через элемент И 37, открываемый высоким потенциалом, формируемым на выходе 3 блока 32. Сигналы, управляющие работой блоков 2 и 17 сплайн-интерполятора (фиг. 1), подаются со входа 1 устройства (фиг. 3) через элемент И 36, открываемый высоким потенциалом, формируемым на выходе 4 блока 32. Кроме того, по шине управления (выход 2) устройства (фиг. 3) поступают сигналы управления, необходимые для блока обратного быстрого преобразования Фурье 7:

со входа 1 устройства (фиг. 3) через элемент И 38, открываемый высоким потенциалом, формируемым на выходе 5 блока 32 - для подачи на сход CLCIN ЦПОС (фиг. 4);

с выхода блока сравнения 27 - для подачи на вход ЦПОС 40 (фиг. 4).

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

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

Блок обратного быстрого преобразования Фурье 7, приведенный на фиг. 4, работает следующим образом. Под воздействием тактовых импульсов, поступающих на сход CLCIN по шине управления, ЦПОС 40 на своих выходах DO-D15, AO-A11 формирует необходимые сигналы. Так, сигнал с выхода ЦПОС 40 через элементы 44 и 47 поступает на счетчик 41. Здесь формируется адрес и в ОЗУ 42 записывается очередное значение F_k/u_k, поступающее на информационный вход устройства (фиг. 4). При поступлении всех значений F_k/u_k устройство (фиг. 4) осуществляет вычисление обратного быстрого преобразования Фурье коэффициентов g_n. Полученные значения коэффициентов сплайна (1/120)g-2, (1/120)g-1, (1/120)g0, (1/120)g1, (1/120)g2, (1/120)g3, ЦПОС 40 по шине данных последовательно передает на информационный вход блока памяти 8. При поступлении по управляющей шине на вход ЦПОС 40 нулевого потенциала на выводах стробирующих сигналов устанавливается высокий уровень, а шина данных DO-D15 устанавливается в высокоимпедансное состояние. Счетчик команд ЦПОС 40 и адресная шина очищаются, прерывания запрещаются. На этом работа блока обратного быстрого преобразования Фурье (фиг. 4) завершается.

Литература

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.