(12) United States Patent
`(12) United States Patent
`Levine
`Levine
`
`11111111111111111111111111111101R011111111111111111111111111
`USOO634510OB1
`(10) Patent No.:
`US 6,345,100 B1
`US 6,345,100 B1
`(to) Patent No.:
`Feb. 5, 2002
`(45) Date of Patent:
`(45) Date of Patent:
`Feb. 5, 2002
`
`(54) ROBUST WATERMARK METHOD AND
`ROBUST WATERMARK METHOD AND
`(54)
`APPARATUS FOR DIGITAL SIGNALS
`APPARATUS FOR DIGITAL SIGNALS
`
`(75) Inventor: Earl Levine, Palo Alto, CA (US)
`Inventor: Earl Levine, Palo Alto, CA (US)
`(75)
`
`Assignee: Liquid Audio, Inc., Redwood City, CA
`(73)
`(73) ASSignee:
`quid Audio, Inc., Redwood City, CA
`(US)
`(
`)
`Subject to any disclaimer, the term of this
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`Notice:
`* )
`
`(56)
`(56)
`
`Appl. No.: 09/172,935
`(21)
`(21) Appl. No.: 09/172,935
`(22) Filed:
`Oct. 14, 1998
`(22)
`Filed:
`Oct. 14, 1998
`7
`(51) Int. Cl." ............................ H04K 1/02; H04L 9/18;
` 1104K 1/02; HO4L 9/18;
`Int. C1.7
`(51)
`GO6K 9/64
`GO6K 9/64
`(52) U.S. Cl. ........................... 380/205; 380/38; 380/37;
`U.S. Cl.
` 380/205; 380/38; 380/37;
`(52)
`805.737, 70.3832.
`380/54; 713/176; 713/179; 382/284
`Field of Search
` 713/176, 179;
`(58)
`(58) Field of Search ................................. 713/176, 179;
`380/37, 38, 51, 54, 55, 59, 205, 210, 212;
`380/37, 38, 51, 54, 55, 59, 205, 210, 212;
`341/50, 55; 348/584; 382/284,305
`341/50, 55; 348/584; 382/284, 305
`References Cited
`References Cited
`U.S. PATENT DOCUMENTS
`U.S. PATENT DOCUMENTS
`5,418,713 A 5/1995 Allen ......................... 364/403
` 364/403
`5,418,713 A
`5/1995
`Allen
`5,613,004 A 3/1997 Cooperman et al.
`... 380/28
`5,613,004 A
`3/1997
`Cooperman et al.
` 380/28
`5,636,276 A
`6/1997 Brugger ......................... 380/4
`5,636,276 A
`6/1997
`Brugger
` 380/4
`5,651,090 A
`7/1997 Moriya et al. .
`... 395/2.31
`5,651,090 A
`7/1997
`Moriya et al.
` 395/2.31
`5,684.920 A 11/1997 Iwakami et al. ..
`... 395/2.12
`5,684,920 A
`11/1997
`Iwakami et al.
` 395/2.12
`5,721,788 A
`2/1998
`Powell et al.
` 382/100
`5,721,788 A 2/1998 Powell et al. ........
`... 382/100
`5,727,092 A
`3/1998
`Sanford, II et al.
` 382/251
`5,727,092 A
`3/1998 Sanford, II et al.......... 382251
`5,727,119 A
`3/1998
`Davidson et al.
` 395/2.12
`5,727,119 A 3/1998 Davidson et al. .......... 395/212
`5,732,188 A
`3/1998
`Moriya et al.
` 395/2.28
`5,732,188 A 3/1998 Moriya et al. ............. 395/2.28
`5,734,823 A 3/1998 Saigh et al. ...
`... 395/200.06
`5,734,823 A
`3/1998
`Saigh et al.
` 395/200.06
`5,734,891 A
`3/1998
`Saigh
` 395/610
`5,734,891 A 3/1998 Saigh ......................... 395/610
`5,768.426 A 6/1998 Rhoads ....................... 382/232
`5,768,426 A
`6/1998
`Rhoads
` 382/232
`
`5,794,217 A 8/1998 Allen .......................... 705/27
`705/27
`8/1998 Allen
`5,794,217 A
`5,825,892 A
`10/1998 Braudaway et al.
`380/51
`5,825,892. A 10/1998 Braudaway et al. .......... 380/51
`5,889,868 A
`3/1999 Moskowitz et al.
`380/51
`5,889,868 A 3/1999 Moskowitz et al. .......... 380/51
`5,930,369 A * 7/1999 Cox et al.
`380/54
`5,930,369 A * 7/1999 Cox et al. ..............
`... 380/54
`5,933,798 A
`8/1999 Linnartz
`702/191
`5,933,798 A 8/1999 Linnartz ..................... 702/191
`5,956,674. A 9/1999 Smyth et al. ............... 704/229
`5,956,674 A
`9/1999 Smyth et al.
`704/229
`5,960,081. A
`9/1999 Vynne et al. ................. 380/10
`5,960,081 A
`9/1999 Vynne et al.
`380/10
`5,960,390 A 9/1999 Ueno et al. ................. 704/229
`5,960,390 A
`9/1999 Ueno et al.
`704/229
`OTHER PUBLICATIONS
`OTHER PUBLICATIONS
`66
`- -
`- -
`-
`S. Craver et al, On the Invertibility of Invisible Water
`S. Craver et al., "On the Invertibility of Invisible Water-
`marking Techniques,” Conf. on Image Processing, Oct. 29,
`marking Techniques," Conf. on Image Processing, Oct. 29,
`1997, vol. 1, pp. 540–543.*
`1997, vol. 1, pp. 540-543.*
`H.-J. Wang et al., “An Integrated Progressive Image Coding
`H.—J. Wang et al., "An Integrated Progressive Image Coding
`and Watermark System,” Conf. on Acoustics, Speech and
`and Watermark System," Conf. on Acoustics, Speech and
`Signal Processing, May 15, 1998, vol. 6, pp. 3721–3724.*
`Signal Processing, May 15, 1998, vol. 6, pp. 3721-3724.*
`* cited by examiner
`* cited by examiner
`Primary Emineral Hayes
`Primary Examiner—Gail Hayes
`ASSistant Examiner Justin T. Darrow
`Assistant Examiner—Justin T. Darrow
`(74) Attorney, Agent, Or Firm-James D. Ivey
`(74) Attorney, Agent, or Firm—James D. Ivey
`(57)
`ABSTRACT
`(57)
`ABSTRACT
`Watermark data is encoded in a digitized signal by forming
`Watermark data is encoded in a digitized signal by forming
`a noise threshold spectrum which represents a maximum
`a noise threshold spectrum which represents a maximum
`amount of imperceptible noise, spread-spectrum chipping
`amount of imperceptible noise, spread-spectrum chipping
`the noise threshold spectrum with a relatively endless stream
`the noise threshold spectrum with a relatively endless stream
`of pseudo-random bits to form a basis signal, dividing the
`of pseudo-random bits to form a basis Signal, dividing the
`basis signal into Segments, and filtering the Segments to
`basis signal into segments, and filtering the segments to
`Smooth Segment boundaries. The data encoded in the water
`smooth segment boundaries. The data encoded in the water-
`mark Signal is precoded to make the watermark data inver
`mark signal is precoded to make the watermark data inver-
`Sion robust and is convolutional encoded to further increase
`sion robust and is convolutional encoded to further increase
`the likelihood that the watermark data will subsequently be
`the likelihood that the watermark data will subsequently be
`retrievable notwithstanding lossy processing of the water
`retrievable notwithstanding lossy processing of the water-
`marked Signal
`marked signal.
`gnal.
`
`57 Claims, 24 Drawing Sheets
`57 Claims, 24 Drawing Sheets
`
`AUDIO
`AUDIO
`SIGNAL
`SIGNAL
`
`110
`
`(
`
`BASIS SIGNAL
`BASIS SGNA
`
`112
`112
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WATERMARKER 100
`WATERMARKER 100
`
`BASIS SIGNAL
`BASIS SIGNAL
`GENERATOR
`GENERATOR
`
`102
`102
`
`SIGNAL ADDER
`SIGNAL ADDER
`
`106
`106
`
`WATERMARKED
`WATERMARKED
`AUDIO
`AUDIO
`SIGNAL
`SIGNAL
`
`120
`120
`
`WATERMARK SIGNAL
`WATERMARKSIGNAL
`GENERATOR
`GENERATOR
`
`104
`
`ROBUST WATERMARK
`ROBUST WATERMARK
`DATA
`DATA
`114
`114
`
`WATERMARK SIGNAL
`WATERMARKSIGNAL
`
`
`
`116
`116
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0001
`
`

