Cascade run length encoding technique

Claim 2

A data transmitter including information source means for generating data signals of at least two information levels, comprising: first circuit means for analyzing said data signals for run lengths of the same respective information level; second circuit means for generating signal steps in accordance with a predetermined code based on the probability of occurrence of said run lengths; and third circuit means coupled to said first and second circuit means responsive to said run lengths and said signal steps for generating predetermined code word groups, said word groups increasing in length in accordance with the decreasing probability of occurence of the respective run lengths of information.

Claim 3

The apparatus as defined in claim 1 further including fourth circuit means for directing the generation of said code words in said third circuit means in response to said generated signal steps.

Claim 4

The apparatus as defined in claim 2 further including fifth circuit means for counting said data signals and generating timing signals indicative thereof.

Claim 5

In a graphic communication system, a binary encoder for reducing the redundancy in a binary signal waveform comprising: shift register means for serially storing the input binary digits of a first and second binary level; format generating means for generating a plurality of format levels in accordance with a predetermined code based on the probability density function of the lengths of the groups of first binary level digits and the groups of second binary level digits; shift-register/counter means coupled to said shift-register means and said format generating means for generating said predetermined code words; and shift/count control means coupled to saId shift-register means and said shift-register/counter means for monitoring the several stages of said shift shift-register/counter means, said shift/count control means controlling the shifting and counting of said shift-register/counter means in response to the increasing length of the code word determined by said format generating means.

Claim 6

In a graphic communication system, a binary encoder for reducing the redundancy in a binary signal waveform comprising: shift register means for serially storing the input binary digits of a first and second binary level; format generating means for generating a plurality of format levels in accordance with a predetermined code based on the probability density function of the lengths of the groups of first binary level digits and the groups of second binary level digits; shift-register/counter means coupled to said shift-register means and said format generating means for generating said predetermined code words; and shift/count control means coupled to saId shift-register means and said shift-register/counter means for monitoring the several stages of said shift shift-register/counter means, said shift/count control means controlling the shifting and counting of said shift-register/counter means in response to the increasing length of the code word determined by said format generating means.

Claim 7

The apparatus as defined in claim 4 further including counter means for counting the input binary digits, and time base generator means for generating clock pulses in response to said counter means.

Claim 8

The apparatus as defined in claim 4 further including buffer storage means for storing said generated code words.

Claim 9

In a graphic communication system including a transmitter for transmitting first and second level binary code words representative of information run lengths encoded in accordance with the statistical distribution thereof, a receiver comprising: storage means for serially storing said transmitted first and second level binary code words; encoder means for generating a code word pattern synchronously with the start of each of the first and second level code words stored in said storage means in accordance with the same statistical distribution of the first and second level binary digit run lengths in said information; gating means coupled to said encoder means and said storage means for comparing said generated code word pattern with said stored first and second level binary words; and switching means coupled to said gating means for transmitting binary digits of the run length binary level being decoded at each comparison until said generated code word pattern compares bit for bit with said stored first and second level binary words to obtain a waveform of the original run length information.

Claim 10

In a graphic communication system including a transmitter for transmitting first and second level binary code words representative of information run lengths encoded in accordance with the statistical distribution thereof, a receiver comprising: storage means for serially storing said transmitted first and second level binary code words; encoder means for generating a code word pattern synchronously with the start of each of the first and second level code words stored in said storage means in accordance with the same statistical distribution of the first and second level binary digit run lengths in said information; gating means coupled to said encoder means and said storage means for comparing said generated code word pattern with said stored first and second level binary words; and switching means coupled to said gating means for transmitting binary digits of the run length binary level being decoded at each comparison until said generated code word pattern compares bit for bit with said stored first and second level binary words to obtain a waveform of the original run length information.

Claim 11

The apparatus as defined in claim 7 further including second gating means coupled to said shift register means for monitoring the binary level of each stage thereof, the output of said gating means coupled to the other input of said switching means.

Claim 12

