The present invention relates generally to embedding and/or encoding auxiliary information within original data. For example, in one embodiment, a method of embedding auxiliary information in data is provided. The auxiliary information is not lost with compression of the embedded data. The embedded data initially includes a non-compressed form including the auxiliary information embedded therein. The method includes: (a) retrieving the auxiliary information from the non-compressed form of the embedded data; (b) compressing the non-compressed form of the embedded data; and (c) embedding the retrieved auxiliary information in the compressed embedded data, whereby the compressed embedded data comprises the auxiliary information embedded therein. Other embodiments are provided and claimed as well.