|||||||||||||||||||||||||||||||||||||||||l||
`
`
`
`USUU58U5932A
`
`United States Patent
`Kawashima et at.
`
`[19]
`
`[11] Patent Number:
`
`5,305,932
`
`[45] Date of Patent:
`
`Sep. 8, 1998
`
`[54]
`
`SYSTEM FOR TRANSMITTING
`C()Ml’RESSl.']l) DATA IF COMPRESSION
`RATIO IS AT LEAST PRESET RATIO AND
`PRE-COMPRESSED DATA IF COMPRESSION
`RATIO IS LESS THAN PRESET RATIO
`
`|7S]
`
`Inventors:
`
`'l'etsu_ji K:.1wa5hitna:'Iht.Isuya
`Inukuehi. both of Kanagawa. Japan
`
`|73] Assigncct Sony Ctarpnrntinn, Tokyo, Japan
`
`|21] Appl.No.:
`
`564,144
`
`in PCT Filed:
`
`Apr.21.199s
`
`|3o] P('l‘No.:
`
`PCTl.lP.95t'l)0795
`
`§3'?1 Date:
`
`Feb. 13, 1996
`
`§ lt]3(I:-J Date; Feb. 13, I996
`
`|87]
`
`PCT Pub. No.: W095,r‘2943‘7
`
`PCT Pub. Date: Nov. 2. 1995
`
`|3U]
`
`Foreign Application Priurity Dnta
`
`a'\pr.22, 1994
`Sen. 12. 1994
`
`[JP]
`[JP]
`
`Jarlan
`Japatt
`
`-‘_'1~I.t84‘i5U
`l‘.'-—.-‘.|fi‘J2H
`
`Int. Cl.”
`|5l|
`I52] U.S. Cl.
`
`|58]
`
`Field ufSea1"ch
`
`G[lfil"3f0|)
`395888; 395E427; 395E433;
`BISU1’-48
`
`3951838, 427,
`.
`'§i3§;'}i'3s; 350.-'43; 3til..’26tI.t'~‘
`
`|56]
`
`References Cited
`U .8. PATENT DOCU MENTS
`
`5.467.037
`5_.:'n‘Jl_.S24
`
`1lil.‘J"J5 Chll
`llJ_r'l9‘)f:t Cnrreircr cl
`
`:1].
`
`3-l-H5]
`395.-’STL‘
`
`P:'imm'_t-' fi'.\‘r:rr:i11c*r—'I‘homas C‘. Lcr:
`A5.stI5't1'1rtt‘ E.t'att1t'm?r—Andcrsnn 1. Chen
`
`A.|‘to.I".'te’_v, Agem‘, or Ffrnt—Frnn1n1er Lawrence & Ilaug
`|_l.l’; William 5. I-‘mmmer
`
`|:=?]
`
`ABSTRACT
`
`A Llilfcrczteefeomprcssion ratio tralcultttjng means 76 in at
`data processing means 71 (if a data transmitting apparatus
`aecnnijng to the present
`invention t:.sJn:ul:ttcs-;. an actual
`dillbrencc and an actual cnrnpressinn ratio hased on the data
`length of pre.-cumpressiun data received from a data murcc
`2 through ]1re—eo1nprcacion data receiving means 74 and the
`data length of CLlmpt'€S‘St:(l
`data nutputtcd [mm a
`tlatu
`eornlircssion circuit 67. If the actual difference is equal In or
`grc ater than a prc$t:l tliflercnoc (1. and the actual ccsmprcssioa
`ratio is aqua] to and gm atcr than a preset eompmasinn ratio
`fl. then the compressed data is transmitted to :1 data c|t:sti-
`nation 3 Ihrnngh :1 transfer request data output means. 79
`Otherwise, the prc—curnpres¢;ion data is transmitted to the
`data destination 3. With this arrangement, it is pnssible to
`prevent it phenomenon in which the size of compressed data
`which occupies a storage area in the data destination 3 is
`substantially the same as the size of uncompressed data
`which occupies the storage area, and also to avoid waste fu]
`data expansion in the data ttcstinaticin 3.
`
`4,9_T?,(_n‘_il
`
`l':u't9'JiJ
`
`i"t.1_ii1':tawa at al.
`
`...................... . 3555,.'42fJ
`
`3|] Claims, 40 Drawing Sheets
`
`
`
`1]IDICA':'I2t::t1'E|a7l‘ [1313
`
`| Is Im crbwaxm
`
`EDIQTDE TIl31'." {ETA
`TS
`
`
`
`Oracle 1103
`
`Oracle 1103
`
`

`
`U.S. Patent
`
`Sop. 8, 1998
`
`Sheet 1 of 40
`
`5,805,932
`
`F/5.7
`
`APPARATUS
`
`DATA
`'I'RANsM1'1'rING
`
`DATA SOURCE
`
`F/5.2
`
`1
`
`KEY INPUT
`MEANS
`
`11
`
`DATA
`TRMEWEETTNG
`APPARATUS
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 2 M40
`
`5,805,932
`
`F/5.3
`
`CDMQMIGMEON
`DATA
`
`DEVICE
`G1%flmHCATIUN
`fl%WSMEfiENG
`DEVICE
`
`32
`APPARATUS
`
`
`
`
`
`3‘
`
`
`
`KEY INPUT
`MEANS
`
`19
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 3 M40
`
`5,805,932
`
`F/5.5
`
`F/6.6
`
`51
`
`DATA
`Tamsmzrwz-ms
`APPARATUS
`
`EXTERNAL
`MEMORY
`
`18
`
`KEY INPUT
`MEANS
`
`
`
`
`
`
`DATA RAM
`
`

`
`U.S. Patent
`
`S01). 8, 1998
`
`Sheet 4 ol'40
`
`5,805,932
`
`F/5.7
`
`51
`
`52 EXTERNAL MEMORY
`
`COMPUTER
`
` HOST
`
`DATA
`TRANSMITTING
`APPARATUS
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 5 of 40
`
`zOHB¢ZHBmflfl
`
`dfiflfl
`
`weanNVH.
`
`mm
`
`_m
`
`zmmwomm
`
`sou
`
`.fi|IutII«
`
`mo
`
`aamapo
`
`N—
`
`mumaom
`
`¢B¢D
`
`mmgaomszou
`
`m_
`
`FDQZHmax
`
`mzamz
`
`mfibl
`
`
`
`
`

