The present invention relates generally to digital watermarking and steganographic embedding and decoding. One claim recites a method of decoding auxiliary data that has been embedded in an audio signal through modifications to the audio signal that are substantially imperceptible. The auxiliary data comprises bits of digital data and the bits being carried in a plurality of embedded code signals embedded in the audio signal, each of the plurality of embedded code signals corresponding to one or more bits in the auxiliary data. The method includes: extracting auxiliary data from a series of blocks of the audio signal, the blocks conveying the same auxiliary data, yet the blocks representing the auxiliary data differently as the embedded code signals conveying the same auxiliary data change over the blocks, and wherein extracting includes evaluating features of the blocks, the features being modulated to carry the auxiliary data; and using the auxiliary data from the series of blocks to increase statistical confidence of accurate recovery of the auxiliary data, the auxiliary data being separately decoded from the blocks and combined to increase the statistical confidence of recovery of the auxiliary data. Of course, other claims and combinations are provided as well.