И данный алгоритм вычисляет Hd, что и завершает доказательство. □

Теорема 3.8.3. Каждый алгоритм вычисления линейной свертки

S (х) = g (л:) d (х), где uegg (х) = L - I и degd{x) = N - I, содержит по меньшей мере L + N - I умножений.

Доказательство. Рассматриваемое вычисление можно в матричном виде записать равенством

S = Hd,

8о О S, 8.

является {{L + N - \) X Л/)-матрицей. Как элементы множества £ Igo. gii ---.gL-il. строки матрицы Н, очевидно, линейно независимы, следовательно, применение теоремы 3.8.1 показывает, что число умножений равно по меньшей мере L -\- N - 1. □

Теорема 3.8.4. Пусть р (х) является простым многочленом степени п. Каждый алгоритм вычисления произведения многочленов

. s(x) = g (х) d (х) (mod р [х))

содержит по меньшей мере 2п - 1 умножений.

Доказательство. Предположим, что алгоритм содержит t \ умножений. Тогда на выходе алгоритма получим линейную комбинацию этих t членов-произведений

- S = AS,

где А является (п X )-матрицей над полем £, а S - вектор длины t, компонентами которого являются эти члены-произведения.

Ясно, что многочлены g (х) и d (х) всегда можно выбрать так, чтобы сделать некоторую одну компоненту многочлена s (х) ненулевой, а остальные нулевыми. Следовательно, п строк матрицы А должны быть линейно независимыми, так что Л должна содержать и п линейно независимых столбцов. Без потери общности можно полагать, что первые п столбцов матрицы А являются линейно независимыми, так что матрица А может быть разбита на блоки вида

