A watermark message embedded in a cover work can be made robust to various types of post-embedding operations, while simultaneously minimizing perceptual impact on the cover work. This is accomplished by the informed coding of the watermark message to be embedded. This is also accomplished by the informed embedding of the watermark message code in the cover work. Finally, the watermark message code may be perceptually shaped to minimize impact on the fidelity of the watermarked work. Further, these techniques may be combined for maximum effect.