# Fast Hartley transformation libraryFHT.h

The Hartley transform is an integral transform closely related to the Fourier transform, but which transforms real-valued functions to real-valued functions. It was proposed as an alternative to the Fourier transform, and is one of many known Fourier-related transforms. Compared to the Fourier transform, the Hartley transform has the advantages of transforming real functions to real functions (as opposed to requiring complex numbers) and of being its own inverse. Fast Hartley transformation can do the same operations as Fourier transformation. It is useful for spectrum analysis and filtering signals in DSP. Fast Hartley transformation can be two times faster than fast Fourier transformation for real numbers data.

## Contents

- Sine and cosine table
- Hartley transformation
- Time domain to frequency domain
- Frequency domain to time domain
- Spectrum
- Energy spectrum
- Magnitude spectrum
- Real spectrum
- Signal manipulations
- Signal reflection
- Signal derivative
- Signal antiderivative
- Signal time and frequency shift
- Magnitude scaling
- Autocorrelation of signal
- Cross-correlation of signals
- Convolution of signals
- Mixing signals

## Function list

C function name | Functions | C++ function name | Functions |
---|---|---|---|

AntiDerivative | 2 functions | AntiDerivative | 2 functions |

AutoCorrelation | 2 functions | AutoCorrelation | 2 functions |

Convolution | 2 functions | Convolution | 2 functions |

CrossCorrelation | 2 functions | CrossCorrelation | 2 functions |

Derivative | 2 functions | Derivative | 2 functions |

EnergySpectrum | 2 functions | EnergySpectrum | 2 functions |

Impulse | 2 functions | Impulse | 2 functions |

MagnitudeSpectrum | 2 functions | MagnitudeSpectrum | 2 functions |

Mix | 2 functions | Mix | 2 functions |

RealSpectrum | 2 functions | RealSpectrum | 2 functions |

Reflect | 2 functions | Reflect | 2 functions |

Scale | 2 functions | Scale | 2 functions |

Shift | 2 functions | Shift | 2 functions |

SinCosTable | 2 functions | SinCosTable | 2 functions |

Spectrum | 2 functions | Spectrum | 2 functions |

C function name | Functions | C++ function name | Functions |

# Sine and cosine table

Cvoid FHT_SinCosTable_flt32 (flt32_t table[], uint8_t exp); void FHT_SinCosTable_flt64 (flt64_t table[], uint8_t exp);

C++void FHT::SinCosTable (flt32_t table[], uint8_t exp); void FHT::SinCosTable (flt64_t table[], uint8_t exp);

Description: Precompute sine and cosine table for fast Hartley transformation

Parameters:

- table - pointer to sine and cosine table (should be able to hold at least 2
^{exp-1}elements) - exp - power of two, which represent count of elements in data array (is computed as 2
^{exp})

Return value: None.

# Hartley transformation

Hartley transformation converts signal representation from time domain to frequency domain and from frequency domain to time domain. Both functions are inverses of each other. If you sequentially call Spectrum then Impulse functions you will get original data.

## Time domain to frequency domain

Cvoid FHT_Spectrum_flt32 (flt32_t array[], const flt32_t table[], uint8_t exp); void FHT_Spectrum_flt64 (flt64_t array[], const flt64_t table[], uint8_t exp);

C++void FHT::Spectrum (flt32_t array[], const flt32_t table[], uint8_t exp); void FHT::Spectrum (flt64_t array[], const flt64_t table[], uint8_t exp);

Description: Do fast Hartley transformation of data from time domain to frequency domain and store result into the same place. The result array can be then processed by RealSpectrum functions to get actual magnitude and phase values of spectrum.

Parameters:

- array - pointer to data array for Hartley transformation
- table - pointer to sine and cosine table is computed by SinCosTable function
- exp - power of two, which represent count of elements in data array (is computed as 2
^{exp})

Return value: None.

## Frequency domain to time domain

