Method of and apparatus for decoding variable-length codes having length-indicating prefixes

Claim 2

A code conversion method whereby data encoded as bit strings of variable length can be utilized in a data processing system having memory units and registers which are adapted to handle data encoded as bit strings of fixed length, said method comprising the steps of: a. serially entering the leading bits of an input bit stream containing successive variable-length codes into a first one of said registers until the number of such entered bits equals a fixed number: b. storing in a memory unit, at each of the addresses therein specified by the various combinations of bits that may be entered into said first register, the following interrelated items of information: b1. a fixed-length code corresponding to the first variablelength code or portion of such code which is defined upon entry of the respective bit combination denoting that address into said first register, and b2. associated information which is related to the number of bits in said variable-length code; c. reading out of said memory unit to a second register, for use in a subsequent portion of said data processing system, the fixed-length code (b1) which is addressed by the bit combination currently stored in said first register, along with its associated information (b2); d. shifting the contents of said first register serially through a number of bit positions determined by said associated information; and e. repeating steps (c) and (d) as needed for enabling the information represented by the succeeding variable-length codes in said bit stream to be processed by said system.

Claim 3

A method as set forth in claim 1 wherein said associated information (b2) is related to the number of significant bits contained in each variable-length code whose length does not exceed said fixed number, and step d involves shifting the contents of said first register by the corresponding number of bit positions.

Claim 4

A method as set forth in claim 2 wherein the fixed-length code entered into said second register in step (c) constitutes the decoded equivalent of the variable-length code specified in step b1.

Claim 5

A method as set forth in claim 1 wherein said associated information (b2) indicates whether the respective variable-length code is or is not longer than said fixed number, and step (d) involves shifting the contents of said first register by said fixed number of bit positions in each case where the respective variable-length code is longer than said fixed number.

Claim 6

A method as set forth in claim 4 wherein the fixed-length code entered into said second register in step (c) thereafter is entered into a third register to form at least a portion of an address for locating within a second memory unit the decoded equivalent of the variable-length code specified in step (b1).

Claim 9

A method as set forth in claim 6 wherein the information (c) stored in said first memory unit at the address therein specified by each one of said length prefixes includes additional information designating the number of bits in excess of N which are represented by that length prefix, and step (g) is effective to cause the number of bits thus designated by the current length prefix to be entered from said bit stream into said second address register.

Claim 10

A code conversion method whereby data encoded as bit strings of variable length can be utilized in a data processing system having memory units and registers which are adapted to handle data encoded as bit strings of fixed length, said method comprising the steps of: a. serially entering the leading bits of an input bit stream containing successive variable-length codes into a first one of said registers until the number of such entered bits equals a fixed number; b. storing in a first memory unit, at each of the addresses therein specified by the various combinations of bits that may be entered into said first register, the following interrelated items of information: b1. a fixed-length code corresponding to the first variable-length code or portion of such code which is defined upon entry of the respective bit combination into said first register, and b2. associated information which is related to the number of bits in said variable-length code; c. storing in a second memory unit, at addressable locations therein which are determined in part by those fixed-length codes in said first memory unit that correspond to variable-length codes which contain more than said fixed number of bits, the fixed-length codes constituting the respective decoded equivalents of such variable-length codes; d. reading out of said first memory unit to a second register the fixed-length code (b1) which is addressed by the bit combination currently stored in said first register, along with its associated information (b2); e. performing one of the following two actions according to the contents of said associated information: e1. if said associated information denotes that the variable-length code specified in step (b1) does not contain more than said fixed number of bits, then read out the contents of said second register as the decoded equivalent of such variable-length code, and thereafter shift the contents of said first register by a number of bit positions equal to the length of such variable-length code; or e2. if said associated information denotes that the variable-length code specified in step (b1) contains more than said fixed number of bits, then transfer the fixed-length code from said second register to a third register, also enter into said third register those bits which constitute the excess portion of said variable-length code, thereby to form a new address containing such bits in combination with at least a portion of said transferred code, then shift the contents of said first register by a number of bit positions equalling said fixed number, and read out of said second memory unit the fixed-length code corresponding to said new address as the decoded equivalent of said variable-length code; and f. repeating steps (d) and (e) as needed for enabling the information represented by the succeeding variable-length codes in said bit stream to be processed by said system.

Claim 11

