An encoding apparatus that embeds a watermark in host data is provided. A multiplexer generates a plurality of bit sequences by adding initial data to the head of the watermark. A scrambler scrambles a plurality of the bit sequences respectively and generates a plurality of scrambled watermarks. An embedder embeds a plurality of the scrambled watermarks in the host data and generates a plurality of candidate watermarked host data. A signal-to-noise ratio calculator evaluates the robustness of the watermarks hidden in the respective candidate watermarked host data. A selector selects one candidate that has the highest level of the robustness as a final watermarked host data.