I|||||||||||l||||||||||||||||||||||||||||l||l||||||||||||||||||||||||l|||||
`
`USU(}58[]5932A
`
`United States Patent
`Kawashima et at.
`
`[19]
`
`[11] Patent Number:
`
`5,805,932
`
`[45] Date of Patent:
`
`Sep. 8, 1998
`
`[54]
`
`SYSTEM I"OR TRANSMITTING
`C()Ml’RI‘ZSSl.'1l) DATA II‘ COMPRESSION
`RATIO IS AT LEAST PRESET RATIO AND
`PRE-COMPRESSED DATA IF COMPRESSION
`RATIO IS LESS THAN PRESET RATIO
`
`|7S]
`
`Inventors:
`
`'l'etsu_ji Knwashima: 'I3tt.Isuya
`Innkuchi. both of Kanagawa. Japan
`
`I73] Assigneez Sony Curpnmlittn, Tokyo, Japan
`
`[21] Appl,No.:
`
`564,144
`
`[22
`
`PCTI-‘ilcd:
`
`Apr.2l, 1995
`
`[an]
`
`PC'l‘No.:
`
`PCTl.lP95fl)0'.-'95
`
`§371 Date:
`
`Feb. 13, 1996
`
`§ lt]3(I:} Dttte; Feb. 13, I996
`
`|87]
`
`PCT Pub. No; W095,«’2943‘7
`
`PCT Pub. Date: Nov. 2. 1995
`
`|3[I]
`
`Foreign Application Prim-ity llnta
`
`Apr.22, 1994
`step. 11 1994
`
`[JP]
`[JP]
`
`Jaflan
`Japan
`
`-‘_'1—I_l84‘J5U
`I'i—.-‘.|h‘J2fu‘
`
`Int. Cl.”
`[5l|
`|52] U.S. Cl.
`
`G06!’ 3100
`_________________________ _ 3951888; 3953427; 3‘J5i'433;
`3I5tl!48
`
`|58]
`
`Field of Search
`
`395E838, 427,
`360.-’48; 361.-"_’6[|.h'
`
`|56]
`
`References Cited
`U .5. PATl:‘N'I' DOCU MENTS
`
`5.-'ifi'?.flS-7
`5_.:'n‘Jl_.S24
`
`1lfl.‘J'95 Chtl
`Ill.-'l9‘)fJ Ctirrciro cl
`
`:1].
`
`3-HIS]
`395.5872
`
`P:'£mm'__\-' £'.\‘nrrti:rc*r—'I‘homas C‘. Lcr:
`A5.'ni5'ti'rrtt E.t'mttt'm?t'—Andersnn 1. Chen
`
`AttiJrtte-'_v, Again‘, or Ffrm—Fmn1n1er Lawrence & Ilang
`|_l.P; William S. I-‘mmmcr
`
`[57]
`
`ABSTRACT
`
`A Lliffercitccfcomprcstsion ratio uilcultttjng means 76 in :1
`data processing means 71 of a data transmitting apparatus
`according to the present
`invention calculates-;. an actual
`diliercncc and an actual compression ratio hased on the data
`length of pre-cuimpressiun data received from a data source
`2 through pre—co1rtprcssion data receiving means 74 and the
`data length of C[lH1pI€SSE(i
`data outputtcd lrom a data
`cornprcssion circuit 67. If the actual difference is equal In or
`greater than a prcecl rliflcrcnoc til‘. and the actual compression
`ratio is aqua] to and greater than a preset L‘OlT1]JI‘CaSfi‘i(ll'I ratio
`fl. then the compre:-med data is transmitted to :1 data desti-
`nation 3 Ihrnugh :1 transfer request data output means. 79
`Otherwise, the prc—cornpres¢;ion data is transmitted to the
`data destination 3. With this arrangement. it is pt'!SSIbIC to
`prevent it phenomenon in which the size (If 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 destination 3.
`
`-4,‘}3'iI‘,(_i&il
`
`l':u't9'Jli
`
`l"Lt_iinawa. ctal.
`
`355i,!42f_I
`
`30 Claims, 40 Drawing Sheets
`
`Oracle 1003
`Oracle 1003
`
`

`
`U.S. Patent
`
`Sop. 8, 1998
`
`Sheet 1 of 40
`
`5,805,932
`
`F/5.7
`
`APPARATUS
`
`DATA
`TRANSMIITING
`
`DATA SOURCE
`
`F/5.2
`
`1
`
`KEY INPUT
`MEANS
`
`11
`
`DATA
`TRANSMEITTNG
`APPARATUS
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 2 01'-10
`
`5,805,932
`
`F/6.3
`
` GI%flWICEMDN
`DATA
`DEVICE
`fl%WSMEHENG
`APPARATUS
`
`
`
`31
`
`
`
`19
`KEY INPUT
`MEANS
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 3 01'-10
`
`5,805,932
`
`F/5.5
`
`F/5.6
`
`51
`
`DATA
`'I‘RANSMI'I'I‘IJ:~.G
`APPARATUS
`
`EXTERNAL
`MEMORY
`
`18
`
`KEY INPUT
`MEANS
`
`
`
`
`
`
`DATA RAM
`
`

`
`U.S. Patent
`
`Sup. 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. 3, 1993
`
`Sheet 5 01'-10
`
`Maa,50om,5
`
`E8
`
`zamwomm
`
`sou
`
`zoHa¢zHamun
`
`4FflQ
`
`mama ’
`
`EonI
`
`uzHzxoz
`
`anmaao
`
`2¢m
`
`Iamenmm
`
`we
`
`wn::rt..1|||||.-.:1|||Ia-::nn1|L-
`
`N_.
`
`mumaom
`
`dkda
`
`mmgqomszou
`
`E.
`
`FDQZHmum
`
`mzamz
`
`mfibi
`
`
`
`

`
`
`
`M...muammflfimmzéu.
`
`
` 68MmafiahSE8mzfi:S.33HwmammozfinnmEan
`
`
`
`
`
`5.39528ammmzcfi.Emmmmmfib2
`
`
`
`zoE.sE.mE¢..H_¢d
`
`mama .8an
`
`P83m.b\n\
`
`
`
`
`
`mafiaufieémsmm
`
`mzfi:
`
`.,5:8EaE32mfiwwmfiasmwafiaum
`
`«M
`
`t3
`
`CS
`
`D..
`
`on;
`
`m1
`
`M
`
`5
`
`50
`
`3,cmEEmean
`
`3932
`
`
`

`
`U.S. Patent
`
`Sup. 3, 1998
`
`Sheet 7 01'-10
`
`5,805,932
`
`F/6.70
`
`S1
`
`INITIALIZE
`
`S2
`
`TRANSFER PROGRAM
`TRANSFER ROM DATA
`
`53
`
`54
`
`S5
`
`55
`
`S7
`
`58
`
`S9
`
`REI;U]E‘..'S'I'
`
`YES
`
`No
`
`STORE KEY INPUT
`DATA
`
`READ AND STORE
`IQPEEF-p‘i30PfPRESSION
`
`PRE—(I)MPRESSION
`" R I-«— DATA LENGTH
`
`CIJTPUT ALL PRE SICN
`To DATA <n~:pRBssIon
`
`STORE COMPRESSED
`DATA
`
`PRE—c:t:mPREssIoN
`"' R 2 --DATA LENGTH
`
`0
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 3 0l'40
`
`5,805,932
`
`F/5.77
`
`PRE SION DATA
`
`
`
`IDIEURMA'I'IOl\I
`CU'I'PU'I'
`CODE EUR MESSAGE
`INDICATING THAT DATA
`IS N01‘ CCMPESED
`
`
`
`
`S14 INDICATING THAT DATA
`
`IS. SED
`
`

`
`._.IHPut3PQMU
`
`Sup. 8, 1998
`
`Sheet 9 of-10
`
`5,805,932
`
`09
`
`
`
`zoaaazaammn4942
`
`E#EHD_d§UHm
`
`mzmmz
`
`mmmmzmma
`
`Emfififid
`
`ZOHmHUmD
`
`
`
`
`
`zazuommuzmmmmuozmaaan
`
`ZHAQOKBZOU
`
`
`
`gazeEWEHEK
`
`mmmmzxme
`
`EDQEDD
`
`mfiflfi
`
`zaHmmm5an
`
`QEEUHDKQ
`
`UZHHQHHHFD
`
`055$
`
`mz¢mz
`
`
`
`muammm:mm.._mz5_a
`
`E5Egg
`
`
`
`pmwfiwmuzflzmmzmu
`
`mzfiz
`
`mmmmam
`
`WZDEME
`
`mm
`
`8
`
`cm
`
`
`
`agedzoHmmmm&AHTmmm
`
`
`
`mamaQEBHHHE
`
`mmqqomazou
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 10 M40
`
`5,805,932
`
`F/6.73
`
`TRANSFER PROGRAM
`TRANSFER.ROM DATA
`
`GD
`
`5103
`
`3104
`
`ES
`
` NO
`
`STORE KEY INPUT
`DATA
`
`READANDSIURE
`
`81°‘
`
`5102
`
`5105
`
`II 5107
`
`GM£1EfiIE PEEDICTED
`0flfl%EBSFHJRATIO
`
`CIIMPRESSION
`RATIO EE'.E'EI.’I'IVE 2
`
`N0
`
`S103
`Sm
`
`GENE.'RATE mnsrm Razors’:
`g:::mRPRE~m°~ESSI°"
`
`
`
`
`GENEEATE mmsrm RB2‘_IJ'ES'I‘
`DATA ma cxznvrpnzssza
`DATA
`
`OUHKE EEUMWHIONKIDE
`FURbfiEEAGE INDICHIBWSTHWT
`DQTA IS NOT UUEEESSED
`
`GH?UTINFm%EEIG§CDUE
`FER MESSAGECDEECATING TENT
`cmam IS CDMPRESSED
`
`5113
`
`(A
`
`

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

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 12 M40
`
`5,805,932
`
`mmmmmam
`
`
`
`.mmozmzzoamwuma
`
`mzamz
`
`3.
`
`mm
`
`
`
`mzmmzuzuemaauaau
`
`uzn%mm.s5a
`
`ammmmgab
`
`m§fiE
`
`IHEETH
`
`F55fifim
`
`uzaaam
`
`mz¢m:
`
`
`
`
`
`omammzoHmmmmmzoonmaomammm
`
`
`
`
`

`
`U.S. Patent
`
`Scp.8,1998
`
`Shcet13 uf40
`
`5,805,932
`
`F/6.76
`
`Szcn
`
`INITIALIZE VARIOUS
`PARAMETERS
`
` S202
`
`REfl)PREHOflfl¥&SSfl1IDAIA
`
`
`
`UH?UEREM)Em$Cflfl%ES—
`SHIIDHHKTOINHE Oflfi¥ES—
`SHWJCKT
`
`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. 8, 1993
`
`Sheet 14 M40
`
`5,805,932
`
`F/5.77
`
`111
`
`57
`
`69
`
`DECISION
`MEANS
`
`BUFFER
`MEMORY
`
`
`
`DATA COMPRESSING MEANS
`
` 96
`
` PRE43}flEEE-
`
`
` 115
`STORAGE
`
`ADDRESS
`UHLULNNWG
`MEANS
`
`SIDNlflfl
`REMXNG
`MEANS
`
`
`
`DATA RAM
`
`
`
`64
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 15 M40
`
`5,805,932
`
`F/5.78
`
`START
`
`5301
`
`EUR PRE4fl1fi%ESSflIlEE3A
`
`HEFGHEHESHXIHME
`
`REED PRE4flIflEEBSIG
`EHTR
`
`3Eg5%‘agg
`STORE COMPRESSED DATAIla
`
`DNHRTU DATA Oflfl¥ESSING
`
`COMPRESS DATA
`
`CALCULATE STORAGE
`ADDRESS FOR NEXT
`COMPRESSED DATA
`
`EEIEEE PORTION OF
`PEEFCEMPRESSION DATA
`
`2 O
`
`1
`
`+
`
`HI ID
`
`RETURN
`
`S303
`
`530A
`
`S305
`
`S306
`
`S307
`
`S308
`
`S309
`
`S310
`
`

`
`U S Patent
`
`S
`
`5
`
`0
`
`M3,
`
`we.1.1.wmT\mI2wA4Ir.2.UIzmamwm
`s,3E.5.
`
`Iufimwmuommmzwfifimmfi_W.I.V:_mm.as
`«H_madmflmmfl
`flO.H.€..:...m_O—.flmn_LNImm.EoE.zou,95.o.Hv.n.;._
`
`
`
`
`
`5-
`3,_
`
`
`
`BMEufimauaz
`
`.30EnmasfifiwNm
`
`Ox
`V‘--.
`
`Q3
`
`LL
`
`
`

`
`U.
`
`8tum
`
`fl
`
`5
`
`M3,
`
`..m92mmmmamhi
` m...N2.mmmmam&E6mmgafioBu: E5.55%as5macaw:
`
`:85.8Esau:
`
`
`emu.s.23at
`
`Eauzvaoz
`
`.H5.43
`8mt_55at9zamzfixm
`
`
`09wemufizmhfi
`
`nozmamam
`%mmaqomezou
`
`E
`
`Ima
`
`_1ER5557 EI %ms
`on
`
`
`

