Data compression method and apparatus

Claim 2

Data compression apparatus comprising: a source of binary data providing a data word and an accompanying code word identifying the number of additional data words which are identical within a predefined tolerance with the data word, first logic means responsive to said data word for providing a coded bistable output signal containing transitions between two separately identifiable states of said output signal at the beginning or middle of selected ones of bit cells containing the bits of said data word to thereby code both the binary character of the bit in the selected one of the bit cells and the bit in the bit cell immediately following said selected bit cells, said first logic means responding to those bits in said data word of one binary characterization by providing a transition at the beginning or middle of each corresponding bit cell depending upon whether said corresponding bit cell is immediately followed by a bit cell containing a bit of said one binary characterization or the other binary characterization respectively, whereby the shortest interval between transitions is 1 1/2 bit cells and occurs between a transition at the middle of the bit cell which is followed by a transition at the beginning of a bit cell, redundant word character generating means for generating a three bit cell transitional pattern containing a transition at the beginning of a bit cell followed by a transition at the middle of the next bit cell, control logic means responsive to said code word and the production of a transition by said first logic means for disabling said first logic means and for enabling said character generating means to insert said transition pattern in said output signal delayed from the end of the bit cell immediately following said selected bit cell by one bit cell, if the number of additional data words is one and by 2 bit cells if the number of additional data words is two or more, said character generating means inserting successive transitional patterns delayed from the previous pattern by a minimum of 1 bit cell and a maximum of 3 bit cells until the total number of bit cell delays corresponds to the number of additional data words, said control means disabling said character generating means and enabling said first logic means in response to the insertion of the last of said transitional patterns.

Claim 3

Data compression apparatus comprising: a source of binary data providing a data word and an accompanying code word identifying the number of additional data words which are identical within a predefined tolerance with the data word, clock means for establishing a plurality of bit cell intervals of substantially uniform time durations, first logic means responsive to said clock means and to said data word for providing a coded bistable output signal containing transitions between two separately identifiable states of said output signal at the beginning or middle of selected ones of the bit cells containing the bits of said data word to thereby code both the binary character of the bit and the selected one of the bit cells and the bit in the bit cell immediately following said selected bit cells, said logic means responding to those bits of said data word of one binary characterization by providing a transition at the beginning or middle of each corresponding bit cell depending upon whether said corresponding bit cell is immediately followed by a bit cell containing a bit of said one binary characterization or the other binary characterization, respectively, whereby the shortest interval between transitions is 1 1/2 bit cells and occurs between a transition at the middle of a bit celL which is followed by a transition at the beginning of a bit cell, said first logic means responding to three consecutive bits of uncoded data in said data word of said other binary characterization by providing a transition at the beginning of the bit cell containing the first of said three consecutive bits and at the middle of a bit cell containing the second of the three consecutive bits to thereby code said three consecutive bits whereby the maximum interval between transitions is 4 1/2 bit cells; redundant word character generating means for generating a 3 bit cell transitional pattern containing a transition at the beginning of a bit cell followed by a transition at the middle of the next bit cell; control logic means responsive to said code word and the production of a transition by said first logic means for disabling said first logic means and for enabling said character generating means to insert said transitional pattern in said output signal delayed from the end of the bit cell containing the last bit identified by the transition produced by said first logic means by 1 bit cell if the number of additional data words is one, and by 2 bit cells if the number of additional data words is two or more, said character generating means inserting successive transitional patterns delayed from the previous pattern by a minimum of 1 bit cell and a maximum of three bit cells until the total number of bit cell delays corresponds to the number of additional data words, said control means disabling said character generating means and enabling said first logic means after insertion of the last of said transitional pattern.

Claim 4

