A watermark embedder encodes auxiliary information, such as a binary message, into a host media signal by modulating message signals with two or more corresponding carrier signals to form a watermark signal and embeds this signal into the host. A compatible watermark decoder uses the carrier signals to demodulate the message signals from the watermarked signal.