GB1570343A – Information storage and retrieval system
– Google Patents
GB1570343A – Information storage and retrieval system
– Google Patents
Information storage and retrieval system
Download PDF
Info
Publication number
GB1570343A
GB1570343A
GB5203/78A
GB520378A
GB1570343A
GB 1570343 A
GB1570343 A
GB 1570343A
GB 5203/78 A
GB5203/78 A
GB 5203/78A
GB 520378 A
GB520378 A
GB 520378A
GB 1570343 A
GB1570343 A
GB 1570343A
Authority
GB
United Kingdom
Prior art keywords
word
signal
absolute
bit
value
Prior art date
1975-12-03
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired
Application number
GB5203/78A
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
System Development Corp
Original Assignee
System Development Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
1975-12-03
Filing date
1976-12-01
Publication date
1980-07-02
1976-12-01
Application filed by System Development Corp
filed
Critical
System Development Corp
1980-07-02
Publication of GB1570343A
publication
Critical
patent/GB1570343A/en
Status
Expired
legal-status
Critical
Current
Links
Espacenet
Global Dossier
Discuss
Classifications
G—PHYSICS
G06—COMPUTING; CALCULATING OR COUNTING
G06F—ELECTRIC DIGITAL DATA PROCESSING
G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
G06F16/22—Indexing; Data structures therefor; Storage structures
G06F16/221—Column-oriented storage; Management thereof
Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
Y10S707/00—Data processing: database and file management or data structures
Y10S707/99931—Database or file accessing
Y10S707/99933—Query processing, i.e. searching
Description
PATENT SPECIFICATION ( 11) 1 570 343
e ( 21) Application No 5203/78 ( 22) Filed 1 Dec 1976 ( 19) t ( 62) Divided out of No 1570341 A ( 31) Convention Application No 637511 ( 32) Filed 3 Dec 1975 in ‘ u Be > ( 33) United States of America (US) W 1 ( 44) Complete Specification Published 2 Jul 1980 _ ( 51) INT CL 3 GO 6 F 15/40 ( 52) Index at Acceptance \ D G 4 A 13 E 13 M 2 C 5 A 8 C 9 C JR ( 72) Inventors: THOMAS EDWARD DECHANT EDWARD LEWIS GLASER PAUL ELDRED PYTT FREDERICK WAY, 111 ( 54) INFORMATION STORAGE AND RETRIEVAL SYSTEM ( 71) We SYSTEM DEVELOPMENT CORPORATION, a corporation organised and existing under the laws of the state of Delaware, United States of America, of 2500 Colorado Avenue Santa Monica, California 90406, United States of America, do hereby declare the invention for which we pray that a patent may be granted to us, and the method by which it is to be performed, to be particularly described in and by the following 5
statement:-
This invention relates to information storage and retrieval systems.
The present invention is, from one aspect, an encoder for converting to hybrid form a received series of absolute words in a decreasing value order comprising means arranged in operation to 10 a) respond to received previous and current absolute words for forming an output signal indicative of the difference therebetween; b) indicate absolute or bit string form of hybrid output comprising means arranged in operation to 1) indicate a preselected minimum difference between the values represented by 15 successively received absolute words for absolute form of output, 2) compare the minimum difference indication and the previous and current difference signal and for indicating the value of the first being greater than, or less than or equal to the latter:
c) provide absolute form outputs comprising 20 1) means operative in response to said less than or equal to indication for outputting the current absolute word and an absolute flag; and d) provide bit string form outputs comprising 1) means responsive to said greater than indication and arranged in operation to form a set of ordered signals comprising a binary bit of one value in association with the number of 25 binarv bits of a second value corresponding to the value of said previous and current difference signal and 2) means arranged in operation to selectively output said set of signals in association with a bit string flag and in a predetermined relation to an outputted absolute word.
The present invention is, from another aspect, an encoder for converting to hybrid form a 30 received series of absolute coded words in decreasing value order comprising:
a) a current register arranged in operation to store a currently received absolute word; b) means arranged in operation to store a received absolute word in said current register:
c) a previous register arranged in operation to store a word received prior to the word in 35 said current register; d) means arranged in operation to transfer a word from said current register to said previous register:
e) means responsive to the stored previous and current absolute words and arranged in operation to form an output signal indicative of the differences in values therebetween; 40 ? 1 1 570 343 f) means arranged in operation to retain the previous and current different signal; g) means arranged in operation to indicate absolute or bit string form of hybrid output comprising 1) means arranged in operation to indicate a preselected minimum difference in value between received absolute words for absolute form of output, 2) means arranged in operation to compare the minimum difference indication and the retained previous and current difference signal and for indicating the value of the first being greater than, or less than or equal to, the latter; h) means arranged in operation to provide absolute form outputs comprising 10 1) means arranged in operation to respond to said greater than indication for outputting a signal representing the stored current absolute word and an absolute flag; and i) means arranged in operation to provide bit string form outputs comprising 1) means arranged in operation to respond to said less than or equal to indication for forming a set of ordered signals comprising a binary bit of one value in association therewith binary bits of a second value the number of which corresponds to the value of said retained 15 previous and current difference signal, and 2) means arranged in operation to selectively output a signal representing said set of ordered signals in association with a bit string flag and in a predetermined relation to an outputted absolute word.
The present invention is, from a further aspect, a decoder for converting hybrid coded 20 signals to absolute coded word signals, the hybrid signals representing a series of occurrence values of decreasing value, the hybrid signals comprising a series of received binary coded word signals including at least one absolute coded word and a bit string word, the bit string word representing an occurrence by the number of bits of displacement of a bit of 25 predetermined value either from another bit of the same predetermined value or from the value represented by an absolute word in the series of hybrid words, a hybrid word comprising a flag signal indicating the type of word comprising:
a) absolute word outputting means comprising means arranged in operation to respond to an absolute word flag signal of a received hybrid word signal to output the received word 30 signal and b) absolute word signal forming and outputting means comprising means arranged in operation to 1) shift register means arranged in operation to store a received bit string word signal, 2) means arranged in operation to repeatedly enable the shifting of the content of the shift register means one bit position in the direction of the least significant bit of the bit string word signal, 3) means arranged in operation to provide an indication when a bit signal indicative of said predetermined value arrives at a preselected position with respect to the shift register means, 40 4) counter means, 5) means arranged in operation to respond to a flag signal indicating a received absolute word signal to set said counter means to a state relative to a reference state corresponding to the value of such absolute word signal, 6) means arranged in operation to enable said counter means to count one state towards said reference state for each such shift of said shift register means, and 7) means arranged in operation to respond to said indication of a bit to output a signal corresponding to the state of said counter means.
Embodiments of the present invention will now be described, by way of example, with reference to the accompanying drawings, in which:Figure 1 is a general block diagram of the data processing machine (DPM); 50 Figures 2, 3 and 4 form a schematic and block diagram of the ENCODE MODULE; Figure 5 is a diagram showing the relationship of Figures 2, 3 and 4; Figure 6 is a schematic and block diagram of the ALU used in various modules in the DPM SYSTEM; Figures 7 and 8 form a flow diagram illustrating the sequence of operation of the ENCODE MODULE; Figures 9 and 10 form a schematic and block diagram of the DECODE I MODULE; Figure 11 is a flow diagram illustrating the sequence of operation of the DECODE I MODULE; The disclosed embodiment of the present invention involves a compaction technique in 60 which the occurrence vectors are represented in a hybrid encoded form ‘Occurrence vectors’ is a term used to identify binary coded values which identify the relative times at which an event occurs Information is stored in a MEMORY MODULE in hybrid encoded form.
Referring now to Table 2 possible occurrence values are depicted, and immediately 65 1 570 343 below, the corresponding binary bits representing an occurrence vector are depicted at 1.
An occurrence vector is said to be in bit string form where a binary 1 or a binary 0 is used to represent the presence or absence of each actual occurrence value This form of representation is depicted at line 1 in Table 2 Line 2 of Table 2 depicts the same information in a binary coded decimal form called absolute code form Thus, bit string form 5 for the information of Table 2 requires 8 digits, each with l binary bit, for storage, whereas absolute code form requires five digits, each with 3 binary bits, for storage.
Each digit in bit string form requires only one binary bit for storage, whereas each of the digits in absolute form requires three binary coded bits However, if the number of blanks or O’s between two binary ones (occurrences) becomes large, it will be seen that a point will 10 be reached where it will be shorter and save memory space to represent the information in absolute form Stating it differently, the distance between the binary l’s in the bit string form determines whether bit string enclosing or absolute encoding will give the best compaction and hence the shortest length of information to be stored.
By way of example, in a very side occurrence vector (i e one with a large number of l’s 15 and O’s the distance between two event-times or occurrences may be great For example, one occurrence value may be 5 and the next 2,673 In this case, absolute encoding should be used since it requires much fewer binary coded bits of information for storage If the distance between event-times is short, and the number of occurrences is therefore frequent, bit string encoding will be better 20 Hybrid encoding refers to an occurrence vector which uses a combination of bit string form and absolute form encoding The present invention involves a technique where a hybrid encoding is used A brief description of the hybrid encoding will now be given.
Table 3 depicts in hybrid code an example of the most significant six words of storage for an occurrence vector containing occurrences at event times 87, 88, 90, 93, 100, 114, 116, 25 119, 123 and 125 Each word contains a bit or “flag” at the left-hand end which identifies whether it is a bit string word or an absolute word A binary 1 indicates an absolute word whereas a binary 0 indicates a bit string word Disregarding the bit string/absolute form bit at the left-hand of each word, each binary bit string word contains the largest occurrence value at the right-hand end and the smallest at the left hand 30 Word 1 is in absolute form and represents 125 with the most significant binary bit at the left and the least significant binary bit at the right (disregarding the bit string/absolute form bit at the left end of the word) Word 2 is in bit string form and has seven binary bit positions representing possible occurrence values 118 through 124 but it only contains actual occurrence values depicted by binary l’s for occurrence values 119 and 123 35 During the process of encoding to hybrid code, an occurrence vector in bit string form is scanned backward from the right-hand end to the left-hand end from the latest event time or largest occurrence value to the earliest event time or smallest occurrence value, assigning absolute and bit string form to the words for storage in memory Memories are normally organized so that information is stored in words As the occurrence values are scanned from 40 the largest to the smallest, absolute and binary form words are assigned so as to give the maximum compaction Thus, word 1 is in absolute coded form and represents the occurrence value 125 Word 2 is in bit string form and has binary l’s at the second and sixth position in the word, indicating occurrence values of 123 and 119 Word 3 is in bit string form with binary 1 bits at the second and fourth positions, representing occurrence values of 45 116 and 114 Encoding is changed from absolute to binary coded form when more than seven bits can be saved by switching from bit string form to absolute form The occurrence value 100 is 14 possible occurrence values away from the occurrence value 114 In the encoding procedure it is necessary to check the efficiency of changing the forms of representation by calculating the number of bits that are saved Since there are three 50 possible occurrence values to the left of occurrence value 114 in word 3, three bits are potentially wasted by switching to absolute form, plus, it will require a full word of seven binary coded bits to represent the information in absolute form Thus a total of 10 ( 7 + 3) bits are required for changing to absolute coded form, producing a saving of four bits.
Therefore, it is desirable to switch from binary form to absolute form Thus, as depicted in 55 Table 2 word 4 is in absolute form and represents the occurrence value 100.
Occurrence value 93 is seven possible occurrence values from the occurrence value 100.
Since seven bits are potentially saved (not more than 7) the form of encoding is not changed and the encoding for the next word 4 will remain in absolute form.
Occurrence value 90 is only three bits away from occurrence value 93 Accordingly, bit 60 string encoding is more efficient and word 6 is in binary string form.
Hybrid encoding is used to store all occurrence vectors in the DPM system Therefore, although one particular line in an iso-entropicgram may product the shortest length of occurrences in bit string form, it may be found that another line of the same iso-entropicgram will actually produce the shortest length when converted to hybrid form 65 A 4 1 570 343 I Hybrid encoding is used to encode all of the occurrence vectors sent back to the auxiliary memory for storage and all occurrence vectors read from the auxiliary memory for processing by the rest of the DPM SYSTEM.
Decoding of the occurrence vectors read from the auxiliary memory and processed in the DPM INTERFACE MODULE is accomplished by entering the hybrid coded string of words largest occurrence value first Information is processed in the DPM SYSTEM in absolute coded form Accordingly, the DECODE I and DECODE II MODULES depicted in Figure 1 translate all hybrid coded information transferred from the auxiliary memory into the MEMORY MODULE into absolute coded form for processing by the DPM SYSTEM Similarly, the ENCODE MODULE translates all processed information in the 10 DPM SYSTEM from absolute form back to hybrid coded form for storage in the MEMORY MODULE and subsequent transfer back to the auxiliary memory The details for performing encoding and decoding in the ENCODE and DECODE MODULES will be described hereinafter with respect to each of these modules 15 1 Conventions and Components Used in the Figures Each of the modules has control input/output lines (narrow lines) and information input/output lines (heavy lines) By way of example, the ENCODE MODULE shows these lines along the right hand side of Figure 3 The narrow lines used to represent each control input/output line represent a single conductor Each heavy line represents 8 conductors for 20 carrying 8 binary coded bits of information in parallel Arrows to the left indicate incoming signals to the corresponding module whereas arrows to the right indicate outgoing signals.
Symbols are shown at the tail of each arrow representing each incoming control input/output line Each of these symbols not only uniquely identifies each line, but identifies the source or module from which the signal for that line originates 25 The convention employed is to use one or two letters followed by one or more numbers.
The letters identify the originating module and the number gives a unique identification to the line For example, Figure 3 of the ENCODE MODULE shows the symbol SM 2 for the top line The signal for that line originates in the SEED MODULE Table 4 gives a list of the letter symbols and the corresponding module Some control input/output lines have 30 identifying symbols which do not follow this convention and the originating module is identified.
Outgoing control input/output lines (arrows to right) are also labeled The symbols on the left (tail of arrow) are logic representing the logical equations for gates used in generating 3 the signal on the outgoing line A symbol is used at the arrowhead to identify the line as it leaves and enters other modules For example, in the ENCODE MODULE, the logic P 9 represents a gate used to generate a logic signal on the line EW 1.
Gating is shown in block diagram in some instances and in others, logical equations are used to represent the gating for simplification Standard symbols are used in the logical 40 equations Thus, a ” 4 ” represent an “OR” condition; a ” ” represents an AND condition; and symbols representing the outputs from flip flops, gates, register, counters, etc are used as the terms in the equations By way of example, logical gating is depicted in the ENCODE MODULE, Figure 4 to reset the flip flop EFRST to 0 The logic is:
P 5.G ERFST CLK The gate represented by this logic is true when true signal are formed at each of the outputs indicated in the equation This, of course, illustrates an AND gate with each of the indicated outputs as inputs to an AND gate The logic P 1 O G+P 7 GE+P11.Co for flip flop P 11 represents three AND gating conditions combined by two OR gating conditions.
Flip flops are extensively used throughout this patent application One type of flip flop 5 used extensively employs a type SN 7474 positive edge triggered D-type flip flop disclosed at page 121 of the book entitled The TTL Data Book for Design Engineers, published 1973 by The Texas Instruments Co Each of these flip flops is identified by a rectangular box with a line in the upper left hand corner, such as that shown for flip flop P 12 of Figure 4 Each of these flip flops is characterized in that an input exists at the top side and one at the bottom side and two inputs exist at the left hand side Also, each has a pair of complementary 55 outputs at the right hand side, the upper one of which has the same symbol as the flip flop (i.e P 12) and the lower one of which has a line over the top referred to as prime (i e, P 12) These flip flops operate as follows A true signal applied at the top side (without clock) sets the flip flop to a 1 state, causing true and false signals at the unprimed and primed outputs respectively (i e, P 12 and P 12) A true signal applied at the bottom side 60 sets the flip flop (without clock) to a 0 state causing false and true signals at the unprimed and primed outputs, respectively (i e, P 12 and P 12) The lower left side input of these flip flops is for clock and the upper left side input is for control of the state into which the flip flop is set responsive to clock at the lower left hand side input A true signal at the upper left side input causes the corresponding flip flop to be set to a true state responsive to a 65 A 1 570 343 simultaneously applied true clock pulse at the lower left side input, and a false signal at the upper left side input causes the corresponding flip flop to be set to a false state responsive to a simultaneously applied true clock pulse at the lower left side input.
To simplify the drawings, the outputs on the right side of flip flops are not always shown as they are for flip flop P 12 For example, see flip flop Pl of the ENCODE MODULE 5 However, the unprimed and primed outputs are always implied and will be used at various places in the system For example, the Pl output of flip flop Pl is not shown on the right of flip flop P 1, but it is shown in the logical equation P 1 GE for controlling the upper left side input to flip flop P 1.
Similar to the control input/output lines and the information input/output lines, heavy 10 connecting lines are used throughout to designate multiple signal conductors whereas a thin line represents a single conductor.
Selection circuits are used throughout the system By way of example, the ENCODE MODULE has selection circuits ED 51-ED 57 The selection circuits each have two or more labeled multi-bit information input circuits, each input circuit for receiving multiple binary 15 coded bits of information, and one multi-bit output for receiving the same number of bits as an information input The information input circuits are labeled directly on the outside of the box such as ED 51-ED 57 of the ENCODE MODULE In some cases, the labels are implied such as for selection circuit D 51 of the DPM INTERFACE MODULE where the label is implied to be the same as the originating circuit of the information signals Also, 20 each selection circuit has a control input corresponding to each of the information inputs which is correspondingly labeled inside of the box A true signal at the correspondingly labeled control input causes the selection circuit to couple only those signals at the correspondingly labeled information input to the output circuit By way of example, in the ENCODE MODULE, a true signal at the 1 side control input of selection circuit ED 51 25 causes the output of register 104 to be coupled through ED 51 to the left input of the ALU.
Various modules also have an arithmetic logic unit ALU of the type SN 74181 disclosed at page 381 of the above TTL book An ALU is shown by way of example in the ENCODE MODULE Figure 2 The arithmetic unit ALU is characterized in that 8 bit signals coded in the 1 2, 4, 8 binary coded number system applied at the inputs #1 and #2 enable ALU to 30 form 8 bit signals coded in the same number system, at an output OP A true signal applied at the ADD input causes a signal at the output OP representing the sum of the two coded signals applied at #1 and #2 Whereas, a control signal applied at the SUB input causes a signal at OP representing the difference between the signals at #1 and #2 in 2 ‘s complement form 35 The arithmetic unit ALU has additional outputs G, L and E A true signal is formed at the G L and E outputs, respectively, when the number represented by the code signal at #1 is “greater than” (>) -less than” (<), and "equal to" (=) than at #2.
The ALU design shown here is for a 4 bit chip However, it could be generalized into larger groupings In all likelihood, larger capacity ALU's (e g, 24 or 32 bits) would make 40 use of type SN 74182 look ahead carry generators, of the above TTL book However, these are not necessary for an 8 bit wide ALU.
It will be obvious to those skilled in the art that minor circuitry peripheral to the SN 74181 is required to receive the true signals and provide the output signals shown and described with reference to the ALU and these circuits aredepicted in the block diagram of Figure 6 45 Some modules have unprimed inputs whereas a primed form (i e, EOFI) is used in the module The primed form (i e EOFI) merely indicates the logical inverse of the unprimed form which is formed by conventional signal inverter circuits Signal inverter circuits are not alwavs shown but are implied in some instances.
Although specific hardware is disclosed for various modules in the DPM system, it should 50 be noted that the modules might also be implemented using micro programmed mini computers with appropriate firmware programs.
ENCODE MODULE A General Description 55
Section I GENERAL DESCRIPTION OF DPM SYSTEM describes hybrid form of coding of the information, with respect to the example in Table 3 The ENCODE MODULE is provided in the DPM SYSTEM of Figure 1 for the purpose of converting absolute coded occurrence vectors to hybrid coded form and controlling the writing of the hybrid coded occurrence vectors into the MEMORY MODULE 60 At the outset it should be kept in mind that occurrence vectors represent a series of occurrence values out of a larger set of incrementally ordered possible occurrence values or event-times Occurrence vectors are stored, retrieved and processed such that the highest numbered occurrence value is first The highest numbered occurrence value identifies the most recent occurrence in the event-time domain The lowest numbered entry, and hence 65 1 570 343 the entry farthest back in event-time, is stored, retrieved and processed last Examples of delimiter and event occurrence vector (in absolute coded form) are shown at " and "T" of Table 1 This form of information representation is quite important to an understanding of the ENCODE MODULE embodiment about to be described and with respect to each of the other module embodiments about to be described 5 The MEMORY MODULE reads and writes information a word at a time A word has 8 binary bits of infl Ormation.
The ENCODE MODULE in the encoding process processes each occurrence vector as follows:
The ENCODE MODULE is called each thime an absolute occurrence is to be encoded by 10 either the REVOLVE MODULE or the OUTPUT MODULE The module which calls the ENCODE MODULE is hereinafter called the calling module.
The ENCODE MODULE receives the absolute occurrence values of an absolute coded occurrence vector in decreasing value order A currently received absolute word and a previously received word in the series ale held and compared The difference between the 15 current and previous absolute values represent the numbher of binary bits of displacement between them If the difference is gireater thlian soi C "specified number of bits" (in this case 7 bits), then the previous absolute value is outputted in the hybrid word series as an "absolute" word (see word O of Table 3) If the difference is less than this "specified number of bits', the present absolute value is entered as an occurrence into a bit string 20 word (see word 2 of Table 3) of the hybrid series The latter is accomplished by shifting the bit string word under formation the number of bit positions designated by the difference and entering a bit of predetermined value, i e, " 1 ", into the bit string word, and the ENCODE MODULE is '-exited" by terminating its operation When a bit string word under formation is complete it is also outputted It should be noted that binary bit at the 25 most significant end of each word being outputted is reserved as a type or flag bit to indicate form of the hybrid word A I'' bit flag indicates an absolute word whereas an "O" bit flag indicates a bit string word.
The hybrid form to which the absolute occurrence values are encoded is a series of absolute and bit string words starting with an absolute word An absolute word in itself 30 represents the value of one occurrence by a combination of binary coded signals A bit string word represents an occurrence value by the number of possible occurrence values of displacement of an occurrence of predetermined value, i e, " 1 ", from the previous absolute word or from the previous occurrence of predetermined value in the hybrid word series The first word of each hybrid word series is always an absolute word and therefore in 35 itself, identifies the value of the first and largest occurrence However, it should be understood that within the broader concepts of the invention, the invention may be employed in a system which is not bound by words, in which case the bit string portion of the hvbrid form would not be confined to words.
Another purpose of the ENCODE MODULE is to perform "clipping" and "clipping" by 40 "interval" Clipping is the operation of determining if each absolute word occurrence value lies between a top limit (TL) and a bottom limit (BL) This operation is performed by comparing each absolute word with TL and BL If the input entry is
The EIR register is shown with two special outputs Eo and Eo True signals are formed at 65 1 570 343 these outputs when the content of the EIR register is 0 and not 0, respectively It will be understood that an appropriate circuit (not shown) is connected to the SB 74100 register for forming these signals Preferably, the circuit has the ” 1 ” output of each bit position connected to the input of a common “OR” gate The output of the “OR” gate is the Eo output, whereas the output of the “OR” gate is connected through an inverter to the Eo 5 output.
The ER register is a data latch of type SN 74116 of the above TTL book and is similar to the SN 74100, except that it has a “CLEAR” line which provides a one step clearing operation.
Register EOP consists of a flip flop MSB and a seven bit parallelin/parallel-out shift 10 register 114 of type SN 74199 as disclosed at page 456 of the above TTL book Register 114 is a 7 bit register and is characterized in that parallel loading is accomplished by applying the 7 bits of data at its upper side and making the shift/load (S/L) control input low or false when the CLOCK input is not inhibited, i e, receives a true signal A true signal at S/L causes a shift to the right by register 114 responsive to the leading edge of a true pulse at the 15 CLOCK input A false signal at S/L causes the 7 bits applied at its upper input to appear at the output of the register 114 and be stored therein responsive to the leading edge of a true pulse at the CLOCK input.
Considering register EOP in more detail, a false signal at P 9 causes register 114 to load the input signals applied at the upper side Typically, a true signal is simultaneously formed 20 at P 9-BSW to the MSB flip flop When CLK goes true, P 9 BSW CLK becomes true and, being applied to the CLOCK input of the MSB flip flop and the register 114, causes the MSB flip flop to be set true and load 7 bits of information from register EO.
In addition, the ENCODE MODULE has counters MAR 3, MLN 3, CTR and NOC.
CTR has 8 states, NOC, MAR 3 and MLN 3 each have 256 states and are of type SN 74161 25 disclosed at page 325 of the above TTL book.
CTR is a 3 bit up/down counter of type SN 74191 disclosed at page 417 of the above TTL book and is characterised in that a false signal at U/D causes the counter to count up when a true signal is applied to the CT input and a true signal at U/D causes the counter to count down when a true signal is applied to the CT input The counter can be preset to a value 30 corresponding to the signals applied at its input at the upper side while applying a true signal to the L input The block indicating CTR contains a circuit not shown, similar to that described for the ER register for forming true signals at the Co and Co outputs when the state of CTR is 0 and not 0, respectively The counter CTR counts through its prefixed sequence of 8 states and automatically resets to its initial or 0 state 35 Each of the MAR 3, MLN 3, and NOC counters are of type SN 74161 of the above ITL book and are controlled to always count upwards Not shown but included within each box is a logical signal inverter to invert the signal at CLR before it reaches the SN 74161 A true signal applied at the CLR (CLEAR) inputs of MAR 3, MLN 3 and NOC causes them to be cleared or reset to a ” O ” state A true signal at the CT input causes the counters MAR 3, 40 MLN 3 and NOC to count up.
The ENCODE MODULE also has flip flops EFRST, ELAST, BSW, ECE, U/D and MSB In addition, a control counter 113 has flip flops Pl and P 12.
The ENCODE MODULE also has a source of recurring clock pulses 102 The source of clock pulses 102 forms a series of equally spaced (not essential) recurring true clock pulses 45 at its output The output of source 102 is connected to one input of an AND gate 112 which forms clock signals at CLK whenever the other input to gate 112 is true in coincidence with a clock pulse A signal inverter 117 inverts the signal at CLK to form pulses at CLK.
The ENCODE MODULE also has an arithmetic logic unit ALU at #1 and #2 in 2 ‘s complement form Conventional OR gates 108 and 110 are connected to G, L and E so that 50 true signals are formed at a GE output of 108 and a LE output of 110, respectively, when the values of the signals at #1 are “equal to or greater than” (ó) that at #2, and “equal to or less than (S) that at #2.
The ENCODE MODULE also has selection circuits ED 51-ED 57 of the type disclosed above The ENCODE MODULE also includes conventional logical OR gates 104110, 118 55 and 119 and an AND gate 112.
C Detailed Description
The ENCODE MODULE can be most readily understood with reference to the description in connection with the block diagram, Figures 2-4, and the corresponding flow 60 diagram Figures 7-8 As an aid, Table 5 contains symbols used to identify the counters, registers, flip flops, and one-shot multivibrators, together with the mnemonic meaning of the svmbols used Also as an aid, the flow diagram contains P numbers adjacent to the various blocks, i e, (P 1), (P 2), etc These P numbers correspond to the outputs of the control counter 113 and thereby indicate the state of the control counter during which the 65 1 570 343 indicated action shown in the flow diagram takes place However, the same P number appears for more than one box Therefore, for added ease in making reference to the flow diagram, symbols EB 1 through EB 26 are used to identify each box in the flow.
Table 5 shows the principal information inputs and 6 utputs and the input control for the ENCODE MODULE Top clipping limit, bottom clipping limit, interval and iso 5 entropicgram width are each 8 bits long and are loaded into registers of the ENCODE MODULE by the modules indicated in Table 5.
Assume initially that clipping is not to be performed in which case OPSW, ETL, EBL, and EIR are all initially 0 Also assume that the ENCODE MODULE is about to be called for its encoding function for the first time Preliminary to calling the module, the current 10 absolute word is received by the ED 56 selection circuit either from the D 54 output of the REVOLVE MODULE or from the ORT 1 register of the OUTPUT MODULE The first current absolute word to be received is the first or largest absolute coded word ( 8 bits in length) of an occurrence vector After the REVOLVE MODULE supplies the current absolute word, true signals are formed at RM 11 and RM 6 by the REVOLVE MODULE 15 When the current absolute word is being supplied by the OUTPUT MODULE, true signals are formed at O M 13 and O M 14 by the OUTPUT MODULE A true signal at RM 11 causes the ED 56 selection circuit to couple the current absolute word at D 54 to the information input of register El The true signal at RM 6 enables the OR gate 109 to activate the load (L) input of El and load the current absolute word into EI Similarly, a true signal at O M 13 20 causes ED 56 to route the information input from the ORT 1 output to the information input of El and the true signal at O M 14 enables the OR gate 109 to activate the load (L) input of El and load the current absolute word into El It should be noted that all current absolute words for one occurrence vector are supplied in sequence largest to smallest by the same calling module 25 The iso-entropicgram width (HW) is stored in the input parameter register file IPRF.
Loading of the iso-entropicgram width into EHW is enabled by true signals at any one of the following outputs: OM 1 output of the OUTPUT MODULE; SM 3 output of the SEED MODULE; and the CM 3 outlet of the CHANGE MODULE.
OPSW is an output circuit of the OPSW flip flop in the OUTPUT MODULE OPSW is 30 the logical inversion of OPSW Only the OUTPUT MODULE determines if clipping is to take place and, if it is to take place, the OPSW flip flop is in a 1 state, otherwise it is in an 0 state Since it is assumed for the following explanation that no clipping is to take place, a true signal appears at OPSW.
The EFRST flip flop is set to a 1 state whenever the present call on the ENCODE 35 MODULE is for converting the first absolute word in a particular occurrence vector.
EFRST is set by the calling module In the caseof the REVOLVE MODULE, a true signal is formed at the RM 2 output, whereas, in the case of the OUTPUT MODULE, a true signal is formed at the OM 1 output, and enables the OR gate 105 to set the EFRST flip flop to a 1 state 40 The ELAST flip flop indicates if the current absolute word is the last one of an occurrence vector A 1 state of ELAST indicates the last one, whereas the 0 state indicates it is not the last one ELAST is set by the calling module In the case of the REVOLVE MODULE, a true signal is formed at RM 9 and in the case of the OUTPUT MODULE, a true signal is formed at O M 18, either of which causes the OR gate 106 to set ELAST to a 1 45 state.
Assume initially that ELAST is in an 0 state Initially the MINI COMPUTER forms a true signal at MINIT which causes gates 118 and 117 to set all of control counters 113 and flip flop ECE to 0 To be explained hereafter, true signals at EMEND thereafter set these elements to 0 The ENCODE MODULE is called by the REVOLVE MODULE by 50 forming a true signal at RM 7 and by the OUTPUT MODULE by forming a true signal at OM 15 Either of these true signals enables the OR gate 107 to trigger the ENGO one-shot’ multi vibrator which, in turn, causes a true signal at the ENGO output The true signal at the ENGO output causes the ECE flip flop to be set to a 1 state The 1 state of the ECE flip flop causes a true signal at the ECE output which, in turn, causes the AND gate 112 to 55 couple the CLK output of the clock 102 to the clock input of each of the control counter 113 flip flops P 1-P 12 Clock signals now being formed at the output of the AND gate 112 cause the ENCODE MODULE to commence its sequence of operation by virtue of the control action of control counter 113 All flip flops P 1-P 11 being in an 0 state and a true signal being formed at OPSW cause flip flop P 5 to be set to a 1 state, forming a true signal at the P 5 60 output.
One form of clipping is caused by the OPSW flip flop in a 1 state An alternate form of clipping is automatically done by the ENCODE MODULE Specifically, in the alternate clipping, the absolute words of an ocucrrence vector are received by the ENCODE MODULE in decreasing order of magnitude The ENCODE MODULE automatically 65 a 1 570 343 clips or discards all of those absolute words which are larger than the iso-entropicgram width and hence lie outside of the iso-entropicgram The alternative form of clipping is very useful in connection with the REVOLVE MODULE where the result of an exclusive OR is clipped to keep only the lower ordered values which are within the isoentropicgram width.
The ENCODE MODULE with automatically perform this clipping, using flow chart blocks 5 EB 6 and EB 8.
Considering the alternate clipping function in more detail, EFRST is set to 1 when the ENCODE MODULE is called for the first time to encode an occurrence vector This is done to insure that the alternate clipping function is performed Thus at EB 6, flip flop EFRST being in a I state, causes EB 8 to be entered where the isoentropicgram width in 10 register EHW is compared with the input current absolute word in register EI If the content of EHW S El the operation of the ENCODE MODULE is exited by forming a true signal at EMEND, thereby indicating to the calling module (i e, REVOLVE) that it has processed one absolute word Actually, the absolute word is just discarded by the ENCODE MODULE When the calling module again calls the ENCODE MODULE to 15 cause another absolute word of the same occurrence vector to be processed, flip flop EFRST will still be in a 1 state, causing EB 8 to again be entered If the current absolute word is larger in value than the iso-entropicgram width, an exit is again taken This is repeated until at EB 8 the current absolute word is smaller than the isoentropicgram width (e g EHW > El) at which time EB 9 is entered to reset flip flop EFRST to 0 Thereafter 20 when called, the ENCODE MODULE does not perform clipping because the ENCODE MODULE goes from EB 6 to EB 7.
Consider now the operation during EB 8 and EB 9 in detail.
Assume EB 1 I and EB 6 of the ENCODE MODULE flow have been traversed, and assume EB 8 is now entered during which the iso-entropicgram width to EHW is compared 25 with the current absolute word in El If the current absolute word is larger than the iso-entropicgram width, it is outside the iso-entropicgram and therefore a “don’t care” condition exists To perform the comparison, the true signal at P 5 causes ED 51 and ED 52 to couple the contents of EHW and El to the arithmetic unit ALU ALU, together with the OR gates 108 and 110 in turn form true signals at outputs LE and G whenever the content 30 of EHW is respectively > than and < than the content of El If the S condition is sensed true signals are now formed at the P 5 LE and EFRST outputs and the true signal at CLK causes the CLOCK SUSPENSION LOGIC -122 (i e, P 5 'LE'CLK) to reset the ECE flip flop to an O state which, in turn, removes the true signal at ECE and thereby causes the AND gate 112 to stop forming clock signals at the input of the control counter 113 The 35 same signal causes the one-shot EMEND to fire and form a true signal at EMEND This signal notifies the caller that the ENCODE function has been completed It also resets control counter 113 through or gate 112 This, then, in effect causes an EXIT to be taken from the ENCODE MODULE where no action is taken until the next request is made to the ENCODE MODULE from the REVOLVE or OUTPUT MODULE 40 If on the other hand, the content of EHW is > than the content of El (true signal at G), EB 9 is entered Assume during EB 8 the content of EHW is > than that of EI and a true signal is formed at G causing EB 9 to be entered The BSW flip flop states of 0 and 1 indicate the previous absolute word has been entered in the hybrid coded output in bit string form and absolute word form, respectively Since the first hybrid word is always in 45 absolute word form BSW is to be set to 0, indicating that the corresponding output is in absolute word form and the MAR 3 and MLN 3 registers are cleared to initial or 0 states, ready for the first hybrid word to be stored in the MEMORY MODULE.
During EB 9 true signals are formed at the following outputs: G, EFRST, and P 5.
Hence at the following pulse at CLK the counters and registers NOC, MAR 3 and MLN 3 50 and flip flops EFRST and ELAST are all reset to 0.
EB 19 is then entered and the same signals cause ER to be reset to 0 and the reset logic resets BSW and MSB of register EOP to 0.
Following EB 119, EB 20 is entered during which the same true signals are also present which causes load logic to load the current absolute used into EO The current absolute 55 word in EO now forms the previous absolute word for the next call on the ENCODE MODULE The same logic also causes NOC to count up one state, indicating that one absolute word has now been provided to the ENCODE MODULE.
At this point, a true signal is formed at the outputs P 5, EFRST Therefore, the next pulse at CLK the ECE flip flop is reset to 0 thereby disabling the gate 112 from applying clock 60 signals to the control counter 113 as described above.
Subsequently, the calling module again calls the ENCODE MODULE and provides the next current absolute word at which time a true signal is applied at either the RM 7 or OM 15 output (of the REVOLVE or OUTPUT MODULES) causing the OR gate 107 to trigger the one shot multi vibrator circuit ENGO, thereby setting the ECE flip flop back to a 1 state 65 f X 1 ( 1 570 343 i U and enabling the AND gate 112 to apply clock signals to the control counter 113.
At this point, it is assumed that the next current absolute word is not the last one in the occurrence vector and hence the ELAST flip flop is in an O state, forming a true signal at ELAST This causes the next clock pulse from gate 112 to reset flip flop P 5 and set flip flop P 6 to a I state, thereby enabling EBI O to be entered 5 l)uring EB 11, a true signal is formed at the P 6 output which causes E)S l and ED 52 to couple the previous absolute word contained in EO and the current absolute word contained in El to the ALU which forms an output at OP corresponding to the difference.
T’his difference is referred to as the previous and current difference signal Additionally, the 1 ( signal at ED 57 causes the selection circuit ED 57 to gate the previous and current difference 10 signal to the information input of the ET into which the signal is loaded by the subsequent clock signal at (‘ K Thus, ET now contains the previous and current difference signal which is the number of bits of displacement (either in event time or in possible occurrence values) between the current absolute word in El and the previous absolute word in EO.
Additionally, the true signal at P 5 causes the U/D flip flop to be reset to a I state, asserting 15 its true signal at the UID output, thereby causing CTR to be set so that it counts down The 116 output of the 1 P 6 flip flop is connected directly to the input of the 1 ‘7 flip flop, thus the following clock coming out of the gate 112 causes the P 7 flip flop to be set to a 1 state, thereby entering EB 11.
During EB I 1 the previous and current difference signal contained in E’ is subtracted 20 from the remaining binary bit signal contained in ER The remaining binary bit signals represent the remaining binary bits to be filled in the bit string word being formed in EOP.
The subtraction results in a difference signal during EB 11 which indicates one of two values and these will now be explained If the content of ER is larger than or equal to ET, the difference is than 0, meaning that the difference represents the remaining available bits in 25 the bit string word (now under formation in EOP) after current absolute word is entered If the content of ER is < than ET, the difference is less than 0 (or -), meaning that the difference represents the number of bits needed in the next bit string word (to be formed) to enter the current absolute word An example of these two conditions is now given: the bit string word has a maximum of 7 available bits (see register 114 in EOP having 8 bits, less 1 30 flag bit = 7) Assume the remaining available binary bits signal in ER = 5 and the previous and current difference signal in ET = 3, giving a positive difference of 2 The difference of + 2 represents the remaining available bits in the bit string word after the current absolute word If the values are reversed (ER = 3 and ET = 5), then the difference is -2 and represents the number of bits needed in the next bit string word to enter the current 35 absolute word In other words, the current absolute word will require all remaining available bits (ER) in the current bit string word under formation in EOP plus 2 additional bits in the next bit string word to be formed.
When on a previous call to the ENCODE MODULE it was found (during EB 18) that the current absolute word was to be outputted in absolute word form, ER was reset to 0 at 40 EB 18 and hence is O at the next entry to EB 11 Under these conditions, a difference less than O is formed during EB 11 However, the difference is the negative of ET ( 0-ET = -ET).
Consider now the details of operation Assume that the ENCODE MODULE is at EB 11 and a true control signal is being formed at the P 7 output This causes ED 51 and ED 52 to couple the content of ER and ET to ALU which, in turn, forms an output 45 representing ER ET Assume the result is < O A control signal is formed at the L output of ALU, indicating that there are insufficient bits in EOP for the current absolute word.
EB 12 is entered.
During EB 12 the control signal at P 7 and L causes ED 57 and the load logic for ET to store the number of bits needed in the next bit string word signal being formed at EOP into 50 ET at the following pulse at CLK Additionally, the same true signals cause ED 53 and the load logic of CTR to store the content of ER into the counter, setting it to a state corresponding to the content of ER If ER contains 0, as occurs when this is only the second call on the ENCODE MODULE and hence is the second time through the flow, the true signals at P 7 and L also cause the flip flop P 8 to be set into a 1 state, thereby causing EB 13 55 to be entered If ER contains 0, CTR is set to 0, causing a true signal at the Co output The true signals at P 8 and Co cause the P 9 flip flop to be set to a 1 state and EB 15 is entered, thereby skipping EB 14.
To be explained in more detail, EB 14 causes the bit string word being formed in EOP to be filled out with leading O 's This operation, and hence EB 14, is skipped when ER is 0 60 since no remaining bits need to be filled in the bit string word under formation.
Return now to EB 11 and consider the operation when ER is not 0 and ER-ET is < O causing a true signal at the L output of ALU Note that ER is not 0 when a bit string word is being formed in EOP and available bits exist in EOP in the bit string word under formation.
EB 12 and 13 are entered as discussed above and CTR is set to a state corresponding to the 65 1 {\ 1 57 ( O 343 number of binary bits remaining to be filled value contained in ER D) uring EBI 4, a true signal exists at P 8 and Co (CTR is not 0) and each pulse at CLK counts CTR down one and causes the EOP shift logic to shift the bit string word one bit position in the direction of the least significant bit thereof until CTR reaches 0, at which time the true signal at Co is removed and one is formed at Co This causes ('TR and E'OP to stop counting and shifting 5 and EB 15 is entered as discussed above.
Assume that during ABI 5 the BSW flip flop is in an () state, having previously been set there during EB 19 thereby indicating that the next event in the hybrid output from the previous event is to be in the form of an absolute word With BSW in an O state, EBI 6 is entered DURING EBI 6, the false signal at P 9 causes the load logic of register 114 to load 10 the previous absolute word contained in EO into the registerl 14 of E()l' and true signals at P 19 and BSW cause the logic 1 '9 BSW to set the MSB flip flop to a I state, indicating that the word in EOP is an absolute word Subsequently, E 1 117 is entered.
During E 13 17, the P 9 output (see right hand of ENCO)DE MODULI, scheinatic) causes a Write Enable signal (EWI) to be formed in the MEMORY MODULL, causing it to store 15 the absolute word contained in EOP into the storage location designated by the content of MAR 3.
The true signals at P 19 and the pulse at CLK cause the content of MAR 3 and MLN 3 to count up one state In this manner, the counter MLN 3 always indicates the number of memory writes and hybrid coded words written in the MEMORY MOI)ULE Thus, an 20 absolute word is outputted by the formation of the true signal at the 1 P 9 output which, in turn, causes the MEMORY MODULE to read the absolute word from EOP.
Return now to EBI 1 and consider the situation where a previous absolute word is contained in E() a current absolute word is contained in EI, and ER is > ET ALU forms the difference between ER and ET (i e, ER ET) and ALU and gate 108 form a true 25 signal The difference signal at the output OP of ALU represents the remaining available bits in the bit string word now under formation in EOP after entry of the current absolute word in El Under these conditions, the bit string word being formed in EOP is shifted by the number of bit positions indicated by ET and the current absolute word is entered into EOP 30 To this end, EB 22 is entered from EB 11 The true signals formed at P 7 and GE cause the load logic of ER to store the difference signal being formed at the OP output of ALU into ER at the occurrence of the following pulse at CLK Thus, ER now contains the new number of bits remaining to be filled in the bit string word under formation which will exist after the current absolute word is entered Additionally the same signals cause ED 53 and 35 the load logic to store in CTR the previous and current difference signal in ET The true signals at P 7 and GE cause the P 11 flip flop to be set to a 1 state at the next clock signal from gate 112 and thereby enter EB 23.
During EB 23 and the subsequent state EB 24, CTR is enabled to count through a sequence of states corresponding in number to the previous and current difference signal 40 which was set into CTR from ET To this end, the true signal at Pl and at CLK, together with the true signal at U/D cause CTR to count down 1 state responsive to each true signal at CLK Additionally in the absence of an 0 state of CTR, a true signal is formed at the Co output The true signals at P 11, Co cause the register EOP to be shifted 1 bit pbsition to the right in the direction of the least significant bit This operation continues until the counter 45 reaches 0 and a true signal is formed at the Co output When a true signal is formed at the Co output, counting and shifting of CTR and EOP is complete and the ENCODE MODULE is ready to enter the value of the current absolute word in EI into the shifted bit string word in EOP EB 25 is entered.
During EB 25, a true signal is formed at the Co output and the subsequent true signal at 50 CLK causes the flip flops MSB of EOP and BSW to be set to a 1 state To be explained, the 1 bit stored in MSB is subsequently shifted into register 114 of EOP during EB 26, thereby causing a bit of predetermined value i e, a 1 bit, the bit string word being formed in EOP.
The number of bit positions existing between the currently formed 1 bit and the previously formed 1 bit or between the currently formed 1 bit and the previous absolute word in the 55 series of hybrid word outputs indicates the value of the current absolute word The 1 state of BSW indicates that a bit string word is now being formed in EOP.
The true signal at P 11 and Co cause the flip flop P 12 to be set to a 1 state at the following clock signal from gate 112 and EB 26 is thereby entered.
During EB 26 a true signal is formed at the P 12 output and the subsequent pulse at CLK 60 causes the content of EOP, including the content of MSB and register 114, to be shifted 1 bit position toward the right toward the least significant end, thereby placing the 1 bit into the register 114 portion of EOP.
EB 20 is now entered During EB 20, a control signal is now formed at the P 12 output and the BSW flip flop is in a 1 state The subsequent pulse at CLK causes load logic to store the 65 1 570 343 current absolute word contained in El into EO thereby forming a new previous absolute word and causes NOC to count up one state, thereby indicating that another absolute word has been encoded into hybrid form NOC counts, and thereby indicates, the number of 1 bits processed in any given seed Additionally, the true signal at P 12 causes the ECE flip flop to be set to an () state at the pulse at CLK, disabling clock signals at the output of gate 5 112 causing the EMEND monostable to lire and thereby form a true signal at the EMEND output This causes counter 113 to be reset and the ENCODE MODULE OPERATION TO EXIT.
A very important operation in the ENCODE MODULE is depicted at EB 18 This is the condition under which previous and current difference signal contained in ET is compared 10 with a predetermined threshold value This is the heart of the decision which enables a change, in hybrid output, from bit string word form to absolute word form and the operation is accomplished as follows During EB 18, the P 10 flip flop is in a 1 state, causing atrue signal at the P 11 output This causes ED 51 and ED 52 to couple the switches 104 and the output of El’ to ALU The ALU compares the applied signals and adds the content of 15 ET to the value 7 represented by the switches 104 and forms a result at OP It should be noted that when EB 18 is entered, the content of the ET is always a negative number, the number being stored in 2 ‘s complement form The reason for this situation is that ET at this point in the operation always indicates the number of bits needed in the next bit string word to enter the current absolute word which is a situation where at EB 11, ET was larger than 20 ER resulting in a negative value Thus, at EBI 8 when ALU combines the content of ET with the value 7 from 104, a difference signal is formed If the difference signal is > 0, i e, the value 7 is > the absolute value in ET, a control signal is formed at G and EB 21 is entered If the value 7 is the absolute value in ET, the difference signal will be S 0, causing a control signal at the LE output of OR gate 110, which in turn causes EB 19 to be 25 entered The result of the comparison of the value 7 and the absolute value in ET is quite important in determining subsequent operations.
If absolute value in ET is < 7 (the value 7 is greater), a control signal is formed at G and the criteria is not met for switching from bit string word to absolute word in the hybrid output because 7 is greater than the absolute value in ET Accordingly, EB 21-26 are 30 entered where the current absolute word in El is entered in the bit string word under formation in EOP' To this end, EOP is shifted right by the number of bits indicated by the absolute value of the previous and current difference signal contained in ET and then a " 1 " bit entry is made into the bit string word being formed in EOP.
If on the other hand, the absolute value in ET is 3 than the threshold value 7, it would 35 be a saving in memory space to switch from bit string word form to absolute word form.
EB 19-20 is entered During EB 19-20, as discussed above, logic resets flip flop BSW to 0, indicating an absolute word form in the hybrid output for the current absolute word.
The operation during EB 19 and EB 26 has already been discussed hereinabove.
Therefore consider EB 21 During eb 21, true signals are formed at the following outputs: 40 P 10, G and at the following pulse at CLK, the U/D flip flop is reset to an 0 state, causing the counter to be set to count up and EB 2 is entered The least significant 4 bits of the 2 's complement value in ET are set in CTR Therefore as CTR is counted up it will return to 0 after the number of counts represented by the absolute value of ET.
During EB 22, the content of ET is transferred to CTR and subsequently during EB 23 45 and 24, CTR is counted up until it finally is recycled to an 0 state, causing a control signal at Co For each state of CTR, the content of EOP is shifted right by one When CTR reaches 0, the control signal at Co causes the MSB flip flop of EOP to be set to 1, thereby providing another occurrence in the bit string word output and subsequently during EB 26, the 1 bit is shifted into the register 114 of EOP, all as described above 50 Thus, it should now be clearly understood that at EB 18, determining whether the value in ET (the number of bits needed in the next bit string word to enter the current absolute word) is > 7, also determines whether the ENCODE MODULE switches from bit string word to absolute string form of output.
There is at least one occurrence held within the ENCODE MODULE that needs to be 55 written out at the end of its operaton Therefore, after the calling module has finished using the ENCODE MODULE, the occurrence being held must be outputted The calling module outputs the remaining occurrence by setting flip flop ELAST Flip flop ELAST is set by the REVOLVE MODULE by forming a signal at RM 9 and by the OUTPUT MODULE by forming a signal at O M 18, either of which causes the OR gate 106 to set 60 ELAST to a 1 state The 1 state of ELAST causes a true signal at the ELAST output, thereby indicating this is the last call on the ENCODE MODULE for the occurrence vector currently being converted to hybrid form The control signal at the ELAST output occurs when the ENCODE MODULE EXITS during the 1 state of P 5 After the control signal at the ELAST output is formed, a control signal is formed by the REVOLVE or OUTPUT 65 1 570 343 MODULE at RM 7 or OM 15, thereby causing the OR gate 107 to trigger the ENGO shot multi-vibrator, thereby causing the ECE flip flop to be set to a 1 state and hence the AND gate 112 to start providing clock pulses where EB 27 is entered.
During EB 27 the true control signals at P 5 and ELAST enable signals being formed at the output of switches 116, representing the 2 ‘s complement of 8, to be gated through the 5 ED 57 selection circuit and allow the following signal at CLK to load the 2 ‘s complement of 8 (i e, a -8) into ET Additionally, the true control signal at P 5 enables the signal in ER, representing the number of binary bits remaining to be filled (in the bit string word under formation in EOP), to be gated through ED 53 to the input of CTR enabling the same pulse at CLK to load this value into CTR The true signals at outputs P 5 and ELAST cause the P 8 10 flip flop to be set to a I state, thereby causing EB 13 to be entered During EB 13 and 14, the bit string word in EOP is filled out with leading O ‘s and right justifed by shifting the bit string word in EOP and counting CTR down until CTR 046 0 Subsequently, EB 15 and 17 are entered where the resultant bit string word is outputted Of course, should ER be O and hence the CTR is set to 0, right shifting is skipped, and outputting is done immediately 15 The foregoing description of the ENCODE MODULE was made assuming that no clipping was to tak E place Only the OUTPUT MODULE enables clipping to take place If clipping is to take place, the OUTPUT MODULE initially forms true signals which enable the bottom limit register EBL, the top limit register ETL, and interval registers EIR to be loaded To this end, the OUTPUT MODULE forms a true signal at O M 16 and then a true 20 signal at OMI The input of selection circuits ED 54 and ED 55 and register EIR are connected to the BL, TL and IR registers of IPRF Thus, the true signals at OM 16 and OM l cause the bottom limit, top limit and interval value (if an interval value exists) to be strobed from IPRF into EBL, ETL and EIR via the load logic contained in each of these registers The interval value is only used and, hence, an interval value stored in the interval 25 register EIR if the user wishes to ascertain if the output lies in certan intervals For example if the user were to check the intervals between 35 and 25, and then again between and 5 of an occurrence vector, he specifies an interval value of 10 The clipping function in general forces the output to lie between certain values set by the user Thus, the operation of the ENCODE MODULE is to compare the very first absolute word of an 30 occurrence vector, which of course is the highest one, with the content of ETL and EBL If the interval value is 0, i e, it is not desired to check between different intervals, and if the current entry lies outside of either limit, the ENCODE MODULE operation EXITS since the value lies outside of the prescribed limits If, on the other hand, the interval value contained in EIR is other than 0, this means that it is desired to check between different limits and the limits contained in ETL and EBL are reduced to new limits by the interval value in EIR Then the comparison between El and ETL and EBL is repeated using the new reduced limits It should be noted that in the example of the ENCODE MODULE included herewith, it is only desired to check for increments in a downward direction.
Therefore if the current absolute word contained in El is above ETL, the ENCODE MODULE operation automatically EXITS without decrementing.
Consider now the actual clipping and interval function in the ENCODE MODULE The OUTPUT MODULE sets OPSW flip flop, contained therein, to a 1 state When flip fllops P 1-P 1 of the control counter 113 are in an 0 state causing true control signals at the P 1, P 2 P 1 outputs and the OPSW output has a true signal, the next clock causes the Pl flip flop 4 to be set to a 1 state During EB 52, the control signal at the Pl output causes the ED 51 and ED 52 selection circuits to couple the content of ETL and EIR to ALU If the top limit in ETL is < the current absolute word in El, the current absolute word is out of limit and a control signal is formed at the L output of ALU and at the following clock pulse at CLK, 50 the ECE flip flop is reset to 0, disabling the clock to the control counter 113, resetting counter 113 to 0, causing the ENCODE MODULE to EXIT and firing one-shot EMEND.
If the top limit in ETL is the current absolute word in El, a control signal is formed at the GE output of the OR gate 108 A true signal is also being formed at the Pl output and the combination of true signals at Pl and GE causes the P 2 flip flop to be set to a 1 state, thereby causing EB 3 to be entered 55 During EB 3, the content of EBL is compared with the content of El To this end, the true signal at P 2 causes ED 51 and ED 52 to couple the content of EBL and EIR to ALU If the bottom limit in EBL is > the current absolute word in El, a control signal is formed at the G output of ALU and EB 4 is entered If, on the other hand, the bottom limit in EBL is 6, the current absolute word in El gate 110 forms a control signal at LE, causing EB 6 to be 60 entered The operation following EB 6 is the same as that described above and need not be reconsidered here.
However, assume that the bottom limit in EBL is greater than the current absolute word in El and a control signal is formed at the G output, causing EB 4 to be entered EB 4 is only shown in the ENCODE MODULE flow in order to indicate that a decision is made based 65 1 I 570 343 on whether the interval value contained in EIR is O or > 0 If, at the time, true signals are formed at P 2 and G, the content of EIR is not 0, a control signal is formed at the Eo output of EIR The true signal at Eo in coincidence with the control signal at P 2 and G enables the P 3 flip flop to be set to a I state at the following clock signal from gate 112, thereby entering EBS.
During EB 5, the top limit in ETL and bottom limit in EBL are decremented by the interval value contained in EIR To this end, a true signal is now formed at the P 3 output, causing EDSI and ED 52 to couple the values contained in EBL and EIR to the input of ALU, thereby causing ALU to form a decremented bottom limit corresponding to the difference (EBL EIR) The true signal at P 3 also causes ED 54 to couple the decremented bottom limit at Ol D to the input of EBL The subsequent signal at CLK causes the load logic of EBL to store the decremented bottom limit into EBL Thus, EBL now contains the previous bottom limit value decremented by the interval value contained in El R The true signal at the P 3 output causes the P 4 flip flop to be set to a 1 state at the following clock signal from gate 112 The control signal at P 4 causes ED 51 and ED 52 to couple the content of the top limit in ETL and the interval value in EIR to ALU, causing ALU to form a decremented top limit at OP representing the difference (ETL EIR) The control signal at the P 4 output causes ED 55 to couple the decremented top limit from OP to ETL and the following signal at CLK causes the decremented top limit to be stored in ETL Thus, ETL now contains the previous top limit value decremented by the interval value contained in EIR EB 2 and EB 3 are again entered where the input value is again compared, this time with the decremented top and decremented bottom limit values as described hereinabove.
D Example of Operation A better understanding of the operation of the ENCODE MODULE will be had with reference to the following ENCODE MODULE example During this example, it is assumed that the ENCODE MODULE is called six times to convert the following input entries from one occurrence vector and coded in absolute form to hybrid form: 125, 123, 119 116, 114 100 To further aid in understanding of the invention, it is assumed that no clipping is to take place Although the clipping function is an important feature in one aspect of the invention Rather than give a complete word description of the following operation, the operation is indicated in symbolic form.
Input on the initial call:
OPSW = O ETL = EBL = EIR = 0 EFRST = 1; EHW = 128 El = 125 The sequence followed is:
EB 1 EB 6, EB 8 EB 9, EB 19 EB 20 EBI: OPSW = O control goes to EB 6 EB 6: EFRST = 1 ‘ control goes to EB 8 EB 8: El ( 125)< EHW ( 128) The input is less than the iso-entropicgram width therefore, control goes to EB 9; EB 9: EFRST = ELAST = O reset flip flops; NOC = O clear number of occurrences; MAR 3 = MLN 3 = 0 clear output memory area address register and length register; EB 19: ER = 0 indicates there are no remaining bits left in output register EOP Here used to force an absolute ones index form (AOI) output on the next call; BSW = 0 indicates we are in absolute ones index form; EB 20: EO( 125) = EI( 125) current input becomes previous input; NOC( 1) = NOC( 0) + 1 up the number of occurrences by one; HALT Output : EOP = 0 MLN 3 = 0 NOC = 1 Memory area blank 1 57 ( O 343 Second call: El = 123 EFRST = 0 Sequence of control:
EBI OPSW = O ' control to EB 6 EB 6 EFRST = O 'control to EB 7 EB 7 ELAST = O ' control to EB 10 EBI O ET( 2) = EO( 125) EI( 123) set U/D = 1 ' CTR to count dowr 1 13 BII ER( 0) ET( 2) < O EB 12 El = -2 CUR ( 0) = ER ( 0) E 113 CTR = O control to EB 15 E 1315 BSW = O ' control to EB 16 EBI 6 EOP( 125) = EO( 125) MSB (EOP) = 1 E B 17 Memory write of EOP MAR 3 ( 1) = MAR 3 ( 0) + I MLN 3 ( 1) 046 MLN 3 ( 0) + 1 EBI 8 ET(-2) + 7 > 0 EB 21 Set counter to count-up U/D = O EB 22 ER( 5) = ET(-2) + 7 CTR( 6)<-ET(-2) EB 23 EB 24 EB 23 CTR( 7) EOP = CTR( 0) EB 25 EOP = BSW = EB 26 EOP = = CTR( 6) + 0 XXXXXXX = CTR( 7) + 1 () 1 (= 0) 10000000 1 XXXXX EB 20 EO( 123) = EI( 123) NOC( 2) = NOC( 1) + 1 HALT Output EOP = 010 XXXXX MLN 3 = 1 NOC = 2 Other parameters remain as for first call; EB 1, EB 6-EB 7, EB 10-EB 13, EB 15-EB 18, EB 21-EB 24, EB 23, EB 25-EB 26, EB 20 bit distance between previous and absolute word; the current absolute word cannot be placed in the remaining number of bits in EOP control to EB 12; kept in 2 's complement form; i e, ET = 11111110; the amount the output register must be shifted if in bit string form, to keep alignment; set output equal to previous input set sign bit to indicate absolute pointer to next memory area address; current physical length of output; control to EB 21 since the number to be clocked to CTR is < 0, must count up to reach 0; number of remaining bits that can be used in EOP; the counter is loaded from the rightmost 3 bits of the 2 's complement of -2, i e 11111110 control to EB 24 shift EOP right; control to EB 25 since CTR is 3 bit register, adding a 1 to the 7 causes wraparound to occur; turn on sign bit; indicates bit string form; shift EOP right one since sign bit position is used to indicate type; current absolute word becomes previous number of occurrences is bumped; Memory Area 11111101 X = remaining bits to be used Third call EI = 119 Sequence of control EB 1 OPSW = 0 ' control to EB 6 EB 6 EFRST = 0 ' control to EB 7 EB 7 ELAST = 0 ' control to EB 10 EB 10 ET( 4) = EO( 123) EI( 119) EB 11 ER( 5) ET( 4) > 0 other paramaters remain the same; EB 1, EB 6-EB 7, EB 10-E B 11, EB 22-EB 24, EB 23-EB 24, EB 23-24, EB 23, EB 25-EB 26, EB 20 ET = bit distance to be considered.
control to EB 22 1 570 343 EB 22 ER( 1) = ER( 5) ET( 4) CTR( 4) = ET( 4) EB 23 EB 24 EB 23 EB 24 EB 23 EB 24 EB 23 EB 25 EB 26 EB 20 HALT CTR( 3)<-CTR( 4) 1 (/) EOP = 0010 XXXX CTR( 2) CTR( 3) 1 (d= 0) EOP = 00010 XXX CTR( 1) = CTR( 2) 1 (-0) EOP = 000010 XX CTR( 0) = CTR( 1) 1 (= 0) EOP = 100010 XX BSW = 1 EOP = 0100010 X EO( 119) = EI( 119) NOC( 3)-NOC( 2) + 1 OUT EOP = 0100010 X MLN 3 = 1 NOC= 3 Fourth Call EI = 116 Sequence of control EB 1, EB 6, EB 7 EB 10 ET( 3)<-EO( 119) EI( 116) EB 11 ER( 1) ET( 3) ( 5/81/40) control to EB 12 EB 12 ET(-2)-ER( 1) ET( 3) CTR( 1)-ER( 1) EB 13 CTR( 1): O EB 14 CTR( 0) = CTR( 1) 1 EOP = 00100010 EB 13 CTR( 0) = 0 EB 15 BSW = 1 EB 17 write EOP to memory MAR 3 ( 2)<-MAR 3 ( 1) + 1 MLN 2)<-MLN EB 18 ET(-2) 7> 0) EB 21 set U/D = 0 EB 22 ER( 5) = ET(-2) + 7 CTR( 6)< ET(-2) EB 23 EB 24 CTR( 7) = CTR( 6) + 1 (L) EOP = 00 XXXXXX EB 23 CTR( 0) = CTR( 7) + 1 (= 0) control to EB 25 EB 25 EOP = 10 XXXXXX BSW = 1 EB 26 EOP = 010 XXXXX EB 20 HALT Output EO( 116) = EI( 116) NOC( 4)-NOC( 3) + 1 EOP = 010 XXXXX MLN 2 = 2 NOC = 4 ER = number of bits left in EOP after current absolute word process; number of positions EOP must be right shifted before the sign bit is set; control to EB 24 control to EB 24 control to EB 24 control to EB 25 set on the most significant bit; indicate bit string; shift EOP right; current absolute word becomes previous bump the number of occurrences; Memory Area 11111101 All other parameters remain the same; EB 1, EB 6-EB 7, EB 10-EB 14, EB 13, EB 15, EB 17-EB 18, EB 21-EB 24, EB 23 EB 25-EB 26, EB 20; same as before; obtain bit distance; there are not enough bits to process this entry using current information in EOP; ET = 11111110 in 2 's complement form; number of positions that EOP must be shifted to keep alignment; control to EB 14 right shift EOP; control to EB 15 control to EB 17 next memory address; physical length of memory area; control to EB 21 CTR to count up CTR = rightmost 3 bits of 2 's complement ET = 11111110; control to EB 24 shift EOP X = remaining usable bits for EOP; 3 bit register therefore wraparound on the add; set sign bit in EOP; indicate bit string form; shift EOP since sign bit indicates type; previous input is replaced by the current; Memory Area 11111101 00100010 1 57 ( O 343 Fifth Call El = 114 sequence of control EBI EB 6, EB 7 EBI O ET( 2)-EO( 116) EI( 114) set the counter to down EBII ER( 5) ET( 2) > O EB 22 ER( 3) = ER( 5) ET( 2) CTR( 2)-ET( 2) EB 23 CTR(I) = CTR( 2) I (p= 0) EB 24 EOI’ = 0010 XXXX EB 23 CTR( 0)-CTR( 1) I (= 0) 11 825 EOP = 1010 XXXX BSW = 1 EB 2 o EOP = 01010 XXX EB 20 EO( 114) = EI( 114) NOC( 5 (-)NOC( 4) + 1 HIA Ll, Outpult EOP 01010 XXX MLN 3 = 2 NOC 5 Siuh (‘Call El = 100 sequence of conlltrol EBI EB 6, EB 7 E 13 10 ET( I 4)-EO( 114) EI( 100) t set U/D = 1 CTR o count down EB 11 ER( 3) ET( 14) (< 0) EB 12 ET(-I l),-ER( 3) ET( 14) CTR( 3) = ER( 3) EB 13 CTR( 8) = O EB 14 CTR( 2) = CTR( 3) 1 EOP = 001010 XX EB 13 CTR( 2) = O EB 14 CTR( 1) = CTR( 2) 1 EOP = 0001010 X EB 13 CTR( 1) + O EB 14 CTR( 0) = CTR( 1) 1 EOP = 00001010 EB 13 CTR( 0) = O EB 15 BSW = 1 EB 17 write memory EOP MAR 3 ( 3) = MAR 3 ( 2) + 1 MLN 3 ( 3) = MLN 3 ( 3) + 1 EB 18 ET-( 11) + 7 < 0 EB 19 ER = O BSW = 0 EB 20 EO( 100) = EI( 100) NOC( 6)<-NOC( 5) + 1 HALT Output EOP = 0 MLN = 3 NOC = 6 remaining parameters remain the same; EBI 1, EB 6, EB 7, EBIO-E B 111, EB 22-EB 24, EB 23, EB 25-EB 26, EB 20; same as before; bit distance; control to EB 22 update the remaining; number of bits; control to 1 B 24 shift EOP right; control to kh 25 set sign bit ol I,)l' indicate bit slring form; shift EOP; Memory Area 11111101 00100010 all other parameters remain the same; EBI, EB 6-E 1 87, 1110-EBI 4, EB 13-EB 14, 11113-EBI 4, EB 13, EB 15, EB 17-E 132 ( O; same as before; control to EBI 2 ET in 2 's complement form; number of positions EOP must be shifted to keep alignment; control to EB 14 control to EB 14 control to EB 14 control to EB 15 control to EB 17 control to EB 19 assure next call will write; current absolute word to be in absolute word form; Memory area 11111101 00100010 00001010 1 570 343 Seventh call set ELAST = 1 sequence of operation EB 1, EB 6 EB 7 ELAST = 1 EB 27 CTR( 0) = ER( 0) ET = -8 EB 13 CTR( 0) = 0 EB 15 BSW = 0 EB 16 EOP( 100) = EO( 100) set sign bit of EOP EB 17 write EOP MAR 3 ( 4) MAR 3 ( 3) + 1 MLN 3 ( 4) MLN 3 ( 4) + 1 E B 18 ET(-8) + 7 < 0 EB 19 ER = O BSW = O EB 20 EO( 100) = EI( 100) HALT EOP = O MLN 3 = 4 NOC = 6 all other parameters remain the same; EB 1, EB 6-EB 7, EB 27, EB 13 EB 15-EB 20; same as before; control to EB 27 in case we are in bit string; assure proper balance at EB 118; control to EB 15 control to EB 16 prepare the output; indicates absolute word type; next address; length; control to EB 19 these are meaningless steps on the last time through note that NOC is not incremented this time; Memory area 11111101 00100010 00001010 11100100 In summary, what has been disclosed is an encoder for converting to hybrid form a received series of absolute word signals of decreasing value order The hybrid form has a series of at least one absolute word signal and bit string word signal An absolute word signal represents the value of one occurrence by the combination of binary coded bit signals A bit string word signal represents one occurrence by the number of bits of 35 displacement of a bit of predetermined value therein from an absolute word signal in the hybrid word series Means include the ALU, ED 52, ED 51 and control counter 113 operative during EB 18 in response to received previous and current absolute word signals for forming an output signal indicative of the difference in value therebetween The previous and current different signal is formed at the OP output of ALU and is stored in 40 ET Additionally there is means including ET and-the control counter 113 for retaining the previous and current difference signal This occurs at EB 10.
The encoder also includes means for indicating absolute or bit string word form of hybrid output and includes means, including the switches 104, for indicating a'preselected minimum permitted difference (e g 7) between successively received word signals Such 45 means includes ALU, ED 51, ED 52 and the control counter 113 for comparing the minimum difference indication and the retained previous and current difference signal and for indicating the first being > than or S to the latter.
The encoder also has means for providing absolute form outputs such means including EOP load and shift logic, the BSW and its set and reset logic and the control counter 113 50 operative in response to the: indication for outputting the stored current absolute word and an absolute flag This operation takes place during EB 18-20, 10-17.
The encoder also includes means for providing bit string form outputs and has means including the EOP, CTR and its load and control logic, ED 52, ER, EOP shift logic, MSB set logic and the control counter 113 which are responsive to the > indication for forming a 55 set of ordered signals comprising a binary bit of one value (e g, 1) associated with the number of binary bits of a second value (e g, 0) corresponding to the value of the retained previous and current difference signal It will be seen that the operation is depicted by EB 21-25 The means for providing bit string form outputs also includes means including the clock and the control counter 113 for selectively outputting the set of signals in association 60 with a bit string flag The binary bit of one value in the bit string form output is in a predetermined relation to the outputted absolute word In this regard, the number of bits of displacement between a bit of the one value and an absolute word indicates the value of the one bit.
A preferred embodiment of the encoder has a current store such as register El for storing 65 1 570 343 a currently received absolute word Means including ED 56 control logic stores received absolute words into the current register EI A previous register EO is provided for storing a previously received absolute word Means including the EO control logic and the control counter 113 transfers the current absolute word from the current register to the previous register, forming therein the previous absolute word This is accomplished at EB 20 5 A further preferred embodiment of the encoder provides hybrid form output in a series of words The means for forming a set of ordered signals includes counter means CTR.
CTR has output Co for indicating completion of counting A bit string word forming register EOP is provided and means including CTR load and control logic and ED 52 is 1 o operative during EB 21-24 in response to the > indication for enabling the counter means to 10 count through a sequence of states corresponding in number to the retained current and previous difference signal contained in ET.
The indication at output Co from CTR indicates completion of the lastmentioned counting Addit onally included is means including EOP and its shift logic and control counter 113 operative during EB 21-25 for shifting the content of the bit string IS forming register one bit position in the direction of the most significant bit thereof for each of the last-mentioned counter means states Additionally included is means including the MSB flip flop and its set logic and the control counter 113 which is operative during EB 25 in response to the last-mentioned completion indication at Co for inserting a binary bit signal of predetermined value (e g, 1) at the least significant end of the content of the bit storing 20 register EO By this means, occurrence is entered in the hybrid form word output The means for outputting additionally comprises means including the P 9 logic and the control counter 113 operative during EB 17 for selectively outputting the content of the bit string word forming register by forming a signal at the P 9 output, indicating that the word in EOP is now ready for output 25 An additional preferred embodiment of the encoder, according to the invention, is a bit string forming imeans which has means for entering a first occurrence in a new bit string worj under formation Included in the last-mentioned means is means (ER) for storing a signal representing the number of binary bits remaining to be filled in the bit string word forming register EOP: Also included is combining means including the ALU, ED 51, ED 52 30 and the control counter 113 operative during EB 11 for forming a signal representing the difference between the values of the remaining number of binary bits to be filled signal and the previous and current difference signal Additionally included is means including the ALL’ ED 51 ED 52 and gates 108 and 110, and the control counter 113 operative during EB 11 for comparing the values of the previous and current difference signal and the 35 remaining binary bits to be filled signal for indicating that the value of the first signal is 3 (GE) than or < (L) than the latter signal Additionally included is means including ET, ED 57 and the control counter 113 operative during EB 12 in response to the < than indication at L for retaining the difference signal in ET from the combining means as the number of bits needed in the next bit string word to enter a current absolute word 40 Means including the CTR load and control logic and ED 52 is operative during EB 11, 22-24 in response to the 3 than indication at GE for enabling the counter means to count through a sequence of states corresponding in number to the retained number of bits needed in the next bit string word signal contained in ET It should be noted that the foregoing operation occurs when, during EB 11, the retained number of bits needed in the 45 next bit string word contained in ER is 3 than the previous and current difference signal contained in ET Also included is the EOP shift control logic, the control counter 113 for shiftina the content of the bit string forming register EOP one bit position in the direction of the most significant bit contained therein for each of the last mentioned counter means states Means including MSB and its set logic and the control counter 113 are operative 50 during EB 25 responsive to the completion signal at Co for inserting bit signal of predetermined value (e g 1) at the least significant end of the content of the bit string register EOP.
A further preferred embodiment of the encoder has a bit string forming means which includes means for filling out the bits of a bit string word being formed when no further 55 occurrences can be entered therein Included therein is means ER for storing a signalrepresenting the number of binary bits remaining to be filled in the bit string word being formed Combining means including ALU, ED 51, ED 52 and the control counter 113 is operative during EB 11 for forming a signal representing the differences between the value of the remaining number of binary bits to be filled signal, contained in ER, and the previous 60 and current difference signal, contained in ET Additionally, there is means including ALU, ED 51, ED 52 gates 108 and 110 and the control counter 113 operative during EB 11 for comparing the value of the previous and current difference signal and the remaining binary bits to be filled signal for indicating that the first is 2 than or < than the latter.
Means including the CTR load and control logic EDS and ED 52 is operative during 65 19) 1 570 343 eb 12-14 in response to the < than indication for enabling the counter means CTR to count through a sequence of states corresponding in number to that indicated by the value of the stored remaining binary bits to be filled signal contained in ER Also included is means including the EOP shift control logic, the control counter 113 operative during EB 13-14 for shifting the content of the bit string forming register EOP one bit position in the direction of 5 the most significant bit thereof for each of the last mentioned counter means states.
According to a preferred embodiment of the encoder, clipping means is provided.
Included therein is means including ETL and EBL for storing an upper limit value and a lower limit value Means including ALU, ED 51, ED 52 and gates 108 and 110 are operative during EB 2-4 for comparing a current absolute word with the upper and lower limit values 10 and for indicating if it is out of the bounds defined by the limit values.
According to a further preferred embodiment of the encoder, an interval adjusting means is provided along with the clipping means Included is means EIR for storing an interval value Means including the ALU, ED 51, ED 52, ED 55, gates 108 and 110, and control counter 113 is operative during EB 5 in response to the indication that the current absolute 15 word is out of bounds for incrementally changing the stored upper and lower limit values in EBL and ETL by the stored interval value in EIR In the specific example shown, the incremental changing is a decrementing action Also included is means for enabling the comparing means to repeat the comparing, using the incrementally changed upper and lower limit values and current absolute word 20 DECODE I MODULE The purpose of the DECODE I MODULE is to convert to absolute word form a series of received occurrences in a hybrid word The occurrences are of decreasing value and are coded in hybrid form Thus, the DECODE I MODULE converts information in the 25 opposite direction from that of the ENCODE MODULE The hybrid coded form comprises a series of binary coded words, including at least one absolute coded word followed by one or more bit string words and/or absolute words Each absolute word represents an occurrence directly in coded form Each bit string word represents an occurrence by the number of bits of displacement of a bit of a predetermined value from 30 either an absolute word or another one of such bits of predetermined value in the series of hybrid words Additionally, each hybrid word has a flag indicating whether it is an absolute or bit string type of word.
The DECODE I MODULE operates in response to a call by a calling module The possible calling modules for the DECODE I MODULE are: PIPE, SEED, REVOLVE, 35 BRIGHTNESS, OUTPUT MODULES and the DPM INTERFACE MODULE In general terms, the DECODE I MODULE decodes a hybrid word by reading it from the MEMORY MODULE and if the flag bit indicates the word is an absolute word, the DECODE I MODULE outputs the word, passing it directly to the calling module The DECODE I MODULE saves the absolute word which has been outputted and then reads 40 another hybrid word from the MEMORY MODULE If the flag bit indicates that the new word is a bit string word, then the bit string word is stored in a shift register and shifted until a -1 " bit (bit of predetermined value) is shifted out of the register With every shift, the previous absolute word value is counted down and each time a " 1 " bit is shifted out of the shift register, the state of the counter is outputted as the absolute word 45 B Components The DECODE I MODULE includes counters MAR 1, MLN 1, DO 1, and BCTR 1.
Counter MA Rl is a 256 state counter of type SN 74161 in the above TTL book Counter MLN 1 is formed of an SN 74191 type counter disclosed at page 417 of the above TTL book 50 and counts up responsive to each true signal applied at the Ct input The MLN 1 counter is also set to a state corresponding to the input signals applied at its upper side responsive to a true signal at the L or load input Internal gating (not shown) forms a true signal at Mo when the MLN 1 counter is at state 0 Counter BCTR is an 8 state counter Counter DO 1 is an 8 bit 128 state counter Both counters BCTR and DO 1 are formed of an SN 74191 type 55 counter disclosed at page 427 of the above TTL book These counters operate as follows: a true signal at the CLR input resets the counters to state 0, a true signal at the L input causes the counters to be set to a state represented by the information input signals applied at its upper input Each true signal at the CT input causes the counter to count up one state.
Counter BCTR has logic (not shown) for forming a true output signal at Bo and Bo when 60 the counter is at state 0 and not at state 0, respectively.
Also included in the DECODE I MODULE is an INRI register Contained therein is a shift register 202 The shift register 202 is a 7 binary bit storage register formed of the type SN 74199 disclosed at page 456 of the above TTL book.
The DECODE I MODULE also includes flip flops Pl through P 5, forming a control 65 2 () 1 570 343 counter 213, and flip flops D 1 FST, EOF 1, D 1 SW, D 1 END, M 591, 51 FF and DCE Each of these flip flops is formed of type SN 7474 disclosed herein in section I F, Conventions Used in the Figures.
One-shot multi-vibrators D 1 GO, D 1 MEND are also provided Each of these one-shot multi-vibrators is characterized whereby a true signal applied at its input causes the 5 indicated output to receive a true signal for a time period equal in length to the time period between the beginning of one clock pulse and the beginning of the next clock pulse at CLK.
The DECODE I MODULE includes a source of equally spaced recurring clock pulses 240.
The DECODE I MODULE also includes the necessary logic to control the various registers, flip flops and counters as indicated by logical equations using the notation 10 indicated hereinabove with respect to the ENCODE MODULE In addition, specific AND gates 216, 218, 220, 222 are shown and OR gates 224, 226, 228, 230, 234 and 235 are shown.
The AND gates 218, 220, and 222 are actually indicated schematically and comprise eight individual AND gates (not shown) for gating eight bits of information through to the corresponding outputs from the indicated source of information along the heavy line inputs 15 The second input to each of the eight AND gates within AND gates 218, 220 and 222 is connected to the indicated control logic indicated by logical equations The output of the AND gates within each of the AND gates 218, 220 and 222 are OR'd together by the OR gate 226 and provided as an eight binary bit information input to the MLN 1 counter.
The rest of the AND and OR gates are also conventional gates well known in the 20 computer art and need no further explanation other than that provided in the following detailed description.
The output of AND gate 216 is indicated by the symbol CLK corresponding to clock The output of an inverter 232 is indicated by the symbol CLK corresponding to the logical inverse of the clock signal CLK similar to the ENCODE MODULE 25 The required input and output control lines to the DECODE I MODULE are indicated along the right hand side of Figure 9; also indicated along the right hand side of Figure 9 are the information input and output circuits using the system of notation described hereinabove.
Referring to the right hand side of the DECODE I MODULE figure, the information 30 inputs to the DECODE I MODULE are shown in heavy lines and are LN 1 from IPRF, MLN 3 from the ENCODE MODULE and ORT 2 from the OUTPUT MODULE The output from the DECODE I MODULE is from the DO 1 counter (heavy line), the EOF 1 output of the EOF 1 flip flop, the D 1 MEND output of the one-shot multivibrator D 1 MEND, and the output of a gate represented by the logical equation P 2 D 1 SW The 35 information output from the DO 1 counter is the absolute words that have been decoded from hybrid form The signal at D 1 MEND indicates the completion of each resultant absolute word in the DO 1 counter, thereby indicating to the calling module that it can read the absolute word from DO 1 A true signal at the EOF 1 output indicates that the number of hybrid words, and hence the length of the memory area, indicated by the words stored in 40 the MLN 1 counter, have been converted and therefore the hybrid occurrence vector has been completely decoded.
C Detailed Description
Table 13 gives the symbols for the important counters, registers and flip flops in the 45 DECODE I MODULE of Figures 9 and 10 and indicates the length thereof and the primary output of the DECODE I MODULE Table 11 shows the primary inputs Figure 11 is a flow chart indicating the sequence of operation of the DECODE I MODULE using similar notation to that described hereinabove with respect to the ENCODE MODULE.
Reference to the DECODE I MODULE flow diagram should be made in reading the 50 following description to aid in a complete understanding of the present invention.
Similar to the ENCODE MODULE, the OR gate 234 is responsive to an initial signal applied at MINIT by the MINI COMPUTER to apply a true signal to the resetting input of each of the flip flops P 1-P 5, resetting them to 0 Also, OR gate 235 responds to the MINIT signal for initially resetting the DCE flip flop to 0 55 The DECODE I MODULE, as mentioned above, is called by any one of the following modules: PIPE, SEED, REVOLVE, BRIGHTNESS, OUTPUT and INTERFACE The MINI COMPUTER, as later described, through the DPM INTERFACE MODULE or one of the other modules stores into one area of the MEMORY MODULE a hybrid coded occurrence vector This hybrid coded occurrence vector is to be converted to absolute 60 coded occurrence words using the DECODE I MODULE (and/or DECODE II MODULE) A calling module initializes the DECODE I MODULE by placing the number of words (length) of the hybrid form occurrence vector to be converted into the MLN 1 counter and by setting the D 1 FST flip flop to a 1 state, indicating that the first call to the DECODE I MODULE is occurring 65 1 570 343 The length of the occurrence vector is provided to the DECODE I MODULE from different sources according to the calling module as follows: PIPE MODULE LN 1 from IPRF; SEED MODULE LN 1 from IPRF; REVOLVE MODULE MLN 3 counter from ENCODE MODULE; BRIGHTNESS MODULE LN 1 from IPRF; OUTPUT MODULE LN 1 from IPRF or ORT 2 register in OUTPUT MODULE; CHANGE MODULE 5 LN 1 from IPRF; INTERFACE MODULE LN 1 from IPRF loading MLN 1 is as follows:
a true signal applied by the OUTPUT MODULE at O M 16 or O M 17 causes AND gates 218 and 222 and OR gate 226 to couple the length value from LN 1 of IPRF and ORT 2, respectively, to the information input of the MLN 1 counter The CHANGE MODULE loads the MLN 1 counter and the SEED MODULE calls the DECODE I MODULE To 10 this end, the CHANGE MODULE applies a true signal at the CM 4 output, causing the AND gate 218 and the OR gate 226 to couple the length value from LN 1 of IPRF to the information input of the MLN 1 counter The SEED MODULE applies a true signal at the SM 2 output which causes the AND gate 218 and OR gate 226 to couple the length of occurrence value from LN 1 of IPRF to the information input of the ML Nl counter The 15 REVOLVE MODULE applies a true signal at RM 14 to cause gates 220 and 226 to couple the length of occurrence value from counter MLN 3 of the ENCODE MODULE to the information input of counter MLN 1.
One of the REVOLVE, SEED, OUTPUT, PIPE, BRIGHTNESS, AND DPM INTERFACE MODULES then sets the D 1 FST flip flop to a 1 state via OR gate 228 by 20 applying a true signal, respectively, at the corresponding output P 11, RM 2, SM 4, B 3, 0 M 21 and D 1 I which, as indicated above, indicates that the first call of the DECODE I MODULE is occurring.
Subsequently, the calling module triggers the Dl GO one-shot multivibrator, causing it to apply a control pulse at its Dl GO output Dl GO is triggered by the gate 230 which 25 receives its control pulse from one of outputs P 13, SM 6, RM 4, B 5, and Dl GO.
A true signal at output Dl GO sets the DCE flip flop to a 1 state, causing a true signal at the DCE output which, in turn, enables AND gate 216 to couple clock signals from the clock 240 to the CLK output Similar to the ENCODE MODULE, the inverter 232 forms the logical inverse of the clock formed at CLK at its output at CLK 30 Since all of the flip flops of the control counter 213 are initially reset to zero, true signals are now formed at the outputs P 1, P 2, P 3, P 4 and P 5 and the clock pulse at CLK causes flip flop Pl to be set to a 1 state and D 1 B 1 of the DECODE flow is entered.
During Dl B 1, the state of the D 1 FST flip flop is checked, assuming that this is the first call on the DECODE I MODULE The D 1 FST flip flop is in a 1 state, causing a true signal 35 at the D 1 FST output Additionally, the Pl flip flop is in a 1 state Accordingly, D 1 B 2 of the DECODE I MODULE flow is entered where the true signals at Pl D 1 FST and CLK cause the D l SW flip flop to be reset to a 0 state The clock pulse at CLK in combination with the true signals at the Pl and D 1 FST outputs causes each of the D 1 END, Dl FST and EOF 1 flip flops to be reset to an 0 state and cause the MAR 1 and BCTR 1 counters to be reset to an 0 40 state Additionally, the clock at CLK in coincidence with the true signal at output Pl causes flip flop P 2 to be set to a 1 state and flip flop Pl is reset to an 0 state.
The D 1 FST, EOF 1, D 1 SW and D 1 END flip flops have been reset at this time for the following reasons The D 1 FST flip flop is reset at this time to indicate that the resetting operation during D 1 B 2 has been completed This is the only function of the D 1 FST flip 45 flop EOF 1 is reset at this time to indicate that the hybrid words in the occurrence vector have not been completely converted The D 1 SW flip flop is used to indicate within the DECODE I MODULE that a MEMORY MODULE read is necessary The 0 state of the D 1 SW flip flop indicates that a read from MEMORY MODULE is necessary to obtain a hybrid word This will subsequently take place during D 1 B 5 A 1 state of the D 1 SW flip 50 flop is used to indicate that a read is unnecessary and, as will be explained subsequently, D 1 B 5 is skipped when D 1 SW is in a 1 state The D 1 END flip flop is an internal flip flop and, when set into a 1 state, indicates to the DECODE I MODULE that after conversion of a hybrid coded occurrence vector the last absolute word has been outputted or passed to the calling module To be explained in more detail, when the D 1 END flip flop is set to a 1 55 state, any subsequent call on the DECODE I MODULE by the calling module will force the DECODE I MODULE to form an end of file indication by setting the EOF 1 flip flop to a 1 state.
Following D 1 B 2, D 1 B 3 is entered During D 1 B 3, the P 2 flip flop is in a 1 state and the D 1 END flip flop is checked If during D 1 B 3 the D 1 END flip flop is in a 1 state, which, as 60 discussed above, occurs when the calling module provides the last word of a hybrid occurrence vector, Dl B 19 of the DECODE I MODULE flow is entered.
The action of the clock suspension logic should now be noted The true signals at P 2, D 1 END and CLK reset the DO 1 counter to 0 and cause the clock suspension logic 222 to form a true signal at the OR gate 235 causing it to reset the DCE flip flop to 0 and trigger 65 1 570 343 the one-shot DIMEND Resetting of the DCE flip flop to an 0 state removes the true signal at output DCE and causes the AND gate 216 to remove the clock signals at CLK, thereby causing the DECODE I MODULE operation to EXIT and await the next call on the DECODE I MODULE The one-shot D 1 MEND then forms a true signal at output S D 1 MEND which causes OR gate 234 to reset flip flops P 1-P 5 to 0 The subsequent 5 operation caused by the D 1 END flip flop being in a 1 state will be further described hereinafter.
The above action of the clock suspension logic 222 is important and should be kept in mind as a similar action is enabled by the clock suspension logic when any one of the other logic conditions indicated for the clock suspension logic 222 becomes true 10 Assume that during D 1 B 3 the last word of a hybrid occurrence vector has not been provided, and the D 1 END flip flop is in a 0 state, causing a true signal at the D 1 MEND output DIB 4 is entered where the state of the D 1 SW flip flop is checked It will be recalled that the D 1 SW flip flop in a 1 state indicates that the MEMORY MODULE read operation is to he skipped, whereas if in an 0 state, causes a MEMORY MODULE read Assume that 15 the D ISW flip flop is in an 0 state D 1 B 5 is entered where the memory read actually takes place.
An input to the DECODE I MODULE is the SM 10 output of the SEED MODULE To be explained in more detail, the SEED MODULE uses the DECODE I MODULE when computing the number of lines to be skipped in an iso-entropicgram However, the SEED 20 MODULE when computing the lines to be skipped, does not require the length value in counter MLN 1 to be decremented Accordingly, the SEED MODULE normally forms a true signal at output SM 10 but removes the true signal when computing the number of lines to be skipped, thereby inhibiting counter MLN 1 from being decremented.
However, for the present description, assume that a true signal is formed at SM 10 True 25 signals are also formed at P 2 and D 1 SW Therefore the MLN 1 counter receives a true signal at its Ct input, causing MLN 1 to be counted down one state reflecting the fact that one word of the hybrid occurrence vector is being read from the MEMORY MODULE The logic P 2 Dl SW CLK being true causes a true signal at the Ct input of MA Rl, causing MA Rl to be counted up one state, reflecting the fact that the next word of the hybrid occurrence 30 vector is to be addressed in the MEMORY MODULE The true signals at P 2 and D 15 W cause a true signal to be formed at the DM 11 output of the DECODE I MODULE, thereby signalling the MEMORY MODULE, causing it to read out the content of the proper memory area specified by the SWITCH MATRIX at the memory location specified in the MA Rl counter prior to its being counted up 35 The control signal at P 2 enables the 8 bit word read-out of the MEMORY MODULE to be stored into the INR 1 register The true signal at P 2 causes the most isngificant bit ( 8 bit) of the word read from the memory to be stored in the MSB 1 flip flop The true signal at P 2 also goes to the S/L input circuit for the shift register 202 causing the remaining 7 bits of the word from the MEMORY MODULE to be loaded into the register 202 when the clock 40 signal is applied from logic P 2 D 1 SW CLK Accordingly, at the end of D 1 B 5 of the DECODE I MODULE flow a hybrid word has been read from the MEMORY MODULE from the appropriate memory area and has been stored in the INR 1 register and the MLN 1 counter has been decreased by one so that the length of occurrence vector contained therein indicates the remaining words to be read from the MEMORY MODULE 45 Assume now that the word stored in the INR 1 register is an absolute hybrid word It will be recalled that the first word of every hybrid occurrence vector string will always be an absolute word When the word stored in INR 1 is an absolute word, the flag bit, the most significant bit of the hybrid word, is stored in the MSB 1 flip flop and causes the MSB 1 flip flop to be in a 1 state With the MSB 1 flip flop in a 1 state, true signals are formed at the 50 MSB 1 and P 2 outputs Accordingly, the P 5 flip flop is set to a 1 state and D 1 B 8 is entered.
A true signal is formed at the P 5 output and the following pulse at CLK causes a true signal at the L input of the DO 1 counter, causing the 7 bits in the shift register 202 of the INR 1 register to be loaded into the DO 1 counter The true signal at P 5 in coincidence with the pulse at CLK enables the clock suspension logic 222 to reset the DCE flip flop to an 0 55 state, thereby disabling the clock at CLK out of the gate 216 and resetting counter 213 An EXIT is taken to await the next call The next call is initiated by a control signal, as described above at one of the inputs to OR gate 230.
If, during the true signal at P 2 the word in the INR 1 register read from memory is a bit string word, the MSB 1 flip flop is in an 0 state and true signals are formed at the MSB 1 and 60 Dl SW outputs and the P 3 flip flop is set to a 1 state, thereby causing DIB 11 of the DECODE I MODULE flow to be entered.
At the beginning of processing of each bit string word of a hybrid occurrence vector, the BCTR 1 counter is in an 0 state having been set there at D 1 B 2 Therefore, during the first entry into D 1 B 11 of the DECODE I MODULE flow, the BCTR 1 counter is in an 0 state 65 1 570 343 Accordingly, a true signal is formed at the Bo output of the BCTR 1 counter so indicating.
The true signal at Bo in combination with the true signal at P 3 causes the P 4 flip flop to be set to a 1 state and D 1 B 13 is entered.
During D 1 813, the BCTR 1 counter is loaded with a signal representing the maximum number of bits in a hybrid word to be processed To this end, true signals are now formed at 5 the P 4 and Bo outputs and the following pulse at CLK causes the L input of the BCTR 1 counter to be energized and the value 7, represented by the setting of the switches 236, is loaded into the BCTR 1 counter, and D 1 B 14 is entered.
During D 1 B 14 of the DECODE I MODULE flow a true signal is formed at the P 4 output Accordingly, the shift register 202 is repeatedly shifted one bit to the right until a 10 one bit indicating an occurrence is shifted out of register 202 into the 51 FF flip flop Each bit shifted out of the least significant end of the register 202 is stored in the sign flip flop 51 FF During D 1 B 15 of the flow a true signal is formed at the P 4 output and the pulse at CLK causes the Ct input of the BCTR 1 counter to be energized and count the counter down one state The same signals cause the CT input of the DO 1 counter to be energized and the 15 counter DO 1 to count down one state For each right bit shift of the register 202, the number of bits left to be processed in the INR 1 register identified by the state of the BCTR 1 counter is counted down one and the absolute word value indicated by the DO 1 counter is counted down one state This operation continues until a 1 bit is shifted out of the shift register 202 into the sign flip flop 51 FF thereby causing a true signal at the 51 FF output 20 The state of the DO 1 counter at this time is an absolute word representing the actual value of the occurrence represented by the 1 bit shifted out of register 202 into the 51 FF flip flop and accordingly, the state of the DO 1 counter is to be outputted to the calling module.
To this end, signals are formed at the P 4 and 51 FF outputs and the following signal at CLK causes the DCE flip flop to be reset to an 0 state and fires the D 1 MEND one-shot 25 causing a true signal at the D 1 MEND output signalling the calling module that an absolute word is completed and contained in the DO 1 counter The D 1 MEND signal resets the control counter 213 to 0 The formation of the signal at D 1 MEND indicates completion of an absolute word and is referred to herein as outputting the absolute word.
Several important special conditions should be noted If during D 1 B 15 and the 1 state of 30 the P 4 flip flop, the content of shift register 202 is not 0, it means that there is a remaining 1 bit (representing an occurrence) yet to be converted to absolute form in a bit string word.
Accordingly, a true signal is formed by register 202 at IO causing the Dl SW flip flop to be set to a 1 state at the following pulse at CLK The 1 state of the Dl SW flip flop is used during the following entry into D 1 B 4 of the flow to bypass the reading of another word 35 from the MEMORY MODULE The reason for this action is that with the D 1 SW flip flop in a 1 state, a new hybrid word will not be read from the MEMORY MODULE following D 1 B 14, as there is still at least a portion of a bit string word remaining in the shift register 202 to be converted to absolute form.
Referring to D 1 B 17 of the flow, whenever the bit string word contained in register 202 of 40 the INR 1 register goes to zero by virtue of the fact that all of the 1 bit (or occurrence) of the bit string word has been shifted out thereof, a control signal is formed at the IO output of the shift register 202 When this occurs another hybrid word must be read from the MEMORY MODULE during Dl B 5 A true signal is formed at the outputs P 4 and 10 causing the D 1 SW flip flop to be reset to a 1 state at the next pulse at CLK The 0 state of 45 the D 1 SW flip flop, during the following entry into D 1 B 4, causes D 1 B 5 of the flow to be next entered where a new hybrid word is read from MEMORY MODULE into the DECODE I MODULE for conversion When the last word of a hybrid occurrence vector has been read from the MEMORY MODULE, the length of occurrence vector value contained in the MLN 1 counter will have been counted down to 0, and a control signal is 50 formed at the Mo output of the MLN 1 counter A true signal at Mo and a true signal at the P 5, the P 4 and 10 outputs causes the D 1 END flip flop to be set to a 1 state at the next pulse at CLK thereby indicating that the last absolute word has been outputted to the calling module With the D 1 END flip flop in a 1 state, the following call on the DECODE I MODULE flow will cause the EOF 1 flip flop to be set to a 1 state responsive to true signals 55 at the P 2 and D 1 END outputs at the occurrence of the pulse at CLK.
One further special situation with respect to the DECODE I MODULE should be noted.
If, during the 1 state of the P 3 flip flop, the BCTR 1 counter is not in an 0 state, then D 1 B 12 and Dl B 11 of the flow are utilized to insure that the proper alignment is made from one bit string word to another This is necessary when the last 1 bit of a bit string word has been 60 converted to absolute word form and outputted, and leading 0 bits remain in the bit string word under conversion in the shift register 202 These leading 0 bits must be taken into account in forming the next absolute work for output.
Referring to D 1 B 11 and D 1 B 12 of the flow and the corresponding action, a true signal at the P 3 output in coincidence with a true signal at the Bo output causes the BCTR 1 counter 65 1 570 343 as well as the DO 1 counter, to be counted down one state responsive to each pulse at CLK.
As a result, the absolute word being formed in DO 1 is adjusted downward by the number of leading O 's remaining in shift register 202 which are indicated by the state of BCTR 1.
Finally, when the BCTR 1 counter reaches an 0 state, a control signal is formed at the Bo output and the true signal is removed at the Bo output terminating the counting of the BCTR 1 and DO 1 counters and causing D 1 B 13 of the flow to be entered as explained above.
D Example of Operation Consider now an example of the operation of the DECODE I MODULE Assume that four words, making up a hybrid occurrence vector, are contained in the memory area 1 of the MEMORY MODULE and are to be converted from hybrid to absolute word form.
Example
Assume the following is in the memory area 1 of the MEMORY MODULE:
1 1 1 1 11 O 1 125) 0 O 1 O O O 1 O ( 123, 1190 O O O 1 O 1 O ( 116, 114) 1 1 1 O O 1 O ( 100) The physical length in words is 4.
Therefore it is the calling program's responsibility to load MLN 1 <-4 and set the initialize flip flop D 1 FST =0 to 1.
First call MLN sequence of control B B& ' 2 END =0 SW =0 re, MAR BCTR ini 3 4 5 read memory into INR do ( 125) 1) =O 0) + m( po PO 3) 4) de 6 O 7; 7 MSB(INR DIB 9 AOI form EXIT output Dot 15 W =0 these flops; itialize registers read; e result; emory address next )sition; crease number words input becomes output; assure a on zero; Dol =123 EOF Second initial conditions: is not clocked DB 2) =BCTR Rl( 1: Bll 13 814 00010001 51 FF =1 1, 3-D 87, Bll, 813-D 816, 14, 17 1; increase pointer; decrease length register; this counter monitors how much register remains be processed; 57 () 343 6) 7) Dol( 124) DISW =1 SIFF =O Dl 14 00) BCT("'R I =00000001 5) ("R Il( 123) 11317 INRI =)00000000 -IALT EOFI =O reduce bits processed & previous D)ISW indicate no ncessary call; shift because from decrement remaining, just assert GO 83-D 84, 14-DIB 16, 84-DIB 14-Dl BIS same as before IN R BCTRI( 122) 0000001 121) 120) =Dol( BCTRI> T H I S A E Occurrence vectors -0, 5 8, 10, 15 l 1, 11 14 l 2 l 3, 6 l 4, 7, 13 l 9 l 12 l TABLE 2
0 1 2 3 4 5 6 7 POSSIBLE OCCURRENCE VALUES 1 1 1 0 1 0 1 0 OCCURRENCE VECTOR BIT,STRING FORM 0 1 2 4 6 OCCURRENCE VECTOR ABSOLUTE FORM clock input ( 1) ( 2) 1 570 343 1 570 343 TABLE 3
Example of hybrid encoding TYPE BIT 0 bit string form I absolute form 1 1 1 ( O O O 121 122 0 1 O 114 > 115 ( O O 1 1 1 1 1 O 1 89 88 90 BRIGHTNESS MODULE 0 1 1 O 123 124 1 O 116 117 0 O 0 1 0 O 91 -125 Absolute -Binary string occurrences 123, 119 -Binary string occurrences 116, 114 -100 Absolute 93 Absolute -Binary string occurrences 90, 88, 87 TABLE 4
B CHANGE MODULE DPM INTERFACE MODULE ENCODE MODULE CM no EM DECODE I MODULE DECODE II MODULE DELTA MODULE OUTPUT MODULE PIPE MODULE REVOLVE MODULE SEED MODULE special mnemonic used DIM D 2 M DM OM Pl RM SM SWITCH MATRIX Word 1 1 0 0 118 0 O 1 1 1 1 0 O 119 1 119 W 1 etc.
S 1 570 343 TABLE 5
MODULE INPUT/OUTPUTS ENCODE MODULE Inlp Uts ETL ( 8 bits) EBL ( 8 bits) EIR ( 8 bits) EHW ( 8 bits) EFIRST flip flop ELAST flip flop top clipping limit loaded from TL of IPRF by OUTPUT MODULE bottom clipping limit loaded from BL of IPRF by OUTPUT MODULE interval value loaded from IR of IPRF by OUTPUT MODULE iso-entropicgram width loaded from HW of IPRF by SEED, CHANGE or OUTPUT MODULES set to 1 to initialize set to 1 to force write to final hybrid coded word Outputs EOP ( 1 flag bit + 7 bits) MLN 3 ( 8 bits) ENOC ( 8 bits) hybrid coded word being written into MEMORY MODULE (flag bit = 0 identifies bit string word; flag bit = 1 identifies absolute coded word) to DECODE i and II MODULES to indicate number of hybrid coded word written into MEMORY MODULE to SEED MODULE to identify number of occurrence values encoded into hybrid coded form and stored in MEMORY MODULE DECODE I MODULE Inputs MLN 1 ( 8 bits) physical length of input in words stored in MEMORY MODULE area being read Loaded by calling module from LN 1 or LN 2 of IPRF or MLN 3 of ENCODE MODULE or ORT 2 of OUTPUT MODULE D 1 FST calling module (via signals applied to gate 228 sets D 1 FST to a 1 state on first call to DECODE I MODULE for conversion of one hybrid word to indicate the first call Hybrid coaded word in one of MEMORY MODULE areas Outputs D 01 ( 8 bits) EOF 1 ( 1 bit) counter which indicates absolute coded word value of occurrence in question flip flop which indicates when the number of words specified by MLN 1 has been decoded by DECODE I MODULE 1 570 343 DECODE II MODULE INPUTS/OUTPUTS are similar to DECODE I MODULE DELTA MODULE Inputs DELI ( 8 bits) DELFST ( 1 bit) number of lines to be revolved loaded by calling module from TI of SEED MODULE or CLINE of CHANGE MODULE or D 56 of OUTPUT MODULE initialization flip flop is set when new process is desired by calling module Outputs DELO ( 8 bits) DELEND ( 1 bit) contains component power of 2 for value in DELI and is output to calling module flip flop which in 1 state indicates that value stored in DELI has been completely transformed into its component power of 2 SEED MODULE Inputs SMHW ( 8 bits) SMLI ( 8 bits) iso-entropicgram width loaded from HW of IPRF line # of seed line loaded from line # of IPRF or from CLINE of CHANGE MODULE MEMORY MODULE current seed (LN 1 words) LN 1 ( 8 bits) Outputs SLINE ( 8 bits) SLN ( 8 bits) current seed in hybrid code is ( 1) stored in MEMORY MODULE area 1 if MINI COMPUTER via user program calls SEED MODULE, or ( 2) stored in MEMORY MODULE area N (n = 1, 2, 3) if CHANGE MODULE calls SEED MODULE the number of words or physical length of the current seed received from MLN 1 or MLN 2 of the DECODE I and II MODULES line number of new seed line physical length in words of the new seed MEMORY module new seed (SLN words) OAR ( 2 bits) the new seed contained in MEMORY MODULE areas designated by OAR contains the number of the MEMORY MODULE area which contains the new seed 1 570 343 ONOC ( 8 bits) contains the number of actual occurrence values in the new seed REVOLVE MODULE INPUTS/OUTPUTS for other modules CHANGE MODULE Inputs change line value (LN 1-words long) seed line value (LN 2-words long) CLINE ( 8 bits) CLN ( 8 bits) MLN 1 of DECIDE I & II ( 8 bits) Outputs Same as that given for seed module OUTPUT MODULE Inputs MLN 2 of DECODE II MODULE, MLN 1 of DECODE I MODULE ( 8 bits) ORT 3 ( 8 bits) OHW ( 8 bits) OLINE ( 8 bits) DELOP ( 1 bit) ETL of ENCODE MODULE EBL of ENCODE MODULE EIR of ENCODE MODULE line value of seed line value of reference vector Outputs OAR MEMORY MODULE area designated by OAR OLN line value of the change vector from MEMORY MODULE area 1 line value of the seed which is to be changed, from MEMORY MODULE area line # of seed from LINE # of IPRF physical length of line value for seed from LN 2 of IPRF physical length of line value for change vector from LN 1 of IPRF length of seed line value from LN 1 of IPRF length of line value of the reference line from LN 2 of IPRF iso-entropicgram width for seed from HW of IPRF line number of line value of seed from LINE # of IPRF set DELOP from DPM INTERFACE MODULE top limit from TL of IPRF bottom limit from BL of IPRF interval value from IR of IPRF from MEMORY MODULE area from MEMORY MODULE AREA number of MEMORY MODULE area containing output output length of output in MEMORY MODULE area designated byg OAR PIPE MODULE 1 570 343 Inputs PW ( 8 bits) LNRQR ( 8 bits) MLN 1 of DECODE I MODULE ( 8 bits) Line value of line 0 (LN 1-words) MLN 2 of DECODE II MODULE ( 8 bits) Delim (LN 2-words) PFIRST ( 1 bit) PLAST ( 1 bit) pipe width loaded from PW of IPRF on first call; contains width of pipe length of request (in events) loaded from LNRQ of IPRF on first call length of line value of seed loaded from LN 1 of IPRF line value of seed located in MEMORY MODULE area 1 length of delimiter event occurrence vector loaded from LN 2 of IPRF and PSAU delimiter event occurrence value located in MEMORY MODULE area 2 initialization flip flop set prior to first call only end flip flop, set prior to last call only Intermediate Output P Mn (n= 1,2) vi vii contains values for each occurrence processed in each event occurrence vector the occurrence value after bias 1 subtracted the “hit count”, i e number of times this occurrence number has been computed during piping process the last value value in area is set to -1 Final Output MEMORY MODULE area 3 contains the final output.
There are the following two values for each entry in the request:
vi vii the best candidate occurrence value to be the beginning occurrence of the request in this entry hit count; if sign bit is set ( -1) this indicates an exact hit The last value in the area is set to -1.
BRIGHTNESS MODULE Inpllts LNRQR ( 8 bits) MLN 1 of DECODE I MODULELine value of seed MLN 2 of DECODE II MODULE delim length of the request (in events) from LNRQ of IPRF length of line value of current event occurrence vector from LN 1 of IPRF from MEMORY MODULE area 1 length of delimiter event occurrence vector from LN 2 of IPRF delimiter event occurrence vector in MEMORY MODULE area 2 1 570 343 PM-data the beginning event occurrence values of the request in certain entries on this layer which are to be checked and stored in P/B MEMORY area 1 BFIRST flip flop set by DPM INTERFACE MODULE to 5 initialize prior to first call BLAST set by DPM INTERFACE MODULE prior to last call for this request only.
Final Outputs 10 MEMORY MODULE area 3 contains the following sets of four values for the best entry in layer 0:
1 beginning delimiter of entry 15 2 # of hits N 3 dmin 4 d,,
Claims (1)
WHAT WE CLAIM IS: 20
1 An encoder for converting to hybrid form a received series of absolute words in a decreasing value order comprising means arranged in operation to a) respond to received previous and current absolute words for forming an output signal indicative of the difference therebetween; b) indicate absolute or bit string form of hybrid output comprising means arranged in 25 operation to 1) indicate a preselected minimum difference between the values represented by successively received absolute words for absolute form of output, 2) compare the minimum difference indication and the previous and current difference signal and for indicating the value of the first being greater than, or less than or equal to the 30 latter:
c) provide absolute form outputs comprising 1) means operative in response to said less than or equal to indication for outputting the current absolute word and an absolute flag; and d) provide bit string form outputs comprising 35 1) means responsive to said greater than indication and arranged in operation to form a set of ordered signals comprising a binary bit of one value in association with the number of binary bits of a second value corresponding to the value of said previous and current difference signal, and 2) means arranged in operation to selectively output said set of signals in association 40 with a bit string flag and in a predetermined relation to an outputted absolute word.
2 An encoder for converting to hybrid form a received series of absolute coded words in decreasing value order comprising:
a) a current register arranged in operation to store a currently received absolute word; b) means arranged in operation to store a received absolute word in said current 45 register; c) a previous register arranged in operation to store a word received prior to the word in said current register; d) means arranged in operation to transfer a word from said current register to said previous register; 50 e) means responsive to the stored previous and current absolute words and arranged in operation to form an output signal indicative of the difference in value therebetween; f) means arranged in operation to retain the previous and current difference signal; g) means arranged in operation to indicate absolute or bit string form of hybrid output comprising 55 1) means arranged in operation to indicate a preselected minimum difference in value between received absolute words for absolute form of output, 2) means arranged in operation to compare the minimum difference indication and the retained previous and current difference signal and for indicating the value of the first being greater than, or less than or equal to, the latter; 60 h) means arranged in operation to provide absolute form outputs comprising 1) means arranged in operation to respond to said greater than indication for outputting a signal representing the stored current absolute word and an absolute flag; and i) means arranged in operation to provide bit string form outputs comprising 1) means arranged in operation to respond to said less than or equal to indication for 65 1 570 343 forming a set of ordered signals comprising a binary bit of one value in association with binary bits of a second value the number of which corresponds to the value of said retained previous and current difference signal, and 2) means arranged in operation to selectively output a signal representing said set of ordered signals in association with a bit string flag and in a predetermined relation to an outputted absolute word.
3 An encoder as claimed in claim 1, wherein the hybrid form comprises a series of words and said means arranged in operation to form a set of ordered signals comprises:
a) counter means; b) a bit string word forming register; 10 c) means arranged in operation to respond to said indication to enable said counter means to count through a sequence of states corresponding in number to the retained current and previous difference signal; d) means arranged in operation to indicate completion of the last mentioned counting; 15 e) means arranged in operation to shift the content of said bit string forming register one bit position in the direction of the least significant bit thereof for each said last mentioned counter means states; and f) means arranged in operation to respond to the last mentioned completion signal for inserting a bit signal of predetermined value at the most significant end of the bit storing 20 register content and wherein said means for outputting comprises means arranged in operation selectively to output the content of said bit string word forming register.
4 An encoder as claimed in claim 3, comprising means arranged in operation to enter a first occurrence in a new bit string word under formation comprising:
a) means arranged in operation to store a signal representing the number of binary bits 25 remaining to be filled in a bit string word being formed; b) combining means arranged in operation to form a signal representing the difference between the value of the remaining number of binary bits to be filled signal and the previous and current difference signal; c) means arranged in operation to the value of the previous and current difference signal and the remaining binary bits to be filled signal for indicating the first is greater than 30 or equal to, or less than the latter; d) means responsive to said less than indication and arranged in operation to retain the difference signal from the combining means as the number of bits needed in the next bit string word to enter the current absolute word; e) means operative in response to said greater than or equal to indication for enabling 35 said counter means to count through a sequence of states corresponding in number to the retained number of bits needed in the next bit string word signal; f) means arranged in operation to indicate completion of the last mentioned counting; g) means arranged in operation to shift the content of said bit string forming register one bit position in the direction of the least significant bit thereof for each said last 4 mentioned counter means states; and h) means responsive to the last mentioned completion signal for inserting a bit signal of predetermined value at the most significant end of the bit storing register content.
An encoder as claimed in claim 3, comprising means arranged in operation to fill out the bits of a bit string word being formed when no further occurrences can be entered 45 therein, comprising means arranged in operation to a) store a signal representing the number of binary bits remaining to be filled in the bit string word being formed; b) form a signal representing the difference between the value of the remaining number of binary bits to be filled signal and the previous and current difference signal; 50 c) compare the value of the previous and current difference signal and the remaining binary bits to be filled signal for indicating the first is greater than or equal to, or less than the latter; d) enable said counter means in response to said less than indication to count through a sequence of states corresponding in number to the value of the stored remaining binary bits 5 to be filled signal; e) indicate completion of the last mentioned counting; and f) shift the content of said bit string forming register one bit position in the direction of the least significant bit thereof for each said last mentioned counter means states.
6 An encoder as claimed in claim 2, having a clipping means, the clipping means comprising:
a) means arranged in operation to store an upper limit value and a lower limit value; and b) means arranged in operation to compare a current absolute word with said upper and lower limit values and to indicate if the current absolute word is out of the bounds defined 65 1 570 343 by the limit values.
7 An encoder as claimed in claim 6, comprising an interval adjusting means comprising:
a) means arranged in operation to store an interval value; b) means responsive to an indication that the current entry is out of bounds and 5 arranged in operation to change incrementally the stored upper and lower limit value by the value of said stored interval value; and c) means arranged in operation to enable said comparingnve means to repeat the comparing, using the incrementally changed upper and lower limit values and current entry.
8 A decoder for converting hybrid coded signals to absolute coded word signals, the 10 hybrid signals representing a series of occurrence values of decreasing value, the hybrid signals comprising a series of received binary coded word signals including at least one absolute coded word and a bit string word, the bit string word representing an occurrence by the number of bits of displacement of a bit of predetermined value either from another bit of the same predetermined value or from the value represented by an absolute word in 1 the series of hybrid words, a hybrid word comprising a flag signal indicating the type of a) absolute word outputting means comprising means arranged in operation to respond to an absolute word flag signal of a received hybrid word signal to output the received word 20 signal; and 2 b) absolute word signal forming and outputting means comprising means arranged in operation to 1) respond to an absolute word signal and each said bit of predetermined value in a subsequent bit string word signal of a received hybrid signal for forming an absolute word signal indicative of actual value of each said bit of predetermined value, and 25 2) output each said formed absolute word signal.
9 A decoder for converting hybrid coded signals to absolute coded word signals, the hybrid signals representing a series of occurrence values of decreasing value, the hybrid signals comprising a series of received binary coded word signals including at least one absolute coded word and at least one bit string word, the bit string word representing an 30 occurrence by the number of bits of displacement of a bit of predetermined value from an absolute word in the series of hybrid words, a received word comprising a flag signal indicating the type of word, comprising:
a) absolute word outputting means comprising means arranged in operation to respond to an absolute word flag signal of a received word signal for outputting the received word 35 signal; and b) absolute word signal forming and outputting means comprising 1) shift register means arranged in operation to store a received bit string word signal, 2) means arranged in operation to repeatedly enabling the shifting of the content of the shift register means one bit position in the direction of the least significant bit of the bit 40 string word signal, 3) means arranged in operation to provide an indication when a bit signal indicative of said predetermined value arrives at a preselected position with respect to the shift register means.
4) counter means, 45 5) means arranged in operation to respond to a flag signal indicating a received absolute word signal to set said counter means to a state relative to a reference state corresponding to the value of such absolute word signal, 6) means arranged in operation to enable said counter means to count one state towards said reference state for each such shift of said shift register means, and 50 7) means arranged in operation to respond to said indication of a bit to output a signal corresponding to the state of said counter means.
A decoder as claimed in claim 9, wherein the absolute word forming means additionally comprises means arranged in operation to adjust said counter means for bits, not of said predetermined value, which remain in said shift register means after the last bit 55 of predetermined value in a received word comprising:
a) additional counter means; b) means arranged in operation to indicate the maximum number of bits in an absolute word for output; c) means arranged in operation selectively to set said additional counter means to a 60 state relative to a state corresponding to said indication of the maximum number of bits in an absolute word; d) means arranged in operation to enable said additional counter means to count one state relative to the set state thereof towards said reference state for each said shift of said shift register means; 65 1 570 343 e) means arranged in operation to provide an indication of the occurrence of said reference value of said additional counter means; f) means responsive to the flag signal of a received bit string word signal and the lack of the last mentioned indication and arranged in operation further to enable both said counter means and additional counter means to count toward the reference states thereof; and g) means responsive to the last mentioned indication and arranged in operation to terminate further enabling of count of said counter means and additional counter means.
11 An encoder for converting a hybrid form a received series of absolute words in a decreasing value order, substantially as hereinbefore described with reference to, and as 10 shown in, the accompanying drawings.
12 A decoder for converting hybrid coded signals to absolute coded word signals, substantially as hereinbefore described with reference to, and as shown in, the accompanying drawings.
For the Applicant, 15 GRAHAM WATT & CO, Chartered Patent Agents, 3, Gray’s Inn Square, London, WC 1 R 5 AH.
Printed for Her Majesty’s Stationery Office, by Croydon Printing Company Limited, Croydon, Surrey, 1980.
Published by The Patent Office 25 Southampton Buildings London, WC 2 A IA Yfrom which copies may be obtained.
GB5203/78A
1975-12-03
1976-12-01
Information storage and retrieval system
Expired
GB1570343A
(en)
Applications Claiming Priority (1)
Application Number
Priority Date
Filing Date
Title
US05/637,511
US4068298A
(en)
1975-12-03
1975-12-03
Information storage and retrieval system
Publications (1)
Publication Number
Publication Date
GB1570343A
true
GB1570343A
(en)
1980-07-02
Family
ID=24556252
Family Applications (4)
Application Number
Title
Priority Date
Filing Date
GB50068/76A
Expired
GB1570341A
(en)
1975-12-03
1976-12-01
Information storage and retrieval system
GB36755/78A
Expired
GB1570344A
(en)
1975-12-03
1976-12-01
Information storage and retrieval system
GB5203/78A
Expired
GB1570343A
(en)
1975-12-03
1976-12-01
Information storage and retrieval system
GB3806/78A
Expired
GB1570342A
(en)
1975-12-03
1976-12-01
Information storage and retrieval system
Family Applications Before (2)
Application Number
Title
Priority Date
Filing Date
GB50068/76A
Expired
GB1570341A
(en)
1975-12-03
1976-12-01
Information storage and retrieval system
GB36755/78A
Expired
GB1570344A
(en)
1975-12-03
1976-12-01
Information storage and retrieval system
Family Applications After (1)
Application Number
Title
Priority Date
Filing Date
GB3806/78A
Expired
GB1570342A
(en)
1975-12-03
1976-12-01
Information storage and retrieval system
Country Status (5)
Country
Link
US
(1)
US4068298A
(en)
JP
(1)
JPS52151535A
(en)
DE
(1)
DE2654975A1
(en)
FR
(1)
FR2334148A1
(en)
GB
(4)
GB1570341A
(en)
Families Citing this family (69)
* Cited by examiner, † Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
GB1588827A
(en)
*
1978-05-31
1981-04-29
System Dev Corp
Data processor method and means for determining degree of match between two data arrays
US4318184A
(en)
*
1978-09-05
1982-03-02
Millett Ronald P
Information storage and retrieval system and method
US4382277A
(en)
*
1979-05-14
1983-05-03
System Development Corp.
Method and means utilizing multiple processing means for determining degree of match between two data arrays
US4422158A
(en)
*
1980-11-28
1983-12-20
System Development Corporation
Method and means for interrogating a layered data base
US4459678A
(en)
*
1981-05-18
1984-07-10
International Business Machines Corporation
Method and apparatus for processing a file of record information
US4502118A
(en)
*
1981-07-07
1985-02-26
Burroughs Corporation
Concurrent network of reduction processors for executing programs stored as treelike graphs employing variable-free applicative language codes
US4495566A
(en)
*
1981-09-30
1985-01-22
System Development Corporation
Method and means using digital data processing means for locating representations in a stored textual data base
US4700294A
(en)
*
1982-10-15
1987-10-13
Becton Dickinson And Company
Data storage system having means for compressing input data from sets of correlated parameters
JPS61145634A
(en)
*
1984-12-19
1986-07-03
Nec Corp
Symbol string identification device and its control system
US5097408A
(en)
*
1985-01-11
1992-03-17
Wang Laboratories, Inc.
Apparatus for specifying a result relation in a relational database system by selection of rows
US4888690A
(en)
*
1985-01-11
1989-12-19
Wang Laboratories, Inc.
Interactive error handling means in database management
US4817036A
(en)
*
1985-03-15
1989-03-28
Brigham Young University
Computer system and method for data base indexing and information retrieval
US4803651A
(en)
*
1986-02-10
1989-02-07
Ibm Corporation
Method for encoding and decoding acyclic, linked-list data structures for efficient storage, retrieval and searching
US4791561A
(en)
*
1987-04-17
1988-12-13
Wang Laboratories, Inc.
Interactive construction of means for database maintenance
US4805099A
(en)
*
1987-04-17
1989-02-14
Wang Laboratories, Inc.
Retrieval of related records from a relational database
WO1989004013A1
(en)
*
1987-10-09
1989-05-05
Nucleus International Corporation
A relational database representation with relational database operation capability
US4975835A
(en)
*
1987-10-30
1990-12-04
Casio Computer Co., Ltd.
Variable length data processing apparatus for consecutively processing variable-length data responsive to one instruction
US4882699A
(en)
*
1988-09-19
1989-11-21
International Business Machines Corp.
Communications network routing and management system
US5829002A
(en)
*
1989-02-15
1998-10-27
Priest; W. Curtiss
System for coordinating information transfer and retrieval
US5237685A
(en)
*
1990-02-26
1993-08-17
International Business Machines Corporation
Linear recurrence dispersal structure and method for parallel processors
US5313604A
(en)
*
1990-11-13
1994-05-17
Hewlett-Packard Company
Method for locating compressed data in a computed memory back up device including steps of refining estimater location
US5225987A
(en)
*
1991-05-20
1993-07-06
Westinghouse Electric Corp.
System for implementing a PC computer configuration system for assembling and mounting of a complex product in situ
US5297280A
(en)
*
1991-08-07
1994-03-22
Occam Research Corporation
Automatically retrieving queried data by extracting query dimensions and modifying the dimensions if an extract match does not occur
US6035343A
(en)
*
1993-06-11
2000-03-07
Fujitsu Limited
Method for executing software formed of software components and a system for executing such software
US5903671A
(en)
*
1993-12-27
1999-05-11
Canon Kabushiki Kaisha
Data compression method and apparatus therefor
US6269363B1
(en)
1994-01-24
2001-07-31
Yossi Matias
Method of accessing data using approximate data structures by relaxing the operations that define same
SE505844C2
(en)
*
1994-09-21
1997-10-13
Qliktech International Ab
Method for extracting information from a database
US5625557A
(en)
*
1995-04-28
1997-04-29
General Motors Corporation
Automotive controller memory allocation
US5799315A
(en)
*
1995-07-07
1998-08-25
Sun Microsystems, Inc.
Method and apparatus for event-tagging data files automatically correlated with a time of occurence in a computer system
US6477585B1
(en)
1995-08-18
2002-11-05
International Business Machines Corporation
Filter mechanism for an event management service
US6052753A
(en)
*
1997-01-21
2000-04-18
Alliedsignal Inc.
Fault tolerant data bus
US7206877B1
(en)
1998-12-22
2007-04-17
Honeywell International Inc.
Fault tolerant data communication network
AUPR824401A0
(en)
*
2001-10-15
2001-11-08
Silverbrook Research Pty. Ltd.
Methods and systems (npw002)
US7580429B1
(en)
*
2002-09-05
2009-08-25
U.S. Robotics
System and methods for improving data compression
US6986110B1
(en)
*
2003-01-02
2006-01-10
Hewlett-Packard Development Company, L.P.
Automated method and system for backtracing of instruction parameters from specified instruction in test cases
US20040249827A1
(en)
*
2003-06-05
2004-12-09
International Business Machines Corporation
System and method of retrieving a range of rows of data from a database system
US20050267884A1
(en)
*
2004-02-06
2005-12-01
Bhonsle Shailendra K
Monotonic independent stack apparatus and methods for efficiently solving search problems
US7844665B2
(en)
2004-04-23
2010-11-30
Waratek Pty Ltd.
Modified computer architecture having coordinated deletion of corresponding replicated memory locations among plural computers
US20060253844A1
(en)
*
2005-04-21
2006-11-09
Holt John M
Computer architecture and method of operation for multi-computer distributed processing with initialization of objects
US20060095483A1
(en)
*
2004-04-23
2006-05-04
Waratek Pty Limited
Modified computer architecture with finalization of objects
US7132963B2
(en)
*
2004-09-13
2006-11-07
Ati Technologies Inc.
Methods and apparatus for processing variable length coded data
US6970110B1
(en)
*
2005-01-08
2005-11-29
Collins Dennis G
Probability centrifuge algorithm with minimum laterally adiabatically-reduced Fisher information calculation
US7870138B2
(en)
*
2006-02-21
2011-01-11
Richard Alton Van Voorhis
File storage and retrieval method
US8300798B1
(en)
2006-04-03
2012-10-30
Wai Wu
Intelligent communication routing system and method
US7657434B2
(en)
*
2006-05-30
2010-02-02
Motorola, Inc.
Frame goals for dialog system
US7505951B2
(en)
*
2006-05-30
2009-03-17
Motorola, Inc.
Hierarchical state machine generation for interaction management using goal specifications
US7797672B2
(en)
*
2006-05-30
2010-09-14
Motorola, Inc.
Statechart generation using frames
US20080133862A1
(en)
*
2006-10-05
2008-06-05
Holt John M
Contention detection with modified message format
US20080140973A1
(en)
*
2006-10-05
2008-06-12
Holt John M
Contention detection with data consolidation
US7831779B2
(en)
2006-10-05
2010-11-09
Waratek Pty Ltd.
Advanced contention detection
US8473564B2
(en)
*
2006-10-05
2013-06-25
Waratek Pty Ltd.
Contention detection and resolution
US20080126503A1
(en)
*
2006-10-05
2008-05-29
Holt John M
Contention resolution with echo cancellation
US20080127213A1
(en)
*
2006-10-05
2008-05-29
Holt John M
Contention resolution with counter rollover
WO2008040071A1
(en)
*
2006-10-05
2008-04-10
Waratek Pty Limited
Contention detection
US20080250221A1
(en)
*
2006-10-09
2008-10-09
Holt John M
Contention detection with data consolidation
JP4707198B2
(en)
*
2006-10-19
2011-06-22
富士通株式会社
INFORMATION SEARCH PROGRAM, RECORDING MEDIUM CONTAINING THE PROGRAM, INFORMATION SEARCH METHOD, AND INFORMATION SEARCH DEVICE
US20080147364A1
(en)
*
2006-12-15
2008-06-19
Motorola, Inc.
Method and apparatus for generating harel statecharts using forms specifications
US8631005B2
(en)
*
2006-12-28
2014-01-14
Ebay Inc.
Header-token driven automatic text segmentation
US7765216B2
(en)
*
2007-06-15
2010-07-27
Microsoft Corporation
Multidimensional analysis tool for high dimensional data
US7747988B2
(en)
*
2007-06-15
2010-06-29
Microsoft Corporation
Software feature usage analysis and reporting
US7870114B2
(en)
2007-06-15
2011-01-11
Microsoft Corporation
Efficient data infrastructure for high dimensional data analysis
US8078658B2
(en)
*
2008-02-01
2011-12-13
International Business Machines Corporation
ASCII to binary decimal integer conversion in a vector processor
US8392489B2
(en)
*
2008-02-15
2013-03-05
International Business Machines Corporation
ASCII to binary floating point conversion of decimal real numbers on a vector processor
US8386757B1
(en)
*
2009-02-13
2013-02-26
Unidesk Corporation
Managed desktop system
US10108993B2
(en)
2010-12-15
2018-10-23
Red Hat, Inc.
Data driven rules engine to dynamically change product business rules
US20120221709A1
(en)
*
2011-02-24
2012-08-30
Bowes James R
Mechanism to allow hosted and on-site implementations to manage product assets as specified by a third party
US10628401B2
(en)
*
2016-04-14
2020-04-21
Qliktech International Ab
Methods and systems for bidirectional indexing
CN110888915A
(en)
*
2019-11-13
2020-03-17
江苏科技大学
Dredger dredging operation analysis method based on big data platform
CN114860190B
(en)
*
2022-04-28
2023-03-24
中国人民解放军战略支援部队信息工程大学
Subinterval division method and subinterval division system for large error in specified interval of floating point arithmetic expression in high-performance calculation function library
Family Cites Families (12)
* Cited by examiner, † Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US3689915A
(en)
*
1967-01-09
1972-09-05
Xerox Corp
Encoding system
US3651483A
(en)
*
1969-01-03
1972-03-21
Ibm
Method and means for searching a compressed index
US3643226A
(en)
*
1969-06-26
1972-02-15
Ibm
Multilevel compressed index search method and means
US3603937A
(en)
*
1969-06-26
1971-09-07
Ibm
Multilevel compressed index generation method and means
US3576534A
(en)
*
1969-08-11
1971-04-27
Compuscan Inc
Image cross correlator
US3612660A
(en)
*
1969-09-08
1971-10-12
Wendell S Miller
Digital data compaction
US3618027A
(en)
*
1970-03-27
1971-11-02
Research Corp
Associative memory system with reduced redundancy of stored information
GB1271620A
(en)
*
1970-05-29
1972-04-19
Inernat Business Machines Corp
Pattern recognition systems
US3697950A
(en)
*
1971-02-22
1972-10-10
Nasa
Versatile arithmetic unit for high speed sequential decoder
JPS5120148B1
(en)
*
1971-05-19
1976-06-23
US3821711A
(en)
*
1972-12-26
1974-06-28
Ibm
Self adaptive compression and expansion apparatus for changing the length of digital information
US3938105A
(en)
*
1974-06-24
1976-02-10
Honeywell Information Systems Inc.
Sequentially encoded data structures that support bidirectional scanning
1975
1975-12-03
US
US05/637,511
patent/US4068298A/en
not_active
Expired – Lifetime
1976
1976-11-30
JP
JP14307076A
patent/JPS52151535A/en
active
Pending
1976-12-01
GB
GB50068/76A
patent/GB1570341A/en
not_active
Expired
1976-12-01
GB
GB36755/78A
patent/GB1570344A/en
not_active
Expired
1976-12-01
GB
GB5203/78A
patent/GB1570343A/en
not_active
Expired
1976-12-01
GB
GB3806/78A
patent/GB1570342A/en
not_active
Expired
1976-12-02
FR
FR7636299A
patent/FR2334148A1/en
active
Granted
1976-12-03
DE
DE19762654975
patent/DE2654975A1/en
not_active
Withdrawn
Also Published As
Publication number
Publication date
GB1570342A
(en)
1980-07-02
DE2654975A1
(en)
1977-06-08
FR2334148B1
(en)
1985-03-08
FR2334148A1
(en)
1977-07-01
US4068298A
(en)
1978-01-10
GB1570344A
(en)
1980-07-02
JPS52151535A
(en)
1977-12-16
GB1570341A
(en)
1980-07-02
Similar Documents
Publication
Publication Date
Title
GB1570343A
(en)
1980-07-02
Information storage and retrieval system
US4609995A
(en)
1986-09-02
Priority controller
US4099257A
(en)
1978-07-04
Markov processor for context encoding from given characters and for character decoding from given contexts
US3296597A
(en)
1967-01-03
Market quotation apparatus
GB1560158A
(en)
1980-01-30
Apparatus for use with memory means
US4059850A
(en)
1977-11-22
Memory system word group priority device with least-recently used criterion
GB1568474A
(en)
1980-05-29
Data processing apparatus
US4229789A
(en)
1980-10-21
System for transferring data between high speed and low speed memories
US5375208A
(en)
1994-12-20
Device for managing a plurality of independent queues in a common non-dedicated memory space
US3553445A
(en)
1971-01-05
Multicipher entry
US4188669A
(en)
1980-02-12
Decoder for variable-length codes
US5138637A
(en)
1992-08-11
First-in-first-out buffer
EP0260461B1
(en)
1995-06-28
Arithmetic coding encoding and decoding method
US3302185A
(en)
1967-01-31
Flexible logic circuits for buffer memory
WO1985001172A1
(en)
1985-03-14
Method and device for two-dimensional facsimile coding
US3693162A
(en)
1972-09-19
Subroutine call and return means for an electronic calculator
US7296048B2
(en)
2007-11-13
Semiconductor circuit for arithmetic processing and arithmetic processing method
US3713109A
(en)
1973-01-23
Diminished matrix method of i/o control
US4734876A
(en)
1988-03-29
Circuit for selecting one of a plurality of exponential values to a predetermined base to provide a maximum value
US4803653A
(en)
1989-02-07
Memory control system
US3702463A
(en)
1972-11-07
Data processor with conditionally supplied clock signals
US4430643A
(en)
1984-02-07
Binary-coded-decimal to binary converter
US5257385A
(en)
1993-10-26
Apparatus for providing priority arbitration in a computer system interconnect
KR840003082A
(en)
1984-08-13
Bus sourcing and shifter control of the central processing unit
US3492648A
(en)
1970-01-27
Keyboard selection system
Legal Events
Date
Code
Title
Description
1980-09-24
PS
Patent sealed [section 19, patents act 1949]
1987-07-22
PCNP
Patent ceased through non-payment of renewal fee
