Research On Several Issues Of Prefix Computation On Computer Arithmetic

Computer arithmetic, a traditional research topic, is still a hot-spot with unceasing improvements. While the process and scale of integrated circuit gets dramatically progress, arithmetic operations implemented in hardware circuitry are becoming more and more abundant, and the operand is becoming wider and wider. However, binary fixed-point (integer) adder is always the most common and fundamental arithmetic operation in kinds of integrated circuits, such as general-purposed processor (GPP), digital signal processor (DSP) and application-specific integrated circuit (ASIC). So it is crucial to thoroughly and systematically research integer adders and various processing techniques used in kinds of arithmetic units.Based on the basic concepts and illustration method of prefix computation, this dissertation proposes a series of relevant concepts, definitions, theorems and inferences, such as span and span space of prefix computing graph, which improve and enrich the prefix computation theory system, therefore provide the rationale for subsequent researches and demonstrations.This dissertation analyses computation principles of various classical adders deeply and systematically, and provides necessary demonstrations. On the one hand, the adder, from the aspect of logical function, is decomposed into three stages for computation: computing of carry condition of each bit, computing of carry chain and computing of final sum according to the resulting carry situation of carry chain; On the other hand, construction methodologies of carry chains of various adders are unified to four kinds of block-based recursion expansion organizations, hence the underlying unified model for integer adders is presented.By evolving the last computing stage, "computing of final sum according to the resulting carry situation of carry chain", this dissertation indicates that based on integer adders with various carry chain structures, various "extended" addition operations, such as dual addition, modulo addition and absolute of difference, can be implemented with minor logic modification to the last computing stage of adders.In this dissertation, novel schemes for modulo 2~n－1 addition operation and modulo 2~n+1 addition operation respectively are proposed, analyzed, and demonstrated. As for the modulo 2~n－1 addition operation, loop-demolished approach is adopted, which is applicable for 1-complement representation, 2-complement representation and unsigned...