Run-length-limited variable-length coding with error propagation limitation

Claim 3

A data procEssing method as set forth in claim 1 wherein the number of shift intervals which elapse between each performance of steps d and e and the next succeeding performance of these steps is determined in each instance by the number of bit positions in the most recently demarcated frame.

Claim 4

A data processing method as set forth in claim 2 wherein the respective groups of bit-storing positions sensed during step b are so located in said device that each such group starts with a position whose relative number within said series of positions is N+i+(i-1) (Z-Y) and ends with a position whose number is Z plus said starting number, where: N is the smallest integer which, when divided by another integer, will yield said fixed ratio, Z and Y, respectively, are the maximum and minimum numbers of consecutive bits each having a given binary value (e.g., 0) in which a valid code word may terminate, and i is a member of a set of integers including 1 and any higher integer having a value such as to define a starting position whose number does not exceed the maximum permissible code word length.

Claim 5

A data processing method as set forth in claim 3 wherein step b involves a logical AND test for each of the sensed groups of bits, the inputs to each such AND test including the inverse of each bit sensed in the Y lowest-numbered positions of that group together with the logical OR of the remaining bits sensed within that group, and step c involves the generation of a satisfaction signal for each group in which said AND test is satisfied.

Claim 6

A data processing method as set forth in claim 1 wherein the particular set of positions selected during each occurrence of step d includes as its highest-numbered position the W''th position of said series, where ''''W'''' is the maximum permissible code word length.

Claim 7

A data processing method as set forth in claim 5 wherein the complete absence of satisfaction signals from the sensed group of positions demarcates a frame of length W.

Claim 10

A data processing method as set forth in claim 7 wherein the number of shift intervals which elapse between each performance of steps e and f and the next succeeding performance of these steps is determined in each instance by the number of bit positions in the most recently demarcated frame.

Claim 11

A data processing method as set forth in claim 7 wherein said encoding step a also imposes run-length-limited constraints upon each code word so that each 1 in said bit stream is separated from the nearest adjacent 1 by a number of 0''s falling within a predetermined range of integers.

Claim 12

A data processing method as set forth in claim 9 wherein said range of integers extends from 1 to 8, inclusive.

Claim 13

A data processing method as set forth in claim 9 wherein said range of integers extends from 2 to 7, inclusive.

Claim 14

Apparatus for encoding original bit strings of variable length into variable-length code words whose respective lengths bear a constant ratio to the lengths of the respective bit strings from which they have been encoded, said apparatus comprising: a. an associative memory containing rows of bit-storing cells, at least some of the cells in each row being of the three-state type, said memory being arranged in three sections, each section including corresponding portions of the various rows of cells, the first of said memory sections containing at least as many cells per row as the maximum number of bits that may exist in any of the variable-length code words and storing in each row thereof the bits of a respective one of said variable-length code words, the second of said memory sections containing at least as many cells per row as the maximum number of bits that may exist in any of the original bit strings from which said variable-length code words are encoded and storing in each row thereof the bits of a respective one of said original bit strings, those cells of said second memory section which do not store bits of such original bit strings being in their ''''don''t care'''' states, the third of said memory sections storing in each row of cells therein a length indication denoting the number of bits in the original bit string which is stored in that same row; b. an argument register of the shift type; c. entry means operable for causing bits of an original bit stream containing a succession of said variable-length bit strings to be serially entered into said argument register and progressively shifted toward a predetermined registration position therein; d. associating means operable for causing the significant bits of the bit pattern currently stored in said argument register to be matched with the significant bits of a corresponding bit string stored in said second memory section; e. a data register of the shift type; f. reading means operable for transferring to said data register the bit pattern which is stored within said first memory section in the same row of cells that contains the matching bit string; g. output means operable for causing bits stored in said data register to be serially read out therefrom as elements of the encoded word which corresponds to the matching bit string; and h. control means responsive to the length indication stored in said third memory section, within the row of cells that contains the matching bit string, for controlling the operations of said output means g and entry means c so that the number of bits serially read out of said data register e following each operation of said reading means f corresponds to said length indication times said constant ratio, and the number of bits serially entered into said argument register b prior to the next operation of said associating means d corresponds to said length indication.

Claim 15

Apparatus for encoding original bit strings of variable length into variable-length code words whose respective lengths bear a constant ratio to the lengths of the respective bit strings from which they have been encoded, said apparatus comprising: a. an associative memory containing rows of bit-storing cells, at least some of the cells in each row being of the three-state type, said memory being arranged in three sections, each section including corresponding portions of the various rows of cells, the first of said memory sections containing at least as many cells per row as the maximum number of bits that may exist in any of the variable-length code words and storing in each row thereof the bits of a respective one of said variable-length code words, the second of said memory sections containing at least as many cells per row as the maximum number of bits that may exist in any of the original bit strings from which said variable-length code words are encoded and storing in each row thereof the bits of a respective one of said original bit strings, those cells of said second memory section which do not store bits of such original bit strings being in their ''''don''t care'''' states, the third of said memory sections storing in each row of cells therein a length indication denoting the number of bits in the original bit string which is stored in that same row; b. an argument register of the shift type; c. entry means operable for causing bits of an original bit stream containing a succession of said variable-length bit strings to be serially entered into said argument register and progressively shifted toward a predetermined registration position therein; d. associating means operable for causing the significant bits of the bit pattern currently stored in said argument register to be matched with the significant bits of a corresponding bit string stored in said second memory section; e. a data register of the shift type; f. reading means operable for transferring to said data register the bit pattern which is stored within said first memory section in the same row of cells that contains the matching bit string; g. output means operable for causing bits stored in said data register to be serially read out therefrom as elements of the encoded word which corresponds to the matching bit string; and h. control means responsive to the length indication stored in said third memory section, within the row of cells that contains the matching bit string, for controlling the operations of said output means g and entry means c so that the number of bits serially read out of said data register e following each operation of said reading means f corresponds to said length indication times said constant ratio, and the number of bits serially entered into said argument register b prior to the next operation of said associating means d corresponds to said length indication.

