Signal processing apparatus and method

DESCRIPTION

GIVES

PATENT OF INVENTION

No. 93 050

APPLICANT: BANG & OLUFSEN A / S, Danish, industrial and commercial, established in Peter Bangsvej 15, DK-7600 Struer, Denmark.

EPIGRAPH: APPLIANCE AND PROCESS FOR PROCESSING

SIGNALS

INVENTORS: Gert Lykke Moeller.

Claim of right of priority under Article 4 of the Paris Convention of 20 March 1883.

Great Britain on 3 February 1989 under⁹ 8902414.5 and the United States Application, October 19, 1989, under^and . 424,112.

> NPI MOD Π3 RF 1S732

<img file="PT93050B_D0001.tif" />

Description of Bang e patent; Olufsen A / S, Danish, industrial and commercial, established at Peter Bangsvej 15, DK-7600 Struer, Denmark (inventor: Gert Lykke Moeller, resident of Denmark), FOR SIGNAL PROCESS AND PROCESS

description

The present invention relates to apparatus and methods for processing signals, for example signals used for communication or control purposes. It is particularly applicable to signal processing which may consist of a number of components each of which is representative of an aspect of a physical entity, the present invention providing means for improving the information content or reducing the uncertainty of such signals.

Signal processing systems are known which process signals consisting of a number of components according to predetermined information about relationships between the components. The so-called artificial intelligence systems employ processors that represent known relationships, in some forms of representation, of rules and apply the 1 -

<img file="PT93050B_D0002.tif" />

rules to an input signal to produce an output signal with greater information content. Conventionally, the rule representation may contain a large number of logical relationships between the possible components of the input signal (which, in general terms, represent known information about the physical entity), a shell process is performed through the representation of rules in a attempt to deduce other relationships and other information. During the search process other rules may be established and you may have to store a large amount of information regarding the results of applying individual rules already visited. Thus, a problem encountered in conventional systems is that the memorization needs can become very large. This has proved to be inconvenient when practically conventional systems are to be realized in small scale processing apparatus, for example in microcomputer systems.

Considerable effort has also been made to establish search strategies in an attempt to find techniques to quickly reach the intended information, but none of these techniques is entirely satisfactory.

Considered in one aspect, the present invention provides a signal processing apparatus for reducing the uncertainty of an input signal which may consist of several components, comprising means for storing a representation of a combination set signal of said components. which indicates if combinations are possible, means for receiving said input signal and identifying any set containing information about a component of said input signal that is determined, means for identifying from the respective identified set combinations consistent with the values ​​of the input signal components, and means for determining from combinations

<img file="PT93050B_D0003.tif" />

information about the value of at least one component of the input signal is identified.

In another aspect, the present invention provides a method for increasing the information content of an input signal by using stored rule information, comprising storing the signal in register means in the form of multiple two-bit pairs. , each corresponding to an input signal variable, the rule information being stored as binary words, each representing an allowable combination of variables, in the same way as in the input signal, taking all first bits of the pairs as a first component of the signal and the second byte with a second component of the signal, the combination in an OR relation of a binary word of a rule with one of the first and second components, combining in one OR relationship the binary word complement with the other of the first and second components and storing the resulting combinations in recorder media, as an exit sign.

Considered in a third aspect, the present invention provides a data processing process according to the information contained in a set of rules, each of which expresses a relationship between a number of variables, comprising converting each rule into a number of first binary words that indicate whether or not particular combinations of variables are permissible and a second set of binary words corresponding to a rule and indicating which variables are implicated in that rule, corresponding to individual bits in the first few. and second words to individual variables, sorted in the same order in all first and second words, taking data containing known values ​​of at least one of said variables, identifying from the second words d «

<img file="PT93050B_D0004.tif" />

any rule involving the known variable or variables, selecting the first words that match the identified rules and using the selected words to determine the value of at least one other variable.

Considered in a fourth aspect, the present invention provides a rule representation apparatus for processing information contained in a set of rules, each expressing a relationship between a number of variables, comprising a rule memory arranged to store binary words, each of which indicates whether or not a particular combination of variables is permissible, including said bit words representing the respective variables in the combinations, a control memory arranged to store respective binary words for each rule, indicating the bits of each word whether a particular variable is involved in the corresponding rule and the order of the associated variables. with the rule memory words the same as the control memory words, and addressing means providing access to each binary word in the rule memory of a particular rule in response to a control memory output indicating that the particular rule is required.

