The present invention is able to determine an encoding parameter using a simple method with little processing load or memory cost, and enables encoding of image data with excellent compression performance. To this end, a prediction error generating unit of an encoding apparatus according to the present invention calculates the difference (prediction error) between a pixel of interest and a predicted value. A prediction order conversion unit converts the prediction error to a non-negative integer, and outputs the non-negative integer as a prediction order M(e). A Golomb encoding unit performs encoding in accordance with a k parameter supplied from a k parameter updating unit. The k parameter updating unit updates the k parameter for use in the next updating based on the prediction order M(e) of the pixel of interest and the k parameter supplied to the Golomb encoding unit.