公开(公告)号：US5644791A

公开(公告)日：1997-07-01

申请号：US241982

申请日：1994-05-11

申请人： James T. Brady ,  Joe-Ming Cheng ,  Oded Cohn ,  James W. Eldridge ,  Yoram Novick ,  Norman K. Ouchi ,  Danit Segev

发明人： James T. Brady ,  Joe-Ming Cheng ,  Oded Cohn ,  James W. Eldridge ,  Yoram Novick ,  Norman K. Ouchi ,  Danit Segev

IPC分类号： H04N13/04 ,  G02B27/22 ,  G06F3/06 ,  G09G3/02 ,  G11B20/00 ,  H04N13/00 ,  G06F13/00

CPC分类号： G11B20/00007 ,  G02B27/2271 ,  H04N13/0422 ,  H04N13/0488 ,  H04N13/0497 ,  H04N13/0203 ,  H04N13/0434 ,  H04N13/0438 ,  H04N13/0459

摘要： A method for operating a data storage system that is comprised of at least one disk. The method includes a step of partitioning a data compression unit into n basic compression units, where n is greater than one. Each data compression unit is comprised of a plurality of disk sectors and each of n basic compression units begins with a different initial sector. A next step partitions the data compression unit into X intervals, where X is less than n. Each of the X intervals begins with a different initial sector and within one of the n basic compression units. Further steps of the method include storing, external to the at least one disk, a plurality of first pointers each of which points to the initial sector of one of the n basic compression units wherein the 1/X, 2/X, . . . , (X-1)/X intervals begin; storing, within each of the initial sectors of the individual ones of the n basic compression units wherein the 1/X, 2/X, . . . , (X-1)/X intervals begin, a second pointer to the initial sector of the interval that begins within the basic compression unit; and, in response to a disk read operation that reads a compressed data unit that begins with one of the sectors that is located within one of the X intervals, accessing the beginning sector of the compressed data unit in accordance with one of the first pointers and one of the second pointers. The step of allocating includes a step of determining an actual compression ratio for the record, determining a value of a longest run of identical characters within the record, and adjusting the actual compression ratio based on the value of the longest run of identical characters. The step of allocating also includes a step of adding at least one additional sector to the estimated number to enable the compressed record to be subsequently updated in place.

摘要翻译： 一种用于操作由至少一个盘组成的数据存储系统的方法。 该方法包括将数据压缩单元划分成n个大于1的基本压缩单元的步骤。 每个数据压缩单元由多个磁盘扇区组成，并且n个基本压缩单元中的每一个以不同的初始扇区开始。 下一步将数据压缩单元分成X个间隔，其中X小于n。 X间隔中的每一个以不同的初始扇区和n个基本压缩单元之一开始。 该方法的另外的步骤包括在至少一个盘的外部存储多个第一指针，每个第一指针指向n个基本压缩单元之一的初始扇区，其中1 / X，2 / X，...。 。 。 ，（X-1）/ X间隔开始; 存储在其中1 / X，2 / X，...的n个基本压缩单元中的各个初始扇区的每个初始扇区内。 。 。 ，（X-1）/ X间隔开始，指向在基本压缩单元内开始的间隔的初始扇区的第二指针; 并且响应于读取从位于所述X个间隔之一内的扇区之一开始的压缩数据单元的磁盘读取操作，根据所述第一指针和/或所述第一指针之一访问所述压缩数据单元的开始扇区 第二个指针之一。 分配步骤包括确定记录的实际压缩比的步骤，确定记录内相同字符的最长行程的值，并且基于相同字符的最长行程的值来调整实际压缩比。 分配步骤还包括将至少一个附加扇区添加到估计的数目以使压缩记录随后能够更新的步骤。

公开(公告)号：US06324621B2

公开(公告)日：2001-11-27

申请号：US09090028

申请日：1998-06-10

申请人： Shanker Singh ,  Joe-Ming Cheng ,  Brent Cameron Beardsley ,  Dell Patrick Leabo ,  Forrest Lee Wade ,  Michael Thomas Benhase ,  Marc Ethan Goldfeder

发明人： Shanker Singh ,  Joe-Ming Cheng ,  Brent Cameron Beardsley ,  Dell Patrick Leabo ,  Forrest Lee Wade ,  Michael Thomas Benhase ,  Marc Ethan Goldfeder

IPC分类号： G06F1200

CPC分类号： G06F12/0802 ,  G06F12/0871 ,  G06F12/0897 ,  G06F12/127 ,  G06F2212/401

