JPH05500878A - data storage - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention] Day tongue 1 The present invention relates to compressing user data and storing it on tape.

When data arrives from the host, it is compressed before being written to tape to reduce tape storage capacity. Tape drives with data compression capabilities (DC drives) ) is known. DC drives read compressed data from tape. data and decompress it before sending it to the host. Wear. The host performs software compression and/or decompression of user data. You can also do that.

There is more than one type of data compression. For example, a specified record, file, etc. Remove separation marks from the data stream and import information about the position of the marks. User data is effectively compressed by storing it in an index. another A completely different approach would be to remove data redundancy, e.g. the user data word as a code word from which the original data can be recovered. Compress user data by replacing. The term “data compression” or It is the latter type that is referred to herein when using the abbreviation DC.

According to the present invention, extra auxiliary information is inserted into the data stream during the data compression process. Compressed data organized in the form of records, characterized by Data storage methods are provided.

The auxiliary information may include error checking information. In addition, auxiliary information includes data separation information, information that can be used later to separate the data. It can be included.

Inject this extra information into the data stream as part of the data compression algorithm. The purpose of inputting data streams is to provide high-speed operation and ease of data error conditions. The aim is to make it especially suitable for various tests.

For example, a code word representing an uncompressed Hyde force Tkund and/or a redundancy check. can be inserted after the "end of record" code word. this These code words may be used during error checking or may not be required. or can be skipped if unsuitable for a particular tape drive. .

The method preferably comprises writing auxiliary information to tape in uncompressed form. Delicious. This makes auxiliary information available to non-DC tape drives. desired for.

The method inserts auxiliary information into a data stream related to one or more records. Can include doing.

The method includes a header containing auxiliary information about one or more records after the header portion. This may include inserting some into the data stream.

The method further includes one or more records before the trailer portion. including inserting a trailing section containing auxiliary information about the data stream into the data stream. I can do that.

Alternatively, or as well, the method records the data independently of the record structure of the data. ・Organize records into groups, or group information about records in groups. It can also include writing to the index associated with the group.

In the described embodiment, the method includes storing information by an entity in a group index. has the ability to write to the box. Here, one entity has one or more records. including the code. In the embodiment, the method includes auxiliary information associated with each entity. It has the ability to write to the header.

The present invention also compresses user data and writes compressed data to tape. A storage device operable according to the method described above is provided.

Specific embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings.

8 and 8 are diagrams relating to data compression algorithms.

FIG. 1 is a partial diagram showing a configuration for storing computer data. (a) is a logical separation mark sent by the user (host) to the data storage device FIG. 3 is a diagram showing a sequence of data records.

(b) and (C) are two for storing the sequence of FIG. 1(a) on tape. FIG. 3 is a diagram showing two different arrangements.

FIG. 2 is a diagram of the group index.

FIGS. 3 and 3A are diagrams of general block access tables.

FIGS. 4 and 4A are diagrams of specific block access tables.

Figures 5 to 7 are diagrams showing further configurations for storing computer data. be.

Figure 8 shows possible valid information for a group's book access table. It is a diagram showing an entry.

9 and 1O are further illustrations of arrangements for storing computer data. Ru.

FIG. 11 forms part of a data storage device embodying the invention and is a helical scan 1 is a diagram illustrating the main physical components of a tape deck using.

Figure 12 shows two data tracks recorded on tape using helical scanning. FIG.

Figure 13 shows the main data of the data track recorded by this data storage method. FIG. 3 is a diagrammatic representation of the format of a region;

Figure 14 shows the sub data of the data track recorded by this data storage method. FIG. 2 is a diagrammatic representation of the format of a data area;

FIG. 15 shows the method, i.e. data storage in groups within the data area of the tape. Details of frame arrangement and index recorded in frames within each group It is a figure showing both.

FIG. 16 is a block diagram of the main components of a data storage device embodying the present invention. It is a diagram.

FIGS. 17 and 18 are block diagrams of the data compression processor.

Figure 19 shows a more detailed functional block diagram of the data storage group processor. This is a diagram.

Figures 20A and 20B illustrate the search for a particular record on tape. , is a flowchart of an algorithm implemented by the drive device.

Further information on data compression, including details of specific DC algorithms, is first given. available.

The purpose of the data compression process is to remove redundancy from the data. Compression effect One measure of the ratio is called the "compression ratio", which is the length of input to be compressed is defined as

This is a measure of the success of the data compression process. The larger the compression ratio, the greater the compression efficiency. The rate will also be higher.

One way to implement data compression is to recognize patterns in input characters and In other words, a substitution method is used.

According to the LZW algorithm, when a unique string of input characters is found, They are entered into a dictionary and assigned a numerical value. When compressing data, the dictionary Dynamically formed and regenerated from the data upon restore. Once the dictionary entry exists, If present, subsequent occurrences of that entry in the data stream are numeric or You can also replace it with a court word. It should be noted that this algorithm , it is not limited to compressing ASCII text data. .

The principle is the same for binary file data bases, imaging data, etc. Very applicable.

Each dictionary entry consists of two items: (1) the algorithm sees in the data; (2) the combination of data hide that forms a unique string attached to Consists of the expressed code words.

The dictionary can contain up to 4096 entries. first eight entries Reservation code used to flag and control certain conditions. It is a word. The next 256 entries contain hide values from 0 to 255. ing. Therefore, some of these 256 items are converted into ASCII text characters. is the associated code word. The remaining positions point to other dictionary positions, eventually A linked list entry that ends by specifying one of the hide values 0 to 255. It is li. By using this linked list data, possible hide The combinations are within the length range of 2 hides to 128 bytes, so it takes too much time to store them. The need for an excessively wide memory array can be avoided.

For the hardware implementation described in more detail below, the dictionary is constructed and then It is stored in a 3-bit wide bank of random access memory (RAM). each The memory address contains a hide value based on the lower 8 bits and an error value based on the next 12 hints. A code word or pointer representing the entry and three by the top three hits. can contain conditional flags. Output used to represent code words The number of bits in the byte stream ranges from 9 bits to 12 bits, Corresponds to dictionary entries in the range 0-4095. At the dictionary construction stage, 51. For each code word, use 9 hits until 2 entries are created. After the 512th entry, 10 bits are used for the code word, After the 1024024th bird, 11 hits are used for the coat word, and the last For the 2048 entries, 12 hits are used in the code word. words Once the code is full, no further entries will be created and all subsequent code The word will be 12 bits in length. Memory address for any dictionary entry The response is determined by performing complex operations on entry values. in the dictionary can contain 4096 entries, so supporting the entire dictionary requires 4. Hyde's RAMI doesn't seem necessary. This is actually true when restoring. It's about fitting in. However, during compression, the dictionary Due to "collisions", more than 4 bytes of RAM are required. This is two different The string/character combinations mapped to the same location in the dictionary RAM. However, the resources in dictionary RAM are limited, and the This is because the process of building a dictionary is complicated. When a dictionary conflict occurs, there are two The collision value of is recalculated for the two new positions, and the original position is replaced with the collision value of the collision position. A rug is put up.

An important property of the algorithm is the combination of compression and decompression. These two actions are , during the compression and decompression process and the buffering of code words for the byte stream. It is tied both during bucking and unbacking. compression algorithm Due to the nature of the system, it is necessary to synchronize the compression and decompression processes.

In other words, decompression can start from any point in the compressed data. I can't.

The restore starts from a point where the dictionary is known to be empty or reset. do. This combination provides one of the fundamental advantages of the algorithm. sand In other words, since the dictionary is embedded in the code word, it is transferred along with the compressed data. do not have to. Similarly, the backing and unbacking processes should also be synchronized. Must be. Do not present compressed data in the correct order to the decompression hardware. Please note that

FIG. 8 is a schematic graphical diagram of the compression algorithm described above. In this example is an input data stream consisting of the following characters: RINT TN To trace the flow of the TIN0 compression process, look at Figure 8 from top to bottom, and It is preferable to start from the beginning and move to the right. The dictionary is reset and has 8 reserved courts. 0-255, including word and code word for all ASCII characters Assume that it is initialized to contain the first 256 entries of .

The compression algorithm performs the following process for each byte in the data stream: go 1. Take a manual part-time job.

2. Search the dictionary for the current input sequence, and if there is a match, use another input sequence. Take the bytes, add them to the current sequence, and remember the largest matched sequence. put.

3. Repeat step 2 until there are no more matches.

4. Create a new dictionary entry for the current "unmatched" sequence.

5. Output the code word for the largest matched sequence.

