||||||||||||||||||||||||||||||||||||||ll||llllllllll|||||||||||||||||||||||
`
`US007 1 6150632
`
`(12) United States Patent
`Fallon
`
`(10) Patent No.:
`(45; Date of Patent:
`
`US 7,161,506 B2
`*Jau. 9. 2007
`
`(54) SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`l)EPl'LV'l)IC1\"I' DATA (IBM PRICSSION
`
`{.75}
`
`Inventor;
`
`James J. I-‘allnn. /\l'l11lOl1.1\‘.. NY (US)
`
`(73)
`
`.L\ssi_s_1nr.-(:1
`
`llealtime Data LLC. New York. NY
`{US}
`
`1, * ) Nolicc:
`
`Subject to any disclainwr. lhc lcnn of l11i.~:
`paleni is cxtmdcd or adjusted llndcr 35
`U.S.('. 1S4(b] by 0 days.
`
`4.574.351 A
`4.593.324 A
`4.681.150 A
`4.730.348 .-'\
`
`4:394-959 A
`4,STO.4-15 A
`
`"1-5173-D99 A
`-'l.S?fi.fi4! A
`4.838.812 A
`
`3.-"I-936 Dang at al.
`6.51-J86 Ohkubo at El].
`"F198? Maihcs ct al.
`3.51988 Mau.'Criskcn
`
`351939 Mflkflmi '3‘ 31-
`9 I939 V3111 Mm-en e1 :1].
`
`1‘«‘?|iki.§'-'m1?i 0' 9]-
`10* 19-*9
`l[J»'l"J.‘49 Sinrer
`131989 Dinnn cl .1].
`
`“'‘-995-995 5‘
`
`3'''l99” 5“"'1“5°“
`
`[_(j.3mi.mgd}
`
`'l'IJjs patent is subject [0 a terminal dis-
`°l5'i““°“‘
`
`DJ"!
`
`I“01’~[‘31UN Pr\'1'13N'1‘ D0['UM|‘3N'l‘5
`4127513
`2.1992
`
`['21) April. Nu: 1I}:"fi68.,768
`
`22
`
`[
`
`)
`
`(551
`
`F’! d:
`1e
`
`. 22, 2083
`
`S
`
`8P
`
`""0" 1’“'’“°='‘i“'' 9”“
`Us 2{m4,r00567g3 A]
`Man 25_ 20.04
`
`Re-Iated U.S. Application Data
`(63) Conlinuatiun 01'applic::tio11 No.
`lOr'0l6.355_. filed on
`Oct. 29. 2001. now Pat. No. 6.524.761. which is a
`conlinuaiinn-in-part of :applicatim1 No.
`(}lJe'7U5.44{-L
`filed un ‘Nov. 3. 2000. new Pa1.Nu_ 6,309.42-'$.w]1ic11
`is :1 czorltinuatiun ofappliculion No. OWE I 0.49|. filed
`011 Dec. 1]. 1998. now Pat. No. 6.195.024.
`
`Int (j]_
`H931” 734
`(S2) U.S. Cl.
`(-58) Field M (1-law“-mafia“ Search
`
`(51)
`
`(56)
`
`(200501)
`
`3-llf5l'. 3411'?!)
`34150‘
`.“”5]_ 57 79 75
`Sec appucmion file rm, complete Search Eism'l_y_
`References Cited
`
`,
`,
`US‘ PATENT DOCUMEN [8
`4'13-L513 A
`]]_-1973 (‘fly 3, a]_
`-'l.3[J2.Tr'5 A
`l1.'19R1 Widcrgxen at al.
`-1.,‘v94.??4 A
`?.'I9:'<3 Widergrv.-n er :1].
`
`‘i‘
`
`[CoIJ1i111Iecl_]
`.
`_
`_
`UTHI:-R 1’UB1_.[(‘.*'-\l‘lUN5
`
`.4_ 11.5)’ (‘mp $¢=I__.f-11:‘ f1fg.f:-Speed Loss:'v.I-5 [Jam
`hack Vcnbrux.
`[|'Il?l':' Trans. On |L.'1rcuils: and System for \«'idm
`F_k1nipm.wsirJr:
`,
`lechnulogy. V01. 2. No. 4. Due. 1992‘. pp. 381-391.
`
`[Chmiuued]
`
`l __ .
`.
`_
`_
`‘
`,.
`_.
`P'"’“"7 E"“'”‘""
`L_‘"h.U3"3’°'?,
`(:4) "mUm.c'v' Algfigf W Hrm__F1bh & NE-ave IF Group 0]
`1 “P” & (‘my "
`57
`
`{
`
`1
`
`ABS1~RA(_»T
`
`Systems and rncrllmdas for providing 1:151 and cllicicnl data
`cnmprc5s.iL111 dieing a COI'l‘11J1il1IIIi0]1 of ccmlenl indepcndcnl
`dam °°’m'P"e531‘*“‘ and °'3'f“em d‘5Pe“d_‘"“ dam °‘““T"_'*3'53‘““'
`In nnc :\_specl'. a_meI]1od ior conlprgsslng data cmnpnses 111::
`steps 0|‘: anzllymug 0 datta blm.-.k 01' an mpul data s!re:m1 to
`1deu111_y_:-1 data type 01 the dala block. the Input data sire-€111:
`comprmng a plurahty of dzsparate dam types: performlng
`content dependent data L‘.L'll'[1pl'l.’.'SS1l.JD. on [he data block, iftllc
`data Iypt: (:1 the data black is id‘<:11til1cd'. pa-srfnrming cunluul
`independent data Compression on the data block. iflhe data
`type 01’ I116 (1313 block 15 not ideutilied.
`
`99 Claims. 34 Drawing Sheets
`
`Mano -':ci.ml\-I
`anurm
`
`
`
`
`uu1I'1
`1 nuktbcxwnm .-zau
`
`umnncxmm '
`:n..v-uruu-Fn7nI m
`|Iu Lani!--L-I
`
`.
`
` Oracle 1027
`
`Oracle 1027
`
`

`
`U.S. P.11TE.I'1vIT DOCUMENTS
`
`4.929.945
`4.955.575
`5.023.922
`5.045.343
`5.045.352
`5.045.027
`5.049.331
`5.097.251
`5.113.522
`5.121.342
`5.150.430
`5.159.335
`5.175.543
`5.179.551
`5.137.793
`5.191.431
`5.204.755
`5.209.220
`5.212.742
`5.225.175
`5.227.393
`5.231.492
`5.237.450
`5.237.575
`5.243.341
`5.243.343
`5.247.533
`5.247.545
`5.253.158
`5.270.332
`5.237.420
`5.293.379
`5.507.497
`5.309.555
`5.355.493
`5.357.514
`5.379.035
`5.379.757
`5.331.145
`5.394.534
`5.395.223
`5.400.401
`5.403.539
`5.405.273
`5.405.279
`5.412.334
`5.414.350
`5.420.539
`5.452.237
`5.451.579
`5.457.037
`5.471.205
`5.479.537
`5.435.325
`5.495.244
`5.505.344
`5.505.372
`5.530.345
`5.533.051
`5.535.355
`5.537.553
`5.557.551
`5.557.553
`5.557.749
`5.551.324
`5.574.952
`5.574.953
`5.533.500
`5.590.305
`5.595.574
`5.504.324
`
`>-5-3*>31>31»)->>>J>>1"?'b>>7*>>J=1>>3-:‘>3*3*>>>>>371?39>>>>>>>}\*3*>>3*>%>>J=1>>>>>>->133“->>2P->>3*>>>'P
`
`5.-1 1990
`1011990
`7.1 1 99 I
`91 1991
`9.1 1991
`9.1 1 99 1
`91 1991
`3.1 1992
`5.1 1992
`5.1 1992
`9.1 1992
`1 0.1 1 992
`1 2.1 1 992
`1.1 1993
`2.11993
`3.-1 1993
`4.1 1993
`5.- 1993
`5.-1 1993
`7.1‘ 1993
`7.1 1993
`7.1 1993
`3.1 1993
`3.1 1993
`9.1 1993
`9.1 1993
`9.-1 1993
`91 1993
`1 1.1 1993
`1 2.-1 1993
`2.1 1994
`3.1 1994
`4.1 1994
`51 1994
`10.1 1994
`1 01 1 994
`1 1 1 995
`1.1 1995
`1.1 1995
`2.1 1995
`3.1 1995
`3.-1 1995
`4.1 1995
`411995
`4.-1 1995
`5.- 1995
`5.11995
`5.1 1995
`9.1 1995
`10..1 1995
`1 11 1995
`1 1.1 1 995
`12.11995
`1 1 1 995
`21 1995
`4.1 1995
`4..-1 1995
`5.1 1995
`7.1 1995
`71 1995
`71 1995
`9.11995
`91 1995
`9.1 1995
`1 0.1 1 995
`1 11 1995
`1 111995
`1 2.1 1 995
`1 2.1 1 995
`1.1 1997
`2.11997
`
`O'Brien cl :11.
`Hori et :1].
`Huang
`Fasccnda
`Mitchell et .11.
`'l‘.=1I1fi'e 1:1 211.
`Gibsun e1 :11.
`Langdon. Jr. 1:1 111.
`Dlnwiddie. Jr. at al.
`Szymborski
`(‘bu
`Rabin el 3].
`Lani:
`Tru1.f|"c er. al.
`Keidn L'I. al.
`I1l:1.5cgawa el :11.
`(‘hevion 1:1 11].
`Iliyama c1 :3].
`Norlnilc 31 .1].
`Westaway et 31.
`E11’
`Dangi 61' a1.
`Miilrar el al.
`Ilannon. Jr.
`Serclussi cl «:11.
`Jackson
`O'Brien el 0.].
`Oslerilmd el 3].
`Turns El
`:11.
`Balkzmski el 111.
`Barrett‘
`Carr
`1‘e1genb:11In1 1:1 11].
`Akins el al.
`Pmvino cl‘ al.
`Patlisnm cl :1].
`Store:
`
`Hiymna el 711.
`Allen at al.
`Kulakowski er a].
`C'r.-11'-.1111
`Wasilewski c1 :11.
`BeL*"-Em e1 3].
`Grayhill cl .1].
`Anderson at a].
`Chang et 21].
`Whiting
`Perkins
`DiCec1:o
`Norlnilc el :11.
`C1111
`A1191: at al.
`Campbell et 3.1.
`Re-rr1iII:1r1I
`Jeong at al.
`R30
`Mahler
`Hiiltl et al.
`Jnrnes
`Kim e1 al.
`B111-{kc e1 11].
`Cmfl
`Brady
`Norris
`C:-urciru cl .1].
`Brady e1‘ :11.
`R1151 c1‘ :11.
`Allen at aL
`Wannabe El 111.
`Bhnndari 91 al.
`(‘hui el al.
`
`US 7,161,506 B2
`Page 2
`
`5.606.706
`3.612.788
`5.613.069
`5.615.017
`5.621.820
`5.623.623
`5.623.701
`5.617.534
`5.627.995
`5.629.732
`5.630.002
`5.635.632
`5.635.932
`5.642.506
`5.649.032
`5.651.795
`5.652.857
`5.651.917
`5.054.703
`5.655.133
`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.7-18.904
`5.757.852
`5.771.340
`5.778.-‘III
`5.781.767
`5.734.572
`5.737.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.995
`3.839.100
`5.841.979
`5.847.762
`5.861.824
`5.861.920
`5.857.167
`5.870.036
`5.870.087
`5.872.530
`3.883.975
`5.885.655
`5.889.961
`5.915.079
`5.917.438
`5.920.326
`5.936.616
`
`3*>73-J>>3=->>>1>>}“->39}-3v>}>FP3b>>}>>>ii‘*>>I>>I>Ii*>>3=13=->.7=->>C5=1{Iv>331>33-33>}?I>3*3bCP'IP>>>>I513>3=1>3*>3i-3>>I¥-37>
`
`11 I 997
`31' I 997
`31" I 1797
`31'] 997
`4-' I 997
`411 997
`-I-"I 997
`5.1" I 997
`51' I 997
`51' I 997
`51' I 997
`61' I 997
`6111 997
`15.-1 I 997
`71 I 997
`71'] 997
`7.-1 I 997
`7-1‘ I 997
`81" I 997
`31 I 997
`9.1’ I 997
`9.1" I 997
`9.-' I 997
`1 U’ I 997
`I 2.1"] 997
`I .11 I 997
`I 21' I 997
`Z’ I 99.‘!
`2.1‘ I 998
`21' I 998
`3-’ I 993
`2: I 998
`31 I 998
`3-‘ I 998
`51' I 9911
`3-' I 5398
`611998
`71' I 998
`71 1998
`7.11 998
`71'] 998
`8-1‘ I 998
`8.“ I 998
`9-‘ I 998
`‘)1’ 19971
`9.‘ I 998
`9-"I 998
`9.-1 I 993
`I 01' I 9913
`I [III 998
`I U1 I 993
`1 IJ.-' I 998
`I 01’ 1 998
`I I 1 I 998
`I 1.1" I 998
`I I -"I 998
`I I 1 I 9915
`I I
`I 998
`1 I
`I 998
`I 7.-1 I 998
`1.1" I 999
`1 -"I 999
`111 999
`3.1’ I 999
`21' I 999
`2. I 9919
`3.1" I 999
`31' I 99*)
`311 9919
`IS.‘ I 999
`I3-"I 999
`7.1"] 999
`81 I 999
`
`Takmnotu et :1].
`Stone
`Walker
`Choi at 0.1.
`Rynderrnau :11 :21.
`Kim cl lll.
`Bakke c1 31.
`Cmfi
`Miller 11:1 :11.
`Mosknwitz el al.
`Carreim el al.
`1'-'11y :21 al.
`Shinagnwa c1 01.
`‘Lee
`Burt c1‘ :11.
`Dillon c1 .11].
`Shimoi el al.
`.\1Ia1.1pi:I el al.
`C.‘Ia.rI1.. lI
`Kikinis
`Mocrtl c1 :11.
`113!
`Saliba
`Boursier ct 111.
`Kenna
`!\1IacD1)nn11.l e1 0.].
`Wise cl :11.
`Kikinis
`Nakano 01 a].
`Schwartz er 211.
`Lee at al.
`Kikinis
`Kirslcn
`Franilszek c1 :11.
`Huang et al.
`Keficcvic el 11.].
`N111-1.1121110 91 3].
`DcMos3 c1 3].
`incur: at al.
`Rostoker el al.
`Hashilnc-10 el al.
`Cfallahan
`lsraelsen et al.
`Kawashhna 11:1 21].
`Sekine e1 :11.
`Yaj 111111
`1131113011 (-21 a].
`Diaz
`
`Langley
`Withers .......... ..
`Canfield et 0|.
`Dubson 121'
`.11].
`Canfielrl el :1].
`Park
`’l‘anal(11
`
`........ .. 341-"I07
`
`341151
`
`deCam1o
`Wegcner
`Schulhofel al.
`(‘anfield et al.
`8.311 at al.
`Mead at al.
`Dccring
`l1'ra.n:1.sz11k cl‘ 11.1.
`Chau
`Dumyo at al.
`‘Narira :71 2|.
`Rust
`Dobbel-1
`Vundrztn. .Ir_ :1 a1.
`Amio
`Rentschlcr 1.71.111.
`'I'orb0l'g. Jr. 01 al.
`
`

`
`931999 Panaoussis
`91999 Heath
`931999 Adams
`l0:']999 Packard
`10.“ I999 Jnqtletle el Ell.
`10«'I'J99 Heath
`lU.tl999 Belt
`ll.’1lJ99 1-Zamntnni
`1131999 F5115: 111.
`1161999 (“hiu-Han
`12-‘I999 Brady
`1331999 Dye
`l2.-‘I999 Spear el £11.
`H2000 Kirslen
`l-‘"2000 A]1a.roni et al.
`2.':'.[J0l'.| Adilctta
`292555 Elumerrnu
`2.-2050 Gilbert at :11.
`
`2.2000 Wilkes
`5'i3"”" 5”‘ ‘°‘”"'
`652000 Krocker eta].
`.
`5.'2000 Little et :11.
`moon Ynhagi E1211.
`3.-2005 Kadnrer
`8.'?.[J0t.| Ando
`852000 WLI el :11.
`torzuuo Snloh
`
`10.3000 Snukkonert
`11.3000 Dye
`.
`.
`.
`132001 Slnmmt
`1.9051 5......
`_
`172551 Dye
`l-200] Borella at al.
`272001 Mttriflfiy et 31.
`2200} Fallon
`5200] Matthews at :0.
`532001
`Iga
`$300.1 Sebastian
`8:200] Mann
`8-"Z001 Aguilar et al.
`893001 Christensen
`1073001 Fallon
`11-"2001 Del Castillo er :11.
`123200] Sehaefer
`B2002 Booth
`752002 Rhee
`892007. Kari
`832002 Esfahani et :11.
`8-"2002 Blurnenau
`9.-‘E002 Tooria.rts
`9"-1002 Mflftlifi
`10.32002 Tcoman et .11.
`1 IF2003 Lipnsti
`12.2002 Heath
`1-"2003 Kohnynshi
`393003 EHSWH-l' 431 31»
`3-"3003 5l0W1l1
`4e'3LttJ3 Saloh
`73003 5-11131‘: El ‘ll
`733003 F3000
`852003 Fallon ....................... .. 710755
`832003 Abdat
`341587
`
`US 7,161,506 B2
`Page 3
`
`341151
`
`341.-'51
`
`8-“E003 Zeineh
`6.606.413 Bl
`80003 Wolfgang
`5.509.323 B1
`9200:’: Rail
`6.618.728 B1
`952003 Fallon
`6.624.761 131'‘
`12.-‘Z003
`Ishida el a.l.
`5.661.839 B1
`352004 .‘-lalnwadj eta].
`5.704.340 Bl
`3-72004 York ........................ .. 714-""748
`6.711.709 I31"
`652004 Ukada
`5.745.282 131
`6-‘"3004 Fallon
`5.748.457 Bl
`1tJt'200| Kepecs
`200l.'0032|?.8 A1
`312002 Singh
`20010037035 A1
`8-""2002 U110
`2002-0104891 A1
`972002 Li e1 :11.
`200270126755 Al
`.'!.'2003 Anton el al. ................ .. 341-'51
`200350034905 A1‘
`5f.‘£0(}3 Ulcada et al.
`3.003.-'0084238 A1
`75003 Schwartz
`300370142874 Al
`I _~
`_
`__ ‘
`_
`‘
`_
`_
`1“0RlJC'N 1’A11=N'1 D0('UM*«'1‘”b
`
`E],
`FF
`”
`F1’
`EP
`FF
`F},
`PEP
`
`EP
`EP
`PP
`‘
`EP
`.
`33*
`JP
`W0
`W0
`WU
`W0
`
`01646”
`0135093
`0283798
`{MMWZ A2
`0%....
`329313;.
`‘*3
`0.8743?
`'
`0595405
`0718751 A2
`07187“ A?
`'
`‘
`9188009
`
`gggfggg
`11149376
`W0 94.4.73
`“,0 94.9%‘)
`WC") 9fi(‘hRiI3
`“,0 92.48.] ,
`" ‘
`
`[$1985
`5-195:5
`J.
`'
`9: 1988
`[.1991
`_, 99
`3.199;
`3,1994
`,
`3'99"
`1531996
`.._199..
`‘I.
`7-1997
`.
`1.333
`1-1999
`F,
`6.994
`l,'l_,]994
`11.1995
`lwlgm.
`"
`'
`
`PEI]-S1111 ‘Feb. 7719 CCSDS .’.:'I_ts."e:.'$ Data Cornprvxstan Re:-onrnrew
`o’ntfon_far' Spane Applirrotfotrs, Chapter 16. Losslcss (‘ornprcssion
`1-lnntlbook. Elserier Science [USAL 2003. pp. 311-326.
`Robert F. Rice. So;:r¢rP:'n¢-rice! Um've-rm! Norlwlers Coding Terk-
`mqnes . Jet Propulsion L.a1:to.ral'ory. Pasadena. California. JPL Pub-
`li-cation 79~22. Mar. 15. 197‘).
`K. Murashila et a1..
`lligh-Speed Statistical Compression using
`Self-organized Rules and Predelermined Code Tables. IEEE. 1996
`Data Compression. conference. no month.
`IBM. Fa.-sl Dos S011 Boot. Feb.
`I. 1994. vol. 37.
`185-186.
`.1. Anclerson el 11!. Codeo squeezes color teleconferencing through
`telephone lines. Electronics 1984. pp. 13-15. no Jnonl1r_
`Robert Rice. "Lossless Coding Standards For Space Data Systems".
`IEEF. I058—5393.'97. pp. 577-585. no month.
`Coene. W (:1 al. “A Fast Route For Application of Rate-distortion
`Opllinal Quantization i.n an MPEG Video Encoder" Proceedings of
`Lhe lnlemaxionnl Conference on Image Processing. US.. New York.
`]EEE_ sep,
`[5_ 1995‘ pp, g2_<.s33_
`‘'0 ratin S stem Plntfonn Abstraction Method". IBM Technical
`Disiflosmeg 135l1el'in. Feb. 1995. vol. 38. Issue No. 2. pp. 343-344..
`
`issue 28. pp.
`
`* cited by examiner
`
`5.949.355 A "'
`5.955.976 A
`5.950.455 A
`5.964.842 A
`5.968.149 A
`5.973.530 A
`5.97-1.471. A
`5.982.723 A
`5.991.515 A
`5.996.033 A
`6.000.009 A
`6.002.411 A
`6.003.115 A
`6.011.901 A
`5.014.594 A
`6.016.317 A
`5.028.725 A
`5.031.939 A
`
`5.03.2.1-18 A
`5‘”51*3'”3 A
`6.073.232 A
`
`5.075.470 A
`5.094.534 A
`5.597.530 A
`6.104.389 A
`5.105.130 A
`5123412 A
`’
`‘
`5.141.053 A
`6.145.069 A
`6.159.241 B1
`........._.. Bl
`5.173.331 Bl
`5.182.125 B1
`6.192.082 Bl
`6.195.024 B1
`5.225.557 131
`5.225.740 B1
`5.253.254 Bl
`6.271.627 Bl
`6.272.628 Bl
`6.282.541 B1
`6.309.424 B1
`5.317.714 B1
`5.331J.52.'J'_ Bl
`5.34S.307 Bl
`5.421.387 B1
`5.434.168 131
`5.-134.595 Bl
`5.-442.659 Bl
`5.449.582 B1
`5.453.501 131
`5.453.509 B1
`5.487.640 B1
`5.489.902 Bl
`6.513.113 B1
`5.539.033 131-
`5.539.455 3|
`5.542.544 Bl
`5590-009 Bl
`5.501.104 131
`5.604.158 131"‘
`5.606.040 Bl‘
`
`

`
`U.S. Patent
`
`Jan. 9. 2007
`
`Sheet 1 of 34
`
`US 7,161,505 B2
`
`INPUT DATA STREAM
`
`IDENTIFY INPUT DATA TYPE AND
`GENERATE DATA TYPE IDENTIFICATION
`SIGNAL
`
`2
`
`
`
`DATA TYPE
`
`ID SIGNAL
`
`CONIPRESS DATA IN ACCORDANCE WITH
`IDENTIFIED DATA TYPE
`
`3
`
`r—
`
`I I |
`
`I
`
`I I I I I
`
`I'—
`
`COMPRESSED DATA STREAM
`
`RETRIEVE DATA TYPE
`INFORMATION OF COMPRESSED
`DATA STREAM
`
`WITH IDENTIFIED DATA TYPE
`
`DECOMF-‘RESS DATA IN ACCORDANCE
`
`I I I
`
`|
`
`I I I I I
`
`FIG. ‘I
`
`PRIOR ART
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 2 M34
`
`US 7,161,506 B2
`
`Eqnmmnoozm
`
`mokamowmmNmmfiznoo
`.$_.3qmEmEmzusmmmzmooozm
`
`
`
`omow
`
`
`zo_mmu.En=2oo2o_mmmmn§_ouSn_z_5.3
`
`zorE_momm_omKWFZDOUmmunfimmmhznou
`
`
`
`mat...zo_»._.m.wfl,u~~n_mm.rwoEwuzpmmmmmnoozm<55xoo._m
`zomE<n_2oo..
`
`
`Emfipm
`
`Fmmhzaoo
`
`_.mmmooozm
`
`sqmkhmwksq
`
`N.0_..._
`
`Rmumnm
`
`cmmfiznoo
`
`cmmmooozm
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 3 of 34
`
`US 7,161,506 B2
`
`B
`
`RECEIVE INITJAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`DATA BLOCK
`
`coum SIZE OF
`
`300
`
`302
`
`BUFFER DATA BLOCK
`
`304
`
`COMPRESS DATA
`BLOCK WITH
`
`ENABLED ENCODERS
`
`303
`
`310
`
`312
`
`314
`
`BUFFER ENCODED
`DATA BLOCK OUTPUT
`FROM EACH
`ENCODER
`
`BLOCKS
`
`COUNT SIZE OF
`ENCODED DATA
`
`CALCULATE
`COMPRESSION
`
`RATIOS
`THRESHOLD LlMiT
`
`commas
`COMPRESSION
`RATIOS WITH
`
`FIG. 3a
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 4 of 34
`
`US 7,161,506 B2
`
`316
`IS
`
`
`COMPRESSION
`
`RATIO OF AT LEAST ONE
`
`ENCODED DATA BLOCK
`
`GREATER THAN
`THRESHOLD?
`
`
`
`
`
`NO
`
`318
`
`320
`
`APPEND NULL
`DE SCRIPTOR TO
`UNENCODED INPUT
`DATA BLOCK
`
`
`
`
`
`
`
`
`
`APPEND
`CORRESPONDING
`DESCRIPTOR
`
`
`
`
`
`OUTPUT UNENCODED
`DATA BLOCK WITH
`NULL DESCRIPTOR
`
`OUTPUT ENCODED
`
`DATA BLOCK WITH
`
`[3 ESCRIPTOR
`
`
`
`MORE
`DATA BLOCKS IN INPUT
`STREAM?
`
`
`
`330
`
`
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`
`STR EAM
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`
`
`FIG. 3b
`
`SELECT ENCODED
`DATA BLOCK WITH
`GREATEST
`COMPRESSION RATIO
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9. 2007
`
`Sheet 5 M34
`
`US 7,161,506 B2
`
`E.«..QQNQOUZM
`
`as§<m.Em
`
`moE_.mumm..o
`
`zo_mmmmn__2oo
`
`wn...__r_.
`
`zozimowmo
`
`zom_mEs_oo
`
`u_Omason
`
`tmm_2
`
`zoEqz_s_mm»mn_
`
`EMDOUZM
`
`>.:.__m$..__mma
`
`mmo5<“_
`
`8E.
`
`q.O_u_
`
`Rmunsm
`
`:mm._.z:oo
`
`cmmmaouzm
`
`
`
`Hzo_»M_%mmm»maEmu_..5mmmmmaoozm<._.<oxooam
`
`
`
`
`zo_mmmEs_oo512.«.55
`
`mw.._m._-Z300mwumnmEMPZDOO
`
`Emumnm
`
`_.mmfizaoo
`
`Emumnm
`
`Nmmpzaoo
`
`Fmmmooozm
`
`mmmmoouzm
`
`semmzw3..in
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 6 of 34
`
`US 7,161,506 B2
`
`500
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`
`
`
`
`B
`
`COUNT SIZE OF
`
`DATA BLOCK
`
`502
`
`BUFFER DATA BLOCK
`
`504
`
`/505
`
`
`
`COMPRESS DATA
`BLOCK WITH
`ENABLED ENCODERS
`
`
`
`508
`
`510
`
`
`
`APPEND CORRESPONDING
`DESIRABILITY FACTORS TO
`ENCODED DATA BLOCKS
`
`
`
`BUFFER ENCODED DATA
`BLOCK OUTPUT
`
`FROM EACH ENCODER
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`RATIOS
`
`CALCULATE
`COMPRESSION
`
`512
`
`514
`
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD
`
`LIMIT
`
`516
`
`FIG. 5a
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 7 of 34
`
`US 7,161,506 B2
`
`518
`IS
`
`
`COMPRESSION
`
`
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`
`
`
`
`
`
`
`
`CALCULATE FIGURE OF
`MERIT FOR EACH ENCODED
`DATA BLOCK WHICH EXCEED
`THRESHOLD
`
`APPEND NULL
`DESCRIPTOR TO
`UNENCODED INPUT
`DATA BLOCK
`
`SELECT ENCODED DATA
`BLOCK WITH GREATEST
`FIGURE OF MERIT
`
`520
`
`522
`
`
`
`
`
`
`APPEND
`CORRESPONDING
`DESCRIPTOR
`
`
`
`OUTPUT UNENCODED
`DATA BLOCK WITH
`NULL DESCRIPTOR
`
`OUTPUT ENCODEO
`DATA BLOCK WITH
`DESCRIPTOR
`
`
`
`MORE
`DATA BLOCKS IN
`INPUT STREAM?
`
`
`534
`
`
`
`RECEIVE NEXT DATA
`
`BLOCK FROM INPUT
`STREAM
`
`
`YES
`
`
`
`B
`
`FIG. 5b
`
`PROCESS
`
`TERMINATE DATA
`COMPRESSION
`
`

`
`US. Patent
`
`HI...
`
`8m
`
`f
`
`7!SU
`
`n,16
`
`m
`
`.6-woO_n_
`
`J.8
`
`UI
`
`:mwpznooMEmumzmcmmmaoozm
`
`
`
`0mo.EEommmNmw._.Z:O0mmmm.._DO0zm.mEéqmmhmEmnnsm
`
`eI
`
`.nzowEEs_ooSzo_E_mommaoommrznoo
`
`zo_wwmmn_s_ouzo_wmmE_2oo4.96..
`
`mncfi~zo_F¢m_W.@~mm»mommwmammmmmmooozmxoogm
`
`
`o_.336omooozm
`
`
`
`nvmm._.z:oo§_.m_..Em3:3.MEmfinmEmmaoozm
`
`Qmiomam3-mmm:8mm?»MEP
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 9 M34
`
`US 7,161,506 B2
`
`INPUT INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`
`
`no
`
`
`
`TIME EXPIRED‘?
`
`
`COUNT SIZE OF
`DATA BLOCK
`
`No
`
`no
`
`ENCODER WITHIN TIME LIMIT
`
`YES
`
`BUFFER
`
`713
`BUFFER ENCODED
`
`DATA BLOCK FOR EACH
`Eggfigfigfig?
`ENCODER THAT
`FROM EACH
`COMPLETED ENCODING
`PROCESS
`
`
`
`
`
`COUNT SIZE OF
`
`
`720
`ENCODEU DATA
`BLOCKS
`
` CALCULATE
`COMPRESSION
`RATIOS
`
`722
`
`
`
`
`
`
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD
`LIMIT
`
`
`
`3'24
`
`FIG. 7a
`
`
`
`
`712
`ENCODING
`
`COMPLETE?
`
`ES
`
`
`
`
`STOP
`ENCODING
`PROCESS
`
`
`
`700
`
`70
`
`B
`
`705
`
`703
`
`704
`
`BUFFER DATA BLOCK
`
`INITIALIZE TIMER
`
`BEGIN
`COMPRESSING
`DATA BLOCK wm-I
`ENCODERS
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 10 of 34
`
`US 7,161,506 B2
`
`726
`IS
`
`
`COMPRESSION
`
`
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`
`GR EAT ER THAN
`THRESHOLD?
`
`NO
`
`
`
`SELECT ENCODED
`DATA E’-LOCK WITH
`GREATEST
`COMPRESSION RATIO
`
`
`
`
`APPEND NULL
`
`DESCRIPTOR TO
`
`UNENCODED INPUT
`DATA BLOCK
`
`
`
`728
`
`730
`
`
`
`APPEND
`CORRESPONDING
`DESCRIPTOR
`
`OUTPUT UNENCODED
`DATA BLOCK WITH
`NULL DESC RIPTOR
`
`
`
`
`
`OUTPUT ENCODED
`DATA BLOCK WITH
`DESCRIPTOR
`
`
`
`
`
`
`
`DATA BLOCKS IN INPUT
`STREAM?
`
`
`
`740
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`
`
`FIG. 7b
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 11 of 34
`
`US 7,161,506 B2
`
`3..soomnoozm
`
`mogimomma§3.qmmkm
`
`zo_mwmmn=2oo
`
`mat.
`
`zo_mmmmn_s_oo
`
`OE.<m
`
`2o_E_momma
`~zo_Ez_s_mm»wm
`
`
`
`zom_mE.200
`
`momason.
`
`tam:
`
`zo:<z_s_w_mEn_
`
`8
`
`w.O_n_
`
`Emtnm
`
`_,EMPZDOU
`
`Emtam
`
`Nmmpzaoo
`
`Emumsm
`
`mmmkznoo
`
`_.mmmooozm
`
`mmmmooozm
`
`mmEMDOOZM
`
`Em_n_n_:m
`
`cmmkznoo
`
`cmKMQOOZM
`
`._.3n_z_
`
`<._.<D
`
`mmntsm
`
`ON
`
`<._.<QH:n_2_
`
`200.5
`
`Eommmoomm
`
`2mE.zD00
`
`
`
`§<mEm.3...<0
`
`3
`
`8
`
`mmooozm
`
`t.:_m<m_mmo
`
`mmoeoi
`
`mméc.
`
`om
`
`émwn
`
`
`
`ms:omraommm
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 12 of 34
`
`US 7,161,506 B2
`
`
`
`.E_.1Qnmnouzm
`
`
`
`._....SEfimthm.
`
`mo.EEomm.n_
`
`m.O_n_
`
`zo_mmmEn.s_oommnoozm
`
`zo_._.mmn__m._..nr.mmaE.._m$__mmn_8
`
`mmofifi
`
`zo_mmwmn§_oo
`
`OCRK
`
`zo_._.<2_...._«_m_._.mn_
`
`_..
`
`zom_mEs_ou
`
`..._Omane:
`
`._._mms_
`
`zo_Ez_s_mmm_o
`
`_...Ecaweohmweom.
`
`.:.._n_7:
`
`<56
`
`mmnfizm
`
`<53
`
`xoo._m
`
`N_m_._.Z3OO
`
`:<mEm3..<0.
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 13 of 34
`
`US 7,161,506 B2
`
`(‘I10
`
`
`
`
`
`
`108
`
`APPLY INPUT DATA
`BLOCK TO FIRST
`ENCODING STAGE
`IN CASCADED
`
`118
`
`PROCESS
`
`ENCOIZIER PATHS STOP ENCODING
`
`
`SELECT BUFFEREO OUTPUT OF LAST
`ENCODING STAGE IN ENCODER
`CASCADE THAT COMPLETED ENCODING
`PROCESS WITHIN TIME LIMIT
`
`
`
`
`
`
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`‘I22
`
`
`
`
`
`
` CALCULATE
`COMPRESSION
`RATIOS
`
`124
`
`COMPARE COMPRESSION
`
`RATIOS WITH THRESHOLD
`LIMIT
`
`126
`
`FIG. 10a
`
`A
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`
`
`
`100
`
`‘I02
`
`DATA BLOCK
`
`1'04
`
`BUFFER DATA
`BLOCK
`
`APPLY OUTPUT
`
`ENCODING
`STAGE TO NEXT
`ENCODING
`STAGE IN
`CASCADE PATH
`
`BUFFER
`ENCODED DATA
`BLOCK OUTPUT
`FROM
`
`STAGE
`
`
`
`N0
`
`1 '12
`
`YES
`
`1 15
`
`114
`
`was
`
`NO
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 14 M34
`
`US 7,161,506 B2
`
`128
`
`IS
`
`
`COMPRESSION
`
`RATIO OF AT LEAST ONE
`
`ENCOOED DATA BLOCK
`GREATER THAN
`
`THRESHOLD?
`
`
`
`
`
`
`
`
`
`
`
`APPEND NULL
`130
`CALCULATE FIGURE or
`nsspnwvoaro
`134 MEWTFOREACHENCODED
`umawcooeo uupur
`DATA BLOCK WHICH EXCEED
`
`
`DATA BLOCK
` THRESHOLD
`
`
`
`
`
`
` SELECT ENCODED DATA
`BLOCK WITH GREATEST
`HGURE OF MERIT
`
`
`
`136
`
`APPEND
`OUTPUT UNENCOOEU
`
`CORRESPONDING
`DATA BLOCK WITH
`132
`DES CRIPTOR
`NULL D ESC RIPTOR
`
`
`
`133
`
`140
`
`DUTP UT ENCODED
`DATA BLOCK WITH
`DESCFNPTOR
`
`DATA BLOCKS IN
`INPUT STREAM?
`
`YES
`
`
`
`STREAM
`
`ERMINATE DATA
`COMPRESSION
`PROCESS
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`
`144
`
`3 FIG. 10b
`
`

`
`HHEhS
`
`43
`
`US 7,161,506 B2
`
`.m.5mmooomo
`
`3:
`
`_‘V.0_n_
`
`7E3.__.DQbJ0
`
`US. Patent
`
`m
`
`1,
`
`flu
`
`M5xmooowo
`
`mwemmooumo
`
`.332\\SE.in.
`
`
`
`~..O....Q..Eommn
`
`
`
`§..mEm$.45.SnE68zmooomomoE_~_omma«.295%.:<mEmE3
`
`
`
`
`
`
`
`mmumamzo_5¢Exmmmmunmxooa
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 16 of 34
`
`US 7,161,506 B2
`
`
`
`RECEIVE INITTAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`
`
`
`
`1200
`
`1202
`
`1204
`
`BUFFER DATA BLOCK
`
`EXTRACT DATA
`
`COMPRESSION TYPE
`DESCRIPTOR
`
`
`
`1206
`IS DATA
`
`COMPRESSION
`
`TYPE DESCRIPTCI '
`
`NULL’?
`
`
`
`
`SELECT DECODER-{SJ
`CORRESPONDING TO
`
`DESCRIPTOR
`‘I 203
`
`RECEIVE NEXT
`OUTPUT
`
`
`DATA BLOCK [N
`UNDECODED
`
`
`DECODEDATABLOCKUSWG
`INPUT STREAM
`DATA BLOCK
`SELECTED DECDDER{S)
`
`
`
`
`
`OUTPUTDECODED
`DATABLOCK
`
`MORE DATA
`BLOCKS IN INPUT
`STREAM’?
`
`NO
`
`TERMINATE
`DECODING PROCESS
`
`
`
`1218
`
`FTG. 12
`
`

`
`US. Patent
`
`01m3J
`
`00
`
`3fl
`
`US 7,161,506 B2
`
`
`
`
`
`Em_uoocmEmucmnmnEmfioo
`
`4.m_mmauscmm__u_.§8
`
`CmEnoocm
`
`co=_cmoomw_
`
`8E5...
`
`EE£_.6m_<
`
`9.9
`
`<9.maze:
`
`
`
` 5%NM.ow_u_.M_.mEuoocm%emuoucm
`:a_.Emoumm
`
`
`Emu:mawn:_EmEooozEmamzcaoo
`
`MDEuoocm
`
`EEnoucm
`
`mo._mnoocmIon?
`
`2..ED._m_u8:m
`
`7.E250
`
`Eoucmamo185man
`
`flan.
`
`Empam
`
`
`
`
`
`

`
`US. Patent
`
`J
`
`0.,
`
`M...
`
`h
`
`4.3
`
`US 7,161,506 B2
`
`
`
` .W.55..Emaucmanf.mc_E§mn_JBuoocm
`
`._oE_._ommoco_mmE
`
`asooco_mm2n_Eoo
`
`
`
`Sgoacommo€m.__:.owm.525ozmm
`
`mEDmficzoototzm
`
`.mmmm._9::oo.cmt:mmE.&mE:oo_.._m::m_
`
`mm:manor.
`
`mmm._mE:o0:....E:m
`
`
`
`cm.Emucaootmtzm
`
`_.Dm._m~:_.._D.UEmt3m
`
`mom._mE_..oo.cmt:m_
`
`8emE:oo_§Em
`
`
`
`

`
`US. Patent
`
`Jan. 9, 2007
`
`Sheet 19 of 34
`
`US 7,161,506 B2
`
`
`
`Receive Initial
`
`
`Data Biock From
`
`--1400
`
`
`Input Data
`Stream
`
`Count Size of
`
`Data Block
`
`Buffer Data Block
`
`
`
`
`
`Apply Content
`Dependent Data
`Recognition
`
`
`
`
`
`Recognize Data
`Stream Content
`‘?
`
`No—I> B
`
`FIGURE 14A
`
`

`
`US. Patent
`
`Jan. 9., 2007
`
`Sheet 20 of 34
`
`US 7,161,506 B2
`
`
` Compress Data
`
`Block with
`
` ~1-410
`
`
`
`
`Enabled Content
`
`lndependent
`Encoders
`
`
`
`
`Buffer Encoded
`Data Block Output
`
`--‘I412
`From Each
`
`
`
`Encoder
`
`
`
`
`Count Size of
`Encoded Data
`
`
`
`Blocks
`
`Calculate
`
`
`Compression
`Ratio
`
`
`
` Compare
`
`Compression
`Ratios with
`
`1418
`
`
`
`
`
`
`
`Threshold Limit
`
` D
`
`FIGURE 14B
`
`

`
`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
`
`ndependent Threshol-
`1420 «-
`
`
`
`
`
`Append Null
`Descriptor to
`Unencoded Input
`Data Block
`
`
`Select Encoded
`Data Block with
`Greatest
`
`
`
` 1422 ~
`
`Compression Ratio
`
`
`
`
`
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`1424 «-
`
`
`Output Unencoded
`Output Encoded
`Data Block with
`Data Block with
`
`Descriptor
`
`Null Descriptor
`
`
`
`
`
`Data Compression
`Process
`
`Terminate
`
`Receive Next
`Data Block From
`
`Input Stream
`
`More Data
`
`Blocks in Input
`Stream
`?
`
`
`
`
`Yes
`
`1430
`
`FIGURE 14C
`
`

`
`US. Patent
`
`Jan. 9, 2007
`
`Sheet 22 of 34
`
`US 7,161,506 B2
`
`Select Recognized
`1434 -- Data TypelFile or Block
`in List or Algorithm
`
`1436 --
`
`Select Content
`
`Dependent
`Algorithmls)
`
`
`
`Dependent Enooder(s)
`
`Compress Data Block
`1438 ~ with Enabled Content
`
`Buffer Encoded Data
`
`‘I440 --
`
`Block From Each
`Encoder
`
`
`
`1442 W Count Size of Data
`Blocks
`
`
`
`Compression
`Ratio of at Least One
`Encoded Data Block
`Greater Than
`
`
`
`
`
`N°+ F ?
`
`
`
`Content Dependent
`Threshold
`
`«-1 448
`
`1444
`
`Calculate
`Compression Ratio
`
`
`
`
`Yes
`
`+ E
`
`FIGURE 14D
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 23 of 34
`
`US 7,161,506 B2
`
`
`
`
`
`awuoocmEmucmamnEflcoo
`
`_.
`
`MDLmuoucm
`
`EDEuoocw
`
`no_ouoocm_3cm?"tDLmuoocm
`
`Eflcoo
`
`Emucmamo
`
`Ema
`
`co_._:moomm_
`
`o__u__§.wo
`
`cogcmoomm
`
`5Ea:
`
`E_.E_Eom_<
`
`<9.mane:
`
`xuo_m_END
`
`._mE:oo
`
`Ema.
`
`Emmtw
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 24 of 34
`
`US 7,161,506 B2
`
`nmuoucm
`
`55..man.
`
`._oEtummn_
`
`
`
`:_u_mmwEEoUEmocmamo
`
`
`
`hoficommnn_ocmm.E._.
`
`“wok
`
`EDm._mE:oU.:mt_._m_
`
`Cwm._m.c:oo.cmt:m
`
`
`
`mflmm5o_“_
`
`m:__EBmn_
`
`co_mmmaEo0
`
`.~onmm
`
`yofiefi
`
`EEflczooumtsm
`
`_.mLmuoocm
`
`mm_m._mE:oo:mt:mmmBuoucm
`
`mmemzczootmtzmmmLmuoucm
`
`
`
`
`
`EmfioucwEm_ucmdmu_.__EmEo0
`
`
`
`u_o_._mm.E.__.so_wm_ozmmcoammh.:50
`
`
`
`
`
`onmmco_mmmaEoo
`
`
`
`
`
`
`
`U_0£mm:.._._.0>oQ<..cmEOONDm._m~c30O.cmt:m3..Done
`
`_.Dfimucnootmtzm
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 25 of 34
`
`US 7,161,506 B2
`
`
`
`
`
`
`Receive Initial
`
`Data Block From
`
`Input Data
`Stream
`
`-V1600
`
`
`
`Buffer Data Block -«r1604
`
`
`
` Count Size of
`Data Block
`
`
`
`-1602
`
`
`
`Apply Content
`Dependent Data ~1606
`Recognition
`
`
`
`Recognize Data
`Stream Content
`?
`
`
`
`No—I> B
`
`YES
`
`* C
`
`FIGURE 16A
`
`

`
`US. 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
`
`FIGURE 16B
`
`

`
`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 Threshol -
`1620 -
`
`
`Append Null
`Setect Encoded
`Descriptor to
`Data Block with
`
`Unencoded Input
`Greatest
`Data Block
` 1622 ~
`Compression Ratio
`
`
`
`
`
`
`
`
`1624 ~
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`
` 1 B26
`
`
`
`Output Unencoded
`Data Block with
`
`
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`
`
`Null Descriptor
`
`'1 630
`
`
`
`Data Compression
`Process
`
`Blocks in Input
`
`Stream
`?
`
`
`
`
`
`
`Terminate
`
`
`
`More Data
`
`Receive Next
`
`Data Block From
`
`Input Stream
`
`Yes
`
`FIGURE 16C
`
`

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

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 29 of 34
`
`US 7,161,506 B2
`
`
`
`EououcmEmucmawuc_EmEooE_._:m.8mm
`
`
`
`
`
`rm._ouoo:m_
`
`
`
`uni.m__u_\EwQ
`
`ncm:o_=:moumw_
`
`
`
`E£__om_<co__mE_.m_
`
`
`
`mafia»q:.xoo._3
`
`..
`
`0:;
`
`<5manor.
`
`
`
`
`
`EmuoucmEwucmamoEflcoo
`
`MDEuoocm
`
`5Euoucm
`
`
`
`moEuoocm.4own?
`
`Eflcoo
`
`
`
`EDLwuoocw.._Emucmn_mn_Em_mm.%m.
`
`
`.cmun_~._gmn,.m_mucF_B::oo
`
`figmEma
`
`
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 30 of 34
`
`US 7,161,506 B2
`
`umuoucm
`
`.._=323
`
`Lofitummo
`
`:o_mmm.aEoo
`
`mn;._.
`
`§n_.:uwmQ
`
`mc_E..2mo
`
`_._o_mmm.&Eo0
`
`€e_:$m525¢
`
`89.
`
`can_.
`
`mtmanor.
`
`_.Deecsooumtam
`
`NDm.mE:o0.:mE:m
`
`8..:9c=oo_E.sm
`
`EDm._mE_._oo.:mt:m
`
`
`
`_.mw;B:zootmczm
`
`
`
`mm.Emgczootmtam
`
`
`
`mm.m._mE:oo.:mt:m_
`
`Cweflcaootmtzm
`
`
`
`

`
`US. Patent
`
`Jan. 9., 2007
`
`Sheet 31 of 34
`
`US 7,161,506 B2
`
`
`
`
`
`Receive Initial
`Data Block From
`
`Input Data
`Stream
`
`"-1800
`
`Count Size of
`Data Block
`
`M1802
`
`
`
`Buffer Data Block --1804
`
`Apply Content
`Dependent I
`Independent Data
`Recognition
`
`-1806
`
`
`
`Recognize Data
`Stream Content
`?
`
`No+ B
`
`FIGURE 18A
`
`

`
`US. Patent
`
`Jan. 9., 2007
`
`Sheet 32 of 34
`
`US 7,161,506 B2
`
`Estimate Optimum
`Encoder{s) From
`Estimation Algorithms
`
`Compress Data
`Black 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 18B
`
`

`
`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 33 of 34
`
`US 7,161,505 B2
`
` Compression Ratio
`of at Least One Encoded Data
`
`Block Greater Than Content
`
`ndependent Thresho! -
`1820 «-
`
`
`
`
`Select Encoded
`Appefjd "U"
`Data Block with
`Descf19*” *0
`Greatest
`Unencoded Input
` 1322 ..
`Data Block
`
`Compression Ratio
`
`F
`
`
`
`
`
`
`
`E
`
`
`
`Append
`Corresponding
`
`Encoding
`Descriptor
`
`
`
`
`
`1824 -
`
`
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`
`
`Descriptor
`
`Output Encoded
`Data Black with
`
`1 B30
`
`Data Compression
`Process
`
`
`
`
`Blocks in Input
`Stream
`'?
`
`
`Yes
`
`FIGURE 18C
`
`
`
`
`
`
`Receive Next
`Data Block From
`
`Input Stream
`
`More Data
`
`Terminate
`
`

`
`US. Patent
`
`Jan. 9, 2007
`
`Sheet 34 of 34
`
`US 7,161,506 B2
`
`
`
`
`Select Recognized
`
`Data Type:'File or Block
`in List or Aigorithm
`
`
`1838'»
`
`1840 -v Content Dependent
`
`Select or Estimate
`
`Atgorithm( s)
`
`
`
`Dependent Enc.oder(s}
`
`Compress Data Block
`1842 ~ with Enabied Content
`
`Encoder
`New F ~ 1 850
`
` Compression
`Ratio of at Least
`
`One Encoded Data
`Block Greater Than
`
`
`
`
`
`Content Dependent
`Threshold
`
`
`
`Yes
`
`i E
`
`1844 ~
`
`1646
`
`1848
`
`Buffer Encoded Data
`Btock From Each
`
`Count Size of Data
`Blocks
`
`ComCrae::ilateR t'o
`p
`on a I
`
`FIGURE 18D
`
`

`
`US 37,161,506 B2
`
`1
`SYSTEMS AND METHODS FOR DAT.-—\
`COMPRESSION SUCH AS CO.\'I'El'Nl'I‘
`DEPENDENT I).-\'f.'\ COMPRESSION
`
`CROSS-RF.l-'liRl-EN('ii TO RI-"'.I..’\'l'l".|.J
`A PP] -lC.‘_’\' l'lOl"~lS
`
`This application is a Continuation ofU.S. application Ser.
`No. l0r‘tllfi.355 filed on Oct. 29. 200]. is a US. Pat. No.
`6.62435]. which is a C‘ontinuation-In-Part of U.S. patent
`application Ser. No. O9:"i'05.-1-‘lti. filed on Nov. 3. 2000. how
`Il.S. Pat. No. 6.309.4M, issued on Oct. 30, 2001, which is
`a (‘ontinuation of U.S. patent application Ser. No. DW2 [0,
`491. filed on Dec. ]l. 1998. which is now U.S. Pat‘. No.
`6.195.024- issued on Feb. 27. 2001.
`
`BACKGROUND
`
`1. Tecltnical Field
`
`The present invention relates generally to a data compres-
`sion and decompression mid, 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 ntaiuters.
`Discrete inliirntation such as text and numbers are easily
`represented in digital data. This type of data representation
`is known as symbolic digital data. Sytnbolic digital data is
`thus an absolute representation of data such as a letter.
`figure. character. mark. machine code. or drawing.
`Continuous ittfonnation 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
`on. recent advances in very large scale intemtion t'VLSI]
`digital computer technology have enabled both discrete and
`analog infomiation to be represented with digital data.
`Continuous inforniation represented as digital data is often
`referred to as dilfuse data. Dilfuse digital data is thus a
`representation ofdata that is of low in fonnation density and
`is typically not easily recognizable to humans in its native
`form.
`
`-Jr
`
`ll]
`
`15
`
`30
`
`40
`
`-'13
`
`There are many advantages associated with digital data
`representation. For ll'l5Ifll1CL‘-_. digital data is more readily
`processed. stored. and transmitted due to its inherently high
`noise inirnuitity. In addition. the inclusion of redundancy in
`digital data representation enables error detection anclfor
`correction. lirror detection anclfor 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 ofdigital data representation is the continu-
`ing need for increased capacity in data processing. storage,
`and transmittal. This is especially true tbr diflitse 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 :1 given quantity t1fiJ'.lli}n}1atiL111. In general. there are
`two types o 1' data compression techniques that may be
`tttilirred either separately or jointly to eneodefdecode data:
`losslcss and lossy data compression.
`lossy data compression tecliniques provide for an inexact
`representation of the original uncompressed data such that
`the decoded {or reconstructed) data diifers irom the original
`unencodedfuncompressed data. Lossy data compression is
`also known as irreversible or noisy compression. lintropy is
`defined as the quzmtity of in formation in a given set ofdata.
`
`EIU
`
`2
`
`Thas, 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 ltttulan senses to eliminate otherwise impercep-
`tible data. For example. Iossy 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 reconstructed}
`data is identical
`to the original unencodedfttnconipressed
`data. Lossless data c