(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
`
`Sheet 2 of 34
`
`US 7,161,506 B2
`
`
`
`VLYOG2GOONF
`
`IMWSLS
`
`YOLdIdOSAaTd
`
`Ma3ssng
`
`bYSLNNOD
`
`faa4adna
`
`¢YaLNNOO
`
`baYaCOONS
`
`3YACOONS
`
`
`NOISSSYdNOONOISSaxaODLAAN!
`
`NOILdlyOS3aG€YBLNNODYag5N8
`
`NOSINYdWOO
`
`FALeeMadang€3WSGOONSvLVO
`
`
`
`WVAULSVLVG
`
`6Ola
`
`/f43sdin¢e
`
`UYSLNNOS
`
`U3YAQOON]A
`
`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
`
`Sheet 5 of 34
`
`US 7,161,506 B2
`
`NOSIeVdNOO
`
`
`
`NOlMdi¥OS3ad€YSLNNODy¥assng
`
`
`
`
`AdALMasing€3YaGOONAviva
`
`NOISSSYdWOO
`
`
`
`NOISSSedNOODLAdNI
`
`
`
`vLY¥OG3GOONA
`
`/MWWFYLSMaing23YSCOONA
`YOLAIYOSTGZ@UALNNOO
`
`fd3a43ng
`
`bYSLNNOO
`
`b3YSQOON3
`
`
`
`WVSELSVLVO
`
`JO3yuNdld
`
`LIAN
`
`NOLLVNIWSL30
`
`08
`
`YAGOSNS
`
`ALIMavaisad
`
`SYOLOVA
`
`bvOls
`
`faassng
`
`UYALNNOOD
`
`U3Y3dOON3
`
`0c
`
`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
`
`Sheet 8 of 34
`
`US 7,161,506 B2
`
`
`
`VLVGGHQOIONA
`
`IMWV3a4LS
`
`NOlldIWOSAG
`
`adAL
`
`NOISSSYdNOO
`NOISSSYdNOD
`
`f4345Ne
`
`baALNNOO
`
`LaYaGOONA
`
`
`
`WVAYLSVLVO
`
`fdaaina
`
`¢é3YACOONS
`
`€YSLNNOD
`
`€3YAGOONA
`
`faadsang ¢YALNNOOD
`
`fdassna
`
`UYSALNNOD
`
`.
`
`u3YSGOONA
`
`9‘Sls
`
`LACNI
`
`viva
`
`VIVd
`
`xHOO7198
`
`Yasang
`
`YSLNNOD
`
`
`
`AWILGalslO3adS
`
`“dFsn
`
`Page 11
`
`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
`
`Jan. 9, 2007
`
`Sheet 11 of 34
`
`US 7,161,506 B2
`
`
`
`VLVGG3G0ON2
`
`
`
`/MWVAYELSfaasaana
`
`yYOLdINOSIaZYSLNNOO
`
`é3YAGOON3
`
`SdALoeMadara€3YAQOONSv1aNOISSSYdNODNOISSauWODL
`
`
`
`NOILdINDS3AG€YBLNNOOdaaine
`NOSINWdNWOO.
`
`VIVOLONI
`
`X00718
`
`FYOSS300"d
`
`YALNNOD
`
`OL
`
`fad344ne
`
`|YaLNNOD
`
`L5YACOONS
`
`
`
`WVAYLSVLVO
`
`08
`
`
`
`4OSyneYaQOONA
`
`
`NOLLWNIWYALSOSHOLOVA
`LYaNALNISVEISSQ06
`
`f¥3dana
`
`UYSALNNOD
`
`UyYAGOONS
`
`Oyog
`
`MSIL
`
`
`
`AWLLGaldlo3ad$
`
`“Yasn
`
`Page 14
`
`Page 14
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 12 of 34
`
`US 7,161,506 B2
`
`dOawNo!d NOSIYVdWOD/NOILVNIWYSL30
`
`
`NOISSSedWOO
`
`OLLVY
`
`NOLLVNINSSL3G
`
`LIYAW
`
`LMdNI
`
`Viva
`
`d345n9
`
`
`
`AVAYLSVLVO
`
`VLiVG
`
`AV"
`
`YALNNOO
`
`“ASN
`
`
`
`
`
`YSNILSwillaaidiodds
`
`NOlduOSaa
`
`NOISSaudWOOUACOONA
`SALALMavulsad06
`
`SHOLOWS
`
`09
`
`¥LVGG3GOINZ
`
`IMWYIYLS
`
`YOLAOSAG
`
`Page 15
`
`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
`
`Sheet 18 of 34
`
`US 7,161,506 B2
`
`papoouyz
`
`
`soyduoseg|Yolsseudwopuolsseudwod
`
`uMB12qpuaddyeulLUe}eq
`Jo}duoseq(pasinbaw4)
`
`adhonex
`€qsiajunoojieyngVcCSsJB}UNOO/SEYNG~OE}
`€3suajunogjeyngq7gsusqunoojeyng
`
`ugsJa}UNOO/EyNYG~Op
`
`bdSiajyunog/eyng
`
`wiqsiaqunoojJeyng
`
`Lgsuejunoojayng
`
`
`
`aclAYNOSIS
`
`Page 21
`
`Page 21
`
`
`
`

`

