Text comparator with counters for indicating positions of correctly decoding text elements within an ordered sequence of text elements

Abstract

A text comparator which includes a decoded data memory (13) which contains a plurality of shift registers (SR2.0.-SR7F), one shift register for each one of the plurality of different symbols forming the data base stored within the mass storage device (11). The decoded signal is applied to the input lead of the shift register associated with that character, and a clock signal applied to each shift register of the decoded data memory. In this manner, the decoded data memory will provide signals on the output leads of each shift register indicative of the most recently received character, as well as each of the preceding K characters received from the mass storage device and decoded, where K is the number of bits contained in each shift register of the decoded data memory. The output lead of the shift registers are connected to the input leads of a variety of logical gates, such as AND gates and OR gates, in order to provide an output signal indicating when the desired textual phrase has been located on the disk. In addition, word counters, paragraph counters, and other devices are employed as desired to provide special text comparison functions.

Claims

I claim:

1. In a textual comparison system, a counter indicating which text element within an ordered sequence of text elements is being decoded comprising:

first means for locating within textual material the presence of a first particular character string indicating the end of a text element, said first means providing a first signal indicating whether said first particular character string has been located;

second means for locating within the textual material the presence of a second particular character string indicating the end of the ordered sequence of text elements, said second means for locating providing a second signal indicating whether said second particular character string has been located; and

a multi-bit serial in/parallel out shift register having a clock input terminal, a data input terminal, and a clear input terminal, said first signal being provided to said clock terminal, and said second signal being provided to said clear terminal;

wherein said shift register, upon receipt of the first signal at the clock input terminal, clocks into said shift register at the data input an input signal, said input signal being one or the other of two values, a first occurring input signal being of one value, the later occurring input signals each being of the other value, wherein the second signal provided to the clear input terminal clears said shift register and provides said first occurring input signal to said shift register, whereby a location of said first occurring input signal within said shift register indicates the number of text elements decoded since the receipt of said second signal.

2. The device of claim 1, wherein the first particular character string is the end of a word, and the second particular character string is the end of a sentence.

3. The device of claim 1, wherein the first particular character string is the end of a sentence, and the second particular string is the end of a paragraph.

4. The device of claim 1, wherein the first particular character string is the end of a paragraph, and the second particular character string is the end of a document.

5. In a textual comparison system, a word counter for indicating which word within a sentence is being decoded comprising:

first means for locating within textual material the presence of an end of word character string, said first means for locating providing a first signal indicating whether said end of word character string has been located;

second means for locating within the textual material the presence of an end of sentence character string, said second means for locating providing a second signal indicating whether said end of sentence character string has been located; and

a multi-bit serial in/parallel out shift register having a clock input terminal, a data input terminal, and a clear input terminal, said first signal being provided to said clock terminal, and said second signal being provided to said clear terminal;

wherein said shift register, upon receipt of the first signal at the clock input terminal, clocks into said shift register at the data input terminal an input signal, said input signal being one or the other of two values, a first occurring input signal being of one valve, the later occurring input signals each being of the other value, wherein the second signal provided to the clear input terminal clears said shift register and provides said first occurring input signal to said shift register, whereby a location of said first occurring input signal within said shift register indicates the number of words decoded since the receipt of said second signal.

6. In a textual comparison system, a sentence counter for indicating which sentence within a paragraph is being decoded comprising:

first means for locating within textual material the presence of an end of sentence character string, said first means for locating providing a first signal indicating whether said end of sentence character string has been located;

second means for locating within the textual material the presence of an end of paragraph character string, said second means for locating providing a second signal indicating whether said end of paragraph character string has been located; and

a multi-bit serial in/parallel out shift register having a clock input terminal, a data input terminal, and a clear input terminal, said first signal being provided to said clock terminal, and said second signals being provided to said clear terminal;

wherein said shift register, upon receipt of the first signal at the clock input terminal, clocks into said shift register at the data input terminal an input signal, said input signal being one or the other of two values, a first occurring input signal being of one value, the later occurring input signals each being of the other value, wherein the second signal provided to the clear input terminal clears said shift register and provides said first occurring input signal to said shift register, whereby a location of said first occurring input signal within said shift register indicates the number of sentences decoded since the receipt of said second signal.

7. In a textual comparison system, a paragraph counter for indicating which paragraph within a document is being decoded comprising:

first means for locating within textual material the presence of an end of paragraph character string, said first means for locating providing a first signal indicating whether said end of paragraph character string has been located;

second means for locating within the textual material the presence of an end of document character string, said second means for locating providing a second signal indicating whether said end of document character string has been located; and

a multi-bit serial in/parallel out shift register having a clock input terminal, a data input terminal, and a clear input terminal, and said second signal being provided to said clear terminal;

