Вычисление преобразований Фурье-Галуа в редуцированных бинарных системах счисления
Автор: Чернов Владимир Михайлович
Журнал: Компьютерная оптика @computer-optics
Рубрика: Численные методы и анализ данных
Статья в выпуске: 3 т.42, 2018 года.
Бесплатный доступ
В работе предлагается новый метод вычисления преобразований Фурье-Галуа (теоретико-числовых преобразований), являющихся модулярным аналогом дискретного преобразования Фурье. Ряд специфических проблем, связанных с вычислением преобразований в конечном поле, удаётся решить с помощью представления элементов этих полей в «экзотических» системах счисления, являющихся редукциями канонических систем счисления И. Катаи при отображении соответствующего кольца целых квадратичного поля в поле классов вычетов по простому модулю. Подробно исследуется случай бинарных редуцированных систем счисления. Доказывается, что такие системы счисления существуют для любого простого числа.
Преобразования фурье-галуа, конечные поля, канонические и редуцированные системы счисления
Короткий адрес: https://sciup.org/140228753
IDR: 140228753 | DOI: 10.18287/2412-6179-2018-42-3-495-500
Список литературы Вычисление преобразований Фурье-Галуа в редуцированных бинарных системах счисления
- Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток/Г. Нуссбаумер; пер. с англ. -М.: Радио и связь, 1985. -248 с.
- Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов/Р. Блейхут; пер с англ. -М: Мир, 1989. -448 с.
- Rader, C.M. Discrete convolution via Mersenne transforms/C.M. Rader//IEEE Transactions on Computers. -1972. -Vol. C-21, Issue 12. -P. 1269-1273. - DOI: 10.1109/T-C.1972.223497
- Schönhage, A. Schnelle Multiplikation großer Zahlen/A. Schönhage, V. Strassen//Computing. -1966. -Vol. 7, Issue 3-4. -P. 281-292. - DOI: 10.1007/BF02242355
- Вариченко, Л.В. Абстрактные алгебраические системы и цифровая обработка сигналов/Л.В. Вариченко, В.Г. Лабунец, М.А. Раков. -Киев: Наукова думка, 1986. -247 с.
- Alfredson, L.-I. VLSI architectures and arithmetic operations with application to the Fermat number transform/L.-I. Alfredson. -Linköping, Sweden: Linköping University, 1996. -296 p. -ISBN: 91-7871-694-2.
- Golomb, S.W. Properties of the sequence 3∙2n+1/S.W. Golomb//Mathematics of Computation. -1976. -Vol. 30, Issue 135. -P. 657-663. - DOI: 10.1090/S0025-5718-1976-0404129-8
- Chernov, V.M. Fast algorithm for "error-free" convolution computation using Mersenne-Lucas codes/V.M. Chernov//Chaos, Solitons and Fractals. -2006. -Vol. 29, Issue 2. -P. 372-380. - DOI: 10.1016/j.chaos.2005.08.081
- Чернов, В.М. Квазипараллельный алгоритм безошибочного вычисления свёртки в редуцированных кодах Мерсенна-Люка/В.М. Чернов//Компьютерная оптика. -2015. -Т. 39, № 2. -С. 241-248. - DOI: 10.18287/0134-2452-2015-39-2-241-248
- Чернов, В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований/В.М. Чернов. -М.: Физматлит, 2007. -264 с. -ISBN: 5-9221-0940-6.
- Koblitz, N. Algebraic aspects of cryptography/N. Koblitz. -Berlin, Heidelberg: Springer-Verlag, 1998. -206 p. -ISBN: 978-3-540-63446-1.
- Боревич, З.И. Теория чисел/З.И. Боревич, И.Р. Шафаревич. -3-е изд. -М.: Наука, 1985. -504 с.
- Kátai, I. Canonical number systems in imaginary quadratic fields/I. Kátai, B. Kovács//Acta Mathematica Hungarica. -1981. -Vol. 37, Issues 1-3. -P. 159-164. - DOI: 10.1007/BF01904880
- Богданов, П.С. Классификация бинарных квазиканонических систем счисления в мнимых квадратичных полях/П.С. Богданов, В.М. Чернов//Компьютерная оптика. -2013. -Т. 37, № 3. -С. 391-400.
- Thuswardner, J. Elementary properties of canonical number systems in quadratic fields/J. Thuswaldner. -In: Application of Fibonacci numbers/ed. by G.E. Bergum, A. N. Philippou, A.F. Horadam. -Dordrecht: Springer, 1998. -P. 405-414. - DOI: 10.1007/978-94-011-5020-0_45
- Богданов, П.С. О сходимости некоторых алгоритмов бинарной и тернарной машинной арифметики для вычислений в мнимых квадратичных полях/П.С. Богданов//Компьютерная оптика. -2015. -Т. 39, № 2. -С. 249-254. - DOI: 10.18287/0134-2452-2015-39-2-249-254
- Айерлэнд, К. Классическое введение в современную теорию чисел/К. Айерлэнд, М. Роузен; пер. с англ. -М.: Мир, 1987. -415 с.
- The on-line encyclopedia of Integer Sequences® (OEIS®) . -URL: https://oeis.org/(дата обращения 10.04.2018 г.).
- Грегори, Р. Безошибочные вычисления. Методы и приложения/Р. Грегори, Е. Кришнамурти; пер. с англ. -М.: Мир, 1988. -207 с. -ISBN: 5-03-001145-5.
