TWI898521B - A method of adding binary strings and a circuit therefor - Google Patents

Abstract

Methods and logic circuits for adding two binary strings that remove the need to consider carry-over bit from an upstream adder by converting each addend into a generalized and optimized binary string. The format of this binary string extinguishes carry-over bits before the carry-over bits can propagate. The conversion removes all instances of neighbouring nonzero bits from the addends, such that there is at least one zero bit between every two nonzero bits. Any carry-over from adding up the addends is caught by the zero bit in the next higher position, and does not propagate. However, the conversion must preserve the values the addends for the addition to give the correction sum, by applying theEquivalence Principle.

Description

Method and circuit for adding binary characters

The present invention relates to a logic circuit for adding numbers in binary character format.

A processor typically contains logic circuits used to perform mathematical operations (i.e., addition, subtraction, multiplication, and division) on numbers in binary format. The most basic type of such circuit is the digital adder.

Figure 1 shows a general-purpose half-adder circuit consisting of an AND gate and an exclusive OR gate.

A half adder takes two single-bit inputs and produces two single-bit outputs, one of which is called the sum bit and the other is called the carry-out (C _OUT ) bit. If both input bits are 1, a carry is generated because the result is equal to 10.

Figure 2 is a simplified diagram of a full adder consisting of two half adders connected to each other. The first half adder passes the carry bit to the second half adder. The truth table of the full adder includes an additional input to include any carry bit from the sum of the previous less significant bits.

The output is the sum of the previous more significant bit and the carry, which is then connected to the carry input of the full adder. This allows cascaded full adders to add binary digits and pass the carry to the next more significant bit, a process known as the "ripple effect."

A series of four full adders can be combined to form a single 4-bit adder, as shown in Figure 3. The ripple effect from all the carries creates a delay. Each adder must wait for the carry signal before it receives all the inputs it needs to produce an output. In a chain of adders, each of these wait times creates an overall performance delay known as "propagation delay." Propagation delay causes full adders with larger numbers to add longer binary characters.

To reduce transmission delay, an improved circuit called a "carry lookahead adder" has been proposed, which places full adders in sequence, as shown in Figure 4. Essentially, a carry value is predicted by combining certain inputs of the full adder, and the full adder's output is fed into another logic element called a "carry lookahead" to propagate the carry signal to the downstream adder while the upstream adder is still calculating. There are two situations in which the downstream adder receives a carry bit: when the upstream adder generates a carry or propagates a received carry. These situations inform the downstream adder of the "carry generate" and "carry propagate" logic combinations. Furthermore, if a longer binary character that can be split into multiple bytes is present, the "group generate" and "group propagate" logic combinations may also occur.

In adders for longer binary characters, the use of a carry-lookahead adder can save exponential amounts of time, but this comes with the disadvantages of high cost and complex logic circuitry, further invoking the infamous Moore's Law of the relationship between cost and complexity. These economic and complexity constraints have also discouraged the industry from developing large-capacity adders.

Despite breakthroughs in lookahead carry logic, previous technologies had no way to escape the ripple effect, making addition operations from the least significant digit to the most significant digit necessary.

Therefore, there is a need in the art for a novel method and logic circuit design that can remove or mitigate any one or more of the aforementioned defects.

A first aspect of the present invention relates to a method for formatting a number in the form of a binary character into a format suitable for addition to another number in the same format and transmitting any carry value resulting from the sum of the addition. The method comprises: providing the number; providing a binary character representing the absolute value of the number; splitting the value of the binary character into a pair of binary sub-characters, wherein the sum of the pair of binary sub-characters x and y is equal to the value of the binary character; rearranging the plurality of zeros and non-zeros in the pair of binary sub-characters x and y so as to: (a) generate a pair of formatted binary sub-characters and , where the pair of binary subcharacters formatted and The sum of the binary subcharacters is equal to the value of the binary character; (b) in each formatted binary subcharacter and Each non-zero bit is separated from any other non-zero bit by at least one zero bit; and (c) in the pair of formatted binary subcharacters and The values of any bit position i in the

The present invention provides the possibility of generating a sum immediately, which can also compensate for the time required for operations before or after the addition of numbers, such as the time required to format binary numbers into a format suitable for addition and the time required to format the sum into the traditional two's complement binary format.

Preferably, one of the pair of binary subcharacters is the subtrahend and the other is the minuend, such that the sum of the pair of binary subcharacters is equal to the difference between the subtrahend and the minuend.

Alternatively, the step of rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y comprises steps (1), (2) and (3) arranged in the following order:

(1) Apply the following equation to remove any middle adjacent non-zero bits in the binary sub-character y:

and

(2) Apply the following equation to remove any pair of adjacent non-zero bits in the following specific order, changing the pair of binary subcharacters x and y from x=1, y=1 followed by x=0, y=1 to x=0, y=0 followed by x=1, y=0:

(3) Apply the following equation to remove any adjacent non-zero bits in the binary subcharacter x:

in, and Represents the binary sub-characters formatted in this pair and The value of the bit at position i.

Alternatively, the step of rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y comprises performing the following step (a) before performing the following step (b): (a) applying the following equation to the pair of binary sub-characters x and y:

where nw represents the pair of binary sub _- characters x and y; (b) applying the following equation to To obtain ,

in, and ; and Binary subcharacters representing different pairs and The value of the bit at position i.

Alternatively, the step of rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y comprises performing the following step (i) before performing the following step (ii):

(i) According to the following equation, the binary sub-characters are and Transformed into and :

(ii) Apply the following equations to x' and y' :

Typically, before performing the step of rearranging the plurality of zeros and non-zeros in the pair of binary sub-characters x and y, the non-zero bits in the same position of the sub-characters are first converted to zero bits.

The above technical features solve the problem of removing redundant bits, requiring this step only when outputting the sum required for subsequent repeated addition operations. This step of removing redundant bits from sub-characters is only applied in implementations that need to output the sum of the previous addition operation, so that the output sum can be optimized again. If redundant bits are not removed, the optimization process becomes more complicated due to the need to handle redundant bits.

Alternatively, the method of the present invention further comprises converting the pair of binary sub-characters and This technical feature can invert the content of a numeric sub-character, making the number negative and changing the method from an addition operation to a subtraction operation that removes the swapped content.

The second aspect of the present invention is to provide a logic circuit to which the method step (1) is applicable, comprising the following configuration:

In addition, the present invention also proposes a logic circuit to which step (2) of the method can be applied, which includes the following configuration:

In addition, the present invention also proposes a logic circuit to which step (3) of the method can be applied, which includes the following configuration:

