In this paper we present the analytical results of the computational requirement for the minimum-distance decoding of convolutional codes. By deriving upper bounds for the number of decoding operations required to advance one code segment, we show that many less operations are required than in the case of sequential decoding This implies a significant reduction in the severity of the buffer-overflow problem. Then, we propose several modifications which could further reduce the computational effort required at long back-up distance. Finally we investigate the trade-off between coding-parameters selection and storage requirement as an aid to quantitative decoder design. Examples and future aspects are also presented and discussed.