`
`
`
`flmuamwu:mflmzéu.
`
`
` 68MmafiahSE8mzfi:S5.5EH55uzmmnnmEEG
`
`
`
`
`
`§.EoE.z8ammmzmfi.Emflfifib2.
`
`5E.§E.mEEEG
`
`mama ean
`
`P33m.b\m
`
`
`
`
`
`mzfizuzuemmmzmw
`
`mzfi:
`
`..5:8Ea5.52mfiwwmfiaswwaaéoam
`
`«M
`
`t3
`
`0S
`
`n.
`
`any
`
`m1
`
`M
`
`5
`
`50
`
`3,cmEd5.3
`
`9932
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 7 M40
`
`5,805,932
`
`F/6.70
`
`START
`
`S1
`
`INITIALIZE
`
`S2
`
`53
`
`54
`
`S5
`
`55
`
`S7
`
`TRANSFER PROGRAM
`TRANSFER ROM DATA
`
`RIEKDES'I'
`
`YES
`
`No
`
`STORE KEY INPUT
`DATA
`
`READ AND STORE
`gig-J§3@PRESSIw
`
`PR.EZ—CIJMPRESSION
`" R l+- DATA Lmcni
`
`CIJTPUT ALL PRE SICN
`TD DATA CIZMPRESION
`
`53
`
`compmazss DATA
`
`STORE COMPRESSED
`DATA
`
`PRE SION
`-*-DATA LENC1'I‘H
`
` TE D CE AND
`
`S10
`
` CE:
`
`§1~1PR£3sIDN§T(¢I*»'£>1:ur}z4‘«§%1;1)/{R2}
`
`_
`
`

`
`U.S. Patent
`
`Sop. 8, 1998
`
`Sheet 3 0l'4I)
`
`5,805,932
`
`F/5.77
`
`PRE SION DATA
`
`
`
`CU'1‘PU'I' INFORMATION
`CODE EUR MESSAGE
`INDICATING 'I’HA'I' DATA
`125 N01‘ CIJMPESED
`
`
`
`
`S14 INDICATING THAT DATA
`
`IS. SED
`
`

`
`emU
`
`_H8tnaD1
`
`.__l
`
`Sup. 8, 1998
`
`Sheet 9 01'-10
`
`5,805,932
`
`
`
`zoaaaznammndhdn
`
`HDEE5.d§UHm
`
`mzcmz
`
`mmmmz¢ma
`
`nmmaflmm
`
`ZOHmHUmQ
`
`
`
`
`
`zazuommuzHmmmuo=maaan
`
`ZQAADGBZDU
`
`
`
`gazeEWEHEK
`
`EDQEDD
`
`mmmmzama
`
`mfififi
`
`zcHmmuEab
`
`Hfibfififlm
`
`uzwufiunzwu
`
`owemm
`
`mz¢mz
`
`muawmmz
`
`PDQBDD
`
`mz<mz
`
`EEfiH9MEHHE
`
`mmmmz¢ma
`
`uzmusgma
`
`E532
`
`.3
`
`
`
`¢ganzoHmmmma;HTmmm
`
`
`
`mamfiQESHHHE
`
`mmaqomazou
`
`mm
`
`8
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 10 of-1|}
`
`5,805,932
`
`F/5.73
`
`START
`
`TRANSFER PROGRAM
`TRANSFER. ROM DATA.
`
`51°‘
`
`5
`
`302
`
`9 Q
`
`5103
`
`3104
`
`YES
`
` NO
`
`STORE KEY INPUT
`DATA
`
`READANDSIDFE
`
`5103
`
`II 5107
`
`CALCULATE PRHJICIED
`COMPRESSION RATIO
`
`CIZMPREESION
`RATIO 1.=rrE:c'rIvE 2
`
`N0
`
`S103
`Sm
`
`cmmawz TRANSFER R.EEUES’I.‘
`32:: M Pmmmslw
`
`
`
`GENEEATE mmsrm RE‘QUESI'
`DATA ma ocnvrpnzsszo
`DATA
`
`ou-rpurr ms-omwmron con:-:
`FDR MESSAGE INDIC.A'I'I'NG tum?
`DATA IS NOT SEJ
`
`OUTPUT INFORMATICN CODE
`FOR MESSAGE IDIDICATING THAT
`DATA IS ED
`
`S113
`
`

`
`U.S. Patent
`
`Scp. 8, 1998
`
`Sheet 11 of 40
`
`5,805,932
`
`