`

`f,
`
`US 6,345,100 B1
`
`Sheet 1 of 24
`17Z JO 1 lamIS
`
`Feb. 5, 2002
`
`Ui
`F
`t':Lt, 11
`
`U.S. Patent
`waled °S11
`
`FIGURE 1
`
`116
`
`114
`DATA
`
`WATERMARK SIGNAL
`
`ROBUST WATERMARK
`
`104
`
`GENERATOR
`
`WATERMARK SIGNAL
`
`120
`
`SIGNAL
`AUDIO
`
`WATERMARKED
`
`106
`
`SIGNAL ADDER
`
`102
`
`GENERATOR
`BASIS SIGNAL
`
`WATERMARKER 100
`
`112
`
`4--
`
`BASIS SIGNAL
`
`110
`
`SIGNAL
`AUDIO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0002
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 5, 2002
`Feb. 5, 2002
`
`Sheet 2 of 24
`Sheet 2 of 24
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`
`
`BASIS SIGNAL GENERATOR 102
`BASIS SIGNAL GENERATOR 102
`
`AUDIO
`AUDIO
`SIGNAL
`SIGNAL
`110
`110
`
`NOISE SPECTRUM
`NOISE SPECTRUM
`GENERATOR
`GENERATOR
`
`202
`202
`
`SECRET KEY 214
`SECRET KEY 214
`
`PSEUDO-RANDOM
`PSEUDO-RANDOM
`SEQUENCE
`SEQUENCE
`GENERATOR
`GENERATOR
`
`204
`204
`
`NOISE
`NOISE
`THRESHOLD
`THRESHOLD
`SPECTRUM
`SPECTRUM
`
`210
`210
`
`CHIPPER
`CHIPPER
`
`206
`206
`
`CHIPPED NOISE
`CHIPPED NOISE
`SPECTRUM
`SPECTRUM
`
`212
`212
`4,
`FILTER BANK
`FILTER BANK
`
`208
`208
`
`1
`BASIS SIGNAL
`BASIS SIGNAL
`112
`112
`
`FIGURE 2
`FIGURE 2
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0003
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 5, 2002
`Feb. 5, 2002
`
`Sheet 3 of 24
`Sheet 3 of 24
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`
`
`FROM
`FROM
`AUDIO
`AUDIO
`SIGNAL
`SIGNAL
`110
`110
`
`NOISE SPECTRUM GENERATOR 202
`NOISE SPECTRUM GENERATOR 202
`
` 1 PREFILTER
`
`PREFILTER
`
`302
`302
`
`SUB-BAND SIGNAL
`SUB-BAND SIGNAL
`PROCESSOR
`PROCESSOR
`
`304
`304
`
`4,
`•N
`/-
`NOISE THRESHOLD
`NOISE THRESHOLD
`SPECTRUM
`SPECTRUM
`
`306
`306
`
`TRANSIENT DAMPER
`TRANSIENT DAMPER
`
`308
`308
`
`MARGIN FILTER
`MARGINFILTER
`
`310
`
`310 i
`
`TO NOISE THRESHOLD SPECTRUM
`TO NOISE THRESHOLD SPECTRUM
`210
`210
`
`FIGURE 3
`FIGURE 3
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0004
`
`

`