In this example, the compression algorithm opens after the compression engine receives the first R. start The input character R matches the character R stored during its initialization. match So the DC engine receives another byte, which is the letter I. next , the sequence R1 is searched in the dictionary, or no match is found.

Therefore, a new dictionary entry R1 is created, with respect to the maximum matching sequence The code word (ie, the code word for the letter R) is output.

The DC engine then searches the dictionary for , find a match. Another character is entered (N) and for the sequence IN and start searching. IN does not match any entry, so a new entry is created and the code word for the maximum matching sequence (i.e., the letter I code word) is output. This process continues and the letter N A search is carried out. When N is found, the next character is entered, NT is entered, and the dictionary is entered. An exploration will be carried out. I can't find this, so I created a dictionary entry for NT. and the code word for N is output. The same sequence is the letter T and ■ also occurs. The code word for T is output and the dictionary for TI An entry is created.

Up to this point, there were no multiple character matches, so no compression was performed. actual , replaced by four 8-bit characters or four 9-bit code words. However, the output stream is only slightly expanded. (this is , representing a 32-bit to 36-bit expansion, or a compression ratio of 1.125:1. ing. ) However, data compression begins when the next character is entered. at the time Then, the DC engine searches for an IN sequence. Once a match is found, the DC The engine receives another character and begins searching for INT. No match found If so, create a dictionary entry for INT and write a dictionary entry for sequence IN. Outputs a previously generated code word. In this case, the two 8-hit characters are replaced by one 9-bit code word, the compression ratio is 16/9 or 1 ．． The ratio is 778:1.

This process continues, again replacing the two characters with a single code word. available. The DC engine starts with T from the previous sequence, followed by the next Receive the character ■. The DC engine searches for and matches the TI sequence, so Another byte is input. The chip then performs a TIN sequence search. cormorant. Since there is no match, a TIN entry is created and the code associated with the TI ・Word is output. This sequence also shows 1,778 as indicated by the IN sequence. :1 compression ratio. The net compression ratio for this string of 9 hides is , l　143・1. This example consists of a very small number of bytes, so this , not a particularly large compression ratio. As more samples of data are stored, more data is stored. The sequence of Hyde is also increased and the sequence of Hyde is replaced by a single code word. -kens also increases. It becomes possible to obtain compression ratios in the range 11-110.1.

A schematic diagram of the restoration process is shown in FIG. In this example, the previous The output of the compressed example is used. The decompression process is very similar to the compression process. However, since there is no need to search for the existence of a given dictionary entry, the restoration algorithm The compression algorithm is not complicated. Connect two processes By matching, the existence of matching dictionary entries at the time of restoration is guaranteed. . The algorithm utilizes the input code word to find the Hyde Noke in the dictionary. the new entry using the same rules as the compression algorithm. Just create. This is the restore algorithm or This is the only way to recover compressed data without sending special dictionaries. Ru.

As in the compression example, the dictionary is reset and the first 256 entries of O~255 It is assumed that the initial settings are to accommodate the files.

The restoration engine begins by receiving the code word for R. restoration Ennn refers to the hide value R using this code word. This value is , last-in, first-out (L IFO) stack and output from the chip. wait. Since R is the root coat word (one of the first 256 entries), We have reached the end of the list for this coat word. Then the chip The output stack is dumped from The restoration engine also coats regarding ■ - Input a word and use it to refer to the Hyde value ■. Again, this value is , is the root coat word, so the output sequence for this coat word is , completes, and the hide value for ■ is popped from the output stack. at this point , the last hide value pushed onto the output stack (1) and the previous code word A new dictionary entry is created using (code word for R).

Each entry is thus created, containing one hide value and the next bar in the sequence. Contains a pointer to the item (previous court 1'). In this way, each A linked list is generated for each dictionary entry.

The next code word is entered (the code word for N) and the process repeated. This time, N is output, the hide value N, and the code word for ■ A new dictionary entry is created containing the .

When a code word for T is entered, T is output and another dictionary entry is entered. Created. The next code word entered represents Hyde Nokens IN. vinegar. The restore engine utilizes this code word to retrieve the previously generated code word in this example. Refer to the second dictionary entry that was created.

This entry contains the byte value N placed on the output stack and the current code Contains a pointer to the code word for I that becomes the code. This new The new code word finds the next byte (I) to be placed on the output stack. used for Since this is the root codeword, the referencing process is The output stack is dumped in reverse order. In other words, ■ is output first. , followed by N. The same process for the following two code words: The sequence is repeated and the original hide sequence RINTINTIN is recovered. Become.

The reserved code words mentioned above are inserted into the data stream during data compression. Two of these are the code words RESET and FLUSH. code war RESET means starting a new dictionary. Court Ward FLUSH indicates that the DC chip has flushed its buffer. vinegar i.e. before filling the buffer sequentially with data again, without compression, and To drain the data currently held in the buffer without restarting compression. It means Based on the algorithm, the DC chip performs RESET and FLU Insert the code word of SH into the data stream.

However, the tape formant has several RESET and FLUSH coats. ・Add constraints on when words must occur, and also add constraints on compressed data. By writing some information to improve access to the code. To ensure that some of the words RESET and F L U S H are available. do.

Since the dictionary has to be reconstructed from the data, the restoration requires the code word R It can only be started from ESET. On the other hand, stopping the restoration is either on any subsequent FLUSH code word, even if it is not the end of a fixed dictionary. can be done. This creates a code word FLUSH at the end of each record. selective recovery of data segments smaller than those used to locate and build the dictionary. This is why it is advantageous to make the original possible.

Most of the data is never referenced before, so at the beginning of the dictionary, Most of the data is ejected without compression. At this stage, the compression ratio is relatively small . Therefore, it is undesirable to restart the dictionary so frequently that it reduces compression efficiency. do not have.

The main purpose of writing extra information to the data stream is to help the data compression engine and the system controller. Therefore, data The only information in the data stream is information not directly needed by the controller. However, it is potentially important information for the restoration process.

Error checking information is probably the most information that can go into a data stream. A case in point. This is written during compression and can be inspected during decompression.

CRC is a good example.

CRC stands for "Cyclic Redundancy Check". This is produced by a series of hides It is a pattern (syndrome). This is due to data corruption occurring during transmission. Several data transmission methods can be used to check for This generates and sent immediately after the data. The receiver of the data also generates it and then Check if the value matches the value received from the transmitter. For example, 4 ha When using ID CRC, the probability of an undetected error is 2/32.

CRCs are also used in data storage and are generated and written to tape. reading The process then generates its own CRC and uses the CR read from the tape. Compare with C.

Putting a CRC in the data stream will cause all the data used to generate the CRC to be Only after the data can it be acted upon. But there are two more options .

It can be compressed together with the data of 1° record.

2. You can write to the uncompressed data stream after the record.

When a CRC is compressed, its value cannot be used on an uncompressed drive. for example , the tape format specification need not leave room for this. child This is part of the compression algorithm (rather than auxiliary information about the data format). Ru. However, since this is a function of uncompressed bytes, the CRC is Can be used for non-compression side hardware.

When writing a CRC to a data stream and uncompressing it, the CRC is truly and is specified as such by the format definition. This is the compression algo Available for all drives that understand the format without any information about rhythm. It is possible.

For compression efficiency, the second choice is better. This is because any CRC This is because it is unthinkable to find it in the dictionary of This is essentially a pseudo-random number that is a function of the bytes that generate the CRC). compressed When it is filled, it expands to about 15 times its original size. 4 Hyde CRC is compressed When compressed, it occupies 6 bytes of storage, and when uncompressed it occupies only 4 bytes of memory. Ru. However, for reduced coupling, the first The first choice is better.

Another example of the type of information that fits into a data stream is to This is information that can be used for System controller write or read You do not need this information during reading; it can be generated on writing, and reading data stream if it can be skimmed or deleted in a simple way easily adapts to the system.

Even records of the same size when compressed produce variable length records, so This type of information is important in a compression environment.

Flash/FOR code word was written automatically by DC chip is the data separator that is removed. However, only the restore drive or these Access separation. To access these boundaries on a non-recovery drive: , extra separation information must be included in the data stream. This is supplementary information be.

This can be a compressed hide count (CBC). CBC, EO If written to the format after the R code word and uncompressed, the unrestored driver Eve can use them as pointer information in linked lists. Ru. Starting at the end of a set of compressed records with a CBC at each or the end , this enters the data and calculates where each compressed record in the set begins and ends. Calculate.

Forma soto is redundant if both are used (FOR code word/CBC) It is. This redundancy provides another check on the validity of the restored data be able to. The restorer calculates the number of bytes restored by counting the number of bytes in the data stream. If they do not match, an error signal can be sent.