`
`U.S. Patent
`
`Sup. 3, 1993
`
`Sheet 12 of 40
`
`5,805,932
`
`mmmmmam
`
`
`
`_mmozmzzoHmHumn
`
`mz¢m=
`
`mo_
`
`«m
`
`mm
`
`
`
`mzmmzuzHemqaua¢u
`
`uzn:um.s5a
`
`aammmgau
`
`m§fiE
`
`IHEETE
`
`ESEfifim
`
`uzuaam
`
`mz4mz
`
`
`
`
`
`omammzoHmmmmm:oonmaumnmmm
`
`
`
`
`

`
`U.S. Patent
`
`Scp.8,1998
`
`Sheet13 uf40
`
`5,805,932
`
`F/6.76
`
`Szcn
`
`INITIALIZE VARIOUS
`PARAMETERS
`
` S202
`
`REflJPREHOflfl¥&SSflIIDA$A
`
`
`
`UH?UEREMJEm$Oflfl%ES—
`SH1lDKHkTDlNflfl GJERES—
`SHWECKT
`
`
`
`
`COMPRESS DATA
`
`STORE COMPRESSED DATA
`
`CALCULATE STORAGE
`ADDRESS FOR NEXT
`COMPRESSED DATA
`
`CALCULATE
`COMPRESSION RATIO
`
`i-*-i +1
`
`
`
`5209 E
`
`S210
`
`CALCULATE PREDICTED
`COMPRESSION RATIO
`
`YES
`
`RETURN
`
`

`
`U.S. Patent
`
`Sup. 3, 1993
`
`Sheet 14 M41}
`
`5,805,932
`
`F/5.77
`
`111
`
`67
`
`69
`
`DECISION
`MEANS
`
`BUFFER
`MEMORY
`
`
`
`DATA COMPRESSING MEANS
`
` 95
`
` PRE4H1flEEE-
`
`
` 115
`STORAGE
`
`ADDRESS
`GHLULNNWG
`MEANS
`
`SIONIWHE
`REMXNG
`MEANS
`
`
`
`DATA RAM
`
`
`
`64
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 15 of 40
`
`5,805,932
`
`F/6.78
`
`START
`
`S301
`
`HIIPREAHIERESSKXIEEEA
`
`HEHEMSSHIIHME
`
`REED PRE4flIfl¥EBSIO
`EHEA
`
`aég§§§|E;E
`STORE COMPRESSED DATAIla
`
`—
`
`4-
`
`DAEATKDDATA Oflfl§EBSING
`
`COMPRESS DATA
`
`CALCULATE STORAGE
`ADDRESS FOR NEXT
`COMPRESSED DATA
`
`EEIEHE PORTION OF
`PEEFCEMPRESSION DATA
`
`Z O
`
`1
`
`1'
`
`HI ID
`
`RETURN
`
`S303
`
`530$
`
`S305
`
`S306
`
`S307
`
`S308
`
`S309
`
`S310
`
`

`
`U S Patent
`
`5
`
`0
`
`M3,
`
`12amEImmpmamwmmm.
`
`
`
`.m..._T\mI2M4CIII3:0cm:mmflomazou-iw%
`uuzHmmm_uoEmzwmmfifi.I.V,_we.1.-1mm.as
`
`on_mE.§§%.
`UZHB.QEDmo.§3:n_o_._mn_LW,Imm.SoE.zou,
`
`
`
`5-
`3,_
`
`_-Nw._—m2.58o2_.w_
`
`GEE8.56%
`
`
`
`BUEmmamQ_sm_.EuNm
`
`Ox
`V‘--.
`
`Q3
`
`LL
`
`
`

`
`U
`
`m3
`
`8
`
`4...n
`
`5
`
`M3,5
`
`0ma
`
`om,zmamam
`
`
`0mmqqomezou
`
`$_
`
`
`
`.zomEHRDMmozmz
`
`.A,5.49
`onBtu%zoamzmmxm
`
`.mat9....
`5HmmpmaaoH3:
`E._.:9.EauommEma_.mmacaw:
`
`
`
`
`zoHmm.mma,co
`
`p.5gm.5SR
`
`m.5%Sm:
`
`
`

`
`Sup. 8, 1998
`
`Sheet 13 of 40
`
` U.S.Patent
`
`

`
`U.S. Patent
`
`Sc]_J.8,1998
`
`Sheet 19 M40
`
`5,805,932
`
`F/5.22
`
`
`
`DDS
`
`SEXIIDR
`
`RECORDED
`
`CONTENT
`
`
`
`
`
`
`
`
`UNCERTIFIED
`
`O 2
`
`CERTIFIED
` 0}
`
`_____—.-.__
`
`unc-up-1-.-u.._
`
`-——_.—.._
`
`-1:;-.~
`
`FILE ALLOCATION
`
`TABLE
`
`I
`
`p + Q
`
`FILE ALLOCATION
`TABLE
`
`|
`I
`I
`
`I
`
`I
`1
`
`I
`
`I
`
`
`
`I
`I
`
`I
`.
`
`2°“ T
`
`

`
`MPamU
`
`503,5
`
`suUnomMND7.‘
`
`
`
`n.EE .E,Hm9m_U¢.Z¢25.8EE Egg5.5HgE5982
`
`mmE$2é32
`
`
`
`—o.u_n_n_u_38E32:88.:55
`
`mMuHHMMm_.__._._
`
`3932
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 21 of 40
`
`.503,5
`
`n3,
`
`
`
`
`
`xaaaomezouzmemmmmzamz
`
`mh_
`
`amom
`
`zommuumn
`
`
`
`zmeamzouSW02
`
`
`
`uzH.H_mmxxw_w_mzmmz
`
`
`
`
`
`aamaaoz¢mwommuzHmmmuomm«Baa
`
`—_N
`
`uzamwmuomm
`
`mzmm:
`
`mzHmmmuomm
`
`ammaamm
`
`mzmu:
`
`
`
`Qfiafifififiwmqm¢a
`
`
`
`mnecsmGZOUMM
`
`mzmmz
`
`zoamaumm
`
`wzdmz
`
`
`
`
`
`D¢DAz==mHnzcmmnumn
`
`New
`
`_§.E..\
`
`Nmabmzunmaz
`
`mom
`
`
`
`mmqaozzacsewn“
`
`UzHE¢J:UQdU
`
`mz¢mz
`
`
`
`mmmmnn¢eammz¢m:
`
`BHQsum
`
`uzHmmaoam
`
`zmmdbdfl
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 22. M41}
`
`5,805,932
`
`F/G. 25
`
`START
`
`5401
`
`TRMfiEERPRfl§mM
`
`5402
`
`REQUESTII 5"‘°
`
` SUBROUTINE
`
`YES
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 23 of 40
`
`5,805,932
`
`FIG. 26
`
`
`
`SET bTH IN
`RECORD STATUS
`TABLE
`
`
`
`
`
`

`
`tHEt3PamU
`
`8mcm.
`
`2
`
`N
`
`n0.”,508.,5
`
`SnEco.u3:53
`
`MWannlauual
`
`
`
`omzomou5BHQMin3:]:90...HOm..OOONmadama%m¢B
`
`
`
`
`
`
`