Data compression apparatus comprising: a source of binary data providing a data word and an accompanying code word identifying the number of additional data words which are identical within a predefined tolerance with the data word, clock means for establishing a plurality of bit cell intervals of substantially uniform time durations, first logic means responsive to said clock means and to said data word for providing a coded bistable output signal containing transitions between two separately identifiable states of said output signal at the beginning or middle of selected ones of the bit cells containing the bits of said data word to thereby code both the binary character of the bit and the selected one of the bit cells and the bit in the bit cell immediately following said selected bit cells, said logic means responding to those bits of said data word of one binary characterization by providing a transition at the beginning or middle of each corresponding bit cell depending upon whether said corresponding bit cell is immediately followed by a bit cell containing a bit of said one binary characterization or the other binary characterization, respectively, whereby the shortest interval between transitions is 1 1/2 bit cells and occurs between a transition at the middle of a bit celL which is followed by a transition at the beginning of a bit cell, said first logic means responding to three consecutive bits of uncoded data in said data word of said other binary characterization by providing a transition at the beginning of the bit cell containing the first of said three consecutive bits and at the middle of a bit cell containing the second of the three consecutive bits to thereby code said three consecutive bits whereby the maximum interval between transitions is 4 1/2 bit cells; redundant word character generating means for generating a 3 bit cell transitional pattern containing a transition at the beginning of a bit cell followed by a transition at the middle of the next bit cell; control logic means responsive to said code word and the production of a transition by said first logic means for disabling said first logic means and for enabling said character generating means to insert said transitional pattern in said output signal delayed from the end of the bit cell containing the last bit identified by the transition produced by said first logic means by 1 bit cell if the number of additional data words is one, and by 2 bit cells if the number of additional data words is two or more, said character generating means inserting successive transitional patterns delayed from the previous pattern by a minimum of 1 bit cell and a maximum of three bit cells until the total number of bit cell delays corresponds to the number of additional data words, said control means disabling said character generating means and enabling said first logic means after insertion of the last of said transitional pattern.

Claim 5

Apparatus for decoding a bilevel signal containing transitions at the beginning or middle of selected ones of the succession of arbitrarily defined bit cell intervals comprising: formulation register means; first logic means for detecting the occurrence of a pair of transitions in said signal during a 3 bit cell interval, the first transition of which occurs at the beginning of the first bit cell of the interval and the second of which occurs at the middle of the second bit cell of the interval; second logic means responsive to the detection of the remaining transitions in said signal for entering a binary 1 in said register means during the bit cell interval containing the transition and for entering a binary 1 or a binary 0 during the following bit cell interval depending upon whether the transition occurs at the beginning or middle of the bit cell; third logic means responsive to the detection of those of said pairs of said transitions the first of which occurs within 2 bit cells following one of said remaining transitions for entering the three bit configuration 000 in said register means; means responsive to the remaining ones of said pairs of transitions during a predetermined number of bit cells constituting the length of a data word, the number of bit cell intervals by which the first of the pair of transitions of said remaining ones exceed said 2 bit cell interval and for detecting the number of bit cell intervals between successive ones of the 3 bit cell intervals containing said remaining ones of said pairs of transitions; and means for storing the data entered into said register means and the associated number of accumulated bit cell intervals.

Claim 6

Apparatus for decoding a bilevel signal containing transitions at the beginning or middle of selected ones of the succession of arbitrarily defined bit cell intervals comprising: formulation register means; first logic means for detecting the occurrence of a pair of transitions in said signal during a 3 bit cell interval, the first transition of which occurs at the beginning of the first bit cell of the interval and the second of which occurs at the middle of the second bit cell of the interval; second logic means responsive to the detection of the remaining transitions in said signal for entering a binary 1 in said register means during the bit cell interval containing the transition and for entering a binary 1 or a binary 0 during the following bit cell interval depending upon whether the transition occurs at the beginning or middle of the bit cell; third logic means responsive to the detection of those of said pairs of said transitions the first of which occurs within 2 bit cells following one of said remaining transitions for entering the three bit configuration 000 in said register means; means responsive to the remaining ones of said pairs of transitions during a predetermined number of bit cells constituting the length of a data word, the number of bit cell intervals by which the first of the pair of transitions of said remaining ones exceed said 2 bit cell interval and for detecting the number of bit cell intervals between successive ones of the 3 bit cell intervals containing said remaining ones of said pairs of transitions; and means for storing the data entered into said register means and the associated number of accumulated bit cell intervals.

