(12)
`
`United States Patent
`Fallon
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,161,506 B2
`*Jan. 9, 2007
`
`US007161506B2
`
`(54) SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`DEPENDENT DATA COMPRESSION
`
`(75) Inventor: James J. Fallon, Armonk, NY (US)
`
`(73) Assignee: Realtime Data LLC, New York, NY
`(Us)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`
`3/1986 Dang et a1.
`4,574,351 A
`6/1986 Ohkubo et a1.
`4,593,324 A
`7/1987 Mathes et a1.
`4,682,150 A
`3/1988 MacCrisken
`4,730,348 A
`2/1989 Makansi et a1~
`4,804,959 A
`9/1989 Van Maren et a1.
`4,870,415 A
`4,872,009 A 10/1989 Tsukiyama et a1~
`4,876,541 A 10/1989 Storer
`4,888,812 A 12/1989 Dinan et a1.
`4,906,995 A
`3/1990 Swanson
`
`This patent is subject to a terminal dis-
`
`FOREIGN PATENT DOCUMENTS
`
`Clalmer'
`
`DE
`
`4127518
`
`2/1992
`
`(Continued)
`OTHER PUBLICATIONS
`
`(21) Appl. No.: 10/668,768
`
`(22) Filed:
`
`Sep. 22, 2003
`
`(65)
`
`Prior Publication Data
`Us 2004/0056783 A1
`Man 25, 2004
`
`Jack VenbruX, A VLSI Chip Set for High-Speed Lossless Data
`gorgpreission , lIE2ElIE\ITrA2‘1nsj OnlgCgigcuits
`3S9§istem for Video
`
`ec n0 ogy, v0. ,
`
`0.
`
`,
`
`ec.
`
`,PP~
`
`-
`
`.
`
`Related US. Application Data
`
`(Continued)
`
`(63) Continuation of application No. 10/016,355, ?led on
`Oct. 29, 2001, HOW Pat. NO. 6,624,761, which is a
`.
`.
`.
`.
`.
`contlnuatlon-m-part of appl1cat1on No. 09/705,446,
`?led 011 Nov. 3, 2000, HOW Pat. NO. 6,309,424, which
`is a continuation of application No. 09/210,491, ?led
`on Dec. 11, 1998, noW Pat. No. 6,195,024.
`
`(51) Int_ CL
`(200601)
`H03M 7/34
`(52) US. Cl. ......................................... .. 341/51- 341/79
`(58) Field of Classi?cation Search ................ .. 341/50,
`34161 67 79 75
`See application ?le for Complete Search h’isto’ry ’
`'
`
`(56)
`
`References Cited
`
`US. PATENT DOCUMENTS
`
`4,127,518 A 11/1978 Coy et a1.
`4,302,775 A 11/1981 Widergren et 31.
`4,394,774 A
`7/1983 Widergren et a1.
`
`. i .
`.
`Pnmary Examm” Lmh .NguYeI:
`(74) Attorney, Agent, or FzrmiFlsh & Neave 1P Group of
`R0 es & Gm LLP
`p
`y
`(57)
`
`ABSTRACT
`
`Systems and methods for providing fast and e?‘icient data
`compression using a combination of content independent
`data Compression and Content dependent data Compression
`In one aspect’ a method for Compressing data comprises the
`steps of: analyZmg a data block of an lnput data stream to
`identify a data type of the data block, the input data stream
`comprising a plurality of disparate data types; performing
`content dependent data compression on the data block, if the
`data type of the data block is identi?ed; performing content
`independent data compression on the data block, if the data
`type of the data block is not identi?ed.
`
`99 Claims, 34 Drawing Sheets
`
`RAYIO 0F n LEAST cNz
`ENCGDED mm smcx
`
`SELECT EucooEn
`mu BLOCK WITH
`GREATEST
`coMPREssloN RATIO
`
`:22
`
`APPE DNULL
`DESCRIF'IOR TO
`uNEucoDED mpur
`mu BLOCK
`
`m
`
`cnRREsPoNDlNG
`nEscRvPTo
`
`OUTPUT ENCODED
`mu awcx wrm
`nsscwma
`
`25
`
`OUTPUT u ENODDED
`DATA BLOCK WITH
`NULL DEscFuPl‘oR
`
`32°
`
`3:2
`
`YES
`
`\‘ERMWATE um
`COMPRESSION
`PRocsss
`
`RECEYVE NEXT DATA m
`BLOCK FROM 1mm
`STREAM
`
`B
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 001
`
`