`Waled *S11
`
`17Z Jo 17 lamIS
`
`HI 00-1`317£`9 Sfl
`
`FIGURE 4
`
`306
`
`414
`
`412
`
`SIGNAL
`
`INDICATOR
`TRANSIENT
`
`SPECTRUM
`THRESHOLD
`
`NOISE
`
`•
`
`SPECTRUM
`
`AUDIO SINGAL
`QUANTIZED
`
`SPECTRUM
`THRESHOLD
`
`r COARSE NOISE .\
`
`410
`
`SPECTRUM
`
`AUDIO SIGNAL
`
`
`
`-N
`
`c-
`
`408
`
`LOGIC
`
`MEASURING
`
`NOISE
`
`406
`
`LOGIC
`
`ENCODING
`QUALITY
`CONSTANT-
`SUB-BAND
`
`404
`
`LOGIC
`MODEL
`
`ACOUSTIC
`PSYCHO-
`SUB-BAND
`
`402
`
`BANK
`FILTER
`
`SUB-BAND
`
`PREFILTER 302
`
`AUDIO DATA ,
`FILTERED
`
`FROM
`
`SUB-BAND SIGNAL PROCESSOR 304
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0005
`
`

`

`Waled °S'Il
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO S laNS
`Sheet S of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`INDICATOR
`TRANSIENT
`
`SIGNAL
`
`V
`
`306
`
`412
`
`SPECTRUM
`THRESHOLD
`
`NOISE
`
`r COARSE NOISE
`
`SPECTRUM
`THRESHOLD
`
`FIGURE 5
`
`410
`
`r AUDIO SIGNAL .\
`
`SPECTRUM
`
`709
`
`504
`
`CONSTANT-QUALITY
`
`QUANTIZATION
`
`SIMULATOR
`
`HOLWTT WIS
`
`SUB-BAND ENCODER SIMULATOR 502
`
`&#707
`
`404B
`
`ACOUSTIC
`PSYCHO-
`SUB-BAND
`
`LOGIC
`MODEL
`
`4
`
`8707
`
`402B
`
`SUB-BAND
`
`--0- BANK
`FILTER
`
`PREFILTER 302
`
`AUDIO SIGNAL
`
`FROM
`
`FILTERED
`
`SUB-BAND SIGNAL PROCESSOR 304B
`
`
`
`
`
`
`
`
`
`&#709 HOSSE OOHd TV/N?IS CIN\/8-80S
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0006
`
`

`

`Waled *S11
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO 9 laNS
`Sheet 6 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`BIT STREAM
`SEUDO-RANDOM
`APPEND TO
`
` P
` ►
`
`FIGURE 6
`
`602B
`
`602C
`
`4
`
`STATE 602
`
`602A
`
`604
`
`HASHING LOGIC
`CRYPTOGRAPH IC
`
`PSEUDO-RANDOM SEQUENCE GENERATOR 204
`
`
`
`
`
`
`
`70Z (JO LWHENES) BONETTOES WOONWAH-OGIÕESd
`
`SECRET KEY 214
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0007
`
`

`

`US 6,345,100 B1
`HI 00-1`317£`9 Sfl
`
`4.
`IN)
`O
`...,
`et et ,,
`cf)
`
`Ui
`7
`
`IN)
`IN) O O
`
`U.S. Patent
`Waled *S11
`
`Z01
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0008
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 5, 2002
`Feb. 5, 2002
`
`Sheet 8 of 24
`Sheet 8 of 24
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`
`
`SPREAD
`SPECTRUM CHIPPING
`SPECTRUM CHIPPING
`
`( SPREAD
`(FOR EACH
`
`
`
`FOREACH
`TIME
`TIME
`SEGMENT
`SEGMENT
`
`NO MORE
`NO MORE
`
`802
`802
`
`MORE
`MORE
`
`C to ) NO MORE
`
`FOR EACH
`FOREACH
`FREQUENCY
`FREQUENCY
`
`
`
`
`
`NO MORE
`V
`NEXT TIME
`NEXT TIME
`SEGMENT
`SEGMENT
`
`808
`808
`
`810
`810
`
`806
`806
`
`800
`
`/ 800
`
`804
`
`MORE
`
`DETERMINE SUBJ,
`
`DETERMINE SUBJ.
`AMPLITUDE FROM POWER
`AMPLITUDEFROM POWER
`THRESHOLD FOR THE SUBJ.
`THRESHOLD FOR THE SUBJ,
`FREQUENCY. AND THE SUBJ,
`FREQUENCY AND THE SUBJ.
`TIME (AMPLITUDE = POSITIVE
`TIME (AMPLITUDE = POSITIVE
`SQUARE ROOT OF THE
`SQUARE ROOT OF THE
`POWER THRESHOLD)
`POWER THRESHOLD)
`
`POP BIT FROM PSEUDO-
`POP BIT FROMPSEUDO
`RANDOM BIT STREAM
`RANDOM BIT STREAM
`
`FIGURE 8
`
`812
`
`
`
`814
`814
`
`POPPED
`BIT = "O"?
`
`
`
`NO
`NO
`
`
`
`YES
`YES
`V
`INVERT SUBJ.
`INVERT SUBJ,
`AMPLITUDE
`AMPLITUDE
`
`
`
`816
`816
`
`
`
`818
`818
`
`
`
`INCLUDE SUBJ.
`INCLUDE SUBJ,
`AMPLITUDE IN CHIPPED
`AMPLITUDEN CHIPPED
`NOISE SPECTRUM
`NOISE SPECTRUM
`
`NEXT FREQ.
`NEXT FREQ.
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0009
`
`

`