`
`3P«M
`
`tn
`
`am.WS
`
`.I_.
`
`I
`
`n99503,5
`
`mzflbommam
`
`Mmmmfio
`
`
`
`.SE49FEM:5mm»
`
`umH..~4H.H.HzHmE
`
`m.5%WZHBUDEMDW
`
`Pu-tmmwT\
`
`
`

`
`ll3PamU
`
`{IHPu
`
`Sup. 8, 1998
`
`Sheet 26 of 40
`
`5,805,932
`
`
`
`mmaqomazouzmamum
`
`mmaamDUemu:
`
`2.
`
`EDQBDO
`
`amen
`
`uzHamm=amm
`
`mzamz
`
`MBHMB
`
`ozmammaomm
`
`mzzmz
`
`namm
`
`HEEEHG
`
`UZHBHM3
`
`mz¢mz
`
`¢a¢n
`
`zom¢a¢n
`
`
`
`m2<m:uzaumaamanzn
`
`%..£.._,
`
`mmnm:upmQ_
`
`mt
`
`fi3ZDEfiU.fiEMNm
`
`
`
`mamaanm
`
`Qfifikfiflfi
`
`mzamz
`
`«om
`
`3....
`
`zmm¢F¢D
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 27 of 40
`
`5,805,932
`
`F/5.30
`
` SUBROUTINE
`
`WRITE
`A'I'I'3IHU'I'E
`DATA
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 28 M41)
`
`5,805,932
`
`FIG. 37
`
`GENERATE WRITE
`'EQUEST DATA
`
`
`
`RANSFER WRITE
`REQUEST {TRACK 0]
`
`GENERATE WRITE
`REQUEST DATA
`
`E
`TRANSFER WHITE
`REQUEST (TRACK 1)
`
`
`
`
`
`S80!
`
`S802
`
`S803
`
`s o
`8 ‘4
`
`GENERATE WRITE
`REQUEST DATA
`
`S805
`
`S606
`
`
`REQUEST (TRACK 9993
`
`TRANSFER WRITE
`
`REQUEST (TFRCK 9997)
`
`GEflfimTE¥fiflTE
`REQUEST DATA
`
`TRANSFER WRITE
`
`S807
`
`
`
`S808
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 29 of-1!}
`
`5,805,932
`
`
`
`HmmaommHHHNE
`
`.wzH.S.mmE_umean
`
`mzmm:
`
`2::4E¢D
`
`on
`
`
`
`mmaumzouawe:
`
`
`
`mmaqomazouzmamwm
`
`2...mt
`
`mmmmam
`
`amozma
`
`zoummmmmzou
`
`mama
`
`BXU
`
`zoamuumn
`
`mzaw:
`
`No.»
`
`fifliizuflflfl.
`
`mmmc
`
`
`
`mz4mzUZHBHEE
`
`a:mzH
`
`BMOQ
`
`m:
`
`manna
`flhbfl
`
`UZH>HMUm¢
`
`mzmmz
`
`4340
`
`
`
`KHEUEEEDzamam
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Sep. 8, 1993
`
`Sheet 30 M40
`
`5,805,932
`
`FIG. 33
`
`S T A R T
`
`890!
`
`N 3912
`RECEIVE DAT:
`ISUBROUTINE
`FROM HOST
`an-purp DATA
`COMPUTER
`
`
`
`' $93
`
`
`
`
`WRITE
`ATTRIBUTE mm
`
`8914
`
`swans DATE
`R3* G mm
`
`ourpum WRITING DATA ‘ID
`am cmvnfissrow
`CRT
`
`compnass
`DATA
`
`3903
`
`3904
`
`3905
`
`STORE ocmpnrssm mm‘
`R4* mm
`
`5906
`
`CALCULATE
`compnssszom RATIO
`
`S907
`
`89-08
`
`'2
`
`R I-— 0
`R 2-— B
`
`8910
`
`RI --— I
`R2--B/cg”)
`
`I 39: I
`
`GENERATE
`FAT
`
`

`
`U.S. Patent
`
`Sep.8,1998
`
`Sheet 31 of 40
`
`5,805,932
`
`FIG. 34
`
`START
`
`Kzzvmmzmm
`
`SAOI
`
`SAIQ
`
`
`
`SUEROUTINE
`STORE
`ADDRESS
`
`
`
`Rsnnamenspcmmnvs arr
`smmc man man RECDRD
`STATUS TABLE
`
`SAO3
`
`SAO4
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 32 of 40
`
`5,805,932
`
`FIG. 35
`
`SAIO
`
` N
`
`Y
`
`S
`
`3”"
`
`SAI2
`
`SA
`
`SAM
`
`SAI5
`
`N
`
`SAIB
`
`G S
`
`AIG
`
`N
`
`SN?
`
`Y
`
`I-"RE—CQVIPRE‘SSION DATA
`?
`
`i
`
`91095 ''F'FF5W" 1” 1-INK
`ADDRESS STORAGE
`AREA
`
`STORE "FPFE'0‘l" IN
`LINK ADDRESS
`STORAGE AREA
`
`W RETURN
`
`)
`
`
`
`k'I'H RECORD or BIT
`DATA
`SIURAGE AREA
`
`SUBROUTINE
`STORE
`ADDRESS
`
`k--—-(R) + I
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 33 of 40
`
`5,805,932
`
`FIG. 36
`
`
`
`
`
`SET (j)'.I‘I-I BIT or
`RECORD STATUS TABLE
`
`SBOI
`
`
`
`S305
`
`
`
`GENERATE DTH RECORD
`OF TABLE DATA
`STORAGE AREA
`
`
`
`
`
`GENERATE 1TH AND
`FOLLOWING RECORD OF
`TAEEEIFHE SKEmGEJ¥EA
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 34 M41}
`
`5,805,932
`
`
`
`SCOI
`
`S602
`
`SGO3
`
`SC05
`
`READ ONE BLOCK OF DATA
`ERCM PRE- SION
`
`DATA SIURAGE
`
`SC05
`
`SO07
`
`SCO8
`
`N
`
`S009
`
`RETURN
`
`
`
`FIG. 37
`
`START
`
`_
`I
`
`--——-— O
`
`
`
`3§’;§.Ef.;’.-E in‘A§J‘.c%%%§&
`AREA
`
`READ ONE BLOCK OF
`DATA ERCM CCMPRESED
`DATA SIDRAGE AREA
`
`GENERATE WRITE
`REQUEST DATA
`
`TRANSFER wan‘:-3
`REQUEST
`
`I..I!\IK ADDRESS ?
`
`IIIIIIIIII
`
`Y
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 35 of 40
`
`5,805,932
`
`
`
`mmaamzouawe:
`
`wn_
`
`uznmmmuomm
`
`mzamz
`
`momma
`
`uzaammsomm
`
`mzmm:
`
`n¢mm
`
`uzuemmpomm
`
`mmmmzmms
`
`mzmma
`
`zoamzamxm
`
`fiemn
`
`EMU
`
`zoHmHumn
`
`mzmm:
`
`
`
`mzcmzuzH:¢mm
`
`BDWZH
`
`axon
`
`5.
`
`Hflbafifiwflfim
`
`
`
`ZMAAOEBZOUzmamwm
`
`
`
`z%HEEfiUEflmfim
`
`m»_mmmmam
`
`MMOEMZ
`
`mmmi
`
`mom
`
`HHHEEEM
`
`aaan
`
`uzamoam
`
`mzmm:
`
`zmmmama
`
`uz>Hmumm
`
`mzmmz
`
`dfiflfl
`
`mom
`
`
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 3, 1993
`
`Sheet 36 of-10
`
`5,805,932
`
`500.
`FIG. 39
` SD02
`
`SD09
`
`
`
`READ DATa
`FROM HOST
`
`COMPUTER
`
` SEIEEXLT iTHT
`IN FILE Anom-
`TION TABLE
`
`I I0
`
`

`
`QMnu
`
`fl3D1
`
`{IHPu
`
`Sup. 8, 1998
`
`Sheet 37 of 40
`
`Mau.50aw5
`
`
`
`mmaamzouHMO:
`
`mu.
`
`anmaao
`
`axon
`
`
`
`mmaaomszouzmamwm
`
`ax
`
`UZHNHQQHEHZH
`
`mzmmz
`
`QMOUMH
`
`uzunm_¢naa
`
`manmameam
`
`mzcmz
`
`mZfi§
`
`mmmmoom
`
`-4unm4u
`
`BHM
`
`UZHENUMM
`
`mzmmz
`
`maaa
`
`mommom
`
`
`
`
`
`mzcm:UZHBMAMQ¢B¢D
`
`BMOQ
`
`eamzamm.
`
`
`
`GHEEEERUaamwm
`
`wowwow
`
`35$
`
`_om
`
`ZOHmHUMD
`
`mzmmz
`
`
`
`fiFEK?8UHMOE
`
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 33 of 40
`
`5,805,932
`
`FIG. 47
`
`SEED!
`
`SE02
`
`SE03
`
`SE04
`
`START
`
`El!
`
`
`
`READ DATA FROM
`HOST compuwgn
`
`SELECT iTH RECORD
`IN FILE ALLOCATION
`TABLE
`
`an 9».
`
`NO
`ID:-.'IC ADDRESS
`'3
`
`3505
`
`
`
`Y
`.
`.
`t-=—-- ( I ) + I
`
`SEMMJIFTNIEED 2
`
`S
`
`EFFECT ERROR
`pnoczss
`
`
`
`RETURN
`
`SUBHOUTINE
`WRITE
`ATTRIBUTE
`DATA
`
`
`
`
`
`
`
`SE09
`
`CALCULATE BIT
`ADDRESS
`
`RESET connaspomnxns SEIO
`BIT IN RECORD
`STATUS TABLE
`
`LINK ADDRESS ?
`
`SELECT NEXT
`RECORD
`
`INITIALIZE
`PRECEDING RECORD
`
`INITIALIZE
`consspounxns RECORD
`
`
`
`SEII
`
`SE33
`
`5534
`
`SEIE
`
`
`
`

