backlinks: /SRSoftwareOverview/FusionRegistration

Given a signal

the Z-transform (for a finite number of points) is defined as

The chirp z-transform computes the z-transform on a contour of the form

where A and W are arbitrary complex numbers. This path describes a spiral, starting at an arbitrary point A and curving in or outwards depending on the value of W. The transform becomes

Making the substitution suggested by Bluestein,

the transform expands to

The transform can now be broken into three parts:

- Construct a signal .
- Circularly convolve the signal with .
- Weigh the result by .

Bluestein's substitution therefore allows us to write the chirp z-transform in terms of a convolution, which, in turn, can be calculated using the fast Fourier transform.

The fast Fourier transform is especially quick for sequences of square lengths. Given that we'd like to calculate M points, and that our input sentence is of length N, we pad our signals to a length

Since multiplication in the Fourier domain leads to circular convolution in the discrete-time domain, the signals need to be padded to a length of at least .

- Construct of length N and pad to L.
- Construct of length L.
- Obtain the FFTs of the above signals and multiply (not quite, more on that later).
- Select elements N to N+M.
- Weigh by .

rainbow