`Waled *S11
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO 6 laNS
`Sheet 9 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`116
`
`WATERMARK SIGNAL
`
`FIGURE 9
`
`906
`
`INVERTER
`SELECTIVE
`
`902
`
`LOGIC
`
`WINDOWING
`SEGMENT
`
`904
`
`SCRAMBLER
`CYCLICAL
`
`DATA 114
`
`WATERMARK
`FROM ROBUST
`
`SIGNAL 112
`FROM BASIS
`
`WATERMARK SIGNAL GENERATOR 104
`
`
`
`
`
`
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0010
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 5, 2002
`Feb. 5, 2002
`
`Sheet 10 of 24
`Sheet 10 of 24
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`1000
`-
`
`
`
`
`
`
`
`
`
`CSELECTIVE)
`
`SELECTIVE
`INVERTER
`INVERTER
`
`•
`POP BIT FROM
`POP BIT FROM
`CYCLICALLY
`CYCLICALLY
`SCRAMBLED ROBUST
`SCRAMBLED ROBUST
`WATERMARKDATA
`WATERMARK DATA
`
`FOR EACH SAMPLE
`FOREACHSAMPLE
`OF A
`OFA
`CORRESPONDING
`CORRESPONDING
`SEGMENT
`SEGMENT
`1
`NO MORE
`NO MORE
`
`
`
`END
`
`FIGURE 10
`FIGURE 10
`
`1002
`1002
`
`1004
`1004
`
`MORE
`
`1006
`
`
`
`
`
`IS THE
`POPPED BITA
`LOGICAL"O"?
`
`YES
`YES
`
`
`
`NO
`NO
`
`1008-\_
`1008
`
`
`
`NEGATE THE
`NEGATE THE
`AMPLITUDE OF THE
`AMPLITUDE OF THE
`SUBJECT SAMPLE
`SUBJECT SAMPLE
`
`1010
`1010
`
`
`
`NEXT SAMPLE)
`NEXT SAMPLE
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0011
`
`

`

`US 6,345,100 B1
`HI 00-1`317£`9 Sfl
`
`17Z JO II laNS
`Sheet 11 of 24
`
`N
`
`Ui
`O
`t':Lt, 11
`
`Waled *S11
`U.S. Patent
`
`
`
`INVERTER 906
`TO SELECTIVE
`
`E/\|LOETES O 1
`
`80||
`
`1108
`
`FIGURE 11
`
`CYCLICALLY SCRAMBLED ROBUST WATERMARK DATA
`
`1104E
`
`1104D
`
`1104C
`
`1104B
`
`1104A
`
`1106
`
`SELECTOR
`CIRCULAR
`
`DATA 114
`
`WATERMARK
`FROM ROBUST
`
`RESEQUENCER 1102
`
`Z0|| || HBONETTÖESER
`
`CYCLICAL SCRAMBLER 904
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0012
`
`

`

`Waled *S11
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO fl laNS
`Sheet 12 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`114
`
`DATA
`
`ROBUST WATERMARK
`
`V
`
`1210
`
`WATERMARK DATA
`INVERSION-ROBUST
`
`FIGURE 12
`
`1208
`
`ENCODER
`
`CONVOLUTIONAL
`
`1206
`
`PRECODER
`1/(1 XOR D)
`
`1202
`
`DATA
`
`RAW WATERMARK
`
`N
`
`DATA ROBUSTNESS ENHANCER 1204
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0013
`
`

`

