計(jì)算機(jī)算術(shù)中若干前綴計(jì)算問題的研究.pdf

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

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

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

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

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