公开(公告)号：US3701108A

公开(公告)日：1972-10-24

申请号：US3701108D

申请日：1970-10-30

Applicant: IBM

Inventor： LOH LOUIS S ,  MOMMENS JACQUES H ,  RAVIV JOSEF

IPC: H03M5/00 ,  H03M7/42 ,  G06F5/00

CPC classification number: H03M7/42 ,  H03M5/00

Abstract: A processor for encoding fixed-length code words into variablelength code words and for decoding variable-length code words into fixed-length code words. The fixed-length code words are assigned to a number of groups and one of several possible coding sets determined by the probability of each word occurring after a preceding word. Each of the fixed-length code words is stored in a first associative memory unit along with its group number, its coding set assignment and a number of addresses arranged in groups. An input fixed-length code word is compared in the memory and will match the corresponding fixed-length stored word. One of the addresses is read out of the memory. The particular group from which the address is read out is determined by the group number of the previously received fixed-length code word. The selected address that is read out and the coding set membership, number of the previous word is entered into a second associative memory containing all the addresses arranged in several coding sets along with the variable-length code words. A match in the second memory unit on an address and a coding set number produces a variable-length code word for the input fixed-length code word. The first memory unit also provides the group number and coding set number for the next input fixed-length code word to be encoded. Decoding is performed in a similar but reverse manner starting with the variable-length coded data being entered into the second memory.

Abstract translation: 用于将固定长度码字编码成可变长度码字并用于将可变长度码字解码为固定长度码字的处理器。 固定长度码字被分配给多个组，并且由在前一个单词之后出现的每个单词的概率确定的几个可能的编码集之一被分配。 每个固定长度码字与其组号，其编码集分配和多个地址排列地存储在第一关联存储器单元中。 输入固定长度码字在存储器中进行比较，并与相应的固定长度存储字匹配。 其中一个地址从内存中读出。 读出地址的特定组由先前接收的固定长度码字的组号决定。 读出的所选择的地址和编码集隶属度，前一个字的数字被输入到包含与可变长度码字一起排列在多个编码集中的所有地址的第二关联存储器中。 第二存储单元中的地址和编码集号的匹配产生用于输入固定长度码字的可变长度码字。 第一存储器单元还为要编码的下一个输入固定长度代码字提供组编号和编码组编号。 以可变长度编码数据输入到第二存储器中，以相似但相反的方式进行解码。

公开(公告)号：US3694813A

公开(公告)日：1972-09-26

申请号：US3694813D

申请日：1970-10-30

Applicant: IBM

Inventor： LOH LOUIS S ,  MOMMENS JACQUES H ,  RAVIV JOSEF

IPC: G06F17/18 ,  H03M7/42 ,  G11B13/00 ,  G06F7/00

CPC classification number: G06F17/18 ,  H03M7/42

Abstract: The present invention relates to a method practiceable on a general purpose electronic computer for statistically analyzing a data set and for producing a set of encoding and decoding (E/D) tables for achieving compaction of the original data set utilizing a variable length code. The method disclosed may operate under constraints of available core, desired compaction rate and speed of compaction/decompaction to produce differing sets of encoding/decoding tables depending upon the constraints imposed. The method would most normally be provided and utilized as a software package wherein the primary inputs are the data set itself and the above enumerated constraints. By utilizing a variable-length code wherein the code assignment is dependent upon the characteristic of preceding data good compaction rates may be achieved utilizing reasonable amounts of memory for the E/D tables. The method comprises three principle steps. The first is the construction of a matrix showing the probability of occurrence of every member of the data set with respect to the immediately preceding member. The second step comprises grouping various rows or columns of this matrix having similar probabilities of occurrence, the third step comprises a reordering of all of the previously grouped rows or columns and finally a second clustering into coding sets may be performed.

Abstract translation: 本发明涉及一种在通用电子计算机上可行的方法，用于对数据集进行统计分析，并用于产生用于利用可变长度码来压缩原始数据集的编码和解码（E / D）表。 所公开的方法可以在可用核心，期望的压缩速率和压缩/解压缩的约束条件下操作，以根据施加的约束产生不同的编码/解码表。 该方法通常将被提供和用作软件包，其中主要输入是数据集本身和上述列举的约束。 通过利用可变长度代码，其中代码分配取决于先前数据的特性，可以利用用于E / D表的合理数量的存储器来实现良好的压缩率。