`
`U.S. Patent
`
`Sep. 3, 1993
`
`Sheet 39 of 40
`
`5,805,932
`
`F/6.42
`
`E.XPECI'EI} COMPRESSION
`
`RATIO ,5
`
`‘P
`MAXIMUM RECORDING
`CAPACITY
`
`O
`
`

`
`U.S. Patent
`
`Sup. 3, 1993
`
`Sheet 40 of 40
`
`5,805,932
`
`FIG. 43
`
`DATA NOT compnzsszn
`
`TA!
`
`
`
`DATA COMPRESSED
`
`Tc:
`
`pflb.
`
`
`
`
`Ta:
`
`FIG. 44
`
`V//flfll/////J
`
`DATA COMPRESSED
`
`Tacz
`
`
`
`
`
` _I'.V.V ‘V V
`
`
`
`
`HMQL.A4|
`
`

`
`5,805,932
`
`1
`SYSTEM FOR TRANSMITTING
`COMPRESSED DATA II? COMPRESSION
`RATIO IS AT LEAST PRESET RATIO AND
`PRE-COMPRESSED DATA IF COMPRESSION
`RATIO IS LESS THAN PRICSET RATIO
`
`'I'l£CHl'N|lCAL FIELD
`
`The present invention relates to an apparatus for and a
`method of transmitting data, compressed by a loss-less data
`compression process, between tnemorics, communication
`devices (including computer terminals), processors, or a host
`computer and an external rnemory.
`The present invention further relates to an apparatus for
`and a method of recording data, transferred from an external
`source and compressed by a loss—lcss data compression
`process, on a recording medittrrt, and more particularly to an
`apparatus for and a method of recording data in an external
`memory that can be connected to a host computer through an
`interface bus, e.g., a magnetic disk device such as a hard disk
`drive, a flexible disk drive. or the like for recording data on
`and reproducing data from a magnetic disk, or an optical
`disk drive for recording data on and reproducing data from
`a recordable optical disk such as a magnctooplical disk, at
`phase-clutngc disk, or the like.
`
`BACKGROUND ART
`
`Generally, computers have a CPU (central processing
`unit) for reading program instructions stored in a main
`memory through a memory control unit and executing the
`program instructions to process various data and control
`various devices.
`
`Program instructions are steps of a program (algorithms)
`for processing data or the like, and a program is normally
`composed of program instructions as a number of steps.
`Some computers effect only simple processing according
`to a registered smal1—scale program which is composed of a
`relatively small number of program instructions. In such
`computers. a program is already registered in a ROM in the
`computer. Iiowcver, a modern computer which carries out a
`number of data processing operations and control operations
`is required to have a separate memory means for storing a
`number of programs and data having a large data length.
`It has been customary to employ an auxiliary memory
`device such as a hard disk drive, an optical disk drive
`employing :1 recordable optical disk such as a magneloop-
`lical dislt. or a bulk-type semiconductor memory, and con-
`nect such an auxiliary memory device to a computer through
`an interface bus for storing programs and data of large
`capacity in the auxiliary Irternory device. According to
`selective startup or it re ading request from an OS (operating
`system) or an application program, it program or data stored
`in the auxiliary memory device is read into a main memory
`device for clfcctirtg data processing and controlling opera-
`tions.
`
`Present trends toward larger-capacity external memory
`devices have resulted in various techniques proposed to
`increase the recording capacity of magnetic disks and optical
`disks.
`
`With the advent of multimedia information processing in
`recent years, the amount of information required by software
`applications, e.g.. the capacity of programs and the capacity
`of data handled by programs, has increased at a rate greater
`than the rate at which the storage capacity of the external
`memory device increases. Therefore, the data compression
`technology tends to he more and more important.
`
`2
`
`One of the data compression techniques which is of the
`loss-less type (entropy coding or lost‘.-loss cording) that
`causes no data loss is drawing attention because it can
`increase an nppttrcttl capacity when data is recorded in an
`external memory device and also can cifectively use corn-
`municatiort lines when data is transmitted.
`According to a data compression process based on the
`loss~less data compression technique, data is compressed by
`reducing redundant data contained in the data. When the
`compressed data is expanded, the uncompressed data prior
`to compremion is fully restored without any loss of infor-
`mation.
`However, the loss-less: data compression technique is of
`such a nature that a compression ratio at which to compress
`data. i.-:., the ratio of the data length of uncompressed data
`to the data length of compressed data. remains unknown
`until all the data is compressed because the compression
`data varies depending on the content of the data to be
`compressed.
`According to the loss-less data compression technique.
`furthermore, binary hit map data or the like which has it very
`high level of redundancy is required to be compressed at a
`high compression ratio of 5 or more. If data that has already
`been compressed by a certain data compression process is to
`be further compressed by tho lo.-o‘.-less data compression
`process,
`then the data will be expanded in many cases.
`'I'heret'ore, the loss-less data compression technique is very
`diflicult to use.
`In the case where data is compressed at a low compression
`ratio, c.g.,
`in the case where compressed data is of a size
`which is 99% of original uI'tcoI'I'tpresscd data, no merit
`is
`attained by data compression since the data length of the
`uncompressed data and the data length of the compressed
`data remain almost the same though the data is definitely
`compressed.
`it is assumed that data to be stored in at
`For example.
`random—access external memory device such as a magnetic
`disk drive or the like is compressed to increase an apparent
`storage capacity of the external memory device. The exter-
`nal memory device stores data in lixed lengths, t:.g., blocks
`of51P. bytes. There l'ore, if 1 Khytcs ofdata are stored in the
`external memory device,
`then they are stored over two
`blocks.
`
`if such 1 Kbytes of data are compressed and the com-
`pressed data has at data length of5l2 bytes or less, then the
`compressed data occupies one block of storage area on the
`disk. Therefore, the size of storage area which is occupied on
`the disk by the compressed data is ta of the size of storage
`area which is occupied on the disk by the uncompressed
`data. an advantage that is olfercd by the data compression.
`However, if the contprlzssed data has a data length greater
`than 512 bytes, then the cornpresscd data actually occupies
`two blocks ct" storage area on the disk even though the data
`has been compressed, and the size of storage area which is
`occupied on the disk by the compressed data is the same as
`the size of storage area which is occupied on the disk by the
`uncompressed data.
`In such at ease. the entire system only causes a wasteful
`expo nditure of the time required for data compression (IF the
`data is expanded. the time required for data compression!
`expansion), and the electric energy required by the CPU and
`a hardware arrangement dedicated for data compression. and
`may possibly suIl"er poor performance due to the data
`compression. If the compressed data is read from the exter-
`nal memory device for transmission to the computer. then
`since the data needs to be expanded, the time required for
`expanding the data is also consumed wastcfully.
`
`a.
`
`.10
`
`13
`
`40
`
`5!]
`
`hill
`
`65
`
`