Cvoid FHT_Impulse_flt32 (flt32_t array[], const flt32_t table[], uint8_t exp); void FHT_Impulse_flt64 (flt64_t array[], const flt64_t table[], uint8_t exp);

C++void FHT::Impulse (flt32_t array[], const flt32_t table[], uint8_t exp); void FHT::Impulse (flt64_t array[], const flt64_t table[], uint8_t exp);

Description: Do fast Hartley transformation of data from frequency domain to time domain and store result into the same place. To restore known signal by its magnitude and phase spectrum you have to call HartleySpectrum functions before doing frequency domain to time domain transformation. That functions transform real spectrum into Harley spectrum, which can be then transform into time domain by these functions.

Parameters:

- array - pointer to data array for Hartley transformation
- table - pointer to sine and cosine table is computed by SinCosTable function
- exp - power of two, which represent count of elements in data array (is computed as 2
^{exp})

Return value: None.

# Spectrum

These functions convert Hartley spectrum to real spectrum and real spectrum to Hartley spectrum. Real spectrum represents the signal by set of magnitudes and phases, and can be converted to Hartley spectrum for inverse Hartley transformation (from frequency domain to time domain).

## Energy spectrum

Cvoid FHT_EnergySpectrum_flt32 (flt32_t energy[], const flt32_t spectrum[], uint8_t exp); void FHT_EnergySpectrum_flt64 (flt64_t energy[], const flt64_t spectrum[], uint8_t exp);

C++void FHT::EnergySpectrum (flt32_t energy[], const flt32_t spectrum[], uint8_t exp); void FHT::EnergySpectrum (flt64_t energy[], const flt64_t spectrum[], uint8_t exp);

Description: Convert Hartley spectrum to energy spectrum, which represents original signal by set of squared magnitudes of different frequencies.

Parameters:

- energy - pointer to energy array (should be able to hold at least 2
^{exp-1}+1 elements) - spectrum - pointer to Hartley spectrum array is computed by Spectrum function
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

## Magnitude spectrum

Cvoid FHT_MagnitudeSpectrum_flt32 (flt32_t magnitude[], const flt32_t spectrum[], uint8_t exp); void FHT_MagnitudeSpectrum_flt64 (flt64_t magnitude[], const flt64_t spectrum[], uint8_t exp);

C++void FHT::MagnitudeSpectrum (flt32_t magnitude[], const flt32_t spectrum[], uint8_t exp); void FHT::MagnitudeSpectrum (flt64_t magnitude[], const flt64_t spectrum[], uint8_t exp);

Description: Convert Hartley spectrum to magnitude spectrum, which represents original signal by set of magnitudes of different frequencies.

Parameters:

- magnitude - pointer to magnitude array (should be able to hold at least 2
^{exp-1}+1 elements) - spectrum - pointer to Hartley spectrum array is computed by Spectrum function
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

## Real spectrum

Cvoid FHT_RealSpectrum_flt32 (flt32_t magnitude[], flt32_t phase[], const flt32_t spectrum[], uint8_t exp); void FHT_RealSpectrum_flt64 (flt64_t magnitude[], flt64_t phase[], const flt64_t spectrum[], uint8_t exp);

C++void FHT::RealSpectrum (flt32_t magnitude[], flt32_t phase[], const flt32_t spectrum[], uint8_t exp); void FHT::RealSpectrum (flt64_t magnitude[], flt64_t phase[], const flt64_t spectrum[], uint8_t exp);

Description: Convert Hartley spectrum to real spectrum which represents original signal by set of magnitudes and phases. Square of magnitude spectrum of the signal can be treated as energy spectrum of original signal.

Parameters:

- magnitude - pointer to magnitude array (should be able to hold at least 2
^{exp-1}+1 elements) - phase - pointer to phase array (should be able to hold at least 2
^{exp-1}+1 elements) - spectrum - pointer to Hartley spectrum array is computed by Spectrum function
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

