Methods are provided for embedding auxiliary information in a host content signal which reduce the memory, bandwidth and computational complexity of the embedding and transmission systems. In one embodiment, a first reduced-scale signal is produced which corresponds to the host content embedded with a first logical value and producing a second reduced-scale signal corresponding to the host content embedded with a second logical value. A first set of segments from the first reduced-scale signal may be combined with a second set of segments from the second reduced-scale signal in a pre-defined manner to produce a composite embedded host content. Thus the storage and transmission requirements of the watermarking system are reduced to having to deal with only the original content plus two reduced-scale signals.