`
`5,805,932
`
`3
`ln comrnunications applications where compressed data is
`divided into packets of fixed length for transmission, there
`are instances in which the number of packets occupied by
`uncompressed data and the number of packets occupied by
`compressed data may he the saint: as each other, posing a
`limitation on efforts to improve the entire system perfor-
`mancc.
`
`It‘ data is compressed according to the loss-less data
`compression process to shorten a time required to transfer
`data between a computer and an external memory device for
`the purpose of using communication lines more effectively,
`then a transfer time tM_,., required for transmitting the corn-
`presscd data is shorter than a transfer time 1,4,: required for
`transmitting the uncompressed data, as shown in FIG. 43 of
`the accompanying drawings.
`\l\’hen the data is comprcssetl. a time lm required for data
`compressionfexpansion is newly needed in addition to an
`actual data transfer time tc. 1. However. since the data to be
`actually transmitted is compressed. the apparent data lcngth
`is reduced. Therefore,
`the data compression shortens the
`transfer time as a whole. In order to shorten the trattsfcr time,
`it is necessary to compress the data rapidly to reduce the
`time 13, required for data compressionfcxpansion.
`lfthe tlata is compressed at a low compression ratio, then,
`as shown in FIG. 44 of the accompanying drawings. because
`an actual data transfer time tm is not reduced substantially,
`the addition of a time tn: reqttired for data comprestiionl
`expansion results in a transfer time tym: required for trans-
`mitting the compressed data which is longer than a tran.sfer
`time I“ required for tr:-zns.n1ittin.g the uncompressed data.
`Consequently. the data compression does not offer merits,
`hut instead lowers the overall system performance.
`For data transmimion between a host computer and an
`external memory device,
`the host computer performs the
`above function of loss-less data compression. With a plu-
`rality of external memory devices connected to the host
`computer, however, a long calculating time is required to
`compress data for transmitting diiIercnt data fmm the host
`computer to the plural external memory devices, and hence
`a considerable period of time is necessary until the transfer
`of data to all the external memory devices is completed.
`Stated otherwise. for trausntilting different data from the
`host computer to the plural external memory devices. the
`host computer is tied up with the data compression, and
`cannot perform other processing.
`Naturally.
`the apparent storage capacity of only those
`external memory devices which are connected to a host
`computer capable of compressing data can be increased.
`That is. only those external memory devices connected to a
`host computer capable of compressing data are given the
`advantages of data compression. An external memory device
`having a disk on which compressed data is recorded can be
`operation for data reproduction by only a host computer
`capable of expanding compressed data.
`if an external memory device incorporates a data com-
`pression function for allowing individual external memory
`devices to compress data. then the time required for a host
`computer to compress data can be eliminated, and a host
`computer having no data compression capability can enjoy
`the advantages of data compression at external memory
`devices, i.c., an increased apparent storage capacity. Such a
`host computer is then able to handle various programs and
`data.
`
`A data compression l'lJt‘tCllUl'l that can be incorporated in
`an external memory device may be perfonned by a loss-less
`data compression technique by which expanded data is made
`
`ll)
`
`10
`
`J
`
`‘J!
`
`35
`
`40
`
`St]
`
`55
`
`an
`
`65
`
`4
`exactly the same as input data. -:._g., the known Ilulfntann
`coding technique or LZW {Lempel-Ziv and Weich) coding
`technique. rather than a data compression technique that
`causes a data loss, which is used to compress digital audio
`data corrvcrtcd from analog audio data or digital image data.
`c.g.. the known discrete cosine coding technique. It’ such :1
`loss—lcss data compression technique is employed, then the
`compression ratio varies depending on the contents of
`supplied data, c.g.. depending on how much the same words.
`the same ctcpremiions, etc. are used in the data.
`Specifically, if it is assurncd that tt compression ratio to be
`expected (hereinafter referred to as an "expected compres-
`sion ratio“) whcn uncompressed data is compressed by the
`loss-less data compression technique has a value of 2, then
`when one logic block of data having a certain data lcngth
`which is transferred from a host computer is compressed by
`an external memory device, the compressed data has a data
`length equal to one physical block whose size is ‘é of one
`logic block provided the data is compressed as expected, i .e ..
`the data is compressed at the same compression ratio as the
`expected compression ratio. In this instance, two physical
`|)lock.s are equal to one logic block.
`Therefore, an optical disk having a physical capacity of
`500 MB (Megaliytel has an apparent capacity of 1 GB
`(GigaBytc) as seen from the host computer. However. when
`the loss-less data compression technique is employed, since
`the data length of compressed data may not necessarily bi: bi
`or less of the data length of the uncompressed data. one logic
`block of transferred data may not be contained within one
`physical block.
`inasmuch as data compression may possibly result in data
`expansion, one logic block of data may be expanded into
`data over three or more physical blocks. Such a phenomenon
`occurs when an actual compression ratio is less than I.
`In this case. the system performance is lowered regardless
`of efforts to increase the performance by increasing the
`apparent capacity by way of data compression. Specifically.
`even though data is compressed. at physical capacity which
`the compressed data occupies on an optical disk remains the
`same as or is greater than the capacity of one logic block.
`When the compressed data is to he read, a time is required
`to expand the compressed data. Consequently,
`the com»
`prcss-ed data occupies the same space on the optical disk as
`would if the data were not compressed, and an additional
`time is needed to expand the compressed data when it is to
`be read. As a result, it is possible for the system to fail to
`olIer any advantages from data compression.
`Data is randomly recorded on and reproduced from it
`magnetic disk or an optical disk. I-‘or recording compressed
`data over two or more physical blocks on an optical disk, for
`example. the data is randomly recorded in physical blocks.
`for example.
`'l'herc are occasions where mutually related compressed
`data over two or more physical blocks are recorded in
`physical blocks at spatially spaced positions on a rnagnetic
`or optical disk. Such instances manifest themselves where
`data is to be randomly recorded on a magnetic or optical disk
`on which data has already been recorded. When data are to
`be read from the magnetic or optical disk,
`at seeking
`(searching) process for searching for the mutually related
`compressed data is lime-consuming resulting in a long
`access time.
`
`The present invention has been made in view of the ahove
`problems. It is an object of the present invention to provide
`an apparatus for and a method of transmitting data for
`increasing overall system perforruance by transmitting
`
`

