A method and apparatus are provided for calibrating a multi-stage A/D converter, such as a pipelined A/D converter. The method and apparatus are based on estimating the bounds of histograms of codes from various stages in the A/D converter. Known approaches were effective in calibrating A/D converters but during bound estimation suffered from lock-up conditions from which it could not recover. Embodiments of the present invention describe two mechanisms for recovering from lock-up conditions and a mechanism for fast locking. If neither a gross lock-up condition nor a fine lock-up condition is detected, the estimated bound is modified based on a comparison of a current digital residue with a fast lock value and a bound window. A discontinuity in the transfer characteristic of the A/D converter can then be removed based on the estimated bound.