A phase vocoder is a type of vocoder which can scale both the frequency and time domains of audio signals by using phase information. The computer algorithm allows frequency-domain modifications to a digital sound file (typically time expansion/compression and pitch shifting).
At the heart of the phase vocoder is the short-time Fourier transform (STFT), typically coded using fast Fourier transforms. The STFT converts a time domain representation of sound into a time-frequency representation (the "analysis" phase), allowing modifications to the amplitudes or phases of specific frequency components of the sound, before resynthesis of the frequency domain representation into the time domain by the inverse STFT. The time evolution of the resynthesized sound can be changed by means of modifying the time position of the STFT frames prior to the resynthesis operation allowing for time-scale modification of the original sound file.
Phase coherence problem 
The main problem that has to be solved for all case of manipulation of the STFT is the fact that individual signal components (sinusoids, impulses) will be spread over multiple frames and multiple STFT frequency locations (bins). This is because the STFT analysis is done using overlapping analysis windows. The windowing results in spectral leakage such that the information of individual sinusoidal components is spread over adjacent STFT bins. To avoid border effects of tapering of the analysis windows, STFT analysis windows overlap in time. This time overlap results in the fact that adjacent STFT analysis are strongly correlated (a sinusoid present in analysis frame at time "t" will be present in the subsequent frames as well). The problem of signal transformation with the phase vocoder is related to the problem that all modifications that are done in the STFT representation need to preserve the appropriate correlation between adjacent frequency bins (vertical coherence) and time frames (horizontal coherence). Except in the case of extremely simple synthetic sounds, these appropriate correlations can be preserved only approximately, and since the invention of the phase vocoder research has been mainly concerned with finding algorithms that would preserve the vertical and horizontal coherence of the STFT representation after the modification. For time scaling operations amplitude coherence is only a minor problem because shifting analysis frames in time has only a minor impact on the amplitude. The phase coherence problem was investigated for quite a while before appropriate solutions emerged.
The phase vocoder was introduced in 1966 by Flanagan as an algorithm that would preserve horizontal coherence between the phases of bins that represent sinusoidal components. This original phase vocoder did not take into account the vertical coherence between adjacent frequency bins, and therefore, time stretching with this system did produce sound signals that were missing clarity.
The optimal reconstruction of the sound signal from STFT after amplitude modifications has been proposed by Griffin and Lim in 1984. This algorithm does not consider the problem of producing a coherent STFT, but it does allow finding the sound signal that has an STFT that is as close as possible to the modified STFT even if the modified STFT is not coherent (does not represent any signal).
The problem of the vertical coherence remained a major issue for the quality of time scaling operations until 1999 when Laroche and Dolson proposed a rather simple means to preserve phase consistency across spectral bins. The proposition of Laroche and Dolson has to be seen as a turning point in phase vocoder history. It has been shown that by means of ensuring vertical phase consistency very high quality time scaling transformations can be obtained.
The algorithm proposed by Laroche did not allow preservation of horizontal phase coherence for sound onsets (note onsets). A solution for this problem has been proposed by Roebel.
An example of software implementation of phase vocoder based signal transformation using means similar to those described here to achieve high quality signal transformation is Ircam's SuperVP.
Use in music 
British composer Trevor Wishart used phase vocoder analyses and transformations of a human voice as the basis for his composition VOX 5 (part of his larger VOX Cycle). Transfigured Wind by American composer Roger Reynolds uses the phase vocoder to perform time-stretching of flute sounds.
See also 
- Flanagan J.L. and Golden, R. M.. ‘Phase vocoder’. Bell System Technical Journal, vol. 45, pp. 1493-1509, 1966.
- Griffin D. and Lim J., 'Signal Estimation from Modified Short-Time Fourier Transform', IEEE Transactions on Acoustics, Speech and Signal Processing, vol 32, no 2, pp. 236-243, 1984.
- J. Laroche and M. Dolson, 'Improved Phase Vocoder Time-Scale Modification of Audio', IEEE Transactions on Speech and Audio Processing, vol 7, no 3, pp. 323-332, 1999. 
- Roebel A., 'A new approach to transient processing in the phase vocoder', DAFx, 2003. pdf
- Wishart, T. ‘The Composition of Vox 5’. Computer Music Journal 12/4, 1988
- Serra, X. 'A System for Sound Analysis/Transformation/Synthesis based on Deterministic plus Stochastic Decomposition', p.12 (PhD Thesis 1989)
|The Wikibook MATLAB Programming has a page on the topic of: Phase vocoder and encoder|
- The Phase Vocoder: A Tutorial - A good description of the phase vocoder
- New Phase-Vocoder Techniques for Pitch-Shifting, Harmonizing and Other Exotic Effects
- A new Approach to Transient Processing in the Phase Vocoder
- Phase Vocoder - Phase vocoder description with figures and equations
- AwesomeBox - Open Source pitch corrector