wherein said shift register, upon receipt of the first signal at the clock input terminal, clocks into said shift register at the data input terminal an input signal, said input signal being one or the other of two values, a first occurring input signal being of one value, the later occurring input signals each being of the other value, wherein the second signal provided to the clear input terminal clears said shift register and provides said first occurring input signal to said shift register, whereby a location of said first occurring input signal within said shift register indicates the number of paragraphs decoded since the receipt of said second signal.

Description

RELATED APPLICATIONS

1. Field of the Invention

This invention relates to a structure and method for searching computer data bases in order to locate and retrieve textual information.

2. Description of the Prior Art

Prior art text comparators for searching a computer data base are known. Structures for carrying out such techniques (such structures are herein called "textual comparison systems") are used, for example, by Lockheed Dialog Information Retrieval Service, the U.S. Government "Flite" service, "Lexis", and others.

Such prior art textual comparison systems are software oriented in that a portion of the information stored in the computer (called a "data base") must be loaded into the computer working memory from a mass memory storage device (typically a magnetic disk). The portion of the data base within the working memory of the computer is scanned by the computer, as controlled by software instructions, in order to determine if any portion of the data base stored in the computer working memory matches the desired text. Typically the textual material comprising the data base is stored by using a set of standard data base characters such as the well-known and commonly used American National Standard Code for Information Interchange ("ASCII"). The ASCII characters and their binary and hexidecimal representations are shown in Table 1. Thus, such prior art software-oriented text comparators are rather slow in that the computer must control the transfer of sequential portions of the data base from a large storage media, such as a disk, to the computer memory, and the computer must then utilize an iterative process in order to determine whether the desired text is contained within that portion of the data base which has been transferred to the computer memory. Because the computer itself is performing the search, such prior art searching techniques are rather slow, and consequently expensive due to the large amount of computer time required to perform a search.

Another prior art comparator system is described in U.S. Pat. No. 4,152,762 issued May 1, 1979 to Bird et al. Bird et al describe a method and structure for text comparison which is rather complex and requires each desired textual word or phrase to be stored in octal format in one of a plurality of "key memories". In addition, the Bird structure requires the use of additional memories, including a "pointer memory" and a "hash memory", as well as a wide variety of other subcircuits. Thus, the Bird structure is rather complex.

SUMMARY

The present invention attacks the problem of text comparison for the purpose of retrieving textual information from a large data base system from a different point of view. In accordance with one embodiment of this invention, information stored in a mass memory unit, such as a magnetic disk, as a plurality of bytes, each byte representing a character, is input to a text comparison sub-circuit which includes a decoder means, decoded data memory, and one or more logical operator sections. Each byte of information received from the disk is input to the decoder means and is immediately decoded, and a signal corresponding to the character corresponding to the byte input to the decoder means byte is generated. The system is capable of handling up to P different characters, where P is a selected positive integer.

The decoded data memory serves to store information received from the decoder means pertaining to characters represented by the bytes of information received from the disk. The decoded data memory contains a plurality of P serial in-parallel out shift registers, one shift register being uniquely associated with each one of the plurality of P different characters forming the data base stored in the storage device. Corresponding to the pth character (wherein p is an integer given by 1.ltoreq.p.ltoreq.P) and contained within the decoded data memory is a pth shift register uniquely arranged to receive the signal from the decoder representing the pth character. Upon receipt of a byte from the disk corresponding to a specific character, a first signal (e.g. a binary zero) is applied to the input serial lead of the shift register uniquely associated with the character decoded by the decoder means, and a second signal (e.g. a binary one) is applied to the serial input lead of all shift registers associated with all other characters. A clock signal is applied to each shift register of the decoded data memory, thus shifting the data on the input lead of each shift register into the least significant bit of the shift register, and shifting each bit previously stored in a shift register to the next most significant bit position within the shift register. In this manner, the decoded data memory will provide signals on the output leads of each shift register indicative of the most recently received character, as well as each of the preceding (K-1) characters (i.e. a "character string" comprising K characters) received from the mass memory unit and decoded, where K is the number of bits contained in each shift register of the decoded data memory. Thus, each bit stored within a shift register will be a binary one except for the binary zero bits stored within a shift register corresponding to the location within the K bit character string of a character corresponding to the shift register. Of importance, only a single shift register within the decoded data memory will store a binary zero bit corresponding to each of the K positions within the K bit character string. By examining the bits stored within each shift register of the decoded data memory, the characters comprising the K bit character string, and their relative position within the character string is determined.

