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.

Office Hours

Monday 10 -2

Tuesday 10-12

Thursday 11-1

My Timetable


Contacts


email: [email protected]

[email protected]

Phone: 2570

Welcome

Welcome To Faculty of Engineering

Almajmaah University


IEEE


http://www.ieee.org/

/

Links of Interest


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

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

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

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


Travel Web Sites

http://www.hotels.com/

http://www.orbitz.com/

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

http://www.kayak.com/

Blackboard

ستقام اختبارات الميدتيرم يوم الثلاثاء 26-6-1440

حسب الجدول المعلن بلوحات الاعلان

Summer training

The registration for summer training will start from 5th week of second semester

Academic advising

Class registration week 1

برنامج التجسير




إحصائية الموقع

عدد الصفحات: 2879

البحوث والمحاضرات: 1280

الزيارات: 62460