`
`5,805,932
`
` U.S.Patent
`
`Scp.8,1998
`
`Sheet18M40
`
`m.2zmm.S¢M6.
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 19 M40
`
`5,805,932
`
`
`
`F/5.22
`
`
`
`CONTENT
`
`DDS
`
`SEXIIUR
`
`RECORDED
`
`
`
`Ir:
`
`
`
`UNCERTIFIED
`
`
`CERTIFIED
`
`_._—_—.-.4.
`
`
`
`.—-u_s-1-...-._
`
`
`
`
`0 2
`
`01
`
`-——_.—.._
`
`-u—:u-..-n
`
`
`
`I
`
`l
`
`FILE ALLOCATION
`
`TABLE
`
`I
`
`p + Q
`
`FILE ALLOCATION
`TABLE
`
` I
`
`.
`
`
`
`
`
`1
`
`I
`I
`I
`
`2°“ 1
`
`

`
`
`
`zoBEE.=,S.mu¢z§as
`
`_u
`
` U.S.Patent
`
`
`
`umHn_.H¢UH.H_mQvHmvU¢2
`
`Scp.8,1998
`
`Sheet20M41}
`
`‘I5
`
`805,932
`
`
`

`
`U.S. Patent
`
`Scp.8,1998
`
`Sheet 21 M40
`
`.503,5
`
`M3,
`
`
`
`
`
`xaaaomazouzmemmmmzamz
`
`mh_
`
`amom
`
`zoamuumn
`
`
`
`mmaamzouawe:
`
`mamz
`
`uzbummammmzamz
`
`
`
`
`
`aamaaozamuommuzHmmmuomm¢y¢a
`
`—_N
`
`uzamwmuomm
`
`mzmmz
`
`uzHmmmuomm
`
`emmaamm
`
`mzmu:
`
`
`
`Qfifififififidmamas
`
`
`
`m:e4smGZOUMM
`
`mzmm:
`
`zoamaumm
`
`mz¢mz
`
`
`
`
`
`D¢DAz==mH:zommnumn
`
`New
`
`#59...‘
`
`fifl5&fiU_fl5:
`
`mom
`
`
`
`mmqaozzaozammw
`
`OzHE¢A:UQdU
`
`m2¢mz
`
`
`
`mmmmnn¢eammz¢m:
`
`BHEgum
`
`uzHmmmomm
`
`24mdfidfl
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Scp.8,1998
`
`Sheet 22 M40
`
`5,805,932
`
`F/G. 25
`
`START
`
`540:
`
`54°?
`
`'
`mum NBHNG
`
`=
`
`3
`
` 0UUHKE A
`mm _
`
` yms
`
`
`
`wrwr mzgggqwlmm
`333%
`INITIRLI
`GE‘NE.TRA'I'E
`CINPUTEV
`REDORD SIATUS
` THEE
`
`SUBROUTINE
`
`.REQUESTI 5"”
`
`YES
`
`