The output leads of the shift registers, which provide signals defining the relative location of characters recently received from the mass storage device and decoded by the decoder means, are connected to the input leads of one or more logical operator sections which include a number of logical gates, such as AND gates and NOR gates, in order to provide an output signal indicating that a desired textual phrase has been located in the mass storage device.

In addition, the operator sections include word counters, paragraph counters, and other devices are employed as desired to provide special text comparison functions. The text comparison sub-circuit, the decoded data memory, and the logical operator sections of this invention are capable of operating at very high speeds, equal to the data output speed of the mass memory unit, thus providing a very high speed textual comparison operation.

A second embodiment of a text comparator constructed in accordance with this invention receives data stored in a mass storage device. This embodiment includes word logic, delimiter logic, set logic, set combination logic, proximity logic, and programming logic. The delimiter logic serves to monitor the characters transferred from the mass storage device and provides a signal depicting whether the character being transferred is a predefined delimiter character and, if so, the type of delimiter character. The word logic serves to store data regarding predefined words (i.e., strings of characters) which are to be located and provides output signals indicating when such predefined words have been located. The set logic receives the delimiter signals and word signals and provides output signals when selected words are located in the same sentence, same paragraph, etc., as desired. The set combination logic serves to combine the signals from the set logic in order to generate output signals in response to more complex search strategies then can be easily detected by the set logic. The proximity logic provides output signals indicating when predefined words detected by the word logic, or predefined set of words, as detected by the set logic, or a combination of this information, occurs within a predefined proximity. For example, the proximity logic will determine, if a first selected word occurs within N (where N is a selected integer) words of a second preselected word.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a textual comparison system constructed in accordance with this invention;

FIG. 2 is a diagram of a decoder means utilized in accordance with this invention;

FIG. 3 is a diagram showing the interrelation of FIGS. 3a and 3b;

FIGS. 3a and 3b are diagrams of the decoded data memory constructed in accordance with this invention;

FIG. 4 is a diagram of one shift register of the decoded data memory of FIG. 3;

FIGS. 5a through 5e are diagrams of specific embodiments of the logical operator section of this invention;

FIG. 6a is a diagram of one embodiment of a word counter of this invention;

FIG. 6b is a diagram of one embodiment of a sentence counter of this invention;

FIG. 6c is a diagram of one embodiment of a paragraph counter of this invention;

FIGS. 7a and 7b are diagrams of another embodiment of the logical operator section of this invention;

FIG. 8 is a block diagram of a textual comparator construction in accordance with a second embodiment of this invention;

FIG. 9 is a diagram depicting the relationship between FIGS. 9a, 9b and 9c which form a schematic diagram of the delimiter logic 113 shown in FIG. 8;

FIG. 10 is a diagram depicting the relationship between FIGS. 10a-10d which in turn form a schematic diagram of the set logic 114 depicted in FIG. 8;

FIG. 11 is a diagram which depicts the relationship between FIGS. 11a and 11b which in turn form a schematic diagram of the set combination logic 115 depicted in FIG. 8;

FIG. 12 is a diagram depicting the relationship between FIGS. 12a-12d which in turn form a schematic diagram of the word logic 112 shown in FIG. 8; and

FIG. 13 is a diagram depicting the relationship between FIGS. 13a-13c which in turn form a schematic diagram of the proximity logic 117 shown in FIG. 8.

DETAILED DESCRIPTION

The following specification recites certain standard, well-known, and generally available TTL components. These TTL components are available from a number of suppliers, including but not limited to those listed in the specification, and as will be appreciated by those of ordinary skill in the art, these specified components can be used in accordance with the teachings of this invention, regardless of the supplier. For further reference, the Applicant cites the "National Semiconductor TTL Data Book", National Semiconductor Corporation, 1976, the "Signetics TTL Logic Data Manual, 1982", Signetics, 1982, and the "Signetics Low Power Schottky Pocket Guide", Signetics, 1978.

FIRST EMBODIMENT

System Overview

FIG. 1 shows a block diagram of a text comparator constructed in accordance with the first embodiment of this invention. Mass storage device 11 comprises a device suitable for the storage of a large quantity of data. Such data is typically called a "data base". The data base might be, for example, textual material such as United States patents, judicial decisions from various courts, or other information. Mass storage device 11 typically comprises a magnetic disk, as is well known in the computer arts, and the data base stored within mass storage device 11 is typically stored in ASCII format, although this invention can be utilized in conjunction with data bases stored in other than ASCII format (for example, EBCDIC).

Data stored in mass storage device 11 is transferred via bus 11a to decoder 12. Typically, bus 11a comprises a plurality of electrical leads, in order that a plurality of bits forming a single byte of information may be transferred simultaneously from mass storage device 11 to decoder 12. The simultaneous transfer of a plurality of bits forming a single byte is often referred to as "parallel data output".