摘要： Aspects for caching storage data include partitioning a storage cache to include a compressed data partition and an uncompressed data partition, and adjusting a size of the compressed data partition and the uncompressed data partition for chosen performance characteristics. A data caching system aspect in a data processing system having a host system in communication with a storage system includes at least one storage device and at least one partially compressed cache. The at least one partially compressed cache further includes an uncompressed partition and a compressed partition, where the compressed partition stores at least a victim data unit from the uncompressed partition.

摘要翻译： 用于缓存存储数据的方面包括对存储高速缓存进行划分以包括压缩数据分区和未压缩数据分区，以及调整所选择的性能特征的压缩数据分区和未压缩数据分区的大小。 具有与存储系统通信的主机系统的数据处理系统中的数据缓存系统方面包括至少一个存储设备和至少一个部分压缩的高速缓存。 所述至少一个部分压缩缓存还包括未压缩分区和压缩分区，其中所述压缩分区至少存储来自未压缩分区的受害数据单元。

公开(公告)号：US20080098170A1

公开(公告)日：2008-04-24

申请号：US11584824

申请日：2006-10-23

申请人： William L. Guthrie ,  Joe-Ming Cheng ,  Nyles Norbert Heise

发明人： William L. Guthrie ,  Joe-Ming Cheng ,  Nyles Norbert Heise

IPC分类号： G06F13/00

CPC分类号： G06F12/0866 ,  G06F2212/601

摘要： A desired cache size in a disk drive is established, and no reordering algorithm is performed on commands in the cache until the desired size is reached. An optimal subset size is also established. Then, an optimization algorithm is performed on all commands in the cache, with only the commands in the optimal subset being output for execution. The cache is refilled to the desired size, and the process is repeated.

摘要翻译： 建立磁盘驱动器中期望的高速缓存大小，并且不对缓存中的命令执行重新排序算法，直到达到期望的大小。 还建立了最佳子集大小。 然后，对缓存中的所有命令执行优化算法，只有最优子集中的命令被输出才能执行。 将高速缓存重新填充到所需的大小，并重复该过程。

公开(公告)号：US6101624A

公开(公告)日：2000-08-08

申请号：US119705

申请日：1998-07-20

申请人： Joe-Ming Cheng ,  Shanker Singh

发明人： Joe-Ming Cheng ,  Shanker Singh

IPC分类号： G06F11/10 ,  G06F11/00

CPC分类号： G06F11/1008

摘要： A method and means for detecting and correcting anomalies in a RAM-based FPGA by comparing CRC residues over portions of the RAM-stored connection bitmap with prestored residues derived from uncorrupted copies of the same bitmap portions. A mismatch selectively invokes either error reporting to the chip only, error reporting and immediate verification testing of counterpart FPGA chip functions, or error reporting, parity-based correction of the words in error, reprogramming of the chip functions with the corrected words, and verification testing.

摘要翻译： 通过比较RAM存储的连接位图的部分上的CRC残差与从相同位图部分的未损坏副本导出的预先存储的残差来检测和校正基于RAM的FPGA中的异常的方法和装置。 不匹配选择性地仅针对芯片进行错误报告，错误报告和对等FPGA芯片功能的即时验证测试，或错误报告，错误的字的基于奇偶校正的校正，使用校正字重新编程芯片功能，以及验证 测试。

公开(公告)号：US6105155A

公开(公告)日：2000-08-15

申请号：US10726

申请日：1998-01-21

申请人： Joe-Ming Cheng ,  Shanker Singh

发明人： Joe-Ming Cheng ,  Shanker Singh

IPC分类号： G06F11/10 ,  G01R31/28

CPC分类号： G06F11/1008

摘要： A method and apparatus in which on-chip functions are checked and any detected anomalies are located within a nested time interval. An on-chip function is tested by (1) applying a predetermined data pattern to the function, (2) computing a linear block error detection code residue from any output from the function being tested, and (3) comparing the residue to a error code residue (signature) derived from the output of a copy of the same function with the same data pattern. In one embodiment, the code signature has been previously derived from an error-free copy of the function. Where the signature is supplied contemporaneously by another copy of the same function also being tested, the function copy is not presumed error free. In both cases, any mismatch between the on-chip code residue and the signature indicates error, erasure, or fault. By either recursive reprocessing or shortening the intervals between comparisons, the mismatch can be located within a nested time or sequence interval.