Next, consider how data is stored on tape, compressed or uncompressed. I will explain.

Supplying data from the user (host computer) to tape storage requires storage Physical separation of data into discrete packages (records) sent to equipment or an overview of the high-level record that a host represents with a particular signal. Regardless of whether it is a mental organization, it usually involves user separation of data. this User separation of data is particularly meaningful for hosts (this implication is Although it is normal for the storage device to not understand this). Therefore, the existence of the input data Even if logical separation is conveyed to storage devices, user separation cannot be divided into logical segments. It is appropriate to consider it as a tion.

Figure 1(a) shows that existing types of hosts can provide tape storage. A sequence of user data and special separation signals is shown. In this example, The data is supplied as variable length records R1 to R9, but this physical separation logic The host understands the meaning, but the storage device does not. In addition to physical separation, The separation information is provided in the form of a special "file mark" signal FM. Phi The mark FM is inserted between data records and provided to the storage device. , again, the meaning of this separation is unknown to the storage device. physical to record The separation gives the separation of the first rubel, while the file mark gives the separation of the first rubel. A second level of separation is obtained that is hierarchical to Lebel's separation.

FIG. 1(b) shows the user data and user data of FIG. 1(a) for tape 0. One possible physical organization for storing the separation information is shown; This organization is based on known data storage methods. Figure 1(a) and Figure 1 The mapping between (b) and file mark FM is simple. is recorded as a constant periodic burst 1, otherwise the data record Records R1 to R9 and file mark FM are treated as signals. They are separated from each other by an interblock gap 2 that is not shown. Pro-Tsuku Gya Step 2 is to separate the stored data into logical unit records that can be understood by the user. File mark FM (constant periodic burst 1) A second level separation mark is formed that divides the record into logical collections of records.

FIG. 1(C) shows the user data and user separation of FIG. 1(a) on tape 10. A second possible and well-known organization for storing information is shown. this place In each case, the user data is an index containing information about the contents of the group. are organized into fixed-size groups 3 with boxes 4. between 2 groups and 3 The boundary between the lines can be indicated by a periodic burst 5. Google the data The division into loops is purely a matter of convenience for the storage involved. , should be obvious to the host. User data within a group is are not physically separated, and each record is separated from the end of the preceding record. The data in the group is separated and recorded. files, and also a collection of records delimited by file marks. All the information you have created is included in the group's index. In this example, record A first portion of the codes R1-R8 and R9 are held in the example group 3.

The length of index 4 is determined by the number of separation marks in the group and the number of records. It generally varies depending on the number, but within the index for the end of the group By recording the index length in place in It is possible to identify boundaries between undefined content, e.g. padding space exists between the end of the data area and the first byte of the index. There is a possibility that

Figure 2 shows the contents of index 4, and as you can see, the index The system consists of two main data structures: the group information table 6 and the block information table 6. It consists of an access table 7. block access table 7 entry The number of birds is determined by the block access table entry in the group information table 6. is stored in the BAT ENTRY count field. glue The file mark count FMC (end of recording (BO) R) Marks include any items contained in the current group, so number of file marks) and record count RC (defined). Contains various counts.

The block access table 7 contains group access entries as a series of access entries. the contents of the group and, in particular, the logical segments of user data held in the group. mentation (i.e. each record boundary within a group) (contains entries representing separation marks). Access entries are They are arranged in the order of the loop contents.

Referring to Figure 3, each entry in the block access table is , a FLAG entry indicating the type of entry, and a C0UNT entry indicating its value. Consists of li. The FLAG field is 8 bits, and the COUNT field is 8 bits long. The field is 24 bits. The bits in the FLAG field have the following meanings: Yes: 5KP - When set, the 5KIP bit indicates “Skip Entry”. Tut. Skip entries are groups that are not picked up by user data. Number of bytes in the group, i.e. (group size) - (user data area support) is).

XFR - DA, when set, indicates writing user data to tape TA TRANSFER bit.

EOX - When set, controls the writing of user data records to tape. END OF DATA TRANSFER bit indicating end.

CMP-cent indicates that the entry is related to compressed data. COMPRESS ION hit.

EOT - This hint value is irrelevant for the purpose of this discussion.

MRK - When set, an entry or a separation mark rather than a data record. SEPARATOR MARK human being associated with.

BOR - When set, BEGINNIN indicates the starting position of the data record. G OF RECORD bit.

FOR - indicates the end of a data record on tape when sent END OF RECORD hit.

Figure 3 shows the seven types of entries that can be created with block access tables. Show the bird. 5EPARATORMARK (separator mark) entry is Since it is defined as a record, it is a BOR and EOR hit set. Next Each of the four entries represents information about a data transfer, so There is a set. 5TART PART OF RECORD (start of record ) entry matches the injury group that started the record, and the next part of the record This corresponds to the case where it extends to the next group. MIDDLE PART OF The RECORD (middle part of record) entry flag indicates that a record is not included in the group. There is no beginning or end, so it is a data transfer bit. END PART The OF RECORD (end of record) entry has an EOR hit in the flag. Instead, the FOR bit sets the total record hide count. Set the TOTAL COUNT (h-total count) entry to give the count. will be cut. Last entry in the book access table in the group always gives the group the amount of space not occupied by user data 5KIP (skip) entry, i.e. counter in 5KIP entry. The entry in the client field is the group size (for example, 126632 hides). is equal to minus the data area size.

Block access table for group 3 of records shown in Figure 1(C) An example of this is shown in FIG. Count en for records R1-8 is the total hide count for that record, but for record R9. The count entry is the hide count for the portion in group 3 of R9. be. Count entries for File Mark FM follow the format. becomes 0 or l. The count entries for 5KIP entries are 12 6632 minus the sum of the byte counts that have already appeared in the table (Does not include TOTAL COUNT entry).

In another embodiment, it may be used to compress a group of data as shown in FIG. Additional possible errors in the block access table showing the algorithm There is an entry. The algorithm number entered in the C0UNT field is This is a desirable number that complies with algorithmic number standards. Compression levels as a group Data transfer and total count FLAG entries for code include C There is an MP bit set. Therefore, compressed and uncompressed records in a group The codes can be differentiated by the drive based on the CMP bit. for example , in Figure 1(C), the even-numbered records are compressed and the odd-numbered records are compressed. Assuming the record is an uncompressed record, the block access table entry The birds are as shown in Figure 4A.

In Figure 4A, UBCX indicates the uncompressed bytes of record X, and CBCX indicates the record Indicates the compressed bytes of X.

Figure 5 shows another possible way to store user data and related information on tape. Show the configuration. Again, user data is added to the group, about the contents of the group. Configure block access tables to include information (compressed into groups) A fixed-size group with an index (uncompressed even if it contains data) configured into a group. Should boundaries between groups be indicated by periodic bursts? can.

However, rather than storing information in the group index by recording In this example, an entity or an "ensemble" consisting of one or more records is used. It is necessary to memorize information about the content of the group by Ru. In this example, the entity has n compressed lengths, each with the same uncompressed length. Records can be included (n is a number greater than or equal to 1) In FIG. 5, group G consists of four complete records of compressed data) "CR, ~CR, and a single entity ENTIT consisting of an 8-hide header portion H Constructed by YI (or El). record)” CR, ~CR, are the same It has the same uncompressed length, but after data compression, it naturally becomes a specific length.

The uncompressed header portion H in the data stream includes: contains information H, - Header length (4 bits). (The next 12 bits are reserved).

ALG# - Memory number l representing the compression algorithm used to compress the data. id).

UBC - Uncompressed byte count for records within an entity (3 hides) ).

#REC3 - Number of records in the entity (2 bytes).

Optionally, at the end of each record within an entity, each record's Can include a trailer section that contains compressed hide counts. It is Noh. For example, the trailing part is the “end of record” (FOR) code. It will be placed immediately after the word.

If this feature exists, it is reserved after the header length H, in the header part. It is also possible to indicate the length of the trailing part, e.g. 3 bits, among the 12 hits entered. .

An example of an embodiment in which each record of an entity has a trailing portion is shown in FIG. 5A. . The trailing portion is added to the uncompressed data stream at the end of each compressed record. written. Therefore, the entity in FIG. 5A has header parts H and , each with an uncompressed trailing part molecule and having the same length when uncompressed Contains records CR, to CR4.

The trailing portion of each record contains the record's compressed hide count (CBC) and and cyclic redundancy check (CRC). The trailing section is for each record in this example. occupies the last 6 bits of the code. The length of the afterword part (TL) is the header part H. It occupies the last 4 bits of the first hide byte of header part H.