Claim 7

Data compression apparatus for generating a bilevel signal which is suitable for transmitting through or recording on a communication medium the bilevel signal being divided into a plurality of bit cells of substantially equal time duration and containing transitions separated by a minimum of 1 1/2 bit cells and a maximum of 4 1/2 bit cells, said apparatus comprising: a source of binary data for providing data words and an accompanying code word identifying a number of additional data words which are identical within a predefined tolerance with the data wOrd; encoder means including bit pair comparator means responsive to adjacent uncoded bits of a data word, said bit pair comparator means responsive to a pair of adjacent bits which have not previously been encoded and which form a first of the four possible two bit configurations by producing a toggle pulse at the beginning of the bit cell containing the first bit of said first two bit configuration, said bit pair comparator means responsive to a pair of adjacent bits which have not previously been encoded and which form a second of the four possible two bit configuration, the second bit of which is the complement of the second bit of said one of the four possible two bit configurations, by producing a toggle pulse at the middle of the bit cell containing the first bit of said second two bit configuration whereby each toggle pulse from said bit pair comparator means identifies two bits of binary data and toggle pulses are separated by a minimum of 1 1/2 bit cells, said encoder means including additional comparator means responsive to three consecutive bits of said data word which have not previously been encoded, each bit of which is the complement of the second bit of said first two bit configuration by producing a first toggle pulse at the beginning of the bit cell containing the first of said three consecutive bits and a second toggle pulse at the middle of the bit cell containing the second of said three consecutive bits, whereby the maximum interval between a toggle pulse produced by said bit pair comparator means and a toggle pulse produced by said additional comparator means is 4 1/2 bit cells, redundant word character generator means responsive to a code word of one or more for disabling said encoder means in response to the first toggle pulse from said bit pair comparator means on said second toggle pulse from said additional comparator means and for subsequently generating one or more pairs of toggle pulses, the first of which occurs at the beginning of a bit cell and the second of which occurs at the middle of the following bit cell, the first toggle pulse of the first of said pair of toggle pulses being delayed from the previous toggle pulse by at least 1 1/2 bit cells plus 1 bit cell if said code word is one and 2 bit cells if said code word is two or more, the first toggle pulse of subsequent ones of said pairs of toggle pulses being delayed from the second of a previous pair of toggle pulses by 1 1/2 bit cells plus a minimum of 1 cell and a maximum of 3 bit cells until the total of the added bit cell delays equal the code word number; means including a toggle device responsive to a toggle pulse from said encoder means or said redundant word character generating means for producing said bilevel signal, said redundant word character generating means enabling said decoder means 1 1/2 bit cells after the second of the final pair of toggle pulses.

Claim 8

