|
|
|
Including graph or tree representation (e.g., abstract syntax tree or AST) |
Method of operation of arithmetic and logic unit, storage medium, and arithmetic and logic unit6028987
Abstract
A method of operation of an arithmetic and logic unit, a storage medium, and an arithmetic and logic unit introducing a technique and concept of converting a serial structure of decisions having an order dependency to an indeterminate code binary tree which can be processed in parallel so as to simplify the configuration and enable higher speed operation processing. Where a serial structure of decisions having an order dependency is converted to a binary tree structure using decision nodes not having dependency input/outputs as leaves and higher priority determination nodes as the nodes other than the leaves, the decision nodes having dependency input/outputs are replaced by decision nodes not having dependency input/outputs provided with connotation decision nodes and indeterminate code generation nodes.
Claims
What is claimed is:
1. A method of operation of an arithmetic and logic unit for solving a problem including a series of decisions having an order dependency by creating a model by a binary tree using processings for decisions not having dependency input/outputs as leaves and using processings for determination of a higher priority as nodes other than the leaves,
in said method of operation of an arithmetic and logic unit, processings for decisions not having dependency input/outputs, corresponding to the decisions, each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information at a point of time when said data input becomes valid and outputting a code of a format combining into one an indeterminate code "Q" of the meaning "cannot be defined" and the quantity as a working conclusion;
said processings for determination of higher priorities, corresponding to the series of decisions, each receiving as its input the working conclusions of two processings for decisions not having dependency input/outputs or the working conclusions of two processings for determination of higher priorities before the same, outputting the working conclusion of the processing for a decision of a higher significant bit not having a dependency input/output or the working conclusion of the processing for determination of a higher priority of a higher significant bit as a working conclusion when the working conclusion of the processing for a decision not having a dependency input/output of a higher significant bit or the working conclusion of the processing for determination of a higher priority of a higher significant bit is not the indeterminate code "Q", and outputting the working conclusion of the processing for a decision not having a dependency input/output of a lower significant bit or the working conclusion of the processing for determination of a higher priority of a lower significant bit as the working conclusion when the working conclusion of the processing for a decision not having a dependency input/output of a higher significant bit or the working conclusion of the processing for determination of a higher priority of a higher significant bit is the indeterminate code "Q"; and
all processings for decisions serving as leaves of the binary tree and all processings for determination of higher priorities located at the same depth in the binary tree being respectively processed in parallel and the working conclusion of the processing for determination of a higher priority serving as a root of the binary tree being defined as the conclusion of the problem.
2. A storage medium which can be read by a computer, wherein
the method of operation of the arithmetic and logic unit disclosed in claim 1 is stored as a program for execution by the computer.
3. A method of operation of an arithmetic and logic unit for transforming
all problems for which a model can be created by a serial structure of decisions having an order dependency configured by
having N (N is any positive integer) number of decision nodes having dependency input/outputs each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input comprising binary information indicating "valid" or "invalid" at a point of time when both of the data input and the dependency input become valid and each outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising binary information indicating "valid" or "invalid" and
having a relationship of relative order between the decision nodes having dependency input/outputs, having the dependency input of the decision node having a dependency input/output of the most significant bit always being "valid", and having the dependency output of a decision node having a dependency input/output located at a higher significant bit connected as the dependency input of a decision node having a dependency input/output located at one lower significant bit from that decision node having a dependency input/output to
a binary tree structure having N number of decision nodes not having dependency input/outputs for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or a quantity of logical value information at a point of time when the data input becomes valid and outputting a code of a format combining into one an indeterminate code "Q" of the meaning "cannot be defined" and a quantity as a working conclusion and
defining the N number of decision nodes not having dependency input/outputs as leaves,
said method of operation of an arithmetic and logic unit replacing a decision node having a dependency input/output by
a decision node not having a dependency input/output having a connotation decision node for executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input always comprising "valid" at a point of time when the data input becomes valid and outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising binary information indicating "valid" or "invalid" and an indeterminate code generation node for outputting an indeterminate code "Q" when the dependency output of the connotation decision node becomes "valid" and outputting a code of a format combining in one the indeterminate code "Q" and the quantity as the working conclusion of the decision node not having a dependency input/output.
4. A storage medium which can be read by a computer, wherein
the method of operation of the arithmetic and logic unit disclosed in claim 3 is stored as a program for execution by the computer.
5. A method of operation of an arithmetic and logic unit for transforming
all problems for which a model can be created by a serial structure of decisions having an order dependency configured by
having N (N is any positive integer) number of decision nodes having dependency input/outputs for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input comprising binary information indicating "valid" or "invalid" at a point of time when both of the data input and the dependency input become valid and each outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising binary information indicating "valid" or "invalid" and
having a relationship of relative order between the decision nodes having dependency input/outputs, having the dependency input of the decision node having a dependency input/output of the most significant bit always being "valid", and having the dependency output of a decision node having a dependency input/output located at a higher significant bit connected as the dependency input of a decision node having a dependency input/output located at one lower significant bit from that decision node having a dependency input/output to
a binary tree structure having N number of decision nodes not having dependency input/outputs for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information at a point of time when the data input becomes valid and outputting a code of a format combining into one an indeterminate code "Q" of the meaning "cannot be defined" and the quantity as a working conclusion and
higher priority determination nodes, corresponding to the series of decisions, which each receives as its input the working conclusions of two decision nodes not having dependency input/outputs or the working conclusions of two higher priority determination nodes in front of this higher priority determination node and outputs the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit as the working conclusion of that higher priority determination node when the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit is not the indeterminate code "Q", while outputs the working conclusion of the decision node not having a dependency input/output of a lower significant bit or the working conclusion of the higher priority determination node of a lower significant bit as the working conclusion of that higher priority determination node when the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit is the indeterminate code "Q" and
defining the decision nodes not having dependency input/outputs as leaves and defining the higher priority determination nodes as other nodes other than leaves,
said method of operation of an arithmetic and logic unit replacing a decision node having a dependency input/output by
a decision node not having a dependency input/output having a connotation decision node for executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input always comprising "valid" at a point of time when the data input becomes valid and outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising binary information indicating "valid" or "invalid" and an indeterminate code generation node for outputting an indeterminate code "Q" when the dependency output of the connotation decision node becomes "valid" and outputting a code of a format combining in one the indeterminate code "Q" and the quantity as the working conclusion of the decision node not having a dependency input/output.
6. A storage medium which can be read by a computer, wherein
the method of operation of the arithmetic and logic unit disclosed in claim 5 is stored as a program for execution by the computer.
7. A method of operation of an arithmetic and logic unit for realizing a priority encoding function for outputting as a binary number, with respect to data input of n-bit binary numbers, a bit position which is first "1" or "0" in a direction from the most significant bit to the least significant bit or the number of continuous "1's" or "0's" in the direction from the most significant bit to the least significant bit by creating a model by a binary tree defining a processing for a decision not having a dependency input/output as a leaf and defining processing for determination of a higher priority as another node other than a leaf,
in said method of operation of an arithmetic and logic unit,
the processings for decisions not having dependency input/outputs, corresponding to each bit of the data input, each executing a predetermined decision based on one bit of the data input at the point of time when the data input becomes valid and outputting a code of a format combining into one an indeterminate code "Q" indicating "cannot be defined" and a quantity as a working conclusion;
the processings for determination of higher priorities, corresponding to each bit of the data input, each receiving as its input the working conclusions of two processings for decisions not having dependency input/outputs or the working conclusions of two processings for determination of higher priorities in front of the same, outputting the working conclusion of the processing for a decision not having a dependency input/output of a higher significant bit or the working conclusion of the processing for determination of a higher priority of a higher significant bit as the working conclusion when the working conclusion of the processing for a decision not having significant dependency input/output of a higher significant bit or the working conclusion of the processing for determination of a higher priority of a higher significant bit is not the indeterminate code "Q", and outputting the working conclusion of the processing for a decision not having a dependency input/output of a lower significant bit or the working conclusion of the processing for determination of a higher priority of a lower significant bit as the working conclusion when the working conclusion of the processing for a decision not having a dependency input/output of a higher significant bit or the working conclusion of the processing for determination of a higher priority of a higher significant bit is the indeterminate code "Q"; and
all processings for decisions serving as leaves of the binary tree and all processings for determination of higher priorities located at the same depth in the binary tree being respectively processed in parallel and the working conclusion of the higher priority determination node serving as a root of the binary tree being defined as the conclusion of the priority encoding.
8. A method of operation of an arithmetic and logic unit for solving a problem including a series of decisions having an order dependency by creating a model by a binary tree defining processings for decisions, corresponding to the decisions, as leaves and defining processings for determination of higher priorities as other nodes other than leaves,
in said method of operation of an arithmetic and logic unit, the processings for decisions outputting any one of "true", "false", and "neither true nor false or do not know" as a result of decision based on one or a plurality of input information;
the processings for determination of higher priorities, corresponding to the series of decisions, each receiving as its input the results of decisions of two processings for decisions or the results of decisions of two processings for determination of higher priorities in front of the same, outputting the result of decision of the processing for a decision of the higher significant bit or the processing for determination of a higher priority of the higher significant bit when the result of decision of the processing for a decision of the higher significant bit or the processing for determination of a higher priority of the higher significant bit is "true" or "false", and outputting the result of decision of the processing for a decision of the lower significant bit or the processing for determination of a higher priority of the lower significant bit when the result of decision of the processing for a decision of the higher significant bit or the processing for determination of a higher priority of the higher significant bit is "neither true nor false or do not know"; and
all processings for decisions serving as leaves of the binary tree and all processings for determination of higher priorities located at the same depth in the binary tree being respectively processed in parallel.
9. A method of operation of an arithmetic and logic unit as set forth in claim 8, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
the processing for determination of a higher priority is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, a code Ti.epsilon.{Y, N, Q} derived from the result of decision of the processing for a decision of a higher significant bit and a code Tj.epsilon.{Y, N, Q} derived from the result of decision of a processing for a decision of a lower significant bit; and when the code Ti is in a relationship superior to the code Tj, the K operator defines the value code "Y" or the value code "N" as the value code taken by the code Tij when the code Ti is the value code "Y" or the value code "N" and defines the value code taken by the code Tj as the value code taken by the code Tij when the code Ti is the value code "Q".
10. A method of operation of an arithmetic and logic unit as set forth in claim 8, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
the processing for determination of a higher priority is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, a code Ti.epsilon.{Y, N, Q} derived from the result of decision of the processing for a decision of a higher significant bit and a code Tj.epsilon.{Y, N, Q} derived from the result of decision of a processing for a decision of a lower significant bit; and when the code Ti is in a relationship superior to the code Tj,
when any code X is given by a 2-bit binary number (X, 1, X, 0) defining the value code "Y" as {11}, the value code "N" as {10}, and the value code "Q" as {0*} (where, "*" is "don't care"), an OR logic is denoted by a "+" operator, an AND logic is denoted by a ".multidot." operator, and a negative logic is denoted by a " " operator, respectively,
the K operator is given as: ##EQU24##
11. A storage medium which can be read by a computer, wherein the method of operation of the arithmetic and logic unit disclosed in claim 8 is stored as a program for execution by the computer.
12. A method of operation of an arithmetic and logic unit for finding the absolute value of the difference of two numbers (X, Y) of n number of digits of any R-nary number by creating a model by one column of n number of processings for decisions, all filled by n number of binary trees defining the processings for decisions from the first digit to a g-th digit (g=1 to n) as the leaves and defining other nodes other than the leaves as the processings for determination of higher priorities, and a matrix comprising n number of rows and m number of columns (m is the smallest integer exceeding log.sub.2 n) of processings for determination of higher priorities
in said method of operation of an arithmetic and logic unit, the processings for decisions each outputting as the result of decision a value code "Y" meaning "true" when the result of the difference (X-Y) of two numbers of the same digit place becomes negative, outputting a value code "N" meaning "false" when the result becomes positive, and outputting a value code "Q" meaning "neither true nor false or do not know" when the result becomes zero;
the processings for determination of higher priorities, corresponding to the series of decisions, each receiving as its input the results of decisions of two processings for decisions or the results of decisions of two processings for determination of higher priorities in front of the same, outputting the result of decision of the processing for a decision of the higher significant bit or the processing for determination of a higher priority of the higher significant bit when the result of decision of the processing for a decision of the higher significant bit or the processing for determination of a higher priority of the higher significant bit is "true" or "false", and outputting the result of decision of the processing for a decision of a lower significant bit or the processing for determination of a higher priority of the lower significant bit when the result of decision of the processing for a decision of the higher significant bit or processing for determination of a higher priority of the higher significant bit is "neither true nor false or do not know"; and
the one column of n number of processings for decisions and the constituent elements of the columns comprising the matrix comprising the n number of rows and m number of columns of processings for determination of higher priorities being respectively simultaneously processed and a borrow operation of each digit being generated from each processing for determination of a higher priority of the m-th column.
13. A method of operation of an arithmetic and logic unit as set forth in claim 12, comprising:
a code judgement step for judging the code for the result of the difference (Xa-Yb) of two numbers based on the result of the generation of the borrow operation of the most significant digit generated from the processing for determination of a higher priority of the n-th row and m-th column;
a code replacement step of respectively replacing the value code "Q" with the value code "Q", the value code "Y" with the value code "N", and the value code "N" with the value code "Y" for the output codes of the processings for determination of higher priorities not including the processing for determination of a higher priority of the n-th row among the group of processings for determination of higher priorities of the m-th column when the result of the code judgement of the code judgement step is negative or when it is negative or zero and leaving them as they are without performing the replacement where the result is positive or zero or when it is positive; and
a second code replacement step for replacing the value code "Q" with the value code "N" to obtain a borrow operation of each digit for the result of replacement or the output code of the processing for determination of a higher priority after the code replacement step.
14. A storage medium which can be read by a computer, wherein
the method of operation of the arithmetic and logic unit disclosed in claim 13 is stored as a program for execution by the computer.
15. A storage medium which can be read by a computer, wherein
the method of operation of the arithmetic and logic unit disclosed in claim 12 is stored as a program for execution by the computer.
16. An arithmetic and logic unit for solving a problem including a series of decisions having an order dependency, said arithmetic and logic unit having
decision nodes not having dependency input/outputs, corresponding to the decisions, for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information at a point of time when the data input becomes valid and outputting a code of a format combining in one an indeterminate code "Q" indicating "cannot be defined" and the quantity as a working conclusion and
higher priority determination nodes, corresponding to the series of decisions, for each receiving as its input the working conclusions of two decision nodes not having dependency input/outputs or the working conclusions of two higher priority determination nodes in front of the same, outputting the working conclusion of the decision node not having a dependency input/output of the higher significant bit or the working conclusion of the higher priority determination node of the higher significant bit as the working conclusion when the working conclusion of the decision node not having the dependency input/output of the higher significant bit or the working conclusion of the higher priority determination node of the higher significant bit is not the indeterminate code "Q", and outputting the working conclusion of the decision node not having a dependency input/output of the lower significant bit or the working conclusion of the higher priority determination node of the lower significant bit as the working conclusion when the working conclusion of the decision node not having a dependency input/output of the higher significant bit or the working conclusion of the higher priority determination node of the higher significant bit is the indeterminate code "Q" and
creating a model for the problem by a binary tree defining a decision node not having a dependency input/output as a leaf and defining a higher priority determination node as another node other than a leaf, simultaneously processing all decision nodes serving as the leaves and all higher priority determination nodes located at the same depth in the binary tree, and defining the working conclusion of the higher priority determination node serving as a root of the binary tree as the conclusion of the problem.
17. An arithmetic and logic unit configured to transform a serial structure of decisions having an order dependency configured by
having N (N is any positive integer) number of decision nodes having dependency input/outputs for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input comprising binary information indicating "valid" or "invalid" at a point of time when both of the data input and the dependency input become valid and outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising the binary information indicating "valid" or "invalid", and
having a relationship of relative order between the decision nodes having dependency input/outputs, having the dependency input of the decision node having a dependency input/output of the most significant bit always being "valid", and having the dependency output of a decision node having a dependency input/output located at a higher significant bit connected as the dependency input of a decision node having a dependency input/output located at one lower significant bit from that decision node having a dependency input/output to
a binary tree structure having N number of decision nodes not having dependency input/outputs for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information at a point of time when the data input becomes valid and outputting a code of a format combining in one an indeterminate code "Q" indicating "cannot be defined" and the quantity as the working conclusion and
defining the N number of decision nodes not having dependency input/outputs as leaves,
said arithmetic and logic unit replacing a decision node having a dependency input/output by
a decision node not having a dependency input/output having a connotation decision node for executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input always comprising "valid" at a point of time when the data input becomes valid and outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising binary information indicating "valid" or "invalid" and an indeterminate code generation node for outputting an indeterminate code "Q" when the dependency output of the connotation decision node becomes "valid" and outputting a code of a format combining in one the indeterminate code "Q" and the quantity as the working conclusion.
18. An arithmetic and logic unit configured to transform a serial structure of decisions having an order dependency configured by
having N (N is any positive integer) number of decision nodes having dependency input/outputs for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input comprising binary information indicating "valid" or "invalid" at a point of time when both of the data input and the dependency input become valid and outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising the binary information indicating "valid" or "invalid", and
having a relationship of relative order between the decision nodes having dependency input/outputs, having the dependency input of the decision node having a dependency input/output of the most significant bit always being "valid", and having the dependency output of a decision node having a dependency input/output located at a higher significant bit connected as the dependency input of a decision node having a dependency input/output located at one lower significant bit from that decision node having a dependency input/output to
a binary tree structure having N number of decision nodes not having dependency input/outputs for each executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information at a point of time when the data input becomes valid and outputting a code of a format combining into one an indeterminate code "Q" of the meaning "cannot be defined" and the quantity as a working conclusion and
higher priority determination nodes, corresponding to the series of decisions, which each receives as its input the working conclusions of two decision nodes not having dependency input/outputs or the working conclusions of two higher priority determination nodes in front of this higher priority determination node and outputs the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit as the working conclusion of that higher priority determination node when the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit is not the indeterminate code "Q", while outputs the working conclusion of the decision node not having a dependency input/output of a lower significant bit or the working conclusion of the higher priority determination node of a lower significant bit as the working conclusion of that higher priority determination node when the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit is the indeterminate code "Q" and
defining the decision nodes not having dependency input/outputs as leaves and defining the higher priority determination nodes as other nodes other than leaves,
said arithmetic and logic unit replacing a decision node having a dependency input/output by
a decision node not having a dependency input/output having a connotation decision node for executing a predetermined decision based on a single or a plurality of data inputs comprising an R-nary number or quantity of logical value information and a dependency input always comprising "valid" at a point of time when the data input becomes valid and outputting a conclusion output comprising an R-nary number or quantity of logical value information and a dependency output comprising binary information indicating "valid" or "invalid" and an indeterminate code generation node for outputting an indeterminate code "Q" when the dependency output of the connotation decision node becomes "valid" and outputting a code of a format combining in one the indeterminate code "Q" and the quantity as the working conclusion.
19. An arithmetic and logic unit provided with a priority encoding function for outputting as a binary number, with respect to data input of n-bit binary numbers, a bit position which is first "1" or "0" in a direction from the most significant bit to the least significant bit,
said arithmetic and logic unit having
decision nodes not having dependency input/outputs, corresponding to each bit of the data input, each executing a predetermined decision based on one bit of the data input at the point of time when the data input becomes valid and outputting a code of a format combining into one an indeterminate code "Q" indicating "cannot be defined" and a quantity as a working conclusion and
higher priority determination nodes, corresponding to each bit of the data input, each receiving as its input the working conclusions of two decision nodes not having dependency input/outputs or the working conclusions of two higher priority determination nodes in front of the same, outputting the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit as the working conclusion when the working conclusion of the decision node not having significant dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit is not the indeterminate code "Q", and outputting the working conclusion of the decision node not having a dependency input/output of a lower significant bit or the working conclusion of the higher priority determination node of a lower significant bit as the working conclusion when the working conclusion of the decision node not having a dependency input/output of a higher significant bit or the working conclusion of the higher priority determination node of a higher significant bit is the indeterminate code "Q" and
creating a model of the priority encoding function by a binary tree defining a decision node not having a dependency input/output as a leaf and defining a higher priority determination node as another node other than a leaf, simultaneously processing all decision nodes serving as leaves and all higher priority determination nodes located at the same depth in the binary tree, and defining the working conclusion of the higher priority determination node serving as a root of the binary tree as the conclusion of the priority encoding function.
20. An arithmetic and logic unit as set forth in claim 19, wherein:
the binary tree has n number of decision nodes serving as the leaves;
a sub binary tree of a height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes serving as the nodes of a depth m, and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes serving as the nodes of a depth s (s is an integer represented as s=1 to m-1);
a decision node is a bit signal line of the corresponding data input;
the pm-th (pm=1 to Nm) higher priority determination nodes from the least significant bit serving as the nodes of the depth m of the sub binary tree
each defines a (2.times.pm-2)-th bit signal line and a (2.times.pm-1)-th bit signal line of the data input as the zero-th bit input and the first bit input and
has an OR logic means for taking an OR logic of the zero-th bit input and the first bit input and outputting the result as a first bit output and
a connection line for outputting the first bit input as the zero-th bit output;
the ps-th (ps=1 to Ns) higher priority determination nodes from the least significant bit serving as the nodes of the depth s of the sub binary tree
each defines a zero-th bit output to an (m-s)-th bit output of a (2.times.ps-1)-th higher priority determination node serving as a node of the depth (s+1) of the sub binary tree as the zero-th bit input to the (m-s)-th bit input of a lower significant bit and defines the zero-th bit output to the (m-s)-th bit output of a (2.times.ps)-th higher priority determination node serving as a node of the depth (s+1) of the sub binary tree as the zero-th bit input to the (m-s)-th bit input of a higher significant bit and
has an OR logic means for taking the OR logic of the (m-s)-th bit input of the lower significant bit and the (m-s)-th bit input of the higher significant bit and outputting the result as an (m-s+1)-th bit output,
a connection line for outputting the (m-s)-th bit input of the higher significant bit as the (m-s)-th bit output, and
(m-s+1) number of selecting means; and
a q-th (q=1 to m-s+1)-th selecting means from the least significant bit receives as its input the (m-s)-th bit of the higher significant bit as the selection input, selects the (q-1)-th bit input of the higher significant bit when the selection input is "true", selects the(q-1)-th bit input of the lower significant bit when the selection input is "false", and outputs the same as the (q-1)-th bit output.
21. An arithmetic and logic unit provided with a priority encoding function for outputting as a binary number, with respect to a data input of n-bit binary numbers, a bit position which is first "1" or "0" in a direction from the most significant bit to the least significant bit,
in said arithmetic and logic unit, a model is created for said arithmetic and logic unit by a binary tree of a height m (m is the smallest integer exceeding log.sub.2 n),
the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of nodes of a depth s (s is an integer represented as s=1 to m-1);
the pm-th (pm=1 to Nm) nodes from the least significant bit of the depth m of the binary tree
each uses a (2.times.pm-2)-th bit signal line and a (2.times.pm-1)-th bit signal line of the data input as the zero-th bit input and the first bit input and
has an OR logic means for taking the OR logic of the zero-th bit input and the first bit input and outputting the result as the first bit output and
a connection line for outputting the first bit input as the zero-th bit output;
the ps-th (ps=1 to Ns) nodes from the least significant bit of the depth s of the binary tree
each uses the zero-th bit output to the (m-s)-th bit output of a (2.times.ps-1)-th node of the depth (s+1) of the binary tree as the zero-th bit input to the (m-s)-th bit input of a lower significant bit and uses the zero-th bit output to the (m-s)-th bit output of a (2.times.ps)-th node of the depth (s+1) of the binary tree as the zero-th bit input to the (m-s)-th bit input of a higher significant bit and
has an OR logic means for taking the OR logic of the (m-s)-th bit input of the lower significant bit and the (m-s)-th bit input of the higher significant bit and outputting the result as an (m-s+1)-th bit output,
a connection line for outputting the (m-s)-th bit input of the higher significant bit as the (m-s)-th bit output, and
(m-s+1) number of selecting means; and
a q-th (q=1 to m-s+1)-th selecting means from the least significant bit receives as its input the (m-s)-th bit of the higher significant bit as the selection input, selects the (q-1)-th bit input of the higher significant bit when the selection input is "true", selects the (q-1)-th bit input of the lower significant bit when the selection input is "false", and outputs the result as the (q-1)-th bit output.
22. An arithmetic and logic unit provided with a priority encoding function for outputting as a binary number, with respect to data input of n-bit binary numbers, the number of continuous "1's" or "0's" in the direction from the most significant bit to the least significant bit,
said arithmetic and logic unit having
decision nodes not having dependency input/outputs, corresponding to the individual bits of the data input, for each executing a predetermined decision based on one bit of the data input at a point of time when the data input becomes valid and outputting a code of a format combining in one an indeterminate code "Q" of the meaning "cannot be defined" and a quantity as a working conclusion and
higher priority determination nodes, corresponding to the individual bits of the data input, which each receives as its input the working conclusions of two decision nodes not having dependency input/outputs or working conclusions of two higher priority determination nodes in front of the same, outputs the working conclusion of the decision node not having a dependency input/output of the higher significant bit or the working conclusion of the higher priority determination node of the higher significant bit as the working conclusion when the working conclusion of the decision node not having a dependency input/output of the higher significant bit or the working conclusion of the higher priority determination node of the higher significant bit is not the indeterminate code "Q", and outputs the working conclusion of the decision node not having a dependency input/output of the lower significant bit or the working conclusion of the higher priority determination node of the lower significant bit as the working conclusion when the working conclusion of the decision node not having a dependency input/output of the higher significant bit or the working conclusion of the higher priority determination node of the higher significant bit is the indeterminate code "Q"; and
the priority encoding function is realized by creating a model by a binary tree using decision nodes not having dependency input/outputs as leaves and using higher priority determination nodes as nodes other than the leaves, simultaneously processing all decision nodes serving as leaves and all higher priority determination nodes located at the same depth in the binary tree, and using the working conclusion of the higher priority determination node serving as the root of the binary tree as the conclusion of the priority encoding function.
23. An arithmetic and logic unit as set forth in claim 22, wherein:
the binary tree has n number of decision nodes serving as the leaves;
a sub binary tree of a part of a height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as the nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as the nodes of a depth s (s is an integer represented as S=1 to m-1);
a decision node is a bit signal line of the corresponding data input;
the pm-th (pm=1 to Nm) higher priority determination nodes from the least significant bit serving as the nodes of the depth m of the sub binary tree
each defines a (2.times.pm-2)-th bit signal line and a (2.times.pm-1)-th bit signal line of the data input as the zero-th bit input and the first bit input and
has an OR logic means for taking an OR logic of the zero-th bit input and the first bit input and outputting the result as a first bit output and
a negative logic means for taking the negative logic of the first bit input and outputting the result as the zero-th bit output;
the ps-th (ps=1 to Ns) higher priority determination nodes from the least significant bit which serve as the nodes of the depth s of the sub binary tree
each uses the zero-th bit output to the (m-s)-th bit output of the (2.times.ps-1)-th higher priority determination node which serves as a node of the depth (s+1) of the sub binary tree as the zero-th bit input to the (m-s)-th bit input of the lower significant bit and uses the zero-th bit output to the (m-s)-th bit output of the (2.times.ps)-th higher priority determination node which serves as a node of the depth (s+1) of the sub binary tree as the zero-th bit input to the (m-s)-th bit input of the higher significant bit, and
has an OR logic means for taking the OR logic of the (m-s)-th bit input of the lower significant bit and the (m-s)-th bit input of the higher significant bit and outputting the result as an (m-s+1)-th bit output,
a negative logic means for taking the negative logic of the (m-s)-th bit input of the higher significant bit and outputting the result as the (m-s)-th bit output, and
(m-s+1) number of selecting means; and
a q-th (q=1 to m-s+1)-th selecting means from the least significant bit receives as its input the (m-s)-th bit of the higher significant bit as the selection input, selects the (q-1)-th bit input of the higher significant bit when the selection input is "true", selects the(q-1)-th bit input of the lower significant bit when the selection input is "false", and outputs the same as the (q-1)-th bit output.
24. An arithmetic and logic unit provided with a priority encoding function for outputting as a binary number, with respect to data input of n-bit binary numbers, the number of continuous "1's" or "0's" in the direction from the most significant bit to the least significant bit, wherein
the arithmetic and logic unit is realized by creating of model by a binary tree of the height m (m is the smallest integer exceeding log.sub.2 n);
the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of nodes of the depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of nodes of the depth s (s is an integer represented as s=1 to m-1);
the pm-th (pm=1 to Nm) nodes from the least significant bit of the depth m of the binary tree
each uses a (2.times.pm-2)-th bit signal line and a (2.times.pm-1)-th bit signal line of the data input as the zero-th bit input and the first bit input and
has an OR logic means for taking the OR logic of the zero-th bit input and the first bit input and outputting the result as the first bit output and
a negative logic means for taking the negative logic of the first bit input and outputting this as the zero-th bit output;
the ps-th (ps=1 to Ns) nodes from the least significant bit of the depth s of the binary tree
each uses the zero-th bit output to the (m-s)-th bit output of the (2.times.ps-1)-th node of the depth (s+1) of the binary tree as the zero-th bit input to the (m-s)-th bit input of the lower significant bit and uses the zero-th bit output to the (m-s)-th bit output of the (2.times.ps)-th node of the depth (s+1) of the binary tree as the zero-th bit input to the (m-s)-th bit input of the higher significant bit and
has an OR logic means for taking the OR logic of the (m-s)-th bit input of the lower significant bit and the (m-s)-th bit input of the higher significant bit and outputting the result as an (m-s+1)-th bit output,
a negative logic means for taking the negative logic of the (m-s)-th bit input of the higher significant bit and outputting this as the (m-s)-th bit output, and
(m-s+1) number of selecting means; and
a q-th (q=1 to m-s+1)-th selecting means from the least significant bit receives as its input the (m-s)-th bit of the higher significant bit as the selection input, selects the (q-1)-th bit input of the higher significant bit when the selection input is "true", selects the(q-1)-th bit input of the lower significant bit when the selection input is "false", and outputs the same as the (q-1)-th bit output.
25. An arithmetic and logic unit for solving a problem including a series of decisions having an order dependency, having
decision nodes, corresponding to the decisions, for each outputting either of "true", "false", and "neither true nor false or do not know" as the result of the decision based on one or a plurality of input information and
higher priority determination nodes, corresponding to series of the decisions, for each receiving as its input the results of the decisions of two decision nodes or the results of the decisions of two higher priority determination nodes, outputs the result of the decision of the decision node of the higher significant bit or the higher priority determination node of the higher significant bit when the result of the decision of the decision node of the higher significant bit or the higher priority determination node of the higher significant bit is "true" or "false", and outputs the result of the decision of the decision node of the lower significant bit or the higher priority determination node of the lower significant bit when the result of the decision of the decision node of the higher significant bit or the higher priority determination node of the higher significant bit is "neither true nor false or do not know"; and
creating a model of the problem by a binary tree using decision nodes as leaves and higher priority determination nodes as nodes other than the leaves and simultaneously processing all decision nodes which serve as leaves and all higher priority determination nodes located at the same depth in the binary tree.
26. An arithmetic and logic unit as set forth in claim 25, wherein:
when the arithmetic and logic unit is for performing a comparison of two numbers of any R-nary system and the comparison decisions for the digits of the two numbers form a series of decisions having an order dependency,
the decision nodes each output "true or false" when the result of difference of the two numbers of the same digit places becomes positive, "false or true" when the result becomes negative, and "neither true nor false or do not know" when the result becomes zero.
27. An arithmetic and logic unit as set forth in claim 25, wherein:
when the arithmetic and logic unit performs an addition of two numbers of any R-nary system and the decisions of existence of a carry at each digit form a series of decisions having an order dependency,
the decision nodes each outputs "true or false" when the result of the sum of the two numbers of the same digit places becomes R or more, "false or true" when the result becomes (R-2), and "neither true nor false or do not know" when the result becomes (R-1).
28. An arithmetic and logic unit as set forth in claim 25, wherein:
when the arithmetic and logic unit performs the subtraction of two numbers of any R-nary system and the decisions of existence of a borrow at each digit forms a series of decisions having an order dependency,
the decision nodes each outputs "true or false" when the result of difference of two numbers of the same digit places becomes negative, "false or true" when the result becomes positive, and "neither true nor false or do not know" when the result becomes zero.
29. An arithmetic and logic unit as set forth in claim 25, wherein:
when the number of decisions in the series of decisions having an order dependency is n,
the binary tree has n number of decision nodes serving as the leaves; and
a sub binary tree of a part of a height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as nodes of a depth s (s is an integer represented as s=1 to m-1).
30. An arithmetic and logic unit as set forth in claim 25, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
a higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, a code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and a code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
the K operator uses the value code "Y" or the value code "N" as the value code taken by the code Tij when the code Ti is the value code "Y" or the value code "N" and uses the value code taken by the code Tj as the value code taken by the code Tij where the code Ti is the value code "Q".
31. An arithmetic and logic unit as set forth in claim 25, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
a higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, a code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and a code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
when any code X is assigned by a 2-bit binary number (X, 1, X, 0) defining the value code "Y" as {11}, the value code "N" as {10}, and the value code "Q" as {0*} (where, "*" is "don't care"), an OR logic is denoted by a "+" operator, an AND logic is denoted by a ".multidot." operator, and a negative logic is denoted by a " " operator, respectively,
the K operator is given as: ##EQU25##
32. An arithmetic and logic unit as set forth in claim 31, wherein each higher priority determination node has:
an OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for selecting and outputting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" as the code Tij,0, respectively.
33. An arithmetic and logic unit as set forth in claim 31, wherein:
when the number of decisions in the series of decision having an order dependency is n and a sub binary tree of the height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as the nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as the nodes of a depth s (s is an integer represented as s=1 to m-1),
a higher priority determination node which serves as a node at the depth m-p (p is an even number indicated as p=0 to m-1) of the sub binary tree has
a NOR logic means for taking the NOR logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1 and
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0; and
a higher priority determination node which serves as a node at the depth m-q (q is an odd number indicated as q=0 to m-1) of the sub binary tree has
a NAND logic means for taking the NAND logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1 and
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0.
34. An arithmetic and logic unit as set forth in claim 31, wherein:
when the arithmetic and logic unit performs a comparison of two n-bit binary numbers (Xa, Yb) and the comparison decisions for the digits of the two numbers (Xai, Ybi; i=0 to n-1) form a series of decisions having an order dependency,
a decision node has
an exclusive OR logic means for taking the exclusive OR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Xai as the code Ti,0.
35. An arithmetic and logic unit as set forth in claim 34, wherein:
each higher priority determination node has
an OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0; and
it is respectively interpreted that "the two numbers (Xa, Yb) are equal" when the output of the higher priority determination node serving as the root of the binary tree is indicated as Q=(0*), that "the two numbers (Xa, Yb) have a relationship of magnitude Xa>Yb" when the output is indicated as Y={11}, and that "the two numbers (Xa, Yb) have a relationship of magnitude Xa<Yb" when the output is indicated as N={10}.
36. An arithmetic and logic unit as set forth in claim 34, wherein:
when the sub binary tree of the height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as the nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as the nodes of a depth s (s is an integer represented as s=1 to m-1),
a higher priority determination node which serves as a node at the depth m-p (p is an even number indicated as p=0 to m-1) of the sub binary tree has
a NOR logic means for taking the NOR logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1 and
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0;
a higher priority determination node which serves as a node at the depth m-q (q is an odd number indicated as q=0 to m-1) of the sub binary tree has
a NAND logic means for taking the NAND logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1, and
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0;
when m is an even number, it is respectively interpreted that "the two numbers (Xa, Yb) are equal" when the output of the higher priority determination node serving as the root of the binary tree is indicated as Q=(0*), that "the two numbers (Xa, Yb) have a relationship of magnitude Xa>Yb" when the output is indicated as Y={11}, and that "the two numbers (Xa, Yb) have a relationship of magnitude Xa<Yb" when the output is indicated as N={10}; and
when m is an odd number, it is respectively interpreted that "the two numbers (Xa, Yb) are equal" when the output of the higher priority determination node serving as the root of the binary tree is indicated as Q=(1*), that "the two numbers (Xa, Yb) have a relationship of magnitude Xa>Yb" when the output is indicated as Y={00}, and that "the two numbers (Xa, Yb) have a relationship of magnitude Xa<Yb" when the output is indicated as N={01}.
37. An arithmetic and logic unit as set forth in claim 34, wherein:
when the arithmetic and logic unit performs a comparison of two code-bearing n-bit binary numbers (Xa, Yb),
the decision node performing the comparison decision for the MSBs (most significant bits) of the two numbers treats the digit value Xan-1 as the digit value Ybn-1 and treats the digit value Ybn-1 as the digit value Xan-1, respectively.
38. An arithmetic and logic unit as set forth in claim 31, wherein:
when the decisions of existence of a carry for the digits (Xai, Ybi; i=0 to n-1) of two digits in the addition of two n-bit binary numbers (Xa, Yb) form a series of decisions having an order dependency,
each decision node has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Xai as the code Ti,0 or a connecting means for outputting the digit value Ybi as the code Ti,0.
39. An arithmetic and logic unit as set forth in claim 38, wherein:
the decision node performing a decision of existence of the carry for the LSBs (least significant bits) of the two numbers has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0; and
does not output the code T0,1.
40. An arithmetic and logic unit as set forth in claim 39, wherein:
each higher priority determination node not due to the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes has
an OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1 is "0", respectively, and outputting the result as the code Tij,0;
the higher priority determination node due to the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes has
a selecting means for selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1is "0", respectively, and outputting the result as the code Tij,0 and does not output the code Tij,1; and
it is respectively interpreted that "there is a carry output" when the output code Tij,0 of the higher priority determination node which serves as the root of the binary tree is "1" and that "there is no carry output" when the output code Tij,0 is "0".
41. An arithmetic and logic unit as set forth in claim 39, wherein:
when the sub binary tree of the height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as the nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as the nodes of a depth s (s is an integer represented as s=1 to m-1),
each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-p (p is an even number indicated as p=0 to m-1) of the sub binary tree has
a NOR logic means for taking the NOR logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1 and
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0;
each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-q (q is an odd number indicated as q=0 to m-1) of the sub binary tree has
a NAND logic means for taking the NAND logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1 and
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0;
the higher priority determination node derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-p (p is an even number indicated as p=0 to m-1) of the sub binary tree has
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0 and does not output the code Tij,1;
the higher priority determination node derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-q (q is an odd number indicated as q=0 to m-1) of the sub binary tree has
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0 and does not output the code Tij,1;
when m is an even number, it is respectively interpreted that "there is a carry output" when the output code Tij,0 of the higher priority determination node which serves as the root of the binary tree is "1" and that "there is no carry output" when the output code Tij,0 is "0"; and
when m is an odd number, it is respectively interpreted that "there is a carry output" when the output code Tij,0 of the higher priority determination node which serves as the root of the binary tree is "0" and that "there is no carry output" when the output code Tij,0 is "1".
42. An arithmetic and logic unit as set forth in claim 31, wherein:
when the decisions of existence of a carry for the digits (Xai, Ybi; i=0 to n-1) of two numbers in the addition of two n-bit binary numbers (Xa, Yb) forms a series of decisions having an order dependency and when the binary tree is comprised using the decision nodes for performing the decision of existence of a carry for the binary digits Xaj, Ybj (j=0 to n-2) as leaves and the sub binary tree of the height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as the nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as the nodes of a depth s (s is an integer represented as s=1 to m-1),
the decision node for performing the decision of existence of a carry for the LSBs of the two numbers has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and
does not output the code T0,1;
a decision node performing a decision of existence of a carry for the digits Xak, Ybk (k=1 to n-1) of the two numbers has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xaj and the digit value Ybj and outputting the result as the code Tj,1 and
a connecting means for outputting the digit value Xaj as the code Tj,0 or a connecting means for outputting the digit value Ybj as the code Tj,0;
the higher priority determination node derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes has
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1 is "0", and outputting the result as the code Tij,0 and does not output the code Tij,1;
each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes has
an OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1 is "0", and outputting the result as the code Tij,0;
when the number of leaves of the binary tree is not a power of 2, uses the higher priority determination node corresponding to the decision node performing the decision of existence of a carry for the LSBs of the two numbers as the dummy node for propagating the code T0,0 output by the decision node as it is; and
has an exclusive OR logic means for taking the exclusive OR logic between the negative logic of the output code Tn-1,1 of the decision node performing the decision of existence of a carry for the MSBs of the two numbers and the code output Tij,0 of the higher priority determination node which serves as the root of the binary tree and defining this as the result of the sum for the MSBs of the two numbers.
43. An arithmetic and logic unit as set forth in claim 31, wherein:
when the decisions of existence of a carry for the digits (Xai, Ybi; i=0 to n-1) of two numbers in the addition of two n-bit binary numbers (Xa, Yb) form a series of decisions having an order dependency and when the binary tree is comprised using decision nodes for performing the decisions of existence of a carry for the digits Xaj, Ybj (j=0 to n-2) of the two numbers as leaves and the sub binary tree of the height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as the nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as the nodes of a depth s (s is an integer represented as s=1 to m-1),
the decision node for performing the decision of existence of a carry for the LSBs of the two numbers has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and does not output the code T0,1;
each decision node performing the decision of existence of a carry for the digits Xak, Ybk (k=1 to n-1) of the two numbers has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xaj and the digit value Ybj and outputting the result as the code Tj,1 and
a connecting means for outputting the digit value Xaj as the code Tj,0 or a connecting means for outputting the digit value Ybj as the code Tj,0;
each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-p (p is an even number indicated as p=0 to m-1) of the sub binary tree has
a NOR logic means for taking the NOR logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1 and
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0;
each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-q (q is an odd number indicated as q=0 to m-1) of the sub binary tree has
a NAND logic means for taking the NAND logic of the code Ti,1 and the code Tj,1 and outputting the result as a code Tij,1, and
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti 1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0;
the higher priority determination node derived from the code T0,1 which originally should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-p (p is an even number indicated as p=0 to m-1) of the sub binary tree has
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0 and does not output the code Tij,1;
the higher priority determination node derived from the code T0,1 which should be output by the decision node performing the decision of existence of a carry for the LSBs of the two numbers among the higher priority determination nodes which serve as the nodes at the depth m-q (q is an odd number indicated as q=0 to m-1) of the sub binary tree has
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0 and does not output the code Tij,1;
when the number of leaves of the binary tree is not a power of 2, defines the higher priority determination node corresponding to the decision node performing the decision of existence of a carry for the LSBs of the two numbers as a dummy node for propagating the code T0,0 output by the decision node as it is;
has an exclusive OR logic means for taking the exclusive OR logic between the negative logic of the output code Tn-1,1 of the decision node performing the decision of existence of a carry for the MSBs of the two numbers and the code output Tij,0 of the higher priority determination node which serves as the root of the binary tree and defining this as the result of the sum for the MSBs of the two numbers when m is an even number; and
has an exclusive OR logic means for taking the exclusive OR logic between the negative logic of the output code Tn-1,1 of the decision node performing the decision of existence of a carry for the MSBs of the two numbers and the negative logic of the code output Tij,0 of the higher priority determination node which serves as the root of the binary tree and defining this as the result of the sum for the MSBs of the two numbers when m is an odd number.
44. An arithmetic and logic unit as set forth in claim 25, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
a higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, a code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and a code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
when any code X is assigned by a 2-bit binary number (X, 1, X, 0) defining the value code "Y" as {00}, value code "N"as {11}, and value code "Q" as {10} and defining {01} as "usage forbidden" (value code "F"), an OR logic is denoted by a "+" operator, an AND logic is denoted by a ".multidot." operator, and a negative logic is denoted by a " " operator, respectively,
the K operator is given as: ##EQU26##
45. An arithmetic and logic unit as set forth in claim 44, wherein each higher priority determination node has:
a first composite logical gate means for taking the OR logic between the AND logic of the code Ti,1 and the code Tj,1 and the code Ti,0 and outputting the result as the code Tij,1; and
a second composite logical gate means for taking the OR logic between the AND logic of the code Ti,1 and the code Tj,0 and the code Ti,0 and outputting the result as the code Tij,0.
46. An arithmetic and logic unit as set forth in claim 44, wherein:
when the number of decisions in the series of decision having an order dependency is n and a sub binary tree of the height m (m is the smallest integer exceeding log.sub.2 n) not including the leaves of the binary tree has Nm (Nm is the smallest integer exceeding n/2) number of higher priority determination nodes which serve as the nodes of a depth m and Ns (Ns is the smallest integer exceeding Ns+1/2) number of higher priority determination nodes which serve as the nodes of a depth s (s is an integer represented as s=1 to m-1),
a higher priority determination node which serves as a node at the depth m-p (p is an even number indicated as p=0 to m-1) of the sub binary tree has
a third composite logical gate means for taking the NOR logic between the AND logic of the code Ti,1 and the code Tj,1 and the code Ti,0 and outputting the result as the code Tij,1, and
a fourth composite logical gate means for taking the NOR logic between the AND logic of the code Ti,1 and the code Tj,0 and the code Ti,0 and outputting the result as the code Tij,0; and
a higher priority determination node which serves as a node at the depth m-q (q is an odd number indicated as q=0 to m-1) of the sub binary tree has
a fifth composite logical gate means for taking the NAND logic between the OR logic of the code Ti,1 and the code Tj,1 and the code Ti,0 and outputting the result as the code Tij,1, and
a sixth composite logical gate means for taking the NAND logic between the OR logic of the code Ti,1 and the code Tj,0 and the code Ti,0 and outputting the result as the code Tij,0.
47. An arithmetic and logic unit as set forth in claim 44, wherein:
when the arithmetic and logic unit performs a comparison of two n-bit binary numbers (Xa, Yb) and the comparison decisions for digits of the two numbers (Xai, Ybi; i=0 to n-1) form a series of decisions having an order dependency,
each decision node has
a NAND logic means for taking the NAND logic of negative logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a NOR logic means for taking the NOR logic of the negative logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,0.
48. An arithmetic and logic unit as set forth in claim 44, wherein:
when the decisions of existence of a carry for the digits (Xai, Ybi; i=0 to n-1) of two numbers in the addition of two n-bit binary numbers (Xa, Yb) forms a series of decisions having an order dependency,
each decision node has
a NAND logic means for taking the NAND logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a NOR logic means for taking the NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,0.
49. An arithmetic and logic unit as set forth in claim 25, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
a higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, a code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and a code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
when any code X is assigned by a 2-bit binary number (X, 1, X, 0) defining the value code "Y" as {01}, the value code "N" as {10}, and the value code "Q" as {11} and defining {00} as "usage forbidden" (value code "F"), an OR logic is denoted by a "+" operator, an AND logic is denoted by a " " operator, and a negative logic is denoted by a " " operator, respectively,
a K operator is given as: ##EQU27## and a higher priority determination node has
a seventh composite logical gate means for taking the OR logic between the AND logic of the code Ti,1 and the code Tj,1 and the code Ti,0 and outputting the result as the code Tij,1 and
an eighth composite logical gate means for taking the OR logic between the AND logic of the code Ti,0 and the code Tj,0 and the code Ti1 and outputting the result as the code Tij,0.
50. An arithmetic and logic unit as set forth in claim 25, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
a higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, a code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and a code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
when any code X is assigned by a 2-bit binary number (X, 1, X, 0) defining the value code "Y" as {00}, the value code "N" as {10}, and the value code "Q" as {11} and defining {01} as "usage forbidden" (value code "F"), an OR logic is denoted by a "+" operator, an AND logic is denoted by a ".multidot." operator, and a negative logic is denoted by a " " operator, respectively,
the K operator is given as: ##EQU28## and a higher priority determination node has
a ninth composite logical gate means for taking the AND logic between the OR logic of the code Ti,0 and the code Tj,1 and the code Ti,1 and outputting the result as the code Tij,1 and
an AND logic means for taking the AND logic of the code Ti,0 and the code Tj,0 and outputting the result as the code Tij,0.
51. An arithmetic and logic unit wherein,
when decisions of existence of a carry for the digits (Xai, Ybi; i=0 to n-1) of two numbers in the addition of two n-bit binary numbers (Xa, Yb) form a series of decisions having an order dependency,
has n number of decision nodes which respectively output "true or false" when the result of the sum of the same digit places becomes 2 or more, "false or true" when the result becomes zero, and "neither true nor false or do not know" when the result becomes 1 as the results of the decisions based on the digit values Xai, Ybi of the two numbers and
a higher priority determination node matrix comprising n number of rows and m number of columns (m is the smallest integer exceeding log.sub.2 n) with rows corresponding to the digits of the two numbers;
the group of the higher priority determination nodes of the first column has
a higher priority determination node of the zero-th row as a dummy node for propagating the result of decision of the decision node of the zero-th digit as it is and
a higher priority determination node of an h1-th row which receives as its input the result of decision of an h1-1-th digit and the decision node of the h1--th digit (h1=1 to n-1), outputs the result of decision of the decision node of the h1-th digit when the result of decision of the decision node of the h1-th digit is "true" or "false", and outputs the result of decision of the decision node of the h1-1-th digit when the result of decision of the decision node of h1-th digit is "neither true nor false or do not know";
the group of higher priority determination nodes of a k-th column (k=2 to m) has
higher priority determination nodes from the zero-th row to a 2.sup.k-1 -th row as the dummy nodes for respectively propagating the result of decisions of the higher priority determination nodes from the zero-th row to the 2.sup.k-1 -th row as they are and
a higher priority determination node of an hk-th row which receives as its input the results of decisions of the higher priority determination node of an hk-2.sup.k-1 -th row and the higher priority determination node of the hk-th row (hk=2.sup.k-1 to n-1), outputs the result of decision of the higher priority determination node of the hk-th row when the result of decision of the higher priority determination node of the hk-th row is "true" or "false", and outputs the result of decision of the higher priority determination node of the hk-2.sup.k-1 -th row when the result of decision of the higher priority determination node of the hk-th row is "neither true nor false or do not know"; and
the n number of decision nodes and the groups of higher priority determination nodes of the columns are respectively simultaneously processed.
52. An arithmetic and logic unit as set forth in claim 51, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
each higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, the code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and the code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
a K operator defines the value code "Y" or the value code "N" as the value code taken by the code Tij when the code Ti is the value code "Y" or the value code "N" and defines the value code taken by the code Tj as the value code taken by the code Tij when the code Ti is the value code "Q".
53. An arithmetic and logic unit as set forth in claim 51, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
each higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, the code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and the code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
when any code X is assigned by a 2-bit binary number (X, 1, X, 0) defining the value code "Y" as {11}, the value code "N" as {10}, and the value code as {0*} (here, "*" is "don't care"), an OR logic is denoted by a "+" operator, an AND logic is denoted by a ".multidot." operator, and a negative logic is denoted by a " " operator, respectively,
the K operator is given as: ##EQU29##
54. An arithmetic and logic unit as set forth in claim 53, wherein: the decision nodes from the first digit to the n-1-th digit each has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Xai as the code Ti,0 or a connecting means for outputting the digit value Ybi as the code Ti,0;
the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and does not output the code T0,1;
among the higher priority determination nodes not including the dummy nodes, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1 is "0", and outputting the result as the code Tij,0;
among the higher priority determination nodes not including the dummy nodes, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1 is "0", and outputting the result as the code Tij,0 and does not output the code Tij,1; and
the output code Tij,0 of the higher priority determination nodes from the zero-th row to the n-1-th row of the m-th column is used as the first digit to the n-1-th digit and the carry output of the arithmetic and logic unit and it is interpreted that "there is a carry output" when the output code Tij,0 is "1" and that "there is no carry output" when the output code Tij,0 is "0", respectively.
55. An arithmetic and logic unit as set forth in claim 54, having:
an exclusive OR logic means of the zero-th digit for taking the exclusive OR logic of the digit value Xa0 and the digit value Yb0 and
a sum generating means provided with an exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of the zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of the sum of the zero-th digits and exclusive OR logic means from the first row to the n-1-th row for taking the exclusive OR logic between each of the negative logics of the output codes Ti,1 of the decision nodes from the first digit to the n-1-th digit and each of the output codes Tij,0 of the higher priority determination nodes from the zero-th row to the n-2-th row of the m-th column and defining this as the result of the sum of the first digit to the n-1-th digit.
56. An arithmetic and logic unit as set forth in claim 53, wherein:
the decision nodes from the first digit to the n-1-th digit each has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Xai as the code Ti,0 or a connecting means for outputting the digit value Ybi as the code Ti,0;
the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and does not output the code T0,1;
the higher priority determination node of the zero-th row of the first column and the higher priority determination nodes from the zero-th row to the 2.sup.k-1 -th row (k=2 to m) of the k-th column are defined as dummy nodes which invert the result of decision of the decision node of the zero-th digit and the results of decisions of the higher priority determination nodes from the zero-th row to the 2.sup.k-1 -th row and propagate the same;
among the higher priority determination nodes of the m-p-th column (p is an even number indicated by p=0 to m-1) not including the dummy nodes, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0;
among the higher priority determination nodes of the m-q-th column (q is an odd number indicated by q=1 to m-1) not including the dummy nodes, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a NAND logic means for taking the NAND logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0;
among the higher priority determination nodes of the m-p-th column (p is an even number indicated by p=0 to m-1) not including the dummy nodes, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0 and does not output the code Tij,1;
among the higher priority determination nodes of the m-q-th column (q is an odd number indicated by g=1 to m-1) not including the dummy nodes, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0 and does not output the code Tij,1;
when m is an even number, the output codes Tij,0 of the higher priority determination nodes from the zero-th row to the n-1-throw of the m-th column are used as the first digit to the n-1-th digit and the carry output of the arithmetic and logic unit and it is respectively interpreted that "there is a carry output" when the output code Tij,0 is "1" and that "there is no carry output" when the output code Tij,0 is "0"; and
when m is an odd number, the output codes Tij,0 of the higher priority determination nodes from the zero-th row to the n-1-th row of the m-th column are used as the first digit to the n-1-th digit and the carry output of the arithmetic and logic unit and it is respectively interpreted that "there is a carry output" when the output code Tij,0 is "0" and that "there is no carry output" when the output code Tij,0 is "1".
57. An arithmetic and logic unit as set forth in claim 56, having
an exclusive OR logic means of the zero-th digit for taking the exclusive OR logic of the digit value Xa0 and the digit value Yb0 and,
when m is an even number,
a sum generating means provided with an exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of the zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of the sum of the zero-th digits and
exclusive OR logic means from the first row to the n-1-th row for taking the exclusive OR logic between each of the negative logics of the output codes Ti,1 of the decision nodes from the first digit to the n-1-th digit and each of the output codes Tij,0 of the higher priority determination nodes from the zero-th row to the n-2-th row of the m-th column and defining this as the result of the sum of the first digit to the n-1-th digit, and,
when m is an odd number,
a sum generating means provided with an exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of sum of the zero-th digits and
exclusive OR logic means from the first row to the n-1-th row for taking the exclusive OR logic between each of the negative logics of the output codes Ti,1 of the decision nodes from the first digit to the n-1-th digit and each of negative logics of the output codes Tij,0 of the higher priority determination nodes from the zero-th row to the n-2-th row of the m-th column and defining this as the result of the sum of the first digit to the n-1-th digit.
58. An arithmetic and logic unit wherein,
when the decisions of existence of a carry for the digits (Xai, Ybi; i=0 to n-1) of two numbers in the addition of two n-bit binary numbers (Xa, Yb) form a series of decisions having an order dependency,
it has n number of decision nodes which respectively output "true or false" when the result of the sum of the same digit places becomes 2 or more, "false or true" when the result becomes zero, and "neither true nor false or do not know" when the result becomes 1 as the result of a decision based on the digit values Xai, Ybi of the two numbers and
a higher priority determination node matrix consisting of n/2 number of rows and m number of columns (m is the smallest integer exceeding log.sub.2 n) with rows corresponding to the odd number digits of the two numbers;
the group of higher priority determination nodes of the first column has
a higher priority determination node of the h1-th row which receives as its input the results of the decisions of the h1-1-th digit and the decision node of h1-th digit (h1=odd number from 1 to n-1), outputs the result of decision of the decision node h1-th digit when the result of the decision of the decision node of the h1-th digit is "true" or "false", and outputs the result of the decision of the decision node of h1-1-th digit when the result of decision of the decision node of the h1-th digit is "neither true nor false or do not know";
the group of higher priority determination nodes of the k-th column (k=2 to m) has
higher priority determination nodes from the first to 2.sup.k-1 -th odd number rows as the dummy nodes for respectively propagating the results of decisions of the higher priority determination nodes from the first to 2.sup.k-1 -1-th odd number rows as they are and
a higher priority determination node of the hk-th row which receives as its input the result of decision of the higher priority determination node of the hk-2.sup.k-1 -th row and the higher priority determination node of the hk-th row (hk=odd number from 2.sup.k-1 to n-1), outputs the result of decision of the higher priority determination node of the hk-th row when the result of decision of the higher priority determination node of the hk-th row is "true" or "false", and outputs the result of decision of the higher priority determination node of the hk-2.sup.k-1 -th row when the result of decision of the higher priority determination node of the hk-th row is "neither true nor false or do not know"; and
the n number of decision nodes and the groups of the higher priority determination nodes of the columns are respectively simultaneously processed.
59. An arithmetic and logic unit as set forth in claim 58, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
each higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, the code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and the code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
the K operator defines the value code "Y" or the value code "N" as the value code taken by the code Tij when the code Ti is the value code "Y" or the value code "N" and defines the value code taken by the code Tj as the value code taken by the code Tij when the code Ti is the value code "Q".
60. An arithmetic and logic unit as set forth in claim 58, wherein:
when the result of decision "true" is defined as the value code "Y", "false" is defined as the value code "N", and "neither true nor false or do not know" is defined as the value code "Q", respectively,
each higher priority determination node is given as a K operator for deriving one code Tij.epsilon.{Y, N, Q} from two codes, that is, the code Ti.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the higher significant bit and the code Tj.epsilon.{Y, N, Q} derived from the result of decision of the decision node of the lower significant bit; and where the code Ti is superior to the code Tj,
when any code X is assigned by a 2-bit binary number (X,1, X,0) defining the value code "Y"as {11}, the value code "N" as {10}, and the value code "Q" as {0*} (here, "*" is "don't care"), an OR logic is denoted by a "+" operator, an AND logic is denoted by a ".multidot." operator, and a negative logic is denoted by " " operator, respectively,
the K operator is given as: ##EQU30##
61. An arithmetic and logic unit as set forth in claim 60, wherein: the decision nodes from the first digit to the n-1-th digit each has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Xai as the code Ti,0 or a connecting means for outputting the digit value Ybi as the code Ti,0;
the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and does not output the code T0,1;
among the higher priority determination nodes not including the dummy nodes, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
an OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1 is "0", and outputting the result as the code Tij,0;
among the higher priority determination nodes not including the dummy node, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1", selecting the code Tj,0 when the code Ti,1 is "0", and outputting the result as the code Tij,0 and does not output the code Tij,1;
the output code Tij,0 of the higher priority determination node of the n-1-th row of the m-th column is used as the carry output of the arithmetic and logic unit and it is interpreted that "there is a carry output" when the output code Tij,0 is "1" and that "there is no carry output" when the output code Tij,0 is "0", respectively;
the arithmetic and logic unit has
an exclusive OR logic means of the zero-th digit for taking the exclusive OR logic of the digit value Xa0 and the digit value Yb0 and
the sum generating means; and
the sum generating means has
an exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of the sum of the zero-th digits,
an exclusive OR logic means of the first row or taking the exclusive OR logic between the output code T0,0 of the decision node of the zero-th digit and the negative logic of the output code T1,1 of the decision node of the first digit and defining this as the result of the sum of the first digits,
a carry generating means of the f-th row for respectively selecting the input digit value Xaf or Ybf to the row when the output code Tf,1 of the decision node of the f-th digit (f=even number from 2 to n-1) is "1", selecting the output code of the higher priority determination node of the f-1-th row when the output code Tf,1 is "0", and outputting the result as the carry to the f+1-th digit,
an exclusive OR logic means of the f-th row for taking the exclusive OR logic between the negative logic of the output code Tf,1 of the decision node of the f-th digit and the output code of the higher priority determination node of the f-1-th row and defining this as the result of the sum of the f-th digits, and
an exclusive OR logic means of the f+1-th row for taking the exclusive OR logic between the negative logic of the output code Tf+1,1 of the decision node of the f+1-th digit and the output of the carry generating means of the f-th row and defining this as the result of the sum of the f+1-th digits.
62. An arithmetic and logic unit as set forth in claim 60, wherein:
the decision nodes from the first digit to the n-1-th digit each has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1, and
a connecting means for outputting the digit value Xai as the code Ti,0 or a connecting means for outputting the digit value Ybi as the code Ti,0;
the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and does not output the code T0,1;
the higher priority determination nodes of the first to 2.sup.k-1 -1-th (k=2 to m) odd number rows of the k-th column are defined as dummy nodes which respectively invert the results of decisions of the higher priority determination nodes of the first to 2.sup.k-1 -1-th odd number rows and propagate the same;
among the higher priority determination nodes of the m-p-th column (p is an even number indicated by p=0 to m-1) not including the dummy nodes, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for taking the negative logic of the result obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0;
among the higher priority determination nodes of the m-q-th column (q is an odd number indicated by q=1 to m-1) not including the dummy nodes, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a NAND logic means for taking the NAND logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0;
among the higher priority determination nodes of the m-p-th column (p is an even number indicated by p=0 to m-1) not including the dummy nodes, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a second selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0 and does not output the code Tij,1;
among the higher priority determination nodes of the m-q-th column (q is an odd number indicated by q=1 to m-1) not including the dummy nodes, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a third selecting means for taking the negative logic of the results obtained by respectively selecting the code Ti,0 when the code Ti,1 is "0" and the code Tj,0 when the code Ti,1 is "1" and outputting the result as the code Tij,0 and does not output the code Tij,1;
when m is an even number, the output code Tij,0 of the higher priority determination node of the n-1-th row of the m-th column is used as the carry output of the arithmetic and logic unit and it is respectively interpreted that "there is a carry output" when the output code Tij,0 is "1" and that "there is no carry output" when the output code Tij,0 is "0"; and
when m is an odd number, the output code Tij,0 obtained by taking the negative logic of the output code Tij,0 of the higher priority determination node of the n-1-th row of the m-th column is used as the carry output of the arithmetic and logic unit and it is respectively interpreted that "there is a carry output" when the output code Tij,0 is "1" and that "there is no carry output" when the output code Tij,0 is "0";
the arithmetic and logic unit has
an exclusive OR logic means of the zero-th digit for taking the exclusive OR logic of the digit value Xa0 and the digit value Yb0 and
the sum generating means;
the sum generating means has, when m is an even number,
the exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of the zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of the sum of the zero-th digits,
the exclusive OR logic means of the first row for taking the exclusive OR logic between the output code T0,0 of the decision node of the zero-th digit and the negative logic of the output code T1,1 of the decision node of the first digit and defining this as the result of the sum of the first digits,
the carry generating means of the f-th row for respectively selecting the input digit value Xaf or Ybf to the row when the output code Tf, 1 of the decision node of the f-th digit (f=even number from 2 to n-1) is "1", selecting the output code of the higher priority determination node of the f-1-th row when the output code Tf,1 is "0", and outputting the result as a carry to the f+1-th digit,
the exclusive OR logic means of the f-th row for taking the exclusive OR logic between the negative logic of the output code Tf,1 of the decision node of the f-th digit and the output code of the higher priority determination node of the f-1-th row and defining this as the result of the sum of the f-th digits, and
the exclusive OR logic means of the f+1-th row for taking the exclusive OR logic between the negative logic of the output code Tf+1,1 of the decision node of the f+1-th digit and the output of the carry generating means of the f-th row and defining this as the result of the sum of the f+1-th digits, while,
when m is an odd number,
an exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of the sum of the zero-th digits,
an exclusive OR logic means of the first row for taking the exclusive OR logic between the output code T0,0 of the decision node of the zero-th digit and the negative logic of the output code T1,1 of the decision node of the first digit and defining this as the result of the sum of the first digits,
a carry generating means of the f-th row for respectively selecting the input digit value Xaf or Ybf to the row when the output code Tf,1 of the decision node of the f-th digit (f=even number from 2 to n-1) is "1" selecting the negative logic of the output code of the higher priority determination node of the f-1-th row when the output code Tf,1 is "0", and outputting the result as the carry to the f+1-th digit,
an exclusive OR logic means of the f-th row for taking the exclusive OR logic between the negative logic of the output code Tf,1 of the decision node of the f-th digit and the negative logic of the output code of the higher priority determination node of the f-1-th row and defining this as the result of the sum of the f-th digits, and
an exclusive OR logic means of the f+1-th row for taking the exclusive OR logic between the negative logic of the output code Tf+1,1 of the decision node of the f+1-th digit and the output of the carry generating means of the f-th row and defining this as the result of the sum of the f+1-th digits.
63. An arithmetic and logic unit as set forth in claim 60, wherein:
the decision nodes from the first digit to the n-1-th digit each has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Xai as the code Ti,0 or a connecting means for outputting the digit value Ybi as the code Ti,0;
the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and does not output the code T0,1;
among the higher priority determination nodes not including the dummy node, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
an OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0;
among the higher priority determination nodes not including the dummy node, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0 and does not output the code Tij,1;
an output code Tij,0 of the higher priority determination node of the n-1-th row of the m-th column is used as the carry output of the arithmetic and logic unit and it is respectively interpreted that "there is a carry output" when the output code Tij,0 is "1" and that "there is no carry output" when the output code Tij,0 is "0";
the arithmetic and logic unit has
an exclusive OR logic means of the zero-th digit for taking the exclusive OR logic of the digit value Xa0 and the digit value Yb0 and
a sum generating means; and
the sum generating means has
an exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of sum of the zero-th digits,
an exclusive OR logic means of the first row for taking the exclusive OR logic between the output code T0,0 of the decision node of the zero-th digit and the negative logic of the output code T1,1 of the decision node of the first digit and defining this as the result of the sum of the first digits,
a carry generating means of the f-th row for taking the negative logic of the results obtained by respectively selecting the input digit value Xaf or Ybf to the row when the output code Tf,1 of the decision node of the f-th digit (f=even number from 2 to n-1) is "1" and selecting the output code of the higher priority determination node of the f-1-th row when the output code Tf,1 is "0" and outputting the result as a carry to the f+1-th digit,
an exclusive NOR logic means of the f-th row for taking the exclusive NOR logic between the output code Tf,1 of the decision node of the f-th digit and the output code of the higher priority determination node of the f-1-th row and defining this as the result of sum of f-th digits, and
an exclusive OR logic means of the f+1-th row for taking the exclusive OR logic between the output code Tf+1,1 of the decision node of the f+1-th digit and the output of the carry generating means of the f-th row and defining this as the result of the sum of the f+1-th digits.
64. An arithmetic and logic unit as set forth in claim 60, wherein:
the decision nodes from the first digit to the n-1- digit each has
an exclusive NOR logic means for taking the exclusive NOR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Xai as the code Ti,0 or a connecting means for outputting the digit value Ybi as the code Ti,0;
the decision node of the zero-th digit has
a NOR logic means for taking the NOR logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic means when the carry input to the arithmetic and logic unit is "1" and selecting the output of the NAND logic means when the carry input is "0" and outputting the result as the code T0,0 and does not output the code T0,1;
among the higher priority determination nodes not including the dummy node, each higher priority determination node not derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
an OR logic means for taking the OR logic of the code Ti,1 and the code Tj,1 and outputting the result as the code Tij,1 and
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0;
among the higher priority determination nodes not including the dummy node, the higher priority determination node derived from the code T0,1 which originally should be output by the decision node of the zero-th digit has
a selecting means for respectively selecting the code Ti,0 when the code Ti,1 is "1" and the code Tj,0 when the code Ti,1 is "0" and outputting the result as the code Tij,0 and does not output the code Tij,1;
the output code Tij,0 of the higher priority determination node of the n-1-th row of the m-th column is used as the carry output of the arithmetic and logic unit and it is respectively interpreted that "there is a carry output" when the output code Tij,0 is "1" and that "there is no carry output" when the output code Tij,0 is "0";
the arithmetic and logic unit has
an exclusive OR logic means of the zero-th digit for taking the exclusive OR logic of the digit value Xa0 and the digit value Yb0 and
a sum generating means; and
the sum generating means has
an exclusive OR logic means of the zero-th row for taking the exclusive OR logic of the output of the exclusive OR logic means of zero-th digit and the carry input to the arithmetic and logic unit and defining this as the result of sum of the zero-th digits,
an exclusive OR logic means of the first row for taking the exclusive OR logic between the output code T0,0 of the decision node of the zero-th digit and the negative logic of the output code T1,1 of the decision node of the first digit and defining this as the result of the sum of the first digits,
a NAND logic means for taking the NAND logic between the output code Tf,1 of the decision node of the f-th digit (f=even number from 2 to n-1) and the input digit value Xaf or Ybf to the row,
an exclusive OR logic means for taking the exclusive OR logic of the output code Tf+1,1 of the decision node of the f+1-th digit and the output of the NAND logic means and outputting the zero-th selected signal of the f+1-th row,
an exclusive NOR logic means of the f-th row for taking the exclusive NOR logic between the output code Tf,1 of the decision node of the f-th digit and the zero-th selected signal of the f+1-th row and outputting the first selected signal of the f+1-th row,
an exclusive NOR logic means for taking the exclusive NOR logic between the output code Tf,1 of the decision node of the f-th digit and the output code of the higher priority determination node of the f-1-th row and defining this as the result of the sum of the f-th digits, and
a sum generation selecting means of the f+1-th row for taking the negative logic of the results obtained by respectively selecting the first selected signal of the f+1-th row when the output code of the higher priority determination node of the f-1-th row is "1" and selecting the zero-th selected signal of the f+1-th row when the output code is "0" and defining the result as the result of the sum of the f+1-th digits.
65. An arithmetic and logic unit as set forth in claim 66, wherein:
when the decisions of existence of a borrow for digits (Xai, Ybi; i=0 to n-1) of two numbers in the subtraction (Xa-Yb) of two n-bit binary numbers form a series of decisions having an order dependency,
each decision node has
an exclusive OR logic means for taking the exclusive OR logic of the digit value Xai and the digit value Ybi and outputting the result as the code Ti,1 and
a connecting means for outputting the digit value Ybi as the code Ti,0.
66. An arithmetic and logic unit as set forth in claim 65, wherein:
the decision node performing a decision of the existence of a borrow for the LSBs (least significant bits) of the two numbers has
a NOR logic means for taking the NOR logic of Xa0 of the negative logic of the digit value Xa0 and the digit value Yb0,
a NAND logic means for taking the NAND logic of Xa0 of the negative logic of the digit value Xa0 and the digit value Yb0, and
a selecting means for taking the negative logic of the results obtained by respectively selecting the output of the NOR logic |