By including the trailing portion, the 5KIP count entry will be correspondingly smaller. or change the characteristics of an entry in the block access table T. do not have.

Writing compressed byte counts to the data stream can be done using a DC drive or as a pointer in a linked list on a non-DC drive configured to can be used to estimate where each compressed record begins and ends.

By using the FOR code word and CBC in the DC drive, It provides redundancy and can be used for error checking purposes during restoration. restoration The device sends an error signal when the CBC and the number of bytes restored do not match. be able to.

The advantage of including the length of the header section (and trailing section, if applicable) in the header is , thereby making it possible to vary this length and at the same time, if desired , which means you can force the drive to skip the header.

inches for each group in the block access table2. There is a record in the Not in the form of a code (in the form of an entity, but in other cases, Information is recorded as described above in connection with FIG. In Figure 5, entity E The block access table entry for 1 is also shown.

The types of entries made in the block access table T are shown in Figures 2 to 4. It is similar to what is described in relation to The difference is that an entry is not a record. , the FLAG field is related to the hide count for the entity. This is what the new setting of the field's CMP bit indicates.

One possibility is that an entity can only contain compressed records. However, this is desirable. Therefore, this Setting the It will represent that. On the other hand, another possibility is that the entity is under pressure. Contains either compressed or uncompressed data, e.g. Specify a specific algorithm number, such as all zeros, to indicate uncompressed data. It becomes possible to make an agreement.

Information is added to block access table T in the form of entities rather than records. By memorizing information, you can write records to tape and extract records from tape. The storage management overhead associated with reading the data is reduced. Figures 2 to 4 When using the scheme shown in the figure, for group G, the block access table In this case, only two entries are required. No need.

Organizing records into entities reduces the processing time required to read and write them. It is easier to transfer multiple records of the same uncompressed size because the intrusiveness of become. The process required to write a sequence of records contained in an entity. The intervention of the processor is to form part of the header and to All you have to do is create a matching entry. In contrast, in Figures 1-4 Using the related known solution, processor intervention is required for each record. become. Because the compressed hide count is unknown until after the compression process is finished, , which is especially important with respect to data compression. Therefore, if a group data, the matching record (and corresponding block access I don't know whether it's the number of entities in the database table or not. block access on an entry By fixing the requirements for access tables, you can determine how many records of data Fill the entire group with one processor intervention, regardless of whether it fits into the group I can do that. Similar benefits can be obtained when reading data.

Referring to Figure 6, if an entity (En) spans two or more groups, For example, an entity E1 containing a single relatively long record CR+ may , group G, and penetrates into group G2. Figure 6 shows the glue Entries in the block access table for groups G, , G2 are also shown. Group In order to weaken the linkage between loops, new entities are Start as early as possible, i.e., if the previous record was not compressed, the group At the beginning of a loop or at the beginning of the first compressed record in a group. at the edges, or if the previous record has been compressed and is missing from the previous group. If it is a compressed record, start at the beginning of the first new compressed record. do. Therefore, at the end of the compressed record CR+, the next entity E2 is opened. start Entity E2 has four compressed records CR2 of equal uncompressed length. ~CRs are included.

Groups contain entities that contain compressed data and “bare records” that contain uncompressed data. This structure is designed to be able to contain a mixture of An example of the configuration is shown in Figure 7, which also shows the corresponding entry in the block access table. is shown.

Group G includes a header portion H and three compressed records 1''CR.

It includes entities consisting of CR2 and CR3. Group G is It also includes an uncompressed record R4 (which does not include a portion of the header). glue Block access table T of block G contains four entries: The first entry is the total/\ite count of entities in the group, The second entry is a file mark entry (entered before the start of record R4). (indicating the presence of a file mark in the force data); the third entry indicates the presence of a file mark in the force data; Total byte count of reduced record R4, last entry is 5KIP entry.

What is noteworthy from Fig. 7 is the CMP bit (the fourth hit of the FLAG field). ) is set for the entity byte count entry? , must not be set for bare record byte count entries. This is the point. A properly configured non-DC drive will Checks whether it is set in the lock access table entry. By doing this, the above-mentioned Data can be identified.

This proposal does not allow separation marks within entities. For example, the host If you are sending a sequence of records of equal length and there are no files in the sequence. If a separation mark or other separation mark is present, the first set of records before the separation mark. The code is contained in one entity and separation marks are written to the tape. , the set of records in the sequence that follows the file mark is the second entity. It can be delivered to Of course, the corresponding entries for the two entities and the A separation mark is created in the associated group's block access table (this The example assumes that only one group is included).

Figure 8 shows possible entries in the group's block access table. The sequence of valid entries is shown. In Figure 8, the state of deafness and the action Specified by a rectangle, and block access table entries are shown by ovals. Ru. “Span” records/entities from one group to another It is something that extends.

Existence of entity and multiple compressed records allowed within the entity The group information table in each group's index takes into account the presence of The following fields are defined as follows:

Record Count - This field is a 4-byte field and counts the current group. of the group information table for all groups up to the current group, including the loop. Specifies the sum of the record count values for the current group entry (see below).

Number of records currently in group - This field is a 2-byte field that specifies the total of: This field is: 1) Separate mark entries in the current group's block access table number of li.

ii) uncompressed records in the current group's block access table; Total count of entries.

1ii) Current group block! Uncompressed records in access tables total count of entries.

iv) Entity entry in the current group's block access table A total count of entries or a total count of entity entries exists. Total number of compressed records in all entities.

■) If such an entry exists, the current block access text for the group Compression within an entity where the start of the entity entry is in the table Number of records - 1゜vi) In the current group's block access table Total count of entity entries.

Number of groups in previous record - This field contains separation marks, access points, - Or, specify the execution number of the highest numbered previous group where the beginning of the uncompressed record occurred. 2 hide fields. This is because these previous groups do not exist. If not, all zero hits will be included.

Organization of records in fixed-size groups as explained in relation to Figures 1-8 In general, groups should be kept independent of each other for restoration purposes. is desirable. That is, in general, the RESET code word for each group Preferably placed at or near the starting point. Two main reasons for this One of them is to reduce the coordination between groups, so that Helps reduce the amount of buffer space required, i.e. reduces the possibility of having to fit more than one group in the buffer. This is because it will become a problem. Place the RESET code word at the beginning of the group. Another reason is that it may be desirable to selectively restore records in the middle of a group. This is because there is no need to go outside the group and start the related dictionary if it is desired. .

There are advantages to placing a FLUSH code word after each record. The LUSH coat word is the same as the “end of record” (FOR) coat word. Also known as compressed data, it improves access to compressed data.

This feature allows a restore or request to be made from the RESET code word that precedes the record. It is now possible to restore the records that are stored separately. FLU at the end of each record Placing the SH code word prevents data from entering the next record. It will also be possible to restore the data for each record.

The amount of compressed data that makes up the data dictionary is called a "compressed object." compression An object can span two or more groups of data, as shown in Figure 9. It's sexual. If records overlap from one group to another the RESET code word at the beginning of the immediately adjacent compressed record. Placed within the data stream.

In FIG. 9, group G1 consists of three complete compressed records CR, ,CR2, CR3 and the first part of the fourth compressed record CR4. record The last part of ``CR'' is included in the next group G2. For this example, Records are not organized into entities.

When compressing data, the dictionary is reset at the beginning of group G1 (see Figure 9). (denoted as R). A FLUSH code word (denoted by F) is placed at the end of each record. inserted into the data stream so that the

The current dictionary continues until the end of record CR, at which point the dictionary is reset. will be cut. Therefore, the current compressed object is record 1” CR, ~CR, It consists of

Later, if it is desired to selectively restore record CR3, for example, this record)” CR, i.e. the compressed object containing records CRs Start the restoration at the beginning of the record CR, and continue restoring the data until the end of the record CR. This makes it possible. Obtaining a “clear break” at the end of record CR3 At the end of "CR," the FLUSH code is Avoid entering the beginning of record 1” CR, because of the word becomes possible.

Therefore, access is accessible FLUSH code word (RES ET code word) to create a dictionary during data compression. You can selectively restore data segments smaller than the amount of data used for Wear. The compressed hide count for each record is recorded in the block access table. The format in which the data is stored is the compressed data that forms the access point. There are several starting points, i.e. points at which a restore operation can be initiated on a drive. This can be shown by one of the following methods. Access points are can be explicitly written in the group's block access table. Others In other words, the presence of an access point is another entry in the block access table. For example, even the existence of an algorithm number entry , may contain an access point at the beginning of the first new record in the group. .

Also, the algorithm number bits indicate that the new dictionary is the first new record in the group. It may also be reserved to indicate that it starts at the beginning of the code.

