||||||||||||||||||||||||||||||||Illllllll|||l||||||||||||||||||l||||||||||
`
`US007-’-ll 553032
`
`(12) United States Patent
`Fallon
`
`(10) Patent No.:
`(45; Date of Patent:
`
`US 7,415,530 B2
`Aug. 19. 2008
`
`(54) SYSTEM AND METHODS FOR
`
`FOREIGN [’A'I'l3N'I‘ DOC'UMI~‘.N'l‘S
`
`.-\C(‘E[.ERATED DAT.-\ STORAGE AM)
`RETRIEVAL
`
`_
`DI;
`
`_?
`‘
`3,
`_
`,
`_. U9-
`413512:
`[(Tol1linl.Ied)
`OTI-ll3.R PUBLlC‘.‘5£l‘lONS
`
`l~.. "Some Practical Universal Noiselcas Coiling Tech-
`Rice. Robe.-rl
`niques". Jet Proptllsiun Laboratory. Pasrtdenu. Chliforniii. JPL Pub-
`liczttion T9-22. Mar. I5. l‘J’r"3'_
`
`[Colilinlledl
`-D'ividYl"11g
`}’r'iiiiar‘1'F\‘aiiiiner
`[7-1} :'l.f."DJ"m.-‘_I‘. xigem, or Firm Ropes 8'. Gray LLP
`
`System; and methods for providing accelerated data storage
`and relrli.-val utilizing lossless (J;-itn compression and decom-
`press.io1J..-1 data storage accelerator includes. one or ‘:1 plurality
`oflijgli speed data conipressiou encoders than are configured
`to siniultancously or sequentially losslessly compress data at
`fl rate equivalent to or faster than the Ir.1nsmissiou rate ofzm
`input data stream. The compressed data 18 subsequently
`Smred inawrget ”‘eF'1°’5_’ °““he" Slomge defmfe Wlmseinpul
`data storage l3ElnCl\lr'ldll1 is lower than the original input data
`strewn l3."iI1Cl\\r'ldI1‘l. Similarly. a data retrieval accelerator
`includes one or :1 plurality of high speed data decompression
`decoders that are cuilfigurcd to z-3il11l.llIElllt3lJllSly or sequen-
`lially losslcssly deconlprcss data at a rate equivalent to or
`faster tlian the input data stream from the target ineruory or
`storage device. The deeumpressed data is then output at rate
`data that
`is greater than the uulpul. rate from the large!
`m I W rd M 1 r , dcv.
`Th dam t r ,
`Id 1.‘, I
`l;‘.l'llJ_D 8'5-O.’-.l1:L.‘
`ICE.
`(3
`'5-i-l.'ls':lt.l'.‘fl.l
`l'L?l'lLc'J
`accelerator method and system may employed:
`in a disk
`slum c ada ter to reduce the time
`1 uinccl
`to store and
`relriefire dalaplrom computer to disk; iii-:|111_i1tIictiL1i1 with rau-
`clnm access memory to reduce the time required to store and
`retrieve data l"ron:| raitdom access memory: in :1 display con~
`[roller to reduce the lime required to send display data. to the
`display colltmller or processor; andlor in an iliplilftiulptll
`controller to reduce the time required to store. retrieve. or
`transmit data.
`
`(22)
`
`Filed:
`
`Oct. 26. zone
`
`(57)
`
`*‘“5T“-“‘-"-T
`
`(75)
`
`Inventor:
`
`J nines .I Fallon. Annoiik. NY {US}
`
`(73)
`
`.L\ssigt1r.-c:
`
`_
`l_ * ) Notice:
`
`[21 ) APPL Nu’:
`
`llealtime Data LLC. New York. NY
`{US}
`_
`_
`_
`‘
`_
`.Sul:I_]et:1 In any dlsclalnter. llie term ofllus
`patent is cxteiidcd or adjusted lnlder 35
`U'S'C' 154"?) by 0 days’
`l“553‘426
`
`(65)
`
`Prior Publicafiun Data
`
`US 1"-007ml-)5-»"483 fil
`
`Milli 33- 2007
`
`R'~"“9d U» - -“PP“°a‘i"" Data
`(63) Conliituatioii of application No.
`l0f62H,795, [lied Q“
`JUL 28‘ 2003‘ mm. P“ No‘ 11301913. which is :1
`continuation of application No. ()9f266.3l}-1. filed on
`Mal.‘ I 1‘ 1999‘ new pat‘ Na‘ 6‘6m_104'
`
`[51 }
`
`(56)
`
`1,“_ CL
`Gag]: ‘I3/go
`U_S_ CL
`tsz)
`(58) Field ul.Clussifimmun Search
`
`f2()[]fi_{)])
`
`
`
`-mg,-231
`.mgJ,23l_
`709933
`See ztpplication file for complete searclihjstory.
`References Cited
`,, ,
`,,
`__
`,,
`US‘ P/H EN] DOC UMEN 18
`4!3u;_‘-,r-is A
`| 1,493; widcrgren 3. ,,]_
`4,394,?‘r4 A
`7.-' I983 Widergren e1 .‘l_I_
`.1.5',r.1.3 51 A
`3.1935 gang 9; ,1],
`4.593.324 A
`691986 (Ihl-ntboet al.
`4.fiS2.15{) A
`T.'19S‘i' Maihes el ul.
`4,73fJ._348 A
`331938 .\a'l:|uC'risken
`
`[(‘rmtinued J
`
`23 (flairns. 20 Drawing Shel.-ts
`
`A I
`__L_*
`
`mm at:
`_,_
`__i_
`
`~=~.».e‘:-:.-'.~.=-l
`.1
`,
`...... g
`
`..
`
`~»
`l’§“3"»'-
`1“ l \ —’Q “°
`W
`
`Oracle 1001
`
`Oracle 1001
`
`

`
`U.S. PATENT DOCUMENTS
`
`4 .754.35 1
`4.304 .9 59
`4370.4 15
`4.372.009
`4.375.541
`4333.3 12
`4.905.995
`4.929.945
`4.953.324
`4.955 .5 75
`4.933.993
`5.023.922
`5.045 .343
`5.045 .352
`5.045.027
`5.049.113 1
`5.091 .732
`5.097.251
`5, 1 1 3 .522
`5. 1 2 1 .342
`5. 1 50.430
`5.1 59.335
`5. 1 75 .543
`5. 1 79.55 1
`5. I 37.793
`5. 1 9 1 .47 1
`5.204.755
`5.209.220
`5.212.742
`5.2 25.1 75
`5.227.393
`5.23 1.492
`5.237.450
`5.237.575
`5.243 .341
`5.243 .343
`5.247.533
`5.247.545
`5.253 . 1 53
`5.270.332
`5.237.420
`5 .2 93.3 79
`5.307.497
`5.309.555
`5.355.493
`5.357.5 14
`5.379.035
`5.379.757
`5.33 1 . 1 45
`5.394.534
`5.395.223
`5.400.401
`5.403.539
`5.405.273
`5.405.279
`5.4 12.334
`5,4 14.3 50
`5.431.539
`5.434.933
`5.452.237
`5.451.579
`5.457.037
`5.471 .205
`5.479.537
`5.433.470
`5,435,325
`5.495.244
`5.505.344
`5.505.372
`5.530.345
`5.533.051
`
`>23-3*>>>>>}>>-21>29>>>~>7*>>J>"#>>2>3*l\*>>>>>37?39>>>>‘#>>}\*>>>3*>>>>3*>>29->>>>3v3a->>2b->>3*>>>'#
`
`61' 1988
`231939
`9.‘ I939
`1132' 1989
`10.’ 1989
`I2.‘ I989
`3.-' 1990
`5.'19*.‘I0
`9." 1990
`I.[].'' 1990
`1-’ 1991
`7.’ I991
`99' 1991
`9-' 1991
`9.’ 1991
`911991
`251992
`351992
`5-' 1992
`6-’ 1992
`9.’ 1992
`1031992
`12-’ 1993
`111993
`2.‘ I993
`3-’ I993
`4.'I993
`55 1993
`51' I
`7-‘ 1993
`7-‘ 1993
`7-’ 1993
`831993
`8-‘I993
`911993
`9.’ 1993
`91’ 1993
`9-" 1993
`1 IR 1993
`12.-‘ 1993
`E! 1994
`331994
`4.‘ 1994
`531994
`I U3 I 994
`101' 1994
`111995
`1.’ I995
`12' 1995
`2-’ 1995
`3." I995
`3-‘ 1995
`471995
`4." I995
`41' 1995
`5.11995
`5-' 1995
`5-‘ 1995
`771995
`9-’ I995
`10.’ 1995
`I 131995
`I 12' 1995
`12.‘ 1995
`1-’ 1996
`1-" 1996
`21' 1996
`41' I995
`41' 1996
`6-' 1996
`791996
`
`Wright
`Makanai 121 3.1.
`Van Maren :71 3.1.
`'1’3uk1y.'un'.=1 cl‘ :11.
`Storer
`DI.'.‘lI1fl at 01.
`Swanson
`()‘B1'i1:n at 111.
`11emn:u:u:1
`Hori at :1].
`O'Brien
`Huang
`i‘:1sc0nda
`.’V1iI'ch0II at a].
`T3.11.170 el 711.
`Gibson el :11.
`1.’.m10ae e1 01.
`Langdcnn. J1". el 31.
`Dinwiddie. Jr. 01 al.
`Szymborski
`(‘I111
`Rabin cl‘ al.
`Lantz
`'1'a.11.[11 el al.
`Keith et al .
`Hasegawa at al.
`Chevion el al.
`Hi}-m11zL et al.
`Normilc 51 -.11.
`Wcslnway et :11.
`1311
`Dang] at :11.
`Miller c1 :11.
`Tlannun. .1r.
`Semussi 01.11.
`Jackson
`O'Brien et 81.
`Oslerlund at al.
`'1arm ct 111.
`Ba.1ka.n3kj el al.
`Barret!
`Carr
`Fcigc11l1:111m 1:1 91.
`Akins cl‘ al.
`Pruvinu at 3].
`Paltismn at al.
`Storer
`Hiy11m.1 121 :11.
`Allen el 21.1.
`K11l11}.'0w5ki 121 111.
`Gamhi
`Wasilewski el al.
`13;-1311.11 1:1 111.
`Grnyhill et a1.
`:\m1urs011 et 1'11.
`C113.n.g (:1 21.1.
`Whiting
`Perkins
`Yam el 5|
`Di::ecL'U
`Normjle 121 :1].
`(Thu
`Alien 01 21.1.
`Campbell Cl 111.
`Alur er al.
`Rcmi|1:u'<1
`Juong 01 31.
`Rae
`Mahler
`111311 101 11.1.
`.1a1r1c3
`
`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.604.824
`5.606.706
`5.611.024
`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.638.498
`5.640.158
`5.642.506
`5.649.032
`5.652.795
`5.652.857
`5.652.917
`5.654.702
`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.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.825.830
`5.832.037
`
`3*>3*J>>3°-3l>i>vJ*3>>3“-I>IP3=-3>>>>~FF*3*>->3?-IF>3-Ii‘*L\v>I>>I>7>>>3=->>J>>>Cfilb>3“->33-3*>>2P'I>J*3b.7=“.fi->I>>>I>3>3='>2P~>3=-3>>IP3>
`
`71' 1 996
`7’ I 996
`9-" 1 996
`9-'1 995
`9.’ 1 996
`1 0.51996
`III! 1996
`1 F1996
`1 1
`1 995
`I 11996
`1 2." I 996
`131996
`I "1997
`2.’ 1 997
`2" I 997
`351 997
`3’ 1 997
`31" I 997
`3-5 I 997
`4- 1 997
`4!" 1 997
`4.‘ 1 997
`5r I 997
`5:‘ I 997
`531 997
`5r" 1 997
`5-1 997
`6*" I 997
`511997
`5-’ 1 997
`65 I 997
`7" I 997
`7" I 997
`7.-" 1 997
`7.’ I 997
`8:‘ I 997
`811997
`951997
`9.’ 1 997
`9'1 997
`I 051 997
`1 1-“ I 997
`12.-' 1 997
`1 22' I 997
`I 21' 1 997
`271998
`22' 1 998
`27 1 998
`2-“ 1 993
`3-‘ I 998
`3-’ I 998
`3-" 1 998
`51' I 908
`5.’ 1 998
`62 I 998
`7.11 998
`71' 1 998
`7." I 998
`7:" I 998
`8-1' I 998
`81’ 1 998
`9-‘ 1 993
`971998
`91’ I 998
`9" 1 998
`9-’ 1 998
`I 0.-' I 998
`I 01' I 098
`10.51998
`1 I1" 1 998
`1 0-’ I 998
`1011998
`1
`I41 998
`
`Kim at al.
`Bakkc c1 :11.
`(.‘ra1"I
`Brady
`Norris
`Caneiru et al.
`Ryndcrlnan cl nl.
`Bria.-*.ly (:1 31.
`Rust 01 :11.
`I-11.1genIobIn2r
`Allen el al.
`Watanahe el :1].
`Bhandari et a1.
`Chui el ELI.
`'1'a.Ica.moto el :11.
`Campbell c1 :11.
`Stone
`Walker
`C1101
`Ryndennau el 31
`Kim et 3].
`Bakke et :11.
`(Tran
`M11131’ et a1.
`Moskowitz el :11.
`Carr;-ire 013.1.
`Fay at al.
`Shinrlgawa 1:1 3].
`'l'y1c1' et a1.
`Okayama et 31.
`Lee
`Burl el 3].
`Dillon at 3.1.
`Shimoi 2.1 31.
`Ma1.1pi11 el 111.
`Clark. 11
`Kikinis
`Moe-rLI at :11.
`Her
`Saliba
`Boursier er a1
`Baklunulsky
`Kmano
`!\1a1cD01:1n1d at :4].
`Wise 1:1 3].
`Kikinis
`Nakano cl. 111.
`Schwarlz el :11.
`1.09.01 31.
`Kikinis
`Kirsten
`Franaszek at 111.
`Hmtrag. et 9.1.
`Jericevic et al.
`Nakazato Cl‘ 31.
`DcM0 53 at al.
`131011: et a1.
`Rnsloker 01 al
`Hashin-1015 01 al.
`Callahan
`lsraelsen 01.11.
`Kawashim al :11.
`Sekinc at al.
`Ya_1'1ma
`Hannah 01 0|.
`Diaz 31 a1.
`141113153’
`Withers
`Canficld at :11.
`'DuIJ5on el al.
`C‘anI'1elcl et :11.
`Knpf
`1-‘ark
`
`

`
`US 7.415.530 B2
`P:3ge3
`
`5.832.126 A
`5.836.003 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.886.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.733 A
`5.991.515 A
`5.996.033 A
`6.000.009 A
`6.002.411 A
`6.00.1115 A
`6.008.743 A
`6.011.901 A
`6.014.694 A
`6.026.317 A
`6.038.725 A
`6.031.939 A
`6.032.148 A
`6.061.398 A
`6.073232 A
`6.075.470 A
`6.091.777 A
`6.094.634 A
`6.097.530 .—'\
`6.104.389 A
`6.105.130 A
`6.123.412 A
`6.141.053 A
`6.145.069 A
`6.169.241 B1
`6.172.936 B1
`6.173.381 131
`6.182.125 131
`6.192.082 B1
`6.195.024 131
`6.195.465 B1
`6.222.886 Bl “'
`6.235.922 131
`6.226.667 Bl
`6.226.740 B1
`6.253.264 131
`6.272.178 Bl
`6.27".‘-1.627 B1
`6.272.628 131
`6.282.641 B1
`6.308.311 B1
`6.309.424 131
`6.317.714 131
`
`1171998 Tnmlkn
`1171998 Sadch
`1171998 dL'Ca.rmr.3
`1171998 Wagoner
`11-"I998 Schulhofet 71].
`1271998 Canfield
`171999 Ryucl a1.
`171999 Mead cl'a1.
`171999 Kajiya eta].
`271999 Decrlng
`21999 Zandi el al.
`291999 I-'1-anaszcket al.
`271999 C'1'I::'LI
`231999 Uumyu el :11.
`371999 Naritact n1.
`371999 Rust
`371999 Dcbbek
`671999 '\r'c-n:l.ran.Ir. E1111.
`671999 Andra
`731999 Reutsclllerel 211.
`8-“I999 1urh0rg.Jr.eta.l.
`9-‘ 1999 Panaoussis
`971999 Heath
`971999 Adams
`1071999 Packard
`1071999 Jnquutle at 31.
`1071999 1163111
`l0.'1990 Nxlnallyet al.
`1071999 Belt
`11-‘I999 Thompson. Jr. cl al
`1171999 Kamatnni
`1171999 Falletal.
`11-‘I999 (‘hiu-fiao
`1231999 Brady
`12.1999 Dye
`1231999 Spcarclal.
`1771999 Jaquetle
`132000 Kirsten
`172000 Almroniel 31.
`22000 Adilctla
`272000 Blumenau
`252000 Gilbert :1 al.
`212000 W11kos
`572000 531011 el :11.
`672000 Km-ekerelal.
`672000 Little ct .11.
`792000 (30:12 :31 a1.
`772000 ‘1'a]1agit:t .11.
`8-"2000 Kadnier
`872000 Amio
`8721100 Wu et :11.
`10.-"2000 Saloh
`1072000 Saultkonen
`1172000 Dye
`1-‘"2001 Shimizll
`193001 Kilazaki
`172001 Dye
`152001 Booclln eta].
`2.-'200l Mnrlanyetnl.
`272001 Fallon
`272001 Zandi 6131.
`4.-"2001 Yogeshwnr
`57200] Norton
`5.-‘"2001
`1V11II‘111i.'f\\?S01.:1.1.
`5.-"2001
`lga
`632001 Sebastian
`872001 Niewcglowski elal
`8-".2001 Mann
`832001 Aguilar cl n1.
`872001 Christensen
`107200] Carmichtlelu-.1111.
`1072001 Fallon
`1172001 1ZIe1('asIillo eml.
`
`375.-240.23
`
`6078
`
`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 131
`6.449.682 Bl
`6.453.602 B1
`6.463.509 Bl
`6.487.640 151
`6.489.902 13-2
`6.513.113 Bl
`6.529.633 Bl
`6.532.121 B1
`6.539.456 B2
`6.542.644 Bl
`6.577.254 B2
`6.590.609 B1
`6.597.812 131
`6.601.104 B1
`6.604.040 R2
`6.604.158 131
`6.606.040 B2
`6.606.413 B1
`6.609.223 B1
`6.618.728 131
`6.624.761 DE
`6.650.261 132
`6.661.339 Bl
`6.661.845 131
`6.704.840 B2
`6.711.709 B1
`6.717.534 B2
`6.731.814 B2
`6.745.282 B2
`6.748.457 BE
`6.756.922 132
`6.310.434 B2
`6.856.651 B2
`6.885.316 B2
`6.885.319 132
`6.888.893 B2
`6.909.383 132
`6.944.740 132
`7.054.493 B2
`7.102.544 131
`7.130.913 132
`7.161.506 B2
`7.181.608
`2
`7.190.284 B1
`7.321.937 132
`200170031092 Al
`200130032128 A1
`200170052038 A1
`20027111137035 AI
`?.002"0080S71 Al
`200270101367 Al
`200270104891 A1
`2002-"01Z'6755 A1
`2002.-0191692 Al
`200370030575 A1
`2003-."003490S Al
`200370084238 A1
`200370142874 AI
`200370191876 Al
`2004.-‘0042506 Al
`200470073710 A1
`200670015650 A1
`200650181441 A1
`200670181442 A1
`20067018-1696 A1
`
`1272001 Schaefer
`272002 Booth
`552002 Sm-oh
`6-"2002 Chcnetal.
`732002 Rhee
`832002 Kaxi
`852002 Esfnhanicl 1-11.
`87200.?
`lilumenntl
`9-".3002 Toorians
`972002 Morein
`1072002 Teomnn at .11.
`1105002 Lipasti
`132002 11¢-alh
`152003 Kobaynshi
`3.12003
`13aswa.rcl'n1.
`3-"2003 Rust eta].
`372003 Slewan
`472003 53101:
`672003
`R3Sll'l1.15!il3l'I.
`732003 Kilade e1. :11.
`7-‘"2003
`I".'l1lone1 11.1.
`772003 Fallon
`82003 Kawasaki E1 11.].
`872003
`1-‘allon
`8-‘"2003 Abdal
`8.9003 Ze-inch
`872003 Wolfgang
`970.003 Rail
`92003 Fallon
`1112003 Nelson clal.
`1272003
`Ishidnetal.
`1272003
`I-1emLl1
`372004 Nalawadictal.
`3-"200-4 York
`472004 Yokoae
`57200-1 Zack E1711.
`672004 Okiuia el .1].
`6-"2004 Fallon 81 al.
`672004 Ossin
`10-"2004 Muthujulnaraswalhy el :11.
`3-“E005 Singh
`-4721105 Mehring
`452005 Geigeret al.
`572005 Li el :11.
`673005 Sllolcmllnhiel :11.
`972005 Abalictal.
`512006 Schwartz
`972006 ‘Lin
`1032096 Fallon
`1-‘"2007
`I‘:-1114.-m
`272007 Fallon at al.
`352007 Dyectal.
`172008 Fallon
`1032001 Zack El :1].
`10-""2001
`1'-Iopucs
`12-13001
`lmllon 813.1.
`372002 Singh
`67200.’! Fallon 01:11.
`872002 Geiger elal.
`8-“"2002 Dtlo
`972002
`1-101111.
`1.’.-200.‘! Fallonet Ell.
`2.7‘:-‘.003
`1‘l'a.ch1cnbcJg.e1 al.
`272003 Anton otal.
`5—'}':'003 C|l\:ik1:1 alal.
`772003 Schwanz
`1072003 Fallon
`372004 Fallonetul.
`4.72004 Fallon
`172006 Fa11on
`832006 Fallon
`8720116
`1'a1lon
`8-‘"2006 Fallon
`
`

