||||||||||||||||||||||||||||||||IIIIHIII1||||||||||||||||||||||l||||||||||
`
`US007-4| 553032
`
`(I2)
`
`United States Patent
`Fallon
`
`(10) Patent No.:
`
`(45; Date of Patent:
`
`US 7,415,530 B2
`Aug. 19. 2003
`
`SYSTEM AND METHODS FOR
`
`FOREIGN [’A'I'I3N'I' DOC'UMI1‘.N'l"S
`
`.-\C(‘ELERA'l‘ED DAT.-\ STORAGE AND
`RETRIEVAL
`
`_
`DI;
`
`Inventor:
`
`J times .I Fallen. Axiuottk. NY {US}
`
`J; K _?
`7’
`'
`,
`_-1)}-
`4l._75lb
`[(Tot1littl.Ied)
`OTI-IF,R PUBLIC.6t'I‘lONS
`
`Asslgnccl’
`_
`Noltce:
`
`ltjeglhme Data LLC‘ New York‘ NY
`{
`)
`_
`‘
`_
`_
`_
`E3uh_]et:1 In any dtsclalnter. the term ofllttht
`pttteitt is extended or adjusted tmder 35
`*3
`*
`U'S'C' 1‘ 4”?) by 0 day:‘'
`1 1 ISSJAI6
`
`l~.. "Some Practical Universal Noiselctts Coiling Tech-
`Rice. Robe.-rt
`niques". Jet Prepttlsion Laboratory. Pasadena. Otlitbrniti. JPL Pub-
`lictttion T9-22. Mar. I5. l‘J’r"3'_
`
`_
`[CIJl‘]l.lI1lll.’.£”
`.
`.
`-David Y 11113
`Pt'ittiat‘_t' E.t‘a.uit'ner
`[7-'1'} :'I.fmrm’_t‘. xigem, or Firm Ropes & Gray LLI’
`
`(75)
`
`(73 t
`
`(21)
`
`APPL N0’:
`
`(32)
`
`Filed:
`
`Oct. 26. 2095
`
`(57?
`
`*‘“5T“-“‘-"-T
`
`(65)
`
`(63)
`
`Prior Publicafiun Data
`
`US 300730053483 «U
`
`M211‘. 23. 2007
`
`R'~"“9d U» - -“PP“°a‘i"“ Data
`(~nnlinuam._m Gr appltwmiun Na loffifl-L795! med 0“
`JUL 23‘ 2003‘ mm. P“ No‘ 11301913. which is :1
`coutinttatiou of appljcattion No. ()9f266.3l}-1. filed on
`Mal.‘ I 1‘ 1999‘ new pm‘ No‘ 6‘6m_104'
`
`(300591;
`
`1,“_ CL
`G961: [3/00
`U_S_ CL
`Field ufclussififltinn Search
`
`_ -mg,-231
`
`709,231
`70991»;
`See flpplicatim me for complete Search hjsmry‘
`
`References Cited
`,
`,
`__
`, , ,
`, ,
`US‘ P/H LN] DOC UMLN 18
`4!3u;_‘-,r-;_-; A
`| 1,-mg; w,'d;_.,g,en 3. ,,j_
`4.394.774 A
`7.-' I983 Wittengnzn at .‘l_I_
`4.574.351 A
`3.1935 gang 9; ,1],
`4.593.324 A
`691986 (Ihkube et at.
`4.fiS2.t5{) A
`‘I319:-5‘! Mathes et til.
`4.730.348 A
`331938 M:|uC'risken
`
`Systeme and methods for providing accelerated data storage
`and retrieval utilizing lossless data compression and decom-
`press.ion..-1 data storage aCCt2'1CrEilIJl' includes. one ora plurality
`ofhjgli speed data eetiipressioo encoders that are configured
`to sinmltaneously or sequentialiy losslessly compress data at
`a rate equtvaietit to or faster titan the tralistntssioit rate of an
`11111111 data stream. The compressed data It; subseqtlemly
`Smred ‘nawrget ”‘eF'1°’5_’ °““he" smmge def"'§‘3 wl_1°5e‘“P"“
`data storage hEtnd\&']dli1 ts. lower than the Ltrtgittal input data
`stream bandwidtli. Stmtlarly. a data retrieval accelerator
`includes one or :1 plurality of high speed data decontpression
`decoders that are coufigtired to z-iil11l.l]IElllt3lJlIS|y or sequen-
`tially lesslcssly dccenlpress data at a rate equivalent to or
`faster titan the input data strearn from the target mernory or
`storage device. The deeompressed data is then output at rate
`data that
`15 greater than the etitptit rate Iroul the torget
`mentor}? or data storage device. Hie data storage and relneval
`accelerator method and system may employed:
`in a disk
`storage aclttpter to reduce the time required to store and
`retrieve data from computer to disk; in conjttnetion with rau-
`dom access memory to reduce the time required to store and
`retrieve data 1"roi:n random access memory: in :1 display eon~
`[roller to redtlce the time required to send display data. to the
`display cmltroller or processor‘; andtor in tin ilipttlfttutpttt
`controller to reduce the time required to store. retrieve. or
`lranslnil data.
`
`[(‘nntinued J
`
`23 (flairns. 20 Drawing Sheets
`
`8
`__L__
`
`_,_
`man |
`__t_
`
`an
`
`t.~...":..n*....|
`-vuiuuum l
`_l_
`
`._
`
`filth [
`\
`
`‘hd
`
`." "'-.
`
`'E——-at
`
`*_:____l ...
`r_i—--|_
`¢.’.t.....;..
`.-T:..'..1.:.:-~
`I"°:':'3‘:'
`-
`H "‘«\|I::9lIIIi‘! /
`_neun-um:-mu -'
`T
`831
`no
`
`"”
`
`5
`
`Oracle 1101
`
`Oracle 1 101
`
`

`
`US. PATENT DOCUMENTS
`
`4.754.315 I
`4.804 .9 59
`4,870.41 15
`4.372.009
`4.15 76.541
`4388.8 12
`4 306.995
`4.929.940
`-1.9 53 .3 24
`4.965 .6 75
`4.983.998
`5.0209 22
`5.045 .1143
`5.045 .052
`5.046.0 27
`5.049.111‘; 1
`5.091 .752
`5.097.261
`5,1 13.522
`5.121 .542
`5. 1 50.430
`5.1 59.336
`5. 1 75 .543
`5. 179.651
`5. 1 10,795
`5.19145 1
`5.204.756
`5.2 09,220
`5.212.742
`5.2 215.1 :15
`5.2 27.0 95
`5.23 1.49.‘!
`5.: 37.4150
`523 5,5 75
`5.243 .341
`5.243 .348
`5.247,6 38
`5 247.646
`5.2153 . 1 as
`5.2 70.8 32
`5.2 87.420
`5.2 93.3 79
`5,3 07,497
`5.3 09.555
`5.555.490
`5.3 57.6 14
`5.3 -19.0315
`5.379.? 57
`5.381 .145
`5.394.534
`5.5 95.2 23
`5.400.-401
`5.403.059
`5.41:-15.230
`5.406,}! 79
`54 12.334
`5.414.850
`5.4 31.6 39
`5,4 34,9 33
`5.4 52.237
`5 .4 6 1 .6 79
`5.4 07.037
`5.471 .206
`5.4 79.53?
`5.4 33.4 70
`5,486.8 26
`5.495 ,244
`5,506.84-4
`5.506.872
`5.530.845
`5.535 .051
`
`>3-3*>>>3->>>>-21>>>>>>7*>>>>>>2>3*7*>>>>>3='>>>>>>>>>}\*>>>3*>}>>3*>>>>>>->293?->>2b->>';a->>>>
`
`61' 1988
`2-’ I 989
`9:‘ I 989
`101' 1989
`101' 1989
`I2: 1989
`3..-' 1990
`5-‘ 1990
`9.’ I990
`101' 1990
`1-" 1991
`771991
`9! 1991
`9-‘ 199.1
`9.1 1991
`91 1991
`2-‘ I992
`3-‘ I 992
`5.-' 1992
`6-" 1992
`9.’ I992
`10! 1992
`12-’ 1992
`1-’ I 993
`3-‘ 1993-
`3-' 1993
`4.‘ I 993
`5-‘ I993
`51' 1
`7-‘ 1993
`7.‘ 1993
`7-’ 1993
`8-' 1993
`8-‘ I 99.1
`9-’ 1993
`9.’ I993
`91 1993
`9-‘ 1993
`1 [H1993
`121' 1993
`2! 1994
`3." 1994
`4-‘ 1994
`5:‘ 1994
`101' I994
`101 1994
`11' 1995
`I1‘ 1995
`11' 1995
`2-’ 1995
`3.-' 1995
`3-‘ 1995
`4-’ 1995
`4.-' 1995
`4.1 1995
`5.-' 1995
`5-‘ 1995
`5-‘ 1995
`7-‘ 1 995
`9-’ I995
`101' 1995
`I 11' 1995
`1 11' I995
`12-‘ 1995
`111996
`1! 1996
`21' 1996
`41 1996
`41 1996
`6-‘ 1996
`7-‘ 1996
`
`Wrighl
`Mnkansi et 0.].
`Van Maren e1 :1].
`'1’sukiy.'una cl‘ :11.
`Storer
`Dinar: at 111.
`Swanson
`()‘Bri1:n at 111.
`1Iemr1:1.n1:1
`Hori at :1].
`O'Brien
`Huang
`i‘ascur1da
`Milchell cl 3].
`'I‘1La.l'fe el 211.
`Gibson el :11.
`Kmtlse e1 :11.
`Langdcnn. Jr. el 01.
`Dinwiddie. 11'. not al.
`Szymborski
`(‘bu
`Rabin cl‘ al.
`Lantz
`'I'cuL[1‘e cl al.
`Keith et al .
`Ha.-cegawa at al.
`Chevion el al.
`Hi}-a.tIIzL at al.
`Normilc at al.
`Weslnway at :11.
`1311
`Dang] at :11.
`Miller c1 :11.
`Tlannun. .1r.
`Seruussi 141.11.
`Jackson
`O'Brien :1 H1.
`Oslerlund at al.
`'1arm :1 111.
`Balkanskj el al.
`Barret!
`(Tun
`Fcigcl111:1um 1:1 211.
`Akins cl‘ al.
`1"ruvinu at a].
`Palfismn at :11.
`Store!
`1-liynma act
`Allen el al.
`Imlakmvski et al.
`Gamhi
`Wasilewski el al.
`I3;-1311.11 1:1 111.
`Gmyhill et al.
`.-\m11:rson et a1.
`C11a.n.g ct a.1_
`Whiting
`Perkins
`Yam el al
`Di1:ec1.'u
`Normjie £1 a].
`(‘.1111
`Allen e1 :11.
`Campbell cl 111.
`Alur er al.
`Rcmillawd
`Juong cl al.
`11‘-no
`Mahler
`111311 at 11.1.
`.la1r11:5
`
`:11.
`
`US 7,415,530 B2
`Page 2
`
`5.535.356
`5.537.658
`5.557.551
`5.557.668
`5.557.749
`5,561,824
`5.563.961
`5.574.952
`5.574.953
`5.576.953
`5.583.500
`5.590.306
`5.596.674
`5.6041524
`5.606.706
`5.611.024
`5.612.788
`5.613.069
`5.615.017
`5,621,820
`5,623,623
`5.6-15,701
`5.627.534
`5.6.‘-17,995
`5.629.732
`5.630.092
`5.635.632
`5.635.932
`5.638.498
`5.640.158
`5.642.506
`5.649.032
`5.652.795
`5.652.357
`5.652.917
`5.65<-'1,70_'1
`5.655.138
`5.666.560
`5,668,737
`5.671.389
`5.675.333
`5.686.916
`5.694.619
`5.696.927
`5,703,793
`5.715.477
`5.717.393
`5.717.394
`5.719.362
`5.711.958
`5.724.475
`5.729.228
`5.748.904
`5.757352
`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.825.830
`5.832.037
`
`3*>75-J>>3=-3l>}{P>>3“-I>b3=-ivibb->FF'3*>>3=-IF>>.T-‘>Jv>I>>IF'7>>29-3='>>D>>>>I-‘v>3“->33-3*>>2P'>J*3bCb‘.fi->>>>I3*$F~3*3=-:P~>3=-3v>IP3>
`
`74' 1 996
`7’ l 996
`9" 1 996
`951 996
`9.’ l 996
`I 051996
`1011996
`1 F1996
`1 1
`1 9915
`I 1 " l 996
`I 2.’ I 996
`131996
`I "1997
`2.’ 1 997
`2" I 997
`351 997
`31 1 997
`31" 1 997
`3-7 I 997
`4: 1 991
`4!" 1 997
`4-‘ 1 997
`5r 1 997
`51’ I 997
`511 997
`51' I 997
`61”] 997
`6*" I 997
`01199?
`6" 1 997
`61997
`7! 1 997
`7" 1 997
`751997
`7-’ I 997
`8-" I 997
`871997
`9.1997
`9-' l 997
`9-‘ 1 997
`10-'1 997
`I 1’ I 997
`121' 1 997
`1 21' I 997
`1 21' l 997
`271998
`2.1" 1 998
`21 l 993
`.1-' 1 99:3
`3-‘ I 998
`3-’ I 998
`31" 1 998
`511998
`5-’ l 998
`61' I 998
`7.11 998
`74' 1 998
`7." I 998
`71’ l 998
`81' I 998
`81’ 1 998
`9-‘ 1 993
`911998
`91’ I 998
`9" 1 998
`9:‘ 1 998
`I 0.-' I 993
`I 0-’ l 998
`1011998
`1 [I-' 1 993
`1 0-’ l 998
`1071998
`I If I 998
`
`Kim at al.
`Hakka c1 :11.
`(‘rafi
`Brady
`Norris
`Caneiru at al.
`Ryndorluan cl nl.
`Bra;-*.1y et a1.
`Rust at :11.
`H1.1genIob1cr
`Allen el al.
`Walanahe el' .11.
`Bhandari et a1.
`Chui at 211.
`'1'.1.Ica.moto 1:51 :11.
`Campbell at :11.
`Stone
`Walker
`C1101
`Ryndennan el al.
`Kim et a].
`Bakke at :11.
`(Tran
`Millcret a.l.
`Moskowitz at IL1.
`Carruiro at :1].
`Fay at a[_
`Shinngawa 1:1 :1].
`'1'}-111.51" et al.
`Okayama or 31.
`Lee
`Bur: :1 al.
`Dillon ct a1.
`Shimoi 2.1 :11.
`Ma1.1pi11 el 111.
`Clark. 11
`1111111115
`Nice-rLI at :11.
`Her
`Saliba
`Boursier er a1
`Bakmnlllsky
`Kmano
`!\*1a1cDm:1n1d at :4].
`Wise 1:1 21].
`Kikinis
`Nakano ct. 111.
`Schwartz et :11.
`Lee. -01 al.
`Kikinis
`Kirsten
`Franaszek at .1].
`Huang at 111.
`Jericevic et :11.
`Nakazato cl‘ al.
`IJcMo 55 er. :11.
`111131115: et al.
`Rnsmker ct al
`Hashimoto et al.
`Callahan
`lsraelsen cl‘ .11.
`Kawashirrnn al :11.
`Sekinc el al.
`Yaj Ema
`Hannah at al.
`Diaz at :11.
`Lang!-=y
`Wilhers
`Canficld at 111.
`Dubson el al.
`Canfleld et :11.
`Knpf
`Park
`
`

`
`US 7,415,530 B2
`P:3gt:3
`
`5.832.126 A
`5.836.110} A
`5.838.995 A
`5.839.100 A
`5.841.979 A
`5.847.762 A
`5.861.824 A
`5.861.920 A
`5.864.342 A
`5.867.167 A
`5.867.602 A
`5.870.036 A
`5.870.087 A
`5.872.530 A
`5.883.975 A
`5.836.655 A
`5.889.961 A
`5.915.079 A
`5.917.438 A
`5.920.326 A
`5.936.616 A
`5.949.355 A
`5.955.976 A
`5.960.465 A
`5.96-1.842 A
`5.968.149 A
`5.973.630 A
`5.974.235 A
`5.974.471 A
`5.978.483 A
`5.982.723 A
`5.991.515 A
`5.996.033 A
`6.000.009 A
`6.002.411 A
`5.(1tJ_‘1.l15 A
`6.008.743 A
`6.011.901 A
`6.014.694 A
`6.026.317 A
`6.038.725 A
`6.031.919 A
`6.032.148 A
`6.061.398 A
`6.073.232 A
`6.075.470 A
`6.091.777 A
`6.094.634 A
`6.097.520 .—'\
`6.104.389 A
`6.105.130 A
`6.123.412 A
`6.141.053 A
`6.145.069 A
`6.169.241 131
`6.172.936 B1
`6.173.381 B1
`6.182.125 Bl
`6.192.082 B1
`6.195.024 131
`6.195.465 B1
`6.222.886 B-1“‘
`6.235.922 131
`6.226.667 Bl
`6.226.740 B1
`6.253.264 131
`6.272.178 Bl
`6.272.627 B1
`6.272.628 131
`6.282.641 Bl
`6.308.311 Bl
`6.309.424 131
`6.317.714 B1
`
`11.1998 Tflltllkfl.
`11119‘-.18 Sadch
`1111998 dL'Ca.rm::J
`11.11998 Wcgener
`1111998 Sc11u111Dfel 1.1.1.
`1211998 Canfield
`111999 Ryltcl a1.
`111999 Mead cl‘ a1.
`111999 Kajiya eta].
`211999 Dccring
`211099 Znndi el al.
`211999 I-‘ranaszek et. al.
`211999 C1'I::.u
`211999 Domyu E1 :11.
`311999 1\1aril'act n1.
`311999 Rust
`311999 Dcbbek
`611999 '\r'on:1ran.Jr.L-1:11.
`611999 Andn
`T1999 Rentschleret :11.
`811999 'l‘o1'horg..1r.eta.l.
`911999 Panaoussis
`9.11999 Heath
`911999 Adams
`1011999 Packard
`10.11999 Jnquutle at 31.
`1011999 111311111
`l0.'199€‘.' Nunallyet al.
`1011999 Belt
`1111999 Thompson. Jr. ct al
`ll-"1999 Kamatnrii
`1111999 F.=1.11e1:-'11.
`ll-‘I999 (‘hiu-Han
`1211999 Brady
`1211999 Dye
`I2-"1999 Spcarclal.
`1211999 Jaquetle
`112000 Kirsten
`112000 Ahnroniel a1.
`29000 Adiletla
`2121100 Blumenau
`2.211011 Gilbert at al.
`212000 W11kos
`512000 531611 el :11.
`612000 Km-ekerelal.
`6.12000 Little ct .11.
`712000 (iuctz et a1.
`7121100 Ynltagitzt .11.
`8-"2000 Kadniar
`81311110 Ando
`8121100 Wu et :11.
`10.-"2000 Satoh
`101.2000 Situltkonen
`1112000 Dye
`152001 Shitnizll
`112001 Kilazaki
`1.-"2001 Dye
`1-‘"2011! Btwcllu eta].
`2120111 Mnrlnrty at :11.
`2121101 Fallon
`212001 Zandi 61 a1.
`4.-"2001 Yogeshwar
`512001 Norton
`512001 Mutt1icwsct:i.1.
`5.-"2001
`Iga
`6321101 Sebastian
`8121.101 Niewcglowski etal
`8-"2001 Mann
`812001 Aguilar (:1 n1.
`8121.101 Christensen
`1012001 Cnrmichilelelal.
`1012001 Fallon
`11121101 Del Castillo et .11.
`
`375.-240.23
`
`360.18
`
`6.330.622 B1
`6.345.307 Bl
`6.392.567 B2
`6.-404.931 B1
`6.421.387 131
`6.434.168 Bl
`6.434-.695 131
`6.442.659 B1
`6.449.682 Bl
`6.452.602 B1
`6.463.509 Bl
`6.487.640 B1
`6.-489.902 13-2
`6.513.113 Bl
`6.529.633 131
`6.532.121 B1
`6.539.456 B2
`6.542.644 Bl
`6.577.254 B2
`6.590.609 131
`6.597.312 131
`6.601.104 B1
`6.604.040 B2
`6.604.158 131
`6.606.040 132
`6.606.413 131
`6.609.223 B1
`6.618.728 B1
`6.624.761 R2
`6.650.261 132
`6.661.339 Bl
`6.661.845 131
`5.704.840 132
`6.711.709 B1
`6.717.534 B2
`6.731.814 B2
`6.745.282 132
`6.748.457 B2
`6.756.922 132
`6.310.434 B2
`6.856.651 B2
`6.885.316 B2
`6.885.319 132
`6.888.893 133
`6.909.383 132
`6.944.740 132
`7.054.493 132
`7.102.544 Bl
`7.130.913 132
`7.161.506 B2
`7.181.608 B2
`7.190.284 B1
`7.321.937 132
`2001.-10031092 Al
`2001.'0032lZ8 A1
`200110052038 A1
`200210037035 AI
`2002"0080S71 Al
`2002.-0101367 Al
`200210104891 A1
`2002-"01Z'6755 A1
`200210191692 Al
`200310030575 A1
`200310034905 Al
`2003.-'0081-1238 A1
`2003511142874 AI
`200310191876 Al
`2001-1.-‘0042506 Al
`200410073710 A1
`20060015650 A1
`2006.-"0lS144l Al
`200650181442 A1
`20061018-1696 A1
`
`1212001 Schaefer
`212002 Booth
`512002
`Sn1'o1'l
`6-"2002 Chcnetnl.
`712002 Rhee
`812002 Kari
`812002 Esfnhaniclnl.
`812002 Blumcnutl
`9.12002 Toorians
`9120112 Martin
`11.112002 Teomnn at .11.
`1112002 Lipasti
`122002 llcath
`112003 Kobaynshi
`312003 Easwar cl‘ n1.
`3-72003 Rust ctnl.
`312003 Stewan
`412003 53101:
`612003 Rasinussen
`712003 Kilade at al.
`712003
`I"n1lone:1 11.1.
`712003 Fallon
`812003 Kawasaki at 11.1.
`812003 Fallon
`812003 Abdul
`8.2003 Ze-inch
`812003 Wolfgang
`912003 Rail
`92003 Fallon
`1112003 Nelson cl .1].
`132003 Ishidnet .-1|.
`1212003
`I-IeraL11
`312004 Nalawadictal.
`3-"2004 York
`4-'2004 Yol-zoae
`51300-1 Keck elnl.
`62004 01t:u'1:1 et .1].
`612004 Fallon B1111.
`612004 Ossin
`10-"2004
`N-'11l1.'11l.I_il.1|l‘1‘1i1l‘.“-lS\1\‘?i11‘1)‘e11:l1.
`3-“E005 Singh
`4-"2005 Mehring
`412005 Geiger et al.
`512005
`1.1 el al.
`6122005 S11o1cm|1:I.l1iel al.
`912005 Abalictal.
`512006 Schwartz
`9.12006 1.11.1
`1012006 Fallon
`1-"2007
`1‘:-lllon
`212007 Fallon et al.
`312007 Dyectal.
`112008 Fallon
`11.112001 Zack at 11.1.
`1012001
`1'-iopucs
`1212001
`I'a11on B1 .'-1.1.
`3.-"2002 Singh
`612002 Fallon c1 :11.
`E12002 Geiger etal.
`812003 Otto
`912002 Li etal.
`12-E002 Fallonet u.l.
`212003 1‘rac111cnbcige1al.
`212003 Anton ntal.
`5-"2003 Clkiklzl eta].
`712003 Schwanz
`11.112003 Fallon
`312004 Fallonet :11.
`4.-"2004 Fallon
`112006 Fa11nn
`832006 Fallon
`8.-"2006
`l'a1lon
`8-"Z-‘.006 Fallon
`
`

`
`US 7,415,530 B2
`Page 4
`
`2006-"0l9llfi44 Al
`2006.-'(}ll)5filJl Al
`2DlJ7"00r-13939 Al
`200100050514 Al
`3007-"005l}5l5 Al
`20U7."00837=l6 Al
`Elli)?-"0lll9l5-‘l Al
`2007.-’0l09l55 Al
`2007-0109155 Al
`2[JU7I"lll'i'4209 Al
`
`852006 Fallon
`8."20(l6 Fallon
`252007 Fallon eta].
`3."I!00'.F Fallon
`3-“Z007 Fallon
`4.-Q00? Fallon eta].
`5.".llJ0'.F Fallon
`5.-“£007 Fallon
`5-"200? Fallon
`7-'?.0llT Fallon ctal.
`
`FOREIGN PATENT DOCUMENTS
`
`EP‘
`EP
`El-"
`EP
`EP
`El’
`EP
`El’
`GB
`IP
`JP
`JP
`WC)
`W0
`W0
`W0
`
`0164577
`0l8509S
`02 83 793
`0405572
`0493 I30
`05 S74 .3’?-'
`0595406
`0Tl8'I5l
`2162025
`605 1 989
`9188009
`ill-193'?-'6
`W0 9414273
`W0 9429852
`W0 9502873
`W0 9748212
`
`1231985
`61986
`'9? l 988
`1.1991
`T1992
`3! I994
`5' [994
`6-I996
`11986
`2 ' 1904
`T1997
`6-1999
`6- l 99-1
`I21 1994
`D1905
`121997
`
`Oil-lliR PUl3l.l(.‘A'l'lONS
`
`Anderson. J.. ct al. "Codec squeezes color teleconferencing Ihrorlgh
`digital telephone lines“. Electronics I984. pp.
`l I3-I I5.
`VEIIIJIILN. Jack. "A VLSI Chip Set for High-Speed Lossless Data
`Compression". IEEE 'l'ra.ns. On Cireilits and Systems for Video Tech-
`nology. vol. 2. No. -1-4.Dec. 1991. pp. 331-391.
`“Fast Dos Sofl Boot“. lBMTeel1nieal Disclosure Bulletin. I"cb. 1994.
`vol. 37. Issue No. 213. pp. 185-186.
`“OperaJ.i:-lg System Platform Abstraction Method". IBM Technical
`Disclosure Bulletin. Feb. 1995. vol. 33. Issue No. 2. pp. 34 3-344.
`
`Murashitn. K.. et al.. "l'llg.l1-Sp-L'I‘.'t.‘l Statistical Compression using
`Self-organized Rules and l-‘re-zletermined Code Tables". IEEE. I996
`Data Compression Conference.
`Coene. W.. e1 :1]. “A Fast Route For Application of Rate-distortion
`Optimal Qunnt izal ion in an MPEG Video Encoder“ Proceedings of
`the Intemational Conferenrze on Image Processing. l.£I.LIsa.nne. Swit-
`zerland. IEEE. Sep. 16. I996. pp. 525-828.
`Rice. Robert. "Lossless Coding Standards for Space Data Systems".
`IEEE 1055-6393-'97. pp. 577-585.
`Ych. I-‘en-Shu. “The (‘C5135 Lossless Data Co1I1pression Recom-
`mendation for Space ApplicaJ.ions". Chapter lti. Lossless |f.’ornpres-
`sion l-lanrlbook. Elsevier Science {USA}. 2003. pp. 3| l-336.
`Millrnan. llownrd. “lrnage and video compression". Compulerworld.
`vol. 33. issue No. 3. Jan. I3. 1999. pp. T8.
`"IBM boosts your memory". (}eek.com [online]. Jun. 26. 2000
`[relricvodon Jul. ti. 200?]. <U1'(l.: htlp‘. -'-’www.geek.com:'i!)rn-boosta-
`your-memory.-'>.
`"IBM R.crsea.rcl1 Breakthmorrgh Doubles Computer Memory Capac-
`ity“. IBM Press Release [on|ine]. Jun. 26. .'£lJlJ0 [retrieved on .l1.1l.6.
`2001'], <URI..-
`l1|l'pIf'#'\V\N'\H.'-U3.ib111.C0l.‘|'l-'pI'I:s5."llS."I:l'l-"]'lI'EBSrE:lEa.SE
`l653.wss:-.
`“Senre—rWorics To Deliver IBM‘: Memory expansion Technology in
`Next-Generation Core Logic for Servers". Serverworks Press
`Release [online], .lu.n. 27. 2000 [retrieved on Jul. 14. 3000}. <l1RI_..'
`l1tlp:.'.-www.scrvenNork5.co1'na'ncws-'press.' 000627 .html>.
`Abali. B.. el 31.. "Memory Expansion Technology IMXTJ Software
`support and perforrna.nce“. IBM Journal of Resea.rch and Develop-
`u1cnl.vol.45.I5sLIc No. 2. Mar. 200l. pp. 287-301.
`Franaszclr. P. A.. et al.. “Algorithms and data structures for com-
`pressed-mcmory machines". IBM Journal ofResea.1'eh and Develop-
`1Ttonl.\-fol. 45. Issue No. 2. Mar. 2001. pp. 245-253.
`Frnnasmk. P. A_. et a].. "On internn] orga.ni?a.l.ion in eornpreswrl
`random-access memories". lBM Journal of Research and Develop-
`ment‘. vol. 45. Issue No. 2. Mar. 2001. pp. 259-270.
`Smith. T.B.. et al.. “Memory Expansion Teellnology (MXTE C‘om-
`peli1jveiJ't‘lp.=1ct", FBM Journal ofkenearch and Developrnenl.\r'o.-15.
`Issue No. 2. Mar. 2001. pp. 303-309.
`'l're:nai.nc. R. B.. et al.. “IBM Memory Expansion 'l'ec’anology
`{'MX'T}", IBM Jou.l'na.l of Reseamh and DevelopI‘nenL Vol. 45. Issue
`No. 2. Mar. 2001. pp. 271-285.
`
`* cited by examiner
`
`

