Аппаратно-программная реализация алгоритма восстановления интерполяционными сплайнами

This algorithm sets a sequence of data conversions that mainly are the characteristics of one neuron. We do not circumscribe an exact sequence of interneuron data exchange, as it cannot be defined because of asynchronous character of interaction.

The algorithm of asynchronous iterations (8) has allowed applying the numerical methods for PDE solving on cellular neural networks. We used multigrid smoothing to improve convergence speed. Our numerical results showed that remarkable accelerations rates ware achieved by these techniques.

REFERENCES

1. Chua L. O., Yang L. Cellular Neural Networks Theory// IEEE Transactions on Circuits and Systems, 1988, vol. 35, No10,

pp. 1257 - 1272.

2. Lijuan S., Panzhen W., Xinyu W. The Application of Cellular Neural Networks for Solving Partial Differential Equations// The Journal of China Universities of Posts and Telecommuni-cations,1997, vol. 4, No.1, pp.45-50.

3. Baudet G.M. The Design and Analysis of the Algorithms for Asynchronous Multiprocessors. Ph.D. Diss.-Pittsburg: Carnegie-Mellon Univ.,1978, PA, 182 p.

4. McCormic S., Rodrigue G.H. Multigrid Methods for Multiprocessor Computers. Tecn. Rept. - Lawrence Livermore: Lab. Livermore CA, 1979, 29 p.

5. Wesseling P. An Introduction to Multigrid Methods. John Wil-ley & Sons, Chichester, 1992, 294 p.

6. Brandt A., Yavneh I. Accelerated multigrid convergence and high-Reynolds recirculating flows// SIAM Journal on Scientific. Computing., 1993, vol. 14, pp. 607-626.

7. Reusken A. Steplength optimization and linear multigrid methods// Numer. Math, 1991, vol. 58, pp. 819-838.

8. Vanek P. Fast multigrid solver// Appl. Of Math., 1995, vol.40, pp. 1-20.

УДК 681.2.06

АППАРАТНО-ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ВОССТАНОВЛЕНИЯ ИНТЕРПОЛЯЦИОННЫМИ СПЛАЙНАМИ

А.Ю.Балыкова, В.М.Жигачев, Б.В.Чувыкин

Розглянуто питання проектування гнтерполюючих анало-го-цифрових ф1льтр1в, що реал1зують алгоритми сплайн-iнтерполяцп. Приведено приклади розрахунку вар1ант1в структур АЦФ i результати iмiтацiйного моделювання.

Рассмотрены вопросы проектирования интерполирующих аналого-цифровых фильтров, реализующих алгоритмы сплайн-интерполяции. Приведены примеры расчета вариантов структур АЦФ и результаты имитационного моделирования.

The questions of designing of an interpolation analog-digital filters (ADF) realizing algorithms of spline-interpolation are considered. The examples of realization of variants of structures ADF and results of imitating modeling are given.

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

Рассмотрим наиболее важные свойства сплайнов.

Сплайны - это финитные функции, составленные из "кусочков" многочленов данной степени, которые состыкованы так, чтобы получившаяся функция была непрерывной и обладала несколькими непрерывными производными, т.е. была достаточно "гладкой".

Полиномиальный сплайн степени n для равномерных отсчетов (сплайн Шенберга) имеет вид [1]:

n + 1

B

k = 0

где знак "+" обозначает одностороннее ограничение:

tn =

tn, t > 0; 0, t< 0.

Если рассматривать полиномиальный сплайн (1) как импульсную характеристику (ИХ) некоторого аналого-цифрового фильтра (АЦФ), то можно найти его передаточную функцию через преобразование Лапласа:

Hn(p) = I (Bn (t)) = { 1 - 7/ * \'

где Ь - оператор преобразования Лапласа, р - оператор дифференцирования, Н - шаг дискретизации. Поскольку оператору аналоговой задержки ехр (-рН) на шаг дискретизации Н для цифрового входного сигнала соответствует оператор дискретной задержки г-1, то передаточная функция (2) АЦФ можно представить в виде функции двух переменных, что соответствует аналоговой и цифровой представлении информации:

Hn(z, p) = (1 - z-1)n -(ph)-

В соответствии с формулой (3) реализация алгоритма восстановления цифрового сигнала интерполяционным сплайном состоит из процедур формирования п -ой конеч-

ной разности и п -кратного интегрирования последовательности 5 -импульсов.

Формально структуру АЦФ с передаточной функцией (3) можно представить в виде последовательного включения типовых динамических звеньев: конечной разности (1 - г-1), формирователя 5 -импульсов и интегрирования 1/(кр). Функция сплайна нулевого порядка (п = 0) реализует цифроаналоговый преобразователь (ЦАП), математическая модель которого определена в виде

(1 - г-1)/кр. С учетом вышесказанного структура АЦФ с передаточной функцией (3) будет иметь вид, приведенный на рис. 1.

Рисунок 1

Полиномиальные сплайны Шенберга степени п = 0 и п = 1 являются интерполяционными (ступенча-тая и линейная интерполяция), т.е. для них выполняется условие интерполяции:

Вп( кк) =

1, к = т; 0, к ф т,

где т - номер узла интерполяции, к = 0, 1, ...п . В случае более высоких порядков условие (4) не выполняется и поэтому необходимо ввести дополнительные аналоговый или цифровой корректирующие фильтры. Аналоговый корректирующий фильтр будет иметь передаточную функцию вида:

Кп (Р) = а 0 + а1Р + ••• + акРк + ••• + апРп

N «0 «1 «2 «3 т

п = 2 1 1/2 0 - 1

1 -1/2 0 - 2

1 1 1/3 0 1

п = 3 1 0 -1/6 0 2

1 -1 1/3 0 3

Передаточную функцию корректирующего фильтра (5) можно реализовать путем введения в структуру АЦФ сумматора с весовыми коэффициентами ак . Соответствующая структура аналоговой части АЦФ приведена на рисунке 2.

Рисунок 2

На рисунке 3 приведен пример кубического интерполяционного сплайна У3 (/) (п = 3, т = 2, а1 = 0,

а2 = -1 / 6, а3 = 0). Для сравнения приведен сплайн Шенберга В (/) этого же порядка.

Коэффициенты ак находятся из условия интерполяции (4). Ниже в табл. 1 приведены значения коэффициентов ак для интерполяционных сплайнов третьего и четвертого порядка [2].

Таблица 1 - Коэффициенты интерполяционных сплайнов

Рисунок 3

Для алгоритма цифровой коррекции передаточная функция ЦФ задается в виде:

К,,

Коэффициенты находятся из условия интерполяции (4). Соответствующая структура цифровой части АЦФ приведена на рисунке 4.

,-1

I

4ч

Л*]