`Waled *S11
`
`17Z JO CI laNS
`
`HI 00-1`317£`9 Sfl
`
`SIGNAL
`
`VERIFICATION
`
`•
`
`1314
`
`CANDIDATE
`WATERMARK
`
`,-7
`
`1312
`
`SIGNAL
`BASIS
`
`FIGURE 13
`
`1306
`
`1304
`
`1302
`
`EVALUATOR
`
`BIT-WISE
`
`CORRELATOR
`
`GENERATOR
`BASIS SIGNAL
`
`WATERMARK DECODER 1300
`
`1310 r
`
`AUDIO SIGNAL
`WATERMARKED
`
`t
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0014
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 5, 2002
`Feb. 5, 2002
`
`Sheet 14 of 24
`Sheet 14 of 24
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`CORRELATOR 1304
`CORRELATOR 1304
`
`
`
`FROM BASIS
`FROM BASIS
`SIGNAL 1312
`SIGNAL 1312
`
`SEGMENT
`SEGMENT
`WINDOWING
`WINDOWING
`LOGIC
`LOGIC
`
`1402
`1402
`
`CYCLICAL
`CYCLICAL
`SCRAMBLER
`SCRAMBLER
`
`1406
`1406
`
`c -
`SEGMENTED
`SEGMENTED
`BASIS SIGNAL
`BASIS SIGNAL
`
`1410
`1410
`
`FROM
`FROM
`WATERMARKED
`WATERMARKED
`AUDIO SIGNAL
`AUDIO SIGNAL
`1310
`1310
`
`
`
`
`
`tBASIS SIGNAL
`BASIS SIGNAL
`SEGMENT
`SEGMENT
`DATABASE
`DATABASE
`
`1412
`1412
`
`cAUDIO SIGNAIL
`AUDIO SIGNAL
`4
`SEGMENT
`SEGMENT
`DATABASE
`DATABASE
`
`1412
`1412
`
`SEGMENT
`SEGMENT
`COLLECTOR
`COLLECTOR
`
`1404
`1404
`
`SEGMENT
`SEGMENT
`EVALUATOR
`EVALUATOR
`
`1408
`1408
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WATERMARK CANDIDATE
`WATERMARK CANDIDATE
`
`FIGURE 14
`FIGURE 14
`
`
`
`1314
`1314
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0015
`
`

`

`Waled *S11
`U.S. Patent
`
`17Z JO SI laNS
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`SIGNAL
`
`VERIFICATION
`
`1514
`
`DATA
`
`WATERMARK
`EXPECTED
`
`1512
`
`DATA CANDIDATE
`RAW WATERMARK
`
`1510
`
`CANDIDATE
`
`WATERMARK DATA
`INVERSION—ROBUST
`
`r-Y
`
`15
`
`FIGURE
`
`1506
`
`1504
`
`1502
`
`LOGIC
`
`COMPARISON
`
`DECODER
`1/(1 XOR D)
`
`DECODER
`
`CONVOLUTIONAL
`
`1508
`
`BUFFER
`CIRCULAR
`
`1314
`
`CANDIDATE
`WATERMARK
`
`FROM
`
`1520
`
`COMPARISION LOGIC
`
`17
`
`PREDETERMINED THRESHOLD 1522
`
`
`
`I
`
`BIT—WISE EVALUATOR 1306
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0016
`
`

`

`17Z JO 91 laNS
`Sheet 16 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`FIGURE 16
`
`1606D
`
`1606C
`
`1606B
`
`1606A
`
`GENERATOR
`ENCODED BIT
`
`• -iv.
`
`Feb. 5, 2002
`
`Ui
`F
`
`: :
`i t\ 1
`
`Waled *S11
`U.S. Patent
`
`DATA 114
`► WATERMARK
`
`ROBUST
`
`
`
`1608A
`
`1608A
`
`1608A
`
`1608A
`
`1604
`
`1602
`
`SHIFTER
`
`DATA 1210
`WATERMARK
`
`ROBUST
`INVERSION-
`
`CONVOLUTIONAL ENCODER 1208
`
`80Z) »JECIOONE TWNO||LINTOANOO
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0017
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 5, 2002
`Feb. 5, 2002
`
`Sheet 17 of 24
`Sheet 17 of 24
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`A
`
`1702
`
`1
`
`0
`
`-1
`
`amplitude
`amplitude
`
`4096
`4096
`
`8.192
`8192
`
`12288
`12288
`
`16384
`16384
`
`samples
`samples
`
`FIGURE 17A
`FIGURE 17A
`
`
`
`
`
`
`
`1704
`1704
`
`1708
`1708
`
`1710
`1710
`
`t
`4096
`
`8192
`
`12288
`12288
`
`16384
`16384
`
`SampleS
`sampts
`
`FIGURE 17B
`FIGURE 17B
`
`amplitude
`amplitude
`
`1706
`
`r j 1708C
`r )
`
`
`
`4096
`
`8192
`
`12288
`
`16384
`16384
`
`samples
`Samples
`
`1710C
`1710C
`FIGURE 17C
`FIGURE 17C
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0018
`
`

`

`Waled *S11
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO XI laNS
`Sheet 18 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`ENCODED BIT
`
`
`
`||8 CIEGIOONE
`
`\7809||
`
`1608A
`
`FIGURE 18
`
`1808
`
`PARITY BIT GENERATOR
`
`1802
`
`1806
`
`1804
`
`1604
`
`ENCODED BIT GENERATOR 1606A
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0019
`
`

