11.3: Special Algorithms for input Data that is mostly Zero

In some cases, most of the data to be transformed are zero. It is clearly wasteful to do arithmetic on that zero data. Another special case is when only a few DFT values are needed. It is likewise wasteful to calculate outputs that are not needed. We use a process called “pruning" to remove the unneeded operations.

In other cases, the data are non-uniform sampling of a continuous time signal.

There are certain applications where approximations to the DFT are all that is needed.

Contributor

• ContribEEBurrus