O
`4,956,808
`1111 Patent Number:
`1191
`Umted States Patent
`
`Aakre et al.
`[45] Date of Patent:
`Sep. 11, 1990
`
`364/900
`358/135 X
`322222
`. 178/22.09 x
`364/900
`
`364/900
`358/260
`360/l9.l X
`
`
`
`1/1985 Heinz
`4.491.934
`4,541,012 9/1985 Teschcr
`:1:;:1s:;2;1:::'.29:m
`,
`,
`on o
`4,588,991
`5/1986 Atalla
`4,597,057
`6/1986 Snow
`-
`2:23;??? 3:2 1S3;:P";)afl
`,
`,
`cl
`4,641,263
`2/1987 Perlman el al.
`4,673,987
`6/1987 Toyokawa
`4,680,647
`7/1987 Moriyama
`
`OTHER PUBLICATIONS
`
`t
`
`°"°‘
`
`IBM Technical Disclosure Bulletin, vol. 22, No. 9, pp.
`4194-4195, Feb. 1980, “Use of a Single Microprocessor
`23: Di;SD—TageNStreaming 'ghro;gl:TTv1S/o Channlegi;
`ov,
`.A. an
`ewman,
`.
`., “ u er ystem."
`Technical Disclosure Bulletin, vol. 2, No. 5, Feb. 1960,
`pp. 86-89.
`.
`.
`.
`Z’t'""’J’ E;“’":"e’j,.D“"‘dBL'd‘f‘“: F
`‘’"'‘J’- 39"’ 0’ ‘""“ '3 ‘Y '
`[57]
`ABSTRACT
`A real time data transformation and transmission appa-
`ratus transforms data from a first data device and trans-
`£Z*§.f’i?oi’?.’;i‘§‘;“§§',Si‘f1,‘:1:f‘;‘E2‘i2Z:?,fL°,;‘iS1:¥.“i§E
`First data device. Data from the first data device is di-
`vided into blocks and is compressed by a compression
`'
`device and written into a buffer. A controller controls
`the buffer to transmltcompressed data to
`second
`.
`.
`data device as a function of the data receiving rate of
`:1‘? 5°°°“é1d11:13 ‘Peedglm P'°;’1df°$
`bgfeg C311‘
`3 -
`3135 3 Pr
`9 "mu
`3310"“ O
`3
`5
`11 31'
`is transmitting data,
`the compressor is compressing
`further blocks of data which are being written to the
`buffer such that the predetermined amount of data is
`1
`11'
`11,
`1, ff
`1 1'
`111-,
`1,
`1:1
`1
`-
`Lilifngma 131031 Z'1"§ZZ.°"l‘-”11‘1’s°.§.‘fs'L'.’es 3.3." c2i..§,?2fe
`blocks of data are transmitted to the second data me-
`d.
`h d
`.
`.
`f th
`d d t
`lum at t e ata receiving rate 0
`a a me-
`‘Wm-
`
`e secon
`
`20 Claims, 3 Drawing Sheets
`
`[54] REAL TINIE DATA TRANSFORMATION
`AND TRANSMISSION ovERLApp[NG
`
`[75]
`
`Inventors: David E. Aakre, Kasson; Roy L.
`Hoffman, Pine Island; David N.
`Moen; Quentin G. Sclunierer, both of
`R h
`’
`'
`.
`°° ester an °f Mm“
`International Business Machines
`Corporation, Armonk, N.Y.
`
`[73] Assignee:
`
`[2]] App]. No.: 54,111
`
`[22] Filed:
`
`May 20, 1987
`
`Rented us, Appucgfion Dan
`.
`,
`1531
`§§:;“““°“ °‘ 5°" "°- ‘89*5‘*5= ’"'- 7’ 1935- 9"”
`'
`[51]
`Int. CL5 .............................................. .. G06F 5/06
`[52] U.S. Cl. ....................................... 364/900; 380/49
`[53] Field of Search
`364/200 MS File, 900 MS File;
`358/260, 261, 261.1, 261.2, 433, 442;
`381/314 31 380/42’ 49' 48’ 50
`References Cited
`mwr oocvmrs
`T964004 11/1977 Davy ................................... 358/260
`3368-870
`8/1965 Chalk“: ~11" 9131-
`- 354/900
`.
`.
`11
`.. ..... . ... .
`. . ...
`3-2313: 3;”; ‘:V1i’l1::’ ‘*1 31'
`'''''-''
`''-'''-332x83
`3358981
`5/1976 Ehrsam eta]
`178/22.05 X
`.
`.
`ng
`364/900
`4 02] 782
`5/1977 Hocmi
`4.040.027
`8/1977 Van Es et al
`364/900
`4,107,775
`8/1978 Ott ................ ..
`364/900 X
`4,159,517 6/1979 Pafadine e-131.
`354/zoo
`4,195,200
`3/1980 Fcistcl
`178/22.19 X
`4.228.501 10/1980 Frissell .
`364/200
`4.258.-118- 3/1981 Heath ............ ..
`364/200
`4.302.775 M981 wwersren er at
`358/13 x
`4'314'355
`2/1982 Leigm" C131‘ '
`364/900
`4,330,844
`5/1982 Dubuc .. ... . . . .. . . ,
`... .. 364/900
`4_36o_840 H/1982 wolfmm 6‘ al.
`358/261
`5/1983 Kondo et al.
`358/431
`4,386,373
`
`5/1984 Price et al.
`4.447,873
`4,467,354
`13/1984
`
`
`
`
`
`[56]
`
`Oracle 1010
`Oracle 1010
`
`
`
`FHEV 1 UJS
`I 20
`C6119‘-£55ICQ:ES§
`
`DGES5
`me»
`2261512»
`Bfifilsiafi
`H3
`E
`E
`
`
`
`
`