`
`U.S. Patent
`
`Aug. 19. 2003
`
`Sheet 1 of 20
`
`Us 7,415,530 B2
`
`E35330
`
`Emobm
`
`Ema
`
`_m>mEmm
`
`
`
`._o_.m._m_moo¢
`
`flan
`
`mmfiofi
`
`_BEm_moo<
`
`Ema5%.
`
`Emmhw
`
`8
`
`2»
`
`9
`
`_‘m_~5w_n_
`
`
`

`
`U.S. Patent
`
`Aug. 19, 2003
`
`Sheet 2 anti
`
`Us 7,415,530 B2
`
`200
`
`Receive Initial
`
`
`
`Data Block From
`
`Input Data
`Stream
`
`
`
`
`
`Compress Data
`Block with
`
`202
`
`Encoder(s)
`
`Store Data
`
`204
`
`are Data Blocks in
`
`Input Stream ?
`
`
`
`No
`
`Terminate Storage
`Acceleration Process
`
`
`
`208
`
`
`
`Receive Next Data
`
`
`
`
`
`Block From Input
`Stream
`
`210
`
`FIGURE 2
`
`

`
`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet3 of20
`
`Us 7.415.530 B2
`
`300
`
`302
`
`304
`
`Retrieve Initial
`
`Data Block
`
`
`
`
`
`From Storage
`Device
`
`De-compress Data
`Block with
`
`Decoder(s)
`
`
`
`Output Accelerated
`Data Block
`
` More Data Blocks
`For Output Stream ?
`
`No Terminate Retrieval
`
`Acceleration Process
`
`308
`
`
`
`Retrieve Next
`
`Data Block
`
`
`
`
`From Storage
`.
`Device
`
`
`310
`
`FIGURE 3
`
`

`
`Time Interval
`
`I
`
`I
`I
`
`T1
`
`T3
`
`T3
`
`I
`I
`
`T4
`
`I
`
`I
`I
`
`I
`I
`
`Receive
`:
`Receive
`I
`Receive
`Renews
`:
`Recieve
`:
`Regewe
`I
`Data Block I
`:
`Data Block 4
`I
`Data Block 3
`I Data Block 2
`Data Block 1
`:
`Data Block
`I
`I
`I
`I
` %____4
`
`MET OD 1
`
`I
`I
`
`I
`I
`
`Qgmpfesg
`Data Bmk
`
`Compress
`:
`I Data Block 1
`I
`I
`I
`
`Compress
`:
`I Data Block 2
`I
`I
`I
`
`Compress
`Data Block 3
`
`1
`I
`
`:
`I
`I
`I
`I
`
`I
`I
`
`I
`I
`
`:
`Compress
`Data Block 4 :
`I
`I
`I
`
`Compress
`}
`: Data Block]
`I
`I
`I
`
`I
`I
`
`:
`I
`I
`I
`I
`
`:
`: Store Encoded
`:
`1' Store Encoded
`Store Encoded
`: Store Encoded
`store, Encoded : Store Encoded
`1
`:
`Data Block I
`1
`Il
`Data Block 4
`Data Block 3
`=
`Data Block 2
`Data Block
`5
`Data Block 1
`I
`I
`I
`I
`I
`I
`j
`I
`1
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`!IfiI|:|_QQ_Z
`
`camp.-.355
`Data Black
`
`:
`:
`I
`I
`I
`
`Store Encoded :
`Data Brock
`I
`I
`I
`
`:
`}
`I
`I
`I
`
`1
`I
`I
`5
`
`Compress
`Data Block 1
`
`Compress
`Data Biock 2
`
`Compress
`Data Block 3
`
`:
`:
`I
`I
`I
`
`Store Encoded
`Data Bfock 1
`
`I Store Encoded
`=
`Data Block 2
`I
`I
`
`FIGURE 43
`
`:
`I
`I
`I
`I
`
`=
`I
`I
`I
`
`Compress
`}
`I Data Block (i-1)
`I
`I
`I
`
`: Store Encoded
`I Data Block {I-2)
`I
`!
`
`:
`I
`I
`I
`I
`
`:
`:
`I
`5
`
`
`
`nunI»mus800:"I51'finvwaned‘Sn
`
`
`
`
`
`
`
`Z8l]SS‘SIFI’.Sfl
`
`

`
`Time Interval
`
`I
`
`TH”)
`
`E
`
`I
`l
`I
`:
`I
`
`T(I+2I
`
`-
`Reaewe
`Data Block
`(H2)
`
`E
`
`I
`I
`I
`:
`I
`
`-
`
`v
`I
`Recleve
`I
`I Data Block
`ll
`(H1)
`I
`
`Receive
`Data BIOGK
`
`METHOD 1
`C
`°’"F”5’55
`Data Block
`
`St
`
`d d
`En
`3": B‘|3° If
`a 3 W
`
`I
`I
`I
`Compress
`I
`I
`I Data Black
`I
`I
`I
`I
`I
`{'+1}
`I
`I
`I Store Enccded I
`: Data BIcck
`I]
`I
`U”!
`I
`
`Compress
`Daia Blcck
`9+2)
`
`I
`I
`I
`I
`|
`I
`Stare Encoded I
`Data Block
`:
`{H2}
`I
`
`ET“
`g°t':‘E'f’5i
`3
`°“
`
`I
`I
`I
`I
`
`Compress
`Data Block
`I
`
`I
`I
`I
`I
`
`Compress
`Data Brock
`fi+1)
`
`I
`I
`I
`I
`
`T(n-I-1)
`
`T(n+2}
`
`T"
`
`'
`R
`9"9'V9
`53*? BI‘-"ck
`r[
`
`compress
`Data Block
`n
`
`store Encoded
`Data mock
`:1
`
`Compress
`Data Block
`(M)
`
`Compress
`Data Block
`n
`
`I
`
`I
`I
`I
`:
`I
`
`:
`I
`I
`I
`I
`I
`I
`:
`I
`
`I
`I
`I
`I
`
`Store Encoded
`Dam Block
`
`I
`I
`I
`I Store Encoded : Store Encoded :
`I
`Data Block
`I
`Data Block
`I
`I
`(I-1)
`:
`i
`I
`I
`I
`I
`
`I
`I Store Encoded
`I
`Data Block
`:
`(n-2)
`I
`
`Store Encoded
`Daia Block
`(M)
`
`Store Encoded
`Daia Block
`n
`
`FIGURE 4b
`
`
`
`
`
`__..___.._..__.___.___.______..._..._._____...¢.______..__
`
`
`
`02105loansso0z‘6I'3'W1'J9Wd'S'fl
`
`
`
`
`
`zu0€s'sII~"I.Sn
`
`

`
`
`
`
`
`HZJ9919°l|S8002‘I51'3“\''Jllalfld'S'[']
`
`
`
`
`
`
`
`
`
`Z80‘£S"SIVILSH
`
`‘I”Irr.e Interval
`
`T1
`
`3
`
`3
`
`I
`I
`
`I
`I
`
`Retrieve
`Dege meek
`
`:
`:
`I
`
`Retrieve
`Data Block 1
`
`:
`I
`
`Retrieve
`Data Block 2
`
`Retrieve
`Data Block 3
`
`Decompress
`Data Block 2
`
`Decompress
`Data Block 3
`
`Output Decoded
`Data Block 2
`
`Output Decoded
`Data Block 3
`
`ED.-IQD_‘L
`Deeemp.-eee
`Date meek
`
`I
`Decompresa
`:
`I Data Block 1
`
`I 1
`
`II
`
`Dutput Decoded I Output Decoded
`Date meek
`:
`Data Btock 1
`
`ED2'
`
`I
`
`I
`
`Decomprese
`Data Block
`
`Decompress
`Data Block 1
`
`Deeornpress
`Data Block 2
`
`Output Decoded
`Data Block
`
`Output Decoded
`Data Block 1
`
`HGURE5a
`
`I M
`
`Retrieve
`Data Block 4
`
`Decomprese
`Data Block 4
`
`Decomprees
`Data Block I
`
`Output Decoded
`Data Block 4
`
`Output Decoded
`Data Block I
`
`ll
`
`'
`
`Decomprese
`Data Block 3
`
`Decon-Iprees
`Data Block (i-1}
`
`Output Decoded
`Data Block 2
`
`Output Decoded
`Data Block [I-2)
`
`IIIIIII IIIIIIIIIIII :
`
`II IIIIIIIII I I
`
`‘
`
`II
`
`

`
`Time Interval
`
`TIMI
`
`E
`I
`
`_
`R“-‘"‘°"""
`Data Bloflk
`
`Retrieve
`:
`I Data Block
`:
`I
`
`TIi+2)
`
`Retrreve
`Data Block
`
`METI;IoQ1
`Damm fess
`D ta 8‘:
`k
`a
`
`Dc
`
`O”l‘Jp”ttaDB“I°°:ed
`a
`on
`
`:
`: Decomprass
`I Data Block
`I
`('‘''1)
`E
`E Data Block
`I
`0+1)
`
`Output Decoded
`
`I
`
`1
`
`Decornpress
`Data Block
`{H2}
`
`Output Decoded
`
`Data Block
`0+2}
`
`E
`I
`
`:
`I
`J
`1
`
`:
`:
`I
`I
`E
`E
`:
`
`I
`
`‘I
`
`:
`I
`:
`l
`
`:
`:
`:
`I
`E
`E
`:
`
`I
`
`T"
`
`RBWBVB
`Dam 3106K
`n
`
`pecomptess
`I:IaI.—,I a|oI;I;
`I1
`
`0 I
`
`In
`
`I1 d
`
`ugpauga ISSEIIE
`n
`
`Dgggrgfiggf
`
`°§§?;"é72ii‘
`i
`
`°I§§f;"‘a'?Lii‘
`(H-1)
`
`5
`5
`5
`E
`I
`:
`I
`I
`I‘
`QUIPIII Decoded :0utputDecode-d1‘ Output Decoded :
`Daga BIOGII
`I
`Data Biock
`I
`Data _BIock
`I
`i
`"-13
`‘I
`'
`E
`5
`!
`I
`
`°o°§{2."$'?£°;i‘
`(0-1)
`
`5
`I
`I
`: Output Decoded
`I
`Data Block
`I
`("'3
`5
`
`De-compress
`Data Block
`:1
`
`Output Decoded
`Data Block
`
`(“"13
`
`Output Decoded
`Data Block
`n
`
`FIGURE 5b
`
`
`
`
`
`-..._.__._.I________._.._________._._.._____.¢._
`
`
`
`
`
`02:01.133115soot‘GI'3nv11131134‘Sn
`
`
`
`
`
`ZH0‘E§'SI1="LSfl
`
`

`
`U.S. Patent
`
`Aug.19,2ll08
`
`Sheet 8 of2(}
`
`US 7,415,530 B2
`
`Receive Initial
`
`Data Block From
`Input Data
`Stream
`
`600
`
`B
`
`Time & Count
`Data Block
`
`602
`
`604
`
`606
`
`Compress Data
`Block with
`
`Encoder(s)
`
`Time 8. Count
`Data Block
`
`608
`
`FIGURE 6a
`
`

