Processing of compacted data

Claim 9

A code conversion method as specified in claim 3 which is operable also upon less frequently occurring input code words of the type wherein a prefix common to all such code words is combined with an individual fixed-length code word, the information stored in step (a) and read out in step (b) including an indication as to whether or not the input code word is of this type, said method including the following step as an alternative to steps (c) and (e): f. in the case of each input code word that has said common prefix, reading the remainder of said code word exclusive of said prefix as the output of said code conversion method.

Claim 10

Apparatus for decoding into fixed-length code words a succession of input code words each represented by serially ordered bits, at least some of said input code words being of a type produced by a variable-length encoding process and respectively having variable-length prefixes, each such prefix being unique to a particular code word length, said apparatus comprising: a. an argument register; b. means for entering into said argument register at least that much of the leading portion of an input code word which contains the prefix thereof; c. an associative memory containing stored code words each corresponding uniquely to a respective length indicating prefix, said associative memory being operable in response to the argument stored in said argument register to generate a match-indicating signal distinctively related to the prefix included in said argument; d. a storage unit having word-storing locations therein respectively corresponding to said code-length indicating prefixes and respectively addressable by the match-indicating signals which are generated by said associative memory in response to such prefixes, each of said locations storing a word which contains a base address unique to the respective prefix and other information indicating which, if any, of the bit positions in an input code word of that length is occupied by bits exclusIve of that prefix; e. a data register for storing the base address of the word in said storage unit which is designated by the match-indicating signal from said associative memory; f. means responsive to the other information in said designated word for forming in said data register a new address which is determined in part by said base address and in part by the remainder of the current input code word exclusive of its prefix; g. a memory having storage locations therein which are addressable in accordance with addresses that may be stored in said data register, each such location storing a fixed-length code word corresponding to the input code word that produced the respective address stored in said data register; and h. means for reading from said memory (g), as the decoded output of said apparatus, the fixed-length code word designated by the address stored in said data register.

Claim 11

Apparatus for decoding into fixed-length code words a succession of input code words each represented by serially ordered bits, at least some of said input code words being of a type produced by a variable-length encoding process and respectively having variable-length prefixes, each such prefix being unique to a particular code word length, said apparatus comprising: a. an argument register; b. means for entering into said argument register at least that much of the leading portion of an input code word which contains the prefix thereof; c. an associative memory containing stored code words each corresponding uniquely to a respective length indicating prefix, said associative memory being operable in response to the argument stored in said argument register to generate a match-indicating signal distinctively related to the prefix included in said argument; d. a storage unit having word-storing locations therein respectively corresponding to said code-length indicating prefixes and respectively addressable by the match-indicating signals which are generated by said associative memory in response to such prefixes, each of said locations storing a word which contains a base address unique to the respective prefix and other information indicating which, if any, of the bit positions in an input code word of that length is occupied by bits exclusIve of that prefix; e. a data register for storing the base address of the word in said storage unit which is designated by the match-indicating signal from said associative memory; f. means responsive to the other information in said designated word for forming in said data register a new address which is determined in part by said base address and in part by the remainder of the current input code word exclusive of its prefix; g. a memory having storage locations therein which are addressable in accordance with addresses that may be stored in said data register, each such location storing a fixed-length code word corresponding to the input code word that produced the respective address stored in said data register; and h. means for reading from said memory (g), as the decoded output of said apparatus, the fixed-length code word designated by the address stored in said data register.

Claim 12

Apparatus as set forth in claim 5 which is further adapted to decode input code words of a special type in each of which a bit string of fixed length is appended to a length-indicating prefix that is common to all input code words of that type, the information contained in each of the words stored in storage unit (d) including an indication as to whether or not such word is addressable by said common prefix, said apparatus further including: i. means responsive to an indication that the currently designated word in storage unit (d) is being addressed by said common prefix for causing the fixed-length bit string appended to that prefix to be read out of said apparatus as its decoded output.

Claim 13

