A method for a machine or group of machines to watermark an audio signal includes receiving an audio signal and a watermark signal including multiple symbols, and inserting at least some of the multiple symbols in multiple spectral channels of the audio signal, each spectral channel corresponding to a different frequency range. Optimization of the design incorporates minimizing the human auditory system perceiving the watermark channels by taking into account perceptual time-frequency masking, pattern detection of watermarking messages, the statistics of worst case program content such as speech, and speech-like programs.