`
`U.S. Pate11t
`
`Slep. 11,1990
`
`Sheet 1 of3
`
`4,956,808
`
`10
`/
`
`16
`
`18
`
`24
`
`COMPRESSOR
`
`
`
`
`
`SECOND
`DATA
`MEDIUM
`
`BUFFER
`
`
`
`30
`
`
`
`CONTROLLER
`
`28
`
`32
`
`
`
`FIG.
`
`1
`
`12
`
`
`
`FIRST
`DATA
`MEDIUM
`
`
`
`
`

`
`U.S. Patent
`
`Sep. 11, 1
`
`mm.:m_
`
`Sheet2of3
`
`4,956,808
`
`on:3..}2_MDmfl
`flflmm_
`1|.1:
`
`_S_om.
`
`mo.
`
`muH>mo
`
`mmuzmaomm
`
`mm.
`
`«S92
`2:Id
`
`om
`
`mzmaammmmmzou
`
`mN
`
`<m.uHumy
`mzumamm<¢zou
`
`flflW
`
`mm<u:ou
`
`mo
`
`
`
`
`.mmtomIII.mobm.m_mmm:um..Hmum~_mmwmmmumm
`
`HMgm,..
`
`
`
`
`
` om[my1lIIIllIllijjnnlu--Jj
`
`
`
`
`