Decoder 12 receives each byte transferred from mass storage device 11, and decodes that byte into one of a plurality of unique decoded data signals. Each such decoded data signal represents a unique one of the characters which form the data base stored in mass storage device 11. For example, such characters typically comprise the numbers zero through nine, twenty-six capital letters, twenty-six lower case letters, and a variety of punctuation and special symbols such as asterisk, period, comma, question mark, space, and the like. Inasmuch as ASCII is one widely used method of coding such characters into a plurality cf bytes, this specification will refer to ASCII coding in order to explain the operation of one embodiment of this invention. However, it is to be understood that this invention is equally useful in systems wherein coding schemes other than ASCII is utilized. A cross reference table listing each character and its ASCII equivalent is given in Table 1.

The output from decoder 12 is connected via bus 12a to decoded data memory 13. Because ASCII comprises a plurality of 96 characters, bus 12a in the preferred embodiment comprises a plurality of 96 leads, one such lead being associated with a unique one of the ASCII characters. However, it should be understood that as many leads as required can be used depending on the number of characters to be decoded and in general bus 12a comprises a plurality of M leads, where M is a selected positive integer representing the number of characters to be decoded.

Decoded data memory 13 stores the decoded data provided by decoder 12 for a sequence of K characters stored in mass storage device 11 where K is a positive integer which is fixed by the particular design of the decoded data memory 13. Typically K will be either eight or sixteen, although K may be any positive integer. Decoded memory 13 comprises a plurality of 96 shift registers, one shift register for each ASCII character. K is equal to the number of bits which are stored within each shift register. The data (i.e., a logical one or a logical zero) contained in each of the K bits of the 96 shift registers of decoded data memory 13 indicates which ASCII characters form each character of the K byte character string ending in the most recently decoded character.

An output bus 13a, containing a number of leads equal to K96 (K96 equals K multiplied by 96), connects each of the K96 output leads of the 96 shift registers of decoded data memory 13 to logical operator section 14. Logical operator section 14 comprises one or more logical gates which perform a logical operation on the data stored in the shift registers of decoded data memory 13. This logical operation provides an output signal indicating when a desired textual phrase, string of characters, or sets of strings of characters, has been located within the data base stored in mass storage device 11. This output signal from logical operator section 14 is applied via bus 14a to central processing unit (CPU) 15. Thus, central processing unit 15 is made aware that a desired textual phrase has been located in mass storage device 11. CPU 15 then follows its set of programmed instructions, and utilizes the desired textual phrase which has been located in the data base. Typically, CPU 15 stores the address location of the beginning of the desired textual phrase which has been located in the data base, stores the record number of the record (i.e., patent number, etc.) in which the desired textual phrase has been found, or performs other desired tasks in response to the location and identification of the desired textual phrase within the data base. It is to be understood that, once the desired textual phrase has been located within the data base stored in mass storage device 11, and the CPU signalled by logical operator section 14, the operation of CPU 15 is generally the same as the operation of central processing units in systems utilizing prior art text comparison techniques.

Decoder 12

Referring to FIG. 2, the detailed operation of decoder 12 will now be explained. The embodiment of decoder 12 shown in FIG. 2 is designed for use with systems utilizing ASCII coding. For systems utilizing other than ASCII coding, the specific design of decoder 12 differs from that shown in FIG. 2, but is easily provided by one of ordinary skill in the art, in light of the teachings of this specification. In ASCII format, as shown in Table 1, each character comprises eight binary digits (bits) or two hexidecimal digits. Input bus 11a comprises eight leads, thus providing to decoder 12 in a parallel output format the 8 bits forming a single ASCII character stored in mass storage device 11 (FIG. 1). Input bus 11a also comprises an additional lead 99, which provides a valid data signal (VDA) which, when high (logical "1") indicates that valid data is available on bus 11a from mass storage device 11. The four least significant bits (LSB) of the ASCII btye received from bus 11a are applied to four bit buffer B-1, thus providing on leads D.sub.0 through D.sub.3 buffered signals representing the four least significant bits of the ASCII byte. Similarly, the four most significant bits (MSB) of the ASCII byte received on bus 11a are applied to four bit buffer B-2, thus providing on leads D-7 through D-4 buffered signals representing the four most significant bits of the ASCII byte. Buffers B-1 and B-2 may comprise, for example, a 74125 device, such as manufactured and sold by Texas Instruments.