摘要翻译： 检查片上功能并且任何检测到的异常位于嵌套时间间隔内的方法和装置。 通过（1）对该功能应用预定的数据模式来测试片上功能，（2）从所测试的功能的任何输出计算线性块错误检测码残差，以及（3）将残差与错误进行比较 从具有相同数据模式的相同功能的副本的输出中导出的代码段（签名）。 在一个实施例中，代码签名已经从功能的无错误副本中获得。 如果签名同时由同一功能的另一份副本同时提供，则该功能副本不会被假定为无误。 在这两种情况下，片上代码残差和签名之间的任何不匹配都表示错误，擦除或故障。 通过递归重新处理或缩短比较间隔，错配可以位于嵌套时间或序列间隔内。

公开(公告)号：US5774081A

公开(公告)日：1998-06-30

申请号：US574098

申请日：1995-12-11

申请人： Joe-Ming Cheng ,  Glen George Langdon, Jr.

发明人： Joe-Ming Cheng ,  Glen George Langdon, Jr.

IPC分类号： G06T9/00 ,  H03M7/40 ,  H03M7/00

CPC分类号： G06T9/005 ,  H03M7/4006

摘要： A method and apparatus for compressing and decompressing data is described. The most frequent symbols (A-Group.) are encoded using an Arithmetic Code, then the remainder of the symbols (H-Group) are first encoded using Huffman's algorithm (or any Prefix code) and then combined with the Arithmetic code resulting in a hybrid Arithmetic/Huffman code. After being encoded into a Huffman code, the H-Group symbols are made into a "super-symbol" which fits into an Arithmetic subinterval allocated to the symbols in the H-Group. The Arithmetic subintervals for the symbols in the H-Group preferably are a negative power of 2 (e.g., 1/2, 1/4, 1/16, 1/32, etc.) of the code space. Each such H-group subinterval has its own associated subset of H-group symbols comprising one Huffman code table that fits into that respective interval. Decoding in an AMSAC system first treats the code stream as Arithmetically encoded. Standard prior art Arithmetic decoding is performed until an interval assigned to the super-symbol(s) is encountered. The Arithmetic super-symbol for this interval is then processed to obtain the Prefix code by reversing the scaling and offsetting, if any, that was needed to fit the super-symbol into the assigned Arithmetic subinterval. The Prefix code is then decoded into the original symbol using standard prior art Prefix techniques.

摘要翻译： 描述了用于压缩和解压缩数据的方法和装置。 使用算术代码对最常用的符号（A组）进行编码，然后使用霍夫曼算法（或任何前缀代码）对符号（H-Group）的其余部分进行编码，然后与算术代码组合，得到 混合算术/霍夫曼码。 在编码为霍夫曼码之后，将H组符号制成适合分配给H组中的符号的算术子间隔的“超符号”。 H组中的符号的算术子区间优选为2的负电力（例如，+ E，fra 1/2 + EE，+ E，fra 1/4 + EE，+ E，fra 1/16 + EE ，+ E，fra 1/32 + EE等）的代码空间。 每个这样的H组子区间具有其自己的H组符号的相关联的子集，其包括适合于该相应间隔的一个霍夫曼码表。 AMSAC系统中的解码首先将码流视为算术编码。 标准现有技术执行算术解码直到遇到分配给超符号的间隔。 然后对该间隔的算术超符号进行处理，以通过将符合超符号所需的缩放和偏移（如果有的话）反转到指定的算术子间隔中来获得前缀码。 然后使用标准的现有技术的前缀技术将前缀码解码成原始符号。

公开(公告)号：US5608396A

公开(公告)日：1997-03-04

申请号：US395343

申请日：1995-02-28

申请人： Joe-Ming Cheng ,  David J. Craft ,  Larry J. Garibay ,  Ehud D. Karnin

发明人： Joe-Ming Cheng ,  David J. Craft ,  Larry J. Garibay ,  Ehud D. Karnin

IPC分类号： G06T9/00 ,  H03M7/30 ,  H03M7/38

CPC分类号： G06T9/005 ,  H03M7/3086

摘要： A system for compressing digital data at one byte-per-cycle throughput by removing redundancy before storage or transmission. The system includes an improved Ziv-Lempel LZ1 process that uses a history buffer to save the most recent source string symbols for use in encoding the source symbols as "match-length" and "match-offset" tokens. The match-length code symbols are selected from two groups of buckets that are assigned variable-length prefixes for the shorter, more probable match-lengths and a fixed-length prefix code for the longer, less probable match-lengths. This exploits a transition from Laplacian match-length probability distribution to Uniform match-length probability distribution for longer match-lengths. The offset code field length is reduced during start-up to improve start-up compression efficiency during filling of the history buffer. The match-length code book is limited to a maximum value T