D_and preferably, the input signal components comprise binary representations of aspects of a physical entity; more preferably, the storing means is arranged to store a matrix of binary codes, each representing a combination of said components known to be possible.

Certain embodiments of the present invention will now be described with reference to the accompanying drawings in which:

Figure 1 is the general concept of a signal processing process according to the present invention;

<img file="PT93050B_D0005.tif" />

Figure 2, three possible types of knowledge representation;

Figure 3 is a block diagram of the signal processing apparatus according to the present invention;

Fig. 3a is the main data stream of the apparatus shown in Fig. 3 in the form of a flow chart;

Fig. 3b shows the operation of the rule base scanning unit of Fig. 3 in flow chart form;

Fig. 3c shows the operation of the rule lookup unit shown in Fig. 3 in flow chart form;

Figure 3d shows the operation of the rule determination unit in the form of a flow chart;

Figure 4, in more detail, is the rule consultation unit of Figure 3;

Figure 5 shows the contents of the recorders in the apparatus of Figures 3 and 4;

Figure 6 is the structure of the rule base of the apparatus of Figures 3 and 4;

Figure 7, the processing of an individual rule;

Fig. 8 is a flow chart of the phases performed in the Fig. 4 query unit;

- 5 'άνβΙ ^' Ά -'- w- * »

<img file="PT93050B_D0006.tif" />

Figure 9, the logical process for identifying rules to visit by performing by the rule base exploration unit of Figure 5;

Figure 10 is the same process as Figure 9 in a second iteration;

Figure 11 shows the results of querying the rules in Figures 9 and 10;

Figure 12 is a rule lookup process using a representation of rules as arrays;

Figure 13, the inference machine of Figure 3, enlarged with a rule determining unit and other recorders;

Figure 14, derived rule determination processes;

Figure 15, the process of demonstrating theorems; and

Figure 16, the abduction process.

Referring first to Figure 1, the signal processing apparatus is arranged to receive an input signal, called an input state vector (SV), and to convert it to an output signal the output state vector, application of information contained in a rule base. 0 Input state vector may contain information at some of the positions (si) and (sN) about known aspects of a physical entity, for example sensor states, but generally other components of the input state vector will be unknown. The apparatus and process function for oh

’^T'* T7r'vr **&gt; 7 *. ? .W .l »'. B

<img file="PT93050B_D0007.tif" />

Signal processing is to determine some or all unknown unknowns when the rule base allows it. The output state vector is said to be the conjugation of the input state vector and the rule base.

In the present system, the possible values ​​stored in the state vector each have four possible two-bit forms, which have the following meanings:

true false tautology (undefined or no matter) contradiction

Figure 2 shows three possible ways of representing a digital form a propositional relationship between three aspects of a physical system. Here is the following rule by way of example:

If the system is in standby or no disc is present, then the turntable is not rotating.

The figure shows three binary state variables RESERVE, DISC, and ROTATE. Note that this rule says nothing about certain variable combinations, thus allowing the turntable to not be rotated if a disk is present but the system is not in reserve. Figure 2a represents a matrix representation of this rule, in which each of the 8 bits in the boxes is associated with one of the 8 combinations of the three variables and indicates whether or not such a combination is permissible. This form of representation has the drawbacks that more information is stored than necessary and that the matrix can become very large and difficult to address when

<img file="PT93050B_D0008.tif" />

number of variables become large.

Figure 2b represents the rule in the form of positive indices, in which only the permitted combinations are listed. Figure 2c shows the negative index form, which lists the disallowed combinations.

Referring now to Figure 3, the main components of the signal processing apparatus, also known as the inference machine, are shown. The apparatus comprises a rule base memory (2), which is a memory in which the rules are stored, preferably in the form of positive indices. It should be noted that the rules (the columns in the figure) will not all have the same dimension, depending on the number of legal combinations in each rule. This is indicated by the different suffixes C, J, D and S. In addition, the device includes a memory (1) of the position structure (PS) which indicates the relationship between the rules and the variables, ie which rules involve what variables. For example, a binary 1 will be stored at position Bij if the variable Vj is implied in the Ri rule. Information measured from the environment is stored in the input vector register (10) and the apparatus includes a rule lookup unit (5) which operates on the contents of this register using the information contained in the memory (1) of the structure of the data. propositions and in the memory of the rule base (2) to provide new values ​​in the state vector register (10), with all new information deduced. During this process, a list is kept in the explanation vector (7) of the rule numbers leading to the new information, and if a contradiction is found, the number of the contradicting rule is stored in the register (6) of the number of the rules. rules of contradiction. The rules that are queried are determined on the basis of information in the memory (1) of the structure of the propositions by a rule base exploration unit (3), a rule list register (4) and registered8.