The buffered four least significant bits (on leads D.sub.0 through D.sub.3) are applied as input signals to demultiplexers 105-2 through 105-7 and the buffered four most significant bits (on leads D-7 through D-4) are applied as input signals to demultiplexer 103. Demultiplexers 103 and 105-2 through 105-7 are four bit to sixteen bit demultiplexers such as the 74LS154 manufactured and sold by Texas Instruments. Thus, each demultiplexer 103 and 105-2 through 105-7 provides a one of sixteen bit demultiplexing function, although only six of the sixteen output signals from demultiplexer 103 (on leads R.sub.2 through R.sub.7) are used because, as previously mentioned, ASCII comprises 96 characters, and these 96 characters are uniquely defined by the output leads of six separate four-to-sixteen bit demultiplexers 105-2 through 105-7, as will be more fully described below. Accordingly, as shown in Table 1, the four most significant bits of an ASCII byte range from a binary 0001 (a decimal 1) to a binary 0111 (a decimal 7).

The output signal on each output lead of demultiplexers 103 and 105-2 through 105-7 is normally high (logical one). Each demultiplexer has as many output leads (16) as there are different binary input signals (16) which can be applied to its four input leads. Each output lead corresponds uniquely to one possible input signal to the demultiplexer. However, when a four bit input signal (the four most significant bits on leads D-4 through D-7 connected to demultiplexer 103, or the four least significant bits on leads D.sub.0 through D.sub.3 applied to demultiplexers 105-2 through 105-7) is input to a demultiplexer, and that demultiplexer is enabled (to be more fully described below), a logical zero is placed on the output lead corresponding to the input signal applied to the demultiplexer. For example, if a four bit binary input signal 0101 is applied to a demultiplexer, and that demultiplexer is enabled, the output lead 5 (corresponding to a binary 0101) of the demultiplexer will be low, and all other output leads of the demultiplexer will be high. All output leads of a disabled demultiplexer are high.

Demultiplexers 103 and 105-2 through 105-7 are enabled by the application of a low signal to their respective enable terminals. This occurs only when valid data is present on bus 11a from the mass storage device. As previously described, a logical one on valid data lead 99 indicates that valid data is present on bus 11a. This logical one signal is inverted by inverter 101a, and a logical zero VDA signal is applied to NOR gate 102 and NOR gates 104-2 through 104-7. Although NOR gates 102 and 104-2 through 104-7 are shown external to demultiplexers 103 and 105-2 through 105-7, these NOR gates are an integral part of the 74LS154 devices. The output lead of NOR gate 102 is connected to the enable input lead of demultiplexer 103, and the output leads of NOR gates 104-2 through 104-7 are connected to the enable input leads of demultiplexers 105-2 through 105-7, respectively. Thus, with a low VDA signal on lead 99, indicating that valid data is not present on input bus 11a, the VDA signal from the output lead of inverter 101a will be high, thus causing the output signal from NOR gates 102 (having its other input lead connected to ground) to be low, thus disabling demultiplexer 103. With demultiplexer 103 disabled, leads R.sub.2 through R.sub.7 will all be high; thus disabling demultiplexers 105-2 through 105-7.

On the other hand, with a logical high on VDA lead 99, indicating that valid data is present on input bus 9, the VDA signal will be low. Because one input lead of NOR gate 102 is connected to ground (logical zero) and the other input lead of NOR gate 102 is connected to VDA, a low VDA signal causes the output signal from NOR gate 102 to go high, thus enabling demultiplexer 103. Demultiplexer 103 then demultiplexes the four most significant bits, thus providing a logical low on the unique output lead R.sub.2 through R.sub.7 corresponding to the value of the four most significant bits (D.sub.4 through D.sub.7). Output leads R.sub.2 through R.sub.7 of demultiplexer 103 are connected to one input lead of NOR gates 104-2 through 104-7, respectively, with the other input lead of NOR gates 104-2 through 104-7 being connected to VDA. With a logical low VDA signal applied to one lead of NOR gates 104-2 through 104-7 and a logical low signal corresponding to the demultiplexed most significant bits of a unique one of leads R.sub.2 through R.sub.7 applied to the other lead of one of the NOR gates 104-2 through 104-7, a high signal will be generated on the output lead of the NOR gate 104-2 through 104-7 corresponding to the value of the most significant bits D4 through D7. Thus, upon receipt of valid data (high VDA signal) a selected one of demultiplexers 105-2 through 105-7 will be enabled, and all other demultiplexers 105-2 through 105-7 will be disabled by the logical high signal on the remaining leads R.sub.2 through R.sub.6. For example, with a high VDA signal, indicating receipt of valid data, and the four most significant bits equal to 0010, demultiplexer 103 is enabled and a low signal generated on lead R.sub.2, with leads R.sub.3 through R.sub.7 remaining high. Demultiplexer 105-2 is enabled by the low VDA signal and the low signal on lead R.sub.2. Demultiplexers 105-3 through 105-7 remain disabled by the high level signals on leads R.sub.3 through R.sub.7, respectively.