Records are organized into entities, and the entities are shown in Figures 5-7. Relatively small amounts of data when organized into groups of explanations related to figures The compression option allows you to take advantage of dictionaries that share An object spans two or more entities, as shown in Figure 10. It is also possible to

FIG. 10 shows three fixed size groups G1, G2 . G3 is shown. Group G1 contains the complete record CR1 and the next record C. Contains the first part of R2. Record CR, is in entity E1 This is the only record of its kind. Group G2 includes the middle part of record CR2. It is. Group G3 includes the last part of record CR2, and Code CR3 etc. are also included. Entity E2 has a single relatively long record. Code CR2 is included.

During compression, the dictionary is reset at the beginning of group G1 (indicated by R), but the record The compressed object consists of record 1”CR and entry 1” since it is relatively short. It extends beyond the entity and includes record 1" CR2 and entity E2.

The compressed object ends at the end of record CR2 and a new compressed object starts at the beginning of record CR,.

Other possibilities include a non-entity header to indicate the start of a new dictionary. The presence of a zero algorithm number and other predetermined values, e.g. There is an algorithm number header entry for using ro etc.

Write compressed byte count for entities in block access table FLUSH coat at the end of each entity, accessible by ・Due to the existence of words, it is possible to selectively restore records for each entity. I can do it. For example, referring to FIG. 10, entity E2 (in this example As it happens, the contents of one record CR,) contain data from the beginning of record CR3. It can be restored without losing it. However, access in tape format RESET at the beginning of entity E, which is the start of the nearest possible previous dictionary Restoration must begin with the code word. Figures 20A and 20B For each record using the information in the entity header that describes the diagram You can also restore data.

Of course, the DC chip will follow the algorithm even in the middle of the record. , inserts a RESET code word into the data stream. The above explanation is RESET codes enforced, recognized, and utilized by the tape format. It is about the word.

For clarity, entities and compression pairs are shown in Figures 5-7. The index does not include the index of the related group.

Next, we will explain the tape format for implementing the helical scan of the present invention. Explain.

The storage method and device described below are based on the DAT Conference 5 standard. (March 1988, Electronic Industry, Tokyo, Japan) <PCM O - Store data in a format similar to that used to store audio data. Utilizes a helical scanning technique. However, the method and apparatus It is better suited for storing computer data than video information.

In FIG. 11, tape 10 from tape cartridge 17 is shown with a winding angle of 90°. A helical scanning tram passes through the rotating head tram 12 at a predetermined angle so that The basic layout of the deep deck 11 is shown. In operation, the tape 10 By rotation of the punch roller 16 or the capstan 15 that presses the tape, the arrow It moves from the feed reel 13 to the take-up reel 14 in the direction indicated by T, and at the same time moves to the take-up reel 14. The head drum rotates in the direction shown by arrow R. The head drum 12 has an angle Two read/write heads HA, HB spaced 180° apart be accommodated. In the known method, these spatulas) HA, HB are shown in FIG. The overlapping diagonal tracks 20 and 21 are respectively placed on the tape 10 as shown in FIG. configured to write. The track written by head HA has a positive axis. azimuth, while the HB writing track has a negative azimuth. . Each pair of positive and negative azimuth tracks 20,21 constitutes a frame.

FIG. 12 shows each track to be written by the device of the present invention. The basic format of the block is shown. Each track has two margin areas 22 ．． Two sub-zones 23. Two ATF (Automatic Track Following) zones 24; It consists of a main area 25. The ATF area 24 is either HA, HB or a known The method provides a signal that allows accurate tracking of the track. In the main area 25 , some auxiliary information may also be stored, or primarily the data supplied to the device. data (user data). Complements stored in the main area and subareas Items of auxiliary information are known as sub-coats, such as user data , its mapping to tape, some recording parameters (format identity, tape parameters, etc.) and logical records of tape usage. It's about organization.

Next, select a block that complies with the DAT Conference 5 standard mentioned above. main area 25 and sub-area 23, details of the invention, including details regarding the block size; An explanation shall be provided.

FIG. 13 shows the data format for the main area 25 of the track. There is. The main area consists of 130 blocks, each 36 bytes long. ing. The first two blocks 26 facilitate timing synchronization during playback. This is a preamble that contains the timing data pattern to be used. remaining 12 8 blocks 27 constitute the "main data area". Each block of the main data area 27 is a "main ID" area 28 of 4 hides and a "main data" area 29 of 32 hides. The configuration is shown at the bottom of FIG.

The main ID area 28 contains a synchronization byte, bytes W1 and W2 containing two pieces of information, and a parameter. Comprised of Liti Hyde. Byte W2 is associated with the block as a whole. used for storing information (type and address), while hide W1 is used for storing information (type and address). It is used to remember the start date.

The main data area 29 of each block 27 generally contains user data and consists of 32 bytes consisting of data and/or parity. . However, it is also possible to store sub-codes in the main data area if desired. It is.

FIG. 14 shows the data format in each sub-area 23 of the track. It is. Each sub-region consists of 11 blocks of length 36 notes. will be accomplished. The first two blocks 30 are the preamble, while the last block 31 is a postamble.

The remaining eight blocks 32 constitute a "sub data area". Each flock 32 , 4-hide “sub-ID” area 33, and 32-hide “sub-data” area 34. The configuration is shown at the bottom of FIG. 14.

The sub ID area 33 includes a synchronous hide, hides SW1 and SW2 containing two pieces of information, and Parity Hyde. Note λ light SW2 is a block block as a whole. Stores information regarding the block (type and address) and the configuration of the sub data area 34. used to do. No. 1ite SWI is used for storing sub-codes.

The sub-data area 34 of each block 32 consists of four 8-note "packs" 35. It consists of 32 bytes grouped into . These packs 35 are The types of sub-courts used and stored in the first half of each pack are Displayed by the pack type label that occupies bytes. all even blocks The fourth puck 35 may be set to zero or the third puck 35 may be set to zero. For the fourth pack of all odd blocks, on the other hand, for the first three punctures for both the block and the preceding block. and is used to store parity check data.

In short, the user data is stored in the main data area block 27 of each track. data area 29, while the sub code is stored in the sub data area block 32. sub-ID and sub-data area 33.34, and the main data area block 27. Data area 28. Can be stored in both.

For the purpose of this explanation, the important subcodes are the tape area to which a particular track belongs. Area ID sub-code used to identify area and record count and a number of sub-coats used to store separator marks.

The area ID sub-code is a 4-hit code stored in three locations. It is. First, it displays all blogs in the track's sub-data area. is stored in the third and fourth packs 35 of the sub-data area 34. The second is All even sub-data area blocks of a track, starting from one block. It is stored in the hide SWI of the sub-ID area 33 of the block 32.

Regarding the tape area identified by this sub-code, see Figure 15. I will discuss this later.

Sub code used to store record and separator mark counts The code is located in the sub-data area of each track within the data area of the tape. Stored in the first two packs 35 of the sub-data area 34 of every block. (See discussion below regarding FIG. 15). These counts, as already mentioned, This is the same cumulative count as the count in the group information table. These couns is used for fast tape searching and groups are used to facilitate the process. is constant for a set of frames, and is constant for a group of frames. The recorded count is applicable as the end count of the group.

