The Fibonacci "convolution" register

As is mentioned above, the operations of the "convolution", the "devolution" and the "reducing to the minimal form" are the main operations of the Fibonacci arithmetic and the devices for their realization were the main topic of Fibonacci patenting abroad. And we consider at this page of our Museum the simplest electronic device for realization of the "convolution".

As the basis of the "convolution" device one can chosen the classical binary register consisting of flip-flops. This register has the special logical circuits for the convolution fulfilment. Each digit of the register contains the binary flip-flop and the logical elements. The "convolution" (011 ® 100) may be presented as the inversion of the flip-flop states. The inversion of the flip-flop state is performed very easily for the flip-flop with the "adjusting" and "counting" inputs.

One of the possible variants of the "convolution" register is shown in Fig. 1. The "convolution" register consists of the five R-S-triggers and the logical elements AND, OR, which are intended for the realization of the "convolution". The "convolution" is performed from the lower flip-flop T1 to the higher flip-flop T5 with the help of the logical elements AND1 - AND5 and the corresponding logical elements OR standing before the R- and S-inputs of the flip-flops. The logical element AND1 realizes the "convolution" of the 1-st digit to the 2-d digit. Its two inputs are connected to the direct output of the flip-flop T1 and the inverse output of the flip-flop T2. The 3-d input is connected with the synchronization input C. The logical element AND1 analyses the states Q1 and Q2 of the flip-flops T1 and T2. If Q1 = 1 and Q2 = 0 this means that the "convolution" condition is fulfilled for the 1-st and the 2-d digits. The synchronization signal C = 1 causes an appearance of the logical 1 at the output of the element AND1. The latter causes the switching of the flip-flops T1 and T2. This results in the digit convolution (01 ® 10).

The logical element ANDk of the k-th digit (k = 2, 3, 4, 5) realizes the "convolution" of the (k - 1)-th and the k-th digits to the (k + 1)-th digit. Its three inputs are connected to the direct outputs of the flip-flops Tk-1 and Tk and the inverse output of the flip-flop Tk+1. The 4-th input is connected to the synchronization input C. The logical element ANDk analyses the states Qk-1, Qk and Qk+1 of the flip-flops Tk-1, Tk and Tk+1. If Qk-1 = 1, Qk = 1 and Qk+1 = 0 it means that the "convolution" condition is fulfilled. The synchronization signal C = 1 results in the switching the flip-flops Tk-1, Tk, and Tk+1. The "convolution" of the corresponding digits (011 ® 100) is over.

Note that of all the elements AND1 - AND5 are connected through the common element ORc to the check output of the convolution register.

The convolution register in Fig. 1 operates in the following way. The input code information is sent to the information inputs 1 - 5 of the convolution register and enters the S-inputs of the flip-flops through the corresponding logical elements OR.

Fibonacci 'convolution' register

Figure 1. Fibonacci "convolution" register.

Let the initial slate of the "convolution" register be the following:

5 4 3 2 1
0 1 0 1 1

It is clear that the convolution condition holds good only for the 1-st, 2-d and 3-d digits. The first synchronization signal C = 1 results in the passage of the convolution register to the following state:

5 4 3 2 1
0 1 1 0 0.

Here the "convolution" condition holds good for the 3-d, 4-s and 5-th digits. The next synchronization signal C = 1 results in the passage of the convolution register to the following state:

5 4 3 2 1
1 0 0 0 0.

The convolution is over.

The "convolution" register plays an important role in the Fibonacci processor as the self-checking device. Let's consider the "convolution" register in Fig.1 since this point of view. The outputs of the logical elements AND1 - AND5 of the convolution register in Fig.1 are connected to the register check output through the common element OR. This output plays an important role as the check output of the "convolution" register.

    It follows from the functioning principle of the convolution register that the logical 1 appears at the check output only for two situations:
  1. The binary code combination written into "convolution" register has not the minimal form. It means that the convolution condition is valid even for the one triple of the neighbouring flip-flops of the "convolution" register. This causes the appearance of the logical 1 at the output of the corresponding element AND. Hence in this case the appearance of the logical 1 at the check output of the convolution register indicates that the convolution process is not over. This means that we have a possibility to indicate the termination of the convolution process by means of observing the check output of the "convolution" register.
  2. The appearance of the constant logical 1 at the check output is the indication of the fault in the convolution register. Hence the convolution register is the natural self-checking device.

It is interesting to emphasize that the circuit in Fig.1 is the unusual circuit. It was recognized as the "pioneer" invention in many countries including U.S.A., Japan, England, Germany, France and Canada.