The output signals on each output lead of the disabled demultiplexers 105-2 through 105-7 will be high, as previously described. The signals on the output leads of the enabled one of demultiplexers 105-2 through 105-7 will be high, except for the single output lead which corresponds to the decoded least significant bits on leads D.sub.0 through D.sub.3 connected to the input leads of demultiplexers 105-2 through 105-7. In this manner, upon the receipt of valid data on bus 11a, a single low signal is generated on a single output lead of demultiplexers 105-2 through 105-7. The lead which contains that low signal corresponds to the character represented by the 8-bit ASCII byte received on bus 11a. For example, with a high VDA signal and an eight bit byte equal to 01101101 received on bus 11a, demultiplexer 103 will be enabled, as previously described, and the four most significant bits (0110) demultiplexed by demultiplexer 103, thereby generating a logical low signal on output lead R.sub.6. This will enable demultiplexer 105-6, which in turn demultiplexes the four least significant bits (1101 ), thereby generating the signals on a logical low on output lead 6D of demultiplexer 105-6, with all other output leads of demultiplexer 105-6 remaining high. Output lead 6D corresponds to the ASCII character m, represented by 01101101. A high signal is present on leads R.sub.2, R.sub.3, R.sub.4, R.sub.5 and R.sub.7, thus disabling demultiplexers 104-2, 104-3, 104-4, 104-5, and 104-7, thereby providing high signals on output leads 2.0. through 5F and 7.0. through 7F. For convenience, the output leads from demultiplexers 105-2 through 105-7 are numbered with two digits. The first digit indicates which of the six demultiplexers 105-2 through 105-7 is connected to the lead, and the second digit indicates the lead number (represented in hexidecimal as 0 through F). Utilizing this notation, the first digit also represents the four most significant bits of the data word received on bus 11a, and the second digit also represents the four least significant bits of the data word received on bus 11a.

Inverters 101a through 101j provide a time delayed VDA' signal. By applying the valid data signal (VDA) on lead 99 to the input lead of inverter 101a, a time delayed valid data signal (VDA') is generated by inverter 101j on node 101. The VDA' signal is delayed from the VDA signal by approximately 100 nanoseconds. The VDA' signal is used to enable the decoded data memory 13 (FIG. 1) to receive data from output leads 2.0. through 7F of decoder 12, but provides a time delay sufficient to allow the proper operation of decoder 12 prior to the receipt of decoded data by decoded data memory 13. Each inverter 101a through 101j may comprise, for example, one of the six inverters comprising a 7404 Hex inverter, such as is manufactured and sold by Texas Instruments.

Decoded Data Memory 13

Referring to FIGS. 3a and 3b, the operation of decoded data memory 13 will now be explained. Upon the receipt of a high VDA' signal (corresponding to valid data on input bus 11a of decoder 12) on node 101 of decoded data memory 13, buffer 201 provides hiqh clock signals CLK-2 through CLK-7. Buffer 201 may comprise, for example, a 74365 device manufactured and sold by Signetics.

Decoded data memory 13 comprises a plurality of shift registers such as shift register SR2.0.. For purposes of clarity, the plurality of 96 shift registers are not individually labelled; only shift register SR2.0. is so labelled. However, the array of shift registers of decoded data memory 13 of FIGS. 3a and 3b are arranged in a matrix comprising six rows (row 2 through row 7) and sixteen columns (column .0. through column F). Thus, shift register SR2.0. is the shift register located at the intersection of row 2 and column .0.. In a similar manner, the shift register located at the intersection of row n and column m will be referred to as shift register SRnm in this specification.

Each shift register SRnm (where n and m are positive integers given by 1.ltoreq.n.ltoreq.N and 1.ltoreq.m.ltoreq.M) is connected to a unique one nm of leads 2.0. through 7F which corresponds to that shift register. Thus, shift register SR2.0. is connected to lead 2.0. and shift register SRnm is connected to lead nm. Leads 2.0., nm and NM in turn are connected to the decoder 12 of FIG. 2. In this fashion, each shift register of the decoded data memory 13 is connected to a unique output lead of decoder 12 (FIG. 2), thereby causing each shift register of decoded data memory 13 to correspond to a unique one of the 96 ASCII characters. For convenience, the ASCII character associated with each shift register is indicated above the shift register. Thus, shift register SR2.0., connected to lead 2.0., corresponds to a blank (b) which is coded in ASCII as a hexidecimal "2.0.", as shown in Table 1. In a similar manner, each of the 96 shift registers of decoded data memory 13 corresponds to a unique ASCII character. As previously mentioned, each shift register SRnm is capable of storing K bits, thus allowing decoded data memory 13 to store K decoded characters and their relative position within the string of K characters.