In addition, the present invention also proposes a logic circuit that can be applied to steps (a) and (b) of the method, which includes the following configuration:

In addition, the present invention also proposes a logic circuit to which step (i) of the method can be applied, which includes the following configuration:

In addition, the present invention also proposes a logic circuit applicable to step (ii) of the method, which includes the following configuration:

In addition, the present invention also proposes a logic circuit that can convert the non-zero bits at the same position in sub-characters x and y into zero bits, which includes the following configuration:

A further aspect of the present invention provides an adder for binary characters, comprising a plurality of adder circuits arranged to achieve the following: each adder circuit can perform bit addition at the same position of two binary characters simultaneously with other adder circuits of the adder circuits; the adder circuit has the following configuration:

Preferably, the obtained bits are further simplified by changing all x _i = 1, y _i = 1 to x _i = 0, y _i = 0.

Typically, the adder further includes an input terminal for inputting each binary sub-word of each pair of the two pairs of binary sub-words, wherein the input terminal is supplied by an upstream circuit for generating the two pairs of binary sub-words; and each pair of binary sub-words has the following characteristics: ‧ No non-zero bit immediately follows another bit of the same value in the same binary sub-word; and ‧ No non-zero bit is in the same position in the other binary sub-word.

Typically, the adder further includes an output terminal configured to output each binary sub-word of a pair of binary sub-words, wherein the output terminal is connected to a downstream circuit for converting the pair of binary sub-words into a binary word representing the sum of the binary words.

Alternatively, before performing the bit addition, the contents of the two binary sub-characters in a pair of binary sub-characters are swapped. This technical feature can invert the contents of a numeric sub-character, making the number negative and transforming the method from an addition operation to a subtraction operation that removes the swapped numeric contents.

501, 503, 505, 507, 508, 509, 511, 513, 515, 517: Steps

To make the above and other objects, features, advantages, and embodiments of the present invention more readily apparent, the accompanying drawings are described as follows: FIG. 1 illustrates a prior art half adder; FIG. 2 illustrates a prior art full adder; FIG. 3 illustrates a prior art 4-bit pulse carry adder; FIG. 4 illustrates a prior art carry lookahead adder; FIG. 5 is a flow chart of two embodiments of the present invention; FIG. 6 illustrates a subroutine for converting two's complement binary characters into a generalized format usable in the embodiment of FIG. 5. FIG7a is a circuit diagram of the subcircuit in FIG6; FIG7b illustrates how the circuit in FIG7a generalizes binary characters; FIG8 illustrates a high-level subcircuit for the implementation of FIG5 by rearranging, adding, or removing zero and non-zero bits from the binary characters output by the semi-optimized subcircuit in FIG6; FIG9 illustrates the three subcircuits represented by the subcircuit in FIG8 and their arrangements; FIG10 is a diagram of one of the three subcircuits in FIG9; and FIG11 is a diagram of the nine subcircuits in FIG10. Figure 12 is the logic circuit diagram for each sub-circuit in Figure 11; Figure 13 is the circuit diagram for another of the three sub-circuits in Figure 9; Figure 14 is the logic circuit diagram for each of the sub-circuits in Figure 13; Figure 15 is the truth table for the logic circuit in Figure 13; Figure 16 is the circuit diagram for another of the three sub-circuits in Figure 9; Figure 17 is the logic circuit diagram for each of the sub-circuits in Figure 16; Figure 18 is the truth table for the logic circuit in Figure 16; Figure 19 provides the logic circuit diagram for the flow chart in Figure 5. Figure 20 is a circuit diagram of the subcircuit in Figure 19; Figure 21 illustrates the adder subcircuit within each subcircuit unit of the subcircuit in Figure 20; Figure 22 illustrates the circuit logic used to construct the subadder of the adder subcircuit in Figure 21; Figure 23 is a truth table for the logic circuit in Figure 22; Figures 24a-24g are a series of diagrams showing how to perform calculations simultaneously for each position of the adder output subword (such as the output shown in the subcircuit in Figure 19); Figure 25 is a circuit diagram used to add the subword in Figure 19. Figure 26 is the logic diagram of the subcircuit in Figure 25; Figure 27 is the truth table for the logic circuit in Figure 26; Figure 28 is the truth table for Figure 26; Figure 29a illustrates how to convert a 4-bit generalized binary number into a 5-bit two's complement binary number; Figure 29b is a deconversion circuit similar to the carry lookahead circuit for generation, transfer, and summation; Figure 30a is another variation of the flowchart in Figure 5; Figure 30b uses FIG30c is a truth table of the logic circuit of FIG30b; FIG31 shows a binary character output by the circuit used for full optimization in FIG6, in which the zero and non-zero bits are rearranged or changed for use in a high-level subcircuit of another embodiment in FIG5; FIG32 shows a subcircuit within the block circuit diagram of FIG31; FIG33 is a subcircuit diagram of each circuit unit in the subcircuit of FIG32; FIG34 is a logic circuit of the subcircuit of FIG33; FIG35 is a high-level subcircuit of FIG36. 3 (Table 6a); FIG. 36 illustrates the binary character output by the semi-optimized circuit of FIG. 6 after rearranging, adding, or removing zero and non-zero bits for use in another sub-circuit of an embodiment of FIG. 5; FIG. 37a is the logic circuit of the sub-circuit of FIG. 36; FIG. 37b is the truth table for step (a) of the first variation of the process of FIG. 36 (Table 6b); FIG. 37c is the truth table for step (b) following the truth table 6b for step (a) of FIG. 37b (Table 6c); Figure 38 is a truth table for the subcircuit in Figure 36; Figure 39 illustrates another subcircuit in one embodiment of Figure 5 by rearranging, adding, or removing zero and non-zero bits from the binary character output by the semi-optimized circuit in Figure 6; Figure 40 is a logic circuit for the subcircuit in Figure 39; Figure 41 is a truth table for the subcircuit in Figure 39; Figure 42 is a subcircuit diagram for processing the output of the subcircuit in Figure 39; Figure 43 is a logic circuit for the circuit in Figure 42; and Figure 44 is a truth table for the subcircuit in Figure 42.

One embodiment of the present invention relates to a multi-bit adder for adding binary characters (i.e., a summand and an addend), wherein two bits in the same significant position, or individual characters in the same position of two binary characters, are added simultaneously during multiple simultaneous operations. This embodiment primarily handles addition, but can also be modified to handle subtraction.