Next, we will discuss the general structure of the frame along the tape realized by the present storage method and device. Consider organization. For example, referring to FIG. areas, namely the lead-in area 36, the data area 37, and the end of the data. 38. Both ends of the tape are BOM (media (start of media) and EOM (end of media). User data is stored in the data area It is recorded in 37 frames. The lead-in area 36 contains the BOR map at the beginning of the recording. - contains the area between the data area 37 and the system information or stored data area 37. Ru. Area ID sub-coats are system area, data area 37, and EOD area. areas 38 to be distinguishable from each other.

The frames 48 of the data area each have a fixed number of frames (e.g., 22). Optionally, these groups 39 are grouped into groups 39 consisting of: They are separated from each other by one or more angle frames with predetermined content.

In connection with the organization of the Jeep data record, these groups are shown in Figure 1 (C ) corresponds to group 3 of the explanation. Therefore, these groups39 Incorporating user data has no effect on logical segmentation of user data. relationship and information about this segmentation (record marks, separation marks, index 40 located at the end of the user data within the group. (The index actually indexes the user data space within the group.) occupy). Figure 15 shows the input that occupies the last part of the last frame of the group. dex is shown, but this is correct before the data is recorded to tape. only with respect to data organization prior to the Hyde interleaving operation typically performed in However, for our purposes, the interleaving operation can be ignored.

In fact, the information in the index is the main data area of the tracks in the group. are physically dispersed within the

Figure 2 shows the contents of index 4, and as mentioned above, the contents of index 4 are shown. The database consists of two main data structures: the group information table and the block access table. consists of access tables. The group information table is placed at the end of the group. It is stored in a fixed location in the group and is the same size regardless of the contents of the group. Contrast The block access table varies in size according to the contents of the group. , extending in the opposite direction from the group information table to into the rest of the data area. in block access table In this case, the entry contains the actual user data from the group information table, i.e. It is created in the opposite direction to the boundary with ``Pat''.

FIG. 15 shows sub-data area block 3 within data area group 39. The contents of 2 are also shown. As mentioned above, the first two packs have a separation mark The second pack 35 contains a record count RC (defined The third pack 35 also includes an area rD and an absolute frame count A. FC is included. Count FMC1 for all trunks in the group and the RC held in the sub-data area block is group index This is the same as that held in the group information table 41 of No. 40.

Figure 16 shows how user data is compressed and recorded according to the tape format described above. FIG. 2 is a block diagram of a storage device for recording. The apparatus includes a section in connection with FIG. Also included is the tape deck 11, which has already been described in detail. In addition to tape and decks, The device has an interface between the device and a host computer (not shown) via a lotus 55. interface unit 50, main data area and sub-data area; User records contained in and retrieved from data area blocks 27 and 32 A data compression processor (DCP) that processes code data and separated data; A group processor 51 consisting of a frame data processor 52 and a frame data processor 52 , write/read tracks, and switch the two heads HA and HB accordingly. a signal organizer 53 for synthesizing/decomposing signals for control the operation of the device in response to commands received from the computer via the unit 50; A system controller is included to control the system. Main components of the device Each of these units will be further explained below.

First, we will discuss the structure and operation of a data compression processor (DCP) or data compression engine. I would like to talk about the work.

Referring to Figure 17, the heart of the engine is the data presented to it. A VLSI data compression chip (DC chip) that can perform both compression and decompression. ). However, only one of the two processes (compression or (restoration) only. To smooth the data transfer speed flowing through the chip , the input and output of the DC chip have two first-in, first-out (FTFO) memories. or are placed.

Data patterns require more processing per note than other patterns. Some clock cycles are large, so the data transfer rate of DC chips is , not constant. The instantaneous data transfer rate is a function of the current compression ratio and the collision of dictionary entries. They both depend on the current data and the last time the dictionary was refreshed. Determined by the data that makes up the entire sequence after it is set. sub system The third section of the system contains an external dictionary used for local storage of the current dictionary entry. A bank of static RAM forming memory (EDM). These en contains characters, code word pointers, and control flags. .

FIG. 18 shows a block diagram of a DC integrated circuit. There are three DC chips blocks, namely input/output converter (IOC), compression and decompression converter (C DC) and Microprocessor Interface (MPI) .

The MPI section provides functionality for controlling and monitoring the DC chip. Applicable The section contains 6 control registers, 8 status registers, and 2 20-hit registers. Input and output cutter counters and programmable automatic dictionary reset circuit It is included. Access to control and status registers is provided by a general-purpose 8-bit master. This is done via the microprocessor interface bus. control register enables and disables various chip functions and allows the chip to be configured in various operating modes. mode (compress, decompress, eject, or monitor). The status register is on-chip. 20-bit counter and various status flags.

It is possible to improve the compression ratio by resetting the dictionary fairly frequently. I understand. This is especially true if the data stream being compressed has similar hide storage. This is true if only a few rings are involved. Frequent dictionary resets There are two important advantages.

First, resetting the dictionary returns the code word length to 9 bits.

Second, create a new dictionary entry that reflects this data stream. (a kind of adaptation). The interface section of the DC chip is Contains a circuit element that dynamically monitors the reduction ratio and automatically resets the dictionary when it is adapted. It is rare. If the data has little or no redundancy, then Most data compression algorithms scale their output.

The IOC section/yon consists of hide streams and variable length code words (from 9 hits). 12-hit stream). eight Two of the reserved code words are used exclusively by the IOC. child One of these code words has a length of one code word for the IOC. Used to command that the value should be incremented. for example, Code word size processes are separated from the CDC section - I OC follows an independent pipeline process, so CDC can be compressed or decompressed without being slowed down by IOC. Ru.

FLUSH (or 'end of record' (EOR)) code word. A second reserved code word indicates that the next code word is in the current packet of data. be the last code word associated, i.e. the FLUSH code word Alerts the IOC that is actually the penultimate compressed record. this From the information, the IOC finishes its backing routine and ends on a byte boundary. Know that. This feature provides the ability to restore this packet to its constituent packets. It is possible to compress a large number of input buckets into one contiguous output bucket while maintaining You can do something like that. IOC sent data directly from input to output without warning You can also send data while monitoring the possible compression ratio of the data. these This feature can be used as another level of extended protection.

The CD C section converts restored data to compressed data and vice versa. This is Ennon. This section matches the maximum data sloop node. It consists of fully regulated control, data paths, and memory elements. CDC is , interfaces with the IOC via two 12-bit hashes. When compressed, I The OC drains the input bytes into the CDC section where they are converted to code words. do. These court words are sent to the IOC and panned to form a bar. It is then sent out from the depths. Conversely, when restoring, the IOC uses the input bytes Convert the stream to a stream of code words and convert these code words into CI) C section where these are converted into a byte stream and sent to the IO Allow it to be sent to C. The CDC section is also used to store dictionary entries. directly interfaces to external RAM that can be used.

CDC utilizes two reserved code words. The first reserved court word is , used whenever the dictionary is reset.

The occurrence of this code word results in two actions. That is, I OC returns to packing or unpacking 9-hit court words; CDC resets the current dictionary and begins building a new dictionary. Dictionary Norise The restart can be performed by MPI via microprocessor control or by automatic reset. Required by set circuit elements. The second reserved court word is the new CDC 1. Construct a new dictionary entry. is running out of available external RAM. Then it will always be generated during compression. This event occurs in the external RAM or If so, it will rarely occur. However, as the amount of memory decreases, CD C encounters too many dictionary conflicts and is unable to construct new dictionary entries. becomes more likely to occur. External memory becomes smaller and dictionary collisions inevitably increase , data throughput and compression performance are slightly degraded. CDC recovery Initially, the decompression process builds the same point dictionary entries as the compression process. This "full dictionary" code is also used to ensure stopping.

Next, returning to FIG. 16, the data storage device responds to commands from the computer. to load/unload tapes and store data records or separator marks. allows data compression, explores selected separation marks or records, and is configured to read back the records of

The interface unit 50 receives instructions from the computer and controls the device. to manage the transfer of data records and separation marks between computers. It has become. When the command is received from the computer, the interface unit 50 to a system controller 54, which controller in turn sends: A return indicating whether or not to comply with the original command is sent via the interface unit 50. send the answer back to the computer. The device is controlled by system controller 54. , to store or read data in response to commands from a computer. Once set up, the interface unit 50 interfaces with the computer. It also controls the transport of records and separation marks between group processors 51. Ru.

When storing data, the group processor 51 stores user data if necessary. compresses and provides user data to it in the form of data records, respectively , configured to organize into data baccenos corresponding to data groups. There is. The processor 51 also stores an index and a corresponding sample for each group. It is designed to compose a program code. When reading, the group process The server extracts the data records and segments from the groups read from tape before the restore. Implement a reverse process that allows you to recover separation marks.

The form of the group prosensor 51 is shown in FIG. group pro The center of the processor 51 is data that forms a group of two or more (for example, two). 71 sofa 56 adapted to hold the amount. Input data support output data The allocation of buffer space to data is controlled by the buffer space manager 57. be controlled. The processor 51 communicates via the first interface manager 58 through the interface 50 and the second interface manager 59 Communicate with frame data processor 52. Overall grouping process Controls include function block 1 that generates group indexes and associated codes during recording. 11-tri 61), generate sub-code on read (function block 62) Implemented by looping manager 60. The grouping manager 60 It is adapted to exchange coordination signals with the stem controller 54.

DC Processor A DCP compresses or compresses data for storage on tape. serves to restore the data for reading by the host. Control signal for the exchange of a DC processor DCP and an interface manager 58, Buffer 56, sofa space manager 51, and grouping manager 6 An interconnection is made between the

The grooving money store 60 organizes compressed data into entities and There is also an entity manager (EM) that generates some of the headers for the entity. include. Grouping manager 60 and buffer space manager 5 7 is the control component, and the data for writing to tape is , rather than passing through them, the interface money directly from the buffer 56. Proceed to Ja59.

