Note: Descriptions are shown in the official language in which they were submitted.
104ZS53
1 A variety of data compression techniques have been devised for
reducing the storage requirements for digital images, and for reducing
the bandwidth required for their transmission. Most of these techniques
are based on some form of run length coding.
In its simplest form, run length coding of images involves two
steps. First, there is the partitioning of each row of the image array
into a sequence of "runs", with each run comprising one or more adjacent
image points with the same binary value, i.e., 0 or 1. Second, it is
necessary to replace each run of image points with a single integer that
specifies the length of the run. For example, a run of 10 successive
image points with the value of 0 can be replaced by the single integer
10. It is not necessary to identify explicitly the binary value of each - `
run. It is sufficient to specify the binary value of the first run in
each row, since the binary values of successive runs alternate between 0
and 1.
More efficient run length coding techniques use variable length
binary code words, rather than integers, to represent the lengths of
the various runs. The run length codes used with such techniques are
designed so that the shorter code words are used to represent more
frequently occurring runs and the longer code words are used for
less frequently occurring runs. For typical applications the runs
of lengths 1 to S occur most frequently. The probability of occurrence
for successively longer runs tends to decrease steadily thereafter.
There is one singlé exception, that is the longest possible run.
Such a run can, for example, represent a completely white line on
the printed page, which occurs frequently. Since the probability
of occurrence tends to decrease with the length of a run, the length
of the code word used to
SA9-73-013 - 2 -
. .
.. : :, : , ....... . .
1~4ZSS3
1 represent a run generally increases with the length of the run. Forexample, a run of length 20 is normally represented by a code word
that is longer than the code word used for a run of length 10.
A slightly different group of run length coding techniques have
been used when the number of image points with a binary value of 0
far exceeds the number of image points with a binary value of 1.
These techniques partition each row of the image array into a number
of runs of O's, each separated by a single 1. Then, only the runs ~
of O's are encoded. Although it is sometimes necessary to encode -
the run of "no O's" that appears between two adjacent l's in a row
of the image array, it is not necessary to encode any runs of l's.
This strategy is particularly effective when used in conjunction with
predictive encoding, which transforms an original image array into a
new array that includes few l's. See, for example, L. Bahl et al, ~:
U.S. Patent 3,769,453, "Finite Memory Adaptive Predictor."
Finally, a few sophisticated data compression techniques for
images use run length codes that have been extended to include a
number of "special" code words in order to represent certain special
i situations. These special code words are used in conjunction with -
the "regular" code words used to represent runs. An example is the ~- -
code described by I. Gorog et al in the article entitled "An
Experimental Low Cost Graphic Information Distribution Terminal,"
1971 SID International Symposium of Techn1cal Papers. Gorog's code -~
includes three special code words for special situations. These
special situations are the occasion that a run in one row of an
image array elther ends dlrectly beneath the end point of a corres-
ponding run in the previous row, or ends one position to the left
or right of this end point.
SA9-73-013 - 3 -
. , .
,. ,., , , . .. , . . , . ' ' : . ' . '
: . . . . . .. . . . . .
1(~42S53
l The primary disadvantage of previous run length coding systems
is that they have used an ordinary or extended run length code which
represented a compromise among three coding objectives. The objectives
are high efficiency for typical images, uniformly high efficiency
for a class of images, and an economical implementation. In this
regard, reference should be made to N. Abramson, "Information Theory
and Coding," McGraw Hill Book Co., New York, 1963 at pp. 85-88 for
a discussion for code efficiency. Abramson's efficiency measure is
based upon the value of a symbol from an information source S, which
can be measured in terms of an equivalent number of binary digits
needed to represent one symbol from that source. The average value
of a symbol from S is denoted by H(S). Note that H(S) = j pjlog(l/p;),
where pj is the probability of the ith source symbol. Given that L
is the average code word length~for any uniquely decodable code for
the source, it is the case that L cannot be less than H(S). Accor-
dingly, the efficiency of the code is the ratio of H(S)/L.
Taking the above coding objectives into account, the most easily
implemented run length code, which uses the fixed length binary in-
teger i as a code word for runs of length i, is not nearly as
~0 efficient as a variable length code. On the other hand, the most
efficient extended run length code possible for a sample of images
is the Huffman code based on the relative frequencies of runs and
special situations in the sample of images. However, since run
length codes for images typically require l to 5~000 code words, the
Huffman code is normally difficult to implement.
Three general types of decoders are currently in use. These
are the tree follower types; a table lookup type; and an encoder
based type.
SA9-73-013 _ 4
.. . . . .
. . ~. ~ . , . ' "' ' '
10425S3
1 A t:ree follower decoder depends on the fact that standard variable
length binary codes have a tree-like structure. The decoder includes
logic circuitry corresponding to the tree, and successive code word
bits cause control circuitry to traverse this tree structure. When a
terminal node of the tree is reached, an entire code word has been
received, and the terminal node identifies the code word.
A table lookup decoder includes a table containing each code word
as a separate entity. As successive code word bits are received, each -~
code word must be checked to see whether it agrees with all code word
bits received so far. When only one code word agrees, that code word
has been received and identified. The table storage required by this
table lookup type of decoder is expensive.
An encoder based decoder includes a copy of the encoder, a bit
generator, and comparison circuitry. The bit generator supplies a
sequence of bits to the encoder. The encoder continuously produces `~ -
the code word appropriate for the run comprising the bits generated
so far. Each code word thus produced is compared with code word ~ -
bits received. When a match occurs, the decoded run length is taken
to be the number of bits generated by the bit generator.
Summary of the Invention
It is therefore an object of this invention to provide a method
and apparatus for decoding ordinary and extended run length codes
that are both highly efficient for a sample of images and uniformly
efficient for a class of images.
The above and other objects are believed satisfied by the
description of a preferred embodiment of the invention, the
apparatus comprising table storage and select/combine
., :
. . . .
SA9-73-013 - 5 -
. . ~ . . ..
:
., . . . ~ . , ,
"' ' ' '', , :. ' ' ' ' '
. .
1042SS3
l circuitry. The table storage is sufficient to hold four small tables
whose values can be adjusted to correspond to any ordinary or extended
run length code The select/combine circuitry accepts as input the
successive bits of a code word and compares the bits received so far
with successive elements of one stored table until it is determined
that an entire code word has been received. Then, this code word is
combined with other table values to produce a binary value which uni-
quely identifies the code word received.
More particularly, the disclosed apparatus comprises a decoder
that can isolate and identify a code word for a specific class of
ordinary and extended run length codes. As will be shown, this class
of codes includes a code of uniformly high efficiency for any desired ~ -
data compression technique and any desired class of images.
The class of codes to be implemented includes the ordinary and
extended run length codes characterized by three parameters, a maximum
number N of regular code words, a maximum number M of special code
words, and a maximum code word length LmaX .
The class of codes to be implemented is further restricted by the
requirements that the code word lengths Lr(l), Lr(2)~ ... for the
regular code words cr(l), cr(2), ... must be monotonically increasing.
The code word lengths Ls(l), L5(2), ... for the various special code
words cs(l), cs(2~, must also be monotonically increasing. That is,
the code word lengths must satisfy the relations
lcLr(l )~Lr(2)~ '--Lmax'
1~LS(1)'LS(2)C -- ~Lmax
F1nally, the code words for the codes to be implemented must be
related algebraically to the elements of four small
SA9-73-013 ~ - 6 -
. .. . . . . , :
.. . . .
; , ,
~42553
1 tables BR= ~br(l), br(2), -- br(Lmax~ ~ ~ BS- [bs(l~ bs(2)'
s max ~ ' [tr(l), tr(2), --. tr(Lmax) ~ , and TS= ~t (1), t (2)
..., tS(Lmax) ~ , whose values are determined by the code word lengths
according to the formulas
br(k) = number of regular code words with length k or less;
bS(k) = number of special code words with length k or less;
b (k) b (k~
tr(k) = r 2k~Lr(i) + s 2k Ls(j);
j_l j=l ~ , -
b (k) b (k) - :
tS(k) = r 2k~Lr(i) + s 2k Ls(j).
~. ,.. ~.... ..
i=l j=l ,,,
In particular, the regular and special code words for codes to
be implemented must be the binary integers related to these table -
values according to the formulas
Cr(,i ) = tr(Lr(i))-br(Lr( ))
CS(j~ = ts(Ls(j))-bs(Ls(i)) j
These relationships between the monotonically increasing
code word lengths, the table values, and the code words themselves
are illustrated in Tables 1 and 2 for a code which includes seven
regular code words and two special code words.
Table 1
SAMPLE CODE --
Lr(i)Ls(i) Cr(j3 Cs(i)
1 2 2 00 01
2 3 3 100 101
3 4 - 1100
4 4 - 110l -
4 - 1110 - :
~ 5 - 11110
7 5 - 11111
SA9-73-012 ~ - 6a -
lO~ZSS3
1 Table 2
TABLE VALUES FOR SAMPLE CODES
k br(k) bs(k) tr(k) tS(k)
0 0 0 0
2 1 1 1 2
3 2 2 5 6
4 5 2 15 15
`7 2 32 32
10 ~ A simple example will serve to illustrate that the class of
ordinary and extended run length codes implemented by the disclosed
decoder includes a code with uniformly high efficiency for any
desired data compression technique and any desired class of images.
Suppose that the desired compression technique requires an ex- `
tended run length code with code words for runs of lengths 1 through
n, and with code words for m special situations. Then, the relative
frequencies of occurrence for the various runs and special situations
may be measured in a sample of images, and these relative frequencies
may be used to separate the runs and special situations into two ordered
lists of events. In particular, the successive regular events are the ;
runs with lengths f through n-l~ where f is the length of the most
~ frequently occurring run. The successive special events are the m
; ~ ~ special situations plus the runs with lengths 1 through f-l and the
~ runs of length n, all taken in order of decreasing frequency of
.
occurrence. The relative frequencies of the n-f regular events and -~
the m~f special events are used to calculate code word lengths that
are ordered and bounded accord~ng to the two relations
.
.
~
~.
SA9-73-013 ~ - 6b -
.
.
.
, . .. . . . : , .
. . , ;
. , : . . .
104ZS53
lLLr(l )~Lr(2)~ ' ~Lr(n-f)~Lmax
l~Ls(l)<Ls(2) <Ls(m+f)<Lma
and that lead to the minimum average code word length permitted by
these relations. Finally, the code word lengths are used in the pre-
viously provided formulas to calculate values for the BR, BS, TR, and
TS tables, and hence to calculate the n-f regular code words cr(l), -
cr(2), ..., cr(n-f) and the m~f special code words cs(l), cs(2),
... , cS(m+f). . :.,
The simple code construction technique just described constructs ~ -
an extended run length code whose code word lengths are both mono- --
tonically increasing and bounded. As will be shown, this code is
normally both highly efficient for the sample images and uniformly
efficient for similar images not in the sample. For typical data
compression techniques the relative frequencies for runs reaches its
maximum value for runs of length f, where f is less than 5, and then
the relative frequencies for successively longer runs tend to decrease
for runs with lengths between f and n-l. Therefore, the above code
construction technique places the regular events approximately in order
of decreasing relative frequency, and it places the special events
exactly in order of decreasing relative frequency, so that monotoni-
cally increasing codeword lengths lead to a code that is highly
efficient for the sample images. Furthermore, E.N. 6ilbert shows
in his article "Codes Based on Inaccurate Source Probabilities",
IEEE Transactions on Information Theory, Vol. IT-17, pp. 304-314,
May 1971, that using a bound LmaX ~log2(n+m) for the length of the
longest codewords tends to promote uniformly high code efficiency.
SA9-73-013 ~ ~ ~c -
- . . . .
.
1~4;~S53
1 The operation of the disclosed decoder, which uses the stored
tables BR, BS, TR, and TS to isolate and identify codewords can be
summarized as follows. As successive bits Y1~ Y2, ... of a codeword
are received, the select/combine circuitry concatenates these bits
into a single integer for comparison with successive elements of the
TS table. When for some value of k the resulting k-bit integer
Y = YlY2---Yk is found to satisfy the relation y CtS(k), it is known
that y is a k-bit codeword which must be identified. To this end,
the codeword y is compared with the table value tr(k). If y <tr(k),
then the decoder calculates the event designation.
s = O
i = y-tr(k) + br(k) + 1,
which signifies that y is the ith regular codeword cr(i). Alternatively,
if y ~tr(k), then the decoder calculates the event designation
s = 1
i = y-ts(k) ~ bS(k) + 1,
which signifies that y is the ith special codeword cs(i). ~ ~ -
Brief Description of the Drawings
FIGURE 1 is a generalized block diagram of a data compression
encoding apparatus in accordance with the present invention;
FIGURE 2 is a generalized block diagram of a data compression
decoder in accordance with the present invention;
FIGURE 3 is a detailed block diagram of one embodiment of encoder -
select/combine apparatus 14 of FIGURE l;
FIGURE 4 is a more detailed block diagram of an embodiment of
encoder tables 16 of FIGURE l;
FIGURE 5 is a detailed diagram of a T router 160 of FIGURE 4,
SA9-73-013 - 6d -
S53
1 FIGURE 6 is a detailed diagram of a B router 161 of
2 Figure 4;
3 FIGURE 7 is a detailed block diagram of shift registers :~
4 182 of Figure 4;
FIGURE 8 is a detailed block diagram of an embodiment
6 of shift out circuitry 17 of Figure l;
7 FIGURE 9 is a detailed block diagram of an embodiment
8 of the decoder select/combine apparatus 51 of Figure 2;
9 FIGURE 10 is a more detailed block diagram of an em-
10 bodiment of the decoder S tables 52 of Figure 2; -:-
11 FIGURE 11 is a detailed diagram of the Ts router 314
12 of Figure 10;
13 FIGURE 12 is a detailed diagram of the BS router 315
14 of Figure 10;
FIGURE 13 is a detailed block diagram of the S shift
16 registers 323 of Figure 10; - ,
17 FIGURE 14 is a more detailed block diagram of an em-
18 bodiment of decoder R tables 53 of Figure 2;
19 FIGURE 15 is a detailed diagram of the TR router 364
of Figure 14;
21 FIGURE 16 is a detailed diagram of the BR router 365 :~:
22 of Figure 14;
23 FIGURE 17 is a detailed block diagram of the R shift
24 registers 373 of Figure 14; ~;
25 FIGURE 18 is an illustration of the outputs of the ::
26 encoder tables 16 of Figure 1 and of the decoder tables 52 : .
27 and 53 of Figure 2;
28 FIGURE 19 is a partial block diagram of another em-
29 bodiment of an encoder select/combine apparatus 14 of Figure l;
SA973013 -7-
. , -,
: .; , .
S53
l FIGURE 20 is a partial block diagram of anothcr
2 embodiment of a decoder select/combine apparatus 51 of
3 Figure 2;
4 FIGURE 21 is a detailed block diagram of an embodi-
ment of an event recognizer 10 of Figure l;
6 FIGURE 22 is a detailed block diagram of an embodi-
7 ment of an event regenerator 50 of Figure 2; and
8 FIGURE 23 is a detailed block diagram of scan line
9 buffers 432 in Figure 21 and scan line buffers 540 of Figure
22.
11 Description of Preferred Embodiments -
. - . .
12 The data compression encoding and decoding circuitry
13 of the present invention may be implemented in various pre-
14 ferred forms and arrangements. One such embodiment is illus-
15 trated by the encoding arrangement of Figure 1 and the decoding -
16 arrangement of Figure 2. ~
17 Figure 1 includes an event recognizer 10. The present -
18 invention relates to the compression of information, wherein
1~ elements of information may be characterized as events. An
information element, or event, may comprise a binary encoded
21 representati~n of an alphanumeric character, an analog voltage,
22 a run of binary video information, a run of binary image in-
23 formation, or any other type of information capable of recog-
nition. The events may be further characterized as regular
25 or special. -
26 The event recognizer 10 is designed to recognize each
27 element of the specifia type of information which is presented
28 to it and to supply a binary output therefrom characterizing
29 each received unit of information. The event characterization
SA973013 -8-
. . . . . .. .. . . . . . .. .
.. . ~ , . . .. . . .
: . . , : . . : ;
. ' ':1 , ~ , . . ..
~` ~0425S3
1 comprises a single bit of information to indicate whether
2 the event is regular or special, and an event designation
3 number that uniquely identifies the event.
4 Although the present invention can be employed in
a wide variety of information environments, including those
6 in which no events are classified as special, it is cur-
7 rently anticipated that the most advantageous usage of the
8 present invention will be in the field of run length encod- -
9 ing. In such a circumstance, the event recognizer 10 may
recognize each sequence of consecutive bits of the same logic
11 level, which is denoted as a run. Runs may also be sequences - ,
12 of bits of one of the logic levels, or sequences of a level
13 terminating in another level. All runs can be classified ~:
14 as regular events, and the event designation number for a
run can simply be the length of that run~ Alternatively,
16 runs of certain lengths can be classified as special events.
17 For example, runs of length 1 or 2 can be classified as
18 special events and characterized by event designation num-
19 bers 1 or 2, while the remaining runs can be classified as
regular events, with the event designation number for a run
21 of length 3 or greater simply two less than the length of -
22 that run. Thus, a run of length 4 would be characterized
23 by event recognizer 10 as regular event No. "2", whereas a
24 run of length 2 would be characterized as special event
No. "2". The event designation number is supplied by the
26 event recognizer 10 on parallel cable 11 together with a
27 bit on line 12 which indicates whether the designation on
28 line 11 refers to a regular event or a special event, and
29 together with a signal on line 13 which indicates that the
SA973013 -9-
.
.
104ZS53
1 event designation information is available on cable 11 and
2 line 12. An example of a suitable event recognizer will
3 be described in detail hereinafter.
4 The signals from the event recognizer 10 are supplied
to an encoder 14. The encoder signals acceptance of the in-
6 formation on cable 11 and line 12 by providing an ~accept"
7 pulse signal on line 15 to the event recognizer 10. The
8 information shown as being received on cable 11 in parallel ~ -
9 may alternatively be supplied in the form of serial infor- ~ -
10 mation over a single line. The parallel transmission of -
11 such information, however, appears to be the more efficient
12 approach. - -~
13 - The encoder 14 responds to the signal supplied from
14 event recognizer 10 by selecting the appropriate entries
from encoder tables 16 corresponding to the event designation
16 appearing on cable 11 and line 12~ The encoder then combines
17 the selected values with the event designation number from
18 cable 11 to generate a code word representation therefor,
19 which is supplied to shift out circuitry 17 for conversion
from parallel to serial form.
21 Encoder 14 is connected to the encoder tables 16 by
22 lines 20, 21 and 22, and by cables 23 and 24. Line 21 com-
23 prises an enabling line operated by acceptance of the
24 im~ediately prior code word by shift out circuitry 17. The
enabling signal, together with a pulse in line 20, causes
26 the contents of tables to be loaded into table readout cir-
27 cuitry. Successive pulses on line 20 are used to aperate
28 the table readout circuitry. Line 22 comprises the special
29 or regular signal from event recognizer 10 on line 12.
. ~'. .
SA973013 -10-
;~ -
,
la~2ss3
1 Cables 23 and 24 comprise the outputs from the table read-
2 out circuitry which supply the table values to encoder 14.
3 The encoder is connected to shift out circuitry 17
4 by means of lines 25, 26 and 27, and by cables 28 and 29.
Cable 29 comprises the codeword in parallel and includes
6 enough lines to encompass the longest codeword. Cable 28
7 comprises the designation of the length of the codeword on
8 cable 29 so that the unused lines comprising the remainder
9 of cable 29 may be ignored. A signal on line 27 indicates
that the codeword is presert on cable 29. Line 26 comprises
11 an output from a clock source in encoder 14 to control the
12 enabling of circuitry 17. A pulse on line 25 indicates to
13 the encoder 14 that shift out circuitry 17 has accepted the
14 codeword on cable 29.
Initialization circuitry is also provided which
16 includes a reset input 30 that is supplied to inputs 31-33
17 to initially reset the encoding circuitry and is supplied
18 via inverter 35 to AND circuit 36 to prevent initialization
19 until the reset is complete. A start signal is supplied at
input 37 to AND circuit 36. It is then supplied to inputs
21 38 and 39 of the encoding circuitry.
22 Shift out circuitry 17 is connected to a transmission
23 link or a storage device by lines 40-42. A signal on line
24 41 indicates that the codeword can be shifted out in serial
form on line 40, and line 42 comprises an acceptance and
26 timing line from the transmission link or storage device.
27 Referring to Figure 2, the decoding ci~cuitry and event
~8 regenerator 50 are illustrated. The event regenerator responds
29 to the decoded signals from decoder 51, which operates with
SA973013 -11-
1042553
1 respect to decoder tables 52 and 53 to reproduce the oriyinal
2 event designation generated by event recognizer 10 in Figure 1.
3 Input lines 60-62 to decoder 51 may be connected
4 directly to lines 40-42, respectively, of Figure 1. Al-
ternatively, lines 40-42 and lines 60-62 may be connected
6 to opposite ends of a communication link or to the input
7 and output, respectively, of a data storage device. As with
8 respect to lines 40-42, line 60 comprises the serialized ~-
9 codeword, line 61 represents the availability on line 60 of
the codeword and line 62 represents acceptance and timing
11 of the codeword by the decoder 51. Tables 52 and 53 are
12 similar to table 16 in Figure 1. The difference is that
13 the table readout circuitry in Figure 1 is loaded with either
14 the table values associated with regular codewords or table
15 values associated with special codewords, depending upon the ~ -
16 significance of the signal on lines 12 and 22. In the de-
17 coder circuitry there is no prior indication as to whether
18 the event is special or regular. Hence, both sets of tables
19 must be supplied to the decoder for selection therebetween.
The decoder tables are connected to decoder 51 by lines
21 70-73 and by cables 74-77. Lines 71 and 73 supply enabling
22 signals to the decoder tables 52 and 53 to thereby load the
23 table readout circuitry thereat. Lines 70 and 72 comprise
24 pulses from the decoder 51 to operate the table readout
circuitry. Cables 74-77 comprise the parallel output of the
26 pre-established values selected from the tables 52 and 53.
27 Decoder Sl selects the output from one of the sets of tables
28 and combines these pre-established values with the codeword
29 to provide the decoded output on cable 80 to event regenerator
,
,
SA973013 -12-
.: . . . . . .
.
~V42S53
1 50, together with a special or regular indication on line
2 81. The decoder is also connected to event regenerator 50
3 by means of lines 82 and 83. Line 82 comprises the signal
4 indicating that the decoded information is supplied on cable
80 and line 81. Line 83 comprises an acceptance line from
6 the event regenerator to indicate that it has accepted the
7 information on cable 80 and line 81.
8 Initialization circuitry is also supplied and is
9 operated by virtue of reset input 90 and start input 91. The
reset input is connected to inputs 92 and 93 of the decoding
11 and event regenerator circuitry and, via inverter 94 to AND
12 circuit 95. AND circuit 95 insures that the start signal will
13 be supplied subsequent to the reset signal to inputs 96 and
14 97 of the decoder and event regenerator.
The specific arrangement of decoder 51 and of decoder
16 tables 52 and 53 will be explained hereinafter. An example
17 of ev~nt regenerator 50 will also be explained hereinafter.
18 Referring now to a specific example of~ncoding cir-
19 cuitry 14 and encoder table 16, Figures 3 and 4-7 will be
discussed.
21 Referring first to Figure 3, an implementation of
22 encoder 14 is shown which employs standard semiconductor
23 modular elements. Special input line 12 is connected di-
24 rectly to special output line 22 so that the line is employed
25 directly to select the special or regular tabular values. -~
26 The event designation cable 11 is connected to a shift regis-
27 ter comprising shift-right units 100 and 101. These units
28 are interconnected and are both connected to the same con-
2~ trol lines 20 and 21 so as to comprise a single shift
SA973013 -13-
:
, ~ .
.
lO~ZSS3
1 register arran~ed to shift only to the right. The contents
2 of the shift register are directed to OR circuit 102 and to
3 adders 103 and 104. The other input to the adders comprises
4 cable 23 from the table readout circuitry. The carry output
105 from the adder circuitry is inverted by NOT circuit 106
6 and supplied to OR circuit 102. The inputs to the adder cir-
7 cuitry from shift register 100, 101 are first inverted by
8 inverters 107, 108. The carry-in input 109 to the adder cir-
9 cuitry is supplied to a fixed voltage. The function of the
resultant adder circuitry, inverters, and carry-in 109 is to
11 subtract the binary value of the shift register 100, 101 -
12 from the binary value appearing on cable 23, and to provide
13 an output from NOT circuit 106 to OR circuit 102 so long as
14 the difference (b-i) is less than 0. The subtraction is ac- -
complished by adders in accordance with the well-known binary
16 relationship of adding the complement of the number to be sub-
17 tracted to the number from which it is to be subtracted and
18 adding a binary 1 thereto, together with inverting the carry
19 output 105 of the adder to obtain the sign of the result.
20 As will be shown, the selection of the proper table -
... . . . .. .
21 values from the table readout circuitry is controlled by OR
22 circuit 102. The table selection circuitry is of significantly
23 lower cost than the random access type. Thus, clock pulses
24 from clock 110 sequences the table readout circuitry, as wlll
be explained hereinafter, under the control of the output of
26 OR circuit 102 on line 111 at gate 112, until the table values
27 corresponding to the event designation number supplied on
28 cable 11 is reached.
29
SA973013 -14-
,
~ ~ .
lO~ZSS3
1 An alternative to this unique circuit arrangement is a
2 random access memory for holding the tabular valuc~. In that
~ situation, thc evcnt ~esignation number on c~le ll woul~ be
4 employed to operate addres~ing circuitry to directly or indi-
rectly address the corresponding memory location.
6 Other circuitry in Figure 3 comprises a shift register
7 115 whose function is to shift a binary 1 initially loaded at
8 input 116 in conjunction with shifts of shift register 100, 101.
9 As the shift register is always loaded with the same values, the
inputs thereto are fixed to the appropriate voltage levels. The
11 contents of shift register 115 are supplied to adders 117 and
12 118 via inverters 119 and 120. The carry-in input 121 of adder
13 118 is affixed to suitable voltage level to generate a 1. The
14 function of adder circuitry 117, 118 is therefore the same as
15 adder circuitry 103, 104, namely to accomplish a subtraction ~
16 of the input thereto of shift register 115 from the input ~ -
17 thereto of cable 24.
18 Similarly, adder circuitry 123, 124 including inverters
19 125, 126 and carry-in input 127 operate to subtract the out-
puts of circuits 103, 104 from the outputs of circuits 117,
21 118. The net result is supplied on output cable 29~ All of
22 the subtracting circuitry comprising circuit 103, 104, cir-
23 cuit 117, 118, and circuit 123, 124 combine the tabular values
24 from cables 23 and 24 with the value of'the evènt designation
number on cable 11 to generate a codeword on cable 29. Sev-
26 eral shifting operations may be involved before the codeword
27 appropriate for the event designation appearing on cable 11
28 and line 12 is developed on cable 29. The presen~e of the
29 appropriate codeword is recognized by the absence of a signal
SA973013 -15- -
. ~; . . ~ :
~04ZS53
1 from OR circuit 102 on line 111. The prcsence of a codeword
2 on cable 29 is indicated to shift out circuit 17 by a signal
3 on line 27, and the length of the codeword is designated by
4 the contents of counter 130, which appears on cable 28. Since
every codeword reguires at least one bit, counter 130 is
6 initially loaded with the binary value 0001, which is repre-
7 sented by inputs 131 thereto.
8 The operation of the circuitr~ of Figure 3 is
9 controlled by latches 135 and 136 and by clocked latch 138.
Upon latch 138 being in the reset state, the absence
11 of a signal from the set output thereof disables AND circuit
12 141 to thereby block any clock pulses from AND circuits 112
13 and 144. The encoder 14 can therefore neither receive event
14 designation numbers on cable 11 nor transfer code words on
cable 29. Hence, when latch 138 is reset, encoder 14 is
16 said to be in the "disabled" state.
17 Upon latch 138 being set, the signal from the set
18 output thereof enables AND circuit 141 to transmit clock
lg pulses from clock 110 to AND circuits 144, 112 and I43, and
or. line 26. The encoder is thus "enabled" and the operation
21 of the encoder is detemined by latches 135 and 136.
22 If latch 135 is set while latch 136 is reset, the
23 circuitry of Figure 3 is ready to receive the event designa- ~ .
24 tion from the event recognizer 10. If both latches 135 and
136 are res~t, the circuitry of Figure 3 is in the process
26 of selecting the pre-established values from the table read- -
27 out circuitry and combining those values with the evlent
28 designation value. If latch 136 is set while 135 is reset,
29 the selection and combination has been completed and a signal .
.:
.... ~,, .
SA973013 -16-
.,
.. ..
ZS53
1 is provided on line 27 to indicate that the resultant
2 codeword is ready for transfer to shift out circuitry 17.
3 These three states of latches 135 and 136 are designated
4 "ready to receive," "selecting" and "ready to transfer."
The fourth state of these latches, in which both are set,
6 cannot occur.
7 The function control circuitry of the apparatus of
8 Figure 3 will now be described. At the beginning of a day's
9 operation, the circuitry must be initialized. First, a re-
set signal is supplied at input 32. This signal is supplied
11 to input 137 of clocked latch 138 and to one input of AND
12 circuit 139. Upon occurrence of the next clock pulse from
13 clock 110 at input 140, latch 138 is reset. This prohibits any
14 further outputs therefrom and thereby blocks gate 141. The
reset signal is also applied tG AND circuit 139 to gate the
16 same clock pulse to OR circuit 142. OR circuit 142 then
17 transmits the clock pulse to set latch 135, and to reset
18 latch 136. The latches are therefore in the "ready to re-
19 ceive" state. Upon termination of the reset pulse, a start
signal is supplied at input 39 to therefore set latch 138
21 upon occurrence of the next clock pulse from clock 110.
22 ~atch 138 thus operates AND circuit 141 to transmit subsequent
23 clock pulses to line 26, to AND circuit 143, and to AND cir-
24 cuits 112 and 144. The encoder 14 is thus placed in operable
condition to receive event designations from event recognizer
26 10.
27 An event designation comprises presence or lack of a
28 special designation signal on line 12, the presence of an
29 even`t designation number on cable 11, and the appearance of
S~973013 -17-
iO42S53
1 a signal at line 13. The signal on line 13 indicates that
2 the event designation is present on line 12 and cable 11.
3 Thus, when latches 135 and 136 are in the "ready to receive"
4 state, so that the set output from latch 135 provides an i
enabling input to AND circuit 144, a signal on line 13 enables
6 AND circuit 144 to thereby gate a clock pulse appearing from
7 AND circuit 141 to OR circuit 145. The first clock pulse so
8 enabled is supplied by AND circuit 144 to event recognizer 10
9 over line 15 to thereby indicate that the event designation
is being accepted. That signal is also supplied to reset the
11 latch 135, as will be explained. The clock pulse is addi-
12 tionally supplied on line 20 to the clock inputs of shift ~ -
13 register 115 and shift register 100, 101, and to counter 130.
14 The operational signal from latch 135 Qn line 21 is also sup-
plied to the load inputs of the same circuits. These circuits
16 are arranged such that the signals at the data inputs thereto
17 will be loaded into the registers or counter upon the com- -
18 bination of the load signal and a clock pulse. Thus, the
19 fixcd inputs to shift rcgistcr 115 arc loadcd, thc cvcnt
designation from cable 11 together with various fixed signals
21 are loaded into shift register 100, 101, and the fixed count
22 is loaded into counter 130. As will be explained, the com- -
23 bination of the signal on line 21 and the pulse on line 20
24 also operates the circuitry of encoded encoder 16 to load
the table readout circuitry. Thus, initial outputs are re-
26 ceived on cables 23 and 24 therefrom and supplied to the
27 subtraction equivalency circuits 103, 104 and 117, 118. The
28 outputs of these circuits are supplied to circuits 123, 124
29 which produces an output on cable 29.
, ~
SA973013 -18-
.. .
.
: . . . ' . ' ' '
, ~
-
104~S53
1 As mentioned above, the clock pulse supplied by
2 AND circuit 144 to event recognizer 10 over line 15, which
3 is gated by a signal on line 13 when latches 135 and 136
4 are in the "ready to receive" state, that is when latch 135
is set and latch 136 is reset, also serves to reset latch
6 135. This, together with the reset condition of latch 136,
7 designates the "selecting" state~
8 When latches 135 and 136 are in the "selecting" state, :: -
9 the reset outputs from these two latches provide enabling
inputs to AND circuits 112 and 143. So long as OR circuit
11 102 generates a positive signal, which indicates that the
12 outputs on cable 29 do not represent the codeword for the
13 previously received event designation, line 111 provides an
14 enabling input to AND circuit 112 and inverter 149 disables
15. AND circuit 143. In such cases, a clock pulse appearing
16 from AND circuit 141 is gated through AND circuit 112 and OR
17 circuit 145 to line 20. This clock pulse, together with the
18 absence of a signal from the reset output of latch 135,
19 causes counter 130 to be incremented, causes shift register
100, 101 to be shifted right by one position, causes shift
21 register 115 to be shifted right by one position, and as will
22 be explained, causes the table readout circuitry to alter
23 the outputs on cables 23 and 24. The resulting contents of
24 shift circuitry 100, 101 and 115, together with the new
values on cables 23 and 24, supply new inputs to subtraction
26 equivalency circuits 103, 104 and 117, 118, and the outputs
27 from these circuits provide new inputs to circuits 123, 124,
28 which in turn generate new outputs on cable 29. Addi- -:
29 tionally, the altered contents of shift register 100 and
SA973013 -19-
2SS3
1 the new carry ~rom adder 107, which is inverted by
2 inverter 106, provide new inputs to OR circuit 102.
3 When latches 135 and 136 are in the "selecting"
4 state, so that the reset outputs from both latches provide
enabling inputs to AND circuits 112 and 143, the absence
6 of a positive signal from OR circuit 102 disables AND
7 circuit 112 and causes inverter 149 to enable gate 143.
8 In such cases a clock pulse from AND circuit 141 sets ~.
9 latch 136. This, together with the reset condition of
latch 135, designates the "ready to transfer" state.
11 When latches 135 and 136 are in the "ready to .
12 transfer" state, so that latch 135 is reset and latch 136 ;` ~
13 is set, the set output from latch 136 provides a signal ~ - --
14 on line 27 to shift out circuit 17. Shift out circuit 17
15 answers the signal on line 17 by supplying an accept pulse ` :-
16 on line 25~ This pulse is transmitted by OR circuit 142
17 to set latch 135 and reset latch 136, thereby returning
18 these latches to the "ready to receive" state. .
19 Encoder tables 16 of Figure 1 are illustrated in .. . .
20 detail in Figure 4. .
21 The encoder tables include a series of plugboards .
22 150-153, the outputs of which are selectively gated by gat- :
23 ing circuits 154-157 and OR circuits 158 and 159 to matrix
24 routers 160 and 161. The plugboards 150-153 comprise stan-
dard commercially available plugboards which may be wired in
26 accordance with a desired code. An example of such a code
27 will be illustrated hereinafter. Plugboards 150 and 152
28 represent the pre-established values.to be selected for
29
SA973013 -20-
. . .. . . . .
, . . .
.
~04ZSS3
1 s~ccial ~v~nts. Pluc3boards 151 and 153 comprisc the
2 pre-established values to be selectcd for regular ovcnts.
3 Special event line 22 is supplied directly to inputs
4 162 and 163 of gate circuits 154 and 156. It is also sup-
plied via inverters 164 and 165 to inputs 166 and 167 of
6 AN~ gates 155 and 157. Thus, upon the appearance of a spe-
7 cial event indicator signal on line 22, AND gates 154 and
8 156 are operated to supply the outputs 168 and 169 of plug-
9 boards 150 and 152 to OR circuits 158 and 159. Inverters
164 and 165 invert the special input signal to block gates
11 155 and 157 from supplying outputs 170 and 171 from plugboards
12 151 and 153 to OR circuits 158 and 159. Similarly, when the
13 event is recognized as regular instead of special, the lack
14 of a signal on line 22 blocks gates 154 and 156 and is inverted
by inverters 164 and 165 to operate gates 155 and 157 to
16 transmit the information at the outputs of plugboards 151
17 and 153 to the OR circuits 158 and 159~
18 The OR circuits transmit all information gated
19 thereto over the corresponding outputs 175 and 176 to the :
respective matrix router 160 or 161. The routers then
21 supply the signals over the respective output lines 180 or
22 181 to shift registers 182. Finally, these signals on lines ~;
23 180 and 181 are loaded into shift registers 182 in response ::
24 to a pulse on line 20 in conjunction with a load signal on ::
line 21. Shift register 182 are then operated by pulses on
26 line 20, and the absence of a load signal on line 21, to
27 sequence through the loaded pre-established table values
28 until the values on cables 23 and 24 are those corresponding
29
SA973013 -21-
.:
lO~ZSS3
1 to the event designation to be encoded. Thus,the gate
2 and OR circuits are employed to select the proper set of
3 plugboards and the routers are employed to arrange the out-
4 puts of the plugboards in the proper sequence for selection
by the encoder 14 through cables 23 and 24 in response to
6 shift pulses on line 20 to shift registers 182.
7 Routers 160 and 161 are shown respectively in Figures
8 5 and 6. The routers illustrated comprise simply a matrix
9 connection between the output lines 175 and 176 of OR circuits
158 and 159 to the inputs 180 and 181 of shift registers 182.
11 Using router 161 in Figure 5 as an example, the eighth bit of -~
12 input t(7), counting from the left, becomes QUtpUt ETl. The
13 seventh bit in each of t(6) and t(7), again counting from
14 the left, becomes outputs ET2. The number of lines repre- -
sented by ET3, ET4, ET5, ET6 and ET7 are seen to increase by
16 one until ET7 is reached. ET7 thus includes 7 lines. ET8
17 also has 7 lines, which are the high order bit position of
18 each of the plugboard outputs, t(l) through t)7). The router
19 of Figure 6 is arranged in the identical manner to that of
Figure 5.
21 ~eferring now to Figure 7, the various shift registers
22 are illustrated. The router outputs as contained in cable 181
.
23 and comprising outputs EBl through EB8 from router 176 are -
24 connected to shift registers 191 through 198 respectively.
25 Similarly, the router outputs comprising cable 180 and com- ;
26 prising individual outputs ETl through ET8 from router 175
27 are connected to the shift registers 201 through 208, respec-
28 tivelyO The shift registers are all arranged so that the ~-
29 combination of the signal on line 21 accompanied by a clock
SA973013 -22-
':
.... r . . , " ' :~: .
il~l4ZSS3
1 pulse on line 20 loads the shift registers with the
2 information compri~ing cables 181 and 180. Certain load
3 input positions of each shift register are designated as "0"
4 and are connected to an appropriate permanent voltage to
designate the binary 0. An example is connecting these in-
6 puts to ground. The combination of the signal on line 21
7 with the clock pulse on llne 20 similarly loads the zero
8 inputs into the shift registers. As is seen, the rightmost
9 bit from each of shift registers 191-198 are provided on
cable 23 and the rightmost bits of shift registers 201-208
11 are supplied on cable 24.
12 Should OR circuit 102 in Figure 3 indicate by a signal
13 on line 111 that the pre-established values corresponding to
14 the event designation are not yet present on cables 23 and
15 24, the signal on line 111 gates a clock pulse from clock -
16 110, via AND circuit 112 and OR circuit 145 to line 20. The -~
17 clock pulse, accompanied by the absence of a signal on line
18 21, operates all of the shift registers 191-198 and 201-208, ~-
19 causing them to shift one bit to the right. Thus, a new set
of data is supplied from the shift registers on cables 23 and
21 24. The shifting continues until such time as OR circuit 102
22 in Figure 3 indicates that the pre-established values corre-
23 sponding to the event designation have been selected.
24 Figure 8 illustrates the shiftout circuitry 17 in
greater detail. As will be explained, the codeword on cable
26 29 and the corresponding codeword length on cable 28 are
27 loaded into shift register 224 and counter 223, respectively,
28 in response to a clock pulse transmitted on line 26. Subse-
29 quently, as will be explained, clock pulses appearing on -
SA973013 -23-
: . . : . .
:
~04ZS53
1 line 42 cause shift register 224 to be shifted le~t so
2 that successive bits of the codeword become available on
3 line 40. The clock pulses on line 42 also serve to decre-
4 ment counter 223, which is used to indicate when the en-
tire codeword has been transmitted over line 40.
6 The operation of the shiftout circuitry 17 in
7 Figure 8 is controlled by latches 212 and 213, in much the -
8 same way that latches 135 and 136 control the operation of ~
9 the encoder in figure 3. If latch 212 is set and latch 213 ~-
10 is reset, then shift out circuit 17 is ready to receive a ~ -
11 codeword and the corresponding codeword length from encoder
12 14 on cables 29 and 28, respectively. If latch 212 is re- - -
13 set and latch 213 is set, then shift out circuit 17 is either -~ -
14 ready to transmit the codeword or is in the process of serial
15 transmission of the codeword over line 40. These two states ~- -
16 of latches 212 and 213 are called the "ready to receive" and
17 the "ready to transmit" states, respectively. Since the clock
18 pulses appearing on lines 26 and 42 may well be derived from ~-~
}9 different clocks, timing considerations require a third state - ;
for latches 212 and 213, called the "transitional" state, in
21 which both latches are reset. The latches are never simul-
22 taneously set.
23 Reset input line 33 to shift out circuit 17 is
24 connected to the reset input 30 of Figure 1 and is connected,
via OR circuits 210 and 211, to latches 212 and 213. Thus,
26 a reset signal serves to reset both latch 212 and 213,
27 thereby placing the circuit in the "transitional" state.
28 When latches 212 and 213 are in the "transitional"
29 state, so that both latches are reset, the reset output of
SA973013 -24-
,, , ,, . , ' , `~
' ~ ' '
1042SS3
1 latch 212 on line 217 and the reset output of latch 213
2 on line 218 serve as enabling inputs to ~ND circuit 215.
3 Also, the absence of a signal from the set output from
4 latch 212 on line 220 serves to disable AND circuit 216.
Thus, when latches 212 and 213 are in the "transitional"
6 state, a clock pulse appearing from encoder 14 on line 26
7 is transmitted via AND circuit 215 to set latch 212, thereby
8 placing latches 212 and 213 in the "ready to receive" state.
9 When latches 212 and 213 are in the "ready to
receive" state, so that latch 212 is set and latch 213 is
11 reset, the set output from latch 212 on line 220 provides
12 an enabling input to AND circuit 216, while the absence of
13 a signal from the reset output of latch 212 on line 217
14 serves to disable AND circuit 215. Additionally, the signal
on line 220 provides a load enable input to counter 223 and
16 shift rPgister 224.
17. Encoder 14 indicates that a codeword and the
18 corresponding codeword length are available on cables 29 ~ -
19 and 28, respectively, by supplying a signal on line 27.
This signal serves as an enabling input to AND circuit 216
21 in Figure 8. If latches 212 and 213 are in the "ready to
22 receive" state, so that the set output of latch212 on line
23 220 provides an enabling input to AND circuit 216, then the.
24 clock pulse from encoder 14 on line 26 immediately follow-
ing the appearance of a signal on line 27 is gated by~AN
26 circuit 216 to O~ circuit 221, and thereby to counter 223
27 and shift register 224. This signal operates in conjunction
28 with the set output from latch 212 on line 220 to load the
29 information on cables 28 and 29 into counter 223 and shift
S~973013 -25-
.
. : : ~ . ; . ,,
104;~553
1 register 224, respectively. The clock signal gated by
2 AND circuit 216 is additionally supplied on line 25 to
3 encoder 14 to thereby indicate that the information on
4 cables 28 and 29 has been accepted and loaded into counter
223 and shift register 224. Lastly, the clock signal gated
6 by AND circuit 216 serves to set latch 213 and is trans-
7 mitted via OR circuit 210 to reset latch 212, thereby placing
8 the latches in the "ready to transmit" state.
9 When latches 212 and 213 are in the "ready to
transmit" state, so that latch 212 is reset and latch 213
11 is set, the absence of a signal from the set output of
12 latch 212 on line 220 serves to disable AND circuit 216
13 and the absence of a signal from the reset output of latch
14 213 on line 218 disables AND circuit 215. Also,the absence
of a signal on line 220 serves as a count enable input to
16 counter 223 and a shift enable input to shift rcgister 224. ~ -
17 The set output of latch 213 supplies a si~nal on line 41 to
18 the transmission link, data storage device, or decodcr 51
19 in Figure 2, which responds by supplying clock pulses on
line 42. These clock pulses are transmitted via OR circuit
21 221 to decrement counter 223 by one and to shift the con-
22 tents of shift register 224 to the left by one bit position.
23 The clock pulses are also transmitted to AND circuit 228,
24 which is disabled by O~ circuit 226 until the contents of
counter 223 is reduced to 001. When the contents of counter
26 223 is reduced to 001, which indicates that only one bit of
27 the codeword in shift register 224 remains to be transmitted
28 on line 40, a clock pulse on line 42 is gated ~ AND cir-
29 cui~ 228 and OR circuit 221 to reset latch 212, thereby
SA973013 -26-
10425S3
1 returning latches 212 and 213 to the "transmit" state.
2 Referring now to a specific example of decoding
3 circuitry 51 and decoder special tables 52 and decoder
4 regular tables 53, Figures 9 through 17 wlll be discussed.
Referring first to Figure 9, an implementation of
6 encoder 51 is shown which employs standard semiconductor
7 modular elements. Input line 61 is connected to AND circuits
8 230 and 231. A signal is present on line 61 so long as
9 serial data is supplied therewith on line 60 to inputs 232
and 233 of shift léft register 234. When the initial bit
11 of the serial data appears on line 60, shift left register
12 234 loads that bit from line 232 into the rightmost bit
13 position of the register, as will be explained. The re- -
14 maining bit positions of the register are loaded with zeroes
from permanently affixed voltages at the inputs thereto.
16 For all subsequent bits of the codeword, shift left register
17 234 shifts to the left and shifts in the successive bits
18 on line 60 via shift-in input 233. Acceptance output pulses
19 are supplied on line 62 from OR circuit 235.
The contents of shift left register 234 are supplied
21 to adders 240 and 241 and to adders 242 and 243. The other
22 input to adders 240 and 241 comprises cable 74 from decoder
23 special tables 52, after first being inverted by inverters
24 245, 246. The other inputs to adder 242, 243 comprise
cable 76 from decoder regular tables 53 and are supplied
26 via inverters 247, 248. The carry-in input 250 to adder
27 240, 241 and the carry-in input 251 to adder circuitry
28 242, 243 are each supplied from a fixed voltage represent-
29 ing a binary "1". As with respect to similar adder
SA973013 -27-
104'~SS3
1 circuitry in Figure 3, the function of this resultant
2 adder circuitry, inverters, and carry-in is to subtract
3 the binary value supplied to the inverted inputs from the
4 binary value supplied to the regular inputs. As with
respect to the adders in Figure 3, the subtraction is ac-
6 complished by the adders in accordance with a well-known
7 binary relationship of adding the complement of the number
8 to be subtracted to the number from which it is to be sub-
9 tracted, and adding a binary 1 thereto.
The selection of the proper table values from the
11 table readout circuitry thereof is controlled by AND cir-
12 cuit 231. The table readout and selection circuitry is of
13 significantly lower cost than the random access type as it
14 is of the se~uential access type. Thus, clock pulses from
a clock 255 sequences the table readout circuitry, as will
16 be explained hereinafter, via the control of the output of
17 AND circuit 231 under the more direct control of the output
18 of subtractor 240, 241 on line 256, until the table values
19 corresponding to the codeword supplied on input 60 is
reached.
21 The output of subtraction unit 240, 241 is supplied -
22 to adders 260 and 261. Circuits 260 and 261 function as
23 adders, with the fixed voltage representing a binary 1 at
24 carry-in input 262 thereto. The adders thus add the result
of the subtraction at subtraction e~uivalency unit 240, 241
26 to thc output from docoder speoial tables 52 on cablc 75
27 and additionally add to that sum the binary 1 from line 262.
28 The output of the adders is supplied to gate circuit 263.
29 Thus, upon the appearance of a positive signal on line 264,
SA973013 -28
"` ~0~%SS3
1 the output of adders 260 and 261 is gated thereby to OR
2 circuit~ 265.
~ ~i.mil.lrly, thc ouLI)u~ o~ su~)Lr.lcL.ion uniL 2~2, 243
4 is supplied to adder circuits 270 and 271. Another input
to the adder circuits comprises the output from decoder
6 regular tables 53 on cable 77. The carry-in input 272 to
7 the adder circuit is connected to a fixed voltage represent-
8 ing a binary "1". Thus, the addition function of adders
9 270 and 271 is identical to the function of adders 260 and
10 261 with the exception that they are operating with respect :~
11 to the values from the decoder regular tables 53 as opposed -~
12 to the decoder special tables 52 for adder circuits 260, 261. : .
13 The output of adders 270, 271 is supplied to gate
14 circuit 273. The gating lnput 274 thereto is connected to
inverter 275. Thus, the carry output signal on line 276
16 from the subtraction unit 242, 243 operates gate circuit 263
17 when the signal is positive and, via inverter 275, operates
18 gate circuit 273 when the signal is negative. The outputs ~ :
19 of gate circuits 263 and 273 are supplied to the inputs of ~. :
20 OR circuits 265, and the resultant output signal therefrom -
21 comprises the event designation number on cable 80. The
22 carry output signal on line 276 from subtraction circuitry ~:`
23 242, 243 comprises the special or regular event designation
24 signal and is supplied additionally on line 81.
The operation of decoder 51 in Figure 9 is controlled
26 by clocked latch 286 and by latches 280 and 281 in much the
27 same way that latches 140, 135 and 136 control the apera-
28 tion of encoder 14 in Figure 3. If latch 386 .is reset, -
29 then the absence of a signal from the set output therefrom ~ ~ -
SA973013 . -29-
-` ~()425S3
1 on line 284 disables AND circuit 289, so that no clock pulses are
available on line 290. In this case decoder 51 can neither receive
codewords on line 60 nor transfer event designations on cable 80 and
line 81. Hence, when latch 286 is reset, decoder 51 is said to be
in the "disabled" state.
On the other hand, if latch 386 is set, then the signal on line -. -
284 enables AND circuit 289 to transmit clock pulses to line 290. In
this case the operation of decoder 51 is determined by latches 280 and ~ -
281. If latch 280 is set and latch 281 reset, decoder 51 is ready to
receive the first bit of a codeword on line 60. If latches 280 and
281 are both reset, decoder 51 is in the process of receiving a code- :
word on line 60 and combining this codeword with table values appearing
on cables 74-77 to determine an event designation for cable 80 and
line 81. If latch 280 is reset and latch 281 is set, then a codeword -
has been decoded, and the resulting event designation on cable 80 and -
line 81 is ready to be transferred to event regenerator 50. These
three possibilities, occurring in conjunction with the set condition
of latch 286, determine the "ready to receive", "combining" and "ready
to transfer" states, respectively, for decoder 51.
At the beginning of a day's operation, decoder 51 in FIGURE 9
is initialized by a reset signal on line 92 followed by a start signal
on line 96. As will be shown, this sequence of two signals places
decoder 51 in the "ready to receive" state. First, the reset signal
on line 92 is supplied to input 285 of latch 286 and to one input of AND
SA9-73-013 - 30 -
, . . ~
" ' ' ", ', :; , ' , ' .
~`` 1042SS3
1 circuit 287. The next clock pulse from clock 255 on line 288 serves
to reset latch 286, thereby placing decoder 51 in the "disabled"
state. This same clock pulse is also gated by AND circuit 287 via OR
circuit 291 to set latch 280 and to reset latch 281. Second, the start
signal on line 96 is supplied to input 294 of latch 286, so that the
next clock pulse from clock 255 on line 288 serves to set latch 286.
The resulting set condition for latches 286 and 280, together with the
reset condition for latches 286 and 280, together with the reset con-
dition of latch 281, constitute the "ready to receive" state for
decoder 51.
Upon decoder 51 being in the "ready to receive" state, latches
286 and 281 are set while latch 281 is reset. Then the set output of
latch 286 on line 284 gates clock pulses from clock 255 onto line --
290 via AND circuit 289. Also, the set output of latch 280 on line
300 provides an enabling input to AND circuit 230 and serves as a
load enable input to shift register 234, while the absence of a reset
output from latch 280 on line 305 serves to disable AND circuit 295.
The signal on line 300 is additionally transmitted via line 71 to
decoder special tables 52 and via line 73 to decoder regular tables -
53. So long as no signal is present on line 61, AND circuits 230 and -
231 are disabled and decoder 51 remains in the "ready to receive"
state. However, when a signal appears on line 61, which indicates
that the first bit of a codeword is available on line 60, a clock
pulse appearing on line 290 is gated via AND circuit 230 and OR circuit
235 to line 302. This clock pulse on line 302, in conjunction with
the signal on line 300,
SA9-73-013 - 31 -
.. . . . .
"` 104ZSS3
1 serves to load the codeword bit appearing on line 60 into the right-
most bit position of shift register 234, via load input 232. Simul-
taneously, the remaining positions of shift register 234 are loaded
with zeroes from permanently affixed inputs. As will be described,
the combination of a clock pulse on line 302 and a signal on line 300,
which is conveyed to decoder special tables 52 and decoder regular tables
53 via lines 70-73, causes table shiftout circuitry to be loaded, so
that table values are presented on cables 74-77. The clock pulse on
line 302 is additionally transmitted via line 62 to acknowledge accep-
tance of the first bit of a codeword. And finally, the clock pulse online 302 serves to reset latch 280, thereby placing decoder 51 in the
"combining" state.
Upon decoder 51 being in the "combining" state, latch 286 is set
and latches 280 and 281 are reset. Then the set output of latch 286 on ~ -line 284 gates clock pulses from clock 255 onto line 290 via AND circuit
289. Also, the reset output from latch 281 on line 302 provides an
enabling input to AND circuits 231 and 295, the reset output of latch
280 on line 305 provides an enabling input to AND circuit 295 and the
lack of a set output from latch 280 on line 300 serves to disable AND
circuit 230. In the manner previously described, the contents of shift
register 234 are combined with table values appearing on cables 74-77
to yield outputs on cable 80 and line 81. These outputs on cable 80
and line 81 constitute an event designation only if the table value
appearing on cable 74 exceeds the value in shift register 234, so that
the carry output
SA9-73-013 - 32 -
;, .. . ..... .
~ . . . . . . .
.
~ ~04ZS53
1 from subtraction e~uivalency circuit 240, 241 is zero. In
2 this case, the absence of a signal on line 2S6 serves to i ;
3 disable AND circuit 231, and inverter 304 provides an cn-
4 abling input to AND circuit 295, so that a clock pulse ap-
pearing on line 290 is gated via AND circuit 295 to reset
6 latch 281. This places decoder 51 in the "ready to transfer"
7 state.
8 On the other hand, if decoder 51 is in the "combining" -
9 state, the presence of a signal on line 256 indicates that
the outputs on cable 80 and line 81 do not constitute an
11 event designation. This means that register 234 does not
12 contain a complete codeword, and that additional codeword
13 bits must be input via line 60. In this case the signal on
14 line 256 provldes an enabling input to AND circuit 231 and,
in conjunction with inverter 304, serves to disable AND
16 circuit 295. So long as no signal is present on line 61,
17 AND circuit 231 is disabled and decoder 51 remains in the
. . . ~ ., . - . . .
18 "combining" state. HGwever, when a signal appears on line
19 61, which indicates that the next codeword bit is available
20 on line 60, a clock pulse appearing on line 290 is gated via -~
21 AND circuit 231 and OR circuit 235 to line 302. This clock
22 pulse on line 302, together with the absence of a set output
23 from latch 280 on line 300, causes shift register 234 to
24 shift left one bit position, shifting the codeword bit
appearing on line 60 into the rightmost bit position via
26 shift input 233. As will be described, the combination
27 of a clock pulse on line 302 and the absence of a signal
28 on line 300, which is conveyed to decoder special tables
29 52 and decoder regular tables 53 via lines 70-73, causes
. ,:
~ ' .
SA973013 -33-
., . . . , .. , ,, . . ; .
1042553
1 new table values to be presented on cables 74-77. The clock pulse on
line 302 is additionally transmitted via line 62 to acknowledge accep-
tance of the codeword bit. This clock pulse on line 302 also provides
a reset input to latch 280, so that decoder 51 remains in the "combining"
state.
Upon decoder 51 being changed to the "ready to transfer" state,
latches 286 and 281 are set while latch 280 is reset. Then the set out-
put of latch 286 on line 284 gates clock pulses from clock 255 onto line
290 via AND circuit 289. If latch 282 is set, then the set outputs from
latches 281 and 282 cause AND circuit 285 to provide a signal on line
82, which is transmitted to event regenerator 50. The signal on line 82
indicates the presence of an event designation on cable 80 and line 81. -
Acceptance of this event designation by event regenerator 50 is acknow-
ledged by a pulse on line 83, which serves to reset latch 282. When
decoder 51 is in the "ready to transfer" state and latch 282 is reset,
the reset output of latch 282 provides an enabling input to AND circuit
293. In this case, a clock pulse appearing on line 290 is gated through
AND circuit 293 onto line 296. The clock pulse on line 296 serves reset
latch 282, and this clock pulse is also transmitted via OR circuit 291
to set latch 280 and to reset latch 281, thereby placing decoder 51 in
the "ready to receive" state.
Reference will now be made to Figures 10-17 for descriptions of
the decoder tables 52 and 53 of FIGURE 2.
SA9-73-013 _ 34 _
, . ~......... ' ' .
1 Figures lQ aln8~ ~S~ustrate each of the elements
2 of the special tables and regular tables, respectively, in
3 block diagram form. The decoder tables include a set of
4 plugboards 310 and 311 in Figure 10 and 360 and 361 in
Figure 14. The outputs 312 and 313 in Figure 10 and 362
6 and 363 in Figure 14 are supplied directly to the appro-
- 7 priate matrix routers 314, 315 and 364, 365, respectively.
8 The plugboards 310, 311 and 360, 361 comprise standard com-
9 mercially available plugboards which may be wired in accor-
dance with a desired code, which must correspond with the
11 code of the encoder. Indeed, plugboards 310, 311, 360 and
12 361 may be the same plugboards 150, 152, 151, 153 used by
13 the encoder tables 16 as shown in Figure 4.
14 Plugboards 310 and 311 represent the pre-established ~-
values for special event codewords. Plugboards 360 and 361
16 represent the pre-established values selected for regular
17 event codewords. The matrix routers 314, 315 in Figure 10
18 and 364, 365 in Figure 14 route the signals from the plug-
19 boards over the respective output lines 320, 321 and 370,
371 to shift registers 323 and 373. The shift registers
21 are then operated by the pulses on lines 70 and 72 in the
22 presence of signals on lines 71 and 73 to load the output
23 signals of the associated plugboards, and operated by pulses ~-
24 on line 70 and on line 72 in the absence of signals on lines ;
71 and 73 to sequence through the loaded signals until the
26 pre-established values on cables 74-77 are those aorrespond-
27 ing to the received codeword, The matrix routers are em-
28 ployed in this operation to arrange the outputs of the plug-
29 boards in the proper sequence for selection by the decoder
SA973013 -35-
.. . .
i04ZSS3
1 51 through the supply of pulses on lines 70 and 72 to shift
2 registers 323 and 373.
3 Matrix routers 314 and 315 are shown, rcspectively,
4 in Figures 11 and 12. Matrix routers 364 and 365 are shown,
respectively, in Figures 15 and 16. The routers illustrated
6 comprise simply a matrix connection between the plugboard
7 output lines and the inputs of the corresponding shift regis-
8 ters. Specifically, matrix router 314 of Figure 11 connects
9 the output lines 312 from TS plugboard 310 to lines 320 of
shift registers 323. Matrix router 315 of Figure 12 connects
11 the output lines 313 of plugboard 311 to inputs 321 of shift
12 registers 323. Matrix router 364 of Figure 15 connects out-
13 put lines 362 of plugboard 360 to inputs 370 ofshift regis-
14 ters 373. Matrix router 365 of Figure 16 connects the output
lines 363 of plugboard 361 to inputs 371 of shift registers
16 373.
17 Using router 314 of Figure 11 as a specific example,
18 the eighth bit of each group of wires TS(l) through TS (7),
19 counting from the right, is supplied as the output of group
of wires DTS8. In this instance, only the wire corl~prising
21 bit position TS(7) has a wire therefrom to shift register
22 input DTS8. The number of bits connected to the shift regis-
23 ter inputs progressively increases by one until each of the
24 various plugboard outputs is connected to the shift register
input DTS2 and DTSl. Shift register DTSl is thus connected
26 to the rightmost bit position of each of the plugboard out-
27 puts. The routers of Figures 12, 15 and 16 are arranged in
28 the identical manner to that of Figure 11.
29
' ~ ' .
SA973013 -36-
,
104ZSS3
1 Referring now to Figures 13 and 17, the various
2 shift registers are illustrated. The router outputs as
3 contained in cable 320 and comprising outputs DTSl through
4 DTS8 are connected to shift registers 331-338, respectively.
Similarly, the router outputs comprising cable 321 and com-
6 prising individual outputs DBSl-DBS8 are connected to shift --
7 registers 341-348 respectively. With respect to Figure 17,
8 the router outputs contained in cable 370 and comprising
9 outputs DTRl-DTR8 are connected to shift registers 381-388
respectively. Similarly, the router outputs comprising
11 cable 371 and comprising individual outputs D9Rl-DBR8 are
12 connected to the shift registers 391-398, respectively. All
13 of the shift registers are arranged so that the c~mbination
14 of the signal on line 71 or on line 73 accompanied by a
clock pulse on line 70 or on line 72 loads the shift registers
16 with the information then present on cables 320 and 321 or
17 on cables 370 and 371. As indicated, certain positions of
18 each shift register are loaded with binary zeroes from -
19 permanently affixed voltages at the inputs thereto.
When shift registers 323 and 373 have been loaded
21 in response to clock pulses on lines 70 and 72 in thè pre-
22 sence of signals on lines 71 and 73, the rightmost bit posi-
23 tion of each shift register are presented to decoder 51 on
24 cables 74-77. In particular, the rightmost bit positions
of shift registers 331-338 in Figure 13 are connected to
26 cable 74, the rightmost bit positions of shift registers
27 341-348 in figure 13 are connected to cable 75, the right-
28 most bit positions of shift registers 381-388 are connected
29 to cable 76, and the rightmost bit position of shift
.
SA973013 -37-
. ~ , . .
.
`` 104Z553
1 registers 391-398 are connected to cable 77. After initial
2 loading of shift registers 323 and 373, clock pulses on
3 lines 70 and 72 in the absence of signals on lines 71 and
4 73 cause each of the shift registers to shift to the right
by one bit position. As a result, a new set of data is sup-
6 plied to cables 74-77.
7 The shifting continues until such time as the signal
8 on line 256 of the decoder circuitry of Figure 9 drops to
9 indicate that the pre-established values corresponding to the
supplied codeword have been selected.
11 An exemplary code is disclosed below, where i repre-
12 sents the regular event designation number, j represents the
13 special event designation number, cr(i) represents the binary
14 codeword representing the ith regular event, and cS(j) repre-
sents the binary codeword corresponding to the jth special
16 event. This exemplary code can be used for encoding any -
17 seven regular events and any two special events. For example,
18 the regular events may comprise seven various run lengths and
19 the special events may comprise an end-of-line indication and -
an end-of-page indication.
21 Exemplary Code
22 i cr(i) j cs(j)
23 1 00 1 01
24 2 100 2 101
25 3 1100
26 4 1101
27 5 1110
28 6 11110
29 7 11111
SA973013 -38-
,
,
1042S53
1 The implementation of the exemplary code to operate w~th the apparatus
illustrated in Figures 1-17 requires the plugboard values listed below.
As has been explained, when a signal is present on line 22, k clock
pulses supplied on line 20 to encoder tables 16 cause bS(k) and tS(k)
to appear, left justified, on cables 23 and 24. When a signal is not
present on line 22, k clock pulses supplied on line 20 to encoder tables
16 cause br(k) and tr(k) to appear, left justified, on cables 23 and 24.
Similarly, k clock pulses supplied on lines 20 and 72 to decoder special ~ -
tables 52 and decoder regular tables 53 cause tS(k), bS(k), tr(k) and
br(k) to appear, right justified, on cables 74-77. Also as has been
explained, exactly k clock pulses are supplied on line 20 to encoder
tables 16 during the generation of a k-bit codeword and exactly k clock -
pulses are supplied on lines 70 and 72 to decoder special tables 52
and decoder regular tables 53 during the decoding of a k-bit codeword.
Since the longest codewords in the exemplary code in Figure 18, namely
cr(6) = 11110 and cr(7) = 11111, comprise only 5 binary bits, plugboard ~
values br(6), tr(6), bS(6), tS(6), br(7)~ tr(7), ~s(7)' and tS(7) are ~-
never supplied on cables 23-24 or on cables 74-77 during the encoding --or decoding of the exemplary code. Therefore, these plugboard values
can be any binary sequence, and hence they are given in Table 2 as
xxxxxxx or xxxxxxxx.
SA9-73-013 - 39 -
.
.. :
,
, .
.
104ZSS3
l Table Values (Plugboard~
k br(i) tr(k) bS(k) ts(k)
00 00 00 00
2 001 001 001 010
3 0010 0101 0010 0110
4 OOlOl Ollll OOOlO Ollll
5OOOlll lO0000 OOOOlO lO0000
6xxxxxxx xxxxxxx xxxxxxx xxxxxxx
7xxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxx
The illustrated decoder table values are right justified. The ~
encoder tables are left justified. ~ -
The above exemplary code is arranged for encoding or decoding two
special events and seven regular events. Regular events may comprise
.~ .
seven various run lengths, and the special events may comprise an end-
of-line indication and an end-of-page indication. Many similar codes
may be developed and implemented in terms of table values such as
illustrated. Similar codes with longer codewords can be implemented
by simply expanding the circuitry of Figures 3-17 horizontally to include
~ additional bit capacity.
The routing circuitry for the encoder and decoder tables are - -
;~ arranged such that the plugboards for the encoder are identical to the
plugboards for the encoder and for the decoder would have to be arranged
somewhat differently, but contain the same information. Either arrangement
w111 work equally well although identical plugboards are envisioned as
being somewhat better from a pract1cal implementation standpoint.
,
SA9-73-013 - 40 -
- . . . . . . - .
.; . . . .. . . . . . .
104ZSS3
Thus, TS plugboard 150 in Figure 4 is identical to TS plugboard 3lO
in Figure lO. Similarly, TR plugboard lSl in Figure 4 is identical to
TR plugboard 360 in Figure l4. Further, BS plugboard 152 and BR plug-
board l53 in Figure 4 are respectively identical to BS plugboard 3ll
in Figure lO and BR plugboard 36l in Figure 14.
In order to better illustrate the correspondence of the above
table values with respect to the arrangement of the plugboards, the
output of TS plugboard l50 or TS plugboard 310 to the respective routers
of Figures 5 and ll will be explained. The output of router l50 is via
cable l75 in Figure 5 and the output of router 3lO is via cable 312 in
Figure ll. As is seen from the expansion of the table values for -
plugboard TS on cables l75 or 3l2, each individually labeled set of ~ ~-
wires comprising the cable represents a specific table value.
EXPANDED TS TABLE VALUES
k tS(k)
cables l75 or 3l2
t(l) t(2) t(3) t(4) t(5) t(6) t(7)
00
2 Ol~
3 OllO
4 Ollll
lO0000
6 xxxxxxx
7 xxxxxxxx
Referring now to the above table together wlth the router l60 of
Figure 5 and shift registers l82 of Figure 7,
SA9-73-0l3 - 4l -
iLO ~Z S S 3
1 the first table value t(l) ls supplied to the first bit position of shift
right registers 198 and 197 via sets of wires ET8 and ET7 of cable 180.
Table value t(2) is supplied to the second bit positions of shift right
registers 196-198 via wires ET6 - ET8 of cable 180. Each succeeding
table value is thus supplied by the corresponding ones of an ever ex-
panding set of wires of cable 180 to the next sequential bit position
of a correspondingly expanding set of the shift registers.
Thus, upon loading of the shift registers from plugboard 150 via
router 160, the initial outputs of the shift register on cable 23
comprises the left-justified table value t(l) followed to the right by
a series of zeroes. Each subsequent clock pulse to the shift registers
shifts to the next succeeding table value which is supplied in left-
justified mode on cable 23 followed by an ever decreasing number of
zeroes to the right.
Referring now to the output of plugboard 310 on cable 312 to
router 314 in routing of the signals therefrom on cable 320 to shift
registers 323, specific reference is made to Figures 11 and 13. The
organization of the router with respect to the above table of expanded ;
ts table values will now be explained. The decoder plugboard output is
identical to that of the previously described encoder.
Plugboard output t(l) is supplied on cable 312 and the bits are
respectively routed to the low order bit positions of shift registers
331 and 332 via the lines of cable 320 of groups of wires DTSl and
DTS2. Similarly, the next table value t(2) is routed to the second
binary position of
SA9-73-013 - 42 -
i
104;ZSS3
l shi~t right registers 331-333 via lines of groups of wires
DTSl-DTS3 of cable 320. Successive pre-established table
3 values are similarly supplied via sequentially increasing
4 numbers of wires to successive bit positions of successively
increasing numbers of the shift right registers 331-338.
6 Upon loading the shift registers, the first
7 pre-established table value, ts(l) is supplied from the
8 registers on the two rightmost wires of cable 74 with fixed
g zeroes in the remaining wires of the cable. Upon receipt of
a clock pulse, the shift registers shift to the right such
ll that pre-established value t(2) is supplied in right-justified -
12 form on cable 74 with fixed zeroes supplied in the remaining -
13 wires of the cable. Succeeding clock pulses supplied to the
14 shift registers cause further shifting, resulting in succes-
sive pre-established values being presented on cable 74 in
16 right-justified form with an ever decreasing number of fixed
17 zeroes on the remaining wires.
18 The resultant outputs of the encoder tables via cables
l9 23 and 24 of Figure 4, via cables 74 and 75 of Figure lO, and
via cables 76 and 77 of Figure 14 as the result of the opera-
21 tion of the associated plugboards, matrix routers and shift
22 re~isters.
23 The encoding and subsequent decoding of one of the
24 events in accordance with the exemplary code as implemented
in the exemplary circuitry of the above embodiment of the
26 invention will now be described.
27 Regular event number 5 comprises a suitable example.
28 Referring to Figure l, event recognizer lO supplies a signal
29 on line 13 together with the binary representation of the
SA973013 -43_
. .
104ZS53
1 number 5 on cable 11 and no signal on line 12. The 8-bit binary repre-
sentation of the decimal value of 5 is "00000101". In Figure 3, this
binary value is received on cable 11. Thus, the top three wires comprise
the binary voltages representing binary bits "101", with the remainder
of the wires having the voltage representing a binary "O".
When encoder 14 is in the "ready to receive" state, so that latch
13~ is set and latch 136 is reset, the signal on line 13 enables AND
circuit 144 to gate a clock pulse from clock 110, via OR circuit 145, to
line 20. This pulse together with the output of latch 135 on line 21, -
causes shift registers 100 and 101 to load the binary event designation
therein, causes shift register 115 to be loaded with the binary value
01000000, and causes counter 130 to be loaded with the binary value 0001.
As has been explained, the clock pulse on line 20 resets latch 135,
thereby placing encoder 14 in the "working" state.
The clock pulse on line 20 and the signal on line 21 in the absence
of the special event signal on line 22 causes the shift registers
182 of the encoder tables in Figure 4 to be loaded w~th the regular
event pre-established values. Thus, the encoder tables provide at that
time on cables 23 and 24 the outputs br(l) = 00 and tr(l) = 00 given ~ ~ -
in Figure 18. These pre-established table values are left-justified,
so that the outputs on cables 23 and 24 are both 00000000.
The contents of shift register 101, namely 01000000, is subtracted
by subtraction unit 103, 104 from the all-zero
SA9-73-013 - 44 -
.
10~2S53
output of cable 23. As the net result of this subtraction is less than
zero, the output of inverter 106 to OR circuit 102 is positive. The
output of OR circuit 102 on line 111 is therefore positive.
Since encoder 14 is in the "working" state, with latches 135
and 136 both reset, the signal on line 111 enables AND circuit 112 to
gate the next clock pulse from clock 110, via OR circuit 145, to counter
100, shift registers 100 and 101, and on line 20 to the encoder tables.
This clock pulse causes the encoder table shift registers to shift so
that the encoder table output on cables 23 and 24 comprises br(2) =
10 001 and tr(2) = 001 from ~igure 18, with both table values left-
justified. Simultaneously, shift registers 100 and 101 and shift
register 115 respond to the pulse on llne 20 and to the absence of the
signal on line 21 by shifting to the right one position, so that the
resulting contents of these shift registers are, respectively,
00000000, 10100000 and 00100000. Simultaneously, the clock pulse
increments counter 130 to the binary value 0010.
The subtractor comprising elements 103, 104 nsw subtracts the value - -
from shift register 101 (10100000) from the pre-established value on
cable 23 (00100000). As this result is negative, inverter 106 still
20 supplies a positive output to OR circuit 102. AND circuit 112 thus
gates the next succeeding clock pulse from clock 110 to shift register
115, shift register 100 and 101, to counter 130, and to the encoder
tables on line 20.
SA9-73-013 - 45 -
. . , ~ . ~
ZS53
1 The clock pulse on line 20 thus causcs thc shift
2 registers of the encoder tables to shift onc position and
3 to supply on output cables 23 and 24 the binary information
4 for K=3 as br(3~ = 0010 and tr(3) = 0101 from Figure 18, with
both table values left-justified. Shift register 115 shifts
6 the binary 1 one more position to the right of input line
7 116 so that the output therefrom is now 00010000. Shift
8 registers 100 and 101 also shift to the right one position
9 so that the resultant output of shift register 100 is all
zeroes and the output of shift register 101 is 01010000.
11 Counter 130 responds to the clock pulse by incrementing
12 the count by 1 to the binary value 0011.
13 The subtractor comprising elements 103, 104 now -
14 subtracts the contents of shift register 101 (01010000)
from the pre~established value on cable 23 (00100000). The -
16 resultant subtraction again results in a negative number
17 so that inverter 106 supplies a positive output via OR
18 circuit 102 to line 111. This signal again enables AND
19 circuit 112 to gate the next succeeding clock pulse from
clock 110 to line 20.
21 This clock signal causes the shift registers of the -
22 encoder tables to supply as the output therefrom on cables
23 23 and 24 the binary information br(4) = 00101 and tr(4) =
24 01111, again left-justified. This is illustrated in the
encoder tables of Figure 18 for k=4 at Columns Br and Tr,
26 respectively. Shift register 115 shifts the binary 1 an
27 incremental step further to the right of the original input
28 line 116. The resultant output of the shift register is
29 00001000. Shift registers 100 and 101 similarly are shifted,
SA973013 -46-
~04Z5S3
1 the output of shift register 100 still comprising all zeroes
2 and the output of shift register 101 then comprisi~g
3 00101000. Counter 130 is incremented to the binary value
4 0100. Now, the resultant subtraction by subtraction unit
103, 104 of the output of shift register 101 (00101000) from
6 the content of cable 23 (00101000) is no longer negative.
7 A positive output signal is thus supplied on line 105, which
8 is inverted by inverter 106. No positive outputs are there-
9 fore supplied to OR circuit 102 and no signal is supplied
on line 111. Thus, AND circuit 112 is disabled. The lack
11 of a signal on line 111 is inverted by inverter 149 to sup-
12 ply a positive enabling signal to AND circuit 143.
13 The next succeeding clock pulse from clock 110 is
14 therefore blocked by AND circuits 144 and 112, but is gated
by AND circuit 143 to set latch 136, thereby placing en-
16 coder 14 in the "ready to transfer" state. The resulting
17 output signal on line 27 indicates that the codeword is
18 present on cable 29 and the binary designation of the cod~e-
19 word length is present on cable 28.
The codeword on cable 29 is derived in the following
21 manner. The output of the subtraction unit comprising
22 elements 103, 104 is the result of the subtraction of the
23 contents of shift register 101 (00101000) fromthe content
24 of cable 23 (00101000). This net result is all zeroes
(00000000). The output of the subtraction unit 117, 118
26 comprises the subtraction of the output of shift register
27 115 (00001000) from the binary content of cable 24
28 ~01111000) as illustrated in Figure 18. The net result
29 supplied as the output of the subtractor 117, 118 is
SA973013 -47-
.
104Z553
1 01110000. The subtraction unit 123, 124 then subtracts
2 the output of the subtraction unit 103, 104 (00000000)
3 from the output of subtraction unit 117, 118 (01110000).
4 The net result of this subtraction, excluding the high
order bit of subtraction unit element 123, is 1110000.
6 The operation of the circuitry of Figure 3 has
7 thus resulted in the production of the appropriate code-
8 word (1110) left-justified on cable 29 together with the
9 codeword length (100) on cable 28. The generation of .
this codeword has required only five clock pulses, one
11 to load the shift registers, three to access successive ~-
12 pre-established table values, and one to set latch 136,
13 thereby indicating that the codeword has been generated.
14 Referring now to Figure 8, the signal on line 27
provides an enabling input to AND circuit 216. When the .
16 shiftout circuitry is in the "ready to receive" state, so
17 that latch 212 is set and latch 213 is reset, a clock .
18 pulse on line 26 is thus gated via AND circuit 216 to line
19 25. This pulse is routed via OR circuit 210 to the reset -~ :
input of latch 212, via OR circuit 221 to decrementing ~ -
21 counter 223 and shift register 224, and to the set input
22 of latch 213. The combination of the clock pulse with the
~ 23 output of latch 212 on line 220 causes counter 223 and
~24 shift register 224 to load the information from cables 28 :~-
and 29. In the present example the codeword 1110 is thereby ~:
26 loaded into the leftmost four bit positions of shift regis-
27 ter 224 while the codeword length 100 is loaded into
28 counter 223.
29 . .
'.''
~ SA973013 -48- ~
... .
: , . . . .
.. ~ .; . ... . . .
.
104;~5S3
1 The pulse on line 25 is additionally supplied to OR
2 circuit 142 in Figure 3. This pulse sets latch 135 and
3 resets latch 136, thereby returning encoder 14 to the "ready
4 to receive" state, so that this circuitry can accept the
succeeding event designation.
6 The setting of latch 213 and the resetting of latch
7 212 in Figure 8 place this shiftout circuit in the "ready
8 to transfer" state. The set output of latch 213 provides
9 a signal on line 41 to the receive device. The signal on
line 41 is accompanied on line 40 by the leftmost bit in
11 shift register 224, which is the leftmost bit of the code-
12 word (1110). Acceptance of this bit is signaled by means
13 of a clock pulse on line 42. This pulse is gated via OR
14 circuit 221 to decrement counter 223 and to shift left by
one bit position shift register 224. In the present
16 example, the resulting contents of counter 223 and shift
17 register 224 are 0011 and 11000000, respectively. Thus,
18 the second bit of codeword 1110 is made available an line
19 40.
The acceptance pulse on line 42 is additionally
21 supplied to AND circuit 228, which is under the enabling
22 control of AND circuit 226 and inverters 225. AND circuit
23 228 is enabled only when the last three bits in counter
24 223 are 001, the binary equivalent of decimal one. Hence,
AND circuit 228 is enabled only when the codeword bit whose
26 acceptance is signaled by a clock pulse on line 42 is the
27 final bit of a codeword. In the present example, the code-
28 word 1110 comprises four bits, and the initial contents of
29 counter 223 is 0100. Therefore, the first acceptance
SA973013 -49-
` 1042S53
1 pulse on line 42 is not gated via AND circuit 228, and
2 the shiftout circuitry remains in the "ready to transfer"
3 state.
4 Acceptance of the second bit of the codeword is
signaled by the acceptance device by means of another
6 clock pulse on line 42. The clock signal is supplied by ~ `
7 OR circuit 221 to counter 223 and to shift left register ~ - "-
8 224. The counter decrements to a count of 010, represent-
g ing the binary equivalent of a decimal 2. Shift left
10 register again shifts to the left one binary position to -
11 provide the 3rd bit of the codeword 1110 on line 40. As `-
12 counter 223 has not yet decremented to a count of 001,
13 AND circuit 228 remains disabled, and the shiftout circuitry
i4 remains in the "ready to transfer" state.
The acceptance device signals acceptance of the
16 third binary bit by a further clock pulse on line 42. Once
17 again, AND circuit 228 is disabled and the signal is supplied
18 by OR circuit 221 to counter 223 and shift left register
19 224. Counter 223 thus decrements to a count of 001, while
shift left register 224 shifts one bit position to the left
21 to provide the fourth and final bit of the codeword 1110
22 on line 40. Upon counter 223 decrementing to the 001 condi- ` -
23 tion, inverter 228 inverts the low order output of the
24 counter. Thus, no signals are supplied to OR circuit 229
and inverter 227 then supplies an enabling signal to AND
26 circuit 226.
27 The acceptance device then signals acceptance of
28 the last bit of the codeword by means of another clock
29 pulse on line 42. This time, the output of counter 223 is
SA973013 -50-
, .. , . . ~ ,
: . .
104ZSS3
1 001, so that inverters 225 and AND circuit 226 provide
2 an enabling input to AND circuit 228. Hence, the clock
3 signal is gated by AND circuit 228 to OR circuit 211,
4 which transmits the signal to reset latch 213. This
terminates the output signal on line 41, which indicates
6 to the acceptance device that the entire codeword has been
7 supplied.
8 As described previously, the reset condition of
9 latch 213, together with the reset condition of latch 212,
constitute a temporary transitional state for the shift-
11 out circuitry. In this state the reset outputs of both
12 latches provide enabling inputs to AND circuit 215. Hence
13 the next clock pulse from clock 110 on line 26 is gated
14 by AND circuit 215 to set latch 212, thereby returning the
shiftout circuitry to the "ready to receive" state.
16 At some point, the codeword 1110 may be supplied
17 to decoder 51 in Figure 2. Operation of the decoder in
18 conjunction with the operation of decoder tables 52 and 53 -~
19 will now be discussed.
Referring now to Figure 9, the codeword is supplied
21 from a storage device, from a transmission link, or directly
22 from the encoder output of Figure 1. First, a signal is
23 supplied therefrom on line 61 to indicate that the first bit
24 of the codeword is present on line 60. As before, the
exemplary codeword is "1110" reading from left to right.
26 When decoder 51 i9 in the "ready to receive" state, latch
27 280 is in the set condition, latch 281 is in the reset con-
28 dition and latch 282 is in the set condition. Thus, latch
29 280 supplies an enabling signal to AND circuit 230. The
SA973013 -51-
104Z553
1 signal on line 61 provides a further enabling signal to
2 the same AND circuit, that the next succeeding cloc]; pulse
3 from clock 255 on line 290 is gated by AND circuit 230 to
4 OR circuit 235. The set output from latch 280 is also
supplied on line 301 to shift left register 234 and on lines
6 71 and 73 to the shift registers of the decoder tables. The
7 clock pulse is transmitted by OR circuit 235 on line 302 to
8 the clock input of shift left register 234 and on lines 70
g and 72 to the shift registers of the decoder tables. The
combination of these signals causes the shift registers of
11 the decoder tables to be loaded and causes the shift left ~-
12 register 234 to load the fixed inputs thereto and to load
13 the first bit of the codeword on line 60 into the low order ~;-
14 bit position via input line 232.
The clock pulse on linc 302 is also supplied on line
16 62 to indicate acceptance of the first bit of the codeword
17 and to reset latch 280. The latch therefore terminates the
18 signal on line 300, disabling AND circuit 230 and terminates
19 the signal on line 301 to prevent further loading of the
shift registers. When reset, latch 280 supplies a signal
21 on line 305 to AND circuit 295. Latch 281 remains reset so
22 as to supply an output signal on line 303 to AND circuit 231.
23 The decoder is thus in the "working" state.
24 At this time, shift register 234 contains the first
bit of codeword 1110, namely 1, preceded by seven zeroes.
26 The shift registers of the decoder tables have been loaded
27 with pre-established values listed in Figure 18. Thus,
28 output ts(l) = 00 is supplied on cable 74, output bS(l) = 00
29 is supplied on cable 75, output tr(l) = 00 is supplied on
SA973013 -52-
109~2SS3
1 cable 76 and output br~l) = 00 is supplied on cable 77.
2 All four outputs are supplied on cables 7q-77 in rlqht-
3 justified form, with zeroes on thc rcmaining wircs thereof.
4 The all-zero output on cable 74 is supplied to subtraction
unit 240, 241 to be subtracted from the output of shift
6 left register 234 (00000001). AS the net result of this
7 subtraction is a non-negative number, a signal is present
8 on line 256. This signal, together with the signals on
9 lines 303 and 61, enables AND circuit 231 to gate the next
clock pulse from clock 255 on cable 290 to OR circuit 235.
11 Again, the clock pulse is transmitted by OR circuit
12 235 to line 302, to shift left register 234, and on lines
13 70 and 72 to the shift registers of the decoder tables. As
14 a result of the previous acceptance pulse on line 62, the
codeword supply mechanism now supplies the second bit of the
16 codeword (1110) on line 60. Shift register 234 responds to
17 the clock pulse on line 302 by shifting to the left and
18 shifting in the second bit of the codeword via shift-in
19 input 233. The content of shift register 234 is therefore
00000011. The clock pulse on lines 70 and 72 causes the
21 shift registers of the decoder tables to provide as outputs
22 tS(2) = 010 on cable 74, b5(2) = 001 on cable 75, tr(2) =001 ~`
23 on cable 76 and br(2) = 001 on cable 77, with all table
24 values right-justified. .
Subtraction unit 240, 241 therefore subtracts the
26 pre-established value on cable 74 (00000010) from the output
27 of shift left register 234 (00000011). Once again, the
28 subtraction result is a non-negative number, so that a
29 positive signal is supplied on line 256.
., . . :
SA973013 -53~
.
- ~04Z553
The clock pulse gated by OR circuit 235 onto line
62 signals the codeword supply apparatus of the acceptance
of the second bit of the codeword. That apparatus there-
fore supplies the third bit (1) of the codeword on line 60.
The positive signal on line 256, together with
signals on lines 61 and 303, enables AND circuit 231 to gate
the next clock signal to OR circuit 235. Once again, this
signal is supplied on line 302 to cause a shift of the shift
left register 234 and of the shift registers of the decoder
tables. The clock signal is also supplied on line 62 to
signal acceptance of the third bit of the codeword by shift
left register 234, whose contents are now 00000111. The
clock pulse causes the decoder tables to supply as outputs
the values ts(3) = 0110, bs(3) = 0010, tr(3) = 0101, and
br(3) = 0010 given in Figure 18.
Subtractor unit 240, 241 subtracts the pre-established
va~ue on cable 74 (00000110) from the output of shift regis-
ter 234 (00000111). Once again, the result of the subtrac-
tion is a non-negative number, causing a positive signal to
be supplied on line 256 to then gate the next appearing
clock pulse from clock 255 to OR circuit 235. The preceding
clock pulse supplied on line 62 has caused the codeword
supply apparatus to supply the fourth, and last, bit of the
codeword (1110) on line 60. The clock pulse is transmitted
by the OR circuit 235 to shift left register 234 and to the
shift registers of the decoder tables. Shift left register
234 therefore shifts to the left and shifts in the "0" bit
of the codeword via input 233. The resultant contents of
register 234 comprises 00001110. At the same time, the
SA973013 -54-
~04Z553
1 shift reqistcrs of the decoder tables provide the values
2 tS(4) = 01111, bS(4) = 00010, tr(4) = 01111 and br~4) =
3 00101, right-justified on cables 74-77.
4 Subtractor unit 240, 241 therefore subtracts the
pre-established value at cable 74 (00001111) from the output
6 of shift register 234 (00001110). Tne result of this sub-
traction is a negative number which terminates the signal on . -~
8 line 256. This disables AND circuit 231 so that no more
9 clock pulses will be transmitted thereby. ~ .
The absence of a signal on line 256 is used by
11 inverter 304 to provide an enabling input to AND circuit
12 295. Since the decoder is in the "working" state, charac-
13 terized by the reset condition of latches 280 and 303, the
14 next clock pulse appearing on line 290 is gated via AND
circuit 295 to set latch 281. This places the decoder in
16 the "ready to transfer" state, in which the signal from
17 latch 281 on line 82 indicates to event regenerator 50 ~:
18 that an event designation is present on cable 80 and line ~ -
19 81. The operation of the decoder circuitry in Figure 9
to determine this event designation will now be described.
21 The result of the subtraction by subtractor 240,
22 241 of the pre-established value on cable 74 tOOOOllll)
23 from the output of the shift register 234 (00001110) is
24 all l's. This output represents a negative 1 and is sup-
plied to adder circuitry 260, 261. Adder 260,261 adds
26 this value to the pre-established value on cable 75
27 ~00000010) and adds to this result a 1 from line 262.
28 The result of this addition is 00000010, which is supplied :
29 to gate circuit 263.
SA973013 -55-
, ~ ' ' ' ,,
1042S53
1 At the same time, subtraction unit 242, 243 subtracts the contents
of cable 76 (00001111) from the output of shift register 234 (00001110).
The result of that subtraction is negative, resulting in the absence
of an output signal on line 276. The precise result of the subtraction
is all l's and is supplied to adder 270, 271. The adder adds the output
of subtractor 242, 243 (11111111) to the output of the decoder tables
on cable 77 (00000101), and adds to that result a 1 appearing on input
line 272. The result of that addition, 00000101, is supplied to gate
circuit 273.
As discussed, no output signal is supplied by subtractor 242, 243
on line 276. Thus, no enabling signal is supplied to enabling input
264 of gate circuit 263. Inverter 275, however, supplies a positive out-
put signal on line 274 to gate circuit 273. Gate circuit 263 thus blocks
the output of adder 260, 261 and gate circuit 273 supplies the output
of adder 270, 271 (00000101) to OR circuits 265, and hence to cable 80.
The resultant output on cable 80, 00000101, is the eight-bit binary
equivalent of a decimal 5, which represents the fifth event designation.
No output is supplied on line 81, indicating that the event designation . - . -
is a regular event rather than special event. :
As shown by the above example, encoder 14 in Figure:l responds to
the event designation by accessing corresponding pre-established values
from encoder table 16 by a shifting process and then combines the event
designation value with the pre-established values to provide a codeword -:
which is serialized by shift-out circuitry 17. Decoder 51 in Figure
SA9-73-013 - 56 -
104'~SS3
1 2 selects corresponding pre-established values from decoder
2 tables 52 and 53 by a similar shifting process and combines
3 the received codeword with selected pre-established values
4 to determine the event designation, which is then supplied
on cable 80 and on 81.
6 Figures 19 and 20 disclose exemplary changes in
7 encoder select/combine circuitry 14 and decoder select/
8 combine circuitry 51 to accommodate a different set of
9 tables. The only difference from the encoder table 16 of
Figures 4, 5, 6 and 7 is that the TS and TR plugboards 150
11 and 151 of Figure 4 are replaced with DS and DR plugboards.
12 In the circuitry of Figure 19, the subtraction unit 103,
13 104 and shift right registers 100 and 101 remain intact.
14 Eliminated from the apparatus of Figure 3 are shift right
register 115, subtractor 117, 118 and subtractor 123, 124.
16 The resultant circuitry is thus much simpler and faster -
17 and includes adder 400, 401 to add the output of the encoder -
18 tables Dr or Ds on cable 402 to the output of shift right
19 register 101. The net result of this addition is supplied
on output cable 29 to shift out circuitry 17 of Figure 1.
21 The relationship between "Dr" encoder and decoder ~ ;
22 tables of Figure 19 and the "Tr" and "Br" tables of Figure
23 18, is summarized by the following mathematical formula:
24 Dr(k)=Tr(k)-Br(k)-l. The special "Ds" table values obey
the same mathematical formula with respect to the special
26 tables of Figure 18.
27 The differences in the tables are accounted for by
28 the logical difference between the circuitry ofFigure 19
29 and that of Flgure 3.
. .
SA973013 _57_
...... .
.... . .
.
104Z553
1 The corresponding decoder is illustrated in Figure
2 20. Most of the circuitry of the decoder in Figure 9 is
3 retained for that Figure 20, including: shift left unit 234;
4 adders 240 and 241, which function together with inverters
245, 246 and input 250 to function as a subtractor; similar
6 adders 242, 243, which function as subtractors; gating
7 circuits 263 and 273; and the OR circuit 265 leading to out- -
8 put 80. The changes comprise the substitution of adders 410,
9 411, inverters 412, 413 and input 414 to subtract the Ds out-
put of the encoder tables on 415 from the content of shift
11 left unit 234, rather than the adders 260, 261 of Figure 9
12 for adding the output of the subtraction unit 240, 241 to
13 the decoder output on cable 75. The output of the subtrac- ~ -
14 tion unit 410, 411 is supplied to gate circuit 263, which is
operated in conjunction with the special signal on line 81
16 to supply the special event number to OR circuit 265 and
17 thence to cable 80.
18 Similarly, adders 420, 421, inverters 422, 423 and :
19 input .424 combine to subtract the Dr ou~put of the encoder
tables on cable 425 from the output of shift left unit 234.
21. Once again, this differs from the circuitry of Figure 9 which
22 employed adders 270 and 271 to add the output of the sub-
23 traction unit 242, 243 to the decoder table output on cable
24 77. In the absence of the special event designation signal
on line 81, inverter 275 operates gate 273 to transmit the
26 regular event number from the subtraction unit 420, 421
27 to OR circuit 265 and to cable 80,
28 Various other combinations o~ encoder tables and
29 combinatorial logic and decoder tables and combinatorial
SA973013 . -58-
.
' '
~04Z553
1 logic may also be envisioned. The essential portions of the
2 present invention have been described above, including var-
3 ious specific exemplary embodiments.
4 Exemplary input and output units which establish or
utilize the data compressed and decoded by the described
6 circuitry will now be discussed. Figure 21 describes an
7 exemplary event recognizer 10 of Figure 1.
8 The source of data in the event recognizer is a
g scanner 430. The scanner may be of any suitable type, such
as of the vidicon type. For the purpose of illustration, the
11 scanner is assumed to be scanning character image information
12 in the form of eight-bit horizontal scans. The data is
13 supplied on line 431 to a set of scan line buffers 432. The -
14 scan line buffers supply a ready signal on line 433 to ini~
tiate a scan operation. Scanner 430 also supplies clock
16 signals on line 434 to the scan line buffers. The data sup-
17- plied by the scanner on line 431 to the scan line buffers
18 merely comprises ones and zeroes representing the black or
19 white significance of each bit position of the scanned image. ~
20 The scan line buffers 432 subsequently supply data -
21 from line 436 in response to clock signals on line 437 to -~
22 operate the event recognizer circuitry. The event recognizer
23 circuitry responds to all runs of data to produce an event
24 designation number in parallel on cable 11 and to provide a
special event indicator on line 12 when appropriate. For the
26 purpose of the illustration, a run i9 defined as a one or as
27 a string of one or more zeroes and the first one following
28 this string of zeroes. If the string of zeroes terminates
29 in an end of line for the scan rather than with a one, the
SA973013 _59_
: . - . " , .: ~
104ZS53
1 entire string is considered simply as the end of line
2 special event. In the exemplary circuitry of Figure 21,
3 the special events include as special event 1, the end of
4 line, and as special event 2, a run of length 1. Regular
events No. 1 through No. 6 are, respectively, runs of
6 lengths 2 through 7, so that the regular event designation
7 number for a run is the length of that run minus one. That
8 is, the regular event designation number is precisely the
9 number of zeroes in the run. Thus, a run of length 2 (which
is a "01") is regular event No. 1.
11 As an example, a scan line of eight consecutive
12 zeroes and no ones, is encoded simply as an end of line,
13 special event No. 1. For further illustration, a scan line
14 comprising seven consecutive zeroes followed by a one, is
encoded as a run of length 8, regular event No. 7, followed
16 by an end of line, special event No. l. Conversely, if the
17 scan line comprises a string of eight consecutive one bits,
18 the circuitry of Figure 21 encodes this as eight consecutive ~ -
19 runs of length 1, special event No. 2, eight times, followed
by an end of line, special event No. 1. Further, a scan line
21 comprising seven consecutive one bits, followed by one zero
22 bit, will be encoded as seven runs of length 1, special
23 event No. 2, seven times, followed by an end of line special
24 event No. 1.
. - .
As a further example, a scan line comprising the
26 following eight bits, 00110100, is defined by the exemplary
27 event recognizer as comprising a run of length 3, followed
28 by a run of length 1, followed by a run of length 2, fol-
29 lowed by an end of line. This would thus be encoded as
SA973013 -60-
. , . . : ~ . '. , , , ' , `, .' .
lO~ZSS3
1 regular event No. 2, followed by special event No. 2,
2 followed by regular event No. 1, followed by special
3 event No. 1.
4 In Figure 21, down counter 440 establishes the
special event designation number which may be gated to
6 cable 11 by gate circuit 441. Up counter 442 establishes
7 the regular event designation number, which may be gated
8 to cable 11 by gate circuit 443. Latch 445 controls
9 gates 441 and 443, and indicates whether the event is
regular or special by supplying a signal on line 12 when
11 the event is a special event. OR circuits 446 transmit
12 the output of gate 441 or gate 443 to cable 11. As the
13 circuitry of the exemplary event recognizer provides a
14 maximum event designation number of seven, OR circuit 446
is connected to only four lines of cable 11. ~rhe remain-
16 ing four lines of the cable are permanently supplied with
17 a voltage level that indicates a binary zero. Several ~ -
18 signals may appear on cable 11 or on line 12 until a
19 definite evént designation is selected. At the time an
20 event is selected, latch 450 supplies a signal on line 13. -
21 Subsequently, encoder 14 signals acceptance of the available
22 data by supplying a clock pulse on line 15.
23 Counter 452 is preset to a binary count of six with
24 the first pulse of each scan line and is subsequently decre-
mented by each clock pulse to reach a count of zero imme-
26 diately prior to the last pulse of the scan line. Latches
27 453 and 454 then combine to operate latch 445 and counters
28 440 and 442 to indicate a run followed by an end of line
29 special event No. 1 if the last data bit on line 436 was
SA973013 -61-
10425s3
1 a one, or to simply indicate an end of line, special event
2 No. 1 if the last data bit on line 436 was a zero.
3 Latch 455 is employed to block one clock pulse from
4 counter 442 during the counting of subsequent zeroes as
data from line 436. This allows the output of counter 442
6 to be one less than the total run length, which is required
7 because each regular event designation number is one less
8 than the run length that it designates.
g Lastly, latches 450 and 457 control the operational
characteristics of the event recognizcr circuitry in the
11 following way. Immediately following a reset signal that was
12 applied to line 31, both latches 457 and 450 are reset and - i -
13 the event recognizer circuitry is ready to accept data from
14 scan line buffers 432, when the circuitry of Figure 21 is
ready to transfer data on cable 11 and line 12, latch 457
16 is reset and latch 450 is in ~he set state. The situation
17 where both latches are set cannot exist.
18 Referring now in more detail to the operation of the
19 circuitry of Figure 21, clock Iatch 460 controls the initiali-
zation of the event recognizer circuitry.
21 Inputs to latch 460 comprise start line 38, reset ~-
22 line 31 and clock 461. Upon application of a reset signal
23 on line 31, the subsequently appearing clock pulse from
clock 461 will operate to reset latch 460. Resetting the
latch 460 will operate to block AND circuit 462 to prevent
26 the application of clock pulses to lines 463, 464 or 465.
27 Also, the combination of the reset signal on line 31 and
28 the clock pulse will operate AND circuit 467 to supply a
29 reset pulse to scanner 430 on line 470, to the scan line
SA973013 -62-
,, ~
, '.' :; .:',, , ' ' : . . ' : ~ ; ':
., . , , ~ . .
1042553
1 buffers 432 on line 471, and to the event recognizer
2 circuitry on line 472. The reset pulse on line 472 is
3 transmitted by OR circuits 473, 474 and 475 to reset latches
4 450, 457 and 454, and transmitted by OR circuit 476 to set
latch 453.
6 A subsequent start signal on line 38 causes latch
7 460 to operate to the set state upon the next following
8 clock pulse from clock source 461. In this state, latch -
9 460 supplies a signal on line 480. Thus, subsequent clock
pulses from source 461 will be gated by AND circuit 462 to ~:~
11 scanner 430 on line 463 and to the event recognizer cir~
12 cuitry on lines 464 and 465. Clock pulses are supplied
13 to the scan line buffers 432 from scanner 430 on line 434
14 and from the event recognizer circuitry on line 437.
15 The set output of latch 457 is connected to AND ~.
16 gate 482. As the latch is initially reset, AND circuit 482 ~ . -
17 blocks clock pulses on line 465 from the event recognizer : :.
18 circuitry. The reset output of latch 457 is applied to
19 enabling input 483 of counter 440, to enabling input 484 .....
20 of counter 442, and to AND circuit 485. The reset output .
21 of latch 450 provides a further enabling input to AND cir- -
22 cuit 485. AND circuit 485 thus gates the first clock pulse ~-
23 from AND circuit 462 to OR circuit 487, OR circuit 488,
24 to the set input 489 of latch 455 and to the set input 490
25 of latch 457. OR circuit 487 transmits the clock pulse to
26 set input 491 of latch 445. This operates latch 445 to
27 supply a special event output signal on line 12 and a
28 signal to operate gate 441. OR circuit 487 also transmits
29 the clock pulse to the pulse input 493 of counter 440.
. ~ '. ,
SA973013 -63- ~
.: . , . ~ ., . : . . .
: ' ' ' . "' . ,~' ' ,, ' ' ,. ', ' , ' ' "' ' ' . ' ' . `
-` 1042SX3
1 The combination o the enable signal on line 483 with the
2 pulse on line 493 operates counter 440 to load an initial
3 count of a binary two. As latch 445 has operated gate
4 441, a binary two is supplied by the gate to OR circuit
446 for output on cable 11, The event recognizer circuitry
6 is therefore arranged to indicate a special event No. 2 if
7 the first data bit detected from the scan line buffer on
8 line 436 is a binary one.
9 OR circuit 488 transmits the clock pulse from AND
circuit 484 to input 494 of counter 442. The combination
11 of the enabling signal at input 484 with the clock pulse
12 on line 494 causes counter 442 to be loaded with an all-zero
13 input. The clock pulse also operates to set latch 455 and
14 set latch 457.
Assuming that the scan line buffers 432 are ready to
16 supply a scan line of data to the event recognizer, a signal
17 is supplied therefrom on line 500 to AND circuit 501. Thus,
18 AND circuit 501, under the control of line 500 and latch 454,
19 transmits clock pulses to the event recognizer circuitry and
on line 437 to the scan line buffers 432 to control the trans-
21 fer of scan line data information to the event recognizer
22 circuitry.
23 In that the "ready" signal remains present on line
24 500, latch 457 remains set, and latch 454 remains reset,
a clock pulse appearing at input 465 is gated by AND circuits
26 482 and 501 to line 437. This clock pulse operates the scan
27 line buffers to acknowledge receipt of the first data bit
28 on line 436. The output of AND circuit 501 is also supplied
29 to input 510 of counter 452 and to AND circuits 512 and 513.
SA973013 -64-
.. . : , . : , , . ... : ,
.
`` 104;ZS53
1 AND circuits 512 and 513, together with counter 452 and
2 lat:ch 453 operate to count the clock pulses supplied on
3 line 437 to the scan line buffers, and thereby count the
4 scan line length and thereby detect the end of a scan line.
Specifically, the previously considered reset pulse
6 on line 472, transmitted by OR circuit 476, sets latch 453.
7 The latch therefore supplies an output on line 516 to en-
8 able AND circuit 513 and to supply an enable signal at in- -
g put 517 of counter 452. The absence of a signal from the
10 set output of latch 453 served to block AND circuit 512. ~-
11 As previously discussed, application of the clock pulse . -
12 from AND circuit 501 on line 437 to the scan line buffers ~- --
13 also results in application of the cIock pulse to input
14 510 of counter 452. The combination of the clock pulse at :- -.
15 input 510 with the enabling signal on line 517 rcsults in `
16 loading counter 452 with the binary input "0110", which
17 is equal to a decimal 6. The same clock pulse is gated
18 by AND circuit 513 to the reset input of latch 453. This
19 resets the latch to terminate the signal on line 516 and
at input 517 of the counter 452. Subsequent clock pulses
21 at input 510 to the counter will therefore serve to decre- -
: 22 ment the count.
23 The second clock pulse appearing at input 510
24 appearing at input 510 therefore causes counter 452 to
decrement to a binary count of 5. Each subsequent clock
26 pulse similarly.decrements the counter such that the third
27 clock pulse decrements the count to 4, the fourth clock
28 pulse decrements the count to 3, the fifth clock pulse
29 decrements the count to 2, the sixth clock pulse decrements
the count to 1, and the seventh clock pulse decrements the
,
SA973013 -65-
,
.', `'' . ~ .
104Z553
1 count to 0. Under all conditions of the counter except
2 for 0, the counter supplies a 1 output on at least one
3 of its output lines to OR circuit 524, so that the OR
4 circuit thus supplies a signal to inverter 523, which
therefore blocks AND gates 512 and 521.
6 Upon occurrence of the seventh clock pulse, which
7 decrements counter 452 to 0, OR circuit 524 then supplies
8 no signal to inverter 523 which therefore supplies a signal
g to enable AND circuits 512 and 521. The combination of the -
reset output signal on line 520 from latch 553 with the
11 signal from inverter 523 causes AND circuit 521 to trans-
12 mit a signal on line 527 to AND circuit 528.
13 The signal on line 527 is the indication that the
14 subsequent clock pulse supplied on line 437 will acknow-
ledge receipt from the scan line buffers 432 of the last
16 bit of the scan line.
17 The description now returns to the response of the
18 event recognizer circuitry to the first data bit appearing -
19 on line 436 from the scan line buffers.
If the first data bit is a one, the combination of
21 the clock pulse from AND circuit 501 and the data signal -
22 on line 436 operate AND circuit 502 to supply a clock pulse
23 to OR circuit 503. OR circuit 503 transmits the pulse to
24 set input 505 of latch 450 and, via OR circuit 474, to re-
set input 506 of latch 457. This sets latch 450 and resets
26 latch 457, thereby placing the event recognizer circuitry
27 in the aondition where it is ready to transmit data and
28 not ready to receive data. Latch 457 therefore prevents
29 further clock pulses from being transmitted by AND circuit
SA973013 -66-
.
~04ZS$3
1 4~2 to the clock input 437 of the scan line buffers 432.
2 The setting of latch 450 supplies an output signal on line
3 13 to the encoder 14 of Figure 1, to indicate that an
4 event designation is present on cable 11 and line 12. It
will be recalled that the output of the event recognizer
6 circuitry at this time comprises a special event signal
7 on line 12 and the event designation number 2 on cable 11
8 from counter 440. Thus, special event No. 2 is indicated,
9 which comprises a run of length 1, or a one appearing at
10 line 436 not following a string of zero bits. . -
11 On the other hand, if the first data bit of the
12 scan line is a zero, then no signal is supplied to AND
13 circuit 502, which therefore blocks the clock pulse ap-
14 pearing from AND circuit 501. The clock pulse operates
to reset latch 455 at input 508 thereto and operates to
16 decrement counter 452 at input-510. The clock pulse
17 further operates on line 437 to acknowledge receipt of the
18 next data bit from scan line buffers on line 436. Finally,
19 the clock pulse is transmitted to AND circuit 509, which
20 is blocked by the absence of a signal from the reset out- .
21 put of latch 455.
22 The initial zero data bit and the clock pulse -~
23 which acknowledges it has no other effect on the event
24 recognizer circuitry than to reset latch 455 and decre-
ment counter 452.
26 Assuming that the end of line has not yet been
27 reached, the next clock pulse appearing on line 465 will
28 be transmitted by AND circuits 482 and 501 to line 437, .
29 to input 508 of latch 455, to AND circuit 509 and to in-
put 510 of counter 452. In this instance, however, latch
SA973013 -67-
.
.
1 455 has been previou ~y4rZesSe~3and now supplies a gating
2 signal to AND circuit 509. AND circuit 509 therefore
3 transmits the clock pulse via OR circuit 488 to input
4 494 of counter 442 and to input 530 of latch 445. This
pulse increments counter 442 to a count of 1 and resets
6 latch 445. Resetting latch 445 terminates the signal on
7 line 12 and blocks gate 441 to prevent further applica-
8 tion of the special event designation signal and the
g special event designation number at the output. Resetting
latch 445 also causes the reset output of the latch to
11 apply a signal to gate 443 to transmit the regular event
12 designation number of 1 from the counter 442 to the output.
13 This result occurs whether or not the data bit from the
14 scan line buffers is a one or a zero. If the data bit is
a zero, nothing further occurs. If the data is a one bit,
16 its results will be explained later.
17 Subsequent consecutive zero bits in the scan line ~
18 buffer result in the continued incrementing of counter 442 -
19 for each applied clock pulse. Thus, the output appearing
therefrom on cable 11 is equal to one less than the number
21 of applied clock pulses.
22 Upon encountering a one bit on line 436, AND
23 circuit 502 and OR circuits 503 and 474 transmit the clock
24 pulse to input 505 of latch 450 and to input 506 of latch
457. This pulse therefore alters the condition of both
26 latches, setting latch 450 and resetting latch 457, Re-
27 setting latch 457 causes AND circuit 482 to prevent the
28 application of any further clock pulses on line 465 to
29 the event recognizer circuitry and to scan line buffers
SA973013 -68-
104'~SS3
1 432. The set output from latch 450 on line 13 indicates
2 to thc encoder 14 in Figure 1 that the output on ca~le
3 11 and line 12 represents the next event to be encoded.
4 The event designation number on cable 11 is therefore the
last count of counter 442 and the absence of a signal on
6 line 12 indicates that a regular event designation number
7 is available on cable 11.
8 Upon the encoder circuitry 14 of Figure 1 indicating
g by a pulse on l~ne 15 that the data on cable 11 and line 12
has been accepted, OR circuit 473 transmits the pulse to
11 latch 450. Latch 450 is reset to terminate the signal on -
12 line 13 and the reset output supplies a signal to AND cir-
13 cuit 485. Latch 457 remains in the reset condition from
14 the data pulse applied via AND circuit 502 and OR circuits
503 and 474 representing the initial one bit, or the one
16 bit following one or more zeroes. Thus, latch 457 supplies -
17 its reset signal to AND circuit 485. The combination of
18 the reset outputs from latches 457 and 450 cause the next -
19 succeeding clock pulse to be gated by AND circuit 485 to
20 set latch 445, to load counter 440 by the combination of
21 the signal on line 483 and the pulse on line 493, to load
22 counter 442 by means of the signal on line 484 and the
23 pulse on line 494 and to set latches 455 and 457 by means
24 of the pulses on lines 489 and 490.
The setting of latch 457 allows the subsequent
26 clock pulse on line 465 to be transmitted to AND circuit
27 501. As we are not yet at the end of line, latah 454
28 continues to supply a reset output to AND circuit 501, and,
29 assuming that the scan line buffer remains in the ready
SA973013 -69-
.,
.
... .
~ ' ` ; : .
104;~SS3
1 state, a signal is supplied therefrom on line 500 to AND clrcuit 501.
The recognition of further runs proceeds in a manner identical to that
described for recognizing the first run of the scan line.
The end of line situation will now be discussed. Upon encountering
the seventh clock pulse to strobe the scan line buffers, counter 452
goes to zero. As previously described, this count results in the appli-
cation of a signal to AND circuit 521, which, since latch 453 is reset,
is transmitted onto line 527. The signal on line 527 therefore enables
AND circuit 528 to transmit the next appearing clock pulse.
Two conditions are possible. The last data bit of the scan line is
either a zero or a one. If the last data bit is a one, the event ~
recognizer circuitry will transmit a regular event designation signal -
on line 12 and an event designation number on cable 11 indicating the- ~
number of zeroes preceding the one bit, or the event recognizer cir- -
cuitry will transmit the special event designation No. 2 to indicate
that the last data bit was a one which was preceded by a one bit.
Subsequently, the event recognizer circuitry will transmit an end of ~ -
line event designation which is special event No. 1. On the other hand,
if the last data bit of the scan line is a zero, no regular or special
events indicating runs will be transmitted. Rather, only the end of
line special event designation will be transmitted.
Preparatory to receipt by event recognition circuitry of the last
data bit of a scan line, AND circuits 482 and 501,
-.
SA9-73-013 - 70 -
., , . . , ~ ~ .. . . . . . . .
. .
. - .: . .
,,
1 51.2 and 528 are ena~led. AND circuit 509 may also be
2 enabled, depending upon whe~her the prcvious data bit
3 was a zero. A clock pulse on line 465 is therefore trans- .
4 mitted via AND circuit 482 and AND circuit 501 to line 437
and to AND circuits 502, 509, 512 and 528. The clock
6 pulse on line 437 operates to strobe the scan line buffers
7 to acknowledge the datà bit on line 436. If the data bit
8 is a zero, nothing occurs at AND circuit 502. If, however,
9 the the data bit is a one, AND circuit 502 operates to
10 transmit the pulse, via OR circuits 503 and 474, to latches - :
11 450 and 457. This will operate the latches to prevent .. . ~ .
12 application of the next clock pulse to the event recognizer ~ .
13 circuitry and to supply a signal on line 13 to the encoder ,
14 circuitry 14 of Figure 1. Whether or not the data bit is
15 a one, AND circuit 509, if enabled, transmits the clock : :
16 pulse to latch 445 and to counter 442. This results in the
17 application of the proper regular event designation number
18 to gate 443. Also, the clock pulse is transmitted by AND
19 circuit 528 to input 532 of latch 454. This operates the ~ ~ -
latch to the set condition to terminate the reset output
21 therefrom to AND circuit 501 and thereby block any further
22 clock pulses from transmittal to the scan line buffers
23 432. This also operates the latch to supply a signal from
24 the set output to AND circuit 533, enabling the AND circuit
for the next clock pulse from AND circuit 482.
26 Lastly, the clock pulse is transmitted by AND
27 circuit 512 and OR circuit 476 to the set input of latch
28 453. The latch is therefore set to terminate the output
29 on line 520, which thereby blocks AND circuits 521 and 528.
SA973013 -71-
.
:104ZS53
1 The latch also supplies a signal on line 516 to input
2 517 of counter 452. Thus, counter 452 is in condition
3 to be loaded upon subsequent enabling of AND circuit 501
4 for beginning the next scan line.
As previously described, if the last data bit of
6 the scan line were a one, latch 457 is reset and latch
7 450 is set, so that a signal on line 13 indicates to the
8 encoder the availability of an event designation on cable - -
9 11 and line 12. As before, the encoder circuitry signals
acceptance of the event designation by application of a
11 pulse on line 15. This pulse resets latch 450, and leaves
12 latch 457 reset, so that the next clock pulse on line 465
13 serves to set latches 457, 445 and 455, and to load counter
14 440 with a count o 2.
It will be recalled that if the last data bit of
16 the scan line were a zero, latch 445 remains reset and
17 counter 440 remains set with the count of 2, it having not
18 been pulsed subsequent to loading.
19 Upon acceptance by encoder 14 of the event information
particularized by a one data bit at the end of the scan line,
21 followed by one clock pulse on line 464, or upon the event
22 recognizer circuitry operating without further response to
23 a zero data bit at the end of the scan line, latch 457 is
24 in the set condition, latch 450 is in the reset condition
and counter 440 holds the value 2. The next clock pulse on
26 line 465 is thus transmitted by AND circuit 482 to AND cir-
27 cuit 533. As latch 454 was previously set to indicate that
28 the previous data bit was at the end of a scan line, AND
29 circuit 533 gates the clock pulse, which is blocked by AND
SA973013 -72-
. '~' ' '' ' `. ".. ' ' ', '" . ',
lO~ZSS3
1 circuit 501. ~hus, no further data is acknowledged from
2 the scan line buffers 432 by AND circuit 501 and line 437.
3 The clock pulse from AND circuit 533 is supplied
4 via OR circuit 487 to input 491 of latch 445 and to pulse
input 493 of counter 440. This operates to set latch 445,
6 if it is not already in that condition, so that it supplies ~ -
7 a signal on line 12 and enables gate 441. The pulse also
8 operates to decrement counter 440 to a binary condition of
9 1.
The pulse output of AND circuit 533 is also supplied
11 to OR circuit 503, which transmits the signal, via OR cir-
12 cuit 474, to reset latch 457 and to set latch 450. Latch : -
13 450 therefore indicates by means of a signal on line 13 that
14 data is available on line 12 and cable 11. As discussed, .
15 this data is available on line 12 and cable 11. As discussed, :~ .
16 this data comprises special event No. 1, the end of line
17 event designation.
18 Lastly, the pulse output of AND circuit 533 is -~ .
19 supplied via OR circuit 475 to reset latch 454. The latch .
thus indicates that the end-of-line condition is terminated,
21 and supplies an output signal to AND circuit 501 to ready
~ the event recognizer circuitry to again strobe the scan line
23 buffers 432, depending upon the presence of the ready signal
therefrom on line 500.
The apparatus illustrated in Figure 21 is merely
26 an examp}e of an event recognizer 10 in Figure 1 for sup-
27 plying various event designations to encoder circuitry 14,
28 Many alternative types of event recognizers may be employed
29 to supply suitable data to the described compression en-
coding and decoding apparatus.
SA973013 -73-
104ZS53
1 Referring now to Figure 22, an exemplary event
2 regenerator 50 of Figure 2 is illustrated in detail, As
3 with respect to event recognizer 10 in Figure 1, the event
4 regenerator in Figure 22 comprises merely one exemplary
type, of which many types are known in the art. The only
6 requirement is that it accept event designations from de- -
7 coder 51 in Figure 2 and generate the data particularized
8 by the event designations from the decoder. The event
9 regenerator must therefore be consistent with the corre-
sponding event recognizer so as to reproduce the original
11 data.
12 In Figure 22, the interconnections between the
13 event regenerator and the decoder 51 of Figure 2 include
14 event designation cable 80, special event designation line
81, data available line 82 and acceptance pulse line 83.
16 The event regenerator circuitry responds to the supplied
17 event designations by converting the designations into
18 strings of data bits which are supplied to scan line buffers `
19 540 which transmit the data to a printer 541. Interconnec-
tions between the event regenerator circuitry and scan line
21 buffers 540 is by way of lines 542, 543 and 544. The same
22 data is subsequently transmitted to printer 541 by means
23 of lines 546, 547 and 548. In each instance, a one data
24 bit is represented by the presence of a signal on line 542
in conjunction with a clock pulse on line 544, or by a sig-
Z6 nal on line 546 in conjunction with an availability signal
27 on line 547. A zero bit is represented by the absence of
28 a signal on line 542 in conjunction with a clock pulse on -
29 line 544, or by the absence of a signal on line 546 in con-
junction with an availability signal on line 547.
SA973013 -74-
.: ,. .. ; , ....
:, . . .
, . ~ . . .
~ 1042SS3
1 Scan line buffers 540 are illustrated hereinafter. Printer 541
may comprise any commercially available printer which will respond to
the supplied data, for example, one of the wire print type.
The event regenerator circuitry includes a register 550 for re-
ceiving the event designation number from cable 80, and a latch 551
for responding to line 81 to indicate whether the designated event is
special or regular. Latch 553 indicates the start of each scan line, ~
and counter 555 counts to determine the end of each scan line. Counter -
558 is a run counter that controls the number of zero data bits trans- -
mitted to the scan line buffers, and latch 560 supplies all the one
data bits to be transmitted.
Lastly, latches 562, 563 and 564 control the operation of the
eYent regenerator circuitry.
The reset and start signals from Figure 3 are applied to clock
latch 565 in Figure 22. Clock 567 supplies its output to latch 565 -~
and to AND circuits 568 and 569. A reset signal at line 93 is applied
to the reset input of latch 565 and to AND circuit 569. The next clock
pulse from clock 567, in combination with the reset input, operates
latch 565 to the reset condition. The combination of the clock pulse
and the reset input at AND circuit 569 transmits the reset pulse to
lines 570, 571, 572 and 573.
The reset pulse on line 572 operates to reset the scan line
buffers 540, and the pulse on line 573 operates to reset printer 541.
The reset pulse on line 570 is transmitted by OR circuit 575 to input
576 of latch 562; via OR circuit 577, to input 578 of latch 563, to `
input 579 of
~-~
SA9-73-013 ~ 75 -
.. . ..................... ... .
.' ~
,
.; . . :, '
1042553
1 latch 564; and, via OR circuit 581, to input 580 of latch
2 560. Line 571 transmits the reset pulse, via OR circuit
~ 5~2, to input 583 of latch 553.
4 Thus, the reset pulse has the effcct of setti~g
latches 562 and 553, and resetting latches 563, 564 and
6 560.
7 Next, the start signal is applied on line 97 to
8 latch 565. The next appearing clock pulse from clock 567
9 operates to set the latch so that it supplies an output to
AND circuit 568. Successive clock pulses are thus gated
11 by AND circuit 568 via line 586 to printer 541, and via
12 line 585 to AND circuits 590, 591 and 592. - :
13 Since latches 563 and 564 were reset by the reset ~`
14 pulse, the absence of a signal from the set outputs of these
latches serves to block clock pulses reaching AND circuits
16 591 and 592. However, since latch 562 was set by the reset
. 17 pulse, the set output of latch 562 provides an enabling in-
18 put to AND circuit 590. The remaining enabling input to
: D19 AND circuit 590 is line 82. A signal on line 82 indicates -~ -
that an event designation is present and ready for trans-
21 mission on cable 80 and line 81 from the decoder 51 in ~ .
22 Figure 2. .
23 Upon the occurrence of the signal on line 82 to
24 indicate the presence of data on cable 80 and line 81,
AND circuit 590 is enabled to transmit a subsequent clock
26 pulse. The first following clock pulse is transmitted to
27 input 595 of latch 562, to input 596 of latch 563, to in- : :
28 put 597 of register 550, to input 598 of clock latch 551,
29 and to AND circuit 599.
. . ~, . . -
SA973013 -76-
.,-' ' ' ~
., , ~. ,, , . . :
104Z553
1 The clock pulse at input 595 of latch 562 resets
2 that latch, disabling AND circuit 590. The pulse on input
3 596 of latch 563 sets that latch to enable ~ND circuit 591
4 to transmit a subsequent clock pulse from line 585.
The clock pulse on line 597, together with the
6 continuing input on line 605, operate register 550 to load
7 the event designation number from cable 80. The event : .
8 designation number from register 550 is then supplied on ' ~ .
9 line 612 to gate 611. The rightmost bit of the event .
designation number from register 550 is additionally sup-
11 plied on line 613 to AND circuit 610.
12 A special event is indicated by a signal on line
13 81, while a regular event is indicated by the absence of
14 the signal. Line 81 is connected to input 607 of latch
551 and to inverter 608. A special event signal on line
16 81, as applied to input 607, together with the clock pulse
17 from AND circuit 590 on input 598, sets latch 551. The
18 absence of a special event signal on line 81 operates in- .
19 verter 608 to supply an input to latch 551. This input,
together with the clock pulse at input 598, operates to :
21 reset latch 551. Thus, the special event signal operates
22 to reset latch 551. Thus, the special event signal operates
23 to set latch 551 to supply an output signal to AND circuit
24 610. The absence of a special event signal operates latch
551 to supply an output signal to the enabling input of
26 gate 611.
27 As latch 553 was set by the reset pulse on line
28 571, the latch has supplied signals to input 600 of counter
29 555 and to AND circuit 599. Thus, AND circuit 599 is
SA973013 _77_
' '
`` 10~;2553
1 enabled to transmit the eloek pulse from AND eireuit 590
2 to input 601 of latch 553 and, via OR cireuit 602, to
3 input 603 of counter 555. The elock pulse from AND gate
4 599 at input 603 of eounter 555, operates in combination
with the set output of latch 553 at input 600, to load
6 counter 555 with the fixed input of the binary value of
eight. The clock pulse additionally is applied to input
8 601 of latch 553 to reset the latch and subsequently termin-
9 ate the signals to AND circuit 599 and to input 600 of
eounter 555.
11 The preeeding has deseribed in detail the functions
12 of the first eloek pulse on line 585 following the setting
13 of lateh 562 and the oeeurrenee of a signal on line 82. In
14 summary, these funetions inelude resetting latch 562, setting
latch 563, and loading event designation data into register
16 550 and lateh 551. In eontinuing operation, the first elock
17 pulse of eaeh event regeneration performs these same three
18 functions.
19 The second pulse from elock 567 on line 585 is
20 bloeked by AND cireuit 590 due to the reset status of latch ~ -
21 562, is transmitted by AND eireuit 591 due to the set status
22 of latch 563, and is bloeked by AND eireuit 592 because of
23 the reset status of lateh 564. The set output of lateh 563 : :
24 is also supplied to input 622 of eounter 558.
The seeond eloek pulse is thus transmi~ted by AND ~.
26 eireuit 591 to input 625 of lateh 564; via OR eireuit 577,
27 to input 578 of lateh 563; on line 83 to deeoder 51 of
28 Figure 2; to AND eireuits 618 and 620; and via OR eireuit
2~ 623, to input 624 of eounter 558.
'
SA973013 -78- : `
10~:553
1 The clock pulse at input 578 of latch 563 resets
2 that latch, disabling AND circuit 591. The pulse on input
3 625 of latch 564 sets that latch to enable AND circuit 592
4 to transmit one or more subsequent clock pulses from line
585. The pulse on line 83 acknowledge to decoder 51 of
6 Figure 2 the receipt of event designation data on cable 80
7 and line 81.
8 AND circuits 618 and 620 operate in the alternative.
g If the supplied event designation were special event No. 1,
which represents the end-of-line condition, then the signals
11 from the set output of latch 551 and the rightmost bit posi-
12 tion of register 550 cause AND circuit 610 to apply a signal
13 to AND circuit 618 and to inverter 619. The invert~d signal
14 from inverter 619 thus blocks AND circuit 620, while AND
circuit 618 is operated to transmit the clock pulse, via OR
16 circuit 582, to input 583 of latch 553. Thissets the latch
. 17 to provide signals to AND circuit 599 and to input 600 of
18 counter 555. These signals will respond to the next sup-
19 plied event designation to load counter 555 with a binary
20 eight. :~ -
21 If the received event designation was other than ~ :
22 special event No. 1, then the absence of a signal from
23 AND circuit 610 serves in conjunction with inverter 619
24 to enable AND circuit 620 and to block AND circuit 618.
The clock pulse is thus transmitted by AND circuit 620 to
26 input 628 of latch 560. The clock pulse therefore sets
27 the latch to provide an output signal to AND circuit 629.
D 28 As will be described, the set output of latch 560 thus
29 enables AND circuit 629 to provide a one data bit on line
SA973013 -79_ -
1(~42553
1 542 upon counter 558 being loaded with, or decrementing
2 to, 0.
3 The clock pulse from AND circuit 591 is also
4 applied to input 624 of counter 558. The combination of
this input pulse with the signal on input 622 from latch
6 563, operates to load counter 558 with the output of OR
7 circuit 615. Now the output of OR circuit 615 has one of
8 three possible values, depending upon the particular event
9 designation. If the event is a regular event, then the
signal from reset output of latch 551 enables gate 611,
11 while the absence of a signal from the set output of this
12 latch blocks AND circuit 610 which disables gate 616; in
13 this case, the event designation number in register 550 is
; 14 loaded into counter 558. On the other hand, if the event -:~
is special event No. 1, then the absence of a signal from
16 the reset output of latch 551 disables gate 611, while the
17 signals from the rightmost bit position of register 550 :~
18 and the set output of latch 551 cause AND circuit 60 to .
19 enable gate 616; in this case the contents of counter 555 ~;
20 is loaded into counter 558. Finally, if the event is ::
21 neither a regular event nor special event No. 1, that is,
22 if the event is special event No. 2, then both gates 611 ~: -
23 and 616 are disabled; in this case counter 558 is loaded
24 with all zeroes.
The preceding has described in detail the functions
26 of the second clock pulse on line 585 followingthe setting
27 of latch 562 and the occurrence of a signal on line 82. :
28 In summar~, these functions include resetting latch 563,
29 setting latch 564, transmitting an acceptance pulse on ~ .. - .
~.
SA973013 -80-
. .
~04Z5S3
1 li.ne 83 to decoder 51 of Figure 2, loading counter 558,
2 and possibly setting latch 560.
3 Subsequent clock pulses from clock 567 on line
4 585 are blocked by AND circuits 590 and 591, because
la~ches 562 and 563 are in the reset condition. Since
6 latch 564 is set, the signal from the set output of this
7 latch provides an enabling input to AND circuit 592.
8 The remaining enabling input to AND circuit is line 543;
9 a signal on line 543 indicates that the scan line buffers
540 are ready to accept information from the event regenera-
11 tor circuitry.
12 Upon the occurrence of a signal on line 543 to
13 indicate that the scan line buffers 540 are ready to accept
14 data, AND circuit 592 is enabled to transmit clock pulses
appearing on line 585. Subsequent clock pulses are thus
16 transmitted by AND circuit 592, via OR circuit 623, to
17 input 624 of counter 558, and to AND circuits 635 and 637. -~ -
18 Since latch 593 is in the reset condition, the
19 absence of a signal from the set output of this latch causes
the absence of a signal on input 622 of counter 558. The
21 absence of a signal on input 622 enables clock pulses ap-
22 pearing on input 624 to decrement counter 558.
23 AND circuits 635 and 637 operate in the alternative,
24 under the control of AND circuit 632. The presence of a
signal from AND circuit 632 enables AND circuit 635 to
26 transmit clock pulses, while inverter 636 acts to block
27 AND circuit 637. Conversely, the absence of a signal from
28 AND circuit 632 blocks AND circuit 635, while inverter
29 636 supplies a~ enabling signal to AND circuit 637,
` '-' `
SA973013 -81-
,, ; , ' . , . , ':
1()42SS3
1 If counter 558 was loaded with ~ number othcr
~ than zero, then it supplies at least one positive output
3 to OR circuit 630. OR circuit 630 therefore supplles a
4 signal to inverter 631, which supplies no signal to AND
circuits 639 and 632. The resulting absence of a signal
6 from AND circuit 629 is interpreted as a zero data bit at
7 input 542 of scan line buffers 540. The absence of a
8 signal from AND circuit 632 blocks AN~ circuit 635 and -.
9 causes inverter 636 to enable AND circuit 637, as pre-
viously described, so that a clock pulse transmitted by
11 AND circuit 592 is supplied to AND circuit 640; via OR
12 circuit 602 to input 603 of counter 555; and to input
13 544 of scan line buffers 540. The clock pulse at AND
14 circuit 640 is blocked by the absence of a signal from
15 AND circuit 629. The clock pulse at input 603 of counter .
16 555, in conjunction with the absence of a signal on input
17 602 from the set output of latch 553, operates to decre~
18 ment counter 555. As will be explained, the clock pulse ~-, -
19 on line 544 to scan line buffers 640 causes the buffers
20 to accept the zero data bit available on line 542. ~ .
21 If counter 558 was loaded with the nu~ber zero,
22 or upon the decrementing of that counter to zero, O~ cir-
23 cuit 630 provides no output signal to inverter 631. The :~:
24 inverter therefore supplies a signal to AND circuits 629 ~.:
and 632. The outputs of these AND circuits are thus con-
26 trolled by latch 560.
27 Latch 560 has been set if a one data bit is to be
28 transmitted to scan line buffers 560, following the trans-
29 mission of a number of zero data bits equal to the number
SA973013 -82-
~04Z5S3
1 loaded into coullter 55~; that is, latch ~60 has becn set
2 unless the event designation specified special event No.
3 1. If latch 560 has been set, thell the set output of this
4 latch causes AND circuit 629 to provide a signal which is
interpreted as a one data bit at input 542 of scan line
6 buffers. The absence of a signal from the reset output of
7 latch 560 causes a corresponding absence of a signal from
8 AND circuit 632, which disables AND circuit 635 and causes -- -
9 inverter 636 to enable AND circuit 637, as previously
described Therefore, a clock pulse transmitted by AND
11 circuit 592 is supplied by AND circuit 637 to AND circuit
12 640; via OR circuit 602, to input 603 of counter 555; and
13 to input 544 of scan line buffers 540.
14 The signal from AND circuit 629 enables AND circuit
15 640 to transmit the clock pulse, via OR circuit 581, to in~
16 put 580 of latch 560, thereby resetting the latch. The
17 clock pulse at input 603 of counter 555, in conjunction
18 with the continuing absence of a signal from the set output
19 of latch 553, decrements that counter. The clock pulse on ~ - -
line 544 causes scan line buffers 640 to accept the one
21 data bit available on line 542.
22 FinaLly~ upon counter 558 being set to zero, or
23 ~being decremented to zero, and upon latch 560 being reset,
24 OR circuit 630 supplies no signal to inverter 631. In-
verter 631 and the reset output of latch 560 thus both
26 supply signals to AND circuit 632, which therefore supplies ~ ;
27 a signal to AND circuit 635 and to inverter 636. This
28 signal enables AND circuit 635 and causes inverter 636 to
29 block AND circuit 637. The next clock pulse transmitted
' ' ~ "' '
SA~73013 -83-
, :
,. , .. , ~ . . , -. .
-: :. . . . .. . .
~4'~553
1 by AN~ circuit 529 is thus supplied by AND circuit 635,
2 via O~ circuit 575, to input 576 of latch 562; via OR
3 circuit 577, to input 578 of latch 563; to input 579 of
4 latch 564; and via OR circuit 581 to input 580 of latch
S60. Thus, latch 562 is set and latches 563, 564 and 560
6 are reset. The event regenerator circuitry is thereby
7 placed in the ready to receive condition for accepting
8 the next event designation from decoder 51 in Figure 2.
9 Scan line buffers 432 in Figure 21 and scan line
buffers 540 in Figure 22 can be identical. For the pur-
11 pose of illustration, one possible implementation for the
12 scan line buffers 432 in Figure 21 is shown in Figure 23.
13 The scan line buffers include primarily two shift
14 right registers 650 and 651. ~uring one cycle, register
650 will be supplying data at the output 436 while shift
16 register 651 is receiving data from input 431. During
17 the subsequent cycle, the shift registers will alternate
18 such that shift register 650 will be receiving data from
L9 input 431 while shift register 651 will be supplying data
to output 436.
21 Latch 654 indicates whether register 650 is available
22 to receive or transmit data, and latch 655 provides the
23 same indication for shift register 651. Both latches pro-
24 vide their reset output to the input side of the buffer
circuitry and their set output to the output side of the
26 buffer circuitry
27 Latch 660 selects the buffer to respond to the
28 input data, and latch 661 selects the shift register to
29 supply the output data. Counter 662 counts the input clock
,
- SA973013 84-
.
1 pulses and latch 6~3 responds ~o the counter to control
2 the input buffer selection. Counter 664 counts the clock
3 pulses from the output side and latch 665 controls the out-
4 put buffer selection.
To begin a new operation, a reset pulse is applied
6 on line 471. The reset pulse is supplied, via OR circuit
7 670, to input 671 of latch 663; via OR circuit 672, to in-
8 put 673 of latch 660; via OR circuit 674, to input 675 of
9 latch 654 and input 676 of latch 661; via OR circuit 678,
to input 679 of latch 655; and, via OR circuit 680, to in-
11 put 681 of latch 665. The reset pulse thus sets latches
12 660, 663 and 665, and resets latches 654, 661 and 655. -
13 The set output of latch 660 is supplied to AND
14 circuits 685 and 686. The reset output of latch 655 is ~ :
also supplied to AND circuit 685. Thus, the AND circuit
16 supplies an output signal to AND circuits 687, 688 and 689. :
17 In addition, the output signal is transmitted, via OR cir- ~ ~
18 cuit 690, to line 433. This indicates to the input source ~ - .
19 of data that the buffer, in particular shift register 651,
is available for accepting the input data. At the same
21 time, the set output of latch 663 is supplied to input 692 :~
22 of counter 662 and to AND circuit 693. The signal at in-
23 put 692 of counter 662 enables the counter to be loaded
24 upon appearance of the first clock pulse at input 434.
25 Finally, the absence of a signal from the reset output of ;
26 latch 660 causes the absence of a signal from AND circuit
27 700, which blocks AND circuits 720, 705 and 712. The ~: .
28 buffer circuitry is therefore set to receive input data,
29 which is directed to shift register 651. ~ -
SA973013 -85-
' ': -
-
104ZS53
The reset output of latch 661 is supplied to AND
2 circuits 695, 696, 697 and 698. It thus selects register
3 651 as the next available output buffer. However, latch
4 655 is currently reset to indicate that register 651 is
available for receiving input data, and therefore unavail-
6 able for transmitting output data. Therefore, no signal
7 is supplied to AND circuit 697, which blocks a ready signal
8 from OR circuit 699 and from line 500. At the same time,
g latch 654 supplies its reset output to AND circuit 700, and
10 latch 655 supplies its set output to input 701 of counter
11 664 and to AND circuit 702.
12 As the result of the reset pulse on line 471, the
13 buffer circuitry is thus arranged to receive data from in- -
14 put 431 and clock pulses on line 434, but unavailable to
transmit data on output line 436.
16 After transmission of the ready signal on line 433, -~
17 a series of clock pulses may be received on line 434 accom- ;
18 panied by some or no data signals on line 431. The first
19 such clock pulse is applied to AND circuits 705 and G88, to
20 input 706 of counter 662 and to AND circuits 707 and 693.
21 The clock pulse is blocked by AND circuit 705, but is trans-
22 mitted by AND circuit 688, via OR circuit 710, to input 711
23 of shift register 651. If the data bit accompanying the
24 clock pulse is a one, then a signal appears on line 431 to
25 AND circuits 712 and 687. The data bit is blocked by AND
26 circuit 712, but is transmitted by AND circuit 687 to input
27 713 of shift register 651. The combination oE a data signal
28 at input 713 in conjunction with a clock pulse at input 711
29 operates the shift register to shift a one into the leftmost
SA973013 -86-
104ZS53
1 position of the register, as the remainder of the register
2 is shifted to the right. If no data signal is supplied at
3 input 713 at the same time as the clock pulse at input 711,
4 the shift register shifts to the right one position, thereby
shifting a zero into the first bit position.
6 The clock pulse at input 706 of counter 662, in
7 conjunction with the signal from the set output of latch 663 -
8 at input 692, causes the counter to be loaded with the binary
9 value six fixed as its input. The signal from the set out-
put of latch 663 also enables AND circuit 693 so that the
11 clock pulse is transmitted thereby to input 715 of latch 663.
12 This causes the latch to reset, terminating the signal at
~ .
13 input 692 to counter 662, and blocking AND circuit 693. The
14 reset output of latch 663 then comprises one of the enabling
inputs of AND circuit 707.
16 Subsequent clock pulses similarly shift data into
17 shift register 651 and are applied to input 706 of counter
18 662, decrementing the counter. As long as the counter con-
19 tains a value greater than zero, it continually supplies an
output signal at at least one of its outputs or to OR circuit
21 716. This output is inverted by inverter 717 to supply no
22 signal to AND circuit 707, thereby blocking the AND circuit.
. -
23 The seventh clock pulse at line 434 decrements ~
24 counter 662 to zero. Subsequently, its all zero output at --
OR circuit 716 results in inverter 717 supplying a positive
26 enabling signal to AND gate 707. The eighth clock~pulse
27 appearing on line 434 is there~ore gated by AND circuit
28 707 to OR circuit 670, and to AND circuits 720, 721, 686
and 689.
.
. .. .~: .
SA973013 -87- ~
.'' " ' ~
, .. : . , :. . ' ~.
; ' ~ ~ " , , :
104~553
1 The clock pulse transmitted by OR circuit 670 to
2 input 671 of latch 663 causes the latch to be set, so that
3 it again provides a loading signal at input 692 of counter
4 662.
The set output of latch 660 has resulted in the
6 enabling of AND circuits 686 and 689. The clock pulse
7 transmitted by AND circuits 707 and 689 is applied to input
8 723 of latch 655, thereby setting the latch. The latch thus -~
9 applies enabling signals to AND circuits 725 and 697. Since
10 latch 661 was in t~e reset state as the result of the reset -~
11 pulse at line 471, AND circuit 697 is thus enabled to trans-
12 mit the output of latch 655, via OR circuit 699, to line 500.
13 This signal therefore indicates that register 651, the buffer -
14 in particular, is ready to transmit data to the output.
Lastly, the clock pulse from AND circuit 707 is
16 transmitted by AND circuit 686 to input 726 of latch 660.
17 This resets the latch, terminating its enabling output to
18 AND circuits 686 and 685. The previous setting of latch 655
19 also terminated the other input to AND circuit 685, so that -
the enabling inputs of AND circuits 687, 688 and 689 are al-
21~ ready terminated. The reset output of latch 660 therefore
22 applies signals to AND circuit 721 and AND circuit 700.
23 Since latch 654 was already reset by the reset pulse at line
24; 471, the output therefrom previously enabled AND circuit 700.
Therefore, the reset output of latch 660 is transmitted
26 thereby to enable AND circuits 712, 705 and 720, and further
27 to be transmitted by O~ circuit 690 to line 433. This indi-
28 cates that the buffer, in particular shift register 65Q, is ~`
29 available for the receipt of data from the input.
SA973013 -88-
, ~ .: . . ; ~ . ; . .
^` 1042~53
1 Shift registers 650 and 651 are therefore now in
2 condition to receive data from the input source and, inde-
3 pendently, to transmit data to the output receiver.
4 The outputting of data from register 651 is done in
5 response to the clock pulses receiv~d at line 437. Each ~ ~ ;
6 clock pulse is transmitted by AND circuit 698, AND circuit
7 725 and OR circuit 710 to input 711 of shift register 651.
The shift register responds to each applied clock pulse by
9 shifting to the right and supplying the successive bits to
AND circuit 696. AND circuit 696 remains enabled by latch
11 661, so that the data bits are transmitted via OR circuit .2 i~-
12 728 to data line 436.
13 Each clock pulse is also applied to input 729 of
14 counter 664 and to AND circuits 730 and 702. The first
clock pulse at input 729, together with the signal supplied
16 at input 701 by the set output of latch 665, causes counter
17. 664 to load the permanently affixed binary value of six ~.
18 therein. Since latch 665 was set by the reset clock pulse, ::
19 the signal from the set output of this latch enables AND :~ .:
circuit 702, while the absence of a signal from the reset
21 output of this latch blocks AND circuit 730. The first
22 clock pulse is thus transmitted by enabled AND circuit 702 - .
23 to input 734 of latch 665. This pulse resets the latch,
24 terminating the signals at input 701 of counter 664 and at ~ -
- .
AND circuit 702. The reset output of the latch is applied
26 to AND circuit 730.
27 Thus, as with respect to counter 662, counter 664
28 will decrement with each further applied clock pulse until :
29 the seventh clock pulse decrements the clock counter to
'
..
SA973013 -89-
iO4;~S53
1 zero. Then, the absence of a signal from OR circuit 732 causes inverter733 to apply an enabling signal to AND circuit 730. The eighth applied
clock pulse is therefore gated by the AND circuit 730, via OR circuit
680, to input 681 of latch 665, and to AND circuits 795 and 737. The
pulse at latch 665 causes the latch to set, again providing a loading
signal at input 701 of counter 664.
As latch 661 is in the reset condition, the clock pulse is trans-
mitted by AND circuit 695 to input 738 of the latch. This sets the
latch, so that it provides outputs to AND circuits 737, 740, 741 and 742.
This indicates that shift register 650 will be selected to provide the
output data, when latch 654 indicates that it is available.
The output of AND circuit 695 is also applied, via OR circuit 678
to input 679 of latch 655. This resets the latch to terminate the set
output therefrom; the resulting reset output from this latch is supplied -
to AND circuit 685. This indicates that shift register 651 is available
to receive data from the input, when latch 660 indicates that this
register is selected.
Register 650 is operated in an identical fashion to that of
register 651. Briefly discussed, the clock pulses from the input are
supplied thereto, via AND circuit 705 and OR circuit 744. The clock
pulses are thus applied to input 745 of the shift register. The input
data is applied, via AND circuit 712, to input 746 of the shift register. -
When shift register 650 is loaded, counter 662 supplies a signal, via
AND circuit 720, to input 748 of latch 654. This sets the latch, turning
off the reset output which had enabled
SA9-73-013 - 90 -
. . . : .; ~ . . .
..
1~4~SS3
1 ~ND clrcuits 712, 705 and 720. The set output of latch
2 654 is supplied to AND circuit 7~9 and to AND circuit 742.
3 AND circuit 749 is thus enabled to transmit any clock pulses
4 from the output device at line 437. The signal at AND cir-
cuit 742 indicates that shift register 650 is ready to
6 transmit data to the output, depending upon selection thereof.
7 by latch 661, via the set output thereof. If both latches
8 654 and 661 are set, AND circuit 742 supplies a signal, via
9 OR circuit 699, to line 500. The clock pulses are then sup-
plied from the output device on line 437, via AND circuits
11 740 and 749, and OR circuit 744, to operate the shift register -
12 650. The shift register thus supplies the output data, via
13 AND circuit 741 and OR circuit 728, to line 436. Counter
14 644 also responds to the clock pulses by counting sufficient
15 bits to indicate a scan line. -
16 The exemplary scan line buffers 432 in Figure 21
17 have been described in detail, and can be identical to the ~
18 scan line buffers 540 in Figure 22. Other types of buffer -
19 mechanisms may be used equally well, and the arrangement of
Figure 23 is provided on an exemplary basis.
2I The shift registers, registers, decrementing counters, ~ `
22 incrementing counters, adders, AND circuits or gates, OR
23 circuits, clocked latches, latches, clocks and inverters are -
24 all commercially available semiconductor circuits for which
interconnection in the manner shown by the present drawings
26 and specification would be apparent to those skilled in the
27 art. It is envisioned that similar circuit elements may be
28 connected in similar manners to perform the same functions
29~ in a similar way.
SA973013 -91-
~ .
.:
104;~
l While the invention has becn particularly shown and
2 described with reference to preferred embodiments thereof,
3 it will be understood by those skilled in the art that various
4 changes in form and details may be made therein without depart-
ing from the spirt and scope of the invention.
e-: .
.
.
SA973013 -92-
.
.. . ..