`

`US 7,161,506 B2
`Page 2
`
`US. PATENT DOCUMENTS
`
`4,929,946
`4,965,675
`5,028,922
`5,045,848
`5,045,852
`5,046,027
`5,049,881
`5,097,261
`5,113,522
`5,121,342
`5,150,430
`5,159,336
`5,175,543
`5,179,651
`5,187,793
`5,191,431
`5,204,756
`5,209,220
`5,212,742
`5,226,176
`5,227,893
`5,231,492
`5,237,460
`5,237,675
`5,243,341
`5,243,348
`5,247,638
`5,247,646
`5,263,168
`5,270,832
`5,287,420
`5,293,379
`5,307,497
`5,309,555
`5,355,498
`5,357,614
`5,379,036
`5,379,757
`5,381,145
`5,394,534
`5,396,228
`5,400,401
`5,403,639
`5,406,278
`5,406,279
`5,412,384
`5,414,850
`5,420,639
`5,452,287
`5,461,679
`5,467,087
`5,471,206
`5,479,587
`5,486,826
`5,495,244
`5,506,844
`5,506,872
`5,530,845
`5,533,051
`5,535,356
`5,537,658
`5,557,551
`5,557,668
`5,557,749
`5,561,824
`5,574,952
`5,574,953
`5,583,500
`5,590,306
`5,596,674
`5,604,824
`
`5/1990
`10/1990
`7/1991
`9/1991
`9/1991
`9/1991
`9/1991
`3/1992
`5/1992
`6/1992
`9/1992
`10/1992
`12/1992
`1/1993
`2/1993
`3/1993
`4/1993
`5/1993
`5/1993
`7/1993
`7/1993
`7/1993
`8/1993
`8/1993
`9/1993
`9/1993
`9/1993
`9/1993
`11/1993
`12/1993
`2/1994
`3/1994
`4/1994
`5/1994
`10/1994
`10/1994
`1/1995
`1/1995
`1/1995
`2/1995
`3/1995
`3/1995
`4/1995
`4/1995
`4/1995
`5/1995
`5/1995
`5/1995
`9/1995
`10/1995
`11/1995
`11/1995
`12/1995
`1/1996
`2/1996
`4/1996
`4/1996
`6/1996
`7/1996
`7/1996
`7/1996
`9/1996
`9/1996
`9/1996
`10/1996
`11/1996
`11/1996
`12/1996
`12/1996
`1/1997
`2/1997
`
`O’Brien et al.
`Hori et al.
`Huang
`Fascenda
`Mitchell et al.
`Taalfe et al.
`Gibson et al.
`Langdon, Jr. et al.
`Dinwiddie, Jr. et al.
`SZymborski
`Chu
`Rabin et al.
`LantZ
`Taalfe et al.
`Keith et al.
`Hasegawa et al.
`Chevion et al.
`Hiyama et al.
`Normile et al.
`WestaWay et al.
`Ett
`Dangi et al.
`Miller et al.
`Hannon, Jr.
`Seroussi et al.
`Jackson
`O’Brien et al.
`Osterlund et al.
`Toms et al.
`Balkanski et al.
`Barrett
`Carr
`Feigenbaum et al.
`Akins et al.
`Provino et al.
`Pattisam et al.
`Storer
`Hiyama et al.
`Allen et al.
`KulakoWski et al.
`Garahi
`Wasilewski et al.
`Belsan et al.
`Graybill et al.
`Anderson et al.
`Chang et al.
`Whiting
`Perkins
`DiCecco
`Normile et al.
`Chu
`Allen et al.
`Campbell et al.
`Remillard
`Jeong et al.
`Rao
`Mohler
`Hiatt et al.
`James
`Kim et al.
`Bakke et al.
`Craft
`Brady
`Norris
`Carreiro et al.
`Brady et al.
`Rust et al.
`Allen et al.
`Watanabe et al.
`Bhandari et al.
`Chui et al.
`
`5,606,706
`5,612,788
`5,613,069
`5,615,017
`5,621,820
`5,623,623
`5,623,701
`5,627,534
`5,627,995
`5,629,732
`5,630,092
`5,635,632
`5,635,932
`5,642,506
`5,649,032
`5,652,795
`5,652,857
`5,652,917
`5,654,703
`5,655,138
`5,666,560
`5,668,737
`5,671,389
`5,675,333
`5,694,619
`5,696,927
`5,703,793
`5,715,477
`5,717,393
`5,717,394
`5,719,862
`5,721,958
`5,724,475
`5,729,228
`5,748,904
`5,757,852
`5,771,340
`5,778,411
`5,781,767
`5,784,572
`5,787,487
`5,796,864
`5,799,110
`5,805,932
`5,808,660
`5,809,176
`5,809,337
`5,812,789
`5,818,368
`5,818,369
`5,818,530
`5,819,215
`5,825,424
`5,832,037
`5,832,126
`5,836,003
`5,838,996
`5,839,100
`5,841,979
`5,847,762
`5,861,824
`5,861,920
`5,867,167
`5,870,036
`5,870,087
`5,872,530
`5,883,975
`5,886,655
`5,889,961
`5,915,079
`5,917,438
`5,920,326
`5,936,616
`
`2/1997
`3/1997
`3/1997
`3/1997
`4/1997
`4/1997
`4/1997
`5/1997
`5/1997
`5/1997
`5/1997
`6/1997
`6/1997
`6/1997
`7/1997
`7/1997
`7/1997
`7/1997
`8/1997
`8/1997
`9/1997
`9/1997
`9/1997
`10/1997
`12/1997
`12/1997
`12/1997
`2/1998
`2/1998
`2/1998
`2/1998
`2/1998
`3/1998
`3/1998
`5/1998
`5/1998
`6/1998
`7/1998
`7/1998
`7/1998
`7/1998
`8/1998
`8/1998
`9/1998
`9/1998
`9/1998
`9/1998
`9/1998
`10/1998
`10/1998
`10/1998
`10/1998
`10/1998
`11/1998
`11/1998
`11/1998
`11/1998
`11/1998
`11/1998
`12/1998
`1/1999
`1/1999
`2/1999
`2/1999
`2/1999
`2/1999
`3/1999
`3/1999
`3/1999
`6/1999
`6/1999
`7/1999
`8/1999
`
`Takamoto et al.
`Stone
`Walker
`Choi et al.
`Rynderman et al.
`Kim et al.
`Bakke et al.
`Craft
`Miller et al.
`MoskoWitZ et al.
`Carreiro et al.
`Fay et al.
`Shinagawa et al.
`Lee
`Burt et al.
`Dillon et al.
`Shimoi et al.
`Maupin et al.
`Clark, 11
`Kikinis
`Moertl et al.
`Iler
`Saliba
`Boursier et al.
`Konno
`MacDonald et al.
`Wise et al.
`Kikinis
`Nakano et al.
`Schwartz et al.
`Lee et al.
`Kikinis
`Kirsten
`FranasZek et al.
`Huang et al.
`Kericevic et al.
`NakaZato et al.
`DeMoss et al.
`Inoue et al.
`Rostoker et al.
`Hashimoto et al.
`Callahan
`Israelsen et al.
`KaWashima et al.
`Sekine et al.
`Yajima
`Hannah et al.
`DiaZ
`Langley
`
`Withers .................... .. 341/107
`Can?eld et al.
`Dobson et al.
`Can?eld et al.
`Park
`Tanaka
`Sadeh
`deCarmo
`Wegener
`Schulhof et al.
`Can?eld et al.
`Ryu et al.
`Mead et al.
`Deering
`FranasZek et al.
`Chau
`Domyo et al.
`Narita et al.
`Rust
`Dobbek
`Vondran, Jr. et al.
`Ando
`Rentschler et al.
`Torborg, Jr. et al.
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 002
`
`

