Circular convolution and fourier discrete transformation.

ABSTRACT

We present the discrete circular convolution and its algorithms of calculus. Using discrete Fourier transform can be determined the circular deconvolution, ie the circular convolution inverse. We exemplify these concepts by solving an equation of circular convolution. This type of convolution product is applies to the periodic phenomena, discretely analyzed. By this paper we continue the series of articles about the types of discrete convolution products and their applications, some of which being cited in the References.

Keywords: Circular convolution, circular deconvolution, discrete Fourier transform, circular convolution equations.

1. DISCRETE CIRCULAR CONVOLUTION

Being given two finite sequences x = ([x.sub.0], [x.sub.1],..., [x.sub.N-1]) and y = ([y.sub.0], [y.sub.1],..., [y.sub.N-1]) of the same of the same length N, is called discrete circular convolution of period N the sequence z = x [cross product] y = ([z.sub.0], [z.sub.1],..., [z.sub.N-1]), where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

We make the convention [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The circular convolution can be considered also for sequences of different lengths, by right completion with 0, such that the two sequences to be of the same length.

2. ALGORITHMS FOR CALCULUS OF DISCRETE CIRCULAR CONVOLUTION

We give three types of circular convolution algorithms, which we will exemplify by the example (1,2,4,5,6)[cross product] (7,3,9,8) = (102,111,91,73,109).

Circular algorithm

The elements of the longer sequence sits outside on a circle in direct sense, i.e. contrary to clockwise motion and the elements of the shortest in the interior of the circle, in indirect sense, i.e. in the sense of clockwise. Its first elements must stand beside one another. Multiply the elements of the two sequences that stand beside one another and add the results. Then move one position the interior sequence in the sense of clockwise and do the same operations. It is finished when the first element of the interior sequence is beside the last element of the exterior sequence. The numbers resulted by this procedure are the elements of the circular convolution.

Bilinear algorithm

The longer sequence is placed from left to right twice. Below it is placed the second sequence from right to left, its first element being under the first element of the above second sequence. Multiply the elements of the two rows that stand beside one another and add the results. Then move one position to the right the bottom sequence and do the same operations. It is finished when the first element of the bottom sequence is beside the last element of the above second sequence. The numbers resulted by this procedure are the elements of the circular convolution.

Exemple.
```1  2  4  5  6  1  2  4  5  6   1  2  4   5  6  1  2  4  5  6
8  9  3  7                         8  9  3  7
32+45+18+7=102                    40+54+3+14=111
1  2  4  5  6  1  2  4  5  6     1  2  4  5  6  1  2  4  5  6
8  9  3  7                          8  9  3  7
48+9+6+28= 91                       8+18+12+35=73
1  2  4  5  6  1  2  4  5  6
8  9  3  7
16+36+15+42=109
```

Aliasing algorithm

This algorithm, the simplex, consists in performing linear complete convolution (see [1] or [6]) of the two sequences and adding to the part from resulting product with the same length as the longest sequence factor, the remaining part.
```1    2    4   5   6
7    3    9   8
------------------------------------
7    14   28  35  42
3    6   12  15   18
9   18  36   45  54
8   16   32  40  48
------------------------------------
7    17   43  73  109  95  94  48
95   94   48
---------------------
102  111  91  73  109
```

3. DISCRETE FOURIER TRANSFORM

The Fourier transform of the finite sequence x = ([x.sub.0], [x.sub.1],..., [x.sub.N-1]) is the sequence x = ([x.sub.0], [x.sub.1],..., [x.sub.N-1]) = F (x), with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (2)

where [[omega].sub.N] = [e.sub.2[pi]/N] is the N order complex root of the unity, i.e.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the complex conjugate.

Theorem 1. The inverse transform is given by the relation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

Proof. Using the formula for sum of a geometric progression, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

because, for j [not equal to] k, we have [[omega].sup.(k-j)N] = 1 and [[omega].sup.k-j] [not equal to] 1. It results the formula (3).

Remark. The direct and inverse discrete Fourier transforms are matrix written F(X) = [F.sub.N]X, respective [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Particularly, for N = 4, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4. THE DISCRETE FOURIER TRANSFORM OF THE CIRCULAR CONVOLUTION

Theorem 2. For two column matrices X = ([x.sub.0] [x.sub.1] ... [x.sub.N-1][).sup.T] and Y = ([y.sub.0] [y.sub.1] ... [y.sub.N-1][).sup.T], we have the formula of discrete Fourier transform of the circular convolution,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

the product of the column matrices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from the right hand of the above formula being performed on elements.

Proof. In conformity with above definitions and iterating the sums, an arbitrary component of the discrete Fourier transform of the circular convolution of the matrices X and Y is given by the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Making the changes of variables m = k - j in the first term and m = k - j + N in the second term from the last formula, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

5. CIRCULAR CONVOLUTION EQUATIONS.

Using the discrete Fourier transform method, we solve as example a circular convolution equation:

Example. Solve the circular convolution equation of period four,

A [cross product] X = B,

where A = (1 9 9 1[).sup.T] and B = (12 + [lambda] 12 - [lambda] 8 + [lambda] 8 -[lambda][).sup.T]. To make discussion after the real parameter [lambda] and checking of obtained solution.

Solution. We denote B = [B.sub.1] + [lambda][B.sub.2], where [B.sub.1] =(12 12 8 8[).sup.T], [B.sub.2] = (1 - 11-1[).sup.T], X = ([x.sub.0] [x.sub.1] [x.sub.2] [x.sub.3][).sup.T] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Apllying the discrete Fourier transform on the equation, this take the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

therefore the equation becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Equaling the components of the column matrices by above equation, it results the system of equations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

from which it is obtained the solutions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and the compatibility condition [lambda] = 0. The unknown [x.sub.2] = p can not be determined, leaving a real parameter. For [lambda] [not equal to] 0 the convolution equation have no solution. For [lambda] = 0 , the equation has an infinity of solutions, given by the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Verification

We verify the above result by circular convolution, computed by aliasing method.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Remark. The above example is the particular case for m = 8, n = 10 of the same equation with the dates

A = (1 m +1 m +1 1[).sup.T] and B = (n + 2 + [lambda] n + 2 - [lambda] n - 2 + [lambda] n - 2 -[lambda][).sup.T].

The author uses such exercises with parameters for student works, especially to masters. Every student has a particular pair of parameters m and n, for example they can be the row and column on which found the place of the student in the seminar room. Thus, every student has quantitatively his individual problem to solve, but all these problems are qualitatively the same.

6. REFERENCES

[1] M. I. Cirnu, Algebraic equations. New solutions for old problems, Lambert Academic Publishing, Germany, 2013.

[2] M. I. Cirnu, Calculation of convolution products of picewise defined functions and some applications, Journal of Information Systems and Operations Management, 6(2012) no. 1, 41-52.

[3] M. I. Cirnu, A certain integral-recurrence equation with discrete-continuous auto-convolution, Archivum Mathematicum (Brno), 47 (2011), 267-272.

[4] M. I. Cirnu, Determinantal formulas for sum of generalized arithmetic-geometric series, Boletin de la Asociacion Matematica Venezolana, 43 (2011) no. 1, 25-38

[5] M. I. Cirnu, Initial-value problems for first-order differential recurrence equations with auto-convolution, Electronic Journal of Differential Equations, 2011 (2011) no. 2, 1-13.

[6] M. I. Cirnu, Linear discrete convolution and its inverse, Journal of Information Systems and Operations Management, Part I. Convolution, 4 (2010) no. 1, 129-137, Part II. Deconvolution, 4 (2010) no. 2, 123-137.

[7] M. I. Cirnu, First order differential recurrence equations with discrete auto-convolution, International Journal of Mathematics and Computation, 4, 2009, 124-128.

[8] A. V. Oppeinheim, R. W. Schafer, J. R. Buck, Discrete-time signal processing, Prentice Hall, 1999.

Mircea Ion Cirnu (1)

(1) Faculty of Applied Sciences, Polytechnic University of Bucharest, cirnumircea@yahoo.com
COPYRIGHT 2013 Romanian-American University
No portion of this article can be reproduced without the express written permission from the copyright holder.