Patent ID: 7620882

Claim:
A decoder that decodes a code by selecting, based on a predetermined condition, a path out of paths representing a transition of each of a plurality of states in a trellis diagram, the decoder comprising: a storing unit that stores a value of a first bit of bits representing a state of a source of the transition in the trellis diagram as information on a selection history of a path selected before time (k−(a constraint length of a code)+1) by adding the value to path selection history information on paths selected by time k−1 when a path at time k is selected; a path detecting unit that detects a path to be excluded from a path selection candidate, based on the information stored in the storing unit and information on a state of a transition source when a state transition occurs between time k−1 and time k; and a decoding unit that decodes a code by deleting the path detected by the path detecting unit.