Basic micro-operations

Problem of noise-tolerant computations. As is known the computer program is performed by using the processor. The processor consists of flip-flops (triggers) connected to combinative logic. In this case the performance of the program is reduced to the flip-flop switching. Unfortunately it is impossible to eliminate the computer errors resulting from fault work of the computer elements. Nevertheless it is necessary to differ two types of the fault work of the computer elements. The first type is so-called "constant failure" of the element when the latter "falls outside the order" constantly. The second type is so-called "alternate failure" of the element when the latter "fall outside the order" temporarily, i.e. in the accidental time moments, while in some other moments element work correctly. The latter type of the failures is called the "malfunction". The "malfunctions" of the processor arise because of the influence of different factors evoked by internal and external noises in the computer elements and their electrical circuits. It was proved experimentally that the "malfunction" intensity of the elements in the switching regime is bigger in two or three exponents of the "malfunction" intensity of the elements being in the stable states. It follows from here that the flip-flop "malfunctions" in the switching regime is the most probable reason of the unreliable functioning of the processor. That is why the design of the self-checking digit automatons guaranteeing the effective checking of the flip-flop "malfunctions" is one of the most important problems of the higher-reliable computer design.

The basic idea of the self-checking processor design consists of the following. It is necessary to choose such a set of the micro-operations called the basic micro-operations and to introduce the effective system of the basic micro-operations hardware checking.

    Let's show a possibility of realization of this idea on the basis of the Fibonacci and "golden" codes. With this in mind let's consider fours basic Fibonacci micro-operations namely:
  1. convolution;
  2. devolution;
  3. replacement;
  4. absorption.

The first two micro-operations were considered above. The convolution and devolution are the following code transformations fulfilled over the next three digits in framework of the same Fibonacci code combination.

Convolution:
0 1 1 ® 1 0 0
Devolution:
1 0 0 ® 0 1 1.

The micro-operation of "replacement"

is the two-placed micro-operation performed over the same digit of two registers, the top register of A and the lower register of B. If the register A has the binary numeral of 1 in the k-th digit and the register of B has the binary numeral of 0 in the same digit then for this condition we can perform the micro-operation of the "replacement". It means that we shift the above-considered numeral of 1 of the top register A to the lower register B.

The micro-operation of the "absorption"

is also the two-placed micro-operation when the binary 1's of the k-th digit of two registers A and B are annihilated mutually, i.e. replaced by the binary 0's.

It is necessary to attract attention to the following "technical" peculiarity of the above-considered basic micro-operations. For the register interpretation of these micro-operations each micro-operation may be performed by means of the inversion of the flip-flops involved in the micro-operation. It means that each micro-operation is reduced to the flip-flop switching.

Logical operations. Let's show a possibility to fulfill the basic logical operations by using these four basic micro-operations.

Let's consider two binary combinations, which are in the registers of A and B. Now let's make up all the possible "replacements" from the top register A to the lower register B:

As the result of the "replacements" we get two new code combination A' and B'. We can see that the former one is the "conjunction" of the code combinations A and B (A' = A Ù B) and the latter one is the "disjunction" of the code combinations A and B (B' = A Ú B). Hence, we can use the micro-operation of the "replacement" for fulfillment of the "conjunction" (Ù) and the "disjunction" (Ú).

The logical operation of "module 2 addition" is fulfilled by using micro-operations of the "replacement" and the "absorption". For example:

In the above example we have fulfilled simultaneously all the possible micro-operations of the "replacement" and the "absorption" over the code combinations of A and B. As the result of such code transformation we got two new code combinations A' = "const 0" and B' = A Å B.

The logical operation of the "code A inversion" is reduced to fulfillment of the micro-operation of the "absorption" over the initial code combination A and the code combination B = "const 1":

As the result we get the code combination B' = `A in the lower register B and the code combination A' = "const 0" in the top register A.

Fibonacci addition. Earlier we showed how to realize the counting and the subtracting the binary 1's by using the micro-operations of the "convolution" and the "devolution". And now we will show how to realize the Fibonacci addition by using the basic micro-operations. The general idea of two Fibonacci representations A and B addition consists of the following. We should move all the binary 1's from the top register A to the lower register B. With this aim in view we use the micro-operations of the "replacement", the "devolution" and the "convolution". The sum is formed in the lower register B.