Data compression apparatus for generating a bilevel signal which is suitable for transmitting through or recording on a communication medium the bilevel signal being divided into a plurality of bit cells of substantially equal time duration and containing transitions separated by a minimum of 1 1/2 bit cells and a maximum of 4 1/2 bit cells, said apparatus comprising: a source of binary data for providing data words and an accompanying code word identifying a number of additional data words which are identical within a predefined tolerance with the data wOrd; encoder means including bit pair comparator means responsive to adjacent uncoded bits of a data word, said bit pair comparator means responsive to a pair of adjacent bits which have not previously been encoded and which form a first of the four possible two bit configurations by producing a toggle pulse at the beginning of the bit cell containing the first bit of said first two bit configuration, said bit pair comparator means responsive to a pair of adjacent bits which have not previously been encoded and which form a second of the four possible two bit configuration, the second bit of which is the complement of the second bit of said one of the four possible two bit configurations, by producing a toggle pulse at the middle of the bit cell containing the first bit of said second two bit configuration whereby each toggle pulse from said bit pair comparator means identifies two bits of binary data and toggle pulses are separated by a minimum of 1 1/2 bit cells, said encoder means including additional comparator means responsive to three consecutive bits of said data word which have not previously been encoded, each bit of which is the complement of the second bit of said first two bit configuration by producing a first toggle pulse at the beginning of the bit cell containing the first of said three consecutive bits and a second toggle pulse at the middle of the bit cell containing the second of said three consecutive bits, whereby the maximum interval between a toggle pulse produced by said bit pair comparator means and a toggle pulse produced by said additional comparator means is 4 1/2 bit cells, redundant word character generator means responsive to a code word of one or more for disabling said encoder means in response to the first toggle pulse from said bit pair comparator means on said second toggle pulse from said additional comparator means and for subsequently generating one or more pairs of toggle pulses, the first of which occurs at the beginning of a bit cell and the second of which occurs at the middle of the following bit cell, the first toggle pulse of the first of said pair of toggle pulses being delayed from the previous toggle pulse by at least 1 1/2 bit cells plus 1 bit cell if said code word is one and 2 bit cells if said code word is two or more, the first toggle pulse of subsequent ones of said pairs of toggle pulses being delayed from the second of a previous pair of toggle pulses by 1 1/2 bit cells plus a minimum of 1 cell and a maximum of 3 bit cells until the total of the added bit cell delays equal the code word number; means including a toggle device responsive to a toggle pulse from said encoder means or said redundant word character generating means for producing said bilevel signal, said redundant word character generating means enabling said decoder means 1 1/2 bit cells after the second of the final pair of toggle pulses.

Claim 9

Apparatus for decoding a bilevel signal containing transitions at the beginning or middle of selected ones of a succession of arbitrarily defined bit cell intervals comprising: a first multistage register; means including first clock means for shifting data through said first register means and for normally entering a binary 0 in the first stage of said first register means; first logic means responsive to a transition in said output signal at the beginning of a bit cell for entering a binary 1 in the first and second stages of said first register means, second logic means responsive to a transition in said output signal at the middle of a bit cell and the absence of a transition in the previous bit cell for entering a binary 1 in the second stages of register means; third logic means for detecting a transitional pattern in said signal including a first transition at the beginning of a bit cell which is followed by a second transition at the middle of the following bit cell for clearing the data in said second and third stages of said register means in response to the second transition in said transitional pattern; a second multistage register means; second clock means for entering the data exiting said first register means into said second register means; clock control means responsive to the detection of said transitional pattern at a bit time interval delayed from a first predetermined reference interval for disabling said second clock means until the expiration of a second predetermined reference interval following a detection of said transitional pattern; and means for accumulating the total number of the bit time interval delays during the entry of a predetermined number of bits in said second register means.

Claim 10

Apparatus for decoding a bilevel signal containing transitions at the beginning or middle of selected ones of a succession of arbitrarily defined bit cell intervals comprising: a first multistage register; means including first clock means for shifting data through said first register means and for normally entering a binary 0 in the first stage of said first register means; first logic means responsive to a transition in said output signal at the beginning of a bit cell for entering a binary 1 in the first and second stages of said first register means, second logic means responsive to a transition in said output signal at the middle of a bit cell and the absence of a transition in the previous bit cell for entering a binary 1 in the second stages of register means; third logic means for detecting a transitional pattern in said signal including a first transition at the beginning of a bit cell which is followed by a second transition at the middle of the following bit cell for clearing the data in said second and third stages of said register means in response to the second transition in said transitional pattern; a second multistage register means; second clock means for entering the data exiting said first register means into said second register means; clock control means responsive to the detection of said transitional pattern at a bit time interval delayed from a first predetermined reference interval for disabling said second clock means until the expiration of a second predetermined reference interval following a detection of said transitional pattern; and means for accumulating the total number of the bit time interval delays during the entry of a predetermined number of bits in said second register means.

