Methods and apparatus for characterizing media are described. An example method includes converting at least a portion of a block of audio into a frequency domain representation, dividing the frequency domain representation into bands, determining a characteristic difference of a first band of the bands, and determining a signature bit based on the characteristic difference, wherein determining the signature bit is performed differently based on whether an index of the first band has a first property.