This embodiment also relates to logic circuitry that can perform pre-processing on a summand and addend, converting the formats of the summand and addend into a format suitable for direct addition via parallel operations. This conversion comprises two steps: a generalization step and an optimization step. Converting either the summand or addend produces a pair of binary characters referred to herein as "generalized" and "optimized," the characteristics of which are described in detail below. These binary characters are in a format where no carry bit needs to be continuously propagated to a more significant bit, or where the carry bit does not persist but terminates after several bits downstream. In practical operations, these binary characters can be considered to eliminate or terminate the carry bit, thereby alleviating the need to continuously propagate the carry bit.

Generally speaking, the optimization algorithm removes all nonzero bits adjacent to the augend and addend, ensuring that there is at least one zero bit between every two nonzero bits. Any carry resulting from the addition of the augend and addend is captured by the next nonzero bit in the next significant digit and is therefore not propagated. However, the optimization algorithm also needs to apply the so-called "equivalence principle" to preserve the original values of the augend and addend so that the correct sum is still obtained after addition.

Figure 5 is a flowchart of the five-step process of this embodiment. Each step is performed by a different logic circuit. The logic circuit diagram for each step is indicated in the text box next to the flow chart. Other circuits with equivalent functions to these logic circuits can also be designed to implement this embodiment in a digital processor.

In the first step 501, the augend and addend in two's complement format are provided. Note that the augend and addend may also be collectively referred to as "addends" herein.

In the second step 503, the addend in binary character format is converted into what is referred to herein as a "generalized binary character format." This converted binary character is referred to as a "generalized binary character."

In the third step 505, the generalized binary character is processed using a process called "optimization" to remove all surrounding non-zero bits to prevent carry bits from being propagated. After the generalized binary character is optimized, an "optimized and generalized binary character" is generated.

The above optimization process can be implemented using any algorithm and logic circuit designed based on the concepts described in the following paragraphs. However, there are two approaches: one is called "full optimization" and the other is called "semi-optimization."

In the fourth step 507, the addend and augend formatted as optimized and generalized binary characters are input into the adder. The output sum is a generalized binary character and may include adjacent non-zero bits, and therefore is no longer an optimized character.

In the fifth step 509, the sum is converted from a generalized binary character to a two's complement binary character.

Numbers processed by logic circuits always exist in the form of bit characters (i.e., binary characters), with each bit value being either 1 (non-zero) or 0. Generally speaking, binary characters can represent positive or negative values. Binary characters representing positive values don't have special names, but if a binary character represents a negative value, it must be in two's complement binary format. This is because it doesn't take a binary character that can represent a positive value, and for better explanation, only one bit of the binary digits is used as the negative sign.

For example, the number 1 is 0000 0000 0000 0001 in 16-bit binary format. However, the number -1 is 1111 1111 1111 1111 in two's complement binary format with a negative sign. Furthermore, the number 27 is 0000 0000 0001 1011 in 16-bit binary format, but the number -27 is 1111 1111 1110 0101 in two's complement binary format with a negative sign.

For the sake of accuracy, all traditional binary characters are in two's complement binary format. Therefore, for convenience, all binary characters representing positive values are not called two's complement binary characters.

Generalized binary characters

The subcircuit shown in Figure 6 is used to perform generalized processing on binary characters. Figure 7a is a diagram of its logic circuit components.

Feed each of the two adders into the circuit components of Figure 7a. If the most significant bit is non-zero, the addend is a negative number in two's complement binary format. In this case, as shown in Figure 7b, the non-zero bit in the most significant bit is 1, which is transferred to the most significant bit as sub-character y . The values of the other bits of the addend are shifted to sub-character x . Therefore, the addend 1000 0011 is split into the first binary character 0000 0011 and the second binary character 1000 0000. To distinguish them, these split binary characters are called sub-characters. The first sub-character 0000 0011 is represented by x , and the second sub-character 1000 0000 is represented by y . The value of each sub-character is read in the same way as any binary character. Thus, the two binary subcharacters represent the two values derived from the value of the addend, with xy being equal to the value of the addend. Typically, the subcharacters have the same character length as their original addend.

Among many pairs of x and y subcharacters, some pairs contain both subcharacters containing non-zero bits, separated by at least one zero bit. The process of identifying such subcharacters is called "optimization." Optimized addend subcharacters can be added directly based on their bit positions, and any carry from the addition of two non-zero bits is captured by an adjacent, more significant zero bit, preventing ripple effects on the bits.

Preferably, x represents a positive number, and y represents another positive number to be subtracted from x . In this case, it's more accurate to say that x is the subtrahend, and y is the minuend. Subtracting y from x yields the value of the original addend. In other words, by applying the equivalence principle, the values of the original addends confirm that rearranging the zero and non-zero bits in x and y is acceptable and does not change the sum.

More specifically, the equivalence principle states that any m( 1) A subcharacter of 1 can be represented by a non-zero bit 1 (in the most significant position) and a subcharacter separated by m-1 zeros. (less significant bits) to replace. Similarly, any m( 1) The sub-characters can be represented by a bit (in the more significant position) and a 1 separated by m-1 zeros (in the less significant position). Here, 1 represents the "1" in the x sub-character, and Represents the "1" in the y subcharacter, which is about to be subtracted from the x subcharacter.

Avoid calling y a negative number. This is because true negative numbers must be represented in two's complement binary format, which contains multiple adjacent non-zero bits, and the optimizer avoids these bits. The addend is considered "generalized" because the value of the addend is no longer represented by a specific, single binary character. In other words, for characters of the same length, the arrangement of zero and non-zero bits in the pair of sub-characters can be changed or rearranged as long as the sum of the two sub-characters remains equal to the addend value. This is the effect of the equivalence principle under each variation of the generalization process. However, the character length of the sub-characters x and y will be one bit longer than the length of the original non-zero value of the addend. This makes the value of x one bit larger, allowing x to be a subtraction. Subtracting an appropriate value of y from x returns the original value of the addend.

The concepts and circuits used in the present invention for adding two generalized binary numbers can be modified to perform subtraction of a generalized binary number (i.e., the minuend) from another generalized binary number (i.e., the subtraction). After the binary numbers are generalized, only the contents of the minuend (x ) and y need to be swapped, so that the adder operation becomes a subtraction. That is, the operation of subtracting the minuend from the subtraction becomes the operation of adding the subtraction to the modified minuend (with the contents of x and y swapped).

The following paragraphs are restricted to the case where x is a subcharacter with the decrementing role, and y is a subcharacter with the decremented role. For convenience, the following abbreviations are used when describing a non-zero bit in y : (1 has a dash through it) represents any non-zero bit in the y subcharacter, or -1 because y is being decremented (this second abbreviation is used in the actual tables in this manual; please do not confuse it with the current abbreviation).