For example let's summarize the following Fibonacci representations:

A0 = 0 1 0 1 0 0 1 0 0 and B0 = 0 0 1 0 1 0 1 0 0.

The first step of the Fibonacci addition is the "replacement' of all the possible binary 1's from the register A to the register B:

The second step is fulfillment of all the possible "devolutions" in the code combination A1, which is in the register A, and all the possible "convolutions" in the code combination B1, which is in the register B:

A1 = 0 0 0 0 0 0 1 0 0 ® 0 0 0 0 0 0 0 1 1 = A2.
B1 = 0 1 1 1 1 0 1 0 0 ® 1 0 0 1 1 0 1 0 0 = B2.

The third step is the "replacement" of all the possible binary 1's from the register A to the register B:

The addition is over because all the binary 1's moved from the register A to the register B. After reducing the Fibonacci representation B3 to the minimal form we get the following sum B3 = A + B:

B3 = 1 0 0 1 1 0 1 1 1 ® 1 0 1 0 0 1 0 0 1 ® 1 0 1 0 0 1 0 1 0 = A + B.

Thus, the Fibonacci addition is reduced to the sequential fulfillment of the micro-operations of the "replacement" over the code combinations A and B, then the "convolutions" over the Fibonacci representations in the register B and the "devolutions" over the Fibonacci representations in the register A.

Fibonacci subtraction. The general idea of the Fibonacci subtraction of the Fibonacci representation B from the Fibonacci representation A in the "direct" code consists of the following. It is necessary to fulfill all the possible "absorption's" of binary 1's over the Fibonacci representations A and B until one of the Fibonacci representations A or B becomes equal to 0. To realize this idea we sequentially fulfill the mentioned micro-operations of the "absorption" and the "devolutions" over the Fibonacci representations in the registers A and B. The subtraction result is formed always in the register of the number bigger by the absolute value. If the result is formed in the top register A it means that the sign of the subtraction result is "+", in the opposite case the sign is "-".

Let's demonstrate the Fibonacci subtraction by using the following example. It is necessary to subtract the Fibonacci representation B0 = 1 0 1 0 1 0 0 1 0 (the register B) from the Fibonacci representation A0 = 1 0 1 0 0 1 0 0 0 (the register A).

The first step is the "absorption" of all the possible binary 1's over the Fibonacci representations A0 and B0:

The second step is the "devolutions" of the Fibonacci representations A1 and B1:

A1 = 0 0 0 0 0 1 0 0 0 ® 0 0 0 0 0 0 1 1 0 = A2,
B1 = 0 0 0 0 1 0 0 1 0 ® 0 0 0 0 0 1 1 0 1 = B2.

The third step is the "absorption":

The fours step is the "devolution":

A3 = 0 0 0 0 0 0 0 1 0 ® 0 0 0 0 0 0 0 0 1 = A4,
B3 = 0 0 0 0 0 1 0 0 1 ® 0 0 0 0 0 0 1 1 1 = B4.

The fifth step is the "absorption":

The subtraction is over. After reducing the Fibonacci representation B4 to the minimal form we get:

B5 = 0 0 0 0 0 1 0 0 0.

The subtraction result is in the lower register B. It means that the sign of the subtraction result is "-", i.e. the difference

R = (A - B) = - 0 0 0 0 0 1 0 0 0.

Note that the arithmetical operations of the "multiplication" and "division" are reduced to the arithmetical operations of the "addition" and "subtraction". It means that the Fibonacci multiplication and division are reduced to the "basic micro-operations".

And now we would like to comment the Fibonacci arithmetic based on the "basic micro-operations". We have proved that all the above-considered "basic micro-operations" possess "functional completeness", that is all the possible logical and arithmetical operations can be reduced to the "basic micro-operations". And therefore, we can design the Fibonacci processor and computer based on the "basic micro-operations".

But what advantages will have such Fibonacci processor in comparison to the classical computers based on the classical "binary" number system? To answer the question we have to demonstrate the possibility to check errors in processors, which can arise in processor over influence of different internal and external factors. Follow us!