Сплайны как средство построения эффективных алгоритмов локального линейного преобразования

В работе рассматривается частное решение общей задачи синтеза эффективного алгоритма вычисления свертки, возникающее при использовании сплайнов для представления конечной импульсной характеристики (КИХ). Исходя из необходимых условий строгой эффективности индуцированного алгоритма, которые были сформулированы в предыдущей работе [13] в виде требований к неоднородному ЛРС (определяющему отсчеты КИХ), и установленной в настоящей работе явной связи между основными характеристиками сплайна и его представлением в виде ЛРС, приведено обоснование использования сплайнов для решения задачи синтеза эффективного алгоритма. Представлен алгоритм модели CR вычисления свертки, порождаемый произвольным сплайном с конкретными характеристиками. Приведены явные выражения для вычислительной сложности порождаемого алгоритма для случаев обобщенных и полиномиальных сплайнов. При ограничении множества сплайнов параметрами (порядок-число узлов) приведены верхние и нижние границы для вычислительной сложности порождаемых этими сплайнами алгоритмов вычисления свертки. Введено понятие МС-сплайнов, как сплайнов, для которых величина сложности реализации порождаемого ими алгоритма достигает своей нижней границы. Приведены примеры построения полиномиальных МС-сплайнов.