Claim 11

Data compression apparatus comprising: a source of data for providing a data word and an accompanying indication of the number of additional data words which are identical within a predefined tolerance with said data word; encoder means for coding said data word by producing first control pulses at the beginning or middle of selected bit cells corresponding to the bit cells of said data word, said encoder means responding to those uncoded bits of a data word which are of one binary characterization by providing a pulse at the beginning of the corresponding bit cell if the bit cell immediately following said corresponding bit cell contains a bit of said one binary characterization, and at the middle of said corresponding bit cell if the bit cell immediately following said bit of said one binary characterization contains a bit of the other binary characterization, said encoder means producing a pair of said first control pulses in response to three consecutive uncoded bits of said other binary characterization, the first pulse of said pair occurring at the beginning of the bit cell corresponding to the first bit of said three consecutive bits and the second pulse of said pair occurring at the middle of the bit cell corresponding to the second of said three consecutive bits whereby the first pulse of said pair of first control pulses is delayed from a first control pulse by a minimum of 1 1/2 bit cells and a maximum of 2 bit cells; redundant word character generator means for identifying the number of said additional data words, said generator means responsive to production of at least one of said first control pulses for disabling said encoder means and for generating at least one pair of second control pulses the first of which occurs at the beginning of a bit cell and the second of which occurs at the middle of the succeeding bit cell, the first pulse of said pair of second control pulses being delayed from a first control pulse by at least 2 1/2 bit cells to thereby identify an additional word of data which is identical with said data word, said character generating means enabling said encoder means 1 1/2 bit cells after the second one of said second pair of control pulses.

Claim 12

Data compression apparatus comprising: a source of data for providing a data word and an accompanying indication of the number of additional data words which are identical within a predefined tolerance with said data word; encoder means for coding said data word by producing first control pulses at the beginning or middle of selected bit cells corresponding to the bit cells of said data word, said encoder means responding to those uncoded bits of a data word which are of one binary characterization by providing a pulse at the beginning of the corresponding bit cell if the bit cell immediately following said corresponding bit cell contains a bit of said one binary characterization, and at the middle of said corresponding bit cell if the bit cell immediately following said bit of said one binary characterization contains a bit of the other binary characterization, said encoder means producing a pair of said first control pulses in response to three consecutive uncoded bits of said other binary characterization, the first pulse of said pair occurring at the beginning of the bit cell corresponding to the first bit of said three consecutive bits and the second pulse of said pair occurring at the middle of the bit cell corresponding to the second of said three consecutive bits whereby the first pulse of said pair of first control pulses is delayed from a first control pulse by a minimum of 1 1/2 bit cells and a maximum of 2 bit cells; redundant word character generator means for identifying the number of said additional data words, said generator means responsive to production of at least one of said first control pulses for disabling said encoder means and for generating at least one pair of second control pulses the first of which occurs at the beginning of a bit cell and the second of which occurs at the middle of the succeeding bit cell, the first pulse of said pair of second control pulses being delayed from a first control pulse by at least 2 1/2 bit cells to thereby identify an additional word of data which is identical with said data word, said character generating means enabling said encoder means 1 1/2 bit cells after the second one of said second pair of control pulses.

Claim 13

