CN115276958B

CN115276958B - Bit reversal shifting method and device, processor and electronic equipment

Info

Publication number: CN115276958B
Application number: CN202210839927.9A
Authority: CN
Inventors: 谭波; 蔡亮
Original assignee: ARM Technology China Co Ltd
Current assignee: ARM Technology China Co Ltd
Priority date: 2022-07-18
Filing date: 2022-07-18
Publication date: 2024-11-19
Anticipated expiration: 2042-07-18
Also published as: CN115276958A

Abstract

The present application relates to the field of computers, and discloses a bit reversal shifting method, device, processor, and electronic device. The method comprises: obtaining data to be processed; generating a shift control signal according to the shift type and the number of shift bits of the data to be processed, and generating a bit reversal control signal according to the number of bits of the data to be processed; performing an XOR operation on the shift control signal and the bit reversal control signal to obtain a bit reversal shifting control signal; inputting the bit reversal shifting control signal and the data to be processed into an inverse butterfly network to obtain a result of bit reversal and circular shifting of the data to be processed; post-processing the result of bit reversal and circular shifting to obtain a result of bit reversal and shifting of the data to be processed. Therefore, the computer can perform bit reversal and shifting operations on the binary number of the data in parallel, thereby improving the computing efficiency.

Description

Bit reversal shifting method and device, processor and electronic equipment

Technical Field

The present application relates to the field of computers, and in particular, to a bit reversal shift method, device, processor, and electronic apparatus.

Background

The operation of bit-inverting and shifting binary numbers of data is a common operation in computers, for example, VBRSR instruction is an operation instruction for bit-inverting and right-shifting binary numbers of one data, and is applied to the fields of cryptography, digital signal processing, image processing, and the like.

At present, a computing unit for implementing operations of bit inversion and shift on binary numbers of data in a computer generally exchanges positions of various numbers in binary numbers to be computed through a circuit such as a replacement circuit to complete the bit inversion operation on the binary numbers, and then shifts the binary numbers after bit inversion through a shift circuit to obtain a final computing result. Thus, the calculation unit is an operation of serially performing bit inversion and shift on binary numbers of data, and the calculation takes a long time.

Disclosure of Invention

In view of this, the embodiments of the present application provide a bit inversion shift method and apparatus, a processor, and an electronic device, where the bit inversion shift control signal is obtained by performing an exclusive-or operation on the shift control signal and the bit inversion control signal, and the bit inversion shift control signal and the data to be processed are input into an inverse butterfly network (Inverse Butterfly Network), so that a bit inversion and cyclic shift result of the data to be processed can be directly obtained, and then the bit inversion and shift result of the processed data can be obtained by post-processing the bit inversion and cyclic shift result, thereby avoiding the operation of serially performing bit inversion and shift on binary numbers of the data by a computer, and further improving the computing efficiency.

In a first aspect, the present application provides a bit-reversal shift method, applied to an electronic device, including:

acquiring data to be processed;

generating a shift control signal according to the shift type and the shift bit number of the data to be processed, and generating a bit reversal control signal according to the bit number of the data to be processed;

performing exclusive OR operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal;

inputting the bit inversion shift control signal and the data to be processed into an inverse butterfly network to obtain a bit inversion and cyclic shift result of the data to be processed;

And carrying out post-processing on the bit inversion and cyclic shift result according to the shift type and the shift bit number to obtain the bit inversion and shift result of the data to be processed.

It can be understood that the bit inversion shift control signal is obtained by performing exclusive or operation on the shift control signal and the bit inversion control signal, and the bit inversion shift control signal and the data to be processed are input into the butterfly network, so that the bit inversion and cyclic shift result of the data to be processed can be directly obtained, the problem that the final calculation result can be obtained by firstly exchanging the positions of all numbers in the binary number to be calculated through circuits such as replacement and the like to finish the bit inversion operation of the binary number, and then shifting the binary number after the bit inversion through the shift circuit is avoided, and the calculation efficiency can be improved.

It is appreciated that in some embodiments of the present application, the shift control signal is a cyclic shift control signal and the bit-reversal shift control signal is a bit-reversal cyclic shift control signal. When the shift direction is left shift or cyclic left shift, the obtained shift control signal is a cyclic left shift control signal, the corresponding bit reversal shift control signal is a bit reversal cyclic left shift control signal, and when the shift direction is right shift or cyclic right shift, the obtained shift control signal is a cyclic right shift control signal, and the corresponding bit reversal shift control signal is a bit reversal cyclic right shift control signal.

It will be appreciated that in some embodiments of the application, the data to be processed is input data.

In one possible implementation manner of the first aspect, the inverse butterfly network includes a K-level network, the binary number of the data to be processed has 2 ^K bits, the shift control signals include K shift control signals corresponding to the K-level network of the inverse butterfly network respectively, the bit number of the shift control signal corresponding to the N-level network of the inverse butterfly network is 2 ^N-1 bits, the bit number of the shift is H bits, and the binary number corresponding to H is M, where K is greater than or equal to N; and

Generating a shift control signal according to the shift type and shift bit number of the data to be processed, including:

Under the condition that the shift type is left shift or cyclic left shift, the first 2 ^N-1 digits of binary numbers after the first signal is cyclic left shift J digits are used as shift control signals corresponding to an N-level network of an inverse butterfly network, wherein the first signal is a binary number with 2 ^N digits, the high 2 ^N-1 digits are 0, the low 2 ^N-1 digits are 1, and J is a decimal number corresponding to the last N digits of M;

when the shift type is right shift or cyclic right shift, the first 2 ^N-1 digits of the binary number after the first signal is cyclic right shift by J digits are used as a shift control signal corresponding to the N-th level network of the butterfly network.

It can be understood that the butterfly network is a novel circuit structure, and the shift control signal corresponding to the butterfly network structure can be more conveniently obtained by circularly shifting the first signal according to the shift type and the shift direction, so as to prepare the subsequent bit inversion and circular shift result obtained through the butterfly network.

It will be appreciated that in some embodiments of the application, the first signal is a particular signal.

It will be appreciated that in some embodiments of the application, the butterfly network comprises a level 3 network.

In one possible implementation manner of the first aspect, the bit inversion control signal includes K bit inversion control signals corresponding to K-stage networks of the butterfly network, and a bit number of the bit inversion control signal corresponding to an N-th stage network of the butterfly network is 2 ^N-1 bits; and

Generating a bit reversal control signal according to the bit number of the data to be processed, comprising:

And setting the second signal as a bit inversion control signal corresponding to an N-level network of the butterfly network, wherein the second signal is a binary number with 2 ^N-1 bits being all 1.

It can be understood that the bit inversion control signal corresponding to the butterfly network can be directly and conveniently obtained through the bit number of the data to be processed, and preparation is made for obtaining the bit inversion and cyclic shift result through the butterfly network.

In one possible implementation manner of the first aspect, the bit inversion shift control signal includes K bit inversion shift control signals corresponding to K-level networks of the butterfly network respectively; and performing exclusive OR operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal, comprising:

And taking the result of exclusive OR operation of the shift control signal and the bit inversion control signal corresponding to the N-stage network of the butterfly network as the bit inversion shift control signal corresponding to the N-stage network of the butterfly network.

It can be understood that the control signal with the functions of bit inversion and cyclic shift for the data to be processed input by the butterfly network can be obtained by performing exclusive or operation on the shift control signal and the bit inversion control signal corresponding to the nth stage network of the butterfly network according to the bits, so that the computer can be prevented from serially performing the operations of bit inversion and shift for the binary number of the data, and the calculation efficiency can be improved.

In one possible implementation manner of the first aspect, the performing post-processing on the bit-inverted and cyclic shift result according to the shift type and the shift bit number includes:

Setting the lower H bit of the result of bit inversion and cyclic shift to zero in the case that the shift type is left shift and the shift bit number is H bit;

setting the high H bit of the result of bit inversion and cyclic shift to zero in the case that the shift type is right shift and the shift bit number is H bit;

when the shift type is a cyclic right shift or a cyclic left shift and the shift bit number is H, the bits of the result of bit inversion and cyclic shift are kept unchanged.

It can be understood that by setting 0 to the high order or low order in the result of bit inversion and cyclic shift according to the shift type and the shift bit number, the result of bit inversion and shift of the data to be processed in the case where the shift type is not cyclic shift can be easily obtained.

In one possible implementation manner of the first aspect, in a case where the shift type is left shift and the shift bit number is H bit, setting a low H bit of a result of bit inversion and cyclic shift to zero includes:

And performing bit AND operation on the bit-inverted and cyclic shift result and the first mask code, wherein the bit number of the first mask code and the bit number of the bit-inverted and cyclic shift result are P, and the low H bit of the first mask code is 0 and the high P-H bit is 1.

It can be understood that, when the shift type is left shift and the shift bit number is H, the bit inversion and shift result can be obtained conveniently by performing the bit and operation on the bit inversion and cyclic shift result and the first mask code, and the operation is easy.

In one possible implementation manner of the first aspect, in a case where the shift type is right shift and the shift bit number is H bit, setting the high H bit of the result of bit inversion and cyclic shift to zero includes:

and performing bit AND operation on the bit-inverted and cyclic shift result and the second mask code, wherein the bit number of the second mask code and the bit number of the bit-inverted and cyclic shift result are Q, and the high H bit and the low Q-H bit of the second mask code are 0.

It can be understood that, when the shift type is right shift and the shift bit number is H, the bit inversion and shift result can be obtained conveniently by performing the bit and operation on the bit inversion and cyclic shift result and the second mask code, and the operation is easy.

In a second aspect, the present application provides a bit-reversal shifting apparatus comprising:

The control signal generation unit is used for generating a shift control signal according to the shift type and the shift bit number of the data to be processed, generating a bit inversion control signal according to the bit number of the data to be processed, and performing exclusive OR operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal;

the butterfly inversion network is used for obtaining the bit inversion and cyclic shift result of the data to be processed according to the bit inversion shift control signal and the data to be processed;

And the post-processing unit is used for carrying out post-processing on the bit inversion and cyclic shift result according to the shift type and the shift bit number to obtain the bit inversion and shift result of the data to be processed.

