計算機算術中若干前綴計算問題的研究.pdf

1、計算機算術是一個亙古而恒新的論題。隨著微電子技術的飛速進步，以硬件電路來實現(xiàn)的算術運算種類越來越豐富、運算器的位寬越來越大。但是二進制定點整數(shù)加法始終是通用微處理器、數(shù)字信號處理器（DSP）和專用集成電路（ASIC）等各類集成電路中最常用和最基礎的算術運算。透徹而系統(tǒng)地研究整數(shù)加法器以及各種算術運算單元中的各項處理技術意義重大。 本文以前綴計算的基本概念和圖示方法為基礎提出前綴計算圖的張度、張度空間等一系列相關概念、定義和定理與

2、推論，完善和豐富了前綴計算的理論體系，為本文的后續(xù)研究和證明提供理論基礎。 本文對各種經(jīng)典加法器的計算原理深入、系統(tǒng)地進行分析和必要的證明，一方面從邏輯功能的角度將加法器分解成“計算各單個位上的進位條件”、“進位鏈計算”和“根據(jù)進位情況計算最終和”三部分計算，另一方面將各種加法器的進位鏈構成方式統(tǒng)一成四種分塊遞歸擴展組織方式，提出了整數(shù)加法器計算和構成的內在統(tǒng)一模型。 本文通過對“根據(jù)進位情況計算最終和”這一部分進行演化

3、，指出能夠以各種不同進位鏈結構的整數(shù)加法器為基礎而僅以極少量電路邏輯改變“根據(jù)進位情況計算最終和”就實現(xiàn)各種“拓廣加法”運算，如雙加運算、模加運算和差的絕對值求解。 本文提出并分析、證明“模2″－1加”和“模2″＋1加”的新算法。對于“模2″－1加”運算，提出了拆環(huán)式的新方案，既可以用于1補碼，也可以用于二進制原碼和補碼；對于“模2″＋1加”運算，改變了傳統(tǒng)的基于縮一碼的作法，改為基于原碼直接進行計算，不僅改進了計算性能還減少了

4、為了實現(xiàn)計算而進行的編碼轉換開銷。 本文將構建的前綴計算理論體系和整數(shù)加法器的內在統(tǒng)一模型應用于構造三類前綴計算圖：最小深度前綴計算圖的規(guī)則構造、最小深度前綴計算圖的混合結構構造以及任意深度最小延遲前綴計算圖的構造。進一步定義一系列概念（如計算自由度、可行區(qū)間等）、提出并證明一系列定理和推論，并以此為基礎構造求解算法并對算法的正確性進行形式證明。 本文將前綴計算理論應用于前導零問題。從前綴計算的角度，提出一系列的定義、定

5、理，證明了前導零檢測算法本質上都可以歸結為前綴計算問題，因而適用遞歸式求解方法。在此基礎之上，給出了前導零的二分遞歸檢測算法，并加以證明；對于前導零的預測方法，通過對加法運算量做“借位留存”減法，將對兩個運算量的預測轉換為對｛1，0，-1｝數(shù)字字符集上的數(shù)字串的特征檢測問題，從而能夠應用二分遞歸求解方法；經(jīng)過細致分析、通過采用了消除連續(xù)的“-1”串的重編碼技術而提出了一種統(tǒng)一位串形式來預測前導零的位數(shù)，并設計出一組位串構成形式的遞歸判別