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

Квазипараллельный алгоритм для безошибочного вычисления свёртки в редуцированных кодах Мерсенна–Люка
Чернов В.М.

Институт систем обработки изображений РАН,
Самарский государственный аэрокосмический университет имени академика С.П. Королёва
(национальный исследовательский университет) (СГАУ)

 

DOI: 10.18287/0134-2452-2015-39-2-241-248

  PDF

Аннотация:
В работе предложен новый «безошибочный» алгоритм вычисления дискретной циклической свёртки. Алгоритм основан на применении нового класса дискретных ортогональных преобразований, для которых существуют эффективные реализации без умножений. Структура этих преобразований связана с представлением данных в избыточной системе счисления с базисом, состоящим из чисел Люка.

Ключевые слова:
дискретная циклическая свёртка, теоретико-числовые преобразования, числа Фибоначчи и Люка, алгоритмы безошибочных вычислений.

Цитированиe:
Чернов, В.М. Квазипараллельный алгоритм безошибочного вычисления свёртки в редуцированных кодах Мерсенна–Люка / В.М. Чернов // Компьютерная оптика. – 2015. – Т. 39, № 2. – С. 241-248. - DOI: 10.18287/0134-2452-2015-39-2-241-248.

Citation: Chernov VM. Quasiparallel algorithm for error-free convolution computation using reduced Mersenne–Lucas codes. Computer Optics 2015; 39(2): 241-248. DOI: 10.18287/0134-2452-2015-39-2-241-248.

Литература:

  1. Stein, J.Y. Digital Signal Processing: A Computer Science Perspective / J.Y. Stein. - New York: John Wiley & Sons, Inc., 2002.
  2. Naudin, C. Algorithmique Algébrique / C. Naudin. – Paris: Masson; 1992. – (In French).
  3. Nussbaumer, H.J. Fast Fourier Transform and Convolution Algorithms / H.J. Nussbaumer. –  Berlin: Springer-Verlag, 1982. – (In French).
  4. Schoenhage, A. Schnelle multiplikation grosser Zahlen / A. Schoenhage, V. Strassen // Computing. – 1966. – Vol. 7(3/4). – P. 281-292. – (In German).
  5. Blahut, R.E. Fast Algorithms for Digital Signal Processing / R.E. Blahut. – Reading:Addison-Wesley Inc, 1985.
  6. Rader, C.M. Discrete convolution via Mersenne transform / C.M. Rader // IEEE Transactions on Computers. – 1972. – Vol. C-21. – P. 1269-1273.
  7. Hoggatt, V.E. Fibonacci and Lucas Numbers / V.E. Hoggatt. – Fibonacci Association Еdition, 1972.
  8. Vajda, S. Fibonacci&Lukas numbers and Golden Section. Theory and applications / S. Vajda. – Chichester: Elis Horwood Ltd, 1989.
  9. Zeckendorf, E. Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas  /  E. Zeckendorf // Fibonacci Quarterly – 1972. – V. 10. – P. 179-182. – (In French).
  10. Freitag, H.T. Phillips G.M, Elements of Zeckendorf Arithmetic / H.T. Freitag, G.M. Phillips //Applications of Fibonacci Numbers. – 1998. – V. 7. – P. 129-132.
  11. Chernov, V. Fast algorithm for "error-free" convolution computation using Mersenne-Lucas codes / V. Chernov  // Chaos, Solitons and Fractals. – 2006. –  V. 29. – P. 372-380.
  12. Chernov. V.M. "Error-free" calculation of the convolution using generalized Mersenne and Fermat transforms over algebraic fields / V.M. Chernov, M.V. Pershina // Lecture Note Computer Science. – 1997. – V. 1296. – P. 621-628.
  13.  Katai,  I. Kanonische Zahlensysteme in der Theorie der Quadratischen Zahlen / I. Katai, B. Kovacs // Acta Scientiarum Mathematicarum (Szeged).  – 1980. – V. 42. – P. 99-107. – (In German).
© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: journal@computeroptics.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20