Apparatus for decoding into code words of fixed length a succession of input code words at least some of which are of variable length, said variable-length code words respectively having variable-length prefixes each uniquely identifying a particular code word length, none of said prefixes constituting the beginning of a longer prefix, and none of said variable-length code words constituting the beginning of a longer code word, said apparatus comprising: a. an associative memory having rows and columns of bit-storing memory cells, said rows respectively storing the bits of the various prefixes, with the bit in the leading position of each prefix occupying a common registration column, there being at least as many cells in each row as there are bits in the longest prefix, each of said cells being capable of assuming either one of two binary states or else a third state in which its setting is considered to be without binary significance, this third state being assumed by any cell that does not store a prefix bit; b. an argument register for said associative memory having positions therein for storing the respective bits of an argument, with the position at which the leading bit of the argument is stored corresponding to said registration column, said register having a capacity for storing at least the number of bits contained in the longest prefix; c. ingating means operable for causing the bits of a bit stream containing the successive input code words to be serially entered into said argument register; d. shift means operable to shift the bits stored in said argument register progressively through selected numbers of positions in the direction of said leading bit position, with exit from said register being accomplished by any bit when it leaves said leading bit position; e. a readable storage unit controlled by the output of said associative memory, said storage unit containing rows of bit-storage cells, each such row of cells being allocated to a corresponding row of cells in said associative memory and containing cells which store a representation of the respective prefix length, other cells which store a representation indicating the number of remaining bits in any code word of the length denoted by said prefix, and still other cells storing a representation of a base address assigned to code words of that length; f. means for operAting said associative memory to find a match between the prefix currently stored in the leading portion of said argument register and the prefixes stored in the respective rows of said associative memory; g. means for reading out of said storage unit the items of information stored in the row of cells which corresponds to the matching prefix found by said associative memory; h. data registers for respectively storing the prefix length, remainder length and base address read out of said storage unit during each such association; i. means responsive to the setting of said prefix length register to operate said shift means (d) and ingating means (c) for shifting out of said argument register the prefix bits of the current input code word and for entering an equal number of bits into said argument register; j. means responsive to the setting of said remainder length register to operate said shifting means (d) and ingating means (c) for shifting out of said argument register the remaining bits, if any, of the current input code word and entering an equal number of bits into said argument register; k. address forming means operable to form a final address which is determined in part by the initial setting of said base address register and in part by the remainder, if any, which is read out of said argument register by means (j); and l. a decoded word store addressable by the final address formed by means (k) to furnish a fixed-length code word equivalent to the input code word from which said final address was derived.

Claim 14

Apparatus for decoding into code words of fixed length a succession of input code words at least some of which are of variable length, said variable-length code words respectively having variable-length prefixes each uniquely identifying a particular code word length, none of said prefixes constituting the beginning of a longer prefix, and none of said variable-length code words constituting the beginning of a longer code word, said apparatus comprising: a. an associative memory having rows and columns of bit-storing memory cells, said rows respectively storing the bits of the various prefixes, with the bit in the leading position of each prefix occupying a common registration column, there being at least as many cells in each row as there are bits in the longest prefix, each of said cells being capable of assuming either one of two binary states or else a third state in which its setting is considered to be without binary significance, this third state being assumed by any cell that does not store a prefix bit; b. an argument register for said associative memory having positions therein for storing the respective bits of an argument, with the position at which the leading bit of the argument is stored corresponding to said registration column, said register having a capacity for storing at least the number of bits contained in the longest prefix; c. ingating means operable for causing the bits of a bit stream containing the successive input code words to be serially entered into said argument register; d. shift means operable to shift the bits stored in said argument register progressively through selected numbers of positions in the direction of said leading bit position, with exit from said register being accomplished by any bit when it leaves said leading bit position; e. a readable storage unit controlled by the output of said associative memory, said storage unit containing rows of bit-storage cells, each such row of cells being allocated to a corresponding row of cells in said associative memory and containing cells which store a representation of the respective prefix length, other cells which store a representation indicating the number of remaining bits in any code word of the length denoted by said prefix, and still other cells storing a representation of a base address assigned to code words of that length; f. means for operAting said associative memory to find a match between the prefix currently stored in the leading portion of said argument register and the prefixes stored in the respective rows of said associative memory; g. means for reading out of said storage unit the items of information stored in the row of cells which corresponds to the matching prefix found by said associative memory; h. data registers for respectively storing the prefix length, remainder length and base address read out of said storage unit during each such association; i. means responsive to the setting of said prefix length register to operate said shift means (d) and ingating means (c) for shifting out of said argument register the prefix bits of the current input code word and for entering an equal number of bits into said argument register; j. means responsive to the setting of said remainder length register to operate said shifting means (d) and ingating means (c) for shifting out of said argument register the remaining bits, if any, of the current input code word and entering an equal number of bits into said argument register; k. address forming means operable to form a final address which is determined in part by the initial setting of said base address register and in part by the remainder, if any, which is read out of said argument register by means (j); and l. a decoded word store addressable by the final address formed by means (k) to furnish a fixed-length code word equivalent to the input code word from which said final address was derived.