`
`U.S. Patent
`
`Scp.8,1998
`
`Sheet 23 M40
`
`5,805,932
`
`F/G. 26
`
`
`
`SET bTH IN
`RECORD STATUS
`TABLE
`
`
`
`
`
`

`
`tHEtaPamU
`
`m...&
`
`8m8..
`
`2
`
`N
`
`M0.”,503,5
`
`SnEco.uoflooom
`
`MWafilaual
`
`MinSzuofomom
`
`
`
`
`:3BHG39.0..‘HOm~.OOONmadama%m¢B
`
`
`

`
`3PQM
`
`tn
`
`0S
`
`n....
`
`w81.
`
`Pu-..mmmT\
`
`n99508.,5
`
`
`
`Mmmmfiomzneoommam
`
`._l
`
`
`
`Man:,§_I.flanHBHM35mm»
`
`mm3mH.EzH%E
`
`m.5%WZHBUDEMDW
`
`
`

`
`QMU
`
`fl3D1
`
`{IHPu
`
`Sup. 8, 1993
`
`Sheet 26 of 40
`
`5,805,932
`
`
`
`mmaaomazouzmamam
`
`mmaamGUemu:
`
`2..
`
`EDQBDO
`
`amen
`
`uzHamm=omm
`
`mzum:
`
`MBHMB
`
`uznammaomm
`
`mzmm:
`
`n¢mm
`
`HEEBEW
`
`UZHBHK3
`
`mz¢mz
`
`¢a¢n
`
`EOE¢a¢n
`
`
`
`mzwmzOzHMHQ¢HBH2H
`
`QNGI
`
`fifififiiwfiflf
`
`mt
`
`fiHE5EEflU.fiEHMm
`
`mamamam
`
`Qfifikfiflfi
`
`mzamz
`
`«om
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 27 of 40
`
`5,805,932
`
`F/5.30
`
`SIDREI INITIALIZING
`
`%%T%.n_¥§ ngfnm Am‘
`
`
`
`
`5715
`
`SUBROUTINE
`WRITE
`A'I'I'3IHU'I'E
`DATA
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 28 of 40
`
`5,805,932
`
`FIG. 37
`
` SBOI
`
`
`
`GENERATE WRITE
`REQUEST DATA
`
`S805
`
`ISEM36
`
`S802
`
`3803
`
`TRANSFER WRITE
`REQUEST (TPACK 9997}
`
`8804
`
`GBflfimEEEfiUTE
`REQUEST DATA
`
`TRANSFER WRITE
`
`REQUEST (TRACK 999$
`
`S808
`
`
`
`
`
`S807
`
`
`GENERATE WRITE
`EQUEST DATA
`
`
`
`TRANSFER WRITE
`REQUEST {TRACK 0]
`
`GENERATE WRITE
`REQUEST DATA
`
`T
`TRANSFER WRITE
`REQUEST {TRACK 1)
`
`

`
`U.S. Patent
`
`Sup. 8, 1998
`
`Sheet 29 of 40
`
`5,805,932
`
`HmmaommManx:
`
`
`
`UZHSEEUSEED
`
`mzams
`
`zmm¢B¢D
`
`on
`
`
`
`mmadmzouemu:
`
`
`
`mwaaomazouzmamwm
`
`ht.mt
`
`mmmmam
`
`wmozma
`
`zonmmmmmzou
`
`dfidn
`
`BXU
`
`ZOHWHUMD
`
`mzaw:
`
`No.»
`
`HHEEEHBQH.
`
`mmmm
`
`
`
`mz4m2DZHBHEB
`
`a:mzH
`
`axon
`
`mt
`
`MBDMH
`flhbfl
`
`uzH>Hmumm
`
`mzmmz
`
`¢a4n
`
`
`
`KHEUFERDEamam
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Scp.8,1993
`
`Sheet 30 M40
`
`5,805,932
`
`FIG. 33
`
`S T A R T
`
`S901
`
`
`N 3912
`
`
`ISUBROUTINE
`RECEIVE DAT:
`FROM HOST
`Mm DATA
`
`com:-uTER_
`
`STORE DATE
`R3* G mm
`
`3903
`
`OUTPUT WRITING DATA TD
`am cmvnfissrow
`.C'-"(T
`
`3904
`
`compnnss
`DATA
`
`STORE CEME’RE‘SSE'D DAT
`R4- DATA
`
`3905
`
`S906
`
`CALCULATE
`compnssszcm RATIO
`
`S907
`
`8908
`
`
`
`8914
`
`‘WRITE
`ATTRIBUTE mm
`
`' $95
`
`'2
`
`R I-— 0
`R 2-— B
`
`8910
`
`I
`RI --=---
`R2--13/cg”)
`
`I 39: I
`
`GENERATE
`FAT
`
`

`
`U.S. Patent
`
`Scp.8,1998
`
`Sheet 31 M40
`
`5,805,932
`
`FIG. 34
`
`START
`
`xmmmmzmm
`
`SAOI
`
`SAIQ
`
`
`
`SUEROUTINE
`STORE
`ADDRESS
`
`
`
`READ aazznnspcmms arr
`smrnc: man man RECDRD
`STATUS TABLE
`
`31:03
`
`35.04
`
`

`
`U.S. Patent
`
`Scp.8,1998
`
`Sheet 32 M41}
`
`5,805,932
`
`FIG. 35
`
`SAIO
`
` N
`
`Y
`
`S
`
`3A"
`
`SAI2
`
`SAI3
`
`SAM
`
`SAI5
`
`k'I'H RECORD or BIT
`DATA
`SKEUEIAREA
`
`
`__..j
`
`
`
`SUBROUTINE
`STORE
`ADDRESS
`
`
`
`k--——-(K) -i-
`
`I
`
`N
`
`SM8
`
`G S
`
`A|6
`
`N
`
`SN?
`
`Y
`
`RRE—cxmpREssIoN DATA
`?
`
`I
`
`57093 "FFF5‘°0" 33“ 1-INK
`ADDRESS STORAGE
`AREA
`
`STORE "FPFF01" IN
`LINK ADDRESS
`STORAGE AREA
`
`f RETURN
`
`J
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 33 M41}
`
`5,805,932
`
`FIG. 36
`
`
`
`
`GENERATE 1TH AND
`FOLLOWING RECORD OF
`TABEEIEHE SKEmGEJ¥ER
`
`
`
`GENERATE OTH RECORD
`OF TABLE DATA
`STORAGE AREA
`
`SET (j)TH BIT OF
`RECORD STATUS TABLE
`
`SBOI
`
`SBO5
`
`

`
`Sheet 34 M40
`
`5,805,932
`
`SCOI
`
`SKXJZ
`
`SC05
`
`SCO7
`
`
`
`
`
`READ ONE BLOCK OF
`Dxnanwmcxnmusmm
`DHNKSKRNEINEE
`
`GENERATE wnxrs
`REQUEST DATA
`
`TRANSFER wan}:
`REQUEST
`
`U.S. Patent
`
`Scp.8,1998
`
`FIG. 37
`
`START
`
`SELECT iTH RECORD
`0F1flI£]WflR.SKEmGE
`AREA
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 35 of 40
`
`5,805,932
`
`
`
`mmaamzouawe:
`
`oh_
`
`uzHmmmoomm
`
`mzamz
`
`momma
`
`uzaammaomm
`
`mzmm:
`
`n¢mz
`
`uzuewmpomm
`
`mmmmzmms
`
`mzamz
`
`wean
`
`
`
`zoamzamxmzOHmHUmD
`
`
`
`emumzmm:
`
`
`
`mzamzuzHo¢mm
`
`BDQZH
`
`axon
`
`5.
`
`Hflbafifihflfim
`
`
`
`ZMAAOEBZOUzmamwm
`
`
`
`z%HEEfiUatmwm
`
`m»_mmmmam
`
`HMOSMZ
`
`mmsfi
`
`mom
`
`QHESBB
`
`¢amn
`
`uzamoam
`
`mz¢m:
`
`zmmmama
`
`uz>Hmomm
`
`mzmmz
`
`dfidfl
`
`mom
`
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet 36 of 40
`
`5,805,932
`
`500.
`
`FIG. 39
`
` READ DATA
`
`FROM HOST
`
`COMPUTER
`
`SD02
`
`SD09
`
` SEL'.EX'.‘I' iTH REIIIRD
`IN FILE MIKE-
`TION TABLE
`
`