It can be understood that the bit inversion shifting device provided by the application is a parallel device, can realize various bit inversion and shifting operations of bit data, finishes the bit inversion calculation of the binary number by a circuit such as substitution and the like before, and then finishes the shifting operation of the binary number after the bit inversion by a cyclic shift related circuit, and changes the bit inversion and shifting operation of the binary number by the bit inversion and shift related circuit, so that the calculation time consumption can be reduced, and the running speed of a computer can be increased.

It will be appreciated that in some embodiments of the present application, when the shift direction is left, the resulting shift control signal is a cyclic left shift control signal, the corresponding bit-inverted shift control signal is a bit-inverted cyclic left shift control signal, and when the shift direction is right, the resulting shift control signal is a cyclic right shift control signal, the corresponding bit-inverted shift control signal is a bit-inverted cyclic right shift control signal.

It will be appreciated that in some embodiments of the application, the butterfly network is a butterfly network element.

In one possible implementation manner of the second aspect, the butterfly network includes a K-level network, the binary number of the data to be processed has 2 ^K bits, the shift control signals include K shift control signals corresponding to the K-level network of the butterfly network respectively, the bit number of the shift control signal corresponding to the N-level network of the butterfly network is 2 ^N-1 bits, the bit number of the shift is H bits, and the binary number corresponding to H is M, where K is greater than or equal to N; and

The control signal generation unit generates a shift control signal according to a shift type and a shift number of bits of data to be processed by:

The control signal generating unit circularly shifts left the first 2 ^N-1 bits of the binary number after J bits of the first signal to be used as a shift control signal corresponding to the N-level network of the reverse butterfly network under the condition that the shift type is left shift or circularly left shift, wherein the first signal is a binary number with 2 ^N bits, the high 2 ^N-1 bits of which are 0, the low 2 ^N-1 bits of which are 1, and J is a decimal number corresponding to the last N bits of M;

When the shift type is right shift or cyclic right shift, the control signal generating unit uses the first 2 ^N-1 bits of binary numbers after the first signal is cyclic right shift by J bits as a shift control signal corresponding to the N-th level network of the butterfly network.

In one possible implementation manner of the second aspect, the bit inversion control signal includes K bit inversion control signals corresponding to K-level networks of the butterfly network, and a bit number of the bit inversion control signal corresponding to an N-th level network of the butterfly network is 2 ^N-1 bits; and

The control signal generating unit generates a bit inversion control signal according to the number of bits of the data to be processed by:

The control signal generating unit sets the second signal as a bit inversion control signal corresponding to an N-th level network of the butterfly network, wherein the second signal is a binary number with 2 ^N-1 bits being all 1.

It can be understood that the control signal generating unit can directly and conveniently obtain the bit inversion control signal corresponding to the butterfly network through the bit number of the data to be processed, and prepare for obtaining the bit inversion and cyclic shift result through the butterfly network subsequently.

In one possible implementation manner of the second aspect, the bit inversion shift control signal includes K bit inversion shift control signals corresponding to K-level networks of the butterfly network respectively; and, the control signal generating unit performs exclusive OR operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal by:

The control signal generation unit exclusive-ors the shift control signal corresponding to the nth stage network of the butterfly network and the bit inversion control signal according to the bit, and uses the exclusive-or result as the bit inversion shift control signal corresponding to the nth stage network of the butterfly network.

It can be understood that the control signal generating unit performs exclusive or operation on the shift control signal and the bit inversion control signal corresponding to the nth stage network of the inverse butterfly network according to the bit, so as to obtain a control signal having a bit inversion and cyclic shift function on the data to be processed input by the inverse butterfly network, so that the computer can be prevented from serially performing the bit inversion and shift operation on the binary number of the data, and the calculation efficiency can be improved. The method can be expanded to exclusive-or a plurality of control signals realizing different functions to generate the control signals with the bit inversion and cyclic shift functions, so long as the control signals with the bit inversion and cyclic shift functions are exclusive-or, the control signals with the corresponding bit inversion and cyclic shift functions are generated.

In one possible implementation manner of the second aspect, the shift bit number is H, and the bit number of the result of bit inversion and cyclic shift is Y; and

The post-processing unit performs post-processing on the bit-inverted and cyclic shift result according to the shift type and shift number of bits by:

Under the condition that the shift type is left shift, performing bit and operation on the bit inversion and cyclic shift result and the first mask code to obtain a bit inversion and shift result, wherein the bit number of the first mask code is Y, the low H bit of the first mask code is 0, and the high Y-H is 1;

Under the condition that the shift type is right shift, performing bit and operation on the bit inversion and cyclic shift result and a second mask code to obtain a bit inversion and shift result, wherein the bit number of the second mask code is Y, the high H bit of the second mask code is 0, and the low Y-H bit is 1;

And under the condition that the shift type is circular right shift or circular left shift, performing bit and operation on the bit reversal and circular shift result and the third mask code to obtain a bit reversal and shift result, wherein the bit number of the third mask code is Y, and all the bits of the third mask code are 1.

It can be understood that, in the case of different shift types and shift digits, the post-processing unit can easily obtain the result of bit inversion and shift of the data to be processed by means of the mask code phase and the manner in which the result of bit inversion and cyclic shift corresponds to the shift types and shift digits.

In a third aspect, the present application provides a processor comprising the bit reversal shifting means of any one of the above second aspect and possible implementations of the second aspect.

In a fourth aspect, the present application provides an electronic device comprising a processor of the third aspect.

Drawings

Fig. 1 illustrates a schematic diagram of an inverse butterfly network, according to some embodiments of the application;

FIG. 2 illustrates a bit reversal shifting apparatus 200, according to some embodiments of the application;

FIG. 3A illustrates a control signal generation unit 202, according to some embodiments of the application;

FIG. 3B illustrates a data flow diagram of bit reversing input data to an inverse butterfly network with a bit reversing control signal, according to some embodiments of the application;

FIG. 3C illustrates a data flow diagram for cyclic right shifting of input data to an inverse butterfly network with a cyclic right shift control signal, according to some embodiments of the application;

FIG. 3D illustrates a data flow diagram for cyclic left shifting of input data to an inverse butterfly network with a cyclic left shift control signal, according to some embodiments of the application;

FIG. 3E illustrates a data flow diagram for bit reversing and cyclic right shifting input data to an inverse butterfly network with a bit reversing cyclic right shifting control signal, in accordance with some embodiments of the application;

FIG. 3F illustrates a data flow diagram for bit reversing and cyclic left shifting input data to an inverse butterfly network with a bit reversing cyclic left shift control signal, in accordance with some embodiments of the application;

FIG. 4A illustrates a schematic diagram of an aftertreatment unit 204, according to some embodiments of the application;

FIG. 4B illustrates a mask code with a shift number of bits between 0 and 7, according to some embodiments of the application;

FIG. 5 illustrates a flow chart of a method of bit-reversal shifting data, according to some embodiments of the application;

fig. 6 illustrates a schematic diagram of an electronic device 100, according to some embodiments of the application.

Detailed Description

Illustrative embodiments of the application include, but are not limited to, bit-reversal shifting methods, apparatus, processors, and electronic devices.

In order to make the objects, technical solutions and advantages of the present application more apparent, the technical solutions of the examples of the present application will be further described in detail by referring to the drawings and the embodiments. It will be apparent that the described embodiments are only some, but not all, embodiments of the application. All other embodiments, which can be made by those skilled in the art based on the embodiments of the application without making any inventive effort, are intended to be within the scope of the application.

In order to more clearly illustrate the aspects of the embodiments of the present application, some terms related to the embodiments of the present application are explained below.

1. Shift operation:

the shift includes four types: left shift, right shift, cyclic left shift, cyclic right shift.

Specifically, the left shift is to shift all binary bits of one number to the left by a specified bit number, the bits left to the right are filled with 0 s, and the high bit is discarded when the high bit left shifts overflow. For example, a 1-bit shift to the left of a binary number 00001111 having a bit width of 8 results in 00011110, and the bits left free to the right are padded with 0.

The right shift is to shift all binary bits of one number to right by a specified number of bits, the left blank bit is filled with 0, and the low bit is discarded when the low bit is overflowed to right. For example, a bit width of 8 binary number 00001111 is shifted to the right by 1 bit, and 00000111 is obtained, and the left blank bit is filled with 0.

The cyclic left shift is to shift all binary digits of one number left by a specified number of digits and put the shifted high digit on the low digit of the number. For example, a 1-bit shift left is performed on the 10001111 cycle of a binary number having a bit width of 8, thereby obtaining 00011111.

The cyclic right shift is to shift all binary digits of a number right by a specified number of digits and put the shifted low digits on the high digits of the number. For example, a cycle of 10001111 right-shifted by 1 bit for a binary number of bit width 8 yields 11000111.

2. Bit reversal operation

The bit inversion operation is to exchange the high and low bits of one number of binary bits. For example, for a binary number 10001111 with a bit width of 8, the 0 th and 7 th bit exchanges, the 1 st and 6 th bit exchanges, the 2 nd and 5 th bit exchanges, the 3 rd and 4 th bit exchanges of the number are exchanged, resulting in 11110001.

3. Bit inversion and shift operation

And performing bit inversion and shift operation, namely performing left shift or right shift on the number after the high and low bit exchange of one number of binary bits.

4. Reverse butterfly network (Inverse Butterfly Network):

The butterfly network is a novel circuit structure, and can rearrange the positions of the digits in the binary number of the input data according to the control signal input to the network to obtain binary output data, wherein the output data is the same as the digits included in the input data, but the arrangement order of the digits is different.

For ease of understanding, first, the logic of the inverse butterfly network to adjust the order of the digits in the input binary number according to the control signal will be described.

The reverse butterfly network is a multi-stage network, for a K-stage reverse butterfly network, the input of the 1 st stage network is the input of the reverse butterfly network, the input of the N (K is more than or equal to N is more than or equal to 2) stage network is the output of the N-1 st stage network, and the reverse butterfly network can be used for rearranging the sequence of the numbers in the binary number of 2 ^K bits.

