An efficient algorithm for turbo code minimum distance computation is essential for estimating their performance in the error floor region without resorting to long simulations. Recently, Berrou et al. [1] introduced the innovative error impulse method, based on iterative decoding. In this paper, we present another iterative algorithm for turbo code distance computation. It is based on the decoding of an all-zero received sequence, performed on half of the code: the subset containing all the codewords with a 1 in a given coordinate i. By shifting i along the whole codeword length, the algorithm estimates the code minimum distance and its multiplicity with limited complexity O(k ² ), k being the interleaver length. Due to the sub-optimality of iterative decoding, the algorithm can produce false results. Investigation by comparison with the exact constrained subcode algorithm [2] shows the all-zero algorithm possesses an excellent reliability.