`
`QMnu
`
`fl3D1
`
`inHPu
`
`Sup. 8, 1998
`
`Sheet 37 M40
`
`Mau.3nu9.3
`
`
`
`mmaamzouHMO:
`
`mu.
`
`aamaao
`
`axon
`
`
`
`mmaaomazouzmamwm
`
`ax
`
`UZHNHAQHEHZH
`
`mzmmz
`
`amoumm
`
`uzbmm_¢naa
`
`maamnmsam
`
`mzamz
`
`m3§E
`
`mmmmnom
`
`r4HHfi¢U
`
`BHM
`
`UZHENUHM
`
`mzmmz
`
`aaaa
`
`mommom
`
`
`
`fiHE5flfiUaamwm
`
`wowwow
`
`Q+\.bE
`
`
`
`mzcmzUZHBMQMQmean
`
`BMOQ
`
`eamzamug
`
`_om
`
`ZOHmHUMD
`
`mzmmz
`
`
`
`fiFEfi?fiUemom
`
`
`
`
`
`

`
`U.S. Patent
`
`Sup. 8, 1993
`
`Sheet38 uf40
`
`5,805,932
`
`FIG. 47
`
`SE09
`
`SE10
`
`SE1!
`
`hl
`
`SEJ2
`
`SE33
`
`SEP4
`
`SEl5
`
`
`
`ADDRESS
`
`RESET CORRESPONDING
`BIT IN RECORD
`STATUS TABLE
`
`LINK ADDRESS ?
`
`SELECT NEXT
`RECORD
`
`INITIALIZE
`PRECEDING RECORD
`
`INITIALIZE
`CORESPONDING RECORD
`
`I SUBHOUTINE
`
`WRITE
`ATTRIBUTE
`DATA
`
`I
`
`SEED!
`
`SE02
`
`SE03
`
`SE04
`
`SE05
`
`N
`
`SE06
`
`SE07
`
`SE08
`
`START
`
`El!
`
`
`
`READ DATA FROM
`HOST conpuwzn
`
`_
`SELECT 1TH RECORD
`IN FILE ALLOCATION
`TABLE
`
`NO
`sun. nancmmmms
`?
`
`Y
`
`i-=--(i)+l
`
`
`
`PROCESS
`
`RETURN
`
`

`
`U.S. Patent
`
`Sup. 3, 1993
`
`Sheet 39 of 40
`
`5,805,932
`
`F/5.42
`
`Exmanmn Oflfi§ESSIDN
`
`RATIOfi
`
`+
`MAXIMUM RECORDING
`CAPACITY
`
`O
`
`

`
`U.S. Patent
`
`Sup. 3, 1998
`
`Sheet 40 of 40
`
`5,805,932
`
`FIG. 43
`
`m
`
`DATA NOT COMPRESSED
`
`DATA COMPRESSED
`
`I
`r
`
`
`Cl
`
`T
`
`Tau
`I
`
`
`
`
`
`
`
`
`H5. 44
`
`
`
`
`
`Tncz
`
`Tcz
`
`T 32
`
`
`
`.:9:$.
`
`.5’;
`
`DATA COMPRESSED
`
`

`
`5,805,932
`
`1
`SYSTEM FOR TRANSMI'I‘TING
`COMPRESSED DATA Ht‘ COMPRESSION
`RATIO IS AT LEAST PRESET RATIO AND
`PRE-COMPRESS ED DATA IF COMPRESSION
`RATIO IS LESS THAN l’Rl'ISliT RATIO
`
`'I'EClINlCAL FIELD
`
`The present invention relates to an apparatus for and a
`method of transmitting data. compressed by a loss-less data
`compression process, between memories, communication
`devices (including computer tenninals), processors, or a host
`computer and an external memory.
`The present invention further relates to an appararus for
`and a method of recording data. t'ranst'erred from an external
`source and compressed by a loss-less data compression
`process, on a recording medium, 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., it magnetic disk device such as it hard disk
`drive, a llcxible 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 :1 magnetooplical disk, a
`phase-cliangc 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 norntally
`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. Ilowcver, a modern computer which carries out a
`number of data processing operations and control operations
`is reqttired 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 magnetoop-
`tical disk. or a bu tk-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 memory device. According to
`selective startup or .1 reading request from an OS (operating
`system) or an application program, a program or data stored
`in the auxiliary memory device is read into a main memory
`device for effectirtg 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.
`
`.10
`
`EU
`
`40
`
`5t]
`
`55
`
`an
`
`65
`
`2
`
`One of the data compression techniques which is of the
`loss-less type (entropy coding or loss-less cording) that
`causes no data loss is drawing attention because it can
`increase an apparent capacity when data is recorded in all
`external memory device and also can effectively use corn-
`munication 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 compression is fully restored without any loss of infor-
`mation.
`However, the loss-less data cornpression technique is of
`such it 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 he
`compressed.
`According to the loss-less data compression technique.
`furthermore, binary hit map data or the like which has a 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 the loss-less data compression
`process,
`then the data will be expanded in many cases.
`Therefore, the loss-less data compression technique is very
`tliilicult to use.
`In the case where data is compressed at a low compression
`ratio, e.g.,
`in the case where compressed data is of a sine
`which is 99% of original uncompressed data, no merit is
`attained by data compression since the data length of the
`uncompressetl data and the data length of the compressed
`data remain almost the same though the data is definitely
`comprcssecl.
`it is assumed that data to be stored in at
`For example.
`random—access external memory device such as rt 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 fixed lengths. c.g.. blocks
`of51P. bytes. Therefore, if 1 Khytes ofdata are stored in the
`external mcrnory device,
`then they are stored over two
`blocks.
`
`if such 1 Kbytes. of data are compressed and the com-
`premcd data has a data length of5t2 bytes or less. then the
`compre-med data occupies one block of storage area on the
`disk. Therefore, the size oi‘ storage area which is occupied on
`the disk hy the compressed data is In of the size of storage
`area which is occupied on the disk hy the uncompressed
`data. an advantage that is offered by the data compression.
`However, if the cornprcssed data has a data length greater
`than 5}? bytes, then the compressed data actually occupies
`two blocks of 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 or) the disk hy the
`uncompressed data.
`In such a case. the entire system only causes a wasteful
`expenditure of the time required for data compression (if the
`data is expanded, the time required for data compressioni
`expansion}, and the electric energy required by the CPU and
`a hardware arrangement dedicated for data compression. and
`may possibly sul]"cr poor performance due to the data
`compression. if the compressed data is read from the t.:xter—
`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 wastefully.
`
`

