Category Archives: technical

A roman inspiration for the Discrete Fourier Transform

CAesAR

Divide et impera (in english, divide and rule): that was one of the main foundations of the political, military and economic strategy of the expansionist Roman Empire. The roman ambition was too big to be achieved without division. They realized that the sum of necessary efforts to perform each part of a divided task may be less than one needed to perform the same task without dividing it.

Playing with algebraic notation without any mathematical or conceptual formalism: if a task that demands an effort T to be performed could be divided in n subtasks, each one with its respective T_i performing efforts, it is intuitive to consider that T_1+T_2+...+T_n=T. Instead, the roman experience establishes the opposite: T_1+T_2+...+T_n<T!

In mathematics and computer science, this “roman insight” is called Divide and Conquer Algorithm: a logical maneuver that breaks a big problem in many little others to (among other benefits) reduce its overall computational complexity. There are many applications of it, but my preferred is the Cooley-Tukey algorithm to process a DFT (Discrete Fourier Transform), most known as the Fast Fourier Transform. A really simple subtlety (breaking the problem into subproblems recursively) makes the problem much easier.

A classical result is to compute the DFT of a sequence with N=2^n elements, N^2 complex multiplications are needed by the original DFT algorithm. If we the Cooley-Tukey algorithm instead, only N \log_2 N multiplications have to be done. Don’t you see big difference? Imagine that you have to process a tiny signal with 1024 samples:

  • Original DFT algorithm: 2^{20} complex multiplications
  • Cooley-Tukey algorithm: 10 \cdot 2^{10}

In this example the FFT, also called as 2-radix FFT (because the sequence is broken recursively in 2 others) is 102.4 faster than the original. If N increases, the difference will be much more than this. What would be the Digital Signal Processing without such subtleties? So, let us divide to conquer.

Ave Cooley and ave Tukey!

New Simulink Blog on MATLAB Central

Just a few months ago, I posted about the blogs on MATLAB Central. There were 4 blogs about MATLAB: Doug’s Pick of the Week, Inside the MATLAB Desktop, Loren on the Art of MATLAB and Steve on Image Processing.