Therefore, x = 0001 0000 and y = 0000 0001 can be written in a single line as follows: Here, at the rightmost character position Indicates that a specific bit in the y subcharacter has a non-zero value. Similarly, a bit in the x subcharacter that has a 1 indicates that there is a non-zero value at that specific bit.

Here's an example of how to generalize the number 31. The two's complement binary format of the number 81 in 8-bit binary format is 0001 1111. When generalizing, 0001 1111 is re-expressed as two sub-characters, i.e., x = 0001 1111 and y = 0000 0000. Applying the equivalence principle, x = 0010 0000 and y = 0000 0001. In the recommended abbreviation, the two sub-characters can be written as ,in The y subcharacter has a 1 at the rightmost bit, and 0010 0000 is in the x subcharacter with a 1 at the 6th bit position. Since 0010 0000 is 32 (decimal) and 0000 0001 is 1 (decimal), xy = 32 - 1 = 31 in decimal.

Here is an example of how to generalize the number 23. The two's complement binary format of the number 23 in 8-bit binary format is 0001 0111. When generalizing, 0001 0111 is re-expressed as two sub-characters, that is, x = 0001 0111 and y = 0000 0000. After applying the equivalence principle, x = 0010 1000 and y = 0001 0001. In the recommended abbreviation, the two sub-characters can be written as Since 0010 1000 is 23 (decimal system) and 0001 0001 is 17 (decimal system), xy = 40 - 17 = 23 in the decimal system.

Here is an example of how to generalize the number -23. The two's complement binary format of the number -23 in 8-bit binary format is 1110 1001 (note that the "1" in the most significant digit represents a negative number). When generalizing, according to Figures 6 and 7, 1110 1001 is re-expressed as two sub-characters, that is, x = 0110 1001 and y = 1000 0000. After applying the equivalence principle, x = 0010 1000 and y = 0001 0001. In the recommended abbreviation, the two sub-characters can be written as Since 0110 1001 = 105 and 1000 0000 = 128 (decimal system), xy = 105 - 128 = -23 in the decimal system.

The concept of one subcharacter being the subtraction and the other being the subtracted can be represented as follows: after the two numbers to be added are converted to generalized binary character format, four subcharacters appear: x ₁ , y ₁ , x ₂ , and y ₂ . Mathematically, an n-bit binary character can be written as follows:

in, and ，i=0,1,...,n-1。<,> represents a set of possible values of the variable. Note that, as mentioned above, is an abbreviation for a non-zero bit in a negative subcharacter. The weight of each bit in the binary subcharacter is the same or a positive integer power of 2. Therefore, n _w can be written as

The domain _of nw covers the range from -( ²ⁿ -1) to ²ⁿ -1.

Semi-optimal generalized binary characters n _w

Generalizing any addend to generate subcharacters simply involves splitting the addend's value into two binary subcharacters. Optimization involves removing all non-zero bits surrounding the subcharacters, changing the position and number of zeros and non-zeros within the subcharacters, and applying the equivalence principle so that the sum of the subcharacters equals the addend's value.

A better optimization strategy is called "semi-optimization" processing, as opposed to "full optimization" processing.

Applying a "semi-optimization" to two sub-characters of a generalized addend produces two sub-characters with the following characteristics: 1. Every two non-zero bits in each sub-character are separated by at least one zero bit; 2. A non-zero bit is immediately followed by another non-zero bit if a non-zero bit is in one sub-character and another non-zero bit is in another sub-character; 3. There is no limit on the number of zero bits.

Semi-optimal generalized binary character examples and negative number examples: Semi-optimal format of two sub-characters:

‧In the same sub-character, no non-zero bit immediately follows another bit of the same value

‧There is no non-zero bit at the same position in another sub-character

Semi-optimal form of two sub-characters:

‧In the same sub-character, no non-zero bit immediately follows another bit of the same value

‧Another sub-character has no non-zero bit at the same position

‧In another sub-character, there may be a non-zero bit immediately adjacent to the next position

Semi-optimal form of two sub-characters:

‧In the same sub-character, no non-zero bit immediately follows another bit of the same value

‧There is no non-zero bit at the same position in another sub-character

‧In another sub-character, there may be a non-zero bit immediately adjacent to the next position

In other words, a pair of semi-optimal binary subcharacters is such that in each obtained semi-optimal positive x subcharacter and negative y subcharacter, all non-zero digits are separated by at least one zero. Alternatively, there are no two consecutive 1s (in all x subcharacters) or two consecutive (in all y subcharacters), but before or after the 1, there can be a ,vice versa.

The following is an example of semi-optimization, where the sub-character is not optimized because there are two non-zeros in the first and second smallest bit positions.

The x and y sub-characters above are derived from the number 3, which is 0000 0011 in two's complement binary format. Under the principle of equivalence, the sub-characters are converted to the following using a semi-optimization process: the x and y sub-characters of each addend are optimized separately without reference to the other addend.

The above abbreviation is .

Alternatively, re-express the two sub-characters in the following way so that x-y = 5-2 = 3.

The above abbreviation is .

In other implementations, it may be possible to optimize 011 to .

Here is a second example of semi-optimization:

The first possible semi-optimization is the following sub-character 8-1=7.

The above abbreviation is .

The second possible semi-optimization is the following sub-character 9-2=7.

The above abbreviation is .

Here is a third example of semi-optimization:

The best example of semi-optimal processing is as follows:

The above abbreviation is .

The three semi-optimization processing examples above show that for any given input, multiple possible semi-optimal sub-characters can be generated.

There are many ways to semi-optimize a pair of generalized characters representing a single numeric value. The most straightforward approach is to algorithmically manipulate the bits of each sub-character pair. In this implementation, the bit manipulation algorithm operates in a manner similar to Booth's multiplication algorithm, which shifts bits to produce the product of a binary multiplicand and a binary multiplier. Booth's multiplication algorithm is used to perform multiplication on a single binary character. In contrast, the bit manipulation used in this implementation does not produce a product or sum, but rather removes the non-zero bits surrounding each sub-character.

However, the bit manipulation algorithm used in this embodiment must adhere to the equivalence principle, so that a pair of sub-characters representing a numerical value can only be transformed into another pair of sub-characters (with different numerical values and a different arrangement of zero and non-zero bits) while still retaining the same numerical value. The desired transformed pair of sub-characters has no non-zero bits surrounding the x and y sub-characters and also exhibits the properties of a pair of semi-optimized sub-characters.

Figure 8 shows a subcircuit diagram for semi-optimizing an 8-bit generalized binary character into a 9-bit semi-optimized generalized binary character. Figure 9 shows that the circuit block in Figure 8 consists of three subcircuits, labeled Vin8o08-31, Vin8o08-32, and Vin8o08-33.