<img file="PT93050B_D0009.tif" />

variable control and rule control (8) and (9), as will be described in more detail below.

main data stream in the apparatus is illustrated in the flow chart of figure 3a. A summary written in the APL language is provided for each flowchart block next to the flowchart blocks of Figure 3a.

Before proceeding with a more detailed description of the apparatus, the information processing (inference) procedure will be explained with reference to a very simple case of just one rule. Suppose, for example, that the rule is:

If A or not B, then not C.

This rule is transformed to the positive index form:

ABC 0 0 0 0 10 0 11 10 0 110

Suppose input state A is true; B and G are unknown ”is measured from the environment. Thus we have the input state vector:

A 0 1

Β 1 1

C 1 1

The rule lookup unit is efficient for identifying all rows of the rule matrix that satisfy the input state vector limitations. In this example are just the last two lines. Each sub-matrix column that contains only the rows identified

<img file="PT93050B_D0010.tif" />

is then tested: if a column contains all 1, the corresponding state variable is limited to true; if all values ​​in the column are 0, the state variable is limited to false; and if either 0 or 1 appear the state variable is undefined (tautology). So we have the following exit state vector, after the query:

with the following interpretation: A is true and C is false; B is unknown.

Turning now to a more detailed description of the preferred embodiment, let us first discuss the memory of the rule base (2) and the memory (1) of the structure of propositions. A precondition for providing simple inference processes is an unambiguous and compact representation of knowledge. In conventional systems, both well-known knowledge elements, namely rules and facts, are stored in the same knowledge base. In the present invention a clear distinction is made between rules and facts: propositional rules or functions are stored in the memory of rule base (2) and facts are stored in the state vector register (10). Simple expressions and simple propositions such as A and B, A or not A (tautology) and A and not A (contradiction or inconsistency) are considered as facts and not as rules.

In a practical system, an operator interface (known as a compiler) must be provided for converting rules expressed by an operator into logical relations to the binary form (preferably in positive index form) used in the base memory.

<img file="PT93050B_D0011.tif" />

rules. The compiler can also check for redundancy in input information and inconsistency with previous rules. The former can be performed with the theorem demonstration technique described below, and the latter with the derived rules technique. With current technology the positive index form is most appropriate due to the high query speed of the rules, but other forms may be used if preferred.

In rule base memory (2) each legal bit combination in a rule is stored in an addressable memory location, for example in a 16-bit word. As mentioned above, rules can have different dimensions; thus, the first rule may occupy C words and the second J words. The order of individual legal combinations in a rule has no importance to the operation of the present invention. However, the order of state variables is important because of the addressing mechanism used, as will be described. Variables in any rule are sorted according to a common scheme, hereinafter referred to as an ordered set or domain. This makes it possible to do very simple addressing of rules and variables.

As mentioned, the memory (1) of proposition structures indicates the binary relationship between rules and variables. Bij is 1 if the variable j is in i; otherwise 0. We can consider the contents of proposition structure memory (or PS memory) as fundamental addressing information, which is used to determine which rules to visit. In fig.

A simple example is given that illustrates the contents of rule base memory (2) and PS memory (1). This example refers to the following two rules:

Rule 1: If the system is in active standby, or no disk is present, then the

<img file="PT93050B_D0012.tif" />

Turntable plate is not rotating.

Rule 2: The sound pickup is on if and only if the turntable is rotating.

You choose an order for the variables to be applied system-wide, for example the alphabetical order. Rules are transformed to positive index form (legal combinations), with variables ordered according to a predefined scheme or domain.

