The invention relates to a coding apparatus for embedding second data into first data without deterioration of the first data, and a decoding apparatus for decoding the coded data to the original first data and the second data without deterioration. The invention provides the coding apparatus which includes a memory for storing at least partial data of the first data and embeds the second data into the first data by performing rotation of the at least partial data stored in the memory in accordance with the second data; and provides the decoding apparatus in which at least partial data of the coded data embedded with the second data is rotated and a correlation with respect to peripheral data is calculated, so that the original first data and the second data are decoded in accordance with a rotation amount determined on the basis of the correlation.