During recording, either the host or the interface unit sends out the data records. Kit 50 is an interface manager to buffer space manager 57. via layer 58) to determine whether processor 51 is ready to receive the record. Inquire. The buffer space manager 57 initially sends a "wait" response, but , among which enable the transfer of data records from the host to the Huffer 56.

If the data is compressed (according to control signals from system controller 54) ), the DC processor processes records based on data compression algorithms, as described above. The code word is used in place of a portion of the data in the code.

In general, transferring multiple records makes sense if the records are shorter, but The host transfers records one at a time.

Grouping manager 60 is connected to buffer space manager 57; For the buffer space manager 57, enter the group's index area. Before starting a group, let the group know how much data it can accept.

The buffer space manager 57 determines whether the maximum number of hides has currently been transferred to the group; Alternatively, whenever the last byte is received from the host, the grouping Notify manager.

If everything transferred from the host cannot fit into the group, the group It is said to "straddle" the boundary between The first part of the transfer is put into one group. , the remaining parts are placed in subsequent groups. The buffer space manager 57 , the host attempts to supply more data than will fit in the current group being configured. If so, the grouping manager 60 is notified. If you do not straddle the group The integer and soku are updated, and the grouping manager 60 waits for another write command. Two.

If it is to span, the index of the current group will be updated and the group can be used to write to tape. The next group is started and from the host data goes directly into the beginning of the new group.

A record is a record delimiter within a group of which it is a part. is transferred to the buffer location corresponding to the final positioning of the data. record size information is sent to the grouping manager 60. If you send a host or separate indication , which is also routed to the grouping manager 60. grouping manager The manager remembers the separation mark and the record count from the BOR and Loop index and separate counter and record count sub-coats Use this information when configuring the . The index is its index at the end of the group. Constructed into a position in the buffer that fits the position.

At the same time, entity manager EM stores the current Generate part of the entity header for the entity. Part of the header is compressed Not done. Similarly, the entity manager EM creates a postscript for each record. It is possible to generate a compressed part (uncompressed).

The Entity Manager EM must adhere to the rules governing entity information. be responsible for that. They are shown below.

a): 1) As soon as possible after the start of the group, 11) Records sent from the host. When the uncompressed size changes, 111) When the compression algorithm changes, the new start a new entity.

Regarding (1) and 1ii) above, due to the need for access points, new The start of the activity is required and the corresponding signal is sent from the grouping manager 60. It is sent to the data compression processor DCP. )b).

1) When it is necessary to store uncompressed records; 11) When it is necessary to store separation marks. , terminate the entity.

The formation of each entity triggers a BAT entry.

Once a group is full, data compression and compression will continue until a new group is started. The entity building process stops.

If human data should not be compressed, the data remains unchanged and Passing the CP, the entity manager EM becomes inactive. restoration record A node can be edited directly into a group without forming part of an entity. information about the records is stored in the group index.

Once the group (including its index and sub-coats) is assembled, The main data of 22 sequential frames is transferred to frame data processor 52. The data area is organized into blocks that constitute data areas and sub-data areas. to frame ID The relevant information is in the data stream. Memorizes the amount of data for 3 frames In the possible frame data processor 52, a group processor and a small Between the shape buffers there is a continuous stream of data.

As mentioned above, between groups of frames recorded on tape, one or more amplifiers In some cases, it may be desirable to insert a frame. This is the frame data program. Processor 52 is activated by instructions from group processor 51 or by If the processor 52 is aware of the group structure, it automatically By configuring it to generate such an ampoule frame at the end, it is possible to become.

The buffer 56 is designed to hold data corresponding to two groups. By reading one group, the overall operation of processor 51 is processing and outputting one group to keep it as easy as possible. Ru. During writing, data from the host is used to create one group and another Groups are written to tape.

While reading data from the tape, the group processor 51 - Receives user data and sub-coats for each frame from the data processor 52; The data is written to the buffer 56 and sent to the group. form. Next, group processor 51 accesses the group index. Logical organization of user data within groups (records/entries) information about the data structure, separation marks) and whether the data is compressed or not. The display can be restored.

When the data is restored, or the data is compressed, it is hosted in compressed format. After being read back to the store and performing software restoration, the Group Prosensor 5 1 is the record or separate map requested by the host via the interface 50. In this case, the data remains unchanged through the DC process. Pass through the DCP.

The entity header portion of the compressed data is sent to the host by a non-DC drive. Sent back and used by the host.

When compressing and decompressing data, the data is processed by the DC process as described above. The data is restored by the server DCP and then sent to the host.

A portion of the header from each entity is used by the DC drive, but Not sent to the server DCP. Some algorithm numbers in the header are It is checked whether it matches the algorithm used in CP. moreover, The number of compressed records for an entity is obtained from the header part, and the entity data Count down the records that are performed when sending the data to the DC processor DCP. be able to.

It is easy to assemble frame data and return it to data for one group. Therefore, when a frame is written to tape, the in-group sequence is Can be tagged with the ken number. This intra-group number can be used, e.g. Header of the main data area of the first block in the main data area of each track of the system It can be shown as a sub-coat within a sub-coat. This sub-coat is When the frame is sent to the group processor 51, the associated frame is stored in the buffer 56. It is used to determine where the item is placed within.

Frame data processor 52 functionally includes a main data area (MDA) processor. processor 65, sub-data area (SDA) processor 66, and sub-coat Consists of unit 67 (in fact, these functional elements are ).

During writing, the sub-coat unit 67 uses the processor 65 and the processor 65 as necessary. and 66, and when reading, the sub-code is sent from the processor 65.66. They are supposed to receive coats and distribute them. Depending on the content of the information, sub- The code is generated by the group processor 51 or the system controller 54. / can be requested, and the separate mark count sub-code is e.g. Determined/utilized by the loop processor 5I, while the area ID sub-code is , determined/utilized by the controller 54. some write parameters In the case of a non-variable sub-code such as, the sub-code is permanently stored in unit 67. You can also do that. Additionally, the sub code unit 67 itself may conveniently It is also possible to generate frame dependent sub-codes.

The MDA processor 65 processes one frame's worth of user data, along with associated sub-coats. ・Data is processed at once. For example, processor 65 may record At one time, one frame is sent from group processor 51 along with sub code from unit 67. Receive one frame's worth of user data. Once the user data is received, the process The processor 65 interleaves the data and outputs the resulting data and sub-codes. The main data area block for the two tracks assembled to make up the frame. Calculate the error correction code before outputting the check. In fact, user data Scrampling (randomization) of data before assembling sub-coats By implementing the can be secured.

When reading, processor 65 reads two sets of main data area blocks associated with the same frame. Perform the reverse process for the Ella without scrambling The dinterleaved user data with corrections sent to the processor 51, separated by the sub-coat or unit 67, and processed as necessary. distributed to either the processor 51 or the system controller 54 depending on the .

The operations of the SDA processor 66 include sub-data areas associated with sub-data areas of the track. Works according to the code and combines these sub-coats into sub-data area blocks. or by disassembling the sub-data area blocks into sub-coats. It is similar to the processor 65 except for this point.

The signal organizer 53 receives the ATF signal from the ATF circuit 80 during recording (data writing). The main data area provided by the frame data processor 52 along with the Assemble blocks and sub-data/area blocks and write them to each sequential trunk. formatter/separator unit adapted to form the signal to be recorded Consists of 70.

If required by unit 70, the track signals are subjected to any necessary pre-assembly and and postamble patterns are also inserted. The pattern responds to the rotation of the head drum. unit 7 by a timing generator 71 to which the output of the pulse generator 81 is supplied. A timing signal is added that coordinates the movement of head 0 and the rotation of heads HA and HB.

The track signal output from the unit to the line 72 is sent to the head switch 73, Each head drive amplifier 74 and the recording/playback switch set at the recording position. The signal is sent alternately to head HA and head HB via switch 75.

The head switch 73 receives the signal from the properly timed timing generator 71. Therefore it works.

Tracks generated alternately by heads HA and HB during playback (data reading) The signal is sent to the record/playback switch 75 (in this case set to the playback position), Each read amplifier 76, second head, switch 77 and clock circuit It is sent via a return circuit 78 to a formatter/separator unit 70. F The operation of head switch 77 is controlled in the same manner as head switch 73. . In this case, unit 70 disconnects the ATF signal and sends it to circuit 80 to data area blocks and sub data area blocks to the frame data processor. It functions to send to the server 52. The processor 52 receives a clock signal from a clock recovery circuit 78. A check signal is also sent.

Switch 75 is under the control of system controller 54.