Binary patterns are stored in rule base memory (2). The structure of corresponding propositions is stored in memory PS (1). This clearly indicates that rule 1 involves ACTIVE RESERVE, DISC TO ROTATE, and rule 2 involves SOUND PICKUP and ROTATE. The variables within the rule words are sorted according to the common domain, so the information in PS memory indicates which variable the rule word bits represent. The operation of the rule base scanning unit (3) is illustrated in the flow chart of Figure 3b (respective APL code is also provided).

Alternatively, the information stored in PS memory may be represented in one of the following index forms:

1) All variable indices associated with a rule represented as an integer vector.

2) All rule indexes associated with a variable represented as an integer vector.

Thus, the alternative representations of the PS information in figure 6 are:

<img file="PT93050B_D0013.tif" />

1) Rule 1: 154 Rule 2: 2 5 .or

2) Var 1: 1 Var 2: 2 Var 5:12 Var 4: 1

The rule query unit 5 will now be explained in more detail by first referring to the processing of a single simple rule. The operation of the consultation unit 5 is illustrated in fig. 5c, in flowchart form. Figure 7 represents the simple rule. If the system is in active standby or no disc is present, then the turntable is not rotating.

input state measured from the environment is considered to be the active standby system which gives the input status vector SV. A. The rule lookup unit identifies lines in the rule matrix that satisfy the state vector limitation, that is, the soaked areas. As noted above, all columns in the overlaid subarray are tested and it is deduced that any column containing s 1 or only 0 has the limited true or false value, respectively. Thus, the output state vector represented is determined, with interpretation when the system is in active reserve, the turntable is not rotating; It is not known whether or not it is present on disk.

In this process, the input state vector can be said to be in conjunction with the rule and that the set projected on any axis determines the corresponding output state vector. If the rule is represented in the form of positive indices, this process can be performed in practice with very simple binary pattern recognition that is easy to perform with

<img file="PT93050B_D0014.tif" />

physical circuits. Referring to FIGS. 4 and 8, in the status vector register (10) a global state vector is retained and local state registers (SV (1) and SV (2) are used in the query rules, which are in compliance with This is the least significant bit and the most significant bit of the state vector. In order to optimize execution speed, the state vector input limitations are stored in two other TV registers (true variable registers) and BV (limited variable registers, ie known to be true or false). . The initialization unit (5.1) determines the address of the rules and the local input state vector by means of a global state vector (10) and memory (1) of proposition structures. Initially, registers of local status vectors are reset to zero. Thus, in the present example, the initial values ​​of local registers are:

SV (1) = ... 000

SV (2) = ... 000

TV = ... 001

BV = ... 001

The steps in figure 8 are performed in the exploration and projection unit (5.2) for a N word rule (W1, W2) ...., WN). In step (8.1), set ε zero a temporary counter ie in step) 8.2) load the current word. In step (8.3) the current word is determined to satisfy the state vector limitations and, if not, the next word is loaded through steps (8.4) and (8.5). If satisfied, the word is further tested by steps 8.6 and 8.7 which, in effect, combine with an OR operation the respective bits of the rule word with the corresponding upper bits of the local state vector and combination with a operation OR the complement of the rule word with the lower bits of the local state vector. It should be noted that steps (8.6) and (8.7) can be performed in any order, being fs

<img file="PT93050B_D0015.tif" />

You can perform these operations in parallel to increase the speed. The process ends when all the words have been tested as indicated by step (8.5).

In this example, the result of this process will be:

SV (1) = 110 SV (2) = 101 with the following interpretation

SV (1) SV (2)

DISC 1 0

ROADING 1 0

Active booking 0 1 (tautology) (false) (true)

The control and explain variable (5.3) updates the global state vector and the global control and explain registers according to the local output state vector (SV (1) and SV (2) registers). Global Status (10) is updated from the individual local subregisters (SV (1) and SV (2).) The addresses of the variables are read from the PS memory. If the output state vector is found to be in contradiction, the CRN register 6 is updated with the index or analogous addressing information of the contradiction rule and then the state search is interrupted.

explanation vector EV (7) is updated if one or more variables are deduced during query rules. In the above example, it was deduced that ROTATE is false. Therefore, the index of the rule or analogous addressing information is placed in the EV RODAR element A RODAR. The index is read from the PS memory.

<img file="PT93050B_D0016.tif" />