A code conversion method whereby data encoded as bit strings of variable length can be utilized in a data processing system having memory units and registers which are adapted to handle data encoded as bit strings of fixed length, said method comprising the steps of: a. serially entering the leading bits of an input bit stream containing successive variable-length codes into a first one of said registers until the number of such entered bits equals a fixed number; b. storing in a first memory unit, at each of the addresses therein specified by the various combinations of bits that may be entered into said first register, the following interrelated items of information: b1. a fixed-length code corresponding to the first variable-length code or portion of such code which is defined upon entry of the respective bit combination into said first register, and b2. associated information which is related to the number of bits in said variable-length code; c. storing in a second memory unit, at addressable locations therein which are determined in part by those fixed-length codes in said first memory unit that correspond to variable-length codes which contain more than said fixed number of bits, the fixed-length codes constituting the respective decoded equivalents of such variable-length codes; d. reading out of said first memory unit to a second register the fixed-length code (b1) which is addressed by the bit combination currently stored in said first register, along with its associated information (b2); e. performing one of the following two actions according to the contents of said associated information: e1. if said associated information denotes that the variable-length code specified in step (b1) does not contain more than said fixed number of bits, then read out the contents of said second register as the decoded equivalent of such variable-length code, and thereafter shift the contents of said first register by a number of bit positions equal to the length of such variable-length code; or e2. if said associated information denotes that the variable-length code specified in step (b1) contains more than said fixed number of bits, then transfer the fixed-length code from said second register to a third register, also enter into said third register those bits which constitute the excess portion of said variable-length code, thereby to form a new address containing such bits in combination with at least a portion of said transferred code, then shift the contents of said first register by a number of bit positions equalling said fixed number, and read out of said second memory unit the fixed-length code corresponding to said new address as the decoded equivalent of said variable-length code; and f. repeating steps (d) and (e) as needed for enabling the information represented by the succeeding variable-length codes in said bit stream to be processed by said system.

Claim 14

A method as set forth in claim 9 wherein the additional code bits entered into said second address register in step (f) comprise the bits of the current variable-length code exclusive of the N bits stored in said first address register.

Claim 15

A method as set forth in claim 9 wherein the additional code bits entered into said second address register in step (f) comprise the bits of a group code related to the fixed-length code which previously was read out of said second memory unit.

Claim 16

Data processing apparatus for converting data which is in the form of variable-length bit strings into data having the form of fixed-length bit strings, utilizing memory units and registers that are capable of handling fixed-length bit strings only, said apparatus comprising: a. a shiftable address register capable of storing N bits, where N is a fixed integer; b. means for entering variable-length code bits serially into said address register, to the N-bit capacity of said register; c. a memory unit having addresses therein corresponding respectively to the various combinations of N bits that may be stored in said address register and adapted to store at each such address the following interrelated items of information: c1. a fixed-lengTh code corresponding to the first variable-length code or portion of such code which is defined upon entry of the respective N-bit combination denoting that address into said address register, and c2. associated information which is related to the number of bits in said variable-length code; d. means for reading out of said memory unit the fixed-length code (c1) and associated information (c2) which are addressed by the N-bit combination currently stored in said address register; and e. means controlled by said reading means (d) for shifting the contents of said address register serially through a number of bit positions determined by said associated information (c2).

Claim 17

Data processing apparatus for converting data which is in the form of variable-length bit strings into data having the form of fixed-length bit strings, utilizing memory units and registers that are capable of handling fixed-length bit strings only, said apparatus comprising: a. a shiftable address register capable of storing N bits, where N is a fixed integer; b. means for entering variable-length code bits serially into said address register, to the N-bit capacity of said register; c. a memory unit having addresses therein corresponding respectively to the various combinations of N bits that may be stored in said address register and adapted to store at each such address the following interrelated items of information: c1. a fixed-lengTh code corresponding to the first variable-length code or portion of such code which is defined upon entry of the respective N-bit combination denoting that address into said address register, and c2. associated information which is related to the number of bits in said variable-length code; d. means for reading out of said memory unit the fixed-length code (c1) and associated information (c2) which are addressed by the N-bit combination currently stored in said address register; and e. means controlled by said reading means (d) for shifting the contents of said address register serially through a number of bit positions determined by said associated information (c2).

Claim 18

Apparatus as set forth in claim 12 wherein said shifting means (e) is effective whenever said associated information (c2) indicates that the current variable-length code does not exceed N bits in length to shift the contents of said address register by the number of bits in said variable-length code.

Claim 19

Apparatus as set forth in claim 12 wherein said shifting means (e) is effective whenever said associated information (c2) indicates that the current variable-length code exceeds N bits in length to shift the contents of said address register by N bits.

Claim 20