`
`5,805,932
`
`5
`either uncompressed data or compressed data based on the
`data length of the uncompressed data, the data length of the
`compressed data, and a preset condition.
`Another object of the present invention is to provide an
`apparatus for and a method of recording data for making it
`unnecessary to expand recorded data, of the data recorded on
`a recording medium. whose actual compression ratio satis-
`fies :i cerium condition, so that the data can be read from the
`recording medium at a greatly increased rate.
`Still another object of the preaznt invention is to provide
`an apparatus for and 21 method of recording data for pre-
`venting two or more physical blocks of data from being
`recorded in physical blocks at physically spaced positions.
`but recording them in areas corresponding to two or more
`suceessive physical blocks for thereby etfectively shortening
`a seek time consumed for reading data.
`
`U.
`
`10
`
`DISCLOSURE OF THE INVENTION
`
`transmitting data according to the
`An apparatus for
`present invention comprises pre-compression data holding
`means for holding pre—comprcssion data. data compressing
`means for compressing the pre—compression data held by the
`prc-compression data holding means, compressed data held-
`ing means for holding compressed data from the data
`compressing means. decision means for determining data to
`be transmitted, based on data lengths ot' the pre-compression
`data and the compressed data and a preset condition, and
`data transmitting means for transmitting either one of the
`pre-compression data held by the pre—con1pression data
`holding means and the compremed data held by the com-
`pressed data holding means, based on the data determined by
`the decision means.
`
`6
`transmitted as the pre-compression data if the actual com-
`pression ratio is smaller than the preset compression ratio.
`Further alternatively, the decision means may comprise
`means for determining the data to he Lrartsmittcd as the
`compressed data if an actual difference between the data
`lengths of the pre-compression data and the compressed data
`is at least a preset difference and also if an actual comprcs~
`sion ratio of the data length of the precomprcssion data to
`the data length of the compressed data is at least :1 preset
`compression ratio, and determining the data to be transmit-
`ted as the pre-compression data otherwise.
`It is assumed that an arrangement is employed to transfer
`compressed data when the actual difference is at least the
`preset dilfcrence. With the preset dilferenee being 512 bytes.
`for example, if the pre~compres-sion data has a data length of
`2 Kbytes, then compressed data is transferred when the data
`length of the compressed data is 1.5 Kbytes or shorter.
`Similarly. if the pre-cornpression data has a data length of
`1 Mbytes (1000 Kbytes). then compressed data is transferred
`when the data length of the compressed data is 999.5 Khytes
`or shorter.
`
`The ratio (actual compression ratio) of the pre-
`comprcssion data (data length=10DU Kbytes) to the com-
`pressed data (data lengths-999.5 Kbytcs) is about 1.0005.
`and the percentage of the data length (corresponding to the
`data length difference} removed by the data compression
`with respect to the data length of the pre-compression data
`is only 0.(t5‘K.-_ With this compression ratio, the data length
`ofthe compressed data re-mains substantially the same as the
`data length of the prmcomprcssion data.
`Consequently, when it
`is determined whether the com-
`pressed data or the prc—con1prcssion data is to be transferred
`based on only the comparison between the actual dillerence
`and the preset dillerunce, if the actual dillercnce is equal to
`or greater than the preset difference-. then the compressed
`data is transferred even though the data length of the
`compressed data remains substantially the same as the data
`length of the prc-compression data. As a conmquence. the
`compressed data needs to be expanded over it period of time
`which is not short, resulting in a wastehil expenditure of
`time.
`
`According to the above decision process, however, com-
`pressed data is transferred only when the actual dilference is
`at least the preset difference and the actual compression ratio
`is at least the preset compression ratio, as described above.
`Thus, even when the actual difference is at least the preset
`dilference, no compressed data is transferred, but the pre-
`cornpression data is transferred, if the actual compression
`ratio is smaller than the preset compression ratio. In this
`case, no time-consuming data expansion process is carried
`out in the data destination, so that any wasteful expenditure
`of time occurs in the data destination.
`to this manner, the
`overall system performance is improved.
`The decision means may comprise means for determining
`whether an actual compression ratio ofthe data length of the
`pre-compression data to the data length of the CLll'lZIpf€8‘eil.:(.l
`data satisfies either one of two preset conditions, determin-
`ing the data to be transmitted as the pre-compression data it‘
`the actual contprcssion ratio satisfies one of the two
`conditions, and de