公开(公告)号：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位组合指定的每个地址 长度代码作为其主要部分。 从第一表读出的长度指示然后将地址寄存器内容移动适当的量，以使下一个后续的可变长度代码进入其中的前导位置。

公开(公告)号：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表的合理数量的存储器来实现良好的压缩率。

公开(公告)号：CA1030658A

公开(公告)日：1978-05-02

申请号：CA135902

申请日：1972-03-01

Applicant: IBM

Inventor： COCKE JOHN ,  MOMMENS JACQUES H ,  RAVIV JOSEF

IPC: H03M7/40 ,  H03M7/42 ,  H03K13/24

Abstract: This data processing technique utilizes compacted data in the form of variable-length codes having length-representing prefix portions which themselves are variable-length encoded. The relatively small amount of storage needed when such a code format is used enables data to be conveniently encoded and handled as groups of characters rather than as single characters. The variable-length prefixes are decoded by a small, fast, search-only type of associative memory which furnishes a match-indicating signal as an address to another memory having conventional storage elements. The output of the latter may contain a base address in still another memory of conventional type and an indication of how many bits remain in the current variable-length code word. These remaining bits furnish a displacement value which, in combination with the base address, will locate the decoded fixed-length word or character group in the last memory unit. In those instances where the length of the variable-length codes would become excessively long (for the less frequently occurring character groups) the original fixed-length codes are employed, each being preceded by a common "COPY" code. A special decoding procedure is invoked by this copy code.

公开(公告)号：CA972868A

公开(公告)日：1975-08-12

申请号：CA125582

申请日：1971-10-20

Applicant: IBM

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

IPC: H03M5/00 ,  H03M7/42

Abstract: A processor for encoding fixed-length code words into variable-length 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.