(42-3) 18 * << * >> * Русский * English * Содержание * Все выпуски

Вычисление преобразований Фурье – Галуа в редуцированных бинарных системах счисления
Чернов В.М.

Институт систем обработки изображений РАН – филиал ФНИЦ «Кристаллография и фотоника» РАН, Самара, Россия,
Самарский национальный исследовательский университет имени академика С.П. Королева, Самара, Россия

 PDF, 331 kB

DOI: 10.18287/2412-6179-2018-42-3-495-500

Страницы: 495-500.

Аннотация:
В работе предлагается новый метод вычисления преобразований Фурье–Галуа (теоретико-числовых преобразований), являющихся модулярным аналогом дискретного преобразования Фурье. Ряд специфических проблем, связанных с вычислением преобразований в конечном поле, удаётся решить с помощью представления элементов этих полей в «экзотических» системах счисления, являющихся редукциями канонических систем счисления И. Катаи при отображении соответствующего кольца целых квадратичного поля в поле классов вычетов по простому модулю. Подробно исследуется случай бинарных редуцированных систем счисления. Доказывается, что такие системы счисления существуют для любого простого числа.

Ключевые слова:
преобразования Фурье–Галуа, конечные поля, канонические и редуцированные системы счисления.

Цитирование:
Чернов, В.М. Вычисление преобразований Фурье–Галуа в редуцированных бинарных системах счисления / В.М. Чернов // Компьютерная оптика. – 2018. – Т. 42, № 3. – С. 495-500. – DOI: 10.18287/2412-6179-2018-42-3-495-500.

Литература:

  1. Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток / Г. Нуссбаумер; пер. с англ. – М.: Радио и связь, 1985. – 248 с.
  2. Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов / Р. Блейхут; пер с англ. – М: Мир, 1989. – 448 с.
  3. 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.
  4. 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.
  5. Вариченко, Л.В. Абстрактные алгебраические системы и цифровая обработка сигналов / Л.В. Вариченко, В.Г. Лабунец, М.А. Раков. – Киев: Наукова думка, 1986. – 247 с.
  6. 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.
  7. 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.
  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.
  9. Чернов, В.М. Квазипараллельный алгоритм безошибочного вычисления свёртки в редуцированных кодах Мерсенна–Люка / В.М. Чернов // Компьютерная оптика. – 2015. – Т. 39, № 2. – С. 241-248. – DOI: 10.18287/0134-2452-2015-39-2-241-248.
  10. Чернов, В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований / В.М. Чернов. – М.: Физматлит, 2007. – 264 с. – ISBN: 5-9221-0940-6.
  11. Koblitz, N. Algebraic aspects of cryptography / N. Koblitz. - Berlin, Heidelberg: Springer-Verlag, 1998. - 206 p. - ISBN: 978-3-540-63446-1.
  12. Боревич, З.И. Теория чисел / З.И. Боревич, И.Р. Шафаревич. – 3-е изд. – М.: Наука, 1985. – 504 с.
  13. 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.
  14. Богданов, П.С. Классификация бинарных квазиканонических систем счисления в мнимых квадратичных полях / П.С. Богданов, В.М. Чернов // Компьютерная оптика. – 2013. – Т. 37, № 3. – С. 391-400.
  15. 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.
  16. Богданов, П.С. О сходимости некоторых алгоритмов бинарной и тернарной машинной арифметики для вычислений в мнимых квадратичных полях / П.С. Богданов // Компьютерная оптика. – 2015. – Т. 39, № 2. – С. 249-254. – DOI: 10.18287/0134-2452-2015-39-2-249-254.
  17. Айерлэнд, К. Классическое введение в современную теорию чисел / К. Айерлэнд, М. Роузен; пер. с англ. –М.: Мир, 1987. – 415 с.
  18. The on-line encyclopedia of Integer Sequences® (OEIS®) [Электронный ресурс]. – URL: https://oeis.org/ (дата обращения 10.04.2018 г.).
  19. Грегори, Р. Безошибочные вычисления. Методы и приложения / Р. Грегори, Е. Кришнамурти; пер. с англ. – М.: Мир, 1988. – 207 с. – ISBN: 5-03-001145-5.
    20. © 2009, IPSI RAS
    Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: journal@computeroptics.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20