Вычислить определитель следующей матрицы и показать, что ранг ее трем;

равен

2 I 2 i 1 2 1 О I

2.18. (ДПФ переставленной последовательности). Рассмотрим дискретное преобразование Фурье

и предположим, что а взаимно просто с п. Пусть перестановка компонент вектора v задается равенством v >i{ai)y Доказать, что

является перестановкой компонент вектора V, задаваемой равенством - y(bk)) некоторого целого Ь, взаимно простого с п.

2.19. Год содержит самое большое 366 дней. Предположим, что все месяцы за исключением последнего содержат по 31 дню.

а. Можно ли однозначно определить порядковый номер дня в году по заданным его номерам в месяце и неделе?

б. Предположим далее, что месяц содержит 31 день, а неделя - 12 дней. Можно ли теперь однозначно определить порядковый номер дня в году по заданным его номерам в месяце и неделе?

в. Используя 31-дневный месяц и 12-дневную неделю, выписать формулу для вычисления порядкового номера дня в году через его номера в месяце и неделе.

г. Сделать несколько числовых примеров.

2.20. Сколько векторов содержится в векторном пространстве GF (2)?

2.21. Правильно ли утверждение о том, что если х, у и z линейно независимы над GF (q), то также линейно независимы векторы х--у, у-- zn z-j- х?

2.22. Доказать, что если S и Т - два двумерных различных подпространства трехмерного пространства, то нх пересечение образует одномерное подпространство.

2.23. Пусть 5 - произвольное конечное множество. Пусть G - множество всех подмножеств множества S. Для двух множеств А к В через Л (J В обозначим множество всех элементов, которые принадлежат хотя бы одному из множеств А или В; через А f] В - множество всех элементов, которые принадлежат одновременно и Л, и В; через Л - В - множество элементов, принадлежащих А, но не принадлежащих В.

а. Показать, что множество G с операцией объединения U множеств в качестве групповой операции * ве является группой.

б. Операция симметрической разности множеств Д определяется равенством

Л АВ= (А-В) и (В- Л).

Показать, что множество G с симметрической разностью в качестве групповой операции образует группу. Является ли она абелевой?

в. Показать, что множество G с операциями Д и П образует кольцо. Является ли это кольцо коммутативным? Содержит ли это кольцо единицу?

Замечания

В этой главе рассматривался обычный материал современной алгебры. Можно указать много учебников, в которых этот материал излагается более детально. В качестве легко усваиваемого вводного курса, по уровню достаточного для данной книги, мы рекомендуем книгу Биркгофа и Маклейна [1] (1941). А\онография Ван дер Вардена [2] (1949, 1953) представляет собой курс более высокого уровня, адресованный в основном математикам и углубленно излагающий многие вопросы. Материал по линейной алгебре и теории матриц можно найти также и в учебниках, специально Посвященных этим разделам алгебры. Особенно подходящей представляется книга Тралля и Торнгейма [З] (1957), так как в отличие от многих других книг в ней не предполагается, что рассматриваемое поле является полем вещественных или комплексных чисел ). В книге Полларда [71 в явном виде изложено понятие преобразования Фурье в произвольном поле.

Поля Галуа названы в честь Эвариста Галуа (1811-1832). Абелевы группы названы в честь Нильса Хенрика Абеля (1802-1829).

) Не требующее предварительной подготовки хорошее изложение начал линейной алгебры и теории матриц можно найти также в книге: Головина Л. И. Линейная алгебра и некоторые ее приложения, -4-е изд. - М.: Наука, 1985. Более углубленное изложение содержится в следующих книгах: Курош А. .Г. Курс высшей алгебры. - 11-е изд. - М.: Наука, 1975; Мальцев А. И. Основы линейной алгебры.-4-е изд, - М.: Наука, 1975. - Прим. перев.

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

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

3.1. Циклические свертки и линейные свертки

В компактном виде линейная свертка записывается как произведение многочленов

s(x) =g(x)d(x). Коэффициенты Sj этого многочлена даются равенствами

h = 11 gi-kd i = Q.....L + N~l,

где deg g (х) = L - 1 и deg d (x) = iV - 1.

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

Циклическая свертка,

S (X) = g (х) d (х) (mod х - 1),

где deg g (х) = 1 ствами

I d {х) = п - 1, коэффициенты даются равен-

= Е gut-k))dk, i = О, . .., п - \,

и двойные скобки обозначают вычисления ро модулю п, если вычислять ее прямо по выписанным формулам, содержит if умножений и п (п - 1) сложений. Циклическую свертку можно также вычислять как линейную свертку с последующим приведением по модулю X - 1 Следовательно, эффективные способы вычисления линейной свертки приводят также к эффективным методам вычисления циклической свертки. Наоборот, эффективные методы вычисления циклической свертки можно легко превратить в эффективные методы вычисления линейной свертки.

Популярным способом вычисления циклической свертки является использование теоремы о свертке и дискретного преобразования Фурье. Согласно теореме о свертке в частотной области,

Sft = GjOi, ft = О, ..., n - 1,

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

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

} При N = L линейную (L х Al-cseptky часто называют Л-точечной линейной сверткой, а циклическую свертку по модулю ~ I часто называют п-точечной циклической сверткой. - Прим. перев.

БЫСТРЫЕ АЛГОРИТМЫ КОРОТКИХ СВЕРТОК

Выход

Рис- 3.1. Вычисление циклической свертки с помощью преобразовання Фурье.

Вещественное преобразование Фурье обладает свойством симметрии (см. задачу 2.12)

n = V , * = 0.....п-1.

Предположим, что d и d - вещественные векторы длины п и пусть компоненты комплексного вектора d длины п задаются правилом

di = d, + idi, i = 0.....п-1.

Тогда его дискретное преобразование Фурье удовлетворяет равенствам

D =--Dt + jDl = D; - jDl Следовательно,

, A =0.....n-1.

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

k = Q.....п-1.

Рис. 3,2. Вычисление двух вещественных циклических сверток с помощью преобразования Фурье.

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

Di = Dl + jDl, k = 0.....п-1.

где в общем случае и и являются комплексными числами. Тогда обратное преобразование Фурье приводит к равенствам

d( = d, + /di, 1=0.....п-1,

из которых обе вещественные последовательности вычисляются немедленно.