It is understood that the control signal of the nth level network is a binary number of 2 ^N-1 bits. The N (K.gtoreq.N.gtoreq.1) level network divides the input data of the level network into 2 ^K-N sub-butterfly networks (clusters), each cluster comprises 2 ^N digits, and the first 2 ^N-1 digits of each cluster are the first sub-cluster and the second 2 ^N-1 digits are the second sub-cluster. After receiving the control signal, the N-th level network adjusts the positions of the ith bit number in the first sub-cluster and the ith bit number in the second sub-cluster in each cluster according to the value of the ith bit number of the control signal. Specifically, if the ith bit number of the control signal is binary 1, exchanging the ith bit number in the first sub-cluster and the ith bit number in the second sub-cluster in each cluster; if the ith bit number of the control signal is 0, the ith bit number in the first sub-cluster and the ith bit number in the second sub-cluster in each cluster are kept unchanged.

For example, as shown in FIG. 1, for a 3-level butterfly network, the order of the digits in the 8-bit bin may be rearranged.

Referring to fig. 1, the level 2 network divides input data into 2 sub butterfly networks (clusters), each cluster including 4 digits, and the first 2 digits of each cluster are the first sub cluster and the second 2 digits are the second sub cluster. The control signal of the level 2 network is a binary number of 2 bits, say 2'b10 ("b" means binary number, "2 preceding" b "means bit width of binary number following" b ", i.e. 2' b10 means binary number 10 with bit width of 2). And the input of the level 2 network is the output of the level 1 network. After receiving the control signal 2' b10, the level 2 network keeps the 0 th bit number in the first sub-cluster and the 0 th bit number in the second sub-cluster unchanged in each cluster, namely the 0 th bit number a7 in the first sub-cluster and the 0 th bit number a5 in the second sub-cluster in fig. 1, when the value of the 0 th bit number of the control signal is 0; and according to the value of the 1 st digit of the control signal being 1, exchanging the 1 st digit of the first sub-cluster and the 1 st digit of the second sub-cluster in each cluster, namely exchanging the 1 st digit a6 of the first sub-cluster and the 1 st digit a4 of the second sub-cluster in the figure 1.

In this way, by inputting different control signals to each level of the butterfly network, the arrangement order of the digits in the input data to the butterfly network can be adjusted.

Embodiments of the present application will be described below with reference to the accompanying drawings.

As described above, in order to improve the calculation efficiency of bit inversion and shift, the embodiment of the present application provides a bit inversion and shift device that uses an inverse butterfly network to perform bit inversion and shift operation on input data, so that the bit inversion and shift operation can be performed in parallel, and the speed of bit inversion and shift is improved. The device firstly determines a control signal corresponding to the shift type and the shift bit number according to the shift type and the shift bit number, and then inputs the input data and the control signal into an inverse butterfly network, so that a result of bit inversion and cyclic shift of the input data can be obtained. And then, according to the type of the shift and the shift bit number, post-processing is carried out on the result output by the inverse butterfly network to obtain a bit inversion and shift calculation result.

Therefore, the application changes the traditional serial structure of bit inversion and shift of input data into a parallel structure, and has short calculation time consumption and improved running speed of the computer; the butterfly network has simple structure, can reduce the circuit area, is easy to expand, and is very suitable for other operations of the expandable vector; this structure can be easily integrated with other shift instructions, for example, the bit inversion of different shift types is performed in parallel, and all simple shift operations can be realized by the bit inversion shift device of the present application.

Specifically, FIG. 2 illustrates a bit reversal shifting apparatus 200 in some embodiments of the application. The device comprises a data acquisition unit 201, a control signal generation unit 202, an inverse butterfly network unit 203 and a post-processing unit 204.

The data acquisition unit 201 is configured to acquire an input parameter, where the input parameter includes input data, a shift type, and a shift bit number that need to be subjected to a bit inversion and shift operation, send the shift type and the shift bit number in the input parameter to the control signal generation unit 202 and the post-processing unit 204, and send the input data to the butterfly network unit 203;

The control signal generating unit 202 is configured to obtain a control signal according to the shift type and the shift bit number given by the data acquiring unit 201, and send the control signal to the butterfly network unit 203. The control signal is used for controlling the input data of the butterfly network element 203 to realize the functions of bit inversion and shift. For example, a control signal having a bit inversion and cyclic shift function (hereinafter referred to as a bit inversion cyclic shift control signal) is obtained according to the received shift type and shift bit number, and the bit inversion cyclic shift control signal is transmitted to the butterfly network unit 203, so that the input data of the butterfly network unit 203 is bit-inverted and cyclic-shifted. The logic for generating the bit-reversal cyclic shift control signal will be described below, and will not be described in detail here.

The butterfly network unit 203 is configured to receive the control signal provided by the control signal generating unit 202, rearrange the positions of the digits in the binary numbers of the input data provided by the data obtaining unit 201 according to the obtained control signal, obtain an intermediate calculation result, and provide the intermediate calculation result to the post-processing unit 204. For example, when the control signal is a bit-reversal cyclic shift control signal, the butterfly network unit 203 switches the high-low digits in the binary number of the input data according to the acquired bit-reversal cyclic shift control signal, and cyclic shifts the switched result to obtain a bit-reversal and cyclic shift result, and sends the bit-reversal and cyclic shift result to the post-processing unit 204.

The post-processing unit 204 is configured to post-process the intermediate calculation result given by the butterfly network unit 203 according to the shift type and the shift bit number given by the data obtaining unit 201, so as to obtain an output result. Specifically, when the shift type is right shift, the post-processing unit 204 pairs the high position 0 of the intermediate calculation result according to the shift number of bits; when the shift type is left shift, the post-processing unit 204 outputs the result as the intermediate calculation result when the shift type is cyclic right shift or cyclic left shift according to the shift bit number to the low position 0 of the intermediate calculation result. In some embodiments, the output result may be obtained by performing a bit-and-bit processing on the mask code obtained according to the shift type and the shift bit number and the intermediate calculation result. For example, the intermediate calculation result is a bit inversion and cyclic shift result, and when the shift operation is not cyclic shift, a corresponding mask code is obtained according to the shift type and the shift bit number, and the high or low bit of the bit inversion and cyclic shift result is positioned 0 according to the bit and the mask code and the bit inversion and cyclic shift result, thereby obtaining the bit inversion and shift result.

It can be understood that the parallel bit inversion shifting device provided by the application can realize various bit inversion and shifting operations of bit data, the original bit inversion calculation of the binary number is finished through a circuit such as replacement, then the operation of shifting the binary number after the bit inversion is finished through a cyclic shift related circuit is changed into the operation of bit inversion and shifting through the bit inversion and shift related circuit, thus the operation of bit inversion and shifting of the binary number can be realized, the calculation time consumption can be reduced, the running speed of a computer is increased, and the operation is simple.

Logic of the control signal generation unit 202 generating the bit inversion and cyclic shift control signal is described below.

As shown in fig. 3A, the control signal generation unit 202 includes a bit inversion control signal generation unit 202a, a cyclic shift control signal generation unit 202b, and a control signal exclusive or unit 202c.

Specifically, the bit inversion control signal generating unit 202a is configured to generate bit inversion control signals corresponding to each stage of the butterfly network. Wherein, the value of each digit on the bit inversion control signal corresponding to each level of the butterfly network is binary 1. For example, for a 3-level butterfly network, the first level bit inversion control signal is a 1-bit binary number 1, i.e., 1' b1, the second level bit inversion control signal is a 2-bit binary number 11, i.e., 2' b11, and the third level bit inversion control signal is a 4-bit binary number 1111, i.e., 4' b1111.

The following describes a specific control procedure of the bit inversion control signal, and fig. 3B shows a specific procedure in which the bit inversion control signal acts on the butterfly network, so that 8-bit data input data of the butterfly network realizes bit inversion.

For the first level network, the input data is divided into 4 sub-butterfly network (cluster) clusters, namely clusters 1 to 4 (only cluster1 is shown in fig. 3B), the first 1 digit of each cluster is the first sub-cluster, the last 1 digit is the second sub-cluster, the control signal of the first level is 1' B1, and the positions of the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged. For the sub-butterfly network (cluster) cluster1, the 0 th digit a7 in the first sub-cluster 1 and the 0 th digit a6 in the second sub-cluster 1 in the sub-butterfly network (cluster) cluster1 are exchanged, and other sub-butterfly networks (clusters) of the first stage exchange corresponding bits in each sub-cluster under the control signal, namely exchange data a5 and a4 in the cluster2, exchange data a3 and a2 in the cluster3, exchange data a1 and a0 in the cluster4, so as to obtain output data of the first stage as a6, a7, a4, a5, a2, a3, a0 and a1.