Figure 10 shows the details of Vin8o08-31, which is composed of multiple basic sub-circuits as shown in Figure 11.

Figure 13 shows the details of Vin8o08-32, which is composed of multiple basic sub-circuits as shown in Figure 14.

Figure 16 shows the details of Vin8o08-33, which is composed of multiple basic sub-circuits as shown in Figure 17.

Preferably, the digitization block circuit of FIG8 can be used to perform semi-optimization on each bit position in the sub-character at the same time, which includes the following steps: Semi-optimization step 1: related to the sub-circuit Vin8o08-31, this step can utilize the equality principle that meets the following equation, the logic of the truth table 1 of FIG12 and the logic circuit of FIG11 to convert any character Removed:

In other words, applying the equation to the pair of x and y sub-characters removes the non-zero values around the y sub-character. As mentioned in the previous paragraph, the truth tables of this specification use another simplified symbol Z to represent the pair of x and y sub-characters. In detail, generalized binary characters can be written as binary numbers, where one character is represented by a positive binary number, the other character is represented by a negative binary number, and the numbers between the two characters are 0 or 1. In general, the n-bit generalized binary number nw can be written _as :

in , x _i =〈0,1〉 and y _i =〈0,1〉, where i =0,1,..., n -1. Here,

The weight of each element is the same or a positive power of 2. Therefore, z _w can also be expressed as follows:

The domain _of zw covers the range from -( ²ⁿ -1) to ²ⁿ -1. This generalized binary number system can also be used for two's complement binary numbers.

Semi-optimization step 2: related to sub-circuit Vin8o08-32, this step can use the equality principle that meets the following equations, the logic of truth table 2 in Figure 15 and the logic circuit in Figure 14 to transform any cluster Transformed into 1:

Semi-optimization step 3: Associated with subcircuit Vin8o08-33, this step removes any character 1 by using the equality principle that satisfies the following equation, the logic of truth table 3 in Figure 18, and the logic circuit in Figure 17:

in, and An optimized and generalized binary character representing half of an addend.

In other words, applying the equation to the pair of x and y subcharacters removes the non-zero values surrounding the x subcharacter.

The order in which steps 1, 2, and 3 are performed is very important and must be followed strictly.

Each generalized binary character of the addend to be added is processed through the semi-optimization steps 1, 2, and 3 above to generate two pairs of semi-optimized generalized binary sub-characters.

Add optimized and generalized binary substrings

Next, two pairs of 9-bit half-optimized generalized binary subwords x ₁ , y ₁ , x ₂ , y ₂ are fed into the adder shown in FIG. 19 and added together.

FIG21 is a detailed diagram of one of the sub-circuits in FIG20. The input of this adder is the four sub-words of the two pairs of half-optimized and generalized addends, and the output is a 10-bit generalized binary word having an x- output sub-word and a y -output sub-word.

Figure 22 shows the logic circuit of the adder. Two such adders (as shown in Figure 21) are required to produce a generalized sum that includes two sub-characters.

However, the 4-bit input of the logic circuit in Figure 22 will only produce one output bit. Similarly, the circuit in Figure 21 shows an 8-bit input.

In fact, only two corresponding bits of the addends (one from each sub-word, x ₁ and x ₂ ) are added together to produce an output bit, X. Similarly, two corresponding bits from each sub-word, y ₁ and y ₂ , are added together to produce an output bit, Y. Output bits X and Y form the sum of the generalized binary word. The adder takes two adjacent bits at positions i and i-1, because the semi-optimization process ensures that one of these bits is zero. These inserted zero bits terminate the carry value so that it is not propagated further.

Furthermore, because the semi-optimization ensures that bits immediately adjacent to non-zero bits are always zero, including an extra bit adjacent to the addition does not affect the output value.

There are 10 subcircuits in Figure 20, each of which is shown in Figure 21. The subcircuits in Figure 20 operate simultaneously because the logic gates in all circuits respond to a high voltage applied to the input wire.

There is no carry value propagation or stripping from one adder to another. Each adder simply calculates the output of the corresponding bit by taking in the input value of the relevant position, which is independent of other adders in the circuit.

Because there are no carry values to propagate or strip in a full-length binary input character, upgrading the schematic simply involves adding more adder subcircuits to the existing configuration.

Figures 24a through 24g illustrate how to add the four optimized, generalized binary characters of two addends. Up to this point, all the processing is intuitive. Each adder subcircuit in Figure 20 simply takes in the associated input bits and produces the output bit at the specific position of the input character. Similarly, the processing illustrated in Figures 24a through 24g is performed synchronously.

In Figures 24a through 24g, the sub-characters being added are 6 bits long, resulting in a 7-bit output. The implementation is the same for 7-bit and 8-bit character lengths. This article arbitrarily uses 6 bits for illustration purposes.

Each adder in FIG. 20 adds the bit at a predetermined position in _the x1 sub-character to the bit at a predetermined position in _the x2 sub-character and generates the output bit value for the same position in the X sub-character. Similarly, the output bit value for the same position in the Y sub-character is generated.

Figure 24a is for position i, starting at i=0. Add _{the x10} bits of _the x1 subcharacter and _{the x20} bits of _the x2 subcharacter. Similarly, add _{the y10} bits of _the y1 subcharacter and _{the y20} bits of _the y2 subcharacter. However, at position i=0, the output for the x0 _subcharacter and _the y0 subcharacter is zero.

This is because the logic circuit in Figure 22 requires two bits from the x1 _sub -character, two bits from the x2 _sub -character, two bits from the y1 _sub -character, and two bits from the y2 _sub -character.

Figure 24b is for i = 1. _The outputs of the truth table in Figure _{23 are} provided using _{bits x10} and x11 of the x1 sub _- character, _{bits x20} and x21 _{of the} x2 sub-character, bits y10 and _y11 of the y1 _{sub -character, and bits y20} and y21 _of the y2 sub-character.

Figure 24c is for i = 2. Add _bits x11 and _x12 of _the x1 subcharacter and bits x21 _and x22 of _the x2 subcharacter to produce the output subcharacter's value _x2 . Apply the _same operation to _the y1 and y2 _{subcharacters} to produce the output subcharacter's value _y2 .

Figure 24d is for i = 3. Add _bits x12 and _x13 of _the x1 subcharacter and bits x22 _and x23 of _the x2 subcharacter to produce the output subcharacter's value _x3 . Apply the _same operation to _the y1 and y2 _{subcharacters} to produce the output subcharacter's value _y3 .

Figure 24e is for i = 4. Add _bits x13 and _x14 of _the x1 subcharacter and bits x23 _and x24 of _the x2 subcharacter to produce the output subcharacter's value _x4 . Apply the _same operation to _the y1 and y2 _{subcharacters} to produce the output subcharacter's value _y4 .