`
`US 7,415,530 B2
`Page 4
`
`2U[.|fi-"Ul9t]fi44 Al
`21.106.-'0l1)5fil.ll A1
`."!1J1J7"l}l}r-13939 A1
`2007.-’0O5l'l514 Al
`21.107-"DQ511515 Al
`21107.-“DQ513746 Al
`lll[i'F-“(E10915-‘l Al
`21107-11109155 Al
`2007-'GlD'all55 Al
`2[iU7I"lil'i'4209 A1
`
`85111116 Fallon
`89211116 Fallon
`252007 Fallon eta].
`3."I!0l}T Fallon
`3-“E007 Fallon
`4.-9007 Fallon elal.
`5.11111’)? Fallon
`S.-“£007 Fallon
`5-"200? Fallon
`7-‘Z1107 Fallon elal.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`E1’
`El’
`EP
`El’
`El’
`EP
`131’
`GB
`IP
`JP
`JP
`W0
`W0
`WO
`W0
`
`11164577
`0185098
`02 83 793
`0405572
`1.1493131}
`{.15 R74 .31-'
`0595406
`0711551
`2162025
`605 1 989
`91311009
`lll~=l93'I-'6
`WO 91414273
`W0 9429852
`V\«’C} 9502373
`W0 9748212
`
`121985
`61986
`'95 l 988
`1.-"1991
`T1992
`3! 1994
`5' [994
`6-1996
`l'l‘)f€6
`2 ' 1904
`‘F1997
`6-1999
`6-199-1
`1211994
`1.11995
`111997
`
`OTI-ll{R PUl3l.1(.‘A'l'lONS
`
`Anderson. J.. el :11. "L'odec squeezes color l'olr.-eonfcnancing lhroilgh
`digital telephone lines". Electronics 1984. pp.
`1 13-1 15.
`Venhriui. Jack. "A VLSI Chip Set for High-Speed Lossless Data
`Compression". IEEE '['rn.ns. On Cireirils and Systems for Video Tech-
`nology. vol. .1. No. 44. Dec. 1991. pp. 331-391.
`“Fast Dos Sofl Boot“. lBM'I'ei:l1nieal |)iselosure Bulletin. I"el). 1994.
`vo1.}7.IssI.tc No. 213. pp. 185-186.
`“OpernJ.ir-rg Syslem Platform Abstraizlion Melhod". IBM Technical
`Disclosure Bulletin. Feb. 1995. vol. 33. Issue No. 2. pp. 343-344.
`
`Murashitn. K.. et al.. "lliglr-Sp:-ed Slalistical Compression using
`Self-organized Rules and Pre-zletermined Code Tables". IEEE. 1996
`Data Compression Conference.
`Coene. W.. el 11. “A Fast Rome For Application of Rate-distortion
`Oplirnal Qunntizalion in an MPEG Video Encoder“ Proceedings of
`the Inlematiunal Conference on Image Processing. l.£I.Usa.nne. Swit-
`zerland. IEEE. Sep. 16. 1996. pp. 525-828.
`Rice. Robert. "Lossless Coding Standards for Space Data Systems".
`IEEE 1055-639397, pp. 57?-SS5.
`Yeh. Fen-Shu. "The CCSDS Lossless Data Compression Recom-
`mendalion for Space ApplicaJ.ions". Chapter 16. Lossless |f.’ornpres-
`sion 1-lnnrlbook. Elsovior Science (USA). 2003. pp. 31 1-326.
`M.i.llman.1Iown.rd. “Lrnnge and video compression". Compulerworld.
`vol. 33. Issue No. 3. Jan. IR. 1999. pp. '18.
`"IBM boosts your memory". (}eek.com [online]. Jun. 25. 2000
`[relrievodon .1111. fr. 200?]. <U1'U_.: hllp‘. -'-’www.gr:clr:.eornr'ibrn-boosla-
`your-memory.-'>.
`“IBM Research Breakthmirgh Doubles Computer Memory (‘apric-
`iry“. IBM Press Release [on|ine]. Jun. 26. 20111) Irelrievocl on .l1.1l.6.
`2007], <URI.: hltpzf.-'www-(J3.lbn1.cornIprr:ss.-'us*'r:n.-‘pressrelease
`l653.wss:-.
`“Scrve—rWorics To Deliver IBM's .-Vlemory expansion Technology in
`Nexl-Generation Core Logic for Servers". Serverworks Press
`Release [online], .1l.1.l1. 27. 211110 [retrieved on Jul. 14. 30111)}, <LJRL.'
`11tlp:.'.-“MW.sr:rvenrvorks.eo111r'news-'press.' lllJl)fi2? .hln1l>.
`Abali. 13.. ul nl.. "Memory Expansion Technology [MXTJ Eoflware
`supporl and perl'orn1a.nce“, IBM Journal of Research and Develop-
`ment. vol. -15. Issue No. 2. Mar. 2001. pp. 287-301.
`Franaszelr. P. A.. et a1.. “Algorithm and data structures for com-
`pressed-memory machines". IBM Journal 0fRES6a.l'C1'l and Develop-
`man1.\rol. 45. Issue No. 2. Mar. 2001. pp. 245-253.
`Frnnaszek. P. As at a].. "On internal or}g.a.I1l2a.1.ion in eornpressod
`randorn-access memories". IBM Journal ofRese.1.rc11 and Develop-
`ment. vol. 45. Issue No. 2. Mar. 2001. pp. 259-270.
`SmiI.l:i. T.E.. :1 nl.. “Memory Expansion Technology (NEXT) Corn-
`pcli1_iveirripact", IBM Journal ofkesearch and Dr:veloprnenl.\r'o. -15.
`Issue No. 2. Mar. 2001. pp. 303-309.
`'l're:nai.nc. R. 13.. el al.. “IBM Memory Expansion Teclrnology
`{'MX'T}". IBM Journal o1ReseaJ1:h and Dr-.'velopmen1.. 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
`
`E85330
`
`Emmbw
`
`Ema
`
`_m>mEmm
`
`
`
`._Bm._m_moo¢
`
`sun
`
`mmfioew
`
`_BEm_moo<
`
`
`
`Ema=..n_:_
`
`Emmhw
`
`8
`
`2»
`
`9
`
`_‘miner.
`
`
`

