A data processing apparatus able to start decoding at a timing earlier than the conventional timing and able to reduce the storage capacity required for a storing means for storing the encoded data until a decoding side decodes the input encoded data in comparison with the conventional storage capacity, which apparatus selects frame data from frame data f(5) having the last decoding order to frame data f(0) having the first decoding order for processing for calculating a delay time min_delay and calculates the delay time min_delay. It calculates the delay time min_delay indicating the delay time from when the decoding side starts to receive input of the frame data to when the data is decoded based on the specified size and the bit rate of the input of the frame data to the decoding side for each of the frame data for processing.