# Signal manipulations

Signal manipulation functions do signal transformation in either time or frequency domain (Hartley spectrum), and change original signal in linear manner to mirror, scale or mix two or more signals, find derivative and antiderivative of signals. They provide a fastest way to compute signal autocorrelation and cross-correlation functions, or may find FIR filter response with complexity no more than O(n*log(n)) floating-point operations, instead of O(n*m) complexity that traditional convolution algorithm can provide.

## Signal reflection

Cvoid FHT_Reflect_flt32 (flt32_t array[], uint8_t exp); void FHT_Reflect_flt64 (flt64_t array[], uint8_t exp);

C++void FHT::Reflect (flt32_t array[], uint8_t exp); void FHT::Reflect (flt64_t array[], uint8_t exp);

Description: Mirror original signal around zero frequency (in frequency domain) or around zero point (in time domain).

Parameters:

- array - pointer to array that holds data of signal in time domain or in frequency domain is computed by Hartley Spectrum function
- exp - power of two, which represent count of elements in array (is computed as 2
^{exp})

Return value: None.

## Signal derivative

Cvoid FHT_Derivative_flt32 (flt32_t array[], uint8_t exp); void FHT_Derivative_flt64 (flt64_t array[], uint8_t exp);

C++void FHT::Derivative (flt32_t array[], uint8_t exp); void FHT::Derivative (flt64_t array[], uint8_t exp);

Description: Do transformation in frequency domain to compute signal derivative. Can be applied to filter impulse response coefficients to make differential filter from Low-pass or Band-pass filters.

Parameters:

- array - pointer to Hartley spectrum array is computed by Spectrum function
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

## Signal antiderivative

Cvoid FHT_AntiDerivative_flt32 (flt32_t array[], flt32_t shift, uint8_t exp); void FHT_AntiDerivative_flt64 (flt64_t array[], flt64_t shift, uint8_t exp);

C++void FHT::AntiDerivative (flt32_t array[], flt32_t shift, uint8_t exp); void FHT::AntiDerivative (flt64_t array[], flt64_t shift, uint8_t exp);

Description: Do transformation in frequency domain to compute signal antiderivative.

Parameters:

- array - pointer to Hartley spectrum array is computed by Spectrum function
- shift - shift value for zero frequency to restore average signal value
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

## Signal time and frequency shift

Cvoid FHT_Shift_flt32 (flt32_t array[], flt32_t shift, uint8_t exp); void FHT_Shift_flt64 (flt64_t array[], flt64_t shift, uint8_t exp);

C++void FHT::Shift (flt32_t array[], flt32_t shift, uint8_t exp); void FHT::Shift (flt64_t array[], flt64_t shift, uint8_t exp);

Description: Shift signal in time or frequency domain by "shift" positions in right direction (if shift is positive) or in left direction (if shift is negative). If applied in frequency domain, then shift signal in time domain. If applied in time domain, then shift signal in frequency domain.

Parameters:

- array - pointer to array that holds data of signal in time domain or in frequency domain is computed by Hartley Spectrum function
- shift - shift value. If positive then shift in right direction. If negative, then shift in left direction
- exp - power of two, which represent count of elements in array (is computed as 2
^{exp})

Return value: None.

## Magnitude scaling

Cvoid FHT_Scale_flt32 (flt32_t array[], flt32_t scale, uint8_t exp); void FHT_Scale_flt64 (flt64_t array[], flt64_t scale, uint8_t exp);

C++void FHT::Scale (flt32_t array[], flt32_t scale, uint8_t exp); void FHT::Scale (flt64_t array[], flt64_t scale, uint8_t exp);

Description: Scale signal magnitude using "scale" value.

Parameters:

- array - pointer to array that holds data of signal in time domain or in frequency domain is computed by Hartley Spectrum function
- scale - scale value is used to multiply signal by
- exp - power of two, which represent count of elements in array (is computed as 2
^{exp})