`
`U.S. Patent
`
`Aug. 19, 2008
`
`Sheet 2 arm
`
`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
`
`Sheet 3 M20
`
`US 7,415,530 B2
`
`Retrieve Initial
`
`
`
`De-compress Data
`Block with
`
`302
`
`Decoder(s)
`
`Output Accelerated
`Data Block
`
`304
`
` More Data Blocks
`For Output Stream ?
`
`No Terminate Retrieval
`
`Acceleration Process
`
`308
`
`
`Retrieve Next
`
`Data Block
`
`
`
`
`From Storage
`.
`Device
`
`310
`
`FIGURE 3
`
`300
`
`
`
`Data Block
`
`From Storage
`Device
`
`

`
`
`
`
`
`
`
`nunI»was3002131'finvwaned‘Sn
`
`T3
`
`I
`I
`
`T3
`
`I
`
`T4
`
`I
`I
`
`Ti
`
`I
`I
`
`T1
`E
`Time Interval
`
`
`II
`
`1 R
`
`Recehre
`Data Block 2
`
`Receive
`Dala Block 3
`
`Receive
`Data Block 4
`
`eceive
`Data Block i
`
`I
`I
`
`Reoieve
`Data Block 1
`
`:
`
`III
`
`I
`I
`
`Regewe
`Data Block
`
`MET 00 1
`
`figmp[es5
`Data Blflck
`
`Compress
`:
`I Data Block 1
`I
`I
`I
`I
`
`Compress
`:'
`I Data Block 2
`I
`I
`I
`I
`
`Compress
`Data Block 3
`
`I
`I
`
`:
`I
`I
`I
`I
`I
`
`I
`I
`
`I
`I
`
`:
`Compress
`Data Block 4 I
`I
`I
`I
`I
`
`Compress
`}
`I Data Block i
`I
`I
`I
`I
`
`I
`I
`
`:
`I
`I
`I
`I
`I
`
`1' Store Encoded
`Il
`Data Block 4
`I
`I
`I
`I
`
`:
`1
`I
`I
`I
`I
`
`: Store Encoded
`:
`Data Block I
`I
`I
`I
`I
`
`:
`1
`
`I
`I
`I
`
`store, Encoded : Store Encoded
`Data Block
`I
`Data Block 1
`I
`I
`I
`I
`
`IfiI|:|.QQ.2
`
`: Store Encoded
`=
`Data Block 2
`I
`I
`I
`I
`
`Store Encoded
`Data Block 3
`
`I !
`
`camp.-.335
`Data muck
`
`:
`:
`I
`I
`I
`
`Store Encoded I
`Data Brock
`I
`I
`
`:
`I
`I
`I
`I
`
`I
`I
`5
`
`Compress
`Data Block 1
`
`Compress
`Data Biock 2
`
`Store Encoded
`Data Bfock 1
`
`FIGURE 4a
`
`:
`I
`I
`I
`I
`
`Compress
`Data Block 3
`
`:
`I
`I
`I
`I
`
`I Store Ended I
`I
`Data Block 2
`I
`5
`I
`
`Compress
`E
`I Data Block (I-1)
`I
`I
`I
`
`: Store Encoded
`I Data Block {I-2)
`I
`
`:
`I
`I
`I
`I
`
`:
`:
`I
`
`
`
`Z8l]SS‘S[FLSfl
`
`

`
`Time Interval
`
`Racewe
`D813 BIOGK
`
`METHOD1
`
`g°t"‘"PB’|E’5'°"(
`a a
`DC
`
`d d
`En
`81
`3'‘: B13”:
`33 on
`
`I
`
`I
`
`ll
`I
`
`TH”)
`
`Recieve
`Data Block
`(H1)
`
`E
`
`I
`I
`:
`I
`
`}
`}
`|
`I
`'
`Compress
`'
`I Date Black
`:
`R
`{*1}
`II
`I
`I
`Istcre Encoded I
`: Date Bicck
`4'
`I
`(“'11
`I
`
`T(I+2)
`
`Receive
`Data Block
`(H2)
`
`E
`
`I
`I
`:
`I
`
`Compress
`Daia Blcck
`9+2)
`
`3
`I
`‘
`I
`:
`I
`Stare Encoded I
`Date Block
`:
`{W2}
`I
`
`I
`
`gem I
`3
`I
`I
`1
`
`:?:::'g.:.::
`I
`
`I
`
`:
`I
`I
`I
`
`3:22:21
`fi+1)
`
`I
`
`:
`I
`I
`I
`
`I
`
`I
`I
`:
`I
`
`:
`I
`I
`:
`:
`I
`I
`:
`I
`
`I
`
`I
`I
`I
`I
`
`T(n-I-1)
`
`T(n+2}
`
`T"
`
`'
`R
`1“-‘W-'|V9
`53*? BI‘-‘ck
`r[
`
`DITIDFBSS
`I;
`Data Block
`n
`
`store Encoded
`Data mock
`n
`
`32:23.21:
`(M)
`
`Compress
`Data Block
`n
`
`31°,eEnmded
`Data Block
`
`1 Store Encoded : Store Encoded :
`I
`Datc Block
`I
`Data _Block
`I
`I
`{I-1)
`:
`I
`I
`I
`I
`I
`
`I Store Encoded
`I
`Data Block
`:
`(n-2)
`I
`
`FIGURE 4b
`
`Store Encoded
`Daia Block
`(n~1)
`
`Store Encoded
`Daia Block
`Fl
`
`
`
`
`
`__..__.._..__.___.___.______..._..._._____...¢.______..__
`
`
`
`02105loanssIIOz‘6I'3'WIllawd'S'f]
`
`
`
`
`
`zu0£‘S'§lt"LSn
`
`

