(39-2) 14 * << * >> *Russian * English * Content * All Issues

Quasiparallel algorithm for error-free convolution computation using reduced Mersenne-Lucas codes
V.M. Chernov

 

Image Processing Systems Institute, Russian Academy of Sciences,
Samara State Aerospace University

 

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

Full text of article: Russian language.

 PDF

Abstract:
In this paper a new “error-free” algorithm for discrete circular convolution calculation is proposed. The algorithm is based on a new type of discrete orthogonal transforms for which there exist efficient multiplication-free implementations. The structure of these transforms is associated with the representation of data in the redundant number system associated with Lucas numbers.

Keywords:
discrete cyclic convolution, number-theoretical transforms Fibonacci and Lucas numbers, “error-free” calculations.

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.

References:

  1. Stein JY. Digital Signal Processing: A Computer Science Perspective. New York: John Wiley & Sons, Inc; 2002.
  2. Naudin C. Algorithmique Algébrique [In French]. Paris:  Masson; 1992.
  3. Nussbaumer HJ. Fast Fourier Transform and Convolution Algorithms. Berlin: Springer-Verlag; 1982.
  4. Schoenhage A, Strassen V. Schnelle multiplikation grosser Zahlen [In German]. Computing 1966; 7(3/4): 281-92.
  5. Blahut RE. Fast Algorithms for Digital Signal Processing. Reading:Addison-Wesley Inc; 1985.
  6. Rader CM. Discrete convolution via Mersenne transform. IEEE Trans Comp 1972; C-21: 1269-1273.
  7. Hoggatt VE. Fibonacci and Lucas Numbers. Fibonacci Association edition; 1972.
  8. Vajda S. Fibonacci&Lukas numbers and Golden Section. Theory and applications. 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 [In French]. Fibonacci Quarterly 1972; 10, 179-182
  10. Freitag HT, Phillips GM. Elements of Zeckendorf Arithmetic, Applications of Fibonacci Numbers 1998; 7; 129-132.
  11. Chernov V. Fast algorithm for "error-free" convolution computation using Mersenne-Lucas codes. Chaos, Solitons and Fractals 2006; 29;. 372-380.
  12. Chernov VM., Pershina MV. "Error-free" calculation of the convolution using generalized Mersenne and Fermat transforms over algebraic fields.1997. Lecture Notes in Computer Science. 1296, LNCS, pp. 621-628.
  13. Katai I, Kovacs B. Kanonische Zahlensysteme in der Theorie der Quadratischen Zahlen [In German]. Acta Scientiarum Mathematicarum (Szeged) 1980; 42; 99-107.
© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail:journal@computeroptics.ru; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20