Return value: None.

## Autocorrelation of signal

Cvoid FHT_AutoCorrelation_flt32 (flt32_t array[], flt32_t scale, uint8_t exp); void FHT_AutoCorrelation_flt64 (flt64_t array[], flt64_t scale, uint8_t exp);

C++void FHT::AutoCorrelation (flt32_t array[], flt32_t scale, uint8_t exp); void FHT::AutoCorrelation (flt64_t array[], flt64_t scale, uint8_t exp);

Description: Do transformation in frequency domain to compute autocorrelation function of signal.

Parameters:

- array - pointer to Hartley spectrum array is computed by Spectrum function
- scale - signal absolute value (norm or magnitude) to scale autocorrelation values to make zero point in time domain to be equal to 1.0
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

## Cross-correlation of signals

Cvoid FHT_CrossCorrelation_flt32 (flt32_t target[], const flt32_t source[], flt32_t scale, uint8_t exp); void FHT_CrossCorrelation_flt64 (flt64_t target[], const flt64_t source[], flt64_t scale, uint8_t exp);

C++void FHT::CrossCorrelation (flt32_t target[], const flt32_t source[], flt32_t scale, uint8_t exp); void FHT::CrossCorrelation (flt64_t target[], const flt64_t source[], flt64_t scale, uint8_t exp);

Description: Do transformation in frequency domain to compute cross-correlation function of two signals.

Parameters:

- target - pointer to Hartley spectrum array is computed by Spectrum function for first signal
- source - pointer to Hartley spectrum array is computed by Spectrum function for second signal
- scale - square root of multiplied absolute values (norms or magnitudes) of both signals to scale cross-correlation values
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

## Convolution of signals

Cvoid FHT_Convolution_flt32 (flt32_t target[], const flt32_t source[], flt32_t scale, uint8_t exp); void FHT_Convolution_flt64 (flt64_t target[], const flt64_t source[], flt64_t scale, uint8_t exp);

C++void FHT::Convolution (flt32_t target[], const flt32_t source[], flt32_t scale, uint8_t exp); void FHT::Convolution (flt64_t target[], const flt64_t source[], flt64_t scale, uint8_t exp);

Description: Do transformation in frequency domain to compute convolution of two signals. If the first signal is time series to be filtered and the second signal is FIR filter coefficients, then convolution result (in time domain) is filtered signal.

Parameters:

- target - pointer to Hartley spectrum array is computed by Spectrum function for first signal
- source - pointer to Hartley spectrum array is computed by Spectrum function for second signal
- scale - scale coefficient to scale convolution values. Set it to 1.0 if you do not need to scale filter response
- exp - power of two, which represent count of elements in spectrum array (is computed as 2
^{exp})

Return value: None.

## Mixing signals

Cvoid FHT_Mix_flt32 (flt32_t target[], const flt32_t source[], flt32_t tscale, flt32_t sscale, uint8_t exp); void FHT_Mix_flt64 (flt64_t target[], const flt64_t source[], flt64_t tscale, flt64_t sscale, uint8_t exp);

C++void FHT::Mix (flt32_t target[], const flt32_t source[], flt32_t tscale, flt32_t sscale, uint8_t exp); void FHT::Mix (flt64_t target[], const flt64_t source[], flt64_t tscale, flt64_t sscale, uint8_t exp);

Description: Add two signals with appropriate coefficients and store result signal into the same place (target array).

Parameters:

- target - pointer to array that holds data of first signal in time domain or in frequency domain is computed by Hartley Spectrum function
- source - pointer to array that holds data of second signal in time domain or in frequency domain is computed by Hartley Spectrum function
- tscale - scale value is used to multiply first signal by
- sscale - scale value is used to multiply second signal by
- exp - power of two, which represent count of elements in arrays (is computed as 2
^{exp})

Return value: None.