Figure 24f is for i = 5. Add _bits x14 and _x15 of _the x1 subcharacter and bits x24 _and x25 of _the x2 subcharacter to produce the output subcharacter value _x5 . Apply the _same operation to _the y1 and y2 _{subcharacters} to produce the output subcharacter value _y5 .

Figure 24g is for i = 6. Add _{the x15} bits of _the x1 subcharacter and _{the x25} bits of _the x2 subcharacter to produce the output subcharacter's value of _x6 . Apply the same operation to _the y1 and y2 _{subcharacters} to produce the output subcharacter's value of _y6 .

Since the 4-bit input from the two generalized binary digit sub-characters sums to one bit (also in the generalized format), the result is two output bits, forming an output sum of two sub-characters (also in the generalized format).

In this section, a semi-optimized generalized binary character addition algorithm is presented. The sum is denoted by N _w , and the semi-optimized summand and addend are denoted by and express.

The addition method is demonstrated in the following steps: (a) Add the positive and negative components using the following equation:

The logic truth table and logic circuit are provided in Table 12 of Figure 23 and Figure 22, respectively.

Convert two sub-characters into a single binary character in two's complement format

The two sub-characters (X and Y), representing the sum of the addend and augend (represented by the x and y sub-characters, which are the output of the next-level circuit), must be converted into traditional binary format (i.e., a single binary character in two's complement format) before they can be read and used by other control programs.

The general deconversion logic is similar to that of a traditional carry-lookahead adder, but the detailed structure is not identical. The subcircuit in Figure 25 replaces the propagation bit, generator bit, and final sum bit in a traditional carry-lookahead adder. Figure 26 shows the corresponding logic within the subcircuit, while Figures 27 and 28 show Truth Table 4 and Truth Table 5a, respectively.

A pair of 8-bit subwords requires 8 subcircuits. This is because each subcircuit can only service two bits in the same position in two subwords, that is, one bit in the x subword and another bit in the y subword, both bits in the same position.

If the adder output reads as follows:

x - y = 84 - 17 = 67

The first step in deconversion is to replace all non-zero bits in the same position in both sub-characters with zeros. These non-zero values cancel each other out. See how bit 4 of both sub-characters above is 1, while the sub-character below has two bits removed.

x - y = 68-1=67

The following deconversion circuit can be used to combine these two subwords into a single binary character:

Mathematically, convert the (n-1)-bit sub-character of Z _w into an n-bit two's complement binary character The method involves using initial bit reduction to replace x _i = y _i = 0 if x _i = y _i = 1.

Next, a conventional adder circuit is used to add the two sub-words that have undergone the above processing. The look-ahead carry logic of the well-known carry-lookahead adder is modified to be suitable for the deconversion requirements of this paper. That is, the following logic is used to replace _the traditional generation ( gi ) _and transmission ( pi ):

g _i = y _i (8b)

The truth logic associated with the conversion to two's complement values and the generation and propagation of outputs is shown in Truth Table 4 in Figure 27. Specifically, Truth Table 4 describes the conditions under which a carry value is predicted for the input bit combination that will generate a carry value and the carry value that will be propagated. However, it should be noted that this generation and propagation, as well as the group generation and propagation processes, are similar to the lookahead adder circuit's outputs from the X and Y sub-characters, and are a series of operations. As the number of bits increases, the operations become more complex. Therefore, the conversion process used to generate two's complement values is not a parallel operation.

The final stage sum circuit can be represented by the following equation:

Y _n = c _n (9b)

When the "carry" of each bit is carried forward, the carry is generated by the improved "carry-lookahead circuit".

The truth logic of truth table 5a in Figure 28a is related to the "final stage sum" logic used to convert the sub-character pairs of the sum into the normal two's complement binary format for i = 0, 1, 2, ..., ( n -1), whose logic circuit is shown in Figure 26.

Figure 29a illustrates the process of converting a 4-bit generalized binary number into a traditional 5-bit two's complement binary number. As shown in Figure 29b, two sub-characters of the 4-bit generalized binary character are provided to generate the improved generation and transmission bits. Each bit of the two sub-characters is sent as one of the inputs to a corresponding position in the logic circuit array of Figure 26.

The output of the array in Figure 29b will be a 5-bit single-digit traditional two's complement number, where the leftmost digit represents the sign of the binary number. If the sum is positive, the leftmost bit is "0", otherwise it is "1" if the sum is negative. This is the concept of a traditional two's complement number. Note that converting a generalized binary number will produce a traditional two's complement number with one extra bit, and this extra bit represents the sign of the binary number.

Therefore, if the sum is negative, the logic circuit in Figure 29b can also restore the sign of the sum value by converting the binary output characters to two's complement format.

Deconvert the two sub-characters only if necessary before any operations requiring addition are completed.

As mentioned above, the final step in this embodiment is deconversion, which involves adding the x sub-character and the y sub-character using a typical full addition algorithm. The modified carry-lookahead algorithm described above is only one of many possible approaches. However, as shown in FIG. 30a , step 509 may be paused until all operations in steps 511 , 513 , and 515 that require outputting the sum of the addends for further addition and subtraction operations are completed (as determined in step 508 ). At this stage, the memory allocated for the generalized binary character (i.e., the final sub-character pair) is dedicated memory.

However, for each subsequent addition, when adding a new number (also in generalized binary format) to the output of the previous addition (in generalized binary format), both numbers must be optimized. In particular, outputting a single addend will cause it to lose its optimized format, even if the output remains in generalized format. To optimize the output value of the previous addition, the pair of binary characters must first be processed to remove redundant bits.

Removing redundant bits from a generalized binary subcharacter can be expressed as follows:

"Redundant bits" appear in pairs and are defined as a non-zero bit position in the x subcharacter and a non-zero bit position in the y subcharacter. These non-zero bits have no other meaning except that they cancel each other out when they are in the same position in the x and y subcharacters.

In the following example of the x subcharacter and the y subcharacter, the first bit of each subcharacter has a non-zero value. These are redundant bits because they are non-zero bits in the same position in both subcharacters.

Therefore, before optimization, we must convert the non-zero values to zero to remove these redundant bits, and obtain the following:

Therefore, redundant bits can be removed simply by converting them to zero without affecting the represented value and still following the equivalence principle.

Therefore, in the flowchart of Figure 30a, if there are many numbers to be added, the sum generated by the previous round of additions must first be processed to remove redundant bits (step 517) before optimization (i.e., step 515). The new addend to be added to the previous round of additions must also be optimized in step 515. There is no need to remove redundant bits from the new addends because the generation of redundant bits is already avoided when the addends are converted to the generalized binary format.

The truth logic for removing redundant bits is shown in truth table 5b in Figure 30c and the logic circuit in Figure 30b.

Second Implementation Using Fully Optimized Generalized Binary Subcharacters

As shown in the flowchart of Figure 5, an alternative to the semi-optimization process for removing non-zero neighbors is called "full optimization" processing, see Figures 31, 32, 33, and 34.

A sub-character that meets the fully optimized conditions must also meet the semi-optimized conditions.

However, the reverse is not true. Full optimization is a subset of semi-optimization.

Figure 31 shows a high-level subcircuit used to fully optimize generalized binary subcharacters. Figure 32 is a circuit diagram of the multiple interconnected subcircuits that support the high-level subcircuit in Figure 31. Figure 33 shows the circuit diagram of each interconnected subcircuit in Figure 32. Figure 34 shows the logic circuit of Figure 33.

Each pair of sub-characters generated by the generalized binary character representing the addend, once fully optimized, will meet the following requirements: ‧ The value of the sub-characters after addition is equal to the addend, and the initial value of each sub-character is split from the addend; ‧ The conditions for fully optimized sub-characters are met, which include: ‧ There are no two adjacent non-zero bits in the same sub-character, that is, any two non-zero bits in the same sub-character must be separated by at least one zero bit; ‧ There will be no two adjacent non-zero bits, even if the two non-zero bits are in different sub-characters

A pair of fully optimized generalized binary sub-characters is shown below. That is, the following is a pair of fully optimized sub-characters:

Two fully optimized x and y sub-characters

‧No two adjacent non-zero bits exist in the same or different sub-characters

‧There is no non-zero bit at the same position in another sub-character

If two sub-characters are aligned by bit position and placed side by side, there will be 5 zero bits around any non-zero bit. Unless the first or last position in a sub-character is a non-zero bit, there will only be 3 zero bits around the non-zero bit.

The following is an incorrect and negative example of a sub-character that is not fully optimized. This is because two non-zero bits cannot appear in two adjacent positions, even if they are in different sub-characters. This is the difference between a fully optimized program and a semi-optimized program. Semi-optimization allows two non-zero bits to appear in adjacent positions as long as they are in different sub-characters.

Two sub-characters x and y that are not fully optimized

In other words, in a fully optimized generalized binary character sub-character, there is at least one zero bit between any two non-zero bits. Conversely, a semi-optimal algorithm ensures that there is at least one zero bit between every two non-zero bits in the same sub-character ( i = ,1,..., n ). Optimized algorithms must also adhere to the "equivalence principle."

The circuits in Figures 31, 32, 33, and 34 are designed based on an algorithm that can completely optimize a pair of sub-characters. This algorithm can also be expressed mathematically.

The following mathematical formula is relevant to executing the full optimization algorithm for Figures 31, 32, 33, and 34:

The horizontal lines above x _i and y _i represent negative values, and the absolute values are represented by binary Boolean variables.

Negative numbers

The truth values for the logic circuits in Figures 31, 32, 33, and 34 are shown in Table 6a of Figure 35. It is easier for readers to directly read the truth table than to try to understand the associated mathematical expressions and circuits.

In other words, after inputting data into the logic circuit in Figure 33, it can generate an output result according to Table 6a in Figure 35.

_The algorithm itself is recursive, starting from the first round i=0, where Z0 _and Z1 are the first two bits, and it is assumed that Z _-1 =0.

According to Table 6a, convert the Z ₀ Z ₁ Z _-1 sub-character to obtain Sub-character (replacing the original Z ₀ Z ₁ Z _-1 ). In the second round, when i = 1, the updated Z ₂ Z ₁ Z ₀ sub-character is input and again transformed according to Table 6a. The regression algorithm continues until the most significant digit is reached, at which point i = n and Z _{n +1} = 0 is completed.

By understanding semi-optimization, it may be easier to understand the full optimization algorithm. In this case, each semi-optimized generalized binary character can be further optimized into a fully optimized generalized binary character by an algorithm that can achieve the following goals: 1) Remove all surrounding non-zero bits so that the x sub-character has two 1 bits and the y sub-character has two 1 bits. bit, and a 1 bit in the x subcharacter and a 1 bit in the y subcharacter The bits are adjacent to each other (i.e., there are no 1s and bits, these cases can be replaced by two adjacent 0 and 1); or 2) the above bits are arranged with adjacent zero and non-zero bits and 3) if the bit immediately before and after the next non-zero bit in the same sub-character is zero bits, then any non-zero bits in the sub-character are retained, while the bits before and after the same position in the other sub-character are zero bits.

