|
|
Ладно, в двух словах:
Есть такое алгебраическое понятие: поле. Элементы поля можно складывать/вычитать и умножать/делить. Можно над ними решать системы линейных уравнений. Множества действительных, комплексных или рациональных чисел - это пример бесконечных полей. Множество целых чисел - это не поле, так как в поле должен существовать обратный по умножению элемент у каждого числа, кроме нуля.
Поля Галуа - это поля с конечным числом элементов. В настоящее время широко используются в технике, например, для избыточного кодирования информации. Код Рида-Соломона, используемый в CD, основан как раз на алгебраических вычислениях в поле GF(256).
Другой пример полей Галуа - это множества классов вычетов целых чисел по модулю простого числа. Если совсем на пальцах: берем целые числа в диапазоне [0:P-1] и определяем сложение и умножение как сложение и умножение целых чисел по модулю P.
Если в поле существует нетривиальный корени из единицы степени N (то есть, такой элемент Q != 1, что Q^N = 1), то в этом поле существует и преобразование Фурье длины N, для которого верна, например, теорема о свертке. Например, в поле комплексных чисел существует нетривиальный корень из 1 степени N для любого N. Этот елемент равен exp(2*pi*i/N). В поле действительных чисел такой элемент не существует, поэтому, чтобы использовать теорему о свертке в поле действительных чисел приходится их вкладывать в поле комплексных чисел.
Если нужно подсчитать свертку целочисленных последовательностей, то можно целые числа используемого диапазона вложить в подходящее поле Галуа, вычислить в нем свертку, пользуясь преобразованием Фурье в этом поле, и если в ходе свертки получаются только целые числа из заданного дапазона, результат будет точо совпадать с лобовой сверткой. Да и сложение/умножение действительных чисел по модулю P обычно проще, чем сложение/умножение в поле комплексных чисел. Не говоря про то, что комплексные числа невозможно точно предствить в компьютере, поэтому всегда будет некоторая погрешность вычисления, связанная с округлениями.
E-mail: 
info@telesys.ru
