## Dr. Ahmed G. Abo-Khalil

Electrical Engineering Department

## Circular discrete

When a function gN is periodic, with period N, then for functions, f, such that fgN exists, the convolution is also periodic and identical to:

$(f * g_N)[n] equiv sum_{m=0}^{N-1} left(sum_{k=-infty}^infty {f}[m+kN] ight) g_N[n-m].,$

The summation on k is called a periodic summation of the function f.

If gN is a periodic summation of another function, g, then fgN is known as a circular convolution of f and g.

When the non-zero durations of both f and g are limited to the interval [0, N − 1], fgN reduces to these common forms:

egin{align} (f * g_N)[n] &= sum_{m,=,0}^{N-1} f[m] g_N[n-m]\ &= sum_{m,=,0}^n f[m] g[n-m] + sum_{m,=,n+1}^{N-1} f[m] g[N+n-m]\ &= sum_{m,=,0}^{N-1} f[m] g[(n-m)_{mod{N}}] equiv (f *_N g)[n] end{align}

(Eq.1)

The notation $(f *_N g),$ for cyclic convolution denotes convolution over the cyclic group of integers modulo N.

Circular convolution is frequently used to characterized systems analyzed through the lens of the Discrete Fourier Transform.

### Fast convolution algorithms

In many situations, discrete convolutions can be converted to circular convolutions so that fast transforms with a convolution property can be used to implement the computation. For example, convolution of digit sequences is the kernel operation in multiplication of multi-digit numbers, which can therefore be efficiently implemented with transform techniques (Knuth 1997, §4.3.3.C; von zur Gathen & Gerhard 2003, §8.2).

Eq.1 requires N arithmetic operations per output value and N2 operations for N outputs. That can be significantly reduced with any of several fast algorithms. Digital signal processing and other applications typically use fast convolution algorithms to reduce the cost of the convolution to O(N log N) complexity.

The most common fast convolution algorithms use fast Fourier transform (FFT) algorithms via the circular convolution theorem. Specifically, the circular convolution of two finite-length sequences is found by taking an FFT of each sequence, multiplying pointwise, and then performing an inverse FFT. Convolutions of the type defined above are then efficiently implemented using that technique in conjunction with zero-extension and/or discarding portions of the output. Other fast convolution algorithms, such as the Schönhage–Strassen algorithm, use fast Fourier transforms in other rings.

Monday 10 -2

Tuesday 10-12

Thursday 11-1

### Contacts

email: [email protected]

[email protected]

Phone: 2570

### Welcome

Welcome To Faculty of Engineering

# Institute of Electrical and Electronics Engineers

http://www.ieee.org/

http://ieeexplore.ieee.org/Xplore/guesthome.jsp

http://ieee-ies.org/

http://www.ieee-pes.org/

http://www.pels.org/

http://www.utk.edu/research/

http://science.doe.gov/grants/index.asp

http://www1.eere.energy.gov/vehiclesandfuels/

http://www.eere.energy.gov/

### القران الكريم

http://quran.muslim-web.com/

### Travel Web Sites

http://www.hotels.com/

http://www.orbitz.com/

http://www.hotwire.com/us/index.jsp

http://www.kayak.com/