Рисунок 4

48

1607-3274 "Радюелектрошка. 1нформатика. Управл1ння" № 1, 2003

В качестве примера рассмотрим интерполяционный сплайн для п = 3 [3]

У3

где коэффициенты а^ = (2 - „/3.

Значение 5 можно ограничить порядком 3-5, поскольку ряд коэффициентов ак быстро сходится. На рисунке 5 приведен пример кубического интерполяционного сплайна у3(г) (п = 3) для варианта 5 = 3 . Точность выполнения условия интерполяции в крайних точек интервала ИХ соответствует 10-3. При необходимости точность интерполяции в узлах может быть повышена за счет увеличения 5, но при этом увеличится длительность ИХ и потребуется увеличение операций умножений и суммирования при реализации алгоритма корректирующего фильтра. Для сравнения приведен сплайн Шенберга В (г) этого же порядка (рис.5).

Рассмотренные выше сплайн-интерполирующие АЦФ имеют разомкнутую структуру, состоящую из звеньев не удовлетворяющих условию физической реализуемости (аналоговые интеграторы). Для обеспечения устойчивости АЦФ необходимо ввести цепи обратной связи (ОС), т.е. перейти к замкнутой структуре. Замкнутые структуры АЦФ могут отличаться вариантами ОС. Обобщенный вариант канонической структуры многопетлевой ОС приведен ниже. В этом случае в цепях ОС последовательно включены АЦП, нерекурсивные ЦФ с передаточными функцией Wn ^(г) и рекурсивный ЦФ с передаточной

функцией 1 /Уп ^(г) в прямом канале преобразования.

А

Ь

1

А

\

1\м

\7

1± |1ш I" 1>Н- 1М I 41 1чп

I

Рисунок 5

Рисунок 6

Коэффициенты передаточных функций Wn (г) и 1 / Уп (г) находятся из условия абсолютной устойчивости

замкнутой структуры по критерию финитности ИХ АЦФ и приведены в таблице 2.

Таблица 2 - Коэффициенты передаточных функций

п = 1 п = 2

^2 ^2

-1 0 -5/2 -3/2 -1

=1 У1 =1 = 0 W2 21 - 3/5г-1 V, = 1 + 3/4 г-1 W 2, 1 = 1 2 = 1 У2 = 1

п = 3

^2 ^3 ^2 1 со ^2 1 со ^2 ^3

0 0 -35/36 0 -23/6 -1 -1 0 -3 -11/6 -2 -1

= 0 ^,2 = 0 W3 3=1 - 46/35г-1+17/35г-2 У3 = 1+73/ 36 г-1 + 73/ 36г-2 W3, 1 = 0 W3 2= 1 - 11/23г-1 3 =1 У3 = 1+11/13 г-1 W3 1 = 1 - 23/6г-1 W3,2 = 0 W3 3 = -2/3г-1 У3 = 1+7 / 2 г-1 W3, 1 = 1 2 = 1 3 =1 У3 = 1

Рисунок 7

О т т но да ян йю w ¿л vft mu

Рисунок 8

Для анализа погрешностей сплайн-интерполирующего АЦФ можно использовать метод имитационного моделирования в среде Simulink 4.0 пакета Matlab 6.0. Это позволяет получить качественные и количественные характеристики интерполирующего АЦФ, необходимые для решения задач проектирования и оценки методических и инструментальных погрешностей процедур восстановления цифровых сигналов. В качестве примера на рисунке 7 приведена имитационная модель сплайн-интерполирую-щего АЦФ на базе трех интеграторов (n = 3) с цифровым корректирующим фильтром (s = 3).

На рисунке 8 приведена ИХ, которая совпадает с ИХ, полученной аналитически.

Таким образом, использование АЦФ замкнутой структуры позволяют реализовывать в аналого-цифровой форме алгоритмы восстановления цифровых сигналов, в основе которых лежат методы сплайн-интерполяции.

ПЕРЕЧЕНЬ ССЫЛОК

1. Альберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения. - М.: Мир, 1972. - 292с.

2. Михотин В.Д., Чувыкин Б.В. Использование сплайнов для восстановления дискретизированных сигналов // Измерение, контроль, автоматизация. - 1982. - №3 (43). - С.17-24.

3. Чувыкин Б.В. Финитные функции. Теория и инженерные приложения // Монография: Под ред. Э.К. Шахова. -Пенза: Изд-во Пенз. гос. ун-та, 1999. - 100 с.

50

ISSN 1607-3274 "Радюелектрошка. 1нформатика. Управл1ння" № 1, 2003