公开(公告)号：US3701111A

公开(公告)日：1972-10-24

申请号：US3701111D

申请日：1971-02-08

Applicant: IBM

Inventor： COCKE JOHN ,  MOMMENS JACQUES H ,  RAVIV JOSEF

IPC: H03M7/40 ,  H03M7/42 ,  G06F7/00

CPC classification number: H03M7/4025 ,  H03M7/425

Abstract: This code conversion method enables data which has been coded in the form of variable-length bit strings for data compaction purposes to be processed by hardware units of conventional design that handle data in the form of fixed-length bit strings. The coding scheme is such that in the bit string of each variablelength code whose length exceeds a certain fixed number of bits N, the first N bits constitute a ''''length prefix'''' which uniquely designates the code length. This N-bit prefix is decoded by a first decoding table to give a base address in a second decoding table. The remaining bits of the variable-length code, whose number is known from the length prefix, then are decoded to give a displacement value relative to the base address for locating the address at which the decoded fixed-length word is found. Concurrently with the execution of this second decoding step, the first step in the decoding of the next variable-length code is performed. If a variable-length code does not have more than N bits, it is decoded in one step by the first decoding table, which stores the decoded word at every address therein which may be designated by all possible N-bit combinations containing the aforesaid variable-length code as their leading portion. A length indication read out of the first table then shifts the address register contents by an appropriate amount to bring the next succeeding variable-length code into the leading position therein.

Abstract translation: 该代码转换方法使得以用于数据压缩目的的可变长度比特串形式的数据能够以处理固定长度比特串形式的数据的常规设计的硬件单元来处理。 编码方案是这样的，即在长度超过某个固定数量的比特数N的每个可变长度码的比特串中，前N个比特构成唯一地指定码长的“长度前缀”。 该N比特前缀由第一解码表解码，以在第二解码表中给出基地址。 从长度前缀知道其可编号码的其余位然后被解码，以给出相对于基址的位移值，用于定位找到解码的固定长度字的地址。 与第二解码步骤的执行同时执行下一个可变长度码的解码的第一步骤。 如果可变长度码不超过N位，则通过第一解码表在一个步骤中解码，该第一解码表将解码字存储在其中可以由包含上述变量的所有可能的N位组合指定的每个地址 长度代码作为其主要部分。 从第一表读出的长度指示然后将地址寄存器内容移动适当的量，以使下一个后续的可变长度代码进入其中的前导位置。

公开(公告)号：US3614736A

公开(公告)日：1971-10-19

申请号：US3614736D

申请日：1968-05-21

Applicant: IBM

Inventor： MCLAUGHLIN JOHN A ,  RAVIV JOSEF

IPC: G06K9/80 ,  G06K9/08

CPC classification number: G06K9/80 ,  G06K9/52 ,  G06K9/68

Abstract: A pattern recognition system is disclosed which will recognize patterns irrespective of their translation rotation or scale change. Input data may be provided by a scanner or other suitable data source. Means for calculating the center of gravity, or alternatively the autocorrelation function are provided which can be employed; and then the data can be transformed for an actual or simulated annular or equivalently radial scan, with exponential spacing along radii. Alternatively, a straightforward raster scan may be employed for recognition which is invarient to translation only. The output is then processed in means for cross correlating with known patterns. The result is preferably raised to the Nth power and summed. Alternatively, 2 can be raised to the power of the cross correlation times K and summed which is easily done on a digital computer, or finally the result can be subjected to maximum operation. In all cases, the pattern is then processed through corresponding means for normalization including a storage device, a multiplier and a decision function unit. Prior to operation for pattern recognition, the system is operated with the normalization storage connected through an inverter to the output of one of the Nth power, power of 2 or maximum operation units for receiving the appropriately processed data relative to a sample for normalization. Then the appropriate normalization may be supplied for each mode of processing after cross correlation.

公开(公告)号：US3675212A

公开(公告)日：1972-07-04

申请号：US3675212D

申请日：1970-08-10

Applicant: IBM

Inventor： RAVIV JOSEF ,  WESLEY MICHAEL A

IPC: H03M5/00 ,  H03M7/42 ,  G06F5/00 ,  H03K13/00

