В.М. Чернов, А.О. Корепанов
Теоретико-числовые преобразования
в задачах цифровой обработки сигналов
Электронное учебное пособие
САМАРА
2010
2
Авторы:
ЧЕРНОВ Владимир Михайлович,
КОРЕПАНОВ Андрей Олегович
Содержание пособия относится к пограничной области между информатикой (теория
и практика анализа и обработки многомерных цифровых сигналов) и математикой (абст
рактная алгебра и теория чисел). <...> 3
ВВЕДЕНИЕ
При вычислении свертки двух ЛАиериодических последовательностей спек
тральным методом с помощью теоремы о свертке (см., например, [1], [2]) и использо
вании дискретного преобразования Фурье значения сворачиваемых последовательно
стей считаются, как правило, принадлежащими полю рациональных чисел Q (естест
венное "пользовательское" допущение) или, после соответствующего масштабирова
ния, нринадлежащими кольцу целых чисел Z . <...> В то же время значения базисных функ
ций дискретного преобразования Фурье принадлежит полю комплексных чисел С алгебраическому расширению R (i) ноля R с индуцированной метрикой, связанной с
обычным понятием модуля комплексного числа, которое, в свою очередь, является по
полнением ноля Q относительно метрики, связанной с абсолютной величиной числа. <...> Паллиативным решением в этом случае
является использование вместо дискретного преобразования Фурье его "модулярных
аналогов" - теоретико-числовых преобразований (ТЧП, преобразований Фурье-Галуа). <...> Модулярные вычисления можно интерпретировать как "приближенные вычис
ления" в некоторой алгебраической структуре, причем эта "приближенность" харак
теризуется делимостью "погрешности" на простое число р. <...> Одной из целей данного пособия является метрическая формализация выше
приведенной интерпретации, что позволило бы с единой точки зрения проанализиро
вать, как и особенности снектральных методов вычисления свертки, так и экстрапо
лировать эти спектральные методы для вложений поля Q в его пополнения относи
тельно других, так называемых <...>
Теоретико-числовые_преобразования_в_задачах_цифровой_обработки_сигналов_[Электронный_ресурс]_.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВБ1СШЕГ0 НРОФЕССИОНАЛБНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ Г0СУДАРСТВЕННБ1Й АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.Н.КОРОЛЕВА
(НАЦИ0НАЛБНБ1Й ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)»
В.М. Чернов, А.О. Корепанов
Теоретико-числовые преобразования
в задачах цифровой обработки сигналов
Электронное учебное пособие
САМАРА
2010
Стр.1
2
Авторы:
ЧЕРНОВ Владимир Михайлович,
КОРЕПАНОВ Андрей Олегович
Содержание пособия относится к пограничной области между информатикой (теория
и практика анализа и обработки многомерных цифровых сигналов) и математикой (абстрактная
алгебра и теория чисел).
Специалисты в области анализа и обработки цифровой информации давно и успешно
используют алгебраические и теоретико-числовые методы, прежде всего в таких областях,
как криптография, корректирующие коды, синтез быстрых алгоритмов дискретных ортогональных
преобразований. Несмотря на это, существует относительно мало доступной монографической
литературы, охватывающей не только одну или несколько из указанных уже
традиционных областей применения методов абстрактной алгебры и теории чисел к решению
задач информатики, но и рассматривающей относительно новые приложения указанных
математических методов и теорий к решению перспективных задач анализа цифровых сигналов.
Ряд монографий отечественных или зарубежных авторов давно уже стал библиографической
редкостью, а книги, изданные за рубежом, практически недоступны широкому
кругу специалистов. Данное пособие ставит своей целью частичное восполнение указанного
пробела.
Пособие предназначено для магистров направления 010400.68 "Прикладная математика
и информатика", обучающихся по программе «Математические и компьютерные методы
обработки изображений и геоинформатики».
Стр.2
3
ВВЕДЕНИЕ
При вычислении свертки двух ЛАиериодических последовательностей спектральным
методом с помощью теоремы о свертке (см., например, [1], [2]) и использовании
дискретного преобразования Фурье значения сворачиваемых последовательностей
считаются, как правило, принадлежащими полю рациональных чисел Q (естественное
"пользовательское" допущение) или, после соответствующего масштабирования,
нринадлежащими кольцу целых чисел Z . В то же время значения базисных функций
дискретного преобразования Фурье принадлежит полю комплексных чисел С -
алгебраическому расширению R (i) ноля R с индуцированной метрикой, связанной с
обычным понятием модуля комплексного числа, которое, в свою очередь, является пополнением
ноля Q относительно метрики, связанной с абсолютной величиной числа.
Таким образом, поле Q вкладывается в полное поле С, причем при реализации на
ЭВМ в силу конечноразрядного представления чисел вычисление нреобразования (1.2)
производится в Q (i), что приводит к погрешности, часто весьма значительной.
Для ряда задач цифровой обработки сигналов (задач криптографии, задачи умножения
больших целых чисел, в частности) принципиально не допускается "приближенный"
ответ. Либо точный, либо - не ответ. Паллиативным решением в этом случае
является использование вместо дискретного преобразования Фурье его "модулярных
аналогов" - теоретико-числовых преобразований (ТЧП, преобразований Фурье-Галуа).
Модулярные вычисления можно интерпретировать как "приближенные вычисления"
в некоторой алгебраической структуре, причем эта "приближенность" характеризуется
делимостью "погрешности" на простое число р.
Одной из целей данного пособия является метрическая формализация вышеприведенной
интерпретации, что позволило бы с единой точки зрения проанализировать,
как и особенности снектральных методов вычисления свертки, так и экстраполировать
эти спектральные методы для вложений поля Q в его пополнения относительно
других, так называемых неархимедовых, метрик поля Q. Реализация программы
для тех или иных конкретных метрик позволит с единой точки зрения анализировать
точность как известных алгоритмов (ДПФ, преобразование Фурье-Галуа),
так и позволит увеличить точность вычисления свертки даже при относительно
скромных вычислительных возможностях.
Стр.3