Watermark information (denoted WM) consists of several symbols which are embedded continuously by reference sequence modulation in an audio or a video signal. At decoder site the WM is regained using correlation of the received signal with a corresponding reference sequence. The symbols form watermark data frames. The invention uses for the bit values ‘zero’ and ‘one’ in each payload symbol and for each payload symbol in a watermark data frame different reference sequences, without using synchronisation symbols. A logarithmic search is performed in the WM decoder to reduce the numbers of correlations to be calculated. The invention makes watermarking of critical sound signals much more robust.