A system for embedding auxiliary digital information into a primary digital signal to form a composite digital signal. Auxiliary data bits modulate a pseudo-random (e.g., PN) sequence to provide an auxiliary data sequence used to modify the Least Perceptually Significant Bits (LPSBs) of successive multi-bit samples of the primary signal. In a cross-term compensation embodiment, a correlation between the PN sequence and the sample bits is determined, and compared to the auxiliary data bits to determine whether there is a desired correspondence. The LPSBs in the samples are toggled, if necessary, to provide the desired correspondence. The selection of LPSBs to modify accounts for a desired noise level of the auxiliary data in the primary signal. LPSBs may be modified based on a sparse PN sequence to achieve the desired noise level and conceal the presence of the auxiliary data.