Fast S-Transform with O(NlogN) Complexity


Description of Technology

Researchers at the University of Calgary have developed a novel algorithm that solves the S-Transform with O(NlogN) computational complexity. This Fast S-Transform algorithm is fully invertible and requires only O(N) storage space, such that its performance is consistent with the Fast Fourier Transform and Discrete Wavelet Transform. The new transform can be performed in both the time domain and the frequency domain.

The S-Transform is a frequency transform that is used to analyze the temporal frequency content of non-stationary signals. By using a progressive frequency resolution similar to the Wavelet Transform, it improves on the performance of the Short-Time Fourier Transform. Unlike the Wavelet, however, the S-Transform maintains a clear relationship to the Fourier spectrum. The transform is ideal for applications studying frequency changes of a signal over time and space. It has been found to be valuable in medical imaging applications such as detecting anomalies in the heart, identifying abnormalities in brain tumours, analyzing ECGs, and transmitting images. Outside of medical imaging, it has been used to characterize liquid crystals, detecting disturbances in power networks, monitoring wind patterns, and detecting gravitational waves. Previous implementations of the S-Transform have a computational complexity of O(N2logN) and a storage complexity of O(N2), which is an unreasonable computational burden when transforming anything other than very small signals.

The Fast S-Transform (FST) has been made freely available open source under the GNU General Public License v3.0 (GPLv3). FST packages in C and Python can be downloaded from Sourceforge at

Non-free version of FST are available under terms different from those of the GPLv3. For more information, please contact

Areas of Application

The S-Transform can be used in most applications that currently use the Wavelet Transform, or used to extract more signal information in applications that currently use the Fourier Transform. Select application areas include:

  • Medical imaging
  • Image transmission/compression
  • Geophysics/Geosciences
  • Sound/Acoustic engineering
  • Astronomy/Astrophysics
  • Financial Engineering
  • Deep learning
IP Status
Competitive Advantages
  • Significantly decreased computation time and memory requirements
  • Data can be transformed "in place"
  • Can transform in less than a second data that previous methods would require over three days to complete
Stage Of Development
  • Algorithm developed and tested in C
  • Implemented in an embedded DSP system