CPC classification number: H03M7/42 ,  H03M5/00

Abstract: A three-state associative memory is employed as an encodingdecoding instrumentality for making conversions between fixedlength codes and variable-length codes. During the encoding process, associations are performed upon fixed-length codes to find the corresponding variable-length codes. The shorter-length codes are assigned to the most frequently occurring words or bytes for achieving a minimum average code length. The available variable-length codes are stored in a field of the associative memory that has uniform word lengths. Memory cells which are not needed for storing bits of the variable-length codes are set to a ''''don''t care'''' state. During each readout of a variable-length code, a corresponding ''''length'''' value is read out of the memory to indicate the number of valid bits that are to be read serially from the data register, excluding the ''''don''t cares.'''' During the decoding process, the bits of successive variable-length codes are fed serially to an argument register, and as each association is performed upon a variable-length code to find the corresponding fixed-length code, the ''''length'''' field indicates the number of bit positions by which the contents of the argument register are to be shifted for bringing the next variable-length code bit string into registry.

Abstract translation: 采用三状态关联存储器作为在固定长度代码和可变长度代码之间进行转换的编码解码工具。 在编码过程中，以固定长度的代码执行关联，以找到相应的可变长度代码。 较短的代码被分配给最常出现的字或字节，以达到最小的平均代码长度。 可用的可变长度代码存储在具有统一字长的关联存储器的字段中。 将存储可变长度代码的位不需要的存储单元设置为“无关”状态。 在可变长度代码的每次读出期间，从存储器中读出对应的“长度”值，以指示要从数据寄存器串行读取的有效位的数量，不包括“不关心”。 在解码过程中，连续的可变长度码的位被串行地馈送到自变量寄存器，并且当根据可变长度代码执行每个关联以找到对应的固定长度代码时，“长度”字段表示数字 的比特位置，通过该比特位置，参数寄存器的内容将被移位，以使下一个可变长度代码位串进入注册表。

公开(公告)号：US3675211A

公开(公告)日：1972-07-04

申请号：US3675211D

申请日：1970-09-08

Applicant: IBM

Inventor： RAVIV JOSEF

IPC: H03M5/00 ,  H03M7/42 ,  G06F5/00

CPC classification number: H03M5/00 ,  H03M7/42

Abstract: A three-state associative memory is employed as an encodingdecoding instrumentality for making conversions between fixedlength codes and variable-length codes. The available variablelength codes are stored in a field of the associative memory that has uniform word lengths. Memory cells which are not needed for storing bits of the variable-length codes are set to a ''''don''t care'''' state. Fixed-length codes and code length indications corresponding to these stored variable-length codes are stored in other fields of the associative memory. A ''''COPY'''' feature enables the system to function with an associative memory of relatively small size which performs normal encoding and decoding operations for the more frequently occurring codes, thereby achieving a high degree of data compaction, while the less frequently occurring codes are handled in a manner that does not achieve such compaction but requires much less memory. Encoding in the ''''COPY'''' mode of operation involves appending the fixedlength code word to a special COPY code which is the same for all code words in this category. Decoding a combination code word of this kind involves discarding the COPY code portion and directly utilizing the remainder as the decoded fixed-length code word. Only one line of stored data is needed in the associative memory to handle all code words which use the COPY code.

Abstract translation: 采用三状态关联存储器作为在固定长度代码和可变长度代码之间进行转换的编码解码工具。 可用的可变长度代码存储在具有统一字长的关联存储器的字段中。 将存储可变长度代码的位不需要的存储单元设置为“无关”状态。 对应于这些存储的可变长度代码的固定长度代码和代码长度指示被存储在关联存储器的其他字段中。 “COPY”功能使得系统能够使用相对较小尺寸的关联存储器，其对于更频繁出现的代码进行正常的编码和解码操作，从而实现高度的数据压缩，而较少出现的代码被处理在 这种方式不能实现这种压实，但需要更少的记忆。 在“COPY”操作模式下的编码涉及将固定长度码字附加到与该类别中的所有码字相同的特殊COPY码。 解码这种组合码字涉及丢弃COPY码部分，并直接利用余数作为解码的固定长度码字。 在关联存储器中只需要一行存储的数据来处理使用COPY代码的所有代码字。