A coded data recoding apparatus includes a coded data analyzing unit 1 for extracting block data and data showing the image characteristics of the block data from moving image coded data, two or more code tables 4 and 5 in each of which the code amount is optimized for each of the above-mentioned image characteristics, a code table selecting unit 2 for selecting a code table which is used for recoding on the basis of the data showing the image characteristics extracted by the coded data analyzing unit 1, and a variable length recoding unit 3 for outputting a bit stream of coded data in which the block data are recoded thereby using the code table selected by code table selecting unit 2 selected.