`U.S. Patent
`
`A
`
`Jan. 9, 2007
`
`Sheet 19 of 34
`
`US 7,161,506 B2
`
`ReceiveInitial
`Data Block From
`Input Data
`Stream
`
`CountSize of
`Data Block
`
`Buffer Data Block
`
`Stream Content
`
`Apply Content
`Dependent Data
`Recognition
`
`Recognize Data
`
`FIGURE 14A
`
`Page 22
`
`Page 22
`
`

`

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

`

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

`

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

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 23 of 34
`
`US 7,161,506 B2
`
`
`
`
`
`sepoouyjuepusdag}us}u0D
`
`wqJepoouyejeqJeyngJayunod
`
`
`juapuedeqeyeqynduyyoBEA|weays
`
`yua}Uu0DBEC
`
`€GJepooug
`
`LQJepooug
`
`
`
`cQJepoous~OZEL
`
`uoniuBooay
`
`aylg/eyeq
`
`uomubooey
`
`Jo(s)siq
`
`(s)wuobiy
`
`VSLAYNDIs
`
`OLE
`
`Page 26
`
`Page 26
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 24 of 34
`
`US 7,161,506 B2
`
`
`
`JoydusseqpjousesuL
`
`jsoL
`
`
`
`pepoougoneyuoIsssidWwoD
`
`Ldsua}UNOO/eLng
`
`ployseJu|MojagOeyUCIsseidWO0d
`
`lqsJajunoOjeyng
`
`L
`
`
`
`
`
`UyIMB]eqployselyLerogyjUB}UODzdsuajunoqveung||~ogee}
`
`
`
`
`
`juepusdegadh,uoIsseJdUODeqsiajunodjeyngVJoydusseq=|uolsseidwioD
`
`7suajunooyjseying
`sJapoouyjuepuedepul|jue}UOD 3Japoouy
`
`L
`
`SUIWUa}Eq
`
`uoissasdwod
`
`/oney
`
`plOysesyL
`
`ZqsJaquNogjeying23Japooug
`
`
`
`egsiejunoojeyng€9vepooug
`
`aSbAYNDIs
`
`ugsysyunoO/jeynguzJaepoous
`
`~OE
`
`Page 27
`
`Page 27
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`A
`
`Jan. 9, 2007
`
`Sheet 25 of 34
`
`US 7,161,506 B2
`
`Receive Initial
`Data Block From
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`Buffer Data Block
`
`Stream Content
`
`Apply Content
`Dependent Data
`Recognition
`
`Recognize Data
`
`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
`
`with Threshold Limit
`
`Calculate
`Compression
`Ratio
`
`Compare
`Compression Ratios
`
`D
`
`FIGURE 16B
`
`Page 29
`
`Page 29
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 27 of 34
`
`US 7,161,506 B2
`
`
`
`Compression Ratio
`of at Least One Encoded Data
`Block Greater Than Content
`Independent Threshold
`1620 ~
`?
`
`
`
`
`
`
`
`
`Append Null
`Select Encoded
`Descriptor to
`
`
`
`Data Block with
`UnencodedInput
`
`
`Greatest
`Data Block
`
`
`
`Compression Ratio
`
`
`
`Append
`
`Corresponding
`
`Encoding
`Descriptor
`
`
`
`
`
`Output Unencoded
`Output Encoded
`Data Block with
`Data Block with
`
`
`
`Null Descriptor
`Descriptor
`
`
`
`
`
`Terminate
`More Data
`
`
`
`
`Data Compression
`Blocks in Input
`Stream
`Process
`
`
`
`Receive Next
`Data Block From}
`Input Stream
`
`
`
`
`
`Yes
`
`1630
`
`FIGURE 16C
`
`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
`
`1636 ~
`
`Select Content
`Dependent
`Algorithm(s)
`
`Compress Data Block
`1638 ~] with Enabled Content
`Dependent Encoder(s)
`
`
`
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`Blocks
`
`Count Size of Data
`
`1640 ~
`
`1642 ~
`
`1644 ~
`
`Compression Ratio
`
`Calculate
`
`
`
`
` Compression
`Ratio of at Least
`
`
`
`One Encoded Data
`Block Greater Than
`
`Content Dependent
`Threshold
`
`?
`~ 1648
`
`
`No> B
`
`FIGURE 16D
`
`Page 31
`
`Page 31
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 29 of 34
`
`US 7,161,506 B2
`
`LgJapoouy
`
`€q48poouy
`
`|3Jepoouz
`
`73Japoouy
`
`uyJepoouy
`
`
`
`sjapoougjuepuedegjue}u0D
`2J8pOOus||~ozey
`
`WULOD|YUOReWHSS
`saiqe|dq-4007]Jo
`
`VZlLaYNSls
`pueuonluBooey
`
`adh]ayl4/eyeq
`juapuedapu|
`OOZL02Ob
`
`
`
`
`sJapoouyjuepuedapL|}Us}UODuonluBoosy
`
`lqJepoousyua}uo0Dejeq
`
`Saassyuepuedaqyeqjnau|490lgBIEQ|weays
`
`OLZL5
`
`ejeq
`
`
`
`eyeqgindu901ge}e
`
`Jeng4ajunogD
`
`Page 32
`
`Page 32
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 30 of 34
`
`US 7,161,506 B2
`
`pspoougwqsiaiUNoO/Jeyng
`Jo\duoseg|uolssaidwuoguossesdop
`UMeyedBUILUIB}9Q
`Joyduoseq(pesmpey5)
`
`adht!
`OSC}OPEL
`
`GZ)AYNols
`zasueyunogjeung||oee,
`UQSJBJUNOO/JENG
`Zqssajunoo/seyng
`eqsusjunoQyeying
`
`L34svaqunoOyeyng
`€qsuejunodyJeyng
`LQsuejunoojeying
`
`Page 33
`
`Page 33
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 31 of 34
`
`US 7,161,506 B2
`
`
`
`
`ReceiveInitial
`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
`?
`
`Yes
`
`v 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
`
`with Threshold Limit
`
`Calculate
`Compression
`Ratio
`
`Compare
`Compression Ratios
`
`D
`
`FIGURE 18B
`
`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
`
`1824 ~
`
`
`
`Append
`Corresponding
`
`Encoding
`Descriptor
`
`
`
`
` Output Unencoded
`Output Encoded
`Data Biock with
`Data Block with
`
`1826 ~
`
`
`Null Descriptor
`Descriptor
`
`
`
`
`
`
`Receive Next
`Data Block From
`
`Input Stream
`
`
`
`
`Terminate
`More Data
`
`
`
`Data Compression
`Blocksin Input
`Process
`Stream
`
`
`
`?
`
`
`Yes
`
`FIGURE 18C
`
`Page 36
`
`Page 36
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 34 of 34
`
`US 7,161,506 B2
`
`1838 ~
`
`Select Recognized
`Data Type/File or Block
`
`in List or Algorithm
`
`
`
`Algorithm(s)
`
`Compress Data Block
`1842 ~| with Enabled Content
`
`Dependent Encoder(s)
`
`Select or Estimate
`1840 ~; Content Dependent
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`Blocks
`
`Count Size of Data
`
`1844 ~
`
`1646 ~
`
`4848
`
`Compression Ratio
`
`Calculate
`
`
`
`
`
`
`
` Compression
`Ratio of at Least
`
`
`One Encoded Data
`
`Block Greater Than
`
`
`Content Dependent
`Threshold
`
`
`FIGURE 18D
`
`No» F
`
`Page 37
`
`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 U.S. application Ser.
`No. 10/016,355 filed on Oct. 29, 2001, is a U.S. Pat. No.
`6,624,761, which is a Continuation-In-Part of U.S. patent
`application Ser. No. 09/705,446, filed on Nov. 3, 2000, now
`USS. Pat. No. 6,309,424, issued on Oct. 30, 2001, which is
`a Continuation of U.S. patent application Ser. No. 09/210,
`491, filed on Dec. 11, 1998, which is now U.S. Pat. No.
`6,195,024, issued on Feb. 27, 2001.
`
`BACKGROUND
`
`1. Technical Field
`
`Thepresent 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 knownto 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 humansin its native
`form.
`
`There are many advantages associated with digital data
`representation. For instance, digital data is more readily
`processed, stored, and transmitted dueto 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 outcomeofdigital 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 knownasirreversible or noisy compression. Entropy is
`defined as the quantity of information in a given set of data.
`
`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