Claim 16

An encoding apparatus as set forth in claim 12 wherein the cells of each of said rows contained within said first memory section are set so that the code word stored therein terminates in one of a plurality of distinctive word-ending bit sequences, those cells of said first memory section which do not store the bits of such code words being in their ''''DON''t care'''' states.

Claim 17

Encoding apparatus as set forth in claim 13 wherein each word stored in said first memory section is so constituted that each 1 bit read out of said data register e by said output means g is separated from the nearest adjacent 1 bit by a number of 0''s falling within a constrained range of values.

Claim 18

Encoding apparatus as set forth in claim 14 wherein said range of values extends from 1 to 8, inclusive.

Claim 19

Encoding apparatus as set forth in claim 14 wherein said range of values extends from 2 to 7, inclusive.

Claim 20

Apparatus for converting a bit stream containing a succession of variable-length code words into a succession of decoded bit strings whose respective lengths bear a constant ratio to the respective code word lengths, said bit stream being so constituted that each valid code word representation therein terminates in one of a plurality of distinctive word-ending bit sequences, said apparatus comprising: a. an input register of the shift type containing a succession of progressively numbered bit-storing positions and having a framing reference point at the end of a given series of such positions; b. entry means operable at intervals for causing bits from said bit stream to be serially entered into said input register and shifted progressively through said series of positions toward said framing reference point; c. framing decision means for sensing the presence or absence of any of said word-ending bit sequences at each of one or more groups of specially designated positions within said series of positions and for generating a current length representation according to the sensed pattern of such bit sequences, said length representation demarcating a particular set of input register positions preceding to said framing reference point in which the pattern of bits currently to be decoded is assumed to be stored and also denoting the length which the decoded bit string will have; and d. means for decoding the pattern of bits currently stored in said set of positions.

Claim 21

Apparatus for converting a bit stream containing a succession of variable-length code words into a succession of decoded bit strings whose respective lengths bear a constant ratio to the respective code word lengths, said bit stream being so constituted that each valid code word representation therein terminates in one of a plurality of distinctive word-ending bit sequences, said apparatus comprising: a. an input register of the shift type containing a succession of progressively numbered bit-storing positions and having a framing reference point at the end of a given series of such positions; b. entry means operable at intervals for causing bits from said bit stream to be serially entered into said input register and shifted progressively through said series of positions toward said framing reference point; c. framing decision means for sensing the presence or absence of any of said word-ending bit sequences at each of one or more groups of specially designated positions within said series of positions and for generating a current length representation according to the sensed pattern of such bit sequences, said length representation demarcating a particular set of input register positions preceding to said framing reference point in which the pattern of bits currently to be decoded is assumed to be stored and also denoting the length which the decoded bit string will have; and d. means for decoding the pattern of bits currently stored in said set of positions.

Claim 22

Apparatus as set forth in claim 17, further comprising: e. control means responsive to the current length representation generated by said framing decision means c for determining the number of bit entry and shift intervals which shall elapse during operation of said entry means b intermediate the current operation of said decoding means d and the next succeeding operation of said decoding means.

Claim 23

Apparatus as set forth in claim 17 wherein said decoding means d comprises the following elements: d1. an associative memory containing rows of bit-storing cells, at least some of the cells in each row being of the three-state type, said memory including two sections each containing corresponding portions of the various rows of cells, said first memory section having at least as many cells per row as the maximum number of bits that may exist in a valid variable-length code word, those cells in said first memory section that do not store bits of such code words being in their ''''don''t care'''' states, said second memory section having at least as many cells per row as the maximum number of bits that may exist in a decoded bit string; d2. means enabling said memory to perform an association, using as an argument the bit pattern stored within said series of positions in said input register a, to find a matching code word in said first memory section; d3. a data register of the shift type; d4. reading means operable for entering into said data register the bit pattern stored within said second memory section in the same row of cells that contains the matching code word, or a predetermined dummy pattern if no matching code word is found; and d5. output means under the control of said control means e for serially reading out of said data register the number of bits denoted by said current length representation.

Claim 24

Apparatus as Set forth in claim 19 wherein the respective groups of positions sensed by said framing decision means are so located in said input register a that each such group starts with a position whose relative number within said series of positions is N+i+(i-1) (Z-Y) and ends with a position whose number is Z plus said starting number, where: N is the smallest integer which, when divided by another integer, will yield said fixed ratio, Z and Y, respectively, are the maximum and minimum numbers of consecutive bits each having a given binary value (e.g., 0) in which a valid code word may terminate, and i is a member of a set of integers including 1 and any higher integer having a value such as to define a starting position whose number does not exceed the maximum permissible code word length.

Claim 25

Apparatus as set forth in claim 20 wherein said framing decision means c includes, for each of said groups, a respective AND circuit the input to which consists of the inverse of the bit sensed in each of the Y lowest-numbered positions of that group together with the logical OR of the remaining bits sensed in that group, each of said AND circuits generating a satisfaction signal when its test is satisfied, and other logical circuitry for converting the pattern formed by the presence or absence of such satisfaction signals into said length representation.

Claim 26

Apparatus as set forth in claim 21 wherein said other logical circuitry is effective to generate a maximum length representation in response to the complete absence of satisfaction signals from said AND circuits.