A bit stream is decoded to generate first quantized DCT-coefficients. The first quantized DCT-coefficients are inversely quantized using a first quantization table, thereby generating DCT-coefficients. The resulting DCT-coefficients are quantized using a second quantization table, thereby generating second quantized DCT-coefficients. Elements in the second quantization table are smaller in value than those in the first quantization table. Predetermined additional information is embedded into the second quantized DCT-coefficients. The second quantized DCT-coefficients having the additional information embedded therein are encoded to produce a bit stream having the additional information embedded therein. The second quantization table is set to be smaller in value than the first quantization table.