`
`‘I”Irr.e Interval
`
`T1
`
`E.
`
`:1
`
`I
`I
`
`I
`I
`
`I
`I
`
`I
`I
`
`Retrieve
`I
`Retrieve
`I
`Retrieve
`I
`Retrieve
`I
`Retrieve
`I Data Block 4
`Data Block 3
`Ir
`Data Block 2
`:
`Data Block 1
`:
`Data Bmk
`I
`I
`I
`I
`___
`
`Decompress
`Data Block 2
`
`Decompress
`Data Block 3
`
`Decomprese
`Data Block 4
`
`I
`I
`:
`Decomprese
`I
`I
`I
`I
`I Date Block 1
`I
`I
`I
`I
`I
`I
`I
`I
`Dugpug Decoded I Output Decoded . Output Decoded I Output Decoded . Output Decoded
`Data mock
`:
`Data Biock 1
`:
`Data Block 2
`I
`Data Block 3
`:
`Data Block 4
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`Dacomp,-es;
`Data Bfock
`
`E
`
`D 3
`
`Decompress
`Data 3|;-_.cI(
`
`:
`:
`I
`I
`
`Dutpug Decoded I
`Data 3105].;
`II
`I
`
`I
`
`I
`I
`I
`I
`
`I
`:
`I
`
`I
`
`Decomprees
`Data Block I
`
`Output Decoded
`Data Block I
`
`Decomprees
`Data Block (I-1}
`
`Decompress
`Data Block 1
`
`I
`I
`I
`I
`
`Deoornpress
`Data Block 2
`
`I‘
`I
`I
`I
`
`Decompreae
`Data Block 3
`
`I Output Decoded I Output Decoded
`:
`Data Block 1
`I
`Data Block 2
`I
`I
`
`Output Decoded
`Dela Block [I-2)
`
`E
`
`I
`
`FIGURE 55!
`
`
`
`Z80‘£S"SIl?'LSfl
`
`
`
`
`
`
`
`
`
`
`
`HZJ9939°l|S8002‘I51'3“\''Jllalfld'S'[']
`
`

`
`
`
`
`
`
`
`01101.walls300:‘GI'3nv11131134‘gm
`
`ZH0E§'SI1="I".Sfl
`
`Time Interval
`
`I
`
`Retrieve
`Data Block
`
`:
`I
`I
`'
`
`T(I+1I
`.
`
`Retneve
`Dat(ai3|)ock
`
`I
`I
`
`I
`I
`I
`I
`
`T(i+2)
`
`Retrieve
`Di.-'.IlI:I+§)|DCk
`'
`
`I
`I
`
`I
`I
`I
`1
`
`II
`I
`
`I
`I
`I
`I
`
`Tn
`_
`
`Retneve
`Data nBIock
`
`I
`I
`
`I
`I
`I
`I
`
`:
`I
`
`I
`I
`I
`|
`
` |
`
`T(rI+1)
`
`T{rI+2)
`
`‘I
`
`I
`I
`I
`
`I
`
`Dgggnggiis
`
`OuIlJDal1ttaDBl=I::I:‘Ied
`
`Deco:-n
`Fm’-'55
`Data Block
`{i+2}
`
`'
`'
`' Decompress
`I
`‘I
`I
`I DataI Block
`I
`,
`I
`(M)
`I
`I
`I
`I
`I
`I
`I
`I
`I0uIput Decoded I Output Decoded I
`I Datg Block
`I
`Data Block
`I
`I
`0+1)
`I
`Ii+2I
`I
`
`Dec
`ass
`D,I§'"I§I',,.=k
`,1
`
`'
`I
`I
`I
`I
`I
`I out
`In
`d d
`I
`gpauga I3‘-Tggke
`I
`I1
`
`I
`I
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`
`I
`I
`I
`I
`I
`
`I M
`
`ETHOQ2
`
`D
`E?:t:I’I'|Bl!||;::3
`
`I
`I
`I
`I
`I
`I
`I Decompress
`I Decompress
`,
`I
`Data _Block
`I
`Date_I Block
`I
`I
`I
`I
`0+1)
`I
`I
`I
`I
`I
`I
`II
`oI_IgpuI Decoded :0uIputDecodecII Output Decoded I
`Data Block
`I
`D8?-3 BIOOK
`I
`13333 _B|DBI<
`I
`I
`(I-1)
`,
`I
`I
`I
`I
`I
`
`Decompress
`Data. I3Iock
`(0-1)
`
`De.-compress
`Data amok
`I1
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I Output Decoded I Output Decoded
`I
`Data BIOCJC
`I
`Data Block
`I
`(n-2)
`I
`{n—1)
`I
`I
`
`FIGURE 5b
`
`'
`I
`I
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`
`I
`.
`._
`I
`I
`I
`0|-IIPUIDEGOGEU I
`Data Block
`I
`II
`I
`I
`
`

`
`U.S. Patent
`
`Aug. 19, 2003
`
`Sheet 3 M20
`
`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
`
`Encode-r(s)
`
`Time 8. Count
`Data Block
`
`608
`
`FIGURE 6a
`
`

