A decoding-processing apparatus that decodes bitstreams using an intermediate format. The apparatus includes a context-calculating unit (2) calculating the probability of symbols contained in incoming bitstreams, a parameter-generating unit (3) generating parameters for use in the context-calculating unit (2), and an arithmetic decoding-calculating unit (4) decoding the incoming bitstreams in accordance with the probability, thereby providing decoded data. The apparatus also includes a stream-converting unit (5) converting the decoded data into intermediate bitstreams, a storage unit (6) storing the intermediate bitstreams, a synchronization-detecting unit (7) detecting 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) permitting 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).