S = (А 1 A-1S,

где А - обратимая {п X п)-матрица. Умножим на обратную к А матрицу С:

Cs = II 1 PIS = CHd.

Так как многочлен р (х) неприводим, то можно показать, что все элементы любой строки матрицы Н линейно независимы, равно как и все элементы любой линейной комбинации строк матрицы Н. Эго утверждение является стандартным результатом теории матриц и будет доказано отдельно в виде теоремы 3.8.6 в конце настоящего раздела. Следовательно, все элементы первой строки матрицы СН линейно независимы, так что согласно теореме 3.8.2 для вычисления первой компоненты вектора CHd требуется по меньшей мере п умножений.

С другой стороны, первая строка вычисления

Cs = [I I PIS,

содержит самое большое \ -\- (t - п) умножений, так как матрица Р содержит t - п столбцов, а вектор S длины t содержит все члены-произведения. Следовательно, 1 -f ( - п) > га, так что i > 2 - 1, что и доказывает теорему. □

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

Хотя мы и не будем этого делать, теорему 3.8.4 можно доказать и для умножения многочленов по модулю многочлена р(х), где р (х) - простой многочлен. Вместо этого мы рассмотрим случай, когда р (х) распадается в произведение k простых многочленов. В этом случае китайская теорема об остатках позволяет разбить задачу на k подзадач, каждая длины п где щ = п.

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

Е (2ni- l) = 2n-ft /=1

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

Теорема 3..5. Пусть многочлен р (х) степени п распадается в произведение k различных простых множителей. Каждый алгоритм вычисления произведения многочленов

S (.х) = g(x)d (х) (mod р (х)) содержит по меньшей мере 2п - к умножений.

Доказательство. Так как китайская теорема об остатках задает не требующее умножений обратимое преобразование, то достаточно рассмотреть вычисление s = Hd, в котором матрица Н блочно-диагональная, т. е.

и соответствующая китайской теореме об остатках i-я подзадача задается вычислением S; = Hdj.

Теперь повторим доказательство теоремы 3.8.4. Предположим, что алгоритм содержит t умножений. Тогда

S = AS, /

где S - вектор длины t, содержащий все члены-произведения, и А представляет собой (п X 0-матрицу над полем Я. Так как А содержит п линейно независимых строк, то она содержит и п\ линейно независимых столбцов, в качестве которых можно вы-, брать первые п столбцов. Тогда ,

S = [А I А IS

Cs = [I I P]S

где С обозначает матрицу, обратную к матрице А. Следовательно, для вычисления первой компоненты вектора Cs требуется самое большое \ + (t - п) умножений. Но, кроме того, выполняется равенство

Cs = С

Рассмотрим теперь некоторую линейную комбинацию строк матрицы Н. Любая линейная комбинация строк каждой из матриц Н; содержит лишь линейно независимые столбцы. Следовательно, любая линейно независимая комбинация строк матрицы Н содержит по меньшей мере п - (к-I) линейно независимых столбцов. Следовательно, по теореме 3.8.2 вычисление первой компоненты вектора CHd требует по меньшей мере п - (к - 1) умножений. Эти верхняя и нижняя границы числа умножений, необходимых для вычисления первой компоненты вектора Cs, приводят к неравенству

1 + ( - п) > п - (А - 1),

так что t~1n - k, что доказывает теорему. □

Теперь мы должны завершить незаконченное доказательство теоремы 3.8.4.

Теорема 3.8.6. Пусть s = Hd представляет собой матричную запись произведения многочленов

s{x)=g (.х) d (X) (mod р (X)),

где р (х) - неприводимый многочлен, и матрица И составлена из коэффициенпюв многочлена g (х). Тогда все элементы любой строки матрицы Н, так же как и все элементы любой линейной комбинации строк матрицы Н, линейно независимы.

Доказательство.

Шаг 1. Обозначим через Cj, сопровождающую матрицу многочлена р (х), определяемую следующей (п X )-матрицей:

о ... о -л

0 ... о -р,

1 ... о -р,

Тогда t-й столбец матрицы И равен Cpg, и через свои вектор-столбцы матрица Н записывается в виде

Н = [g C,g Cpi

crg]-

Пусть w - произвольная ненулевая вектор-строка, а wH - соответствующая линейная комбинация строк матрицы Н. Надо показать, что никакая линейная комбинация столбцов wH не равна нулю. Предположим, что

0= I]a<(wCpg) =

liaiCp

Так кк это равенство должно выполняться для любого g, то w-a(Cp) = 0,

а(Ср) = S aiC\

представляет собой матрицу размера п X п, вычисленную по матрице Ср. Поскольку строка w отлична от нулевой, то матрица а (Ср) должна быть вырожденной, так как в противном случае w-a(Cp) не может равняться нулю. Следовательно, нам надо показать, что единственным многочленом степени не более п - 1, таким что подстановка в него матрицы Ср приводит к вырожденной матрице, является нулевой многочлен. ,

Шаг 2. Легко проверить, что любой простой многочлен р (х) обращается в нуль при подстановке в него его сопровождающей матрицы. Таким образом, р (Ср) = О, где О обозначает нулевую {п X п)-матрицу. Пусть а (х) обозначает многочлен степени не более п - 1, такой что матрица а (Ср) вырожденна, и пусть v обозначает ненулевой вектор из нулевого пространства матрицы а (Ср). Тогда, так как р (х) является неприводимым многочленом степени п, то существуют многочлены А {х) а Р (х), такие что

Следовательно,

А (X) а (х) (А(Ср)а(Ср)Н

- Р{х)р{х) = 1. P(Cp)p(Cp)lv = Iv.

Но р (Ср) = О, так что мы имеем А (Ср) а (Ср) v = v, что npoJ тиворечит выбору v : а (Ср) v = 0. Следовательно, за исключе нием нулевого многочлена, не существует многочлена а (х) степей п - 1 или меньше, такого что матрица а (Ср) является вырожденной. &Г0 завершает доказательство теоремы. □

Задачи

а. Комплексное умножение (е + jf) = (а -- / ) (с -- jiS) можно вычислить с тремя вещественными умножениями и пятью вещественными сложениями по алгоритму

е = (,ii-b)d + a{c - (tj,

f = (a-b)d+ b{c+ i.

Положить cad константами и записать алгоритм умножения в матричной форме

где А И В представляют собой матрицы предсложений и постсложеннй, а D - диагональную матрицу.

6. 2-точечная циклическая свертка s{x) = g (х) d (х) (mod х ~ 1) может быть вычислена по алгоритму

Г1 I 1 -1

о + 1

1 I

1 -I

Предположим, что многочлены d {х) и g {х) имеют комплексные коэффициенты. Сколько потребуется вещественных сложений и вещественных умножений для выполнения этого алгоритма, если комплексная арифметика реализуется обычным классическим способом?

в. Представить теперь входные и выходные данные в виде векторов длины четы:ре и выписать объединенный алгоритм с шестью вещественными умножениями, Сколько вещественных сложений содержит этот алгоритм?

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

вычисления взаимной корреляционной функции V gt+jdt этих после-

довательностей.

3.3. Построить алгоритм фильтрации 4-точечной последовательности входных данных в КИО-фильтре с тремя отводами, используя для этого алгоритм Кука - Тоома для свертки.

3.4. а. Начиная с алгоритма вычисления 2-точечной линейной свертки

S (х) = g.dx + [girfx + godo - igi - go) (rfi - do) U + godo, построить алгоритм вычисления

six) = g (x) d ix) (mod д: - л: + 1). б. Повторить задачу, начиная с алгоритма

S {х) = gldix + [fei + go) (di + do) ~ ВЛ - godo] X + g.

Какой из алгоритмов заслуживает предпочтения?

3.5. Допустим, что у нас имеется устройство {жесткий модуль или подпрограмма) для вычисления 315-точечной циклической свертки, и что требуется пропустить 1000-точечный вектор данных через КИО-фильтр с 100 отво-

. дамн. Описать, как надо разбить данные и организовать устройство свертки, чтобы получить требуемый ответ. З.в. Построить алгоритм 4-точечной циклической свертки комплексных последовательностей, содержащий четыре комплексных умножения. Сравнить построенный алгоритм с алгоритмом 4-точечной циклической свертки вещественных последовательностей, используемым для свертки комплексных последовательностей.

3.7. Одним из способов определения поля комплексных чисел является расширение поля вещественных чисел с помощью неприводимого многочлена Р W = Jc + 1. Комплексное умножение при этом определяется равенством

fi + /д: (а + 6л:) (с + dx) {mod х + 1).

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

3.8. а. Сколько умножений содержит алгоритм Винограда вычисления 16-то-чечной циклической свертки, если в качестве модулей используются только разложения

X-l = {ж- 1) 1) (д9 1J f4+ 1) (в 1JJ