Apparatus for reduced redundancy encoding of binary data comprising: a source of binary data providing a data word and an associated code word identifying the number of additional data words which are identical with said data word within a predefined tolerance; first and second logic means responsive to said data word and said code word, respectively, and for providing a bilevel output signal which may be considered as arbitrarily divided into a plurality of bit cells of equal time duration, and which contains transitions between the separately identified levels at the beginning or middle of selected ones of the bit cells for identifying the bits of said data word and said additional data words; said first logic means including bit comparator means for producing transitions at the beginning or middle of selected ones of said bit cells to identify pairs of bits in adjacent bit cells, said bit comparator means responsive to those uncoded bits of said data word of one binary characterizAtion by providing a transition at the beginning or the middle of each corresponding bit cell containing said bit of said one binary characterization depending upon whether said corresponding bit cell is immediately followed by a bit cell containing a bit of said one binary characterization or the other binary characterization, respectively, to thereby code the two bits in the adjacent bit cells, said bit comparator means responsive to three consecutive uncoded bits of said other binary characterization by providing a transition at the beginning of the bit cell containing the first of said three consecutive bits and a transition at the middle of the bit cell containing the second of said three consecutive bits; said second logic means responsive to the production of a transition by said first logic means for inhibiting said first logic means at the beginning of the bit cell following the bit cells containing the two bits coded by the transition produced by said first logic means and for thereafter producing a three bit transitional pattern containing a pair of transitions the first of which is produced at the beginning of a bit cell after a delay of 1 bit cell if said number is one or a delay of 2 bit cells if said number is two or more, the second transition of said pair being produced 1 1/2 bit cells after said first transition of said pair; arithmetic means for reducing said code word by the number of said bit cell delays of the first transition of said transitional pattern; said second logic means responsive to the number of the reduced code word for producing succeeding transitional patterns which are delayed from the previous transitional pattern by a minimum of 1 bit cell and a maximum of 3 bit cells; said second logic means responsive to a reduction of the number of said code word to zero for enabling said first logic means whereby transitions in said output signal are separated by a minimum of 1 1/2 bit cells and a maximum of 4 1/2 bit cells and the run length of any particular word is proportional to the total of the delays associated with the first of said pairs of transitions.

Claim 14

Apparatus for reduced redundancy encoding of binary data comprising: a source of binary data providing a data word and an associated code word identifying the number of additional data words which are identical with said data word within a predefined tolerance; first and second logic means responsive to said data word and said code word, respectively, and for providing a bilevel output signal which may be considered as arbitrarily divided into a plurality of bit cells of equal time duration, and which contains transitions between the separately identified levels at the beginning or middle of selected ones of the bit cells for identifying the bits of said data word and said additional data words; said first logic means including bit comparator means for producing transitions at the beginning or middle of selected ones of said bit cells to identify pairs of bits in adjacent bit cells, said bit comparator means responsive to those uncoded bits of said data word of one binary characterizAtion by providing a transition at the beginning or the middle of each corresponding bit cell containing said bit of said one binary characterization depending upon whether said corresponding bit cell is immediately followed by a bit cell containing a bit of said one binary characterization or the other binary characterization, respectively, to thereby code the two bits in the adjacent bit cells, said bit comparator means responsive to three consecutive uncoded bits of said other binary characterization by providing a transition at the beginning of the bit cell containing the first of said three consecutive bits and a transition at the middle of the bit cell containing the second of said three consecutive bits; said second logic means responsive to the production of a transition by said first logic means for inhibiting said first logic means at the beginning of the bit cell following the bit cells containing the two bits coded by the transition produced by said first logic means and for thereafter producing a three bit transitional pattern containing a pair of transitions the first of which is produced at the beginning of a bit cell after a delay of 1 bit cell if said number is one or a delay of 2 bit cells if said number is two or more, the second transition of said pair being produced 1 1/2 bit cells after said first transition of said pair; arithmetic means for reducing said code word by the number of said bit cell delays of the first transition of said transitional pattern; said second logic means responsive to the number of the reduced code word for producing succeeding transitional patterns which are delayed from the previous transitional pattern by a minimum of 1 bit cell and a maximum of 3 bit cells; said second logic means responsive to a reduction of the number of said code word to zero for enabling said first logic means whereby transitions in said output signal are separated by a minimum of 1 1/2 bit cells and a maximum of 4 1/2 bit cells and the run length of any particular word is proportional to the total of the delays associated with the first of said pairs of transitions.