Similarly, the VC variable control register (8) is updated if one or more variables are deduced while querying the rules. Again, in the above example a solid 1 is placed in the ROTATE element of (VC). Note that only newly demarcated variables are identified in the register (VC) for rule control, as will be described later. 0 rule control vector (RC) (9) is updated if the number of tautologies in the local output state vector is 0 or 1. A logical 0 is then placed in the RC index of the current rule, which has the effect of the rule will not be checked again.

At the end of the rules lookup, the inferred information is available for all other rules and the outside environment.

In some circumstances, for example in a denominator state event control system, it may be desirable to make only a rule base query, so that only the consequences are determined at one level of the current input. However, many applications will require the determination of the maximum amount of additional information, in which case further rule base queries (rule feedback) are required.

Therefore, another important aspect, in the case of state event control, is the distinction between input (independent) and output (dependent) variables. A very simple extension of the rule consultation technique mentioned above makes it possible to use the inference machine as a state event controller as well as a deduction machine. We can consider the rules of state events as dynamic rules, which map the system states into a new state, and the normal propositional functions as static rules, which represent a state space.

<img file="PT93050B_D0017.tif" />

static

Each of the rules is supplemented with an input / output preamble that describes which variables are input and output (respectively 1 and 0 logical).

Consider for example the rule:

(A or B) = C. If we choose A and B as input variables, we take the following internal binary representation:

ABC

<td> 1/0</td><td> 1</td><td> 1</td><td> 0</td>

<td>RW1</td><td> 0</td><td> 0</td><td> 0</td>

<td>RW2</td><td> 0</td><td> 1</td><td> 1</td>

<td>RW3</td><td> 1</td><td> 0</td><td> 1</td>

<td>RW4</td><td> 1</td><td> 1</td><td> 1</td>

The rule words (RW1 ... RW4) are in the form of normal positive indices. In this embodiment, A and B are independently} and each combination of A and B is associated with an output value.

When the rule is consulted, the register (BV) is assigned the value of the combination of the preamble l / θ and the current BV value:

BV = 1/0 and BV

In the case of a rule without any distinction between input and output (a normal static rule) all variables are treated as input.

If the rule is dynamic, the RC register is not updated after the rules are queried. In this case, the search for an equilibrium may imply several queries of the same rule.

<img file="PT93050B_D0018.tif" />

In this embodiment, mixing static and dynamic rules on the same basis is not allowed.

The overall operation of the inference machine will now be described with particular emphasis on dealing with various rules. The combination of a single rule and the corresponding state vector variables has just been described, this is done repeatedly in the rule lookup unit (5). However, in a rule base with more than one rule, that rule base has to be explored to identify rules to query. Any rule that may deduce new information is a candidate and must be visited. The inference machine independent search module is the rule base scanning network (3), which generates the candidate rule numbers stored in the rule list register RL (4). The criteria for visiting the rules is that at least one of the axes must be limited to truth or falsehood, that is, the rule surrounds a variable in the input vector that is determined, and the current local state vector was not previously one. input state vector of the same rule. All candidate rules with a common axis can be executed in parallel. When candidates are consulted, a new search (the rule control feedback in Figure 3) must be searched to find a new RL set of candidate rules.

The state vector transformation ends when a minimum of tautologies (or a minimum of uncertainty in the signal represented by SV) has been reached; that is, when the RL candidate rule list is empty, or when a contradiction is identified during the consultation. In the example of figure 6, with the input information the system is in active reserve the contents of the status vector are

<img file="PT93050B_D0019.tif" />

1

1

Ο 1

The contents of the rule control register will be

RC = 1 1

A logic in the rule control register means that the corresponding rule must be searched. A 0 makes it possible to abandon the rule as a candidate rule. In the present case, both rules are accepted to be visited. The variable control register has the following values:

CV = 0 0 0 1.

Here a logical 1 means that the corresponding variable is identified as having been limited since the last state search. In case of omission all limited variables in the input state vector are identified with a 1.

A list of candidate rules is determined by unit (3) using information from VC, RC and PS memory, as shown in Figure 9. The mathematical expression is: RL ^ = RC_i and (or (VC and PS)). In other words, the control word of the variables is combined by a relation E with each line separately from PS and then combined by a relation OR the results to determine in which rules the bound variables in VC occur, as if indicates in the first line of figure 9. The result is conjugated with RC, element by element, as illustrated in the second line of figure 9. 0 RC rule control register can be accessible to the user, so that the user can exalt search rules.

