Parallel processing of information by means of a network of logic without a computer

odamaskin@gmail.com Oleg Damaskin


Parallel processing of information by means of a network of logic without a computer


"the brain is not computer but it works fast"


Statement of the Problem

It does not pretend to offer any specific decisions or specific devices for parallel processing information without a computer. It does not offer specific ideas for artificial intelligence systems. It simply discusses some possible principles of information processing that are linked to the idea of ??providing information of a Boolean formula.

It is assumed that the input information at each time represents the state of binary information elements of an ordered set of these elements in the power of n elements. For ease of understanding, we shall call the set of state elements, ie, "picture", as if it were drawn from ones and zeros in a certain moment of time, we shall call "the frame".

Traditionally, information processing begins with the presentation of "frame" in the form of a sequence of points, ie sequence of binary elements, stretching the "picture" in time, and introducing it into the computer to conduct operations in accordance with laid down in the computer program. It is clear that the parallel operations simultaneously on all points "paintings" in theory should provide faster results. Perhaps even more important aspect of the parallel approach is that such an approach may allow the right to see the "picture" in general, to get a general idea about it, and then proceed to detail. This is especially important when creating complex control machines such as robots. Instead of the traditional approach "from specific to general," you can implement the principle "from general to specific."


The theoretical basis for solving the problems of parallel processing of information is considered before, "Presentation of information by a Boolean formula" ( http://moiidei.com/nauka-estestvennyie/predstavlenie-informatsii-bulevoy-formuloy.html ), where it was shown that the sequence of zeros and ones can be replaced by a Boolean formula in which each letter displays a subset of the main sequence and, in general formula displays a subset formed by the consolidation and the intersection of basic subsets. It is important to note that the operations of intersection and union of subsets can be interpreted as corresponding to the logical operations of conjunction ("and") and disjunction ("or"), indicating that the ability to use logic when processing information.

Breaking into subsets

The introduction of the alphabet


In the "Presentation of information by a Boolean formula," it was shown that for a correct presentation of information by a Boolean formula original set of n elements should be divided into at least m pairs of mutually disjoint subsets, where m is given by n = 2 to the degree m. If for each subset to associate some of the letters, the alphabet of the language of Boolean formulas will consist of 2m letters. Obviously, the larger the number of elements n in the set, the smaller the number of letters in the alphabet is required for the realization of a Boolean formula. For example, for a set of 8 elements are required 6 letters almost as much as the and elements, as for the set of the 1024 elements are required only 20 letters.. The more elements in the set, the more economical the alphabet is. Moreover, the number of letters in the alphabet can be reduced by half, given that the original set is divided into pairs of opposite sets.However, then it will be necessary to introduce in the alphabet special character of opposition or of denial, that lengthens itself a Boolean formula.

Breaking into subsets

Actually one can to break the initial set of m pairs on opposite (mutually disjoint) subsets by many ways depending on the purpose of a particular device which will apply parallel processing of information, but the essence the decomposition is independent from this.
So here would be considered a method that was used in the program to minimize Boolean function ("Practical minimization of Boolean functions" http://moiidei.com/nauka-estestvennyie/prakticheskaya-minimizatsiya-bulevyih-funktsiy.html) because it is relatively easy to implement dynamically (earlier this principle Andrew Plakhov suggested to me http://www.membrana.ru/particle/2121), although to speed up the program it would be better to use a static fragmentation.


This fragmentation will be shown in the example for the set of 8 elements (n = 8). Denote the elements of the letter э. Then the set of elements can be written as


mD = { э1, э2, э3, э4, э5, э6, э7, э8 }


To further decomposition will apply a simple principle.
We will form the first pair of subsets as the first and second half of set D, then each of the resulting subsets are also split into two halves, and from first halves compiled one of the subsets of the second pair, a second subset from the second halves. Next, have each half of the newly obtained subsets is divided into halves and out of quarters we form the new sets, etc. The result will be obtained the following sets


mC = { э1, э2, э3, э4 } mCp = { э5, э6, э7, э8 }


mB = { э1, э2, э5, э6 } mBp = { э3, э4 , э7, э8 }


mA = { э1, э3, э5, э7 } mAp = { э2, э4, э6, э8 }


Obviously, mCp, mBp, mAp respectively denote the sets of opposing subsets of designated mC, mB, mA.

Circuit of the parallel formation of a Boolean formula


In the "Minimization of Boolean Functions applying Equivalence of Sets" ( http://moiidei.com/nauka-estestvennyie/minimizatsiya-bulevyih-funktsiy-po-sovpadeniyu-mnozhestv.html ) and "Practical minimization of Boolean functions" forming a Boolean formula occurs sequentially through the steps. At each step, each set can be seen and chose a set of with the greatest similarities (and in fact, the set with the smallest number of zeros and with the largest number of units). Naturally, such an approach is unacceptable for the parallel processing of information, and no computational operations, in principle, should not be.
Here we propose a fundamentally different approach. Everything should be based only on logical operations. Variant of this approach is seen again at the example of constructing a Boolean formula for the information set of 8 elements. For convenience, review the relevant schemes are constructed for each pair of subsets separately, although the practical implementation of these schemes will be combined. Scheme 1 shows the three separate schemes, but together, not to make three drawings, moreover, it shows that the scheme consists of the same can be said to elementary subcircuits





э1 э2 э3 э4 э5 э6 э7 э8 set ( mD = mC + mCp)
э1 э2 э5 э6 э3 э4 э7 э8 set ( mD = mB + mBp)
э1 э3 э5 э7 э2 э4 э6 э8 set ( mD = mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ and / \ and / \ and / \ and /
\or / \or / \or / \or / switching logic level 1
\ / \ /
\--- and----/ \--- and----/
\---or--- / \---or----/ switching logic level 2
| |
sC(sB,sA) sCp(sBp,sAp) signals
| ------->and<-------no---------|
| | |
| C(A,B) | output letters
| -----no---->and<--------------|
\ | /
\ Сp (Ap,Bp) / output letters
\ ­­­------> and <--------/
\---------->or <--------/ switching logic level 3
| \
sD

Scheme 1

How does work the scheme? The work is illustrated in Table 1 for some typical examples. For example, option 1, when state of at all levels of logic in the position "or" all the signals from the original set of data elements equal to zero and the on output of the circuit not appears at least one letter. This means that the set is "empty", ie There is no element in the state 1 (the Boolean formula - 0). Or, conversely, option 2, when all logic elements are in a state "and" and all the signals are equal to one, it means that the set of "fully occupied" (a Boolean formula - 1). Each of these results obtained instantly, in one step. In one step the same results are obtained if only one element of the information field at 1 (all others 0) or, conversely, is only one element in the state 0 (all others 1) (options 3 and 5), and in some cases and in two or 6 active elements (versions 4 and 6). ВIn some cases, on the first step appears at the output of only one letter (versions 10 and 11), ie the first step is determined only by the first letter of the formula. This character shows that in this subset are concentrated all (version 10) or majority (version 11) of the excited elements. And finally, there are options (8.9), when there is not a single character, or, conversely, are all. In all these cases should proceed to the second step. For this part of the elements is disconnected. As a result, can get the scheme type of Scheme 2, the operation of which is illustrated in Table 2.


Table 1
v logic
e level signals Boolean
r. 3 2 1 sC sCp sB sBp sA sAp letters formula
1 or or or 0 0 0 0 0 0 0 0 final
2 or and and 1 1 1 1 1 1 1 1 final
3 or or or 1 0 1 0 1 0 С,B,A C*B*A final
4 or or or 1 0 1 0 1 1 C,B C*B final
5 or and and 1 0 1 0 1 0 С,B,A C+B+A final
6 or and and 1 0 1 0 1 1 C,B C+B final
7 or and and 0 0 0 0 0 0 0 move to version 8
8 or or and 0 0 0 0 0 0 0 disconnect mCp (Sch.2a) and move to Table 2.
9 или или и 1 1 1 1 1 1 0 disconnect mCp (Sch.2a) and move to Table 2
10 или или или 1 0 1 1 1 1 C C* disconnect mCp(Sch.2a) and move to Table 2
11 или и и 1 0 0 0 0 0 C C+ disconnect mCp(Sch.2b) and move to Table 2


Schemes 2a and 2b are working on exactly the same principle as Scheme 1, but due to the fact that half of the elements from multiple mD is disabled, the options are fewer.

э1 э2 э3 э4 set ( mC )
э1 э2 э3 э4 set ( mB + mBp)
э1 э3 э2 э4 set ( mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ and / \ / \ and / \ /
\or / \or / \or / \ or / switching logic level 1
\ / \ /
\---- or----/ \---- or-----/
| |
sB(A) sBp(Ap) signals
| ------->and<-------no-------------|
| | |
| B(A) | output letters
|----------no------>and<------------|
|
Bp(Ap) output letters




Scheme 2a.


э5 э6 э7 э8 set ( mCp)
э5 э6 э7 э8 set ( mB + mBp)
э5 э7 э6 э8 set ( mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ / \ and / \ / \ and /
\ or / \or / \ or/ \or / switching logic level 1
\ / \ /
\------ or------/ \-----or----/
| |
sB(A) sBp(Ap) signals
| ------->and<-------no----------------|
| | |
| B(A) | output letters
| -----no--------->and<----------------|
|
Bp(Ap) output letters


Scheme 2b.





Table 2


v logic
e level signals Boolean
r. Scheme 1 sB sBp sA sAp letters formula
1 Sch.2a and 1 1 1 1 1 С*1 final
2 Sch.2a and 1 0 1 0 B,A C*(B+A) final
3 Sch.2b and 1 0 1 0 B,A C+BA final
4 Sch.2a and 0 0 0 0 disconnect mBp (Sch.3)and move to Tables 3а и 3b


э1 э2 э3 э4 set ( mC )
э1 э2 set ( mB )
э1 э3 э2 э4 set ( mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ and / \ or / \ and / \ or /
\or / \ / \or / \ / switching logic level 1
\ / \ /
\-----or----/ \------or----/
| |
sA sAp signals
| ------->and<---------no-----------|
| | |
| A | output letters
| -----no------>and<----------------|
|
Ap output letters


Scheme 3.


Table 3a


v logic
e level signals Boolean
r. 1 sA sAp letters formula
1 and 1 0 A С*(B*A+Bp*Ap) final
2 and 1 0 A C*B*A+Cp*Bp*Ap final

Table 3b

v logic
e level signals Boolean
r. 1 sA sAp letters formula
1 and 1 0 A С*(B+A)(Bp+Ap) final
2 and 1 0 A (C+B+A)(Cp+Bp+Ap) final


Control for scheme


In the formation process of Boolean formulas to represent the information is occur specific transformation of scheme, the on output of which appear, in the end, the Boolean formula in the form of a sequence of letters. Actually, for process control are apply two types of signals: switching logic and disabling the input elements.

Switching logic


The scheme provides for n levels of logic, ie number of levels equal to the number of pairs of opposite subsets, in fact is used by one level less, and the formal number of different combinations of logic states can be equal to 2n-1. I say officially, because I have not been carefully studied this question, but in fact, as seen from the above example, the number of steps and, consequently, the number of switching logic depends on the specific problem, the specific structure of the transformed set of information elements. It is not excluded that it is possible to construct a circuit without switching logic, if you just build a separate circuit with logic elements, "or" and a separate circuit with logic elements "and".


As logic switches


Switching logic is to translate all the logical elements of a given level from one state to another, ie of status "or" c "and" or vice versa. This switching is carried out by teams from the clock generator (and hence must be a clock generator) , flow and sequence of which, in turn, be controlled from the output of the main scheme in accordance with the results at each step and specific to that particular device for processing information. The first step on the first tact, usually can be the installation of logic elements at all levels in status "or" although, for example, you can start (a very powerful sets with many thousands of elements) with "and" on the first levels (artificial decrease in sensitivity, "visual acuity"). Termination of the work should be done when a signal about getting formula is, it is not necessary that the formula is built to the end, it is possible that for the solution of some problems enough only part of the formula. Go to the next steps, respectively, is carried out when the formula is ready.

Disconnection elements


Disabling the elements implemented on the same principles as the switching logic and for disconnection are used scheme, similar schemes for formation information (see dawn).


Processing of information presented by the Boolean formula

What does the presentation of information by a Boolean formula

Speaking informally, the information submitted this on the language of a much higher level than binary encoding, with relevant consequences. Each letter of the language, not to mention every word carries a lot of information. One can confirm this assertion on the easiest example, the fields of information of m black and white dots of rectangular shape. ЭThis field can be divided into n = 2 in the degree m pairs mutually disjoint subsets, each of which matched as the future character (the letter) of a Boolean formula. A break on the set of pairs can be like this. The left and right halves, top and bottom, center and periphery . Then the first letter of the same formula indicates which part of the field contains most of the black, for example, points, and, perhaps, in some control systems that may be enough to make a decision. The evolution of the Boolean formula, respectively, and specifies the conditions for a decision.

From a formal point of view presentation of information by Boolean formula makes it possible to apply Boolean formula for the information processing through the aid of well-known apparatus of Boolean algebra in at least two areas. To process the information itself - in accordance with the theory of sets, while the use of control information - in accordance with the algebra of logic. In fact. For example, the operation of the disjunction of two formulas will unite the information presented by each formula, while shortening the total formula, and operation of the conjunction will highlight the specific information required by the intersection of the sets of and, in particular, to restore to this fragment the entire formula, ie all the information. Moreover, these operations can be implemented by not computer methods, but logic by circuits similar to those used above .

However, in real devices, a Boolean formula, which carries the information may be submitted not letters of the alphabet, but all the same to the same binary code that will allow process the information by logical means. It is also clear that the length of the encoded formula(word) is rather important parameter in terms of reducing the amount of memory of storage devices. On what does the length of the encoded formula? Well, first of all, the length of the formula. I have developed a method of minimizing Boolean formula is exactly the formula provides minimality. First of all, we note that in this method, the length of the formula depends on the nature of the information,the nature of the "image", is the location of zeros and ones on the set. A length is always different. It may be just one letter or formula may consist of a maximum number of characters is based on the number of sensors and the complexity of information, note. For example, for data sets of 8 elements the maximum length of the formula is 6 letters (not counting the other characters). Perhaps a professional mathematician can determine the maximum number of characters in the formula in the general case for any number of elements in the set.


The second factor - the length of the code letters, which depends primarily on the number of letters in the alphabet. The number of letters, in turn, depends on the number of pairs of subsets into which is divided the entire field of information, ie in fact from the size of the field. For example, an alphabet of about 64 characters of information provides a 2 to the power of 64 bits. This is quite a lot (as shown in the famous parable about the number of grains on a chess board) for some of the technical project in the field of cybernetics, and this example shows that the number of bits per letter grows much slower than the increase in the amount of information. Thus, for the amount of information 2 to the power 3 = 8 bits per letter requires 3 bits of information for 2 to the 64 bits requires 8 bits, ie only on 5 bits more . True, in fact, and in either case in the alphabet it must be added of some of the signs for set operations, which will increase the length of the code letters for a bit, which leads to redundancy, which in principle can be used for certain reductions in the most formula, as shown below.


It was noted above that the proposed method of presentation provides a minimal formula in terms of Boolean algebra.It was also noted that, on the other hand, the presentation of information by the formulas of Boolean algebra can be regarded as a language of a higher level than binary coding. Like other languages, it has its own, we can say, linguistic laws, it is determined to transform the binary information in the words of this language. This issue deserves a separate study, but a few examples worth considering now. For example, the formulas in Tables 3a and 3b were obtained in only three steps, because for the first two steps, it was determined that the location of zeros and ones in the opposite symmetric subsets, and therefore for the final construction of the formula was sufficient to determine the location of zeros and ones in only one of subsets. This property of symmetry can also be used to reduce the formula by introducing a special character "sim" (coded as one letter). Then, for example, the formula C * B * A + Cp * Bp * Ap can be written as C * B * A + sim. In short, we can find a lot of opportunities to reduce the formula by some recurring combinations of letters in formulas.

But, in my opinion, more important is the semantic essence of the proposed method for reducing formula. In particular, the formula for this method is constructed gradually from a more general picture of a more private details, and, in many cases does not necessarily bring the construction of the formula to the end. You do not need to look for a house on a street, if you are not in that city.

Storage and data compression
Memorizing information is one of the stages of information processing. Presentation of information by a Boolean formula allows you to compress a information and hence reduce the amount of memory in the device. In the beginning we talked about the "frame" and "picture". Under the frame refers to the amount of information that can be obtained with parallel processing of information on a given set of information elements. The more elements, the more information. But by repeatedly applying this set of elements can be obtained much more information and to form is all the "big picture". When the binary representation of the information actually remembered every "frame", although, of course, and the binary representation, there are methods of compression, but not common, but with respect to a given specific information. Data compression capabilities can be illustrated by a simple example. We assume in our case there are two 8-cell frame, ie overall "picture" consists of 16 elements, and then you have to count the total number of letters in the total number of elements, ie, out of 16. This means that to the set D must be added the set Dp, and any of the formulas derived above should include the letter D. For example, the CBA formula can be written as


DCBA (1)


(the sign of the conjunction "*" is omitted), and it is this formula displays the first frame. And on the set Dp (second frame) has received information in the form of the formula


DpC(B+A) (2)


Then the total information will be obtained from the disjunction of these two formulas, ie

DCBA+DpC(B+A) (3)

This formula consists of 8 letters (Dp - this is a letter opposing the letter D). However, this formula can be reduced by the rules of Boolean algebra and present, such as

C(B(A+Dp)+DpA), (4) which consists of 6 letters. I do not know how to implement the reduction of the formula so as to guarantee its minimum after the reduction, although the idea of ​​such a reduction, I have. In any case, it may be that this will be a complex process and to reduce the formula will need quite a long time. Perhaps it would be advisable to divide memory into two parts: the operational, storage formula without abbreviations and main which will be to memorize the reduced formula.


Replicating


Replicating "frame" as disabling elements, can be done about the same principle as the formation of the formula. To replicating, a network is built like in the opposite direction compared to the net to get the formula. We show that network as an example of the formula C (B + A). In this relatively simple case replicating proceeds as follows.

э1 э2 э3 э4 э5 э6 э7 э8 sets ( mD = mC + mCp)
э1 э2 э5 э6 э3 э4 э7 э8 sets ( mD = mB + mBp)
э1 э3 э5 э7 э2 э4 э6 э8 sets ( mD = mA + mAp)
| | | | | | | |
o o o o o o o o switching on 0 or 1
\ / \ / \ / \ /
\ / \ / \ / \ /
\ / \ /
\ / \ /
\__________/ \_________/
| |
sC(sB,sA) sCp(sBp,sAp) input signals
| ------------------------------|
| | |
| C (A,B) | input letters
| ------------------------------|
|
Сp (Ap,Bp) input letters



Scheme 4.

This scheme differs from Scheme 1 not only the direction of signals but also the lack of logic elements. In Scheme 1 the logical elements are needed to determine the form of a Boolean formula (conjunctive or disjunctive ).In Scheme 4 it not required, as here, on the contrary, the type of formula is already known, and accordingly the type of formula determines the state of elements (which elements of more units or zeros) and this is done, including through switching elements to 0 or 1 . In general, the procedure is about the same as in the construction of the formula, the set of replicable elements constructed in steps. Therefore, after the elements have to be excited for a while. Replicating "pictures" can be carried out by "cadres" or on row, or in any order. For this we need to implement the conjunction of the formulas for the entire picture with a formula designating a particular frame. For example, to get the first shot for "paintings" by the formula C (B (A + Dp) + DpA), must reproduce the formula DC (B (A + Dp) + DpA), and for the second shot must reproduce the formula
DpC (B (A + Dp) + DpA).