(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
`
`Page 1
`
`

`

`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.
`
`Page 2
`
`

`

`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
`
`Page 3
`
`

`

`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
`
`Page 4
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet2 of34
`
`US 7,161,506 B2
`
`Ewmmnm
`
`camt/500
`
`cmmmDOozw
`
`E.{QQMQOUZN
`
`\\S_31“]..th
`
`KOklEOmMQ
`
`Emuuam
`
`rmmFZDOO
`
`Emuubm
`
`mmmHZDOO
`
`rmmmooozm
`
`mmmmDOOZm
`
`3‘(mmkm«R«G
`
`
`
`ZO_wmmmn.§ODZO_mmmmn=200F3QZ.<F<D
`
`ZOPQEwaOmmwkZDOOEmulemmHZDOO
`
`
`
`mat\ZOPMiHQMmeOEmmnsmmmmwQOOZw<F<DXOOJm
`zomEEEOO..
`
`
`N.OE
`
`Page 5
`
`Page 5
`
`
`
`
`
`
`
`
`
`

`

`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
`
`Page 6
`
`

`

`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
`
`Page 7
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet5 0f34
`
`US 7,161,506 B2
`
`E«Qomqoozm
`
`moEEomeNmmfizaoo§:EgmEmfiammmmmooozm
`
`EmmmDm
`
`_‘mthDOO
`
`PM«@000me
`
`
`
`S>xmmkw«Red
`
`ZOmE/EEOO
`
`
`20—wmwmm200ZO_wmmmn:>_OOb.52—
`ZOChEOmMOmmwFZDOOmmuEDm
`
`
`
`uni\ZO_FM~_/~.__.QmwhmoEmmuammmmMDOOZw<F<D
`cmmmooozm
`
`Emuqu
`
`cKMFZDOO
`
`ow
`
`
`
`ZOF<Z_S_mm._.MQmmOFO’qm
`
`
`
`m0MMDOEmmmoozw
`
`
`
`.5me>t‘:m<m_wm0
`
`0von
`
`ON
`
`<._.<D
`
`XOOAm
`
`KMFZDOO
`
`Page 8
`
`Page 8
`
`
`
`
`
`
`
`
`

`

`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
`
`Page 9
`
`

`

`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
`
`Page 10
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet8 0f34
`
`US 7,161,506 B2
`
`
`
`«RedQWQOOZM
`
`\xSEq‘mwfimEwnfiam
`
`KOHQEQMMQNEMFZDOO
`
`20—wwmmn2200
`
`mat.
`
`ZOEmmeEOO
`
`0F<m
`
`ZOFEKOmwO
`\ZO_._.<Z_§mm._.mo
`
`ZOwE<n=200
`
`EmmmDm
`
`mKMFZDOO
`
`EwmmDm
`
`cme2300
`
`0.0E
`
`NmmeOOZm
`
`mmmmooozm
`
`.
`
`cmmmooozm
`
`FDQZ
`
`<._.<D
`
`mmumDm
`
`<F<Q
`
`x0015
`
`mmFZDOU
`
`om
`
`-mwmj
`
`
`
`NEE.thamlm
`
`Page 11
`
`BMuEDm
`
`_.mmFZDOO
`
`rmmwOOOZm
`
`V<<mmhmE.«G
`
`Page 11
`
`
`
`
`
`
`
`
`
`
`
`

`

`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
`
`Page 12
`
`

`

`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
`
`Page 13
`
`

`

`U.S. Patent
`
`hS
`
`f0
`
`S
`
`61,
`
`2R"M
`
`78
`
`M,wGE
`
`«EB3805
`
`,zo_mmmmms_oo5%:9.zo_mwmmas_oo<205%n«EnigmaNmmhzaoo
`nJaEEEEwEmulammmmmooozm
`0.21Rmmuam<20x005Romwmoommmmg
`
`
`
`
`\zoEszEmommmkzaoommmmooozmmmutzm2055200.«9238mzQEEommo
`
`
`ow9
`
`\mwmuam
`
`vmeZDOO
`
`Pwmmooozw
`
`§<MKBW<K<Q
`
`ucmmkzsoomEmtamcmmmooozm
`
`
`U20.22.25th305$
`tam:>t45<mamoom
`
`
`
`
`
`noMEREmmooozm
`
`3-mmm:
`
`438$2?$58&6QO
`
`Page14
`
`Page 14
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet12 0f34
`
`US 7,161,506 B2
`
`:N05...
`
`
`
`c;0.5...Simwtb(.35
`
`F31Z_
`
`<F<D
`
`ON
`
`<F<D
`
`XOOAm
`
`mwFZDOO
`
`ZO_mmmMn:200
`
`O_._.<m
`
`ZOmE<QEOO\ZO_._.<Z_§mw._.mo
`
`tam—>—
`
`ZO_F<z=2mw._.mo
`
`ZO_wmmMn=>.OO
`
`mm:
`
`9m05...
`
`C.E0\m...
`
`mOmMDwE
`
` mmnfiDm
`
`
`ZOPQEmeomekO/E
`
`ow
`
`«R<QQMQOOZM
`
`\xsSzxmwfim
`
`EOBQEOWMQ
`
`a.07...
`
`Page 15
`
`«@000me
`
`Dov00m
`
`
`ESE..HEEqmtamqm
`
`-KMmD
`
`>u.._.=m<m_wm0cm
`
`Page 15
`
`
`
`
`

`

`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
`
`Page 16
`
`

`

`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
`
`Page 17
`
`

`

`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
`
`Page 18
`
`

`

`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
`
`Page 19
`
`

`

`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
`
`Page 20
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet18 of34
`
`US 7,161,506 B2
`
`nmuoocm
`
`
`55:38868558Sawmasoo
`5?98232mséemo
`
`0Q>HOSNI
`
`
`
`56.5me895chE
`
`EDw..9c:00>.wt3m
`
`MDmLmHCDOOEmtSm
`
`v0whmeJOOtmtDm
`
`NDmgmHCDOOtmtDm
`
`)(ommr
`
`Em§a300tmt§
`
`mmmgmwcsootmtsm
`
`mmmhwaJOOtmtSm
`
`CmmLmEDOOtthm
`
`
`
`mmrmEDOE
`
`Page 21
`
`Page 21
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 19 0f 34
`
`US 7,161,506 B2
`
`
`
`Receive Initial
`Data Block From
`
`
`~ 1400
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`N 1402
`
`
`
`
`
`
`Buffer Data Block ~1404
`
`
`Apply Content
`Dependent Data
`Recognition
`
`
`
`~1406
`
`Recognize Data
`Stream Content
`
`
`
`?
`
`No—> B
`
`FIGURE 14A
`
`Page 22
`
`Page 22
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 20 of 34
`
`US 7,161,506 B2
`
`
`
` Compress Data
`
` ~141O
`
`independent
`
`
`Encoders
`
`
`Enabled Content
`
`Block with
`
`
`
`
`
`Buffer Encoded
`Data Block Output
`
`~1412
`From Each
`
`
`
`Encoder
`
`
`
`
`
`
`
`Count Size of
`~1414
`Encoded Data
`
`
`Blocks
`
` Calculate
`
`~1416
`Compression
`
`Ratio
`
`Page 23
`
`
`Compare
`Compression
`
`
`Ratios with
`
`
`
`Threshold Limit
`
` D
`
`FIGURE 148
`
`Page 23
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 21 0f 34
`
`US 7,161,506 B2
`
`
`
`Compression Ratio
`
`of at Least One Encoded Data
`Block Greater Than Content
`
`
`
`
`
`Independent Threshold
`1420 ~
`
`
`
`
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`Output Unencoded
`Data Block with
`
`
`
`
`Null Descriptor
`
`
`
`
`
`Append Null
`Select Encoded
`Data Block with
`Descriptor to
`
`
`
`Greatest
`Unencoded Input
`
`Data Block
` 1422 ~
`Compression Ratio
`
`
`
`Append
`Corresponding
`1424 ~
`
`Encoding
`Descriptor
`
`
`
`
`
`
`
`
`Receive Next
`
`More Data
`
`Terminate
`
`
`
`Data Block From
`Blocks in Input
`
`
`Data Compression
`
`Stream
`Process
`
`
`?
`
`
`Input Stream
`
`
`
`Yes
`
`1430
`
`FIGURE 140
`
`Page 24
`
`Page 24
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 22 0f 34
`
`US 7,161,506 B2
`
`Select Recognized
`1434~ Data Type/File or Block
`in List or Algorithm
`
`Algorithm(s)
`
`Select Content
`
`1436 ~
`
`Dependent
`
`Compress Data Block
`1438 ~ with Enabled Content
`
`
`Dependent Encoder(s)
`
`
`1440 ~
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`No—> F
`
`
`Compression
`Ratio of at Least One
`
`Encoded Data Block
`
`
`
`
`
`
`1442 ~ Count Size of Data
`Blocks
`
`Calculate
`1444 ~ Compression Ratio
`
`
`
`Greater Than
`
`Content Dependent
`Threshold
`?
`
`
`
`~1448
`
`Yes
`
`+ E
`
`FIGURE 14D
`
`Page 25
`
`Page 25
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet23 of34
`
`US 7,161,506 B2
`
`coEcmoomm
`
`2&6qu
`
`cozEmoomm
`
`5Eu:
`
`@555?
`
`owmw
`
`<mrm130E
`
`
`
`$885E3580E950
`
`MDLGUOUCm
`
`5Lmnoocm
`
`
`
`NDLmUoocm\(Ova
`
`ED$805985:35:500
`
`
`
`EmucwamoEmaSac.xoo_mSam88%
`
`6280$3
`
`Page 26
`
`Page 26
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 24 0f 34
`
`US 7,161,506 B2
`
`umuoocm
`
`53>Ema
`
`53:0me
`
`
`
`563.580063530
`83.scammaeoomom§caoo\.mt:m
`
`
`
`
`
`83:8829595.
`
`62.
`
`EDwLmuCDOOtthm
`
`
`
`
`
`29395.32mm03mmCosme.:80
`
`05mmco_mmm.ano
`
`20595.m>on<E980moBmycsootmtam2on?
`
`
`
`
`
`r0mgmuCDOOtmtbm
`
`_‘
`
`memucsootmtsm
`
`_,
`
`
`
`
`
`mhmnoucmEmucmamugEmEoo
`
`mLmuoocm
`
`8385800
`
`32:28
`
`mm:meOE EocweE.\ozmm
`mmmauczootmtsmmm508cm
`mmemuczootwtzmmmLmuoocm
`
`Page 27
`
`Page 27
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 25 of 34
`
`US 7,161,506 B2
`
`Receive Initial
`
`
`
`
`
`Data Block From
`
`~1600
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`N 1602
`
`Buffer Data Block ~1604
`
`
`
`
`
`
`
`
`Apply Content
`Dependent Data
`Recognition
`
`
`
`~1606
`
`
`
`Recognize Data
`Stream Content
`?
`
`No+ B
`
`YES
`vi
`
`C
`
`FIGURE 16A
`
`Page 28
`
`Page 28
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 26 of 34
`
`US 7,161,506 B2
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`Buffer Encoded Data
`
`Block Output From
`Each Encoder
`
`
`
`Count Size of
`
`Encoded Data Blocks
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`D
`
`FlGURE 1GB
`
`Page 29
`
`Page 29
`
`

`

`U.S. 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
`
`
`
`
`
`Append Null
`
`Select Encoded
`Descriptor to
`Data Block with
`
`
`
`Unencoded Input
`Greatest
`
`
`Data Block
`
`
`
`Compression Ratio
`
`1624 ~
`
`Output Unencoded
`Data Block with
`
`
`
`Append
`
`Corresponding
`
`Encoding
`Descriptor
`
`
`
`
`
`Output Encoded
`Data Block with
`
`
`Null Descriptor
`
`
`
`Descriptor
`
`
`
`
`
`
`
`Receive Next
`More Data
`Terminate
`
`
`Data Block From ,
`Blocks in Input
`
`
`Data Compression
`
`Process
`Stream
`
`
`?
`
`
`
`Input Stream
`
`
`
`Yes
`
`1630
`
`FIGURE 160
`
`Page 30
`
`Page 30
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 28 of 34
`
`US 7,161,506 B2
`
`Select Recognized
`1634~ Data Type/File or Block
`in List or Algorithm
`
`Algorithm(s)
`
`Select Content
`
`1636 ~
`
`Dependent
`
`Compress Data Block
`1638 ~ with Enabled Content
`
`
`
`
`Dependent Encoder(s)
`
`1640 ~
`
`1642 N
`
`Buffer Encoded Data
`
`Block From Each
`Encoder
`
`Blocks
`
`Count Size of Data
`
`1644 ~
`
`Compression Ratio
`
`Calculate
`
`
`
`
`Compression
`Ratio of at Least
`
`
`One Encoded Data
`Block Greater Than
`
`
`
`
`
`Content Dependent
`Threshold
`
`FIGURE 16D
`
`Nov B
`
`Page 31
`
`Page 31
`
`

`

`U.S. Patent
`
`Jan.9,2007
`
`Sheet29 of34
`
`US 7,161,506 B2
`
`_‘
`
`mLmvoocm
`
`
`
`8:.QEES
`
`vancozEmoomm
`
`
`
`Eczema8353
`
`$332563Lo
`
`or:w
`
`
`
`<5.mmDOE
`
`
`
`emuoocmEmucmamngEmEoocoacmoomm
`
`
`
`
`
`
`
`$385#5288E980
`
`m0gmboocm
`
`E5805
`
`NDL303m.2ON?
`
`
`
`EDLQUOOCM“CQHCOO
`
`2:38me
`
`Ema
`
`
`.mtnm5:500
`
`Emucmqmus2859:x8598
`
`3mm
`
`Emgm
`
`Page 32
`
`Page 32
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 30 of 34
`
`US 7,161,506 B2
`
`
`
`Loacowmoco_mmm5Eoocmmemfioo
`5:5San..aQ
`83:8805mm
`33..
`
`
`
`323%5
`
`umuoocw
`
`EDm.§c:00tmt3m
`
`no99:80:th
`
`Eemaczootmtzm
`
`
`
`NDmLQCDOOtmtDm2000*.
`
`
`
`ommrovmw
`
`mtMMDOE
`
`rmemwcsoototsm
`
`mmBmEsooEtzm
`
`mmemacsootmtsm
`
`CwwgquDOOEmtDm
`
`Page 33
`
`Page 33
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 31 0f 34
`
`US 7,161,506 B2
`
`
`
`
`Receive Initial
`
`Data Block From
`
`Input Data
`Stream
`
`~1800
`
`Count Size of
`Data Block
`
`~1802
`
`
`
`
`Buffer Data Block ~1804
`
`
`
`
`Apply Content
`Dependent /
`Independent Data
`Recognition
`
`
`
`
`~1806
`
`Page 34
`
`
`
`Recognize Data
`Stream Content
`
`No-> B
`
`?
`
`Yes
`
`+ C
`
`FIGURE 18A
`
`Page 34
`
`

`

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

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 33 of 34
`
`US 7,161,506 B2
`
`
`
`Compression Ratio
`
`of at Least One Encoded Data
`
`Block Greater Than Content
`
`
`
`Independent Threshold
`1820 ~
`
`
`
`
`
`Append Null
`
`Select Encoded
`Descriptor to
`Data Block with
`
`
`
`Unencoded Input
`Greatest
`
`
`
`Data Block
` 1822 ~
`
`Compression Ratio
`
`
`
`Append
`Corresponding
`1824 ~
`
`Encoding
`Descriptor
`
`
`
`
`
`Output Unencoded
`Output Encoded
`Data Block with
`Data Block with
`
`
`Null Descriptor
`
`Descriptor
`
`
`
`
`
`Receive Next
`
`
`
`Terminate
`More Data
`
`
`Data Block From
`Data Compression
`
`
`
`Blocks in Input
`Process
`Stream
`
`
`
`?
`
`
`Input Stream
`
`
`
`Yes
`
`1830
`
`FIGURE 180
`
`Page 36
`
`Page 36
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 34 0f 34
`
`US 7,161,506 B2
`
`1838~
`
`
`
`Select Recognized
`
`
`Data Type/File or Block
`in List or Algorithm
`
`
`Select or Estimate
`
`1840 ~ Content Dependent
`
`Algorithm(s)
`
`Dependent Encoder(s)
`
`
`Compress Data Block
`1842 ~ with Enabled Content
`
`No» F
`
`1844 ~
`
`1646 ”
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`Count Size of Data
`Blocks
`
`1848
`
`
`
`Calculate
`-
`-
`Compressron Ratio
`
`
`
`Content Dependent
`Threshold
`
`
`
`~ 1850
`
`Yes
`
`v E
`
`FIGURE 18D
`
`Page 37
`
`
`
`
` Compression
`
`Ratio of at Least
`
`
`One Encoded Data
`Block Greater Than
`
`
`
`Page 37
`
`

`

`US 7,161,506 B2
`
`1
`SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`DEPENDENT DATA COMPRESSION
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a Continuation of US. application Ser.
`No. 10/016,355 filed on Oct. 29, 2001, is a US. Pat. No.
`6,624,761, which is a Continuation-In-Part of US. patent
`application Ser. No. 09/705,446, filed on Nov. 3, 2000, now
`US. Pat. No. 6,309,424, issued on Oct. 30, 2001, which is
`a Continuation of US. patent application Ser. No. 09/210,
`491, filed on Dec. 11, 1998, which is now US. Pat. No.
`6,195,024, issued on Feb. 27, 2001.
`
`BACKGROUND
`
`1. Technical Field
`
`The present invention relates generally to a data compres-
`sion and decompression and, more particularly, to systems
`and methods for data compression using content indepen-
`dent and content dependent data compression and decom-
`pression.
`2. Description of Related Art
`Information may be represented in a variety of manners.
`Discrete information such as text and numbers are easily
`represented in digital data. This type of data representation
`is known as symbolic digital data. Symbolic digital data is
`thus an absolute representation of data such as a letter,
`figure, character, mark, machine code, or drawing.
`Continuous information such as speech, music, audio,
`images and video, frequently exists in the natural world as
`analog information. As is well known to those skilled in the
`art, recent advances in very large scale integration (VLSI)
`digital computer technology have enabled both discrete and
`analog information to be represented with digital data.
`Continuous information represented as digital data is often
`referred to as diffuse data. Diffuse digital data is thus a
`representation of data that is of low information density and
`is typically not easily recognizable to humans in its native
`form.
`
`There are many advantages associated with digital data
`representation. For instance, digital data is more readily
`processed, stored, and transmitted due to its inherently high
`noise immunity. In addition, the inclusion of redundancy in
`digital data representation enables error detection and/or
`correction. Error detection and/or correction capabilities are
`dependent upon the amount and type of data redundancy,
`available error detection and correction processing, and
`extent of data corruption.
`One outcome of digital data representation is the continu-
`ing need for increased capacity in data processing, storage,
`and transmittal. This is especially true for diffuse data where
`increases in fidelity and resolution create exponentially
`greater quantities of data. Data compression is widely used
`to reduce the amount of data required to process, transmit,
`or store a given quantity of information. In general, there are
`two types of data compression techniques that may be
`utilized either separately or jointly to encode/decode data:
`lossless and lossy data compression.
`Lossy data compression techniques provide for an inexact
`representation of the original uncompressed data such that
`the decoded (or reconstructed) data differs from the original
`unencoded/uncompressed data. Lossy data compression is
`also known as irreversible or noisy compression. Entropy is
`defined as the quantity of information in a given set of data.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`Thus, one obvious advantage of lossy data compression is
`that the compression ratios can be larger than the entropy
`limit, all at the expense of information content. Many lossy
`data compression techniques seek to exploit various traits
`within the human senses to eliminate otherwise impercep-
`tible 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
`provide an exact representation of the original uncom-
`pressed data. Simply stated, the decoded (or