1. A digital watermarking system comprising: a memory; an embedding location component that determines data locations in binary data according to an underlying technique, each data location associated with a value; a data structure forming component that forms a data structure in the memory with values associated with the determined data locations in the binary data, each location within the data structure associated with one or more locations in the binary data; a parity component that calculates parity values for the values in the formed data structure; a modification reduction component that initially determines what locations in the binary data to modify to encode a digital watermark based on at least some of the parity values and reduces a total number of locations needed to encode the digital watermark by utilizing properties associated with the formed data structure; and an embedding component that modifies the reduced number of locations in the binary data according to the underlying technique.