`

`US 7,161,506 B2
`Page 3
`
`9/1999 Panaoussis ................. .. 341/51
`5,949,355 A *
`9/1999 Heath
`5,955,976 A
`9/1999 Adams
`5,960,465 A
`5,964,842 A 10/1999 Packard
`5,968,149 A 10/1999 Jaquette et al.
`5,973,630 A 10/1999 Heath
`5,974,471 A 10/1999 Belt
`5,982,723 A 11/1999 Kamatani
`5,991,515 A 11/1999 Fall et al.
`5,996,033 A 11/1999 Chiu-Hao
`6,000,009 A 12/1999 Brady
`6,002,411 A 12/1999 Dye
`6,003,115 A 12/1999 Spear et al.
`6,011,901 A
`1/2000 Kirsten
`6,014,694 A
`1/2000 Aharoni et al.
`6,026,217 A
`2/2000 Adiletta
`6,028,725 A
`2/2000 Blumenau
`6,031,939 A
`2/2000 Gilbert et al.
`6,032,148 A
`2/2000 Wilkes
`6,061,398 A
`5/2000 Satoh et al.
`6,073,232 A
`6/2000 Kroeker et al.
`.
`6,075,470 A
`6/2000 Little et al.
`.
`6,094,634 A
`7/2000 Yahagi et al.
`.
`6,097,520 A
`8/2000 Kadnier
`6,104,389 A
`8/2000 Ando
`6,105,130 A
`8/2000 Wu et al.
`6,128,412 A 10/2000 Satoh
`6,141,053 A 10/2000 Saukkonen
`6,145,069 A 11/2000 Dye
`.
`.
`6,169,241 B1
`1/2001 Shimizu
`.
`.
`6,172,936 B1
`1/2001 Kitazaki
`6,173,381 B1
`1/2001 Dye
`6,182,125 B1
`1/2001 Borella et al.
`.
`6,192,082 B1
`2/2001 Moriarty et al.
`6,195,024 B1
`2/2001 Fallon
`6,226,667 B1
`5/2001 Matthews et al.
`6,226,740 B1
`5/2001 Iga
`
`8/2001 Mann
`6,272,627 B1
`8/2001 Aguilar et al.
`6,272,628 B1
`8/2001 Christensen
`6,282,641 B1
`10/2001 Fallon
`6,309,424 B1
`11/2001 Del Castillo et al.
`6,317,714 B1
`12/2001 Schaefer
`6,330,622 B1
`2/2002 Booth
`6,345,307 B1
`7/2002 Rhee
`6,421,387 B1
`8/2002 Kari
`6,434,168 B1
`8/2002 Esfahani et a1.
`6,434,695 B1
`8/2002 Blumenau
`6,442,659 B1
`9/2002 Toorians
`6,449,682 B1
`9/2002 Morein
`6,452,602 B1
`10/2002 Teoman et al.
`6,463,509 B1
`11/ 2002 Lipasti
`6,487,640 B1
`12/2002 Heath
`6,489,902 B1
`1/2003 Kobayashi
`6,513,113 B1
`3/2003 EaSWilf et 61
`6,529,633 B1
`3/2003 Stewart
`6,539,456 B1
`4/2003 Satoh
`6,542,644 B1
`7/2003 Kltade et a1~
`6,590,609 B1
`7/2003 Fallon
`6,601,104 B1
`6,604,158 B1* 8/2003 Fallon ....................... .. 710/65
`6,606,040 B1* 8/2003 Abdat ....................... .. 341/87
`
`8/2003 Zeineh
`6,606,413 B1
`8/2003 Wolfgang
`6,609,223 B1
`9/2003 Rail
`6,618,728 B1
`6,624,761 B1* 9/2003 Fallon ....................... .. 341/51
`6,661,839 B1
`12/2003 Ishida et al.
`6,704,840 B1
`3/2004 Nalawadi et al.
`6,711,709 B1* 3/2004 York ........................ .. 714/748
`6,745,282 B1
`6/2004 Okada
`6,748,457 B1
`6/2004 Fallon
`2001/0032128 A1 10/2001 Kepecs
`2002/0037035 A1
`3/2002 Singh
`2002/0104891 A1
`8/2002 Otto
`2002/0126755 A1
`9/2002 Li et al.
`2003/0034905 A1* 2/2003 Anton et al. ................ .. 341/51
`2003/0084238 A1
`5/2003 Okada et al.
`2003/0142874 A1
`7/2003 Schwartz
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`
`GB
`JP
`JP
`W0
`W0
`W0
`W0
`
`FOREIGN PATENT DOCUMENTS
`0164677
`12/1985
`0185098
`6/1986
`0283798
`9/1988
`0405572 A2
`1/1991
`0405572 A3
`3/1991
`0493130
`7/1992
`0587437
`3/1994
`0595406
`5/1994
`0718751 A2
`6/1996
`0718751 A3
`2/1997
`9188009
`7/1997
`
`2162025
`6051989
`11149376
`W0 9414273
`W0 9429652
`W0 9502873
`W0 9748212
`
`1/1986
`2/1994
`6/1999
`6/1994
`12/1994
`1/1995
`l2/l997
`
`Pen-Shu Yeh, The CCSDS Lossless Data Compression Recommen
`dation for Space Applications, Chapter 16, Lossless Compression
`Handbook, Elsevier Science (USA), 2003, pp. 311-326.
`Robert F. Rice, Some Practical Universal Noiseless Coding Tech
`niques , Jet Propulsion Laboratory, Pasadena, California, JPL Pub
`lication 79-22, Mar. 15, 1979.
`K. Murashita et al., High-Speed Statistical Compression using
`Self-organized Rules and Predetermined Code Tables, IEEE, 1996
`Data Compression, conference, no month.
`IBM, Fast Dos Soft Boot, Feb. 1, 1994, vol. 37, Issue 28, pp.
`185-186.
`J. Anderson et al. Codeo squeezes color teleconferencing through
`telephone lines, Electronics 1984, pp. 13-15, no month.
`Robert Rice, “Lossless Coding Standards For Space Data Systems”,
`IEEE 1058-6393/97, pp. 577-585, no month.
`Coene, W et al. “A Fast Route For Application of Rate-distortion
`Optimal Quantization in an MPEG Video Encoder” Proceedings of
`the International Conference on Image Processing, US., New York,
`IEEE, Sep. 16, 1996, pp. 825-828.
`“Operating System Platform Abstraction Method”, IBM Technical
`Disclosure Bulletin, Feb. 1995, vol. 38, Issue No. 2, pp. 343-344.
`
`* cited by examiner
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 003
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 1 0134
`
`US 7,161,506 B2
`
`INPUT DATA STREAM
`
`I
`
`2
`IDENTIFY INPUT DATA TYPE AND
`GENERATE DATA TYPE IDENTIFICATION /
`SIGNAL
`
`DATA TYPE l
`
`ID SIGNAL
`
`l
`
`COMPRESS DATA IN ACCORDANCE WITH _/3
`IDENTIFIED DATA TYPE
`
`I
`
`COMPRESSED DATA STREAM
`
`I
`
`5
`RETRIEVE DATA TYPE
`INFORMATION OF COMPRESSED /
`DATA STREAM
`
`I
`
`6/‘
`
`DECOMPRESS DATA IN ACCORDANCE _/6
`WITH IDENTIFIED DATA TYPE
`
`I
`
`FIG. 1
`PRIOR ART
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 004
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`43f02teehS
`
`US 7,161,506 B2
`
`Ks«\QQMQOOZN
`
`\\S_Enumwtm
`
`.KOHQEOmMQ
`
`ZOEmmmnzzOo
`
`uni
`
`ZOHmmmNEEOU
`
`02.48
`
`ZOwE/EEOO
`
`ZOrEEwaO
`\ZO_H<Z_§mewD
`
`E{mmfim«Q«6.
`
`Emmuam
`
`wmmkzaoo
`
`EmnEDm
`
`mMmFZDOO
`
`Emu.qu
`
`mmwkZDOO
`
`rmmmDOOZm
`
`mmMmDOOZm
`
`mmmmooozm
`
`Emumnm
`
`cmmHZDOO
`
`cwmmDOozw
`
`FDAZ.
`
`(ban.
`
`Ewan—3m
`
`<._.<D
`
`XOOIE
`
`amt/.500
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 005
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 3 0f 34
`
`US 7,161,506 B2
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`COUNT SIZE OF
`DATA BLOCK
`
`BUFFER DATA BLOCK "[304
`
`COMPRESS DATA
`BLOCK WITH
`ENABLED ENCODERS
`
`BUFFER ENCODED
`DATA BLOCK OUTPUT
`FROM EACH
`ENCODER
`
`V
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`V
`CALCULATE
`COMPRESSION
`RATIOS
`
`COMPARE
`COMPRESSION
`RATIOS WITH
`THRESHOLD LIMIT
`
`I
`A
`FIG. 3a
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 006
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 4 0f 34
`
`US 7,161,506 B2
`
`316
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`NO
`
`i
`YES
`V
`318
`APPEND NULL
`322
`sELECT ENCODED
`DATA BLOCK WITH / DESCRIPTOR TO /
`GREATEST
`UNENCODED INPUT
`COMPRESSION RATIO
`DATA BLOCK
`
`V
`APPEND
`CORRESPONDING J324
`DESCRIPTOR
`
`‘
`OUTPUT ENCQDED
`DATA BLOCK WITH V4525
`DESQRIPTQR
`
`TY
`OUTPUT UNENCODED
`DATA BLOCK WITH J 320
`NULL DESCRIPTOR
`
`MORE
`DATA BLOCKS IN INPUT <————-———-———
`STREAM?
`
`YES
`
`I
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`I
`B
`
`FIG. 3b
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 007
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`43f05teehS
`
`US 7,161,506 B2
`
`E.<0QMQOOZw
`
`\xSEvfikhm,
`
`10595.0me
`
`ZO_mmwmn:200
`
`mat.
`
`ZOEWMNEEOU
`
`OF<K
`
`ZOmEddEOO
`
`Emmuam
`
`_.MMFZDOO
`
`Em“..qu
`
`NmwFZDOO
`
`EmmmDm
`
`mmMHZDOU
`
`rmmwQOOZm
`
`mmmmooozm
`
`mmmmooozw
`
`Emuqu
`
`cmmFZDOO
`
`cmmwooozw
`
`ZOEhEOmmO
`\ZO_._.<Z=>_N_m._.mo
`
`(.36
`
`m0MMDOE
`
`tam—2
`
`ZOF<2_S_mm.—.m0
`
`mmooozw
`
`>._.3_m<m_mm0
`
`meFO/‘n.
`
`.EJQZ.
`
`<._.<O
`
`mmuubm
`
`<._.<D
`
`KOOAm
`
`«EPZDOO
`
`33mme
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 008
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 6 6f 34
`
`US 7,161,506 B2
`
`RECEIvE INITIAL _/500
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`v
`COUNT SIZE OF _/5O2
`DATA BLOCK
`
`5 4
`BUFFER DATA BLOCK -/ 0
`
`TV
`COMPRESS DATA I506
`BLOCK WITH
`ENABLED ENCODERS
`
`v
`508
`APPEND CORRESPONDING
`DESIRABILITY FACTORS TO I
`ENCODED DATA BLOCKS
`
`V
`510
`BUFFER ENCODED DATA
`BLOCK OUTPUT J
`FROM EACH ENCODER
`
`V
`COUNT SIZE OF
`ENCODED DATA _/512
`BLOCKS
`
`V
`CALCULATE
`COMPRESSION _/514
`RATIOS
`
`516
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD -/
`LIMIT
`
`1
`A
`FIG. 5a
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 009
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 7 0f 34
`
`US 7,161,506 B2
`
`518
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`NO
`
`YES
`
`i
`
`i
`520
`APPEND NULL
`CALCULATE FIGURE OF
`MERIT FOR EACH ENCODED j524 DESCRIPTOR TO /
`DATA BLOCK WHICH EXCEED
`UNENCODED INPUT
`THRESHOLD
`DATA BLOCK
`
`526
`SELECT ENCODED DATA
`BLOCK WITH GREATEST 1
`FIGURE OF MERIT
`
`V
`APPEND
`CORRESPONDING ¢528
`DESCRIPTOR
`
`V
`OUTPUT UNENCODED 522
`DATA BLOCK WITH 1
`NULL DESCRIPTOR
`
`\'
`OUTPUT ENCODED
`DATA BLOCK WITH ¢530
`DESCRIPTOR
`
`532
`
`MORE
`DATA BLOCKS IN
`INPUT STREAM’?
`
`YES
`Y
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`RECEIVE NEXT DATA I534
`BLOCK FROM INPUT
`STREAM
`
`B FIG. 5b
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 010
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`teehS
`
`43f000
`
`US 7,161,506 B2
`
`«Q.{QQWQOUZM
`
`\\SEqmmhm
`
`EOHQEUMNQ
`
`ZO_wwmmn=>_Oo
`
`mnCL.
`
`ZO_mwwmn_EOO
`
`Orr/xx
`
`ZOwE/EEOO
`
`
`
`Rm".qu
`
`vmwFZDOO
`
`Emu..qu
`
`m15.2300
`
`EmmmDm
`
`mmmHZDOU
`
`Em“.qu
`
`:mwFZDOO
`
`
`
`rmmmOOOZm
`
`Nmmmooozm
`
`mmKwQOOZm
`
`.
`
`cmmmooozm
`
`om
`
`ZO_._.n=N_omwO
`\ZO_._.<Z=2mm._.mo
`
`qR<Q
`
`:57:
`
`<,_.<D
`
`mmmusm
`
`<F<Q
`
`XOOAm
`
`mmFZDOO
`
`Evflkfiw
`
`mwSE.
`
`om
`
`-mmmj
`
`
`
`NEE.thamlm
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 011
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 9 0f 34
`
`US 7,161,506 B2
`
`INPUT INITIAL
`70O\ DATA BLOCK FROM
`INPUT DATA STREAM
`
`70
`
`v
`
`B ’
`
`COUNT SIZE OF
`DATA BLOCK
`
`710
`
`‘I
`
`704\ BUFFER DATA BLOCK
`
`ENCODING
`COMPLETE?
`
`‘I
`
`706x INITIALIZE TIMER
`
`\
`
`BEGIN
`708\ COMPRESSING
`DATA BLOCK WITH
`ENCODERS
`
`YES
`
`i (714
`
`BUFFER
`ENCODED DATA
`BLOCK OUTPUT
`FROM EACH
`ENCODER
`
`v [716
`STOP
`ENCODING
`PROCESS
`
`f718
`,
`BUFFER ENCODED
`DATA BLOCK FOR EACH
`ENCODER THAT
`COMPLETED ENCODING
`PROCESS
`WITHIN TIME LIMIT
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`1720
`
`CALCULATE
`COMPRESSION
`RATIOS
`
`V
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD 1724
`LIMIT
`
`I
`A
`
`FIG. 7a
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 012
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 10 0f 34
`
`US 7,161,506 B2
`
`726
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`NO
`
`1
`YES
`'4'
`728
`APPEND NULL
`732
`SELECT ENCODED
`DATA BLOCK WITH / DEscRIPTOR TO /
`GREATEST
`UNENCODED INPUT
`COMPRESSION RATIO
`DATA BLOCK
`
`V
`APPEND
`CORRESPONDING ‘r734
`DESCRIPTOR
`
`‘
`OUTPUT ENOODED
`DATA BLOCK WITH E736
`DESCRIPTOR
`
`\
`730
`OUTPUT UNENCODED
`DATA BLOCK WITH ./
`NULL DESCRIPTOR
`
`MORE
`DATA BLOCKS IN INPUT <———————
`STREAM?
`
`YES
`
`I
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`I
`B
`
`FIG. 7b
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 013
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`43f011teehS
`
`US 7,161,506 B2
`
`(.35QMQOOZM
`
`\\SEq‘mmkm
`
`KOkntmowmQ
`
`ZO_wwwmu_200
`
`mat.
`
`ZOEmmMaEOU
`
`9.2m
`
`ZOwEddEOO
`
`Emu.qu
`
`_,MNFZDOO
`
`Emmqu
`
`NMMHZDOO
`
`Emuunm
`
`mmmHZDOO
`
`Pmmmooozm
`
`mmmmooozm
`
`
`
`mm.mmooozm
`
`EwnEDm
`
`cmmeDOO
`
`cwmeOOZm
`
`ZOFm—mommo
`\ZO_.~.<z=2mw._.mo
`
`Simmkm«H<Q
`
`uOMEDQE
`
`tme
`
`ZO_._.<Z§_mm._.mD
`
`mwooozm
`
`>._._.:m<w:wwD
`
`meHO<u
`
`FDQZ
`
`<._.<O
`
`awn.qu
`
`
`
`<._.<OPDQZ
`
`$00.5
`
`EOmwwOOmn—
`
`mmHZDOO
`
`-Kmmb
`
`
`
`NSF»QMEBMQm,
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 014
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`43f021tee.hS
`
`US 7,161,506 B2
`
`ZO_wwmmn=>.Oo
`
`mat
`
`ZOFn:N_Ommo
`
`KN<QQMQOUZM
`
`\xSS‘c‘mmbm.
`
`EOBQEOMMQ
`
`mmDOozm
`
`>._._u=m<m_mm0
`
`wm0h0<u
`
`ZOmE<QEOO\ZOF<Z§MNHMQ
`
`35mph.m«R«\Q
`
`ZO_wmmmn=200
`
`O_._.<m
`
`".0meGE
`
`tam—2
`
`ZOF<Z§Mmeo
`
`c.E9m
`
`F31Z.
`
`<H<O
`
`mm“.qu
`
`<F<D
`
`XOOAm
`
`mthDOU
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 015
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 13 0f 34
`
`US 7,161,506 B2
`
`100
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`102\.
`
`B ’
`
`"
`COUNT SIZE OF
`DATA BLOCK
`
`I,
`
`104T”
`
`BUFFER DATA
`BLOCK
`
`v
`
`1D5\ INITIALIZE TIMER
`
`‘I
`APPLY INPUT DATA
`BLOCK TO FIRST
`108
`\ ENCODING STAGE
`IN CASCADED
`ENCODER PATHS
`
`\
`
`A’ TIME EXP'RED?
`
`APPLY OUTPUT
`OF COMPLETED
`ENCODING
`STAGE TO NExT
`ENCODING
`STAGE IN
`CASCADE PATH
`
`BUFFER
`ENCODED DATA
`BLOCK OUTPUT
`FROM
`COMPLETED
`ENCODING
`STAGE
`
`1 18
`r
`STOP ENCODING ‘
`PROCESS
`A
`
`(120
`l
`SELECT BUFFERED OUTPUT OF LAST
`ENCODING STAGE IN ENCODER
`CASCADE THAT COMPLETED ENCODING
`PROCESS WITHIN TIME LIMIT
`
`I
`COUNT SIzE OF
`ENCODED DATA r[122
`BLOCKS
`I
`CALCULATE
`COMPRESSION _/124
`RATIOS
`I
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD 1126
`LIMIT
`
`FIG. 103
`
`I
`A
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 016
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 14 0f 34
`
`US 7,161,506 B2
`
`128
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`YES
`
`III
`CALCULATE FIGURE OF
`134\ MERIT FOR EACH ENCODED
`DATA BLOCK WHICH ExcEED
`THRESHOLD
`
`SELECT ENCODED DATA
`136
`\ BLOCK WITH GREATEST
`FIGURE OF MERIT
`
`NO
`
`i
`
`APPEND NULL
`DESCRIPTOR TO
`UNENCODED INPUT
`DATA BLOCK
`
`130
`
`‘L
`APPEND
`138w CORRESPONDING
`DEscRIPToR
`
`‘V
`OUTPUT UNENCODED 132
`DATA BLOCK WITH 1
`NULL DESCRIPTOR
`
`OUTPUT ENCODED
`14%» DATA BLOCK WITH
`DEscRIPTOR
`
`DATA BLOCKS IN
`INPUT STREAM?
`
`146
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`YES
`V
`I144
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`I
`B FIG. 10b
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 017
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 15 0f 34
`
`US 7,161,506 B2
`
`E. <Q hDnCDO
`
`\ 8 S \ \ 8:
`
`No:
`
`
`
`
`<20 5050 A 8 580mm 1 moEEowmo <20 SQ; SEEM E3
`
`5&3 \ . zopoébm A mwumnm V606 m
`
`, 8 mwaoown
`
`5 580mm
`
`moEEuwmq
`
`5 $0086
`
`\ 3
`2,
`
`v r GE
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 018
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 16 0f 34
`
`US 7,161,506 B2
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`I
`
`BUFFER DATA BLOCK
`v
`
`l
`
`EXTRACT DATA
`COMPRESSION TYPE
`f 1204
`DESCRIPTOR
`
`IS DATA
`COMPRESSION
`
`1 206
`
`YES
`
`NO
`
`1210
`SELECT DECODER{S) J
`CORRESPONDING TO
`DESCRIPTOR
`l
`DECODE DATA BLOCK USING _f1212
`SELECTED DECODER(S)
`
`Ir
`
`OUTPUT DECODED
`DATA BLOCK
`
`OUTPUT
`UNDECODED
`DATA BLOCK
`
`(1220
`RECEIVE NEXT
`DATA BLOCK IN
`INPUT STREAM
`
`YES
`
`MORE DATA
`BLOCKS IN INPUT
`STREAM?
`
`TERMINATE
`DECODING PROCESS
`
`1218
`
`FIG. 12
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 019
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 17 0f 34
`
`US 7,161,506 B2
`
`
`
`
`
`wkmuoocm Emvcmawo E980
`
`
`
`< All mabououcm 1
`
`55805
`
`
`
`mohmuoucm (0N2.
`
`mw> E950
`
`Emucwqmo
`
`
`
`Emncmqwus E950 02 Eng 1
`
`awuoucm cgEmoomm
`
`
`
`
`
`5 Saw
`
`
`m All]: 3 380cm BEES
`a 82
`
`E5255 1 w
`
`
`
`. cozEmooom
`
`. I 8 EEQEQQZ
`. 6 5w:
`
`<2 mmzwi
`
`92. w
`
`ON 2 w w
`
`ES 59.; xogm Ema E85
`
`
`
`
`hmtsm LQEJOO Lilli
`
`
`Ema
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 020
`
`

`

`Jan. 9, 2007
`
`43f0001teehS
`
`US 7,161,506 B2
`
`
`
`Batomeucmaq<m5E§mQ
`
`56:83Augsumm5m9:
`
`2me
`
`m2mmDOE
`
`rmemucaootwtzm
`
`mmBwucaootmtsm
`
`mm98::00:wt3m
`
`cmBmucsootwtzm
`
`
`
`8685500co_www.ano
`
`US. Patent
`
`5:39mm
`
`nouoocm
`
`EEmanoEtzm
`
`Nombyczoogtzm
`
`8emEzoo\._mt:m
`
`EDwhmucaootmtsm
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 021
`
`

`

`Receive Initial
`Data Block From
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`Buffer Data Block
`
`Recognize Data
`Stream Content
`7
`
`US. Patent
`
`Jan. 9, 2007
`
`Sheet 19 0f 34
`
`US 7,161,506 B2
`
`FIGURE 14A
`
`Apply Content
`Dependent Data
`Recognition
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 022
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`Sheet 20 0f 34
`
`US 7,161,506 B2
`
`Compress Data
`Block with
`
`Enabled Content
`
`Independent
`Encoders
`
`Buffer Encoded
`
`Data Block Output
`From Each
`Encoder
`
`HGURE14B
`
`Count Size of
`Encoded Data
`Blocks
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression
`Ratios with
`
`Threshold Limit
`
`D
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 023
`
`

`

`[LS.Ikuent
`
`JML%ZMW
`
`$wq21m34
`
`US7J61506B2
`
`Independent Threshold
`
`Compression Ratio
`of at Least One Encoded Data
`Block Greater Than Content
`
`HGURE14C
`
`Select Encoded
`Data Block with
`Greatest
`Compression Ratio
`
`Append Null
`Descrlp’tor t0
`Unencoded Input
`Data BIOCk
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`Receive Next
`Data Block From
`Input Stream
`
`More Data
`Blocks in Input
`Stream
`?
`
`Terminate
`Data Compression
`Process
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 024
`
`

`

`[LS.Ikuent
`
`JML%ZMW
`
`$wq22m34
`
`US7J61506B2
`
`Select Recognized
`Data Type/File or Block
`in List or Algorithm
`
`Select Content
`
`Dependent
`Algorithm(s)
`
`Compress Data Block
`1438 ~ with Enabled Content
`
`Dependent Encoder(s)
`
`HGURE14D
`
`Compression
`Ratio of at Least One
`Encoded Data Block
`Greater Than
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`Count Size of Data
`Blocks
`
`Calculate
`
`Compression Ratio
`
`Content Dependent
`Threshold
`’?
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 025
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`43f032teehS
`
`US 7,161,506 B2
`
`
`
`288$EmucmumoE950
`
`5539$
`
`NDLmuoocm
`
`noLmnoucm
`
`EDLmUOOCm
`
`
`
`Ema
`
`EmEoo
`
`Emucmqmo
`
`Ema
`
`cogcmoomm
`
`2:528
`
`coEcmoomm
`
`5Es:
`
`@558?
`
`
`
`<9,mmDOE
`
`EmaSac.
`
`Lmtzm
`
`xoo_mEND
`
`5:500
`
`Emotm
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 026
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`43f042teehS
`
`US 7,161,506 B2
`
`umuoocm
`
`53>Ema
`
`Batu.me
`
`5335800
`
`wQ>H
`
`85:0me
`
`ozmmco_mwmano
`
`
`
`Eccmmzf.m>on<
`
`E980
`
`Emucmqmo
`
`$633.50
`
`29395.
`
`82.
`
`moEmEsootmtzm
`
`moemycsootmtzm
`
`EDEQEoOtmtzm
`
`
`
`2053.5...32mm03mmc939.:50
`
`mc_E§mQ
`
`coammano
`
`Eocwefi.\ozmm
`
`FmemycsoOEmtsm
`
`mmemacsootwtzm
`
`mmemacsooumtsm
`
`FmLouoocm
`
`mmLmuoucm
`
`mm.885.
`
`
`
`mm;mmDOE
`
`EEmyczootmtam
`
`
`
`
`
`
`
`mhwnoucmEwucmamngEmEoo
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 027
`
`

`

`Receive Initial
`Data Block From
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`Buffer Data Block
`
`Recognize Data
`Stream Content
`?
`
`US. Patent
`
`Jan. 9, 2007
`
`Sheet 25 0f 34
`
`US 7,161,506 B2
`
`FIGURE 16A
`
`Apply Content
`Dependent Data
`Recognition
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 028
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`Sheet 26 0f 34
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`Buffer Encoded Data
`
`Block Output From
`Each Encoder
`
`US 7,161,506 B2
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`Count Size of
`Encoded Data Blocks
`
`Calculate
`
`Compression
`Ratio
`
`D
`
`FlGURE 168
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 029
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`Sheet 27 0f 34
`
`US 7,161,506 B2
`
`Compression Ratio
`of at Least One Encoded Data
`Block Greater Than Content
`
`Independent Threshold
`
`Select Encoded
`Data Block with
`Greatest
`Compression Ratio
`
`FIGURE 160
`
`Append NU“
`Descriptor to
`Unencoded Input
`Data BIOCk
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`Receive Next
`
`Data Block From
`Input Stream
`
`More Data
`
`Blocks in Input
`Stream
`?
`
`Terminate
`
`Data Compression
`Process
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 030
`
`

`

`[LS.Ikuent
`
`JML%ZMW
`
`Swm28M34
`
`US7J61506B2
`
`Select Recognized
`Data TypelFile or Block
`in List or Algorithm
`
`Select Content
`
`Dependent
`Algorithm(s)
`
`Compress Data Block
`1638 ~ with Enabled Content
`
`Dependent Encoder(s)
`
`HGURE16D
`
`Compression
`Ratio of at Least
`One Encoded Data
`Block Greater Than
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`Count Size of Data
`Blocks
`
`Calculate
`
`Compression Ratio
`
`Content Dependent
`Threshold
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 031
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`43f092teehS
`
`US 7,161,506 B2
`
`
`
`
`
`emuoocmEwucmamoEmEoo
`
`605Ema
`
`5$805
`
`No5805
`
`noquoocm
`
`EDLmuoocm
`
`
`
`
`
`93505E28832EmEoo
`
`E$805
`
`mm6305
`
`8:9558
`
`ucm:oEcmoumm
`
`
`
`SEE?cosmefim
`
`3332:03.0
`
`w
`
`or:
`
`
`
`<5,mmDOE
`
`E980
`
`\vacmqmo
`
`“coucwamug
`
`9mm
`
`coacmoomm
`
`Ema:55
`
`.mtnm
`
`$2500
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 032
`
`

`

`Jan. 9, 2007
`
`43f003teehS
`
`US 7,161,506 B2
`
`5:3flag
`
`
`
`Satome:o_mmmano
`
`RE.
`
`83880
`
`mc_E._2mn_
`
`cofimmEEoo
`
`623%a25m
`
`mtNEDOE
`
`US. Patent
`
`vmuoocmE0BmEzootmtsm
`
`EEmgczootmtzm
`
`NoemEzoOEmtsm
`
`noEmEzoOtwtzm
`
`Fmw§c300totsm
`
`mmemucaoogtnm
`
`
`
`mm.ewucsoototsm
`
`cwmkwucsooEtzm
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 033
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`Sheet 31 0f 34
`
`Receive Initial
`Data Block From
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`Buffer Data Block
`
`US 7,161,506 B2
`
`Apply Content
`Dependent I
`Independent Data
`Recognition
`
`Recognize Data
`Stream Content
`?
`
`FIGURE 18A
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 034
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`Sheet 32 0f 34
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`Buffer Encoded Data
`
`Block Output From
`Each Encoder
`
`Count Size of
`Encoded Data Blocks
`
`Estimate Optimum
`Encoder(s) From
`Estimation Algorithms
`
`US 7,161,506 B2
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`D
`
`FIGURE 188
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 035
`
`

`

`US. Patent
`
`Jan. 9, 2007
`
`Sheet 33 0f 34
`
`US 7,161,506 B2
`
`ndependent Threshol
`
`Compression Ratio
`of at Least One Encoded Data
`Block Greater Than Content
`
`FIGURE 18C
`
`Select Encoded
`Data Block with
`Greatest
`Compression Ratio
`
`Appefild NU”
`Descnptor to
`Unencoded Input
`Data BIOCk
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`Output Encoded
`Data Btock with
`
`Descriptor
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`Receive Next
`
`Data Block From
`Input Stream
`
`More Data
`
`Blocks in Input
`Stream
`?
`
`Terminate
`
`Data Compression
`Process
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 036
`
`

`

`[LS.Ikuent
`
`JML%ZMW
`
`$wm34m34
`
`US7J61506B2
`
`Select Recognized
`Data Type/File or Block
`in List or Algorithm
`
`Select or Estimate
`
`Content Dependent
`Algorithm(s)
`
`Compress Data Block
`1842 ~ with Enabled Content
`
`Dependent Encoder(s)
`
`HGURE18D
`
`Compression
`Ratio of at Least
`One Encoded Data
`Block Greater Than
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`Count Size of Data
`Blocks
`
`Calculate
`
`Compression Ratio
`
`Content Dependent
`Threshold
`
`Veritas Techs. LLC
`Exhibit 1017
`Page 037
`
`

`

`US 7,161,506 B2
`
`1
`SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`DEPENDENT DATA COMPRESSION
`
`
`CROSS—REFERENCE TO RELATED
`APPLICATIONS
`
`
`
`2
`Thus, one obvious advantage of lossy data compression is
`hat the compression ratios can be larger than the entropy
`imit, all at the expense of information content. Many lossy
`data compression techniques seek to exploit various traits
`within the human senses to eliminate otherwise iinpercep—
`ible data. For example, lossy data compression of visual
`imagery might seek to delete information content in excess
`of the display resolution or contrast ratio.
`On the other hand, lossless data compression techniques
`flrovide an exact representation of the original uncom-
`3ressed data. Simply stated, the decoded (or reconstructed)
`data is identical to the original unencoded/uncompressed
`data. Lossless data compression is also known as reversible
`or noiseless compression. Thus, lossless data compression
`ias, as its current limit, a minimum representation defined
`3y the entropy of a given data set.
`There are various problems associated with the use of
`ossless compression techniques. One fundamental problem
`encountered with most lossless data compression techniques
`are their content sensitive behavior. This is often referred to
`as data dependency. Data dependency implies that the corri-
`oression ratio achieved is highly contingent upon the content
`
`0 the data being compressed. For example, database files
`0 en have large unused fields and high data redundancies,
`
`o ering the opportunity to losslessly compress data at ratios
`0 5 to 1 or more. In contrast, concise software programs
`have little to no data redundancy and, typically, will not
`losslessly compress better than 2 to 1.
`Another problem with lossless compression is that there
`are significant variations in the compression ratio obtained
`when using a single lossless data compression technique for
`data streams having different data content and data size. This
`process is known as natural variation.
`A further problem is that negative compression may occur
`when certain data compression techniques act upon many
`types of highly compressed data. Highly compressed data
`appears random and many data compression techniques will
`substantially expand, not compress this type of data.
`For a given application, there are many factors that govem
`the applicability of various data compression techniques.
`These factors include compression ratio, encoding and
`decoding processing requirements, encoding and decoding
`time delays, compatibility with existing standards, and
`implementation complexity and cost, along with the adapt-
`ability and robustness to variations in input data. A direct
`relationship exists in the current art between compression
`ratio and the amount and complexity of processing required.
`One of the limiting factors in most existing prior art lossless
`data compression techniques is the rate at which the encod—
`
`ing and decoding processes are performed. Hardware and
`
`
`software implementation tradeo s are often dictated by
`encoder and decoder complexity along with cost.
`Another problem associated with lossless compression
`methods is determining the optimal compression technique
`for a given set of input data and intended application. To
`combat this problem, there are many conventional content
`dependent techniques that may be utilized. For instance, file
`type descriptors are typically appended to file names to
`describe the application programs that normally act upon the
`data contained within the file. In this manner data types, data
`structures, and formats within a given file may be ascer-
`tained. Fundamental limitations with this content dependent
`technique include:
`(1) the extremely large number of application programs,
`some of which do not possess published or documented file
`formats, data structures, or data type descriptors;
`
`
`
`
`
`
`
`This a