Apparatus for processing data which is encoded in the form of variable-length bit strings wherein the first N bits of any variable-length code exceeding N bits in length constitutes a length prefix uniquely identifying that particular code length, N being a fixed integer, said apparatus comprising: a. a shiftable first address register capable of storing N bits; b. means for entering variable-length code bits serially into said first address register, to the N-bit capacity of said register; c. a first memory unit having addresses therein corresponding respectively to the various combinations of N bits that may be stored in said first address register and adapted to store at each such address the following interrelated items of information: c1. a fixed-length code corresponding to the first variable-length code or N-bit portion of such code which is defined upon entry of the respective N-bit combination into said first address register, and c2. associated information which is related to the number of bits in said variable-length code, such information indicating, in the case of a code exceeding N bits in length, the number of bits which are represented by the respective N-bit prefix; d. means for reading out of said first memory unit the fixed-length code (c1) and associated information (c2) which are addressed by the N-bit combination currently stored in said first address register; e. means controlled by said reading means and effective when information (c2) indicates that the related variable-length code does not exceed N bits in length to shift the contents of said first address register by the number of bits contained within that variable-length code; f. a second shiftable address register capable of storing M bits, where M is a fixed integer; g. means controlled by said reading means (d) and effective when information (c2) indicates that the related variable-length code exceeds N bits in length to transfer the fixed-length code (c1) to said second address register and also effective to enter into said second address register the remaining bits of the current variable-length code, the number of such bits being indicated by said information (c2), thereby to form a combined M-bit address, and being further effective to shift the contents of said first address register by N bits; h. a second memory unit having addressable locations therein corresponding respectively to the various M-bit combinations that may be stored in said second address register and adapted to store a distinctive fixed-length code at each such location; and i. means effective when said information (c2) indicates that the related variable-length code exceeds N bits in length for reading out of said second memory unit the fixed-length code addressed by the M-bit combination currently stored in said second address register.

Claim 21

Apparatus for processing data which is encoded in the form of variable-length bit strings wherein the first N bits of any variable-length code exceeding N bits in length constitutes a length prefix uniquely identifying that particular code length, N being a fixed integer, said apparatus comprising: a. a shiftable first address register capable of storing N bits; b. means for entering variable-length code bits serially into said first address register, to the N-bit capacity of said register; c. a first memory unit having addresses therein corresponding respectively to the various combinations of N bits that may be stored in said first address register and adapted to store at each such address the following interrelated items of information: c1. a fixed-length code corresponding to the first variable-length code or N-bit portion of such code which is defined upon entry of the respective N-bit combination into said first address register, and c2. associated information which is related to the number of bits in said variable-length code, such information indicating, in the case of a code exceeding N bits in length, the number of bits which are represented by the respective N-bit prefix; d. means for reading out of said first memory unit the fixed-length code (c1) and associated information (c2) which are addressed by the N-bit combination currently stored in said first address register; e. means controlled by said reading means and effective when information (c2) indicates that the related variable-length code does not exceed N bits in length to shift the contents of said first address register by the number of bits contained within that variable-length code; f. a second shiftable address register capable of storing M bits, where M is a fixed integer; g. means controlled by said reading means (d) and effective when information (c2) indicates that the related variable-length code exceeds N bits in length to transfer the fixed-length code (c1) to said second address register and also effective to enter into said second address register the remaining bits of the current variable-length code, the number of such bits being indicated by said information (c2), thereby to form a combined M-bit address, and being further effective to shift the contents of said first address register by N bits; h. a second memory unit having addressable locations therein corresponding respectively to the various M-bit combinations that may be stored in said second address register and adapted to store a distinctive fixed-length code at each such location; and i. means effective when said information (c2) indicates that the related variable-length code exceeds N bits in length for reading out of said second memory unit the fixed-length code addressed by the M-bit combination currently stored in said second address register.

Claim 22

Apparatus of the kind set forth in claim 15, further comprising the following elements: j. a third address register; k. a third memory unit for storing fixed-length codes at locations therein addressable by the contents of said third address register; l. means for reading out of said third memory unit the fixed-length code addressed by the contents of said third address register; m. means for converting each of the fixed-length codes read out by reading means (l) into a selected one of several group codes; and n. means for entering into said third address register the group code corresponding to the fixed-length code previously read out of said third memory unit in combination with one of the following: n1. the fixed-length code (c1) read out of said first memory unit by said reading means (d), if the length of the current variable-length code does not exceed N bits, or n2. the fixed-length code read out of said second memory unit by said reading means (i), if the length of the current variable-length code exceeds N bits; whereby said reading means (l) is effective to read out of said third memory unit a fixed-length code the identity of which is determined in part by the current variable-length code and in part by the preceding variable-length code.

Claim 23

Apparatus for converting successive variable-length codes whose bits are contained in a serial bit stream into corresponding fixed-length codes, said apparatus comprising: a. a first address register capable of storing N bits, where N is a fixed integer; b. a first memory unit for storing a first set of fixed-length codes at addresses therein which may be specified by the N-bit combination stored in said first address register; c. means for entering bits from said bit stream into said first address register; d. means for reading out of said first memory unit the fixed-length code in said first set whose address is specified by the N-bit combination in said first address register; e. a second address register capable of storing M bits, where M is a fixed number; f. a second memory unit for storing a second set of fixed-length codes at addresses therein which may be specified by the M-bit combination stored in said second address register; g. data entry means controlled by said reading means (d) for causing the fixed-length code read out of said first memory unit to be entered into said second address register as a constituent of an M-bit address to be formed in said second address register; h. other data entry means for entering into said second address register, as another constituent of said M-bit address, a group of additional selected code bits; and i. means for reading out of said second memory unit the fixed-length code in said second set corresponding to the M-bit address thus formed in said second address register.

