SU1665515A1 - Device for minimizing fibonacci 1-code - Google Patents

Abstract

The invention relates to computing technology and allows increasing the speed of a device. The latter contains a group of 1–4 convolution blocks, elements AND 5, 6, and has groups of information inputs 7 and outputs 8. Each convolution block contains two triggers, two AND elements, an AND element — NOT, and a one-bit adder. In each convolution block, the corresponding element AND checks the fulfillment of the convolution condition. Since convolution can be performed only for two bits, at the same time, in blocks 1-4, convolutions on AND-NOT elements generate signals that prohibit convolution in previous convolution blocks. With the help of elements And 5 and 6 is carried out correction of the lower bit of the source code. The speed of the device is achieved, in addition, through the use of a pipelined conversion method. 1 hp f-ly, 2 ill.

Description

G0 f88 lf87 86 f83 f84 r83 82 81

The invention relates to computing and is intended to bring the 1-Fibonacci code to its minimum form.

The aim of the invention is to increase speed.

FIG. 1 shows a diagram of a device for converting a 1-Fibonacci code to its minimum form (for an 8-bit code); FIG. 2 is a diagram of a convolution block;

The device contains the first group of blocks 1.1-1.8 convolution, the second group of blocks 2.1-2.9 convolution, the third group of blocks 3.1 convolution, the fourth group of blocks 4.1-4.9 convolution, the first 5 and the second 6 elements And, the group of information inputs 7.1-7.8 devices, output group 8.1-8.9 devices.

FIG. 1 group of clock inputs of the device is not shown.

Each convolution block 1 (2-4) (Fig. 2) contains the first 9 and second 10 triggers, the first AND 11 element, the AND-NO 12 element, the second AND 13 element, and the one-bit adder 14.

The device works as follows.

The need to perform a convolution operation on a code image is determined by checking the conformity with the attribute of the minimal form of the source code. Compliance with the minimum form of a 1-Fibonacci code is described by a logical equation

S-U a- L a i - i l 1 7

where ai is the value of the 1st bit of the code obtained by shifting the source code ai by bit to the right. This equation defines an algorithm for sequential control based on a minimum form.

In each block 1-4, the convolutions of groups on the element And 11 checks the fulfillment of the condition of convolution by a logical equation. To do this, in each cycle, the source code and the value of the same code shifted to the right are recorded in triggers 9 and 10, respectively. After the end of the transients at the outputs of the elements And 11 we have the results of checks of the condition of convolution. Since the convolution can be performed only for two bits, for this, simultaneously, in blocks 1-4 of convolution on the AND-NE 12 element, a signal is generated that prohibits convolution in the previous convolution blocks. For example, when convolving a type code 1111 ... as described above, the convolution will be performed for the first and third groups (each group contains two bits) starting with the highest bits, Since the condition

convolution, then at the output of the element AND-NOT 12, the zero signal that goes to the first input of the previous convolution unit is sent to the first input of the element And 13 and

prohibits the execution of convolution. In the older groups of the specified code, convolution is performed, and the transfer signal from the output of adder 14 (in our case from the convolution unit 1.8) goes to the second and fifth

0 inputs respectively blocks 2.9 and 2.8 convolution of the next group. Let us assume that it is necessary to reduce to a minimal form the code 1010101 —the image of the number 21 in 1 Fibonacci code, which is the 5th and the worst case in terms of the time of convolution.

This code in the lower order contains one and therefore does not correspond to the sign of the normal form. According to the first clock signal arriving at the fourth input of the convolution blocks, the source code is entered into the triggers of the 1.1 1.1.8 convolution blocks. In the triggers of 10 convolution blocks, simultaneously shifted to the right are the values of the source code. On elements 11 and 11, the convolution condition is checked. Since the source code does not contain two contiguous single bits, then at the outputs of elements AND 11 of all convolution blocks there is a zero signal, and

0 at the inputs of the elements AND-NOT 1Z-unit, Therefore, convolution is allowed in all blocks of convolution. Since the second bit of the code contains zero, the contents of trigger 10 of block 1.1 are also zero and the unit signal from its inverse output (fourth output of block 1.1 convolution) is fed to the first input of the element 5, to the second input of which the single signal comes from the trigger output 9 blocks 1.1 overflow. At the first input of the one-bit adder 14 there is a zero signal, since the output of the element 11 is a zero signal, and at the second input there is a single signal equal to the value of the low-order bit.

5 of the source code from the output of the trigger 9. On the one-bit adder 14 of the block 1.1, the low-order bit is summed with the unit arriving at the transfer input from the output of the And element 5. After the end

The 0 transients at the outputs of convolution blocks 1 have the first intermediate result 1010110, which is also an image of the number 21 in the 1 Fibonacci code. Thus, in the first cycle, the implementation of 5 is only the low-order correction of the source code.

The second clock signal, this code (1010110), enters into triggers 9 convolution blocks 2 and, similarly, triggers 10 convolution blocks 2. In the second cycle, processes similar to the first cycle occur, with the only difference that in block 2.2 the convolution condition is satisfied, and in the others there is no. Since, in block 2.3, the convolution condition also does not hold, then, according to the above, the single signal from the output of the NAND element 12 of the block 2.3 arrives at the first input of the 2.2 block — at the first input of the AND element

13, The result of checking the convolution condition on the And 11 element of the convolution block 2.2 is fed to the first input of a one-bit adder.