Clock signals CLK-2 through CLK-7 are connected to each shift register within row 2 through row 7, respectively. Upon the receipt of a high VDA' signal, CLK-2 through CLK-7 go high. The low to high transition of clock signals CLK-2 through CLK-7 enables all shift registers of rows 2 through 7, respectively, of decoded data memory 13. Enabling each shift register causes the signal on the signal lead connected to that shift register to be stored in the least significant bit of the shift register, and all other data previously stored shifted to the next most significant bit. Thus, for example, if a logical zero is present on signal lead 2.0., and a high VDA' signal is received, CLK-2 will go high, thus causing the logical zero on lead 2.0. to be stored.in the least significant bit of shift register SR2.0.. All other data previously stored in shift register SR2.0. will be shifted to the next most significant bit, with the previously stored most significant bit being lost.

The plurality of shift registers comprising decoded data memory 13 may comprise, for example, eight bit serial in, parallel out shift registers, such as 74164 devices manufactured and sold by Signetics. Alternatively, each shift register SR2.0. through SR7F may comprise a plurality of 74164 devices serially connected in order to increase the number of bits which are stored within each of the 96 shift registers forming decoded memory 13.

Of importance, only a single logical zero will be present on signal leads 2.0.-7F at any time. Thus, the unique one of the 96 shift registers which corresponds to the most recently decoded byte from mass storage device 11 will store a least significant bit equal to a logical zero, while all other shift registers will store a least significant bit equal to a logical one. Thus, for example, if a blank was the most recently decoded ASCII character, decoded data memory 13 will indicate this fact by the presence of a logical zero as the least significant bit of shift register 2.0., with the least signigicant bits of all other shift registers 5Rnm being equal to a logical one. In a similar fashion, the previously decoded character will be indicated by the presence of a logical zero as the next to least significant bit stored in the shift register corresponding to the previously decoded character. Thus, if an "!" was the previously decoded character, the next to least significant bit stored within shift register SR21 (corresponding to the exclamation point) will be a logical zero, and the next to least significant bit stored within all other shift registers will be a logical one. In this manner, each of the most recently decoded K characters are indicated by the location of logical zeros within the shift register of decoded data memory 13, where K is the number of bits stored in each shift register.

An example of the ability of decoded data memory 13 to store a character string which is decoded by decoder 12 (FIG. 1) will now be given. Initially all bits contained within each of the 96 shift registers of decoded data memory 13, comprise logical ones. This may be accomplished, for example, by providing a low VDA signal, thus disabling demultiplexers 105-2 through 105-7 (FIG. 2), and thereby providing logical one signals on leads 2.0. through 7F, and providing a series of K low to high transitions on terminal 101, thus shifting a series of K logical one signals into each K bit shift register (SR2.0. through SR7F) of decoded data memory 13. These low to high transitions on terminal 101 are easily provided with well known circuitry (not shown).

If the word "Work" is to be decoded by decoder 12, the 8 bits corresponding to the hexadecimal ASCII code 57 for a "W" will be output from mass storage device 11 to input bus 11a of decoder 12 (FIG. 2). A valid data signal (high VDA) will also be made available on bus 11a. Demultiplexer 103 will be enabled, and a logical low signal generated on lead R.sub.5 corresponding to the most significant bits of the ASCII code for W. The logical low on lead R.sub.5, and the low VDA signal will enable demultiplexer 105-5. Demultiplexer 105-5 then demultiplexes the least significant bits, and provides a logical low on output lead 57. All remaining output leads of demultiplexers 105-2 through 105-7 remain high at this time. The output signals on demultiplexers 105-2 through 105-7 are then (after the time delay provided by inverters 101a through 101j) shifted into the least significant bit positions of their corresponding shift registers of decoded data memory 13 (FIG. 3). Thus, the least significant bit of shift register SR57 will store a logical zero, and the least significant bits of all remaining shift registers will store a logical one. The shift register SR57 will store the bits 111.0., and all other shift registers will store the bits 1111, if shift registers SR20 through SR7F comprise four bit shift registers.