`
`U.S. Patent
`
`Aug. 19, 2003
`
`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
`
`
`
`
`
`Yes
`
`ore Data Blocks in
`input Stream ?
`
`NO
`
`Terminate Storage
`Acceleration Process
`
`618
`
`622
`
`
`
`Receive Next Data
`
`Block From input
`
`Stream
`Yes
`
`FIGURE 6b
`
`

`
`U.S. Patent
`
`Aug. 19, 2003
`
`Sheet 10 M20
`
`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
`
`Decoder(s)
`
`Time & Count
`Data Block
`
`708
`
`FIGURE 7a
`
`

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

`
`
`
`
` Bufferlcmlntet 1
`
`Strum
`
`Bufierfcounter 2
`
`Bufierfcounhar 3
`
`Deflirminafionr
`Comparison
`
`Encoded Data
`Stream IIW‘
`
`
`
`
`
`
`
`zao£s‘s1v‘.«LSn0110IIM45800Z'61'3"VJllawd‘ST!
`
`Bufferfcountar :1
`
`FIGURE 8
`
`

`
`
`
`
`
`
`
` zao£s‘s1v‘.«LSn01109!WIS8I10Z'6!'3“VJllawd‘ST!
`
`Data «In? Nut! Dasertpl‘/or
`
`
`
`
`
`FIG. 9
`
`

`
`Video Inpuus}
`
`Data Output
`Stream
`
`
`
`1 020
`
`1030
`
`1040
`
`1050
`
`10
`
`FIGURE 10
`
`
`
`
`
`Z8:[I£S‘S[t!"LSf]0310Hl39llS8002‘(SI'3"Vlllalfld'S'fl
`
`
`
`
`
`
`
`

`
`
`
`E90£S“Slv‘LSnoz1051mans3002151'finvmaxed‘Sn
`
`
`
`
`
`-
`*°D2:::::='
`
`°
`G
`°
`
`,
`
`
`
`Display
`Formatter
`
`Output
`Memory
`
`Display
`Processor
`
`Dispiay Data
`
`
`
`
`
`“’?‘a
`Retneval
`Accelerator
`
`
`
`80
`
`1110
`
`1120
`
`1130
`
`1140
`
`1150
`
`FIGU RE 1 1
`
`

`
`
`
`:90£s‘s1v‘LSnone9:musson:15!‘Rawma1e.1‘Sn
`
`
`
`
`
`
`
`1205
`
`Parallel Digital
`Data
`
`Serial Digital
`Data
`
`'1 235
`
`1 240
`
`1 245
`
`FIGURE. 12
`
`

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

`
`
`
`
`
`
`
`zao£s‘s1v‘.«LSn01108!WIS8002'6!'3'“?Jllawd‘ST!
`
`Analog Data
`
`Parallel Digital
`Data
`
`Digital Data
`Darnux
`
`Serial Data
`Interface
`
`Serial Digital
`Data
`
`
`
`
`
`Data
`Retrieval
`
`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
`
`
`
`Data Serial
`Data
`
`
`'
`
`1512
`
`
`
`Digital Parallel
`Data ?
`
`NO
`
`1510
`
`
`
`Yes
`
`
`
`I ata Digitize 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 ?
`
`
`
`1 532
`
`Reoeive Next
`
`Data Block
`
`1534
`
`FIGURE 15b
`
`

`
`US 17,415,530 B2
`
`1
`SYSTEM AND METHODS FOR
`ACCEIERATED DATA S"l‘ORAGI£ AND
`RETRIIEVAL
`
`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'lJ.S. patent appli-
`cation Ser. No. t)9X266.39-1 tiled on Mar 1 l.. 1999. now US.
`Pat. No. 6.601.104, both ofwhich are hereby incorporated by
`reference herein in their entirety.
`
`I3./\C‘KGRC)lJl‘-ll)
`
`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 cornpression and decompression.
`2. Description of the Related Art
`Information may be represented in a variety of manners.
`Discrete infonnation such as text and numbers are easily
`represented in digital data. This type ofdnta representation is
`known as symbolic digital data. Symbolic digital data is thus
`an absolute representation o I‘ data such as a letter. Iigure.
`character. tnark. machine code. or drawing.
`Continttotts information such as speech. music. attdio.
`images and video frequently exists in the natural world as
`analog ittfonnation. As is well-known to those skilled in the
`an, recent advances in very large scale itttegration (V151)
`digital computer technology have enabled both discrete and
`analog information to be represented with digital data. Con-
`tinuous informa lion 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 information density and is
`typically not easily recognirablc to humans in its native form.
`There are many advantages associated with digital data
`representation. For instance, digital data is more readily pro-
`cessed. stored. and transmitted due to its inherently high noise
`immunity. In addition. the inclusion of redundancy in digital
`data representation enables error detection andfor correction.
`Error detection andlor correction capabilities are dependent
`upon Lite amount and type ofdata redttndancy. available error
`detection and correction processing. and extent of data cor-
`rnption.
`One outcome ofdigital data representation is the continu-
`ittg need for increased capacity in data processing. storage.
`and transmittal. This is especially true for ditliise data where
`increases in fidelity and resolution create exponentially
`greater quantities ofdata. Data compression is widely used to
`rcdttce the amount of data rcqtlircd to process. trt-;Inst11it_. or
`store a given quantity of iiiforinatioii. In general. there are two
`types of data compression techniques that may be utilized
`either separately orjointly to encodetdecodc data: lossy and
`lossless data compression.
`Lossy data compression techniques provide for an inexact‘
`representation ofthe original uncompressed data such that the
`decoded tor reconstructed} data dilfers from the original
`uncncodedfuncontpressed data. I.ossy data compression is
`also known as irreversible or noisy compression. Negentropy
`is defined as tl1c quantity o finfortuation in a given set of data.
`Tltus, one obvious advantage oflossy data compression is that
`the compression ratios can be larger than that dictated by the
`negentropy limit. all at the expense of information 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
`
`to
`
`15
`
`3 I]
`
`40
`
`-'13
`
`EIIJ
`
`2
`
`visual imagery might seek to delete inlonnation content in
`excess of the display resolution or contrast ratio of the target
`display device.
`On the other hand_. lossless data cornpression techniques
`provide an exact representation ofthe original uncompressed
`data. Simply stated. the decoded (or reconstructed) data is
`identical to the original unencodedlurtcompressed data. Loss-
`less data compression is also known as reversible or noiseless
`compression. Titus. 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 kncrwn within the current an that data compres-
`sion provides several unique benefits. First. data compression
`can reduce the time to I.t'a1'isrttit data by ntore elllcierttly uti-
`lizing low bandwidth data links. Second. data compression
`economizes on data storage and allows more itnormation to
`be stored tor a fixed memory size by representing information
`more etliciently.
`One problem with the current art is that existing memory
`storage devices severely limit the performance of constttner,
`entertainment, office. worl>:st'ation. servers. and 1:nai|1li‘aI't‘te
`computers for all disk and memory intensive operations. For
`example. magnetic disk mass storage devices currently
`employed in a variety of home. business. and scientific com-
`puting applications stiffer liom significant seek-time access
`delays along with profound read./write data rate limitations.
`(.'u11'entIy the lastest available (10,000) rptn disk drives sup-
`port only a 17.1 Megabyte per second data rate (Ml3:‘sec].
`This is in stark contrast to the modern Personal Cornputefls
`Peripheral Component Interconnect (PCI ] Bus‘ s inputfoutput
`capability of 264 MB} sec and internal local bus capability of
`S00 Mlifsec.
`
`Another problem within the current art is that emergent
`high perforniance disk interface standards such as the Small
`Computer Systems Interface (SCSI-3] and Fibre Channel
`offer only the promise of higher data transfer rates through
`intermediate data bttl'liering in random access memory. These
`interconnect strategies do not address the fundamental prob-
`lem that all modern magnetic disk storage devices for the
`personal computer marketplace are still limited by the some
`physical media restriction of l ?.l MB!-sec. Faster disk access
`data rates are only achieved by the high cost solution of
`simultaneously accessing multiple disk drives with a tech-
`nique known 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
`tnass storage devices include magnetic and optical tape. mag-
`netic and optical disks. and various solid-state mass storage
`devices. It should be noted that the present irtvcntion applies
`to all forms and ntarmers. of memory devices including stor-
`age devices utilizing magnetic. optical. and chemical tech-
`niques. or any combination thereof.
`
`SUMMARY OF THE lNVEN'f ION
`
`The present invention is directed to systems and methods
`for providing accelerated data storage and retrieval by utiliz-
`ing lossless data c