`
`U.S. Patent
`
`Sep.11,l990
`
`Sheet 3 of3
`
`4,956,808.
`
`om.j:1:
`
`m:oH>mma
`
`mmmmoo<
`
`mm»mHumm
`
`mfla
`
`mmmm
`
`muH>
`
`mmhmHomm
`
`mama
`
`mum
`
`mmmmoo<
`
`mmHmHomm
`
`Mafia
`
`mmmmazou
`
`mmmmooq
`
`mm»mHumm
`
`0:
`
`om_
`
`mm.07..
`
`
`
`
`
`
`

`
`1
`
`4,956,808
`
`REAL TIME DATA TRANSFORMATION AND
`TRANSMISSION OVERLAPPING DEVICE
`
`This is a continuation of co-pending application Ser.
`No. 689,545 filed on 1/7/85, now abandoned.
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`This invention relates to data transformation and
`transmission, and in particular to a device for compress-
`ing data from a fast access storage device and for trans-
`mitting compressed data to a slower medium.
`2. Description of the Prior Art
`Compression or transformation of data usually results
`in an irregular flow of compressed data which is not
`conducive to efficient recording on magnetic tape or
`transmitting over communication channels with reason-
`able efficiency. Computers with large, volatile direct
`access main storage devices usually require that the data
`contained therein be saved on nonvolatile, removable
`media such as tape for archival and backup purposes.
`The amount of data to be stored in conjunction with the
`relatively slow sequential access speed of tape storage
`devices compared to the fast access speed of direct
`access storage devices has led to significant efforts to
`compress data and to increase the speed of tape storage
`devices. However, there is still a disparity in their rela-
`tive speeds which is usually dealt with by fust storing
`blocks of data from the direct access storage device into
`a buffer which is dedicated to providing dam to tape
`during save operations.
`In U.S. Pat. No. 4,360,840 to Wolfrum et al, data is
`compressed in real time as it is produced by a facsimile
`raster scamier and stored in a buffer for transmission.
`Data is not transmitted until a full page of text has been
`compressed and stored. While this procedure reduces
`the amount of buffer space required to store a page of
`data, it does not address the problem of transmitting the
`data from the buffer while it is being compressed. This
`can result in loss of valuable transmission time and pos-
`sibly require larger storage devices to store a full page
`of text.
`
`U.S. Pat. No. 3,490,690 to Apple et al relates to com-
`pression of an instruction trace and recording the com-
`pressed data to tape. Compressed data is written to tape
`and sections of data are dropped and not recorded when
`the tape gets behind or “no data“ characters are re-
`corded on the tape when the tape gets ahead. This re-
`sults in lost data and does not optimize the data storage
`capability of the tape.
`SUMMARY OF THE INVENTION
`
`A real time data transformation and transformed data
`transmission device is provided which compresses data
`provided from a first data medium and provides the
`compressed data to a second data medium which ac-
`cepts data at a rate slower than the rate at which the
`first data medium provides data. The compressed data is
`provided to the second data medium as required by the
`second data medium to operate in an efficient manner.
`A transformation means receives a first block of data
`from the first data medium and compresses the data into
`a corresponding block of compressed data which is
`preferably smaller than the uncompressed block of data.
`A buffer means receives the compressed data and stores
`blocks of compressed data for provision to the second
`data medium. A control means is coupled to the trans-
`
`5
`
`l0
`
`I5
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`formation means and to the buffer means for controlling
`the buffer means to provide a continuous flow of com-
`pressed data to the second data medium as a function of
`the data acceptance rate of the second data medium.
`Overlapped with the provision of compressed data to
`the second data medium, the control means also causes
`the transformation means to compress a second block of
`data into the buffer means as a function of the amount of
`usable free space in the buffer means.
`In the preferred embodiment, the first data medium is
`a direct access storage device of a computer which
`periodically has its data saved onto the second medium
`which is a tape storage device. The tape storage device
`receives data at a rate compatible with constant opera-
`tion of the tape storage device so that the tape need not
`be stopped and restarted which considerably slows the
`save operation. Data which is stored to the tape is com-
`pressed in accordance with a desired compression
`scheme to increase data density on the tape which re-
`duces the number of tapes needed for the save operation
`and reduces the time required to store data on tape.
`The first block of data from the direct access storage
`device is compressed and stored in the buffer means.
`Once the entire first block of data is stored in the buffer
`means, a write to tape operation begins. While the first
`block of data is being written to tape, the control means
`coordinates the writing to the buffer means of the sec-
`ond block of data. Since the data transfer rate of the
`direct access storage device is much greater than the
`data receiving rate of the tape device, the second block
`of data is preferably written into the buffer means be-
`fore the first block of data is completely written to the
`tape. The second block of data is then written to tape,
`while a third block of data is compressed to the buffer
`means in whatever free space exists. The control means
`assures that data in the buffer is not lost while blocks are
`being stored and written at the same time; the control
`means also allocates buffer cycles between storing and
`writing data, with writing data to the tape having prior-
`ity over the storing of compressed data from the direct
`access storage device.
`The storing and writing of compressed blocks of data
`continues until all the desired data is saved on tape. The
`tape is run in a continuous or streaming mode unless
`there is not a complete block of compressed data avail-
`able from the buffer means to prevent under running of
`the tape.
`In the event that there is not a complete block of data
`available from the buffer means, the tape will stop in an
`interblock gap until a complete block is available. The
`storage capacity of the buffer means is chosen to be
`large enough to hold the largest possible block of data
`which has been compressed. In some instances this may
`be larger than the block of data to be compressed if the
`block of data does not lend itself to compression. With
`that size buffer means, and considering the data transfer
`rates of the direct access storage device and the tape
`device, and the transformation or compression charac-
`teristics of the data to be saved, the availability of a
`complete block of compressed data from the buffer
`means when required by the tape device is virtually
`assured.
`In an alternate embodiment, data is compressed or
`transformed and stored in the buffer means. Coordina-
`tion of the overlapping of transforming and storing data
`in the buffer means with writing to and from tape is
`based on the amount of compressed data stored in the
`buffer means. In this embodiment, the size of the buffer
`
`

`
`4,956,808
`
`3
`means is determined as a function of the data transfer
`rates of the direct access storage device and the tape
`device, and the transformation characteristics of the
`data to be saved such that transformed data is always
`available when requested by the tape device.
`The present invention has the advantage of compress-
`ing data in real time as defined by the tape device re-
`quirements for data. This permits the data to be com-
`pressed to its limit in accordance with the selected com-
`pression technique and be written to tape as fast as the
`tape accepts the data. Fewer tapes are required for a
`save operation because the data is compressed to its
`limit. Because the compression and writing to tape are
`overlapped a desired amount as a function of the prede-
`termined size of the blocks of data, the tape operates in
`a continuous or streaming mode thus reducing the time
`required for the save operation.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a simplified block diagram of a real time
`data transformation and transmission overlapping de-
`vice in accordance with the present invention; and
`FIGS. 2A and 2B, the left side of 2A mating with the
`right side of 2B, are a schematic block diagram of the
`data transformation and transmission overlapping de-
`vice of FIG. 1.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`time data transformation and transmission
`A real
`device is indicated generally at 10 in FIG. 1. A first data
`medium 12 such as a direct access storage device of a
`computer is coupled by a line 14 to a data transforma-
`tion means 16 (also referred to as data compressor I6)
`which transforms data as by compression, encryption or
`other forms of data transformation. The lines referred to
`herein comprise busses, coaxial cable, optical fibers or
`other appropriate communicative means. In the pre-
`ferred embodiment, data compressor 16 receives a
`block of data_from first data medium 12 and compresses
`the block of data by removing redundant data bytes or
`characters which are typically randomly scattered
`throughout the block of data.
`Data compressor 16 provides the compressed data to
`a buffer 18 along a line 20. Buffer 18 comprises a dy-
`namic random access memory and provides compressed
`data to a second data medium 24 on a line 26. Second
`data medium 24 has a data transfer rate which is usually
`slower than the data transfer rate of first data medium
`12.
`In one functional embodiment, second data medium
`24 is a magnetic tape unit such as an IBM model 3430,
`having known start and stop times and first data me-
`dium 12 is a random access storage device such as an
`IBM model 3370. When a section of data contains a
`series of redundant bytes, a gap during which no data is
`provided to buffer 18 occurs. If data were written from
`the buffer 18 directly to the second data medium 24 as
`the data is being compressed, the gap would cause sec-
`ond data medium 24 to stop and rewind the tape to the
`correct point to start receiving data again.
`To solve this problem, a control means or controller
`28 is coupled between compressor 16 by a line 30 and
`buffer 18 by a line 32. Controller 28 determines when a
`block of data has been compressed by compressor 16
`and written to buffer 18. Controller 28 then initiates the
`writing of that block of data to the second data medium
`24 at a rate determined by second data medium 24 re-
`
`4
`quests for bytes of data. While the data is being trans-
`mitted to the second data medium 24, a next block of
`data is compressed by compressor 16 as controlled by
`controller 28. The next block of data is compressed into
`buffer 18, which is a first in, first out data buffer, before
`the first block of compressed data is completely trans-
`mitted to the second data medium 24 such that the sec-
`ond data medium 24 operates in a streaming mode and
`is not required to stop and start during a block or be-
`tween data blocks.
`In FIGS. 2A and 2B, a hardware implementation of a
`Systems Network Architecture (SNA) compression
`algorithm used, and the apparatus of the present inven-
`tion is shown. The block of data is received from a
`storage device 34 one byte at a time on a line 36 and is
`written into a first register 38 and then into a second
`register 40 via a line 42 while the next byte of data is
`written into first register 38 such that the registers con-
`tain sequential bytes of the block of data.
`A first comparator 44 receives the first byte of data in
`second register 40 on a line 46, the second byte of data
`in first register 38, and a prime or preselected byte on a
`line 48 from a memory device 52. First comparator 44
`compares the first and second bytes of data with the
`prime byte to determine if the data contains a series of at
`least two prime bytes. A second comparator 54 receives
`the first data byte on line 46, the second data byte on
`line 42 and a third data byte on line 36 to determine if
`there is a series of at least three identical bytes. A series
`of at least three identical bytes of data which are not the
`same as the prime byte, detected in this manner are
`referred to as a nonprime series. If no prime or non-
`prime series are detected, the condition is referred to as
`mixed data.
`Mixed data bytes are written into a buffer 58 which is
`coupled by a line 60 through a selector 62 to line 46.
`Selector 62 is controlled by a compress sequencer 64
`which receives information identifying the type of data
`series from first comparator 44 and second comparator
`54 on lines 68 and 70 respectively. From this informa-
`tion, compress sequencer 64 controls formation of a
`string control byte (SCB) by a SCB coder 72. SCB
`coder 72 forms the SCB as a function of information
`provided from compress sequencer 64 on a line 74. The
`information and hence the SCB is representative of the
`type of series of bytes and indicates the number of bytes
`in the particular series of bytes it represents.
`By controlling selector 62 via a line 78, compress
`sequencer 64 controls the content and order in which
`data provided to selector 62 by second register 40 via
`line 46 and SCBs provided to selector 62 from SCB
`coder 72 on a line 79, are written into buffer 58. In the
`case of a prime series, the SCB is not followed by data
`bytes because the prime byte is predefined in memory
`device 52. An SCB indicating a nonprime series is fol-
`lowed by a data byte of the repeated character. An SCB
`indicating mixed data is followed by all bytes of the
`mixed data.
`
`Using the above SNA compression scheme, data is
`usually compressed more than 50 percent. In the pre-
`ferred embodiment, an SCB is a byte of data having 2
`bits defining the type of series it represents, and 6 bits
`which represent the number of bytes of data in the series
`up to 63. Buffer 58 is capable of storing 32,768 bytes. If
`a block is all mixed data, the data will expand by one
`byte, the SCB, for each 63 bytes of data. Therefore, the
`size of a block of data to be compressed was predeter-
`
`[0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`65
`
`

`
`5
`mined to be 32,256 bytes so that it will always fit in
`buffer 58 when compressed.
`Use of other compression or encryption routines is
`within the scope of the present invention. The particu-
`lar routine described above is implemented in hardware
`to obtain a desired high speed of compression.
`Compress sequencer 64 is coupled to first register 38
`and second register 40 by a line 80 to shift data from line
`36 into first register 38 and to shift data from first regis-
`ter 38 to second register 40. Compress sequencer 64 also
`indicates to a compress address register 110 in FIG. 2B
`by a line 112, the correct buffer 58 address for data to be
`written into. Compress sequencer 64 is coupled to a
`SCB address register 114 by a line 116 and to a previous
`address register 118 by a line 120. SCB address register
`114 contains the buffer 58 address for the SCB indicat-
`ing the type of data run it precedes.
`SCBs are written to buffer 58 at a time after a run of
`mixed data occurs because the SCB indicates the length
`of the run which is not known until the run of mixed
`data is finished. However, the address of‘ the SCB pre-
`cedes the data whether it is mixed or nonprime. Previ-
`ous address register 118 contains the address of the last
`byte of the last previously compressed block in buffer
`58. An address selector 124 which is coupled to com-
`press address register 110 and SCB address register 114
`by lines 126 and 128 respectively provides buffer 58
`with the appropriate address for data and SCBs on a line
`129 as they are written into buffer 58. SCB address
`register 114 receives an address from compress address
`register 110 on line 126 when initiated by compress
`sequencer 64 on line 116.
`A buffer controller 132 is coupled to address selector
`124 by a line 134 and initiates selection and provision of
`the address to buffer 58 by address selector 124. Buffer
`controller 132 is coupled to compress sequencer 64 by
`lines 136 and 138. Buffer controller 132 grants a buffer
`cycle to compress sequencer 64 on line 136, and com-
`press sequencer 64 indicates on line 138 that a byte of
`data or a SCI} is available to be written to buffer 58 and
`the buffer address has been updated. In this manner, a
`block of data is compressed and written to buffer 58.
`Once a complete block of compressed data is avail-
`able from buffer 58, the block is transmitted to a set of
`latches 150 over a line 152. The availability of a com-
`plete block of compressed data is indicated by a finished
`block line 139, which is set responsive to a complete
`block of data having been transferred from data storage
`device 34 to first register 38. Finished block line 139 is
`coupled to compress sequencer 64 which initiates trans-
`mission of the compressed block of data. Compress
`sequencer 64 is also coupled to storage medium 34 by a
`line 141 to initiate transfer of data from storage medium
`34 to first register 38.
`The second data medium indicated at 154 receives the
`compressed data from latches 150 at the rate required
`by second data medium 154. A device sequencer 158 is
`coupled to second data medium 154 by lines 160 and
`162. Line 160 provides requests for bytes of data from
`second data medium 154. Line 162 provides an indica-
`tion to second data medium 154 that a compressed block
`of data has been provided to second data medium 154.
`Device sequencer 158 is also coupled to buffer con-
`trol 132 by line 164 which provides requests for a buffer
`58 cycle from second data medium 154. Device se-
`quencer 158 increments a device address register 170
`over a line 172 such that the device address register 170
`contains the address of the byte to be written to latches
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4,956,808
`
`6
`150 from buffer 58. The device address indicated by
`device address register 170 is provided by a line 174 to
`selector 124 for provision to buffer 58.
`The device address is also provided to a previous
`address comparator 176 and a compress address com-
`parator 178 by line 174. The previous address compara-
`tor 176 compares the device address to the previous
`address indicating the address of the last byte of the
`latest block of data completely written to buffer 58. The
`previous address is provided to the previous address
`comparator 176 by the previous address register 118 on
`a line 180. The previous address is not inserted into
`previous address register 118 until a complete block is
`written to buffer 58.
`When a comparison is indicated on a line 182 which
`is coupled to device sequencer 158, device sequencer
`158 stops the transmission of compressed data from
`buffer 58 to second data medium 154 because a com-
`plete block of data has been transmitted. The previous
`address is not changed before a block is completely
`transmitted to second data medium 154. A desired inter-
`block gap is then established on second data medium
`154 while the previous address is changed and the next
`block of compressed data is transmitted without inter-
`ruption of the operation of second data medium 154.
`Thus, second data medium 154 can operate efficiently in
`a streaming or a start stop mode.
`Compress address comparator 178 is coupled to line
`126 to receive the address contained in compress ad-
`dress register 110 which indicates the present address of
`the buffer 58 that data is being written into. An address
`in device address register 170 equal to an address in
`compress address register 110 indicates that data is
`available to be written into buffer 58, but that previ-
`ously compressed data from that address has not yet
`been transmitted to second data medium 154. Compress
`address comparator 178 is coupled by a line 182 to
`buffer control 132 to prevent the grant of a buffer cycle
`to compress sequencer 64 and thus ensure that data is
`not written to buffer 58 until data having the same ad-
`dress is transmitted to second data medium 154.
`In a further preferred embodiment, previous address
`register 118 is loaded with a buffer 58 address at which
`compressed data is stored which is a desired number of
`bytes from the byte currently being written to second
`data medium 154. The number of bytes is predetennined
`as a function of the relative data transfer rates of storage
`device 34 and second data medium 154 together with
`the predicted transformation characteristics of the data
`in storage device 34. This permits data to be arranged in
`other than compressed blocks of a size defined by the
`compressibility of the data. Since the address in previ-
`ous address register H8 is changing as data is being
`written to second data medium 154, second data me-
`dium 154 arranges the data to best suit its characteris-
`tics. Interblock gaps are inserted by second data me-
`dium 154 where and if desired.
`In yet a further preferred embodiment, the second
`data medium 154 comprises an interface to a communi-
`cation system such as a packet switching system. In this
`embodiment, buffer 58 provides compressed packets to
`second data medium 154 as a function of the transmis-
`sion bandwidth of the second data medium. Buffer 58
`serves as a buffer to both the compression characteris-
`tics of the packet and access irregularities to the second
`data medium. thus ensuring the availability of a com-
`pressed packet for transmission.
`
`

`
`4,956,808
`
`8
`the second data medium is initiated by the control
`means.
`
`7
`Buffer controller 132 prioritizes access to buffer 58.
`Buffer 58 access is requested by device sequencer 158
`on line [64, compress sequencer 64 on line 138 and a
`refresh controller(not shown) when buffer 58 is a dy-
`namic memory. Highest priority is given to device se-
`quencer 15!! followed by compress sequencer 64. Low-
`est priority is given to refresh. If all three request access
`simultaneously, buffer controller 132 grants priority as
`described above. In doing this,
`it places priority on
`transmitting data to second data medium 154 to keep
`second data medium 154 operating in a continuous man-
`ner. Thus, data is saved in a minimal amount of time
`with the use of a minimum amount of second data me-
`dium 154, whether it be magnetic tape or transmission
`bandwidth.
`While the invention has been shown and described
`with reference to preferred embodiments thereof, it will
`be understood by those skilled in the art that various
`changes in form and details may be made therein with-
`out departing from the spirit and scope of the invention.
`What is claimed is:
`1. Real
`time data transformation and transmission
`apparatus for overlapping transformation of blocks of
`data provided from a first data medium which has a
`selected data transfer rate and transmission of the trans-
`formed blocks of data to a second data medium which
`has a selected data receiving rate, said apparatus com-
`prising:
`transformation means coupled to the first data me-
`dium for transforming blocks of data received from
`the first data medium into variable size blocks of
`transformed data and providing said transformed
`data of an irregular rate;
`buffer means coupled to the transformation means
`and to the second data medium for storing the
`transformed data and transmitting the transformed
`data to the second data medium; and
`control means coupled to the transformation means
`and to the buffer means for controlling the trans-
`formation means to provide transformed data to
`the buffer means as a function of the amount of data
`in the buffer means and controlling the buffer
`means to transmit the transformed data to the sec-
`ond data medium as a function of the data receiving
`rate of the seond data medium provided that the
`buffer means contains a predetermined amount of
`data sufficient to ensure that each block of trans-
`formed data is transmitted to the second data me-
`dium continuously at the data receiving rate of the
`second data medium.
`2. The apparatus of claim 1 wherein the predeter-
`mined amount of data comprises a block containing a
`selected number of bytes of transformed data.
`3. The apparatus of claim 1 wherein the predeter-
`mined amount of data comprises a block containing a
`selected number of bytes of data from the first data
`medium prior to transformation, and wherein the con-
`trol means controls the buffer means such that a com-
`plete block of data is compressed into the buffer means
`before transmission of the transformed data to the sec-
`ond data medium is initiated by the control means.
`4. The apparatus of claim 1 wherein the predeter-
`mined amount of data is equal to blocks of data of a
`selected size and the control means controls the buffer
`means such that a complete block of data is transformed
`and stored into the buffer means by the transformation
`means before transmission of the transformed data to
`
`5. The apparatus of claim 1 wherein the control
`means controls the amount of data stored in the buffer
`means to be at least equal to a predetermined amount of
`data such that the second data medium receives trans-
`formed data at a substantially continuous rate.
`6. The apparatus of claim I wherein the second data
`medium comprises a magnetic tape device operating in
`a streaming mode.
`7. The apparatus of claim 1 wherein the data transfer
`rate of the first data medium is substantially greater than
`the data transfer rate of the tape device.
`8. The apparatus of claim 1 wherein the second data
`medium comprises a magnetic tape device operating in
`a start/stop mode.
`9. The apparatus of claim 1 wherein the transforma-
`tion means comprises a data compression means for
`compressing the data from the first data medium.
`10. The apparatus of claim I wherein the data com-
`prises blocks of characters, said data compression means
`compressing the blocks of characters as a function of
`redundant sequential bytes of data.
`11. The apparatus of claim 1 wherein the transforma-
`tion means comprises a data encryption means for en-
`crypting the data from the first data medium.
`12. The apparatus of claim 11 wherein the transfor-
`mation means compresses data at a rate which is greater
`than the data receiving rate of the second data medium.
`13. The apparatus of claim I wherein the buffer
`means comprises a first in, first out buffer which re-
`ceives transformed data from the transformation means
`and provides the data to the second data medium as
`requested by the second data medium for substantially
`continuous operation of the second data medium.
`14. Real time data compression and transmission ap-
`paratus for overlapping compression of blocks of data
`provided at a first data transfer rate and transmission of
`the compressed data to a data medium which has a
`second, lower, data transfer rate, said apparatus com-
`prising:
`compression means for receiving the blocks of data at
`said first
`transfer rate and compressing said re-
`ceived data into variable size blocks of compressed
`data;
`buffer means coupled to said compression means and
`to the data medium for storing the blocks of com-
`pressed data and transmitting the compressed data
`to said data medium;
`control means coupled to the compression means and
`to the buffer means for controlling the compression
`means to provide compressed data to the buffer
`means as a function of the amount of data in said
`buffer means and controlling the buffer means to
`transmit the compressed data to the data medium at
`said second transfer rate; and
`end of block detection means coupled to said buffer
`means for providing a signal to said control means
`indicating an end of a variable size block of com-
`pressed data said control means being responsive to
`said signal
`to temiinate transmission unless said
`signal indicates that a complete, additional, block
`of compressed data is stored in said buffer.
`15. The real time data compression and transmission
`apparatus of claim 14 wherein the data medium com-
`prises a tape storage device, and the control means
`coordinates compression and transmission of blocks of
`
`l0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`

`
`9
`data in a manner such that the tape storage device effi-
`ciently stores the blocks of compressed data.
`16. The real time data compression and transmission
`apparatus of claim 14 and further comprising a memory
`coupled to the compression means for storing blocks of
`data. to be compressed, said first memory having a high
`data transfer rate in comparison to the second medium.
`17. The real time data compression and transmission
`apparatus of claim 16 wherein the compression means is
`a hardwired compressor, and supplies blocks of com-
`pressed data at substantially the same rate as blocks of
`data to be compressed are supplied to the compression
`means from the memory.
`18. The real time data compression and transmission
`apparatus of claim 14 wherein the control means initi-
`ates compression of a further block of data upon detec-
`tion of an end of a block of compressed data during
`transmission of comp