The apparatus as defined in claim 8 wherein said storage means is a logical shift register, said first mentioned gating means is an exclusive-OR gate, and said second gating means is a logical AND gate.

Claim 13

The apparatus as defined in claim 9 wherein said switching means is a logical flip-flop circuit.

Claim 16

The method as defined in claim 11 wherein the step of encoding includes: encoding said groups of binary digits of a first binary level according to their respective probabilities of occurrence; and further encoding said groups of binary digits of a second binary level according to their respective probabilities of occurrence.

Claim 17

The method as defined in claim 11 wherein the step of encoding includes: encoding said groups of binary digits of a first binary level according to their respective probabilities of occurrence; and further encoding said groups of binary digits of a second binary level with an equal number of binary digits of one binary level except the last digit which remains a digit of the other binary level.

Claim 18

The method as defined in claim 11 wherein the step of encoding includes: encoding said groups of first leveL binary digits and groups of second binary level digits according to the probabilities of occurrence of the groups of said first level binary digits.

Claim 19

The method as defined in claim 11 wherein the step of encoding includes: encoding said groups of first level binary digits and groups of second binary level digits according to the probabilities of occurrence of the groups of said second level binary digits.

Claim 22

The method as defined in claim 16 wherein the step of generating includes: generating a code word pattern for said first level binary digit run lengths according to their respective probabilities of occurrence; and further generating a code word pattern for said second level binary digit run lengths according to their respective probabilities of occurrence.

Claim 23

The method as defined in claim 16 wherein the step of generating includes: generating a code word pattern for said first level binary digit run lengths according to their respective probabilities of occurrence; further generating a code word pattern for said second level binary digit run lengths; and said code pattern comprising an equal number of binary digits in said run lengths of the first binary level except the last digit which remains a digit of said second binary level.

Claim 24

The method as defined in claim 16 wherein said step of generating includes: generating a code word pattern for said first level binary digit run lengths and said second level binary digit run lengths according to the probability of occurrence of the run lengths of said first level binary digits.

Claim 25

The method as defined in claim 16 wherein said step of generating includes: generating a code word pattern for said first level binary digit run lengths and said second level binary digit run lengths according to the probability of occurrence of the run lengths of said second level binary digits.

Claim 26

In a graphic communication system, the combination comprising: means for generating a source of image exploring rays; means for focusing said image exploring rays to form an exploring beam of light of predetermined size; means for projecting the exploring beam of light onto a document containing data and redundant background information to be explored in a raster type sweep scan; means for imparting relative translatory motion between said beam of light and said document to be explored; means for detecting the information modulated reflected light rays from said document; quantizing means coupled to said detecting means for generating video binary waveforms representative of successive scan lines of information; means for encoding said video binary waveform into code words in accordance with the probability of occurrence of the run lengths of binary information in said video binary waveform; and buffer storage means for storing said generated code words, wherein said means for imparting relative translatory motion further includes means for repeatedly scanning an Information line until said buffer storage means has adequate capacity to store the information detected from an entire scan line, wherein a line containing data and redundant background information is normally scanned once, only the most complex line of information necessitating repeated scanning.

Claim 27

In a graphic communication system, the combination comprising: means for generating a source of image exploring rays; means for focusing said image exploring rays to form an exploring beam of light of predetermined size; means for projecting the exploring beam of light onto a document containing data and redundant background information to be explored in a raster type sweep scan; means for imparting relative translatory motion between said beam of light and said document to be explored; means for detecting the information modulated reflected light rays from said document; quantizing means coupled to said detecting means for generating video binary waveforms representative of successive scan lines of information; means for encoding said video binary waveform into code words in accordance with the probability of occurrence of the run lengths of binary information in said video binary waveform; and buffer storage means for storing said generated code words, wherein said means for imparting relative translatory motion further includes means for repeatedly scanning an Information line until said buffer storage means has adequate capacity to store the information detected from an entire scan line, wherein a line containing data and redundant background information is normally scanned once, only the most complex line of information necessitating repeated scanning.