Embedding a watermark includes identifying watermark locations in the data stream, partitioning the identified watermark locations into watermark location blocks each to be embedded with a watermark value portion from the watermark value and altering a predetermined maximum number of data stream values to embed the watermark value portion and introduce no more than a predetermined level of distortion according to a code table. Extracting the watermark bit-sequence includes identifying watermark locations in the data stream, partitioning the identified watermark locations into watermark location blocks each expected to be embedded with a watermark value portion from the watermark value and generating the watermark value by matching each data stream value to a watermark value portion using a code table.