Claim 24

Apparatus for converting successive variable-length codes whose bits are contained in a serial bit stream into corresponding fixed-length codes, said apparatus comprising: a. a first address register capable of storing N bits, where N is a fixed integer; b. a first memory unit for storing a first set of fixed-length codes at addresses therein which may be specified by the N-bit combination stored in said first address register; c. means for entering bits from said bit stream into said first address register; d. means for reading out of said first memory unit the fixed-length code in said first set whose address is specified by the N-bit combination in said first address register; e. a second address register capable of storing M bits, where M is a fixed number; f. a second memory unit for storing a second set of fixed-length codes at addresses therein which may be specified by the M-bit combination stored in said second address register; g. data entry means controlled by said reading means (d) for causing the fixed-length code read out of said first memory unit to be entered into said second address register as a constituent of an M-bit address to be formed in said second address register; h. other data entry means for entering into said second address register, as another constituent of said M-bit address, a group of additional selected code bits; and i. means for reading out of said second memory unit the fixed-length code in said second set corresponding to the M-bit address thus formed in said second address register.

Claim 25

Apparatus as set forth in claim 17 wherein said other data entry means (h) causes the remaining bits of the current variable-length code, excluding the N bits already entered in said first address register, to be entered into said second address register.

Claim 26

Apparatus as set forth in claim 17 which includes the following additional feature: j. encoding means controlled by said reading means (i) for generating a group code corresponding to each fixed-length code which is read out of said second memory unit; said other data entry means (h) being effective to enter the bits of each group code thus formed into said second address register as the other constituent of the next M-bit address which is formed therein.

Claim 27

Apparatus for processing data which is encoded in the form of vAriable-length bit strings wherein the first N bits of any variable-length code exceeding N bits in length constitutes a length prefix uniquely identifying that particular code length, N being a fixed integer, said apparatus comprising: a. a primary processor including the following elements: a1. a first address register capable of storing N bits, a2. means for entering variable-length code bits into said first address register, a3. a first memory unit for storing at various addressable locations therein fixed-length codes which respectively correspond to the various N-bit addresses that may be stored in said first address register, a4. a first data register, and a5. reading means for causing the fixed-length code which is addressed in said first memory unit by the N-bit address currently stored in said first address register to be entered into said first data register; b. a secondary processor including the following elements: b1. a second address register, b2. means for entering into said second address register the fixed-length code bits stored in said first data register together with variable-length code bits that have not been entered into said first address register, b3. a second memory unit for storing at various addressable locations therein fixed-length codes which respectively correspond to the various addresses that may be stored in said second address register, b4. a second data register, and b5. reading means for causing the fixed-length code which is addressed in said second memory unit by the address currently stored in said second address register to be entered into said second data register; and c. control means effective when said entering means (b2) has completed an entry into said second address register, but before said reading means (b5) has effected a corresponding entry into said second data register, to initiate a new operation of said entering means (a2), whereby the operations of said primary and secondary processors are overlapped.

Claim 28

Apparatus for processing data which is encoded in the form of vAriable-length bit strings wherein the first N bits of any variable-length code exceeding N bits in length constitutes a length prefix uniquely identifying that particular code length, N being a fixed integer, said apparatus comprising: a. a primary processor including the following elements: a1. a first address register capable of storing N bits, a2. means for entering variable-length code bits into said first address register, a3. a first memory unit for storing at various addressable locations therein fixed-length codes which respectively correspond to the various N-bit addresses that may be stored in said first address register, a4. a first data register, and a5. reading means for causing the fixed-length code which is addressed in said first memory unit by the N-bit address currently stored in said first address register to be entered into said first data register; b. a secondary processor including the following elements: b1. a second address register, b2. means for entering into said second address register the fixed-length code bits stored in said first data register together with variable-length code bits that have not been entered into said first address register, b3. a second memory unit for storing at various addressable locations therein fixed-length codes which respectively correspond to the various addresses that may be stored in said second address register, b4. a second data register, and b5. reading means for causing the fixed-length code which is addressed in said second memory unit by the address currently stored in said second address register to be entered into said second data register; and c. control means effective when said entering means (b2) has completed an entry into said second address register, but before said reading means (b5) has effected a corresponding entry into said second data register, to initiate a new operation of said entering means (a2), whereby the operations of said primary and secondary processors are overlapped.