All those blogs are quite good, but it was too much attention for MATLAB itselft and nothing specific for Simulink. This injustice no longer exists. there’s a brand new exclusive Simulink Blog: Seth on Simulink (http://blogs.mathworks.com/seth/). I recommend it for all who uses this powerful but not worthly explored simulation tool (I think most people strangely prefers coding rather than connecting blocks!).

Yahoo! Pipes and Widsets Widget for MATLAB Central Blogs were updated. Check it out:

Yahoo! Pipes

Add to my Widsets

Scientific American Math Feeds Widget

For those who appreciate to read math articles, and specially for who reads Scientific American Math Section, that’s a way to get in touch everywhere using your mobile phone: a brand new WidSets widget I created:

Sciam Math Widget

To add it to you dashboard, click the button bellow:

Add to my Widsets

If WidSets sounds unfamiliar to you, spend a few minutes reading an introductory post that I wrote about it.

Mashing up the MATLAB Central Blogs

Although there are many sites, blogs and other resources about MATLAB on the web, one is worth be the frequently accessed by users: MATLAB Central, an official exchange area for users community. Inside, there are 4 blogs I like:

  • Loren on the Art of MATLAB: Loren Shure works on design of the MATLAB language at The MathWorks. She writes here about once a week on MATLAB programming and related topics.
  • Doug’s Pick of the Week: Doug is an Application Engineer at The MathWorks. A MATLAB user since 1994, he gets paid to live, eat, and breathe MATLAB! Each week, he highlights a submission from the File Exchange that he finds useful or interesting.
  • Steve on Image Processing: Steve Eddins manages the Image & Geospatial development team at The MathWorks and coauthored Digital Image Processing Using MATLAB. He writes here about image processing concepts, algorithm implementations, and MATLAB.
  • Inside the MATLAB Desktop: The MATLAB Desktop team, comprised of eight developers, builds the main user interface for MATLAB, including the Command Window, the Editor, and the Current Directory browser.

Using pipes again, I decided to join the four feeds (what also includes some podcasts) into one:

MATLAB Blogs Pipe
http://pipes.yahoo.com/dilsonlira/matlab_central_blogs

If you use Netvibes, add it to your page:

Add to netvibes

To get this feed into your mobile phone, I also created a WidSets widget:

Add to my Widsets

Mobilizing the feeds with WidSets

I’ve been following the developments of Nokia Beta Labs very closely. I do that not only as a customer, but as an enthusiast of mobile computing and mobile communications. There are many interesting applications I’ve tested on my phone, some of them I continue using and some I don’t think they are so useful. So far, my preferred is WidSets: a Java application that aggregates feeds, simple games, web search tools and other widgets in a custom dashboard that can be managed on a PC. It’s a kind of Netvibes on a mobile phone.

Dashboard

 Widgets, aggregators, social bookmarking and all these web 2.0 stuff make our lives much easier when we are using a PC. Certainly, they are much more valuable on a device full of limitations: a keyboard is hard to type, limited memory and (in many cases) charged usage. It’s such a calvary to open up a mobile browser, type a url and, only for that point on, start surfing on the web. At least for me, 70% of internet time is spent accessing the same few sources, most of them could be (and really are) bookmarked and the updates read by rss feeds, not the website itself. So, in a mobile phone, much more than any other device, the content should be easily accessible. Considering this, WidSets fits very well.

It’s interesting to know that it’s not only compatible with Nokia phones, it’s free and there are thousands of available widgets and if you want, create your own. Supported by a growing developer community and a well documented API, you can download the SDK and start coding. But, if you are not a geek or simply don’t have time for that (including myself), it’s really easy to create a new feed widget with just a few clicks. After that, you can keep it private or publish to other users also enjoy.

I have already published some feed widgets (most in portuguese language) in my WidSets page, including this blog’s feeds. So, if you like to read my feeds on your mobile phone, become a WidSets user put Manoel Lira’s Blog widget on your dashboard.

IEEE Communications Digest Mashup

I believe that some facilities brought by so called Web 2.0 should not be ignored. Who usually reads news in different sources has reasons enough to become a mashup user. My favorite mashup tool is still a beta release but works fine so far: Yahoo! Pipes – there I can mix different feed sources into one or exactly the opposite: split one source into many other subfeeds. More sophisticated ideas (like geocode a feed into a map, filter and even translate the feeds) can also be implemented. Everything is done graphically, in a very intuitive way, connecting blocks and pipes – that’s why the name.

Certainly this short description of Pipes can be useful, but it’s not the main idea of this post: one of the first pipes I’ve created is a IEEE Communications Digest (for those who are not familiarized with, IEEE means Institute of Electrical and Electronics Engineers and is the biggest technical professional organization in the world). This mashup is a short compilation of some IEEE publications feeds in Communications area. It aggregates:

If you are interested, check it out: http://pipes.yahoo.com/dilsonlira/ieee_communications_digest. To have access to the texts pointed by the feeds, an IEEE member login is required. Otherwise, only the feed titles can be read.

A Nyquist–Shannon Sampling Theorem misunderstanding

The Nyquist-Shannon Sampling Theorem estabilishes that a sampling process of a continuous-time x(t) signal is perfectally reversible if the sampling frequency is at least the Nyquist rate (the double of the sampled signal bandwidth). However, I’ve been realizing some really experienced engineers have a lightly distorced interpretation of the theorem: to believe that the quality of a reconstructed signal increases with the sampling frequency and the frequencies much higher than Nyquist rate are needed to perform a satisfatory reconstruction.

A strongly possible reason to this erroneous understanding is the thought that the signal reconstruction is made by a linear interpolation of the samples. From that perspective, a higher rate sampling really makes the reconstructed signal closer to its original shape. But, the point is that the signal is not simply reconstructed by an interpolation. Instead, the process is compose by two stages:

  • A train of impulses is generated, which one multiplicated by it respective sample value;

x_i(t)=\sum\limits_{n=-\infty}^{\infty}x[n]\delta(t-nT)

  • Then, the resulting signal passes into a low-pass filter to discard all frequencies above the original signal bandwidth.

It is important to know that in practical terms, the reconstruction is not perfect because the theorem is only valid for bandlimited signals – requiring the signal to be prefiltered what makes a distortion on it and the low-pass filter is unrealizable because it’s response is not causal. So, although the mathematical behavior of the theorem is not achived phisically, the constraint is not the sampling rate, since the Nyquist rate be respected.