To efficiently generate a re-encoding history data bit by convolution- encoding each data bit of a data clock to a branch word for transmission, fixing the required number of re-encoding history data bits based on the position of the decoded branch word and selecting the combination of the data bits for a previously decoded data bit sequence.

A most likely decoder 100 receives and decodes a matrix 102 interleaved with plural branch words. Each time of decoding one of the branch words, a composite data but is shifted into a sequence to generate a history data bit sequence as data 107. A re-encoding history data bit generator 101 selects the combination of data bits at a prescribed position within the history data bit sequence with respect to the position of a decoded data but finally shifted into the sequence, re-encodes the selected combination and outputs it as the re-encoding history data bit.