For the second level network, the input data is divided into 2 sub-butterfly network (cluster) clusters, namely cluster1 'and cluster2' (only cluster1 'is shown in fig. 3B), the first 2 digits of each cluster are the first sub-cluster, the second 2 digits are the second sub-cluster, the control signal of the second level is 2' B11, and the positions of the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged, and the positions of the 1 st digit in the first sub-cluster and the 1 st digit in the second sub-cluster are exchanged. Exchanging the 0 th digit a7 in the first sub-cluster 1' and the 0 th digit a5 in the second sub-cluster 1' in the sub-butterfly network (cluster) cluster1', and exchanging the 1 st digit a6 in the first sub-cluster 1' and the 1 st digit a4 in the second sub-cluster 1 '; under the control signal, other sub butterfly networks (clusters) of the second stage exchange corresponding bits in each sub cluster, namely exchange data a3 and a1 in cluster2', and exchange data a2 and a 0; finally, output data of the second stage are obtained as a4, a5, a6, a7, a0, a1, a2 and a3.

For the third level network, the input data is divided into 1 sub-butterfly network (cluster) of which the first 4 digits are the first sub-cluster and the second 2 digits are the second sub-cluster of each cluster1", the control signals of the third level are 4' b1111, the positions of the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged, the positions of the 1 st digit in the first sub-cluster and the 1 st digit in the second sub-cluster are exchanged, the positions of the 2 nd digit in the first sub-cluster and the 2 nd digit in the second sub-cluster are exchanged, and the positions of the 3 rd digit in the first sub-cluster and the 3 rd digit in the second sub-cluster are exchanged. For the sub-butterfly network (cluster) cluster1", the 0 th digit a7 in the first sub-cluster 1" and the 0 th digit a3 in the second sub-cluster 1 "in the sub-butterfly network (cluster) cluster1", the 1 st digit a6 in the first sub-cluster 1 "and the 1 st digit a2 in the second sub-cluster 1" are exchanged, the 2 nd digit a5 in the first sub-cluster 1 "and the 2 nd digit a1 in the second sub-cluster 1" are exchanged, and the 3 rd digit a4 in the first sub-cluster 1 "and the 3 rd digit a0 in the second sub-cluster 1" are exchanged, so that output data a0, a1, a2, a3, a4, a5, a6, a7 of the third level are obtained.

That is, for an N-bit binary number, the inverse butterfly network may perform bit inversion on the input data through a log ₂ (N) level network, and the control signal of the ith level is a2 ^i-1 -bit all-1 binary signal. By inverting the control signal, the butterfly network can realize bit inversion of the input data. The bit inversion control signal generated by the bit inversion control signal generation unit 202a can realize bit inversion of the input data in the butterfly network.

The cyclic shift control signal generating unit 202b is configured to generate a bit cyclic shift control signal corresponding to each stage of the butterfly network.

The cyclic shift control signal is described below.

Assuming that the butterfly network is a K-level network, the binary number input to the network includes a2 ^K -bit number, the bit number of the nth-level control signal is 2 ^N-1 bits, and if the binary number corresponding to the shifted bit number is M, the nth-level control signal can be obtained by: a.2 A specific signal of ^N -bit binary numbers (wherein the high 2 ^N-1 bits of the specific signal are 0, the low 2 ^N-1 bits are 1) is circularly shifted left (the operation instruction is circularly shifted left) or circularly shifted right (the operation instruction is circularly shifted right) by J bits (J is a decimal number corresponding to the last N bits of M), so as to obtain an intermediate control signal P; b. the first 2 ^N-1 bits of P are used as the control signal for the nth stage.

For example, taking a cyclic shift of 5 bits to the right as an example, where the butterfly network is a 3-level network, the binary number input to the network includes 8 digits, and if a cyclic shift of 5 bits is desired, only a cyclic shift of 5 bits is required to be generated. Wherein the binary number corresponding to the cyclic shift right of 5 bits is 3' b101.

As shown in fig. 3C, the specific signal corresponding to the first level is 2-bit binary number 01, namely 2' b01, the specific signal 2' b01 is circularly shifted to the right by 1 bit, wherein ' 1 bit ' is a decimal number corresponding to the lowest binary number 1 in 3' b101, 2' b01> is 1' b1=2 ' b10 ("> > >" represents circular right shift), and the upper 1 bit data of the circular right shift result of the specific signal is selected as the circular right shift control signal of the first level, namely the circular right shift control signal of the first level is 1' b1; the specific signal corresponding to the second stage is 4' b0011, the specific signal 4' b0011 is circularly shifted to the right by 1 bit, namely the lowest 2 bits of binary number 3' b101 corresponding to the shift bit number are ' 01', 4' b0011> >2' b 01=4 ' b1001, and the upper 2 bits of data of the circular right shift result of the specific signal are selected as the circular right shift control signal of the second stage, namely the circular right shift control signal of the second stage is 2' b10; the specific signal corresponding to the third stage is 8' b00001111, the specific signal 8' b00001111 is circularly shifted to the right by 5 bits, namely, the corresponding shift bit number is 3' b101 value, 8' b00001111> is 3' b101=8 ' b 0111000, and the upper 4 bits of the specific signal circularly right shifting result are selected as the circularly right shifting control signal of the third stage, namely, the circularly right shifting control signal of the third stage is 4' b0111.

The specific process of implementing bit cyclic right shift of the input data of the butterfly network is described below by taking the effect of the obtained cyclic right shift 5-bit control signal on the butterfly network as an example, wherein the input data of the butterfly network is 8-bit data as an example.

As shown in fig. 3C, for the first level network, the input data is divided into 4 sub-butterfly network (cluster) clusters, respectively, cluster1 to cluster4 (only cluster1 is shown in fig. 3C), the first 1 digit of each cluster is the first sub-cluster, the second 1 digit is the second sub-cluster, the control signal of the first level is 1' b1, and the positions of the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged. For the sub-butterfly network (cluster) cluster1, the 0 th digit a7 in the first sub-cluster 1 and the 0 th digit a6 in the second sub-cluster 1 in the sub-butterfly network (cluster) cluster1 are exchanged, and other sub-butterfly networks (clusters) of the first stage exchange corresponding bits in each sub-cluster under the control signal, namely exchange data a5 and a4 in the cluster2, exchange data a3 and a2 in the cluster3, exchange data a1 and a0 in the cluster4, so as to obtain output data of the first stage as a6, a7, a4, a5, a2, a3, a0 and a1.

For the second level network, the input data is divided into 2 sub-butterfly network (cluster) clusters, namely cluster1 'and cluster2' (only cluster1 'is shown in fig. 3C), the first 2 digits of each cluster are the first sub-cluster, the second 2 digits are the second sub-cluster, the control signal of the second level is 2' b10, the number at the position of the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster is unchanged, and the numbers at the positions of the 1 st digit in the first sub-cluster and the 1 st digit in the second sub-cluster are exchanged. For the sub-butterfly network (cluster) cluster1', the 0 th digit a7 in the first sub-cluster 1' and the 0 th digit a5 in the second sub-cluster 1 'in the sub-butterfly network (cluster) cluster1' are kept unchanged, and the 1 st digit a6 in the first sub-cluster 1 'and the 1 st digit a4 in the second sub-cluster 1' are exchanged; under the control signal, the data a3 and a1 in the cluster2' are kept unchanged, and the data a2 and a0 are exchanged; finally, output data of the second stage are obtained as a4, a7, a6, a5, a0, a3, a2 and a1.

For the third level network, the input data is divided into 1 sub-butterfly network (cluster) of which the first 4 digits are the first sub-cluster and the second 2 digits are the second sub-cluster of each cluster1", the control signal of the third level is 4' b0111, the positions of the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged, the positions of the 1 st digit in the first sub-cluster and the 1 st digit in the second sub-cluster are exchanged, the positions of the 2 nd digit in the first sub-cluster and the 2 nd digit in the second sub-cluster are exchanged, and the 3 rd digit in the first sub-cluster and the 3 rd digit in the second sub-cluster are kept unchanged. For the sub-butterfly network (cluster) cluster1", the 0 th digit a5 in the first sub-cluster 1" and the 0 th digit a1 in the second sub-cluster 1 "in the sub-butterfly network (cluster) cluster1", the 1 st digit a6 in the first sub-cluster 1 "and the 1 st digit a2 in the second sub-cluster 1" are exchanged, the 2 nd digit a7 in the first sub-cluster 1 "and the 2 nd digit a3 in the second sub-cluster 1" are exchanged, and the 3 rd digit a4 in the first sub-cluster 1 "and the 3 rd digit a0 in the second sub-cluster 1" are unchanged, so that output data a4, a3, a2, a1, a0, a7, a6, a5 of the third level are obtained.

For example, in the case of a 3-stage network, which is a cyclic shift left by 5 bits, the binary number input to the network is an 8-bit binary number, and if a cyclic shift left by 5 bits is desired, only a cyclic shift left control signal of 5 bits is generated. Wherein the binary number corresponding to the cyclic shift left by 5 bits is 3' b101.

As shown in fig. 3D, the specific signal corresponding to the first stage is 2' b01, the specific signal 2' b01 is circularly shifted left by 1 bit, wherein "1 bit" is a decimal number corresponding to the lowest binary number 1 in 3' b101, 2' b01< < <1' b1=2 ' b10 ("< <") represents circular shift left), and the upper 1 bit data of the circular shift left result of the specific signal is selected as the circular shift left control signal of the first stage, that is, the circular shift left control signal of the first stage is 1' b1; the specific signal corresponding to the second stage is 4' b0011, the specific signal 4' b0011 is circularly shifted by 1 bit, namely the lowest 2 bits "01" corresponding to the shift bit number 3' b101, 4' b0011< <2' b 01=4 ' b0110, and the upper 2 bits of data of the specific signal circularly left shift result are selected as the second stage circularly left shift control signal, namely the second stage circularly left shift control signal is 2' b01; the specific signal corresponding to the third stage is 8' b00001111, the specific signal 8' b00001111 is circularly shifted left by 5 bits, namely, the corresponding shift bit number is 3' b101 value, 8' b00001111< < <3' b101=8 ' b11100001, and the upper 4 bits of the cyclic left shift result of the specific signal are selected as the cyclic left shift control signal of the third stage, namely, the cyclic left shift control signal of the third stage is 4' b1110.

As shown in fig. 3D, for the first-level network, the input data is divided into 4 sub-butterfly networks (clusters), respectively, cluster1 to cluster4 (only cluster1 is shown in fig. 3D), the first 1 digit of each cluster is the first sub-cluster, the second 1 digit is the second sub-cluster, the control signal of the first level is 1' b1, and the positions of the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged. For the sub-butterfly network (cluster) cluster1, the 0 th digit a7 in the first sub-cluster 1 and the 0 th digit a6 in the second sub-cluster 1 in the sub-butterfly network (cluster) cluster1 are exchanged, and other sub-butterfly networks (clusters) of the first stage exchange corresponding bits in each sub-cluster under the control signal, namely exchange data a5 and a4 in the cluster2, exchange data a3 and a2 in the cluster3, exchange data a1 and a0 in the cluster4, so as to obtain output data of the first stage as a6, a7, a4, a5, a2, a3, a0 and a1.

For the second level network, the input data is divided into 2 sub-butterfly network (cluster) clusters, namely cluster1 'and cluster2' (only cluster1 'is shown in fig. 3D), the first 2 digits of each cluster are the first sub-cluster, the second 2 digits are the second sub-cluster, the control signal of the second level is 2' b01, and the numbers at the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged, and the numbers at the 1 st digit in the first sub-cluster and the 1 st digit in the second sub-cluster are unchanged. For the sub-butterfly network (cluster) cluster1', the 0 th digit a7 in the first sub-cluster 1' and the 0 th digit a5 in the second sub-cluster 1 'in the sub-butterfly network (cluster) cluster1' are exchanged, and the 1 st digit a6 in the first sub-cluster 1 'and the 1 st digit a4 in the second sub-cluster 1' are unchanged; other sub butterfly networks (clusters) of the second stage exchange data a3 and a1 in a cluster2' under a control signal, and the data a2 and a0 are unchanged; finally, output data of the second stage are obtained as a6, a5, a4, a7, a2, a1, a0 and a3.

For the third level network, the input data is divided into 1 sub-butterfly network (cluster) of which the first 4 digits are the first sub-cluster and the second 2 digits are the second sub-cluster of each cluster1", the control signal of the third level is 4' b1110, the positions of the 0 th digit in the first sub-cluster and the 1 st digit in the second sub-cluster are exchanged, the positions of the 2 nd digit in the first sub-cluster and the 2 nd digit in the second sub-cluster are exchanged, and the 3 rd digit in the first sub-cluster and the 3 rd digit in the second sub-cluster are exchanged. For the sub-butterfly network (cluster) cluster1", the 0 th digit a7 in the first sub-cluster 1" and the 0 th digit a3 in the second sub-cluster 1 "in the sub-butterfly network (cluster) cluster1" are unchanged, the 1 st digit a4 in the first sub-cluster 1 "and the 1 st digit a0 in the second sub-cluster 1" are exchanged, the 2 nd digit a5 in the first sub-cluster 1 "and the 2 nd digit a1 in the second sub-cluster 1" are exchanged, and the 3 rd digit a6 in the first sub-cluster 1 "and the 3 rd digit a2 in the second sub-cluster 1" are exchanged, so that output data a2, a1, a0, a7, a6, a5, a4, a3 of the third level are obtained.

Therefore, the cyclic shift control signal generating unit 202b may obtain a corresponding cyclic shift control signal according to the shift bit number and the shift type, and perform cyclic shift on the input data in the butterfly network according to the cyclic shift control signal, so as to implement adjustment of the corresponding positions of the numbers at each position of the input data in the butterfly network.

The control signal exclusive-or unit 202c is configured to exclusive-or the bit inversion control signal generated by the bit inversion control signal generating unit 202a with the cyclic shift control signal generated by the cyclic shift control signal generating unit 202b, and generate a bit inversion cyclic shift control signal, which is the control signal output by the control signal generating unit 202.

The exclusive or operation of the bit inversion control signal and the cyclic shift control signal is described below.

The bit-reversal cyclic shift control signal can be obtained by exclusive-or-operating the bit-reversal control signal and the cyclic shift control signal generated by the cyclic shift control signal generating unit 202 b. The control signal of the nth stage can be obtained by: acquiring a bit inversion control signal and a cyclic shift control signal of an N-th stage; exclusive or operation is performed on the binary value of the ith bit of the nth stage bit inversion control signal and the binary value of the ith bit of the nth stage cyclic shift control signal, that is, if the value of the ith bit of the bit inversion control signal is the same as the value of the ith bit of the cyclic shift control signal, the obtained value of the ith bit of the bit inversion cyclic shift control signal is 0, and if the value of the ith bit of the bit inversion control signal is different from the value of the ith bit of the cyclic shift control signal, the obtained value of the ith bit of the bit inversion cyclic shift control signal is 1.

As shown in fig. 3E, taking the bit inversion control signal shown in fig. 3B and the shift type shown in fig. 3C as right shift, the cyclic right shift control signal obtained by shifting the number of bits to 5 bits is exclusive-ored, and the bit inversion cyclic right shift control signal is obtained as an example for explanation.

For the first-stage network, the bit inversion control signal 1' b1, the cyclic shift control signal 1' b1, the binary value 1 of the 0 th bit of the bit inversion control signal of the 1 st stage and the value 1 of the 0 th bit of the cyclic shift control signal are subjected to exclusive OR operation, the two values are the same, the value of the 0 th bit of the bit inversion cyclic shift control signal of the 1 st stage is obtained to be 0, and then the bit inversion cyclic shift control signal of the first-stage network is 1' b0;

For the second-stage network, the bit inversion control signal 2' b11 and the cyclic shift control signal 2' b10 are subjected to exclusive or operation, wherein the binary value 1 of the 0 th bit of the second-stage bit inversion control signal and the value 0 of the 0 th bit of the cyclic shift control signal are subjected to exclusive or operation, the two values are different, the value 1 of the 0 th bit of the second-stage bit inversion cyclic shift control signal is obtained, the binary value 1 of the 1 st bit of the second-stage bit inversion control signal and the value 1 of the 1 st bit of the cyclic shift control signal are subjected to exclusive or operation, the two values are identical, and the value of the 1 st bit of the second-stage bit inversion cyclic shift control signal is obtained, and then the bit inversion cyclic shift control signal of the second-stage network is 2' b01;

For the third-stage network, the bit inversion control signal 4'b1111 and the cyclic shift control signal 4' b0111 are subjected to exclusive or operation, the binary value 1 of the 0 th bit of the third-stage bit inversion control signal and the value 1 of the 0 th bit of the cyclic shift control signal are subjected to exclusive or operation, the two values are identical, the value of the 0 th bit of the third-stage bit inversion cyclic shift control signal is obtained, the binary value 1 of the 1 st bit of the third-stage bit inversion control signal and the value 1 of the 1 st bit of the cyclic shift control signal are subjected to exclusive or operation, the value of the 1 st bit of the third-stage bit inversion control signal is obtained, the binary value 1 of the 2 nd bit of the third-stage bit inversion control signal and the value 1 of the 2 nd bit of the cyclic shift control signal are subjected to exclusive or operation, the two values are identical, the value of the 2 nd bit of the third-stage bit inversion cyclic shift control signal is obtained is 0, the binary value 1 of the 3 bit of the third-stage bit inversion control signal and the value 0 of the third bit of the cyclic shift control signal is obtained, and the two values of the cyclic shift control signal are different, and the cyclic shift control signal is obtained, and the cyclic shift network is 1000.

Taking the effect of the obtained control signal with the cyclic shift of 5 bits on the butterfly network as an example, introducing the bit inversion cyclic shift control signal obtained by performing exclusive or operation on the bit inversion control signal and the cyclic shift control signal to enable the butterfly network input data to realize the effects of bit inversion and cyclic shift.

Fig. 3E shows a specific process of bit reversing and cyclic right shifting the input data using a bit reversing cyclic shift signal, taking the input data of the butterfly network as 8-bit data as an example.

For the first level network, the input data is divided into 4 sub-butterfly network (cluster) clusters, namely clusters 1 to 4 (only cluster1 is shown in fig. 3E), the first 1 digit of each cluster is the first sub-cluster, the last 1 digit is the second sub-cluster, and the control signal of the first level is 1' b0, so that the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are unchanged. For the sub-butterfly network (cluster) cluster1, the 0 th bit a7 in the first sub-cluster 1 and the 0 th bit a6 in the second sub-cluster 1 in the sub-butterfly network (cluster) cluster1 are unchanged, and under a control signal, the corresponding bits in the other sub-clusters of the first stage are also unchanged, namely the data a5 and a4 in the cluster2 are kept as original values, the data a3 and a2 in the cluster3 are kept as original values, and the data a1 and a0 in the cluster4 are kept as original values, so that output data of the first stage are a7, a6, a5, a4, a3, a2, a1 and a0.

For the second level network, the input data is divided into 2 sub-butterfly networks (clusters), respectively cluster1 'and cluster2' (only cluster1 'is shown in fig. 3E), the first 2 digits of each cluster are the first sub-cluster, the last 2 digits are the second sub-cluster, the control signal of the second level is 2' b01, and the numbers at the 0 th digit in the first sub-cluster and the 0 th digit in the second sub-cluster in each cluster are exchanged, and the numbers at the 1 st digit in the first sub-cluster and the 1 st digit in the second sub-cluster are unchanged. For the sub-butterfly network (cluster) cluster1', the 0 th digit a6 in the first sub-cluster 1' and the 0 th digit a4 in the second sub-cluster 1 'in the sub-butterfly network (cluster) cluster1', the 1 st digit a7 in the first sub-cluster 1 'and the 1 st digit a5 in the second sub-cluster 1' are unchanged; other sub butterfly networks (clusters) of the second stage exchange data a2 and a0 in a cluster2' under a control signal, and the data a3 and a1 are unchanged; finally, output data of the second stage are obtained as a7, a4, a5, a6, a3, a0, a1 and a2.

For the third level network, the input data is divided into 1 sub-butterfly network (cluster), namely, cluster1", the first 4 digits of each cluster are the first sub-cluster, the last 2 digits are the second sub-cluster, the control signal of the third level is 4' b1000, the number of bits 0 in the first sub-cluster and the number of bits 0 in the second sub-cluster in each cluster are unchanged, the number of bits 1 in the first sub-cluster and the number of bits 1 in the second sub-cluster are unchanged, the number of bits 2 in the first sub-cluster and the number of bits 2 in the second sub-cluster are unchanged, and the number of bits 3 in the first sub-cluster and the number of bits 3 in the second sub-cluster are exchanged. For the sub butterfly network (cluster) cluster1", the 0 th digit a6 in the first sub cluster1" and the 0 th digit a2 in the second sub cluster1 "in the sub butterfly network (cluster) cluster1" are kept unchanged, the 1 st digit a5 in the first sub cluster1 "and the 1 st digit a1 in the second sub cluster1" are kept unchanged, the 2 nd digit a4 in the first sub cluster1 "and the 2 nd digit a0 in the second sub cluster1" are kept unchanged, and the 3 rd digit a7 in the first sub cluster1 "and the 3 rd digit a3 in the second sub cluster1" are exchanged to obtain output data a3, a4, a5, a6, a7, a0, a1, a2 of the third stage.

For the bit reversal cyclic left shift, fig. 3F shows a specific process of performing an exclusive or operation on the bit reversal cyclic left shift control signal obtained by performing a bit reversal and cyclic shift on the input data of the butterfly network by using the bit reversal control signal shown in fig. 3B and the cyclic left shift control signal with a shift type of left shift and a shift bit number of 5 bits shown in fig. 3D, where the specific process of obtaining the bit reversal cyclic left shift control signal shown in fig. 3F according to the bit reversal control signal and the cyclic left shift control signal exclusive or operation is the same as the process of obtaining the bit reversal cyclic right shift control signal shown in fig. 3E, and details are not repeated herein. As shown in fig. 3F, each stage xors the bit inversion control signal with the cyclic left shift control signal to obtain the bit inversion cyclic left shift control signal of each stage, the first stage is 1' b0, the second stage is 2' b10, and the third stage is 4' b0001.

The obtained bit inversion cyclic left shift control signal is used for controlling the input data of the butterfly network, so that the bit inversion and cyclic left shift of the input data can be realized. Fig. 3F shows a control process of the bit reversal loop left shift control signal corresponding to the left shift 5 bits on the input data of the butterfly network, and the specific control process is the same as the bit reversal loop right shift control process, which is not described herein. Fig. 3F shows the result of bit-reversing and cyclic left-shifting the input data a7, a6, a5, a4, a3, a2, a1, a0 by 5 bits, as a5, a6, a7, a0, a1, a2, a3, a4.

It will be appreciated that the above-described bit inversion and cyclic shift of the input data to the butterfly network by xoring the bit inversion control signal with the cyclic shift control signal is merely an example.

The control signal generating unit 202 can directly generate a control signal for performing bit inversion and cyclic shift on input data by using the butterfly network, so that the butterfly network can directly obtain a bit inversion and cyclic shift result for performing bit inversion and shift on the input data based on the control signal and the input data, thereby realizing parallel operation for performing bit inversion and shift on the data, being beneficial to accelerating the calculation speed and reducing the calculation time consumption.

The logic of the post-processing unit 204 in fig. 2 for performing post-processing on the bit-inverted and cyclic shift result obtained by the butterfly network unit 203 based on the shift type and the shift number will be described below.

As described above, the intermediate calculation result of bit inversion and shift is output from the butterfly network, and the intermediate calculation result obtained by the butterfly network unit 203 may be post-processed by the post-processing unit 204 as the final result of bit inversion and shift. For example, the result bit-ANDed may be calculated from the mask film and the middle, resulting in a bit-reversed and shifted final result.

In particular, FIG. 4A illustrates a schematic diagram of a parallel post-processing unit 204, according to some embodiments of the application. As shown in fig. 4A, the post-processing unit 204 includes a mask code generating unit 204A and a bit and unit 204b.

A mask code generating unit 204a for generating a mask code according to the shift type and the shift number of bits;

And a bit and unit 204b, configured to and the intermediate calculation result obtained by the butterfly network unit 203 and the mask code bit obtained by the mask code generating unit 204a, and high or low 0, so as to obtain an output result. For example, if the intermediate calculation result is a bit inversion and cyclic shift result, the obtained bit inversion and cyclic shift result is bit-and-bit-with the mask code obtained according to the shift type and shift bit number, and the high or low position 0 is bit-inverted and shift result is obtained.

The logic of the mask code generation unit 204a to generate the mask code according to the shift type and the shift number of bits will be described below.

The bit width of the mask code is the same as the bit width of the intermediate calculation result obtained by the butterfly network element 203. When the shift type is cyclic shift, the binary value on each bit of the mask code is 1; when the shift type is not cyclic shift, for right shift, the values of several bits of the mask code high shift bits are all 0 and the values of the remaining bits are all 1 from the high bit. For the left shift, from the low order bit, the values of the mask code low shift bits are all 0 and the values of the remaining bits are all 1.

Taking the mask code bit width of 8 bits as an example, when the shift type is cyclic left shift or cyclic right shift, the mask code generating unit 204a obtains the mask code value with all bits of 1, that is, 8' b11111111, which means that the value of the 8-bit binary number is 11111111. For the case where the shift type is not cyclic shift, that is, left shift or right shift, fig. 4B shows that the decimal value corresponding to the shift bit number is between 0 and 7, the mask code generating unit 204a obtains the 8-bit binary mask code value according to the shift bit number and the shift type.

The 3 bits corresponding to the shift bit number are B2, B1 and B0 bits from high to low, the 8-bit mask codes corresponding to the right shift are A7, A6, A5, A4, A3, A2, A1 and A0 bits from high to low, and the 8-bit mask codes corresponding to the left shift are A7, A6, A5, A4, A3, A2, A1 and A0 bits from high to low. As shown in fig. 4B, when the shift bit number is 3' B000, the right shift mask is 8' B11111, and the left shift mask is 8' B11111; when the shift bit number is 3' b001, the right shift mask is 8' b01111111, and the left shift mask is 8' b11111110; when the shift bit number is 3' b010, the right shift mask is 8' b00111111, and the left shift mask is 8' b11111100; when the shift bit number is 3' b011, the right shift mask is 8' b00011111, and the left shift mask is 8' b11111000; when the shift bit number is 3' b100, the right shift mask is 8' b00001111, and the left shift mask is 8' b11110000; when the shift bit number is 3' b101, the right shift mask is 8' b00000111, and the left shift mask is 8' b11100000; when the shift bit number is 3' b110, the right shift mask is 8' b00000011, and the left shift mask is 8' b11000000; when the shift bit number is 3' b111, the right shift mask is 8' b00000001, and the left shift mask is 8' b10000000. The bit and unit 204b shown in fig. 4A performs an and operation on each bit of the intermediate calculation result obtained by the butterfly network unit 203 and each bit of the mask code obtained by the mask code generating unit 204A, thereby obtaining a bit-inverted and shifted result, that is, an output result.

Taking the bit reversal and right shift of 5 bits as an example, the mask code generating unit 204A in fig. 4A may phase the mask code 8' b00000111 corresponding to the bit reversal and right shift result a3, a4, a5, a6, a7, a0, a1, a2 and the right shift result a2, 0, a1, a2 obtained in the above-mentioned intermediate calculation result in fig. 3E.

In some embodiments, the process of generating the mask code by the mask code generating unit 204a may be performed in parallel with the process of generating the control signal by the control signal generating unit 202 and performing bit inversion and cyclic shift on the input data by the butterfly network unit 203 to obtain the intermediate calculation result, so that the calculation speed may be increased and the calculation time may be reduced. In some implementations, the mask code generating unit 204a may adopt a circuit structure of a temperature code, which is simple and convenient to implement.

It can be understood that the control signal generating unit 202 includes a parallel structure of the bit inversion control signal generating unit 202a and the cyclic shift control signal generating unit 202b, and the control signal exclusive or unit 202c exclusive or the control signals generated by the two control signal generating units, so as to obtain control signals capable of realizing two control functions, speed up computation time and reduce time consumption.

It should be understood that the above-described bit-reversal shifting apparatus 200 is merely illustrative, and the structure of the bit-reversal shifting apparatus 200 shown in the embodiment of the present application does not constitute a specific limitation of the bit-reversal shifting apparatus 200, and in other embodiments of the present application, fewer or more units may be included, some components may be combined, some components may be separated, or different components may be arranged, and the illustrated components may be implemented in hardware, software, or a combination of software and hardware.

The embodiment of the application also provides a bit inversion shifting method, which can utilize the bit inversion shifting device 200 to realize bit inversion and shifting of data. Since the bit-reversal shifting apparatus 200 has corresponding functional units for implementing the bit-reversal shifting method, the description will be made with reference to the configuration of the bit-reversal shifting apparatus 200 shown in fig. 2, the control signal generating unit 202 shown in fig. 3A, and the post-processing unit 204 shown in fig. 4A.

Specifically, fig. 5 illustrates a flow diagram of a bit-reversal shift method, according to some embodiments of the application. As shown in fig. 5, the method includes the following steps.

S501: the data acquisition unit 201 acquires input parameter data including input data, shift type, and shift number of bits.

In some embodiments, the data acquisition unit 201 acquires the input parameter data with the bits inverted and shifted, and sends the shift type and the shift number of bits in the input parameter data to the control signal generation unit 202 and the post-processing unit 204, and sends the input data to the butterfly network unit 203.

It is understood that the input parameter data of the bit-reversed and shifted acquired by the data acquisition unit 201 may be input parameter data of a bit-reversed and shifted related instruction. The input data is binary number which needs to be subjected to bit inversion and shift, and the shift type is cyclic left shift, cyclic right shift, left shift or right shift.

For example, taking binary number 8-bit data requiring bit inversion and shifting as an example, the data acquisition unit 201 acquires bit-inverted and shifted input parameter data including input data 8'b00001111, shift type is shift right, shift bit number is 5 bits, corresponding binary number is 3' b101, and the shift type right shift and shift bit number 3'b101 in the input parameter data are sent to the control signal generation unit 202 and the post-processing unit 204, and the input data 8' b00000111 is sent to the butterfly network unit 203.

S502: the control signal generation unit 202 generates a control signal according to the shift type and the shift number.

In some embodiments, the control signal generating unit 202 generates a control signal according to the shift type and the shift bit number, for implementing binary bit inversion and cyclic shift of the input data of the butterfly network unit 203.

Specifically, for generating the bit-reversal cyclic shift control signal, the control signal generation unit 202 includes a bit-reversal control signal generation unit 202a, a cyclic shift control signal generation unit 202b, and a control signal exclusive or unit 202c.

The bit inversion control signal generation unit 202a is configured to generate bit inversion control signals corresponding to each stage of the butterfly network, and send the obtained bit inversion control signals to the control signal exclusive or unit 202c. Wherein, the value of each digit on the bit inversion control signal corresponding to each level of the butterfly network is binary 1. For example, for a 3-stage butterfly network, the first stage bit inversion control signal is 1' b1, the second stage bit inversion control signal is 2' b11, and the third stage bit inversion control signal is 4' b1111.

The cyclic shift control signal generating unit 202b is configured to generate a cyclic shift control signal corresponding to each stage of the butterfly network according to the shift bit number and the shift type, and send the obtained cyclic shift control signal to the control signal exclusive or unit 202c. For example, for a 3-stage butterfly network, the shift type is right shift, the number of shift bits is 5 bits, the corresponding binary number is 3' b101, the corresponding cyclic right shift control signals are obtained according to the manner shown in fig. 3C, and the generated cyclic right shift control signals are sent to the control signal exclusive or unit 202C.

The control signal exclusive or unit 202c receives the bit inversion control signal transmitted by the bit inversion control signal generation unit 202a and the cyclic shift control signal transmitted by the cyclic shift control signal generation unit 202b, exclusive-ors the received bit inversion control signal of the corresponding number of stages with the bit corresponding to the cyclic shift control signal of the corresponding number of stages, obtains the bit inversion cyclic shift control signal of the corresponding number of stages, and outputs the generated bit inversion cyclic shift control signal as the control signal generation unit 202. For example, the bit inversion control signal shown in fig. 3B transmitted by the bit inversion control signal generation unit 202a is received, the first stage is 1'B1, the second stage is 2' B11, the third stage is 4'B1111, the cyclic right shift control signal shown in fig. 3C transmitted by the cyclic shift control signal generation unit 202B is received, and the first stage 1' B1, the second stage 2'B10, and the third stage 4' B0111 are received. As shown in fig. 3E, the first-stage bit reversal control signal 1' b1 is xored with the first-stage cyclic right shift control signal 1' b1, so as to obtain a first-stage bit reversal cyclic right shift control signal 1' b0; the second-stage bit inversion control signal 2'b11 is exclusive-ored with the second-stage cyclic right shift control signal 2' b10 to obtain a second-stage bit inversion cyclic right shift control signal 2'b01, and the third-stage bit inversion control signal 4' b1111 is exclusive-ored with the third-stage cyclic right shift control signal 4'b0111 to obtain a third-stage bit inversion cyclic right shift control signal 4' b1000. The control signal exclusive or unit 202c sends the generated bit inversion cyclic right shift control signals of the first stage 1' b0, the second stage 2' b01, and the third stage 4' b1000 to the butterfly network unit 203.

S503: the butterfly network unit 203 obtains an intermediate calculation result according to the input data and the acquired control signal.

In some embodiments, the butterfly network unit 203 is configured to receive the control signal from the control signal generating unit 202, perform bit inversion and cyclic shift on the input data from the data obtaining unit 201 according to the obtained control signal, obtain an intermediate calculation result, and send the intermediate calculation result to the post-processing unit 204.

For example, the butterfly network unit 203 receives the bit inversion cyclic right shift control signal given by the control signal generating unit 202 as shown in fig. 3E, performs bit inversion and cyclic right shift on the input data 8' b00001111 given by the data obtaining unit 201 according to the obtained bit inversion cyclic right shift control signal, obtains a binary number (bit inversion and cyclic shift result) obtained by performing bit inversion and cyclic shift on the input data as shown in fig. 3E, that is, an intermediate calculation result is 8' b10000111, and gives an intermediate calculation result 8' b10000111 to the post-processing unit 204.

S504: the post-processing unit 204 generates a mask code according to the shift type and the shift number, and post-processes the intermediate calculation result to obtain output data.

In some embodiments, the post-processing unit 204 generates a mask code according to the shift type and the shift bit number given by the data obtaining unit 201, and performs post-processing on the intermediate calculation result and the mask code bit and manner given by the butterfly network unit 203 to obtain output data.

Specifically, the post-processing unit 204 includes a mask code generating unit 204a and a bit and unit 204b.

The mask code generating unit 204a is configured to generate a mask code according to the shift type and the shift bit number given by the data acquiring unit 201, where the number of bits for generating the mask code is the same as the number of bits of the intermediate calculation result. When the shift type is cyclic shift, the binary values of the bits of the mask code are all 1, when the shift type is right shift, the values of the bits of the mask code front shift bit are all binary 0s from the high bit, the values of the rest bits are all binary 1 s, when the shift type is left shift, the values of the bits of the mask code rear shift bit are all binary 0s from the low bit, the values of the rest bits are all binary 1 s, i.e. the number of 0s is left shift bit from the low bit. For example, fig. 4B shows that, for 8-bit input data, the mask code generation unit 204 obtains a corresponding mask code according to the shift type and the shift number of bits. In some implementations, the data acquisition unit 201 may generate a corresponding mask code according to logic of a temperature code (thermo code).

And a bit and unit 204b, configured to bit-and the intermediate calculation result obtained by the butterfly network unit 203 and the mask code obtained by the mask code generating unit 204a, thereby obtaining a bit-inverted and shifted result, that is, an output result.

For example, the shift bit number is 5 bits, the shift type is right shift, and the bit and unit 204b inverts the bit and obtains the bit of the intermediate calculation result 8'b10000111 and the bit of the right shift result 8' b00000111 given by the mask code generating unit 204a and the inverse butterfly network unit 203.

It should be understood that the execution sequence of steps S501 to S504 is merely an example, and in other embodiments, other execution sequences may be adopted, and partial steps may be split or combined, which is not limited herein.

It will be appreciated that the bit-reversal shifting apparatus of the present application may be employed in a processor of an electronic device.

In order to facilitate understanding of the technical solutions of the embodiments of the present application, the following describes a hardware structure of the electronic device 100.

Further, fig. 6 illustrates a schematic structural diagram of an electronic device 100, according to some embodiments of the present application. The electronic device 100, as shown in fig. 6, includes one or more processors 101, a system Memory 102, a Non-Volatile Memory (NVM) 103, a communication interface 104, input/output (I/O) devices 105, and system control logic 106 for coupling the processors 101, the system Memory 102, the Non-Volatile Memory 103, the communication interface 104, and the input/output (I/O) devices 105.

Wherein: the Processor 101 may include one or more processing units, for example, may include a central Processor CPU (Central Processing Unit), an image Processor GPU (Graphics Processing Unit), a digital signal Processor DSP (DIGITAL SIGNAL Processor), a neural network Processor (Neural Network Processing Unit, NPU), a microprocessor MCU (Micro-programmed Control Unit), an AI (ARTIFICIAL INTELLIGENCE ) Processor, or a processing module or processing circuit of a programmed logic device FPGA (Field Programmable GATE ARRAY), or other Processor including a shift device for data bit inversion, and implementing the shift and data bit inversion according to a shift instruction, the specific Processor type is not particularly required herein.

In some embodiments, the processor 101 may include the aforementioned bit-reversal shifting device, so that in the case where the data needs to be bit-reversed and shifted, the bit-reversal shifting device is utilized to process the related instruction related to bit reversal and shift, and the device adopts a parallel structure, so that the calculation efficiency is high.

The system Memory 102 is a volatile Memory such as Random-Access Memory (RAM), double data rate synchronous dynamic Random Access Memory (Double Data Rate Synchronous Dynamic Random Access Memory, DDR SDRAM), or the like. The system memory is used to temporarily store data and/or instructions, for example, in some embodiments, the system memory 102 may be used to store the relevant instructions described above for inverting and shifting data bits, and so on.

Nonvolatile memory 103 may include one or more tangible, non-transitory computer-readable media for storing data and/or instructions. In some embodiments, the non-volatile memory 103 may include any suitable non-volatile memory, such as flash memory, and/or any suitable non-volatile storage device, such as a hard disk drive (HARD DISK DRIVE, HDD), compact Disc (CD), digital versatile Disc (DIGITAL VERSATILE DISC, DVD), solid state disk (Solid-state-STATE DRIVE, SSD), and the like. In some embodiments, the nonvolatile memory 103 may also be a removable storage medium, such as a Secure Digital (SD) memory card or the like.

In particular, the system memory 102 and the nonvolatile memory 103 may each include: a temporary copy and a permanent copy of instruction 107. The instructions 107 may include: execution by at least one of the processors 101 causes the electronic device 100 to implement the binary numbers provided by embodiments of the present application that implement bit reversing and shifting of data according to the instructions related to bit reversing and shifting of data.

The communication interface 104 may include a transceiver to provide a wired or wireless communication interface for the electronic device 100 to communicate with any other suitable device via one or more networks. In some embodiments, the communication interface 104 may be integrated with other components of the electronic device 100, e.g., the communication interface 104 may be integrated in the processor 101A. In some embodiments, electronic device 100 may communicate with other devices through communication interface 104.

Input/output (I/O) devices 105 may include input devices such as a keyboard, mouse, etc., output devices such as a display, etc., through which a user may interact with electronic device 100.

The system control logic 106 may include any suitable interface controller to provide any suitable interface with other modules of the terminal 100. For example, in some embodiments, the system control logic 106 may include one or more memory controllers to provide an interface to the system memory 102 and the non-volatile memory 103.

In some embodiments, at least one of the processors 101 may be packaged together with logic for one or more controllers of the system control logic 106 to form a system package (SYSTEM IN PACKAGE, SIP). In other embodiments, at least one of the processors 101 may also be integrated on the same Chip with logic for one or more controllers of the System control logic 106 to form a System-on-Chip (SoC).

It is to be understood that the configuration of the electronic device 100 shown in fig. 6 is merely an example, and in other embodiments, the electronic device 100 may include more or fewer components than shown, or may combine certain components, or may split certain components, or may have a different arrangement of components. The illustrated components may be implemented in hardware, software, or a combination of software and hardware.

Embodiments of the disclosed mechanisms may be implemented in hardware, software, firmware, or a combination of these implementations. Embodiments of the application may be implemented as a computer program or program code that is executed on a programmable system comprising at least one processor, a storage system (including volatile and non-volatile memory and/or storage elements), at least one input device, and at least one output device.

Program code may be applied to input instructions to perform the functions described herein and generate output information. The output information may be applied to one or more output devices in a known manner. For purposes of the present application, a processing system includes any system having a Processor such as, for example, a digital signal Processor (DIGITAL SIGNAL Processor, DSP), microcontroller, application SPECIFIC INTEGRATED Circuit (ASIC), or microprocessor.

The program code may be implemented in a high level procedural or object oriented programming language to communicate with a processing system. Program code may also be implemented in assembly or machine language, if desired. Indeed, the mechanisms described in the present application are not limited in scope by any particular programming language. In either case, the language may be a compiled or interpreted language.

In some cases, the disclosed embodiments may be implemented in hardware, firmware, software, or any combination thereof. The disclosed embodiments may also be implemented as instructions carried by or stored on one or more transitory or non-transitory machine-readable (e.g., computer-readable) storage media, which may be read and executed by one or more processors. For example, the instructions may be distributed over a network or through other computer readable media. Thus, a machine-readable medium may include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer), including but not limited to floppy diskettes, optical disks, read-Only memories (CD-ROMs), magneto-optical disks, read Only Memories (ROMs), random access memories (Random Access Memory, RAMs), erasable programmable Read-Only memories (Erasable Programmable Read Only Memory, EPROMs), electrically erasable programmable Read-Only memories (ELECTRICALLY ERASABLE PROGRAMMABLE READ-Only memories, EEPROMs), magnetic or optical cards, flash Memory, or tangible machine-readable Memory for transmitting information (e.g., carrier waves, infrared signal digital signals, etc.) using the internet in an electrical, optical, acoustical or other form of propagated signal. Thus, a machine-readable medium includes any type of machine-readable medium suitable for storing or transmitting electronic instructions or information in a form readable by a machine (e.g., a computer).

In the drawings, some structural or methodological features may be shown in a particular arrangement and/or order. However, it should be understood that such a particular arrangement and/or ordering may not be required. Rather, in some embodiments, these features may be arranged in a different manner and/or order than shown in the illustrative figures. Additionally, the inclusion of structural or methodological features in a particular figure is not meant to imply that such features are required in all embodiments, and in some embodiments, may not be included or may be combined with other features.

It should be noted that, in the embodiments of the present application, each unit/module mentioned in each device is a logic unit/module, and in physical terms, one logic unit/module may be one physical unit/module, or may be a part of one physical unit/module, or may be implemented by a combination of multiple physical units/modules, where the physical implementation manner of the logic unit/module itself is not the most important, and the combination of functions implemented by the logic unit/module is only a key for solving the technical problem posed by the present application. Furthermore, in order to highlight the innovative part of the present application, the above-described device embodiments of the present application do not introduce units/modules that are less closely related to solving the technical problems posed by the present application, which does not indicate that the above-described device embodiments do not have other units/modules.

It should be noted that, in the examples and descriptions of this patent, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises the element.

While the application has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the application.

Claims

1. A bit-reversal shift method, applied to an electronic device, comprising:

acquiring data to be processed;

Generating a shift control signal according to the shift type and the shift bit number of the data to be processed, and generating a bit inversion control signal according to the bit number of the data to be processed,

The generation process of the shift control signal comprises the following steps: the first 2 ^N-1 bit number of binary numbers after the first signal is circularly shifted left or circularly shifted right by J bits is used as a shift control signal corresponding to an N-th level network in a K-level network of an inverse butterfly network, wherein the first signal is a binary number with 2 ^N bits, the upper 2 ^N-1 bits of which are 0 and the lower 2 ^N-1 bits of which are 1, K is equal to or greater than N, J is a decimal number corresponding to the last N bit number in the binary numbers corresponding to the shift bit number, and

The generation process of the bit inversion control signal comprises the following steps: setting a second signal as a bit inversion control signal corresponding to an N-level network of the butterfly network, wherein the second signal is a binary number with 2 ^N-1 bits being all 1; performing exclusive OR operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal;

2. The method according to claim 1, wherein the butterfly network comprises a K-level network, the binary number of the data to be processed has 2 ^K bits, the shift control signals comprise K shift control signals respectively corresponding to the K-level network of the butterfly network, the bit number of the shift control signals corresponding to the N-level network of the butterfly network is 2 ^N-1 bits, the shift bit number is H bits, and the binary number corresponding to H is M, wherein K is greater than or equal to N; and

The first 2 ^N-1 digits of the binary number after the first signal is circularly shifted left or circularly shifted right by J digits are used as a shift control signal corresponding to an N-th network in a K-level network of an inverse butterfly network, and the shift control signal comprises:

Under the condition that the shift type is left shift or cyclic left shift, the first 2 ^N-1 bits of binary numbers after the first signal is cyclic left shift by J bits are used as shift control signals corresponding to an N-level network of the reverse butterfly network, wherein J is a decimal number corresponding to the last N bits of M;

and under the condition that the shift type is right shift or cyclic right shift, the first 2 ^N-1 bits of binary numbers after the first signal is cyclic right shift by J bits are used as a shift control signal corresponding to the N-level network of the butterfly network.

3. The method of claim 2, wherein the bit reversal control signal comprises K bit reversal control signals respectively corresponding to K-stage networks of the inverse butterfly network, and a bit number of the bit reversal control signal corresponding to an nth-stage network of the inverse butterfly network is 2 ^N-1 bits.

4. A method according to claim 3, wherein the bit-reversal shift control signal comprises K bit-reversal shift control signals respectively corresponding to K-stage networks of the inverse butterfly network; and performing exclusive or operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal, including:

And taking the result of exclusive OR operation of the shift control signal corresponding to the N-stage network of the butterfly network and the bit inversion control signal according to the bit as the bit inversion shift control signal corresponding to the N-stage network of the butterfly network.

5. The method according to any one of claims 1 to 4, wherein post-processing the result of the bit inversion and cyclic shift according to the shift type and the shift number of bits comprises:

setting a lower H bit of a result of the bit inversion and cyclic shift to zero in a case where the shift type is left shift and the shift bit number is H bit;

Setting the high H bit of the result of the bit inversion and cyclic shift to zero in the case that the shift type is right shift and the shift bit number is H bit;

in the case where the shift type is a cyclic right shift or a cyclic left shift and the shift bit number is H bits, the bits of the result of the bit inversion and cyclic shift are kept unchanged.

6. The method of claim 5, wherein, in the case where the shift type is a left shift and the shift bit number is H bits, setting the lower H bits of the bit-inverted and cyclic shifted result to zero comprises:

And performing bit AND operation on the bit-inverted and cyclic shift result and a first mask code, wherein the bit number of the first mask code and the bit number of the bit-inverted and cyclic shift result are P, and the low H bit and the high P-H bit of the first mask code are 0 and 1.

7. The method of claim 5, wherein, in the case where the shift type is a right shift and the shift bit number is H bits, setting the high H bits of the result of the bit inversion and cyclic shift to zero comprises:

and performing bit AND operation on the bit-inverted and cyclic shift result and a second mask code, wherein the bit number of the second mask code and the bit number of the bit-inverted and cyclic shift result are Q, and the high H bit and the low Q-H bit of the second mask code are 0.

8. A bit reversal shift device, comprising:

A control signal generating unit for generating a shift control signal according to the shift type and shift bit number of the data to be processed, generating a bit inversion control signal according to the bit number of the data to be processed, performing exclusive OR operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal,

The generation process of the shift control signal comprises the following steps: the control signal generation unit circularly shifts left or right the first signal by the first 2 ^N-1 bits of the binary numbers after J bits are circularly shifted, wherein the first signal is a binary number with the high 2 ^N-1 bits being 0 and the low 2 ^N-1 bits being 1 and 2 ^N bits, K is more than or equal to N, J is the decimal number corresponding to the last N bits in the binary numbers corresponding to the shift bit numbers, and

The generation process of the bit inversion control signal comprises the following steps: the control signal generation unit sets a second signal as a bit inversion control signal corresponding to an N-level network of the butterfly network, wherein the second signal is a binary number with 2 ^N-1 bits being all 1;

The butterfly inversion network is used for obtaining a bit inversion and cyclic shift result of the data to be processed according to the bit inversion shift control signal and the data to be processed;

9. The apparatus of claim 8, wherein the inverse butterfly network comprises a K-stage network, the binary number of the data to be processed has 2 ^K bits, the shift control signals comprise K shift control signals respectively corresponding to the K-stage network of the inverse butterfly network, the bit number of the shift control signal corresponding to the N-stage network of the inverse butterfly network is 2 ^N-1 bits, the shift bit number is H bits, and the binary number corresponding to H is M, wherein K is greater than or equal to N; and

The control signal generating unit circularly shifts left or circularly right the first signal by the first 2 ^N-1 bits of the binary number after J bits, and uses the first signal as a shift control signal corresponding to an N-th network in a K-th network of an inverse butterfly network, and the control signal generating unit comprises:

The control signal generating unit takes the first 2 ^N-1 bits of binary numbers after the first signal is circularly left shifted by J bits as a shift control signal corresponding to an N-level network of the butterfly network under the condition that the shift type is left shift or circularly left shift, wherein J is a decimal number corresponding to the last N bits of M;

And the control signal generating unit takes the first 2 ^N-1 bits of binary numbers after the first signal is circularly right shifted by J bits as a shift control signal corresponding to an N-level network of the butterfly network under the condition that the shift type is right shift or circularly right shift.

10. The apparatus of claim 9, wherein the bit reversal control signal comprises K bit reversal control signals corresponding to K-stage networks of the inverse butterfly network, respectively, and a bit number of the bit reversal control signal corresponding to an nth-stage network of the inverse butterfly network is 2 ^N-1 bits.

11. The apparatus of claim 10, wherein the bit-reversal shift control signal comprises K bit-reversal shift control signals respectively corresponding to K-stage networks of the inverse butterfly network; and the control signal generating unit performs exclusive or operation on the shift control signal and the bit inversion control signal to obtain a bit inversion shift control signal by:

the control signal generating unit exclusive-ors a shift control signal corresponding to an nth stage network of the butterfly network and a bit inversion control signal according to bits, and uses the exclusive-or result as a bit inversion shift control signal corresponding to the nth stage network of the butterfly network.

12. The apparatus according to any one of claims 9 to 11, wherein the shift bit number is H bit, and the bit number of the result of bit inversion and cyclic shift is Y; and

The post-processing unit performs post-processing on the result of the bit inversion and cyclic shift according to the shift type and the shift bit number by:

Performing bit and operation on the bit-reversal and cyclic shift result and a first mask code to obtain the bit-reversal and cyclic shift result under the condition that the shift type is left shift, wherein the bit number of the first mask code is Y, the low H bit of the first mask code is 0, and the high Y-H is 1;

performing bit and operation on the bit reversal and cyclic shift result and a second mask code to obtain the bit reversal and shift result under the condition that the shift type is right shift, wherein the bit number of the second mask code is Y, the high H bit of the second mask code is 0, and the low Y-H bit is 1;

and performing bit and operation on the bit-inverted and cyclic-shifted result and a third mask code to obtain the bit-inverted and cyclic-shifted result under the condition that the shift type is cyclic right shift or cyclic left shift, wherein the bit number of the third mask code is Y, and each bit of the third mask code is 1.

13. A processor, characterized in that it comprises a bit-reversal shifting device according to any one of claims 8 to 12.

14. An electronic device, characterized in that, the electronic device comprising the processor of claim 13.