`
`5,805,932
`
`3
`In comrnunicittions 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
`corrlpressccl data may he the same as each other, posing a
`limitation on ctforts to improve the entire system perfor-
`ma ncc.
`
`If 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 [Ac] required for transmitting the corn-
`presscd data is shorter than a transfer time L1,: required for
`transmitting the uncompressed data, as shown in FIG. 43 of
`the accompanying drawings.
`When the data is compressed. a time tm required for data
`compressionfcxpansion 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 lcrtgth
`is reduced.
`'T‘hc.re-fore,
`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 comprcssionfcxpansion.
`lfthe data is compressed at a low compression ratio. then.
`as shown in FIG. 44 of the accompanying drawings. laecausc
`an act:Ltn.l data transfer time In is not reduced substantially,
`the addition of a time 15.: required for data compression!
`exrpa nsion results in a transfer time tAc.: required for trans-
`mitting thc compressed data which is longer than a trartsler
`time tM required for transmitting the uncompressed data.
`Consequently. the data compression does not ol1'cr merits,
`hut instead lowers the overall system performance.
`For data transmission between a host computer and an
`external memory device, the host computer performs thc
`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 dilIcrcnt data from 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 transniitting dillerent 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 rccorded can be
`operation for data reproduction by only a host computer
`capable of cxpandi ng Ltomprcssed 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 it 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 corltpression finietion that can be incorporated in
`an external memory device may be performed by a loss-less
`data compression technique by which expanded data is made
`
`or
`
`.10
`
`10
`
`J
`
`‘J!
`
`3-0
`
`35
`
`40
`
`50
`
`55
`
`an
`
`65
`
`4
`exactly the same as input data. e.g., the known Iluffntanrt
`coding technique or LZW {Lempel-Ziv and Welch) coding
`technique, rather than a data compression technique that
`causes a data loss, which is used to compress digital audio
`data converted from analog audio data or digital image data,
`c.g.. the known discretc cosine coding technique. If such a
`loss—loss 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 expressions, etc. are used in the data.
`Specifically, it'll is assumed that a compression ratio to he
`expected (hereinafter referred to as an "expected compres-
`sion ratio“) when uncompressed data is compressed by the
`loss-less data compression technique has 3 value of 2, then
`when one logic block of data having a certain data length
`which is transferred from a host computer is compressed by
`an external memory device, the com_prcsscd data has a data
`length equal to one physical block whose size is ‘/5 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
`|)locks are equal to one logic block.
`Therefore, an opticrd disk having a physical capacity of
`500 MB (Megaflyte) has an apparent capacity of 1 GB
`(Gig:iBytc) 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 be 1}:
`or less of the data length of the uncompressed data. one logic
`block of transferred data may not be contained within one
`physical hloclc.
`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 cornprcsscd. a 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-
`pressed 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
`he read. As a result, it is possible for the system to fail to
`olIcr any advantages from data compression.
`it
`Data is randomly recorded on and reproduced front
`magnetic disk or an optical disk. For 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.
`There are occasions where mutually related compressed
`data over two or more physical blocks are recorded in
`physical blocks at spatially spaced positions on a magnetic
`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, a seeking
`(searching) process for searching for the mutually related
`compressed data is time-consuming, resulting in a long
`access time.
`
`The present invention has been made in view of the above
`problems. it is an object of the present invention to provide
`an apparatus for and a method of transmitting data for
`increasing overall system performance 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-
`ties :t certain condition, so that the data can be read from the
`recording medium at a greatly increased rate.
`Still another object of the present 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 recorrling them in areas corresponding to two or more
`successive physical blocks for thereby eltectively shortening
`a seek time consumed for reading data.
`
`-'.n
`
`.10
`
`DISCLOSURE OF THE INVENTION
`
`An apparatus for transmitting data according to the
`present invention comprises pre-compression data holding
`means for holding pre—comprcssion data, data compressing
`means for compressing the procornpression data held by the
`prc-cornprcssion data holding means, compressed data hold-
`ing means for holding compressed data from the data
`compressing means, decision means for determining data to
`he I.t'a.nsn'tittcd, based on data lengths of 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-compression data
`holding means and the compressed data held by the com-
`pressed data holding means, based on the data determined by
`the decision means.
`
`The prc-compression data held by the pre-compression
`data holding means is compressed by the data compressing
`means, and the compressed data is held by the compressed
`data holding means.
`The decision means determines data to be transmitted,
`based on data lengths oi‘ the pro-compression data and the
`compressed data and a preset condition. Based on the data
`determined by the decision means,
`the data transmitting
`means transmits either one of the prt:-compression data and
`the compressed data.
`For example, it‘ the preset condition is satisfied, then the
`compressed data is transmitted, and if the preset condition is
`not satisfied, then the pre—compression data is transmitted.
`As a result,
`it
`is possible to prevent a phenomenon in
`which the size of compressed data which occupies a storage.
`area in a data destination is substantially the same as the size
`of uncompressed data which occupies the storage area. and
`also to avoid wasteful data expansion in the data destination.
`decision means may comprise means for determining
`the data to be transmitted, based on an actual rtillcrence
`between the data lengths of the pre-compression data and the
`cornprcssed data and a preset dil]'erenr:e, determining the
`data to be transmitted as the compressed data if the actual
`dillierence is at least the. preset difference, and detcnrtirting
`the data to be transmitted as the pre-compression data if the
`aclual dilference is smaller than the preset ditference.
`Alternatively. the decision means may comprise means
`for determining the data to be transmitted, based on an actual
`compression ratio of the data length of the pre—comprcssion
`data to the data length of the compressed data and a preset
`compression ratio, determining the data to be transmitted as
`the compressed data if the actual compression ratio is at least
`the preset compression ratio, and determining the data to he
`
`4-0
`
`St]
`
`55
`
`fill
`
`55
`
`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 Lransrnitted as the
`compressed data if an actual (liffercncc between the data
`lengths of the pre-compression data and the compressed data
`is at least a preset dilferencc and also if an actual comprcs~
`sion ratio of the data length of the prccompression data to
`the data length of the compressed data is at least a preset
`compression ratio, and detcrrnining the data to be transmit-
`ted as the pre-compression data otherwise.
`It is assu mad that an arrangement is employed to transfer
`compressed data when the actual difierence is at least the
`preset dilfcrence. With the preset dilierencc being 512 bytes,
`for example, if the pre~compression data has a data length of
`2 Kbytes, then compressed data is transferred when the data
`length of the compressed data is 1.5 Kbylcs or shorter.
`Similarly. if the pre-compression data has a data length of
`1 Mbytes [1000 Kbytcs). then compressed data is trartslerred
`when the data length of the compressed data is 999.5 Khytes
`or shorter.
`
`The ratio (actual compression ratio) of the pre-
`compression data (data length=100U Kbytes) to the com-
`pressed data (data length-999.5 Kbytes) is about 1.t](t05.
`and the percentage of the data length (corresponding to the
`data length diilerence} removed by the data compression
`with respect to the data length of the pre-compression data
`is only 0.05%. With this compression ratio, the data length
`ofthe L‘(‘tl1'tpt'C:‘x‘s't':l1l data remains substantial