`

`U.S. Patent
`U.S. Patent
`
`Feb. 5, 2002
`Feb. 5, 2002
`
`Sheet 19 of 24
`Sheet 19 of 24
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`(
`
`BEGIN
`BEGIN
`
`)
`
`V
`
`1902
`1902
`
`1900
`
`1. 1900
`
`
`
`
`
`(
`
`
`
`
`
`FOREACH BIT OF
`FOR EACH BIT OF
`THE EXPECTED
`THE EXPECTED
`ROBUST WATERMARK
`ROBUST WATERMARK
`DATA
`DATA
`i
`NO MORE
`NO MORE
`
`MORE
`MORE
`
`
`
`v
`
`1904
`1904
`
`
`
`
`
`CORRELATE
`CORRELATE
`CORRESPONDING SEGMENTS
`CORRESPONDING SEGMENTS
`OF THE WATERMARKED
`OF THE WATERMARKED
`AUDIO SIGNAL AND
`AUDIO SIGNAL AND
`SEGMENTED BASIS SIGNAL
`SEGMENTED BASIS SIGNAL
`FOR THE SUBJECT BIT
`FOR THE SUBJECTBT
`
`
`
`
`
`1906-\_ SELF-CORRELATE SEGMENTS
`SELF-CORRELATE SEGMENTS
`1906
`OF SEGMENTED BASIS
`OF SEGMENTED BASIS
`SIGNAL FOR THE SUBJECT
`SIGNAL FOR THE SUBJECT
`BIT
`BIT
`
`
`
`1908-\_
`1908
`
`
`
`
`
`
`
`
`
`DETERMINE THE RATIO OF
`DETERMINE THE RATIO OF
`THE CORRELATION TO THE
`THE CORRELATION TO THE
`SELF-CORRELATION
`SELF-CORRELATION
`1,
`ESTIMATE THE PROBABILITY
`ESTIMATE THE PROBABILITY
`OF THE SUBJECT BIT HAVING
`OF THE SUBJECT BIT HAVING
`A LOGICAL VALUE OF ONE
`A LOGICAL VALUE OF ONE
`FROM THE RATIO
`FROM THE RATIO
`
`
`
`FIGURE 19
`FIGURE 19
`
`_ J -(
`1912
`
`4,
`NEXT BIT
`NEXT BIT
`
`)
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0020
`
`

`

`Waled *S11
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO OZ laNS
`Sheet 20 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`2112
`
`CANDIDATE
`BASIS SIGNAL
`
`2008
`
`FILTER BANK
`
`2006
`
`CHIPPER
`
`
` L
`
`2004
`
`GENERATOR
`SEQUENCE
`
`PSEUDO—RANDOM
`
`SECRET KEY 2014
`
`NTS OFFSET 2011
`
`.J
`
`i
`J
`
`2010
`
`
`
`\
`
`CITOHSENHH|
`
`W[]?||0EdS
`
`SPECTRUM
`THRESHOLD
`
`ESION
`
`NOISE
`
`v
`
`[
`
`2002
`
`GENERATOR
`
`NOISE SPECTRUM
`
`WATERMARK ALIGNMENT MODULE 2000
`
`
`
`
`
`000Z BINGOWINEWNOIT, XHVW HIVM
`
`20A
`
`FIGURE
`
`1310
`
`AUDIO SIGNAL
`WATERMARKED
`
`PORTION OF
`
`LEADING
`
`
`
`
`
`
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0021
`
`

`

`Waled *S11
`U.S. Patent
`
`17Z JO It laNS
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`FIGURE 20
`
`FIGURE 20B
`
`FIGURE 20A
`
`FIGURE 20B
`
`BEST CORR. 2030
`
`BEST OFFSET 2028
`
`V
`
`OFFSET 2024
`
`2026
`
`COMPARATOR
`
`CORRELATION 2022 -1110
`
`4
`
`2020
`
`CORRELATOR
`
`-±
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0022
`
`

`

`Waled *S11
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO ZZ laNS
`Sheet 22 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`TO N.T.S. DATABASE
`ADD THE NEW N.T.S.
`
`2108-1_
`
`OFFSET
`
`SPECTRUM FOR THIS
`NOISE THRESHOLD
`2106---k_GENERATE A NEW
`
`MWEN W ELWHENES)
`
`ir
`
`FIGURE 21A
`
`CURRENT OFFSET
`
`N.T.S. FOR THE
`
`2112-k_ADJUST THE EXISTING
`
`)
`
`END
`
`(
`
`EXISTING N.T.S.
`RETRIEVE THE
`
`*
`YES
`
`Å
`
`2110
`
`OFFSET
`
`RECORDED BEST
`ACCORDING TO
`
`ADJUST AUDIO SIGNAL
`
`_f-2126
`
`4,
`
`ON
`
`NO
`
`AN EXISTING N.T.S.?
`
`ALIGNED WITH
`CENTRAL OFFSET
`IS THE
`
`TEMPORALLY
`CURRENT
`
`MORE
`
`2102
`
`Yr (FOR EACH RANGE
`
`NO MORE
`
`ERHOW ON
`
`OF OFFSETS
`
`2104
`
`2100
`
`)
`
`BEGIN
`
`(
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0023
`
`

`

`Waled *S11
`U.S. Patent
`
`Feb. 5, 2002
`
`17Z JO £Z laNS
`Sheet 23 of 24
`
`HI 00-1`317£`9 Sfl US 6,345,100 B1
`
`NEXT OFFSET
`
`2122
`
`BEST SO FAR
`
`CORRELATION IF THE
`THE B.S.C., AND THE
`RECORD THE OFFSET,
`
`2120—\_
`
`SIGNAL
`
`WITH THE AUDIO
`
`*
`
`MORE
`
`CORRELATE THE B.S.C.
`
`FIGURE 21
`
`FIGURE 21B
`
`FIGURE 21B
`
`NEXT RANGE
`
`NO MORE
`
`I
`
`RANGE
`
`OF THE SUBJECT
`FOR EACH OFFSET
`
`2124
`
`FIGURE 21A
`
`2118—__
`
`2116
`
`CANDIDATE
`BASIS SIGNAL
`
`N.T.S. TO FORM A
`
`CHIP AND FILTER THE
`
`2114
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0024
`
`

`

`Waled *S11
`U.S. Patent
`
`17Z JO 17Z laNS
`
`US 6,345,100 B1
`HI 00-1`317£`9 Sfl
`
`2220
`Y.
`
`OOZZZ
`
`2220C
`
`CIRCUITRY
`PROCESSING
`
`AUDIO
`
`
`
`2220D
`
`2202
`
`PROCESSOR
`
`7,...__
`
`00ZZ
`
`2200
`
`FIGURE 22
`
`W.A.S. 1310
`
`
`
` 1
`
`A
`
`W.A.M. 2000
`
`
`
`OZZZ09ZZ
`
`
`
`SIGNAL
`
`VERIFICATION
`
`47
`WATERMARK DECODER 1300
`
`1
`+
`
`pD.R.E. 1204
`
`•
`—(.. 114
`
`
`
`2230
`
`2206
`
`W.A.S. 120
`
`100
`
`WATERMARKER
`
`I
`AUDIO SIGNAL 110-1
`
`‘..
`C
`
`
`
`MEMORY 2204
`
`DISH-Blue Spike-408
`Exhibit 1015, Page 0025
`
`

`

`1
`1
`ROBUST WATERMARK METHOD AND
`ROBUST WATERMARK METHOD AND
`APPARATUS FOR DIGITAL SIGNALS
`APPARATUS FOR DIGITAL SIGNALS
`
`CROSS-REFERENCE TO RELATED
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`APPLICATIONS
`The present application is related to the following
`The present application is related to the following
`co-pending patent applications which are filed on the same
`co-pending patent applications which are filed on the same
`date on which the present application is filed and which are
`date on which the present application is filed and which are
`incorporated herein in their entirety by reference: (i) patent
`incorporated herein in their entirety by reference:(i) patent
`application Ser. No. 09/172,583 entitled “Robust Watermark
`application Ser. No. 09/172,583 entitled "Robust Watermark
`Method and Apparatus for Digital Signals” by Earl Levine;
`Method and Apparatus for Digital Signals" by Earl Levine;
`(ii) patent application Ser. No. 09/172.936 entitled "Robust
`(ii) patent application Ser. No. 09/172,936 entitled "Robust
`Watermark Method and Apparatus for Digital Signals” by
`Watermark Method and Apparatus for Digital Signals" by
`Earl Levine and Jason S. Brownell; (iii) patent application
`Earl Levine and Jason S. Brownell; (iii) patent application
`Ser. No. 09/172,937 entitled “Secure Watermark Method
`Ser. No. 09/172,937 entitled "Secure Watermark Method
`and Apparatus for Digital Signals' by Earl Levine; and (iv)
`and Apparatus for Digital Signals" by Earl Levine; and (iv)
`patent application Ser. No. 09/172,922 entitled “Efficient
`patent application Ser. No. 09/172,922 entitled "Efficient
`Watermark Method and Apparatus for Digital Signals” by
`Watermark Method and Apparatus for Digital Signals" by
`Earl Levine.
`Earl Levine.
`
`FIELD OF THE INVENTION
`FIELD OF THE INVENTION
`The present invention relates to digital Signal processing
`The present invention relates to digital signal processing
`and, in particular, to a particularly robust watermark mecha
`and, in particular, to a particularly robust watermark mecha-
`nism by which identifying data can be encoded into digital
`nism by which identifying data can be encoded into digital
`Signals. Such as audio or Video signals. Such that the identi
`signals such as audio or video signals such that the identi-
`fying data are not perceptible to a human viewer of the
`fying data are not perceptible to a human viewer of the
`Substantive content of the digital Signals yet are retrievable
`substantive content of the digital signals yet are retrievable
`and are Sufficiently robust to Survive other digital signal
`and are sufficiently robust to survive other digital signal
`processing.
`processing.
`
`BACKGROUND OF THE INVENTION
`BACKGROUND OF THE INVENTION
`Video and audio data have traditionally been recorded and
`Video and audio data have traditionally been recorded and
`delivered as analog signals. However, digital Signals are
`delivered as analog signals. However, digital signals are
`becoming the transmission medium of choice for Video,
`becoming the transmission medium of choice for video,
`audio, audiovisual, and multimedia information. Digital
`audio, audiovisual, and multimedia information. Digital
`audio and Video signals are currently delivered widely
`audio and video signals are currently delivered widely
`through digital Satellites, digital cable, and computer net
`through digital satellites, digital cable, and computer net-
`WorkS Such as local area networks and wide area networks,
`works such as local area networks and wide area networks,
`e.g., the Internet. In addition, digital audio and Video signals
`e.g., the Internet. In addition, digital audio and video signals
`are currently available in the form of digitally recorded
`are currently available in the form of digitally recorded
`material Such as audio compact discs, digital audio tape
`material such as audio compact discs, digital audio tape
`(DAT), minidisc, and laserdisc and digital video disc (DVD)
`(DAT), minidisc, and laserdisc and digital video disc (DVD)
`Video media. AS used herein, a digitized signal refers to a
`video media. As used herein, a digitized signal refers to a
`digital signal whose Substantive content is generally analog
`digital signal whose substantive content is generally analog
`in nature, i.e., can be represented by an analog Signal. For
`in nature, i.e., can be represented by an analog signal. For
`example, digital Video and digital audio Signals are digitized
`example, digital video and digital audio signals are digitized
`Signals Since Video images and audio content can be repre
`signals since video images and audio content can be repre-
`Sented by analog signals.
`sented by analog signals.
`The current tremendous growth of digitally Stored and
`The current tremendous growth of digitally stored and
`delivered audio and Video is that digital copies which have
`delivered audio and video is that digital copies which have
`exactly the same quality of the original digitized signal can
`exactly the same quality of the original digitized signal can
`easily be made and distributed without authorization not
`easily be made and distributed without authorization not-
`withstanding illegality of Such copying. The Substantive
`withstanding illegality of such copying. The substantive
`content of digitized Signals can have significant proprietary
`content of digitized signals can have significant proprietary
`value which is Susceptible to considerable diminution as a
`value which is susceptible to considerable diminution as a
`result of unauthorized duplication.
`result of unauthorized duplication.
`It is therefore desirable to include identifying data in
`It is therefore desirable to include identifying data in
`digitized Signals having valuable content Such that duplica
`digitized signals having valuable content such that duplica-
`tion of the digitized signals also duplicates the identifying
`tion of the digitized signals also duplicates the identifying
`data and the Source of Such duplication can be identified. The
`data and the source of such duplication can be identified. The
`identifying data should not result in humanly perceptible
`identifying data should not result in humanly perceptible
`changes to the Substantive content of the digitized signal
`changes to the substantive content of the digitized signal
`when the Substantive content is presented to a human viewer
`when the substantive content is presented to a human viewer 65
`65
`as audio and/or Video. Since Substantial value is in the
`as audio and/or video. Since substantial value is in the
`Substantive content itself and in its quality, any humanly
`substantive content itself and in its quality, any humanly
`
`US 6,345,100 B1
`US 6,345,100 B1
`
`s
`
`2
`2
`perceptible degradation of the Substantive content Substan
`perceptible degradation of the substantive content substan-
`tially diminishes the value of the digitized signal. Such
`tially diminishes the value of the digitized signal. Such
`imperceptible identifying data included in a digitized signal
`imperceptible identifying data included in a digitized signal
`is generally known as a watermark.
`is generally known as a watermark.
`Such watermarks should be robust in that Signal process
`Such watermarks should be robust in that signal process-
`ing of a digitized signal which affects the Substantive content
`ing of a digitized signal which affects the substantive content
`of the digitized signal to a limited, generally imperceptible
`of the digitized signal to a limited, generally imperceptible
`degree should not affect the watermark So as to make the
`degree should not affect the watermark so as to make the
`watermark unreadable. For example, Simple conversion of
`watermark unreadable. For example, simple conversion of
`the digital signal to an analog Signal and conversion of the
`io the digital signal to an analog signal and conversion of the
`analog signal to a new digital signal should not erode the
`analog signal to a new digital signal should not erode the
`watermark Substantially or, at least, should not render the
`watermark substantially or, at least, should not render the
`watermark irretrievable. Conventional watermarks which
`watermark irretrievable. Conventional watermarks which
`hide identifying data in unused bits of a digitized signal can
`hide identifying data in unused bits of a digitized signal can
`be defeated in Such a digital-analog-digital conversion. In
`is be defeated in such a digital-analog-digital conversion. In
`15
`addition, Simple inversion of each digitized amplitude,
`addition, simple inversion of each digitized amplitude,
`which results in a different digitized signal of equivalent
`which results in a different digitized signal of equivalent
`Substantive content when the content is audio, should not
`substantive content when the content is audio, should not
`render the watermark unreadable. Similarly, addition or
`render the watermark unreadable. Similarly, addition or
`removal of a number of Samples at the beginning of a
`20 removal of a number of samples at the beginning of a
`digitized signal should not render a watermark unreadable.
`digitized signal should not render a watermark unreadable.
`For example, prefixing a digitized audio Signal with a
`For example, prefixing a digitized audio signal with a
`one-tenth-Second period of Silence should not Substantially
`one-tenth-second period of silence should not substantially
`affect ability to recognize and/or retrieve the watermark.
`affect ability to recognize and/or retrieve the watermark.
`Similarly, addition of an extra Scanline or an extra pixel or
`25 Similarly, addition of an extra scanline or an extra pixel or
`25
`two at the beginning of each Scanline of a graphical image
`two at the beginning of each scanline of a graphical image
`should not render any watermark of the graphical image
`should not render any watermark of the graphical image
`unrecognizable and/or irretrievable.
`unrecognizable and/or irretrievable.
`Digitized Signals are often compressed for various
`Digitized signals are often compressed for various
`reasons, including delivery through a communications or
`30 reasons, including delivery through a communications or
`storage medium of limited bandwidth and archival. Such
`storage medium of limited bandwidth and archival. Such
`compression can be lossy in that Some of the Signal of the
`compression can be lossy in that some of the signal of the
`Substantive content is lost during Such compression. In
`substantive content is lost during such compression. In
`general, the object of Such lossy compression is to limit loSS
`general, the object of such lossy compression is to limit loss
`of Signal to levels which are not perceptible to a human
`35 of signal to levels which are not perceptible to a human
`35
`viewer or listener of the Substantive content when the
`viewer or listener of the substantive content when the
`compressed signal is Subsequently reconstructed and played
`compressed signal is subsequently reconstructed and played
`for the viewer or listener. A watermark should Survive Such
`for the viewer or listener. A watermark should survive such
`lossy compression as well as other types of lossy Signal
`lossy compression as well as other types of lossy signal
`processing and should remain readable within in the recon
`40 processing and should remain readable within in the recon-
`40
`Structed digitized signal.
`structed digitized signal.
`In addition to being robust, the watermark should be
`In addition to being robust, the watermark should be
`relatively difficult to detect without specific knowledge
`relatively difficult to detect without specific knowledge
`regarding the manner in which the watermark is added to the
`regarding the manner in whic