Dynamic magnetic information storage or retrieval – Recording for changing duration – frequency or redundant...
Reexamination Certificate
1999-10-25
2003-03-11
Hudspeth, David (Department: 2651)
Dynamic magnetic information storage or retrieval
Recording for changing duration, frequency or redundant...
C360S048000, C711S111000, C711S114000, C710S068000, C707S793000
Reexamination Certificate
active
06532121
ABSTRACT:
TECHNICAL FIELD
The present invention relates to data compression and more particularly to embedding meta-data in a compression stream.
BACKGROUND OF THE INVENTION
Data compression systems are known in the prior art that encode a stream of digital data signals into compressed digital code signals and decode the compressed digital code signals back into the original data. Data compression refers to any process that attempts to convert data in a given format into an alternative format requiring less space than the original. The objective of data compression systems is to effect a savings in the amount of storage required to hold or the amount of time required to transmit a given body of digital information.
To be of practical utility, a general purpose digital data compression system should satisfy certain criteria. The system should have reciprocity. In order for a data compression system to possess the property of reciprocity it must be possible to re-expand or decode the compressed data back into its original form without any alteration or loss of information. The decoded and original data must be identical and indistinguishable with respect to each other. The property of reciprocity is synonymous to that of strict noiselessness used in information theory. Some applications do not require strict adherence to the property of reciprocity. One such application in particular is when dealing with graphical data. Because the human eye is not that sensitive to noise, some alteration or loss of information during the compression de-compression process is acceptable.
The system should provide sufficient performance with respect to the data rates provided by and accepted by the devices with which the data compression and de-compression systems are communicating. The rate at which data can be compressed is determined by the input data processing rate into the compression system, typically in millions of bytes per second (megabytes/sec). Sufficient performance is necessary to maintain the data rates achieved in present day disk, tape and communication systems which rates typically exceed one megabyte/sec. Thus, the data compression and de-compression system must have enough data bandwidth so as to not adversely affect the overall system. The performance of data compression and de-compression systems is typically limited by the computations necessary to compress and de-compress and the speed of the system components such as, random access memory (RAM), and the like, utilized to store statistical data and guide the compression and de-compression process. Performance for a compression device is characterized by the number of processor cycles required per input character under the compressor. The fewer the number of cycles, the higher the performance.
Another important criteria in the design of data compression and decompression systems is compression effectiveness, which is characterized by the compression ratio. The compression ratio is the ratio of data size in uncompressed form divided by the size in compressed form. In order for data to be compressible, the data must contain redundancy. Compression effectiveness is determined by how effectively the compression procedure uses the redundancy in the input data. In typical computer stored data, redundancy occurs both in the nonuniform usage of individual symbology, example digits, bytes, or characters, and in frequent recurrence of symbol sequences, such as common words, blank record fields and the like.
General purpose data compression procedures are also known in the prior art, three relevant procedures being the Huffman method, the Tunstall method and the Lempel-Ziv method. The Huffman method is widely known and used, reference thereto in article of D. A. Huffman entitled “A Method For Construction Of Minimum Redundancy Codes”, Proceedings IRE, 40, 10 pages 1098-1100 (September 1952). Reference to the Tunstall algorithm may be found in Doctoral thesis of B. P. Tunstall entitled “Synthesis of Noiseless Compression Codes”, Georgia Institute of Technology (September 1967). Reference may be had to the Lempel-Ziv procedure in a paper authored by J. Ziv and A. Lempel entitled “A Universal Algorithm For Sequential Data Compression”, IEEE Transactions on Information Theory, IT-23, 3, pages 337-343 (May, 1977).
Redundant arrays of inexpensive or independent data storage devices (RAID) are being employed by the mass storage industry to provide variable capacity data storage. RAID systems use interconnected disk drives to achieve the desired capacity of mass storage. With this approach, a disk drive of one capacity may be manufactured and packaged with the same or different capacity drives to provide the required storage capacity. RAID systems eliminate the need to manufacture disk drives individually designed to meet specific storage requirements. Each disk drive in a RAID system is usually housed in an individual module for handling and installation. The modules slide into and out of a larger enclosure that houses the array of disk drives and provides the sockets, plug-ins and other connections for the electrical interconnection of the drives. Controllers orchestrate the interconnection and control access to selected disk drives for data reading and writing operations.
A RAID system is an organization of data in an array of data storage devices, such as hard disk drives, to achieve varying levels of data availability and system performance. Data availability refers to the ability of the RAID system to provide data stored in the array of data storage devices even in the event of the failure of one or more of the individual data storage devices in the array. A measurement of system performance is the rate at which data can be sent to or received from the RAID system.
Of the five basic architectures developed for RAID systems, RAID 1 and RAID 5 architectures are most commonly used. A RAID 1 architecture involves an array having a first set of data storage devices with a second set of data storage devices which duplicates the data on the first set. In the event of the failure of a data storage device, the information is available from the duplicate device. The obvious drawback of this RAID system implementation is the necessity of doubling the storage space.
A RAID 5 architecture provides for redundancy of data by generating parity data. Each of the data storage devices are segmented into a plurality of units of data, known as blocks, containing equal numbers of data words. Blocks from each data storage device in the array covering the same data storage device address range form what are referred to as “stripes”. A parity block is associated with each stripe. The parity block is generated by performing successive exclusive OR operations between corresponding data words in each of the data blocks. Changes to data blocks in a stripe necessitates re-computation of the parity block associated with the stripe. In a RAID 4 system, all parity blocks are stored on a single unit in the array. As a result, the data storage device containing the parity blocks is accessed disproportionately relative to the other data storage devices in the array. To eliminate the resulting constriction of data flow in a RAID 4 system, a RAID 5 architecture distributes the parity blocks across all of the data storage devices in the array. Typically in a RAID 5 system, a set of N+1 data storage devices forms the array. Each stripe has N blocks of data and one block of parity data. The block of parity data is stored in one of the N+1 data storage devices. The parity blocks corresponding to the remaining stripes of the RAID system are stored across the data storage devices in the array. For example, in a RAID 5 system using five data storage devices, the parity block for the first stripe of blocks may be written to the fifth device; the parity block for the second stripe of blocks may be written to the fourth drive; the parity block for the third stripe of blocks may be written to the third drive; etc. Typically, the location of the parity block in the array for succeedin
Rust Robert A.
Voigt Douglas L.
Baca Anthony J
Davidson Dan I.
Hewlett--Packard Company
Hudspeth David
LandOfFree
Compression algorithm with embedded meta-data for partial... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression algorithm with embedded meta-data for partial..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression algorithm with embedded meta-data for partial... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3084521