Other variations of semi-optimization

The above description should allow any reader to understand how the embodiments of the present invention operate. To demonstrate that other algorithms can achieve optimization, and that the scope of the present invention should not be limited to the above embodiments and algorithms, two other methods for achieving semi-optimization are proposed below.

The first variation of semi-optimizing the generalized binary number n _w (a pair of sub-characters whose value when added is equal to the addend) consists of two steps:

(a) Using the following semi-optimal transformation equation, transform any generalized binary number _nw into a partially semi-optimal binary number of the first form: :

This step can be performed by finding the difference between shifting _nw by one bit to a more significant carry (i.e., _2nw ) and _nw . The first form of the partial semi-optimization algorithm is shown in the following equation and truth table 6b:

Here, we assume that z _{n +1} = z _-1 = z _-2 =0.

Equation (11) and the corresponding expanded equations (12a) and (12b) imply multiplying a sub-character by 2 and then subtracting the sub-character from the product to transform each sub-character in the sub-character pair. It was unexpectedly found that there are very few bit positions and arrangements that do not meet the requirements of semi-optimal sub-characters. Therefore, this method can almost achieve complete semi-optimization. In other words, this step is not perfect, and this algorithm cannot guarantee complete semi-optimization because it cannot (i) There is one , if _there exists a sub-character; and (ii) There is an 11 in n _w . If there is an sub-characters, these conflict with the semi-optimal definitions above.

FIG37b shows the truth table 6b generated by the equations of step (a) in accordance with a variation of the present semi-optimization process or algorithm. The semi-optimization process of the above equations cannot guarantee a complete semi-optimization because it cannot (i) There is one , if _there exists a sub-character; and (ii) There is an 11 in n _w . If there is an sub-characters, these conflict with the semi-optimal definitions above.

(b) To solve the problem that any bit does not meet the semi-optimal sub-character requirements, 11 or Any bit in the permutation is transformed into a perfect semi-optimal number , which can be expressed by the following equation and truth table 6c:

Figure 37c shows the truth table 6c of the equation above. The bit manipulation represented by equations (13a) and (13b) is the result of taking into account the non-zero combinations that fail to meet the semi-optimization requirements of equation (11).

Therefore, step (b) is used to make up for the deficiency of step (a) so that any number can be converted into a completely semi-optimal number. , or simply To express.

Combining steps (a) and (b), and assuming z _{n +1} = z _-1 = z _-2 = z _-3 = 0, the semi-optimal algorithms in equations (12a), (12b), (13a), and (13b) can be combined to produce the following equation:

In this case, both positive and negative n _w can be semi-optimized through parallel operations rather than regression operations.

Semi-optimal output and It depends only on z _i , z _{i -1} , z _{i -2} and z _{i -3} in n _w .

Figure 38 is truth table 7 after combining steps (a) and (b) (i.e., equations (14a) and (14b)). The corresponding logic circuits are shown in Figures 36 and 37a.

The second variation of semi-optimizing the generalized binary number n _w (a pair of sub-characters whose value when added is equal to the addend) consists of two steps:

(a) According to the following equation or the truth table in Table 8 of Figure 41, and the logic circuits shown in Figures 39 and 40, and Transformed into and ,

(b) Applying the semi-optimal transformation equation (11), truth table 9 in Figure 44, and the logic circuits in Figures 42 and 43, the following equation can be obtained:

It produces semi-optimal numbers and .

In other words, the difference between the first and second variations of the semi-optimal process is based on reversing the order of applying the bit manipulation algorithm and equation (11).

The bit manipulation algorithm implemented in the second variation according to equations (15a) and (15b) differs from the bit manipulation algorithm implemented in the first variation according to equations (13a) and (13b) because the possible non-zero combinations that need to be removed to meet the one-half optimal sub-character requirement (which have been removed by bit manipulation) are found to be different in the first and second variations.

The above description of the embodiments is presented by way of example only, and various modifications are readily apparent to those skilled in the art. The above description, examples, and figures provide a complete description of the structure and use of exemplary embodiments of the present invention. Although various embodiments of the present disclosure have been described above with a certain degree of specificity, or with reference to one or more individual embodiments, those skilled in the art will readily appreciate that numerous modifications of the disclosed embodiments can be made without departing from the spirit and scope of the present disclosure.

501, 503, 505, 507, 508, 509, 511, 513, 515, 517: Steps

Claims (18)

A method for formatting a binary character number into a format suitable for addition to another number of the same format and transmitting any carry value of the sum, comprising: providing the number; providing a binary character representing the absolute value of the number; splitting the value of the binary character into a pair of binary sub-characters, wherein the sum of the pair of binary sub-characters x and y is equal to the value of the binary character; rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y to achieve the following: (a) generating a pair of formatted binary sub-characters , where the pair of binary subcharacters formatted equal to the value of the binary character; (b) in each formatted binary subcharacter each non-zero bit is separated from any other non-zero bit by at least one zero bit; and (c) in the pair of formatted binary subcharacters The values of any bit position i in cannot be non-zero at the same time. The method of claim 1, wherein the step of rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y comprises converting the non-zero bits at the same position of the pair of binary sub-characters x and y into zero bits. The method of claim 1, wherein one of the pair of binary subcharacters is a subtrahend and the other is a minuend, such that a sum of the pair of binary subcharacters is equal to a difference between the subtrahend and the minuend. The method of claim 1, wherein the step of rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y comprises steps (1), (2), and (3) in the following order: (1) applying the following equation to remove any middle adjacent non-zero bits in the binary sub-character y: (1a) and (1b) (2) Apply the following equation to remove any pair of adjacent non-zero bits in the specified order, transforming the pair of binary subcharacters x and y from x=1, y=1 followed by x=0, y=1 to x=0, y=0 followed by x=1, y=0: (5a) (5b) (3) Apply the following equation to remove any adjacent non-zero bits in the binary subcharacter x: (6a) or (6b) in, and Represents the binary sub-characters formatted in this pair The value of the bit at position i. The method of claim 1, wherein the step of rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y comprises, before performing the step (b), performing the following step (a): (a) applying the following equation to the pair of binary sub-characters x and y: (11) in represents the pair of binary sub-characters x and y; (b) applying the following equation to To obtain , (13a) (13b) in, = and ; and Binary subcharacters representing different pairs and The value of the bit at position i. The method of claim 1 further comprising swapping the pair of binary sub-characters and content. The method of claim 1, wherein the step of rearranging the plurality of zeros and non-zeros of the pair of binary sub-characters x and y comprises, before performing the following step (ii), performing the following step (i): (i) respectively rearranging the binary sub-characters according to the following equations and Transformed into and : (15a) (15b) (ii) Apply the following equation to and superior: (11) . A logic circuit to which step (1) of the method of claim 4 can be applied, wherein the logic circuit comprises a configuration as shown in FIG11 . A logic circuit to which step (2) of the method of claim 4 can be applied, wherein the logic circuit comprises the configuration shown in FIG14 . A logic circuit to which step (3) of the method of claim 4 can be applied, wherein the logic circuit comprises the configuration shown in FIG17 . A logic circuit to which step (a) and step (b) of the method of claim 5 can be applied, wherein the logic circuit includes the configuration shown in FIG37a. A logic circuit to which step (i) of the method of claim 7 is applicable comprises the configuration shown in FIG. 40 . A logic circuit to which step (ii) of the method of claim 7 is applicable comprises the configuration shown in FIG. 43 . A logic circuit to which the method as described in claim 2 can be applied includes the configuration shown in FIG30b. A binary character adder includes a plurality of adder circuits arranged so that each adder circuit can perform bit addition at the same position of two binary characters simultaneously with other adder circuits of the adder circuits. The adder circuit has the configuration shown in FIG22. The binary character adder as described in claim 15 further includes: an input terminal, which can input each binary sub-character of each pair of binary sub-characters of the two pairs of binary sub-characters, wherein the input terminal is supplied by an upstream circuit, which is used to generate the two pairs of binary sub-characters; each pair of binary sub-characters has the following characteristics: no non-zero bit is immediately following another bit of the same value in the same binary sub-character; and there is no non-zero bit in the same position of another binary sub-character. The binary character adder as described in claim 15 further includes: an output terminal that can output each binary sub-character of a pair of binary sub-characters, wherein the output terminal is connected to a downstream circuit for converting the pair of binary sub-characters into a binary character that can represent the adder sum of the binary characters. A binary character adder as described in claim 15, wherein the contents of the two binary sub-characters in the pair of binary sub-characters are swapped with each other before performing bit addition.