The letter "o" (hexadecimal 6F) is then output from mass storage device 11 to decoder 12 (FIG. 2). Demultiplexer 103 decodes the four most significant bits D.sub.4 through D.sub.7 and provides a logical low signal on output lead R.sub.6. The low signal on lead R.sub.6, together with the low VDA signal, enables demultiplexer 105-6. Demultiplexer 105-6 then decodes the four least significant bits D.sub.0 through D.sub.3, and provides a logical low signal on output lead 6F. All signals on all remaining output leads of demultiplexers 105-2 through 105-7 are logical ones at this time. The signals on the output leads of demultiplexers 105-2 through 105-7 are then shifted into the least significant bit of their associated shift registers of decoded data memory 13 (FIG. 3). At this time, shift register SR6F corresponding to the character "o" will store the bits 1110, indicating that a "o" has been the most recently decoded character. Similarly, shift regiser SR57 will store the bits 1101, indicating that the character "W" was the previously decoded character. All others shift registers of decoded data memory 13 will store the bits 1111 indicating that their associated characters are not one of the last four characters decoded.

The character "r" (hexadecimal 72) is now output from mass storage device 11 to decoder 12 (FIG. 2). Demultiplexer 103 decodes the most significant bits of the character "r", and provides a logical zero signal on output lead R.sub.7. Demultiplexer 105-7 is thus enabled, and provides a logical zero signal on output lead 72, with the signals on all other output leads 2.0. through 7F being logical ones. The signals on the output leads of demultiplexers 105-2 through 105-7 are then shifted into decoder data memory 13 (FIG. 3). Shift register SR72 will store the bits 1110, shift register SR6F will store the bits 1101, shift register SR57 will store the bits 1011, and all remaining shift registers will store the bit 1111, indicating that the character string "Wor" has been decoded.

The ASCII character "k" (hexadecimal 6B) is then output from mass storage device 11 to decoder 12 (FIG. 2). Demultiplexer 103 decodes the most significant bits of the ASCII character, thus providing a logical zero signal on lead R.sub.6. The logical zero signal on lead R.sub.6 enables demultiplexer 105-6. Demultiplexer 105-6 demultiplexes the least significant bits of the ASCII character, thereby providing a logical zero signal on output lead 6B, with logical ones being present on all other output leads 2.0. through 7F. The data on the output leads of demultiplexer 105-2 through 105-7 is then shifted into decoder data memory 13 (FIG. 3a). At this time, shift register SR6B will store the bits 1110, shift register SR72 will store the bits 1101, shift register 6F will store the bits 1011, and shift register SR57 will store the bits 0111, indicating that the character string "Work" has been decoded.

                  TABLE 1
    ______________________________________
                                ASCII
                ASCII           Code
                Code            (Hexi-
    Character   (Binary)        decimal)
    ______________________________________
    blank       00100000        2.0.
    !           00100001        21
    "           00100010        22
    #           00100011        23
    $           00100100        24
    %           00100101        25
    &           00100110        26
    '           00100111        27
    (           00101000        28
    )           00101001        29
    *           00101010        2A
    +           00101011        2B
    ,           00101100        2C
    -           00101101        2D
    .           00101110        2E
    /           00101111        2F
    .0.         00110000        3.0.
    1           00110001        31
    2           00110010        32
    3           00110011        33
    4           00110100        34
    5           00110101        35
    6           00110110        36
    7           00110111        37
    8           00111000        38
    9           00111001        39
    :           00111010        3A
    ;           00111011        3B
    <           00111100        3C
    =           00111101        3D
    >           00111110        3E
    ?           00111111        3F
    @           01000000        4.0.
    A           01000001        41
    B           01000010        42
    C           01000011        43
    D           01000100        44
    E           01000101        45
    F           01000110        46
    G           01000111        47
    H           01001000        48
    I           01001001        49
    J           01001010        4A
    K           01001011        4B
    L           01001100        4C
    M           01001101        4D
    N           01001110        4E
    O           01001111        4F
    P           01010000        5.0.
    Q           01010001        51
    R           01010010        52
    S           01010011        53
    T           01010100        54
    U           01010101        55
    V           01010110        56
    W           01010111        57
    X           01011000        58
    Y           01011001        59
    Z           01011010        5A
    [           01011011        5B
                01011100        5C
    ]           01011101        5D
     or         01011110        5E
    -           01011111        5F
    `           01100000        6.0.
    a           01100001        61
    b           01100010        62
    c           01100011        63
    d           01100100        64
    e           01100101        65
    f           01100110        66
    g           01100111        67
    h           01101000        68
    i           01101001        69
    j           01101010        6A
    k           01101011        6B
    l           01101100        6C
    m           01101101        6D
    n           01101110        6E
    o           01101111        6F
    p           01110000        7.0.
    q           01110001        71
    r           01110010        72
    s           01110011        73
    t           01110100        74
    u           01110101        75
    v           01110110        76
    w           01110111        77
    x           01111000        78
    y           01111001        79
    z           01111010        7A
    {           01111011        7B
                01111100        7C
    }           01111101        7D
    .about.     01111110        7E
    DEL         01111111        7F
    ______________________________________