`
`US. Patent
`
`Aug.19,2008
`
`Sheet 9 of 20
`
`US 7,415,530 B2
`
`610
`
`612
`
`A
`
`
`Determine
`Compression Ratio
`and Bandwidths
`
`Store Data
`
`614
`
`
`
`
`
`
`Modify:
`Input Bandwidth or
`Compression or
`Buffering
`
`' ompression
`Ratio and Input
`Bandwidth
`Compatible
`
`
`
`
`
`
`Receive Next Data
`
`Block From input
`Stream
`
`Yes
`
`ore Data Blocks in
`input Stream ?
`
`NO
`
`Terminate Storage
`Acceleration Process
`
`618
`
`622
`
`Yes
`
`FIGURE 6b
`
`

`
`U.S. Patent
`
`Aug.19,2008
`
`Sheet 10 of 20
`
`US 7,415,530 B2
`
`Retrieve Initial
`
`Data Block
`From Storage
`Device
`
`700
`
`B
`
`Time 8; Count
`Data Block
`
`T02
`
`704
`
`Decempress Data
`Biock with
`
`706
`
`Decode-r(s)
`
`Time 8; Count
`Data Block
`
`708
`
`FIGURE 7a
`
`

`
`US. Patent
`
`Aug. 19, 2008
`
`Sheet 11 M20
`
`US 7,415,530 B2
`
`T10
`
`A
`
` Buffer
`Data Block
`
`712
`
`
`
` Determine
`Decompression
`Ratio and
`
`Bandwidth-s
`
`Output Accelerated
`Data Block
`
`714
`
`
`
`M°d'fY3
`Output Bandwidth
`or Decompression
`or Buffering
`
`713
`
`Decompression
`Ratio and Output
`Bandwigith
`°°‘“|?f“b‘e
`
`
`
`Retrieve Next Data
`
`Block From
`
`
`
`720
`
`722
`
`FIGURE 7b
`
`Storage Device
`
`
`More Data Blocks
`for Output Stream ‘?
`
`Terminate Retrieval
`
`Acceleration Process
`
`No
`
`
`

