To improve the decoding accuracy and to accelerate decoding processing by decoding a data stream bit by bit each time of one-step trace back with a fixed state determined by the value of a tail bit as an origin state.

Before ACS operation reaches a number X of convolved data except for the tail bit, a viterbi decoder 37 decodes data bit by bit, while successively performing the trace back just for a path memory length with the maximum likelihood state which has the least value of path metric as an origin. Before the ACS operation reaches the final ACS operation, data are decoded bit by bit each time the trace back for the path memory length is finished, while successively performing the trace back just by the path memory length with the maximum likelihood state selected out of state candidates determined by the tail bit as the origin. When the ACS operation reaches the final ACS operation of a reception symbol D26, data are decoded bit by bit each time one-step trace back is performed with a specified state 00 as the origin.