A decoding-processing apparatus (1) comprising: a context-calculating unit (2) operable to calculate the probability of symbols contained in incoming bitstreams; a parameter-generating unit (3) operable to generate parameters for use in the context-calculating unit (2); an arithmetic decoding-calculating unit (4) operable to decode the incoming bitstreams in accordance with the probability, thereby providing decoded data; a stream-converting unit (5) operable to convert the decoded data into intermediate bitstreams; a storage unit (6) operable to store the intermediate bitstreams; a synchronization-detecting unit (7) operable to detect calculation start timing from the intermediate bitstreams fed out of the storage unit (6), thereby providing detected calculation start timing; and a multivalued calculating unit (8) operable to permit the intermediate bitstreams fed out of the storage unit (6) to be multivalued in synchronism with the detected calculation start timing from the synchronization-detecting unit (7).