`
`
`
`
` Bufferlcmlntet 1
`
`Strum
`
`Bufierfcounter 2
`
`Bufierfcounhar 3
`
`Daarminafionr
`Comparison
`
`Encoded Data
`Sh-cam IIW‘
`
`
`
`
`
`
`
`zao£s‘s1v‘.«LSn0110Z1W188I10Z'61'3"V10819:]‘ST!
`
`Bufferfcauntar :1
`
`FIGURE 8
`
`

`
`
`
`
`
`
`
` zao£s‘s1v‘.«LSn01109!WIS9I10Z'6!'3“\’10319:]‘ST!
`
`Data «In? Nut! Daeertpoor
`
`
`
`
`
`FIG. 9
`
`

`
`Video Inpuus}
`
`Data Output
`Stream
`
`
`
`1 020
`
`1030
`
`1040
`
`1050
`
`10
`
`FIGURE 10
`
`
`
`
`
`2805-,‘§"S[1v‘LSH0210PI1391188002"(SI'3"Vlllélfld'S'fl
`
`
`
`
`
`

`
`
`
`:90£§“Slv‘LSnoz1051mans3002151'finv;uaJBd‘Sn
`
`
`
`
`
`-
`*°D2::::*
`
`°
`a
`0
`
`
`
`Display
`n
`orma El’
`
`F
`
`Output
`M
`ENTIOTY
`
`Display
`Pr
`Sam
`063
`
`Dispiay Data
`
`
`
`
`
`D13
`Retrieval
`Accelerator
`
`
`
`80
`
`1110
`
`1120
`
`1130
`
`1140
`
`1150
`
`FIG U RE 1 1
`
`

`
`Parallel Digital
`Data
`
`1210
`
` 1205
`
`
` za0£§‘s1r‘LSnone9:Iaausson:15!‘Rawma1ed'g'n
`
`
`
`Serial Digital
`Data
`
`‘1 235
`
`1 240
`
`1 245
`
`FIGURE. 12
`
`
`
`
`
`

`
`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 17 M20
`
`US 7,415,530 B2
`
`1312
`
`1314
`
`1316
`
`Select Initial
`
`Select Initial
`
`
`Analog Data With
`1300
`Parallel Digital
`5%: ,',';l‘n':'::u':''
`
`Data With Input
`' Mm‘
`Input Analog
`
`Mux
`Mux
`
`
`.
`
`.
`
`.
`
`
`
`Latch Parallel
`Convert Serial
`
`
`
`Digital Input Data
`
`
`Data Format
`
`
`
`
`
`Analog to Digital
`Convert Input
`Signd
`
`1302
`
`
`
`Buffer Digitized
`Analog Data
`
`1304
`
`
`
` Buffer Serial
`
`Buffer Parallel
`Digital Data
`
`Digital Data
`
`
`Compress input Data Block Output Encoded
`
`
`
`Data Block
`
`FIGURE 13
`
`

`
`Analog Data
`
`Parallel Digital
`
`Serial Digital
`Data
`
`
`
`
`
`
`
`29o£s‘s1v‘.«LSn01108!WIS9I10Z'6!'3“\’Jllawd‘ST!
`
`
`
`
`
`Data
`Retrieval
`
`Serial Data
`Interface
`
`1435
`
`1440
`
`1445
`
`FIGURE 14
`
`

`
`U.S. Patent
`
`Aug.19.2008
`
`Sheet 19 of 20
`
`US 7,415,530 B2
`
`1500
`
`
`
`Receive Initial
`Data Block
`
`
`
`Decompress Data
`Block
`
`1 502
`
`
`
`'
`
`1512
`
`Data Serial
`Data
`
`
`
`Digital Parallel
`Data ?
`
`NO
`
`1510
`
`
`
`Yes
`
`
`
`I ata Digitiza n
`Analog Data
`9
`
`
`
`Yes
`
`
`
`Buffer Digitized
`Analog Data
`
`B
`
`1514
`
`Buffer Parallel
`
`Digital Data
`
`Buffer Serial
`
`Digital Data
`
`FIGURE 15a
`
`

`
`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 20 of 20
`
`Us 7,415,530 B2
`
`Digital to Analog
`Convert Data
`
`1 520
`
`
`
`Demux Digital
`Parallel Data
`
`1524
`
`1528
`
`Output Analog
`Data
`
`1522
`
`Output Parallel
`Digital Data
`
`1525
`
`Output Serial
`Digital Data
`
`1530
`
`More Data
`
`No
`
`Blocks in Input
`Stream ?
`
`
`
`1532
`
`Reoeive Next
`
`Data Block
`
`1534
`
`FIGURE 15b
`
`

`
`US 1415.530 B2
`
`1
`SYSTEM AND METHODS FOR
`ACCEIJZRATED D.-STA S1l()RAGE AND
`RETRIEVAL
`
`This application is a continuation ofU.S. patent applica-
`tion Ser. No. 103628.795. filed on Jul. 23. 2003. now U.S. Pat.
`No. 7,130,913. which is a continttation ol'1J.S. patent appli-
`cation Ser. No. l)9X266.39-1 tiled on Mar 1 l..
`.1999. now US.
`Pat. No. 6.601.104, both ol'wbicl1 are hereby incorporated by
`reference lterein in their entirety.
`
`I3./\Cl(GROlJNl)
`
`l . Technical liield
`
`The present invention relates generally to data storage and
`retrieval and. more particularly to systems and methods for
`improving data storage and retrieval bandwidth utilizing loss-
`less data contpression and decompression.
`2. Description of the Related Art
`Information may be represented in a variety of manners.
`Discrete infonnatitui such as text and numbers are easily
`represented in digital data. This type ofdata representation is
`known as symbolic digital data. Symbolic digital data is thus
`an absolute representation oi‘ data such as a letter. Iigure.
`character. mark. machine code. or drawing.
`Continuous inforntation such as speech. music. audio.
`images and video frequently exists in the natural world as
`analog infortnation. As is well-l-tnown to Lhosc skilled in the
`art, recent advances in very large scale integration (\’LSI]
`digital computer technology have enabled both discrete and
`analog ittlortnatioti to be represented with digital data. Con-
`tinuous information represented as digital data is often
`referred to as diffiise data. Diflitse digital data is thus a rep-
`resentation of data that is of low ir1l'ormation density and is
`typically not easily recogitizablc to humans in its native form.
`'Il.tere are many advantages associated with digital data
`representation. For instance. digital data is more readily pro-
`ccssed. stored. and transrnitted due to its inherently high noise
`immunity. In addition. the inclusion of redundancy in digital
`data representation enables error detection andfor correction.
`Error detection andfor correc.tion capabilities are dependent
`t.Ipon Lite amount and type ofdata rcdttndancy. available error
`detection and correction processing, and extent of data cor-
`ruption.
`One outcome ofdigital data representation is the continu-
`ing need for increased capacity in data processing. storage.
`and transmittal. This is especially true for dilliise data where
`increases in fidelity and resolution create exponentially
`greater quantities ol'data. Data compression is widely used to
`reduce the amount of data rcqtlircd to process. trt-;tnst11it_. or
`store a given quantity ol'inl'ormation. In general. there are two
`types of data cotnprcssion techrtiques that may be utilized
`either separately orjoirttly to encodeldecodc data: lossy and
`lossless data compression.
`Lossy data compression techniques provide for an inexact‘
`representation oftlte original uncompressed data such that the
`decoded tor reconstructed} data ditlers from the original
`ttnencodedfuncotnpressed data. l.os5ty data compression is
`also known as irreversible or noisy compression. Negentropy
`is defined as the quantity olinl’ortnation in a given set of data.
`Tltus, one obvious advantage oflos sy data compression is that
`the compression ratios cart be larger than that dictated by the
`negentropy limit. all at the expense of inl'ormation content.
`Many lossy data compression techniques seek to exploit vari-
`ous traits within the human senses to eliminate otherwise
`imperceptible data. For example. lossy data compression of
`
`Ur
`
`lt.I
`
`15
`
`40
`
`-'13
`
`St‘:
`
`=1: ‘J:
`
`6|]
`
`2
`
`visual imagery might seek to delete inlbnrtation content in
`excess of the display resolution or contrast ratio of the target
`display device.
`On the other hand_. lossless data compression techniques
`provide an exact representation ofthe original uncompressed
`data. Simply stated. the decoded (or reconslnteted} data is
`identical to the original tmencodedluncompressed data. Loss-
`less data compression is also known as reversible or noiseless
`compression. Thus. lossless data compression has, as its cur-
`rent limit, a minimum representation defined by the negent-
`ropy of a given data set.
`It is well known within the current an that data compres-
`sion provides several unique benefits. First. data compression
`can reduce the time to l.l':lD5l'l'lll data by more cliicicntly ttti-
`lizing low bandwidth data links. Second. data compression
`economizes on data storage and allows more itdotmation to
`be stored liar a Fixed memory size by representing infomiation
`more efficiently.
`One problem with the current art is that existing memory
`storage devices severely limit the perfonuanoc ofcrwrtstttner,
`entertairunent, ollice. worl>:sl'ation. servers. and ]1‘1£tiI‘lli’EII't‘tt}
`computers for all disk and memory intensive operations. For
`example. magnetic disk mass storage devices currently
`employed in a variety ofliome, business. and scicntilic com-
`puting applications suffer lrom significant seek-time access
`delays along with profound read./write data rate limitations.
`(.‘u11'ently the lastest available (10,000) rpm disk drives sup-
`port only a 17.1 Megabyte per second data rate (lVll3:‘sec].
`This is in stark contrast to the n1odernPersooal Cornputer‘s
`Peripheral Component lntercomtect (PCT) Bus‘ s inputfoutput
`capability of 264 MBi’sec and internal local bus capability of
`S00 Mlifsec.
`
`Another problem within the current art is that emergent
`high perfornrartce disk interface standards such as the Small
`Computer Systems Interface (SCSI-3] and Fibre Cliannel
`offer only the promise of higher data transfer rates thronglt
`intermediate data bttliering in random access memory. These
`ititerconnect st'rat'egies do not address the fundamental prob-
`lem that all modern magnetic disk storage devices for the
`personal compttter marketplace are still limited by the same
`physical media restriction of l ?.l MB2'sec. Faster disk access
`data rates are only achieved by the high cost soltttion of
`simultaneously accessing multiple disk drives with a tech-
`nique krtown within the art as data striping.
`Additional problems with bandwidth limitations similarly
`occur within the art by all other tonne of sequential. pseudo-
`random_. and random access mass storage devices. Typically
`mass storage devices include irtayetic and optical tape. mag-
`netic and optical disks. and various solid-state mass storage
`devices. It should be noted that the present invention applies
`to all forms and manners of memory devices including stor-
`age devices utilizing magnetic. optical. and chemical recli-
`niques. or any contbination thereof.
`
`SUMMARY OF THE lNV'EN'l"JON
`
`The present inventiorr is directed to systems and methods
`For providing accelerated data storage and retrieval by utiliz-
`ing lossless data compression and decompression. The
`present invention provides an effective increase of the data
`storage and retrieval bandw