14, to the second input of which the output of the trigger 9 receives the value of the second bit of the intermediate result code. Thus, the convolution in the group of two bits is performed by summing the youngest of them with the result of the convolution for this group of bits. After the termination of the transient processes in the one-bit adders 14, the code of the second intermediate result 1011000 appears at the outputs of the convolution blocks 2, which is also the image of the number 21 in the 1-Fibonacci code.

The third clock signal, this code in the manner described above, enters the triggers 9 and 10 of convolution blocks 3. As can be seen, the convolution will be performed in the convolution block 3.4 corresponding to the fourth bit. Similar to the previous clocks after the end of the transient processes at the outputs of the convolution blocks 3, we have the third intermediate result 1100000, which is also the image of the number 21 in the 1 Fibonacci code.

In the fourth cycle, the processes similar to the first three cycles occur, and after the summation process of 14 convolutions blocks 4 at the outputs of the latter is completed, we have the final result of the 21 number code, represented in the minimum Fibonacci 1 code, i.e. . 10,000,000.

When converting the type code ... 111 to the minimum form in convolution block 1.1, the low-order correction is not performed, because at the fourth output of convolution block 1.1 we have a zero signal from the inverse output of the trigger 10. Therefore, at the output of AND 5 there is a zero signal, arriving at the transfer input of a one-bit adder 14. Since convolution is performed in the two higher bits of the specified code, a zero signal from the first output of the convolution block prohibits convolution in convolution block 1.1. Consequently, the output of the element And 13 of the convolution unit 1.1 also contains a zero signal. Thus, the value of the low-order bit from the output of trigger 10 is transferred to the third output of block 1.1 without change.

convolutions. After performing the convolution, the specified code will look like ... 1001. In the next cycle, the code. ,, 1001 is transferred to 2.4, 2.3, 2.2, and 2.1 convolutions, while in the 2.1 convolution block, the low bit of the code will be corrected with the And 6 element. The device then works as described above until the final result is obtained. .

Thus, in the device, in four (generally in p / 2) cycles, it is possible to simultaneously reduce to the minimum form of n / 2 codes, and the maximum frequency of the data to be converted is limited in the conveyor mode by the time of three transients (in general, p + 2) convolution blocks and does not depend on the size of the code.

Claims (2)

Claim 1. Device for reducing 1-Fibonacci code to the minimum form, containing the first group of convolution blocks, the first output of (i + 1) -ro (l 1-n-1, n - code width) of the convolution block of the first group connected with the first input of the i-ro convolution block of the first group, the group of information inputs of the device is connected to the second inputs of the corresponding convolution blocks of the first group, the second output of the 1st convolution block of the first group is connected to the third input (i + 1) -ro of the convolution block of the first group, the first clock input of the device group is connected to four the first inputs of the convolution blocks of the first group, characterized in that, in order to improve speed, it contains from the second to the n / 2nd group of convolution blocks, the first and second elements AND, and the fifth input of the 1st convolution block of the first group connected to the second input (i + 1) -ro of the convolution block of the first rpyrlIf py, the first output 0 + 1) -ro () of the convolution block of the k-th (k 2-n / 2) group is connected to the first input of the j-ro convolution block the k-th group, the second output of the j-ro convolution block of the k-th group is connected to the third input of the (j + 1) -th convolution block of the k-th group, the third output of the j-ro convolution block (k-1) -H group is connected to wto j-ro convolution block of the k-th group. The third outputs of the convolution blocks of the n / 2 group are the group of outputs of the device, the second to the n / 2-th clock inputs of the group of which are connected to the fourth inputs of the convolution blocks of the corresponding groups, the second the output of the n-th convolution block of the first group is connected to the second input (n + 1) of the convolution block of the second group, the third output (n + 1) of the convolution block of the m-th (m 2-n / 2-1) group is connected with the second input (n + 1) of the convolution block (m + 1) -th group, the fifth input of the j-ro convolution block of the k-th group is connected to the second the input (j + 1) -ro of the k-th group block, the fourth and fifth outputs, the third input of the first convolution unit of the first group are connected respectively to the first and second inputs, to the output of the first element And, the fourth and fifth outputs, the third input of the first the convolution unit of the second group are connected respectively with the first and second inputs, with the output of the second element I, the input of the zero potential of the device is connected to the fifth inputs of the nth convolution unit of the first group and with the fifth input of the (n + 1) -th block convolutions of the k-th group. 2. The device according to claim 1, characterized in that the convolution unit contains the first 1 second triggers, the first and second elements AND, the H-NOT element and the one-bit sum {mator, with the first input of the convolution unit connected to the first input of the second element Jra And, the output of which is connected to the input of the First addend of the one-bit adder, the output of the sum, the transfer output and the transfer input of which are respectively the third output, the second output and the third input of the convolution unit, the second and fifth inputs of which are connected to the information inputs ne pvogo and second flip-flops, recording resolution of which is connected to the fourth input of the convolution unit, the direct output of the second - 10 flip-flop is connected to the first input of the first element And, the output of which is connected to the second input of the second element And, the output of the first trigger And, with the first input of the element 15NAND, with the input of the second term of the one-digit adder, it is the fifth output of the convolution block, the fourth output of which is connected to the inverse output of the second trigger, the direct output of which is 20 n with the second input of the element IS-NOT, the output of which is the first output of the convolution block. FIG. 2