摘要翻译： 一种通过在存储或传输之前去除冗余来以一个字节每周期吞吐量压缩数字数据的系统。 该系统包括一个改进的Ziv-Lempel LZ1进程，该进程使用历史缓冲区来保存用于将源符号编码的最新源字符串符号作为“匹配长度”和“匹配偏移”令牌。 匹配长度代码符号从两组桶中选择，分配给可变长度前缀的更短，更可能的匹配长度以及固定长度前缀码用于更长的较少可能的匹配长度。 这利用了从拉普拉斯匹配长度概率分布到长度匹配长度的统一匹配长度概率分布的转换。 在启动期间，偏移码字段长度减小，以提高历史缓冲区填充期间的启动压缩效率。 匹配长度码本被限制在最大值T <256以限制延迟并简化处理。 几个未使用的匹配长度代码插槽被重新分配给“控制代码”，它们可以在运行时插入到压缩数据流中，而不会减慢或中断编码过程。 通过与源数据同时解码和CRC比较，可以快速验证压缩数据，允许根据需要插入纠错“控制代码”，而不会中断或减缓压缩流。

公开(公告)号：US5666114A

公开(公告)日：1997-09-09

申请号：US343316

申请日：1994-11-22

申请人： Robert Bruce Brodie ,  Joe-Ming Cheng ,  Lawrence John Garibay ,  Jaishankar Moothedath Menon ,  Chan Yiu Ng ,  Tram Thi Mai Nguyen

发明人： Robert Bruce Brodie ,  Joe-Ming Cheng ,  Lawrence John Garibay ,  Jaishankar Moothedath Menon ,  Chan Yiu Ng ,  Tram Thi Mai Nguyen

IPC分类号： G06F12/04 ,  G06F3/06 ,  G06F12/02 ,  G11B20/00

CPC分类号： G06F3/0601 ,  G06F12/023 ,  G06F2003/0697 ,  G06F2212/401

摘要： A constant size storage can be managed to preserve locality of referencing where it is partitioned into linear addressable storage space for compressed symbol strings and a linked list addressable space for overflowing portions of each compressed string, a token to the overflow being embedded in the linear address. The linear space is readjusted periodically in a direction so as to maintain the amount of available overflow within to lie within a certain range of current usage. Changes in compression statistics result in changing overflow usage requiring readjustment to minimize internal fragmentation etc.

摘要翻译： 可以管理恒定大小的存储以保留引用的位置，其被分割成用于压缩符号串的线性可寻址存储空间和用于每个压缩字符串的溢出部分的链接列表可寻址空间，将溢出的令牌嵌入到线性地址 。 沿着一个方向周期性地重新调整线性空间，以便将可用溢出量保持在当前使用的一定范围内。 压缩统计数据的变化导致需要重新调整的溢出使用情况发生变化，以尽量减少内部碎片等。

公开(公告)号：US5525982A

公开(公告)日：1996-06-11

申请号：US228321

申请日：1994-04-15

申请人： Joe-Ming Cheng ,  Yancy Cheng

发明人： Joe-Ming Cheng ,  Yancy Cheng

IPC分类号： G06F5/00 ,  G06T9/00 ,  H03M7/30 ,  H03M7/46

CPC分类号： H03M7/3086 ,  G06T9/005

摘要： A method and means for ascertaining maximal length pattern matches of K characters per cycle between character strings in a reduced amount of time using a pipeline like concurrent dataflow model in which a recursive exhaustive greedy comparison matching between the strings in consistent direction yields a parsing of the longest matches, the recursion being constrained by relations among K, the match length L, and a tracking variable J, said constraints governing further recursions ascertaining prefix extensions from one string to another and any intra-string pattern matches. Embodiments processing K equal to one, two, or three characters at a time are disclosed.

摘要翻译： 一种方法和装置，用于使用诸如并行数据流模型的流水线在缩短的时间量之间确定字符串之间的每个周期的K个字符的最大长度模式匹配，其中在一致方向上的串之间的递归穷举贪婪比较匹配产生解析 最长匹配，递归由K之间的关系，匹配长度L和跟踪变量J约束，所述约束控制进一步的递归，确定从一个字符串到另一个字符串的前缀扩展，以及任何字符串内模式匹配。 公开了一次处理K等于一个，两个或三个字符的实施例。