<img file="PT93050B_D0020.tif" />

All rules identified in the RL register of the rule lists are consulted. In this case, only the first rule is a candidate. As illustrated above, the result of the query is a deduction that A ROTATE is false. This information may imply new deductions in other rules. Therefore, set variable A ROTATE to 1 ”in the VC register;

CV = 0 0 1 0.

The explanation vector EV (7) is also updated. The third variable was deduced in rule 1, so the integer value 1 is stored in the third position of EV:

EV = 0 0 1 0

If the query for the rules had led to a contradiction, the CRN register (6) would be updated with the current rule number and would end the search.

No further information can be deduced from the current rule because two of the three axes are limited. A zero is therefore placed in the RC rule control register to prevent further visits to this rule:

RC = 0 1

The rule base exploit unit is now re-enabled to roll back rule control and to determine a new rule list.

This process is shown in Fig. 10 and is similar to Fig. 9. The VC register is initialized to zero.

Rule 2 is the only rule to look up in the list and is queried in a process similar to that described above with reference to figure 7. The result is represented in figure 11. In the state vector variables here (and in figure 16, below) values ​​0 and 1 are used for abbreviation

<img file="PT93050B_D0021.tif" />

represent false and true. All variables in rule 2 are now limited and thus RC is updated with a zero.

RC = 0 0

In rule 2 the variable SOUND COLLECTOR is deduced and thus the EV vector is updated:

EV = 0 2 1 0

The rule control feedback is checked again to reactivate the rule base exploration unit, but this time the RC rule control vector is zero and the rule list is zero, thus ending the deduction.

Of course, in a more complex case more than one variable may be deduced in a query of the rules.

The positive index form of rule representation has been described above in particular. However, the matrix representation can also be used as shown in Figure 12. Figure 12a shows the same rule used in previous examples with three-dimensional matrices. Again, the example assumes the ACTIVE RESERVE entry as true. 0 The input state vector and rule set is a matrix with the same structure as the rule (Figure 12b) and projection on each axis is performed by the OR (disjunction operation) function. Obviously, the projection on the input limit axes will give an equivalent output. Thus, it is only necessary to project on the non-limited axes (tautology). This is an alternative practical realization of rule consultation; however, it requires a more complicated pattern search and with current technology the positive index form provides the highest query speed.

<img file="PT93050B_D0022.tif" />

<img file="PT93050B_D0023.tif" />

Well-known inference techniques such as resolution, modus ponens or modus tollens can be readily accomplished by transforming the state vector described above. However, more complex or composite inferences, such as derivative rule determination, theorem demonstration, and abduction may be made by the apparatus of the present invention. Figure 13 shows the enlarged inference machine with a rule determination unit (12). Figure 3d illustrates, in the form of a flow chart, a preferred embodiment of the operation of the rule determining unit (12). The input vector VL contains integer values ​​that indicate the variables involved. In the example of Figure 14, the problem is to determine the derived relationship between the SOUND COLLECTOR and ACTIVE RESERVE variables; thus VL = 2 4. The relationship is determined by testing the validity of all combinations of variables. If the CRN (contradiction rule number) output is 0, the combination is valid; otherwise it is invalid. The four possible combinations are shown in Figure 14 and the results are stored in the derived rule register. The ratio can be recognized as a NAND ratio: that is, the active standby system and sound pickup will never appear at the same time. Through CRN, EV and PS it is easy to draw up an explanatory list with all the rules involved in inference;

ERL = 1 1, that is both rules are involved.

Figure 15 illustrates the principle of theorem demonstration, which is based on the derived rule determination technique. The problem is to prove that the predefined rule set implies a user-defined conclusion. In this case, the derived relationship between the variables and the conclusion is compared, element by element, with the binary representation of the conclusion. Given the rule base of Figure 6, the example is to prove

<img file="PT93050B_D0024.tif" />

OR the system is in active standby OR the sound pickup is on. The conclusion to be demonstrated is an OR relationship between SOUND COLLECTOR and ACTIVE RESERVE (Pigura 15a). The derived relationship (Figure 15b) between SOUND COLLECTOR and ACTIVE RESEE VA was demonstrated in the previous example. Theorem C is demonstrated if DR implies C, that is, DR is less than or equal to C for all elements. As can be seen from Figure 15c, the condition is not satisfactory. Therefore the theorem cannot be demonstrated.