The tape deck 11 controls the rotation of four servos, that is, the capstan 15. Cab's tongue servo 82 to control the rotation of reel 14 and 15, respectively. The first and second reel servos 83, 84 and head tram 12 to control It is composed of a drum servo 85 that controls rotation. Each servo has both Includes a motor M and a rotation detector coupled to an element controlled by a servo It is.

The reel servos 83 and 84 have start of media (BOM) and end of media (EOM) ) detection means 86 are linked together, but these means 86 may, for example, and the reel being driven to take up the tape (depending on the direction of tape movement) The motor current (determined by can be based on the detection of the motor current.

The tape deck 11 further includes a device for recording on the tape when recording data. An automatic track following circuit 80 is provided which generates an ATF signal. When reading , the ATF circuit 80 responds to the ATFI-RACK signal read from the tape. , add the adjustment signal % to the carburetor tongue servo 82, and record the head HA and HB on the tape. Ensure proper alignment with recorded tracks. tape deck 11 includes a pulse generator that generates timing pulses synchronized with the rotation of the heads HA and HB. A pulse generator 81 is also included.

The operation of tape, de, and key 11 is controlled by servos 82 to 85 and BOM/EOM detection means 8. It is controlled by a deck controller 87 connected to 6. The controller 87 , which causes the servo to advance the tape the desired distance (nominal speed or high speed). degree). This control energizes the servo for a time interval appropriate for the set tape speed. or from one or more rotation detectors associated with the servo. This is done by foot-hacking the tape displacement information.

The deck controller 87 is itself sent by the system controller 54. managed by control signals. The deck controller 87 has BOM and EO A signal indicating that M has been reached is output to the controller 54. There is. .

System controller 54 is a high-level interface between the computer and storage devices. It manages the interactions between the When performing basic operations such as read/unload, the functionality of other units of storage is It has the dual function of adjusting the performance. Regarding this latter, controller 54 functions to coordinate the operation of the deck 11 and the data processing section of the storage device. .

In controlling the tape deck 11, the system controller Move the tape to the controller 87 at normal read/write speed (Normal) or to move the tape forward or backward at high speeds. , that is, request high-speed forwarding (F, FWD) or high-speed rewinding (F, RWD). can become.

When the deck controller 87 reaches the BOM or EOM, the deck controller 87 The information is reported to the controller 54.

Next, regarding the operation of locating the record for restoration, Figure 20A and This will be explained in relation to FIG. 20B.

When the host issues a command to restore a record, the controller 54 Generate a search key with a value equal to the record count of the desired record. current The current record count is determined by the grouping manager of the group processor 51. It is held at 60. The tape is then advanced at high speed (many times faster than normal). (or rewound, if appropriate), while the head drum On the other hand, the heads HA and HB rotate at a speed that maintains the relative speed at a constant value. For motes, it is possible to read approximately 1 track subarea every 300 Yes (steps 91a and 91b). Fast reading of track sub-areas is known This technique is therefore not described in detail.

Figure 20A shows a fast forward search and Figure 20B shows a fast backward search. It is shown.

During fast forward search (Figure 20A), each subarea is read in sequence. Record counts and searches held in the second pack of data area blocks The keys are compared by controller 54 (step 92a). record· If the count is less than the search key, the search continues, but the record count is , if the search key is greater than or equal to the search key, the fast forward search ends and the tape is read (step 93). As a result, currently Record counter held in a subarea of the track opposite the head drum is always less than the search key.

During fast backward search (Figure 20B), each subarea is read sequentially. record counts and search keys held in the second pack of data blocks. are compared by controller 54 (step 92b). record card If the record count exceeds the search key, [continues but the record count exceeds the search key. If the key is below, high-speed rewinding is stopped.

Then, in both fast forward search and fast backward search, the tape is (step 94), and each sequential group is It is read and temporarily stored in buffer 56 of group processor 51.

The record count kept in each group's index is the first search key It is compared with the search key until it reaches the above value (step 95). At this point, record The record to be searched is in the group of buffer 56 whose read count was just tested. Reading is stopped because the code is present. For each record, block When an entry is created in the access table, the index in this group Examine the block access table of the box to identify the records involved. (step 96) and in the buffer of the first data record byte. The address is calculated (step 97). Next, group processor 51 tells the system controller 54 to find the record to be searched and indicates that the next data record is ready to be restored and read. This is reported by the controller to the host (step 98). with this, The search operation ends.

Of course, it is clear that other search methods can be implemented.

To detect when the boundary of the tape data area is crossed during high-speed searching. , the area I is read by the system controller 54 whenever a subarea is read. A check is made for the D sub-code. This subcode allows you to When a search beyond the data area is indicated, the tape direction is reversed and Generally, the search is resumed at a slower rate. For clarity, Section 20A [1 and 20A] This area rD check is omitted from Figure 20B.

Once you have located the records involved, the next step is to Check the algorithm number to indicate which algorithm was used to compress the data. It is to check. This indicates that the algorithm number is the block address for the associated group. If stored in the access table, this is done by examining the table. be exposed.

The algorithm number is the algorithm used by the tape drive's DC chip. or one of the DC chips if there are more than one), the next step is The goal is to find the beginning of the compression target that contains important records. This is related to Figure 9. This can be done in a variety of ways depending on the particular recording format as described above. Ru.

Once the beginning of the compressed object containing the relevant record is found, the restore begins. , the FLUSH (or EOR) code word at the end of the record is reached. will continue until The restore record can then be sent to the host.

The presence of a FLUSH code word at the end of a record indicates the beginning of the next record. This indicates that records can be reliably restored without having to look at the data from the beginning. Ru.

When compressed records are organized into entities, related groups are The location is determined as described above with respect to FIGS. 20A and 20B.

Therefore, the #RECS entry in the entity header within the group It can be used to locate related entities.

The restore will check the Algorithm ID entry in the related entity. starts from the immediately previous access point that can be found, and Indicates that the compressed data in the entity continues from an already started dictionary. , skip to the previous entity until the access point is found. ・Return to header etc. Only recovered data from related records is retained. Not possible. Therefore, the presence of data in the entity header indicates that the associated record Easily find codes and access points and restore data management processes It has the advantage of being able to be separated from the process. Record compression byte If there is a footnote after each compressed record in an entity that contains For example, these CBCs are the count of FLUSH code words at the time of restoration. (or not) to determine the starting point for retaining restored data. It can be used effectively.

Therefore, the presence of auxiliary information in the data stream ・Find the previous access point and confirm the point where the restored data should be kept. It can be effectively used for recognition.

During normal data reading, auxiliary information, e.g. error checking information of the data stream, is information and/or data separation information accordingly.

Generate a CRC on the drive (DC or non-DC) and configure it into the entity. One possibility is to compare with the CRC of the trailing portion of the created record.

Also, the drive (again DC or non-DC) uses the CBC in the trailing part to You can find where compressed records begin and end.

It is understood that the invention is not limited to helical scan data recording. explained The compression algorithm is just an example and the invention can be applied according to different algorithms. It can also be applied to the storage of data that is compressed.

Special table Hei 5-500878 (16) FIG4 IG4A FIG17 Micro 7' Roseana Bass〒〒゛Nitor input dry''-'7　, T Kata ■ Sound? 71 banhku 7 aids, international search report international search report GB 9100082 SA　43981

Claims (11)

[Claims] 1. Inserting extra auxiliary information into the data stream during the data compression process organized in record (CRn) format on tape (10), characterized by A data storage method that writes compressed data. 2. The method of claim 1, wherein the auxiliary information comprises error checking information. . 3. Claim 1 or 2, wherein the auxiliary information includes data separation information. The method described in section. 4. the aforementioned step of writing said auxiliary information to tape (10) in uncompressed format; A method according to any of the claims. 5. inserting auxiliary information related to two or more records into the data stream; A method according to any of the preceding claims, comprising the steps. 6. Header section containing auxiliary information about two or more subsequent records (CRn) (H) into the data stream. the method of. 7. Trailing part containing auxiliary information about two or more preceding records (CRn) (T) into the data stream. is the method described in Section 6. 8. Data records are grouped into groups (G), regardless of the record structure of said data. n) information about the stages of organization and records (CRn) in one group; in the index (4) associated with said group. Any method described in the scope of the request. 9. Multiple entities where one entity has more than one record (CRn) of the claim comprising writing information to said group index by the property. The method described in Scope Item 8. 10. A stage for writing auxiliary information to the header (H) related to each entity (En) 10. The method of claim 9, comprising a floor. 11. operable according to the method claimed in any of the preceding claims; , a storage device that compresses user data and writes the compressed data to tape (10).