Figure 16 illustrates the abduction. Here, the output state vector is known, and the problem is to determine all input state vectors (assumptions) that imply this conclusion. This is accomplished by a primitive deduction (state vector transformation) of the limited output state vector. Figure 16 refers to the same rules as Figure 6, and the output state vector SOUND PICKUP is false is the given vector (Figure 16a). This state vector is negated, deduced and again denied (Figure 16b), giving the conclusion:

No disc, turntable not rotating, or system in active standby means completion The sound pickup is turned off.

Alternatively, the abduction process may be performed without negating the exit state vector. In this case, the end user specifies the known output state vector and a set of input variables. The system deduces all combinations of input variables and compares the result of each deduction with the output state vector. If the determined and specified output state vectors are equal, a corresponding input state is stored. Therefore, the result of this abduction process is the set of input combinations that satisfy the output limitation.

<img file="PT93050B_D0025.tif" />

It will be seen that the present invention, except in its described embodiments, provides the following features and advantages: the knowledge base is represented in a compact binary format, with each rule transformed into a real frame. The size of the rule base is therefore approximately proportional to the number of rules and independent of the number of state variables. Therefore, there is no problem with bursting combinations. During the consultation of rules the size of the knowledge base remains fixed.

Rules can also be consulted in any order and therefore there is a possibility to process rules in parallel, for example in a number of processors, leading to the possibility of an almost unlimited speed increase.

The logical transformation is based on a parallel search for binary patterns. The technique can be performed in virtually any programming language, but is suitable for practical realization with physical parallel processing circuits. Any switching circuit technology, including electrical, mechanical or optical devices, may be a candidate, but of course the most practical presently will be the realization in semiconductor material tablets. The components of the apparatus described, including PS memory (1), rule base memory (2), rule base scanning unit (3) and rule lookup unit (5) can, if desired , can be performed practically on a general purpose computer, and their functions can easily be performed by the program steps shown as an example in figures 3a to 3d.

The logical transformation is performed without changing the rule base, in contrast to the conventional solution, in which time-derived rules are added.

<img file="PT93050B_D0026.tif" />

during the search state. Therefore, the rule base according to the present invention has a fixed dimension during interference, which is important when performing on small-scale computer systems.

The logical transformation is usually performed with fewer rule queries and higher execution speed than conventional inference.

In practice, the logical transformation may be effected as a transformation of a binary state vector that represents spectra of a physical entity. The input state vector represents the measured or known system state and the system may interact directly with physical devices such as transducers that generate the input state vector. The output is of course an updated state vector according to input stimuli (the input state vector) and system limitations (knowledge base).

State vector may include tautology (unintended) and contradiction (inconsistency) as state values ​​that must be treated as truth or falsehood. Therefore, the system can identify and manipulate inconsistent or superfluous knowledge.

All the inference processes performed are based precisely on a fundamental logical transformation. Well-known inference processes such as resolution, modus ponens or modus tollens can be performed without difficulty by this new transformation. Composite or complex inference techniques can also be performed without difficulty, such as determining derived rules or demonstrating theorem but by two or more state vector transformations using parallel or sequential processing.

<img file="PT93050B_D0027.tif" />

This new inference technology makes it possible to introduce artificial intelligence into many important and new application areas, including small microcomputer systems for real-time process control.

In a possible form of the present invention it may be performed on a coprocessor of a microcomputer or other controller, either as a special purpose integrated circuit or as a card adapted to be connected to the computer data address bus. Interface software can be provided between the coprocessor and commonly used programming languages ​​in industrial control, such as PASCAL, APL and C so that programs written in these languages ​​can call information processing routines in the coprocessor.

Although the present invention has been described in connection with variables having two states, it can be used in systems in which variables can take values ​​in a continuous range. In such a system, this range may be divided into relatively small subgams, a value of a variable falling within or not within one of the small subgams being represented in binary form and processed with the described techniques.

In addition, the present invention can be extended to so-called fuzzy logic systems, where each rule state has a certain probability value, recording probability values ​​in association with combinations stored in memory ( 2) the rule base. These values ​​can then be processed during or after processing the state vector and rule base information.