二進位數並行連加運算的化簡方法及連加器電路的製作方法
2023-09-21 06:32:15 1
專利名稱：二進位數並行連加運算的化簡方法及連加器電路的製作方法
技術領域：
本發明涉及一種計算機二進位運算方法，特別是涉及一種二進位數連加運算的化簡方法。本發明還涉及一種二進位連加運算的連加器電路。
背景技術：
目前計算機在做二進位數連加運算時，一般採用的方法是逐級運算，即兩個數相加得出結果後再與第三個數相加，或者是兩兩同時相加後再將結果兩兩相加，依此類推，得出最終結果，其運算是一個或幾個二進位數加法器同時參與運算來完成的。
至於可以轉化為連加運算的乘法運算，目前計算機大多採用陣列乘法器運算電路。(見《計算機組成原理》白中英編著，科學出版社，2000年11月第三版，第39頁)。這種運算方法，以不帶符號的n位×n位二進位數陣列乘法器為例，假定陣列最後一行使用行波進位加法器，則需要n(n-1)個全加器和n2個與門，雖然邏輯門數量較少，但運算速度比較慢。
發明內容
本發明的目的在於提供一種二進位數連加運算的化簡方法；本發明的目的還在於提供一種二進位數連加運算的化簡運算連加器電路。採用本發明提供的方法與電路，能夠減少運算時間，提高計算機的運算速度。
為了達到上述目的，本發明一種二進位數連加運算的化簡方法採用的技術方案是將所有相加的二進位數中具有相同位權的數據組成列，通過同時對每一列欲加的數進行相加運算得到各自相加後的本位和對高位的進位，將運算結果轉換成由較少的幾個多位二進位數的連加運算，再對所述連加運算重複上述處理過程，將運算結果轉換為由更少的幾個多位二進位數的連加運算，繼續對新的運算重複上述過程，一直到將運算轉換為二個多位的二進位數的相加運算，每次化簡前後連加的二進位數的數量滿足如下的約束關係，n個二進位數的連加運算，若n滿足2k-1≤n＜2k，化簡後，可轉換成k個二進位數的連加運算；最後再用現有的計算二個多位二進位相加運算的加法器，算出最終結果。
現假定有n個不同的m位二進位數相加，所有在相同的位的數組成列，例如所有個位組成一列，則共有m列數據，每列均含有n個數，對任一列數，其n個數加合後的得數由本位和對高位的進位組成，若n滿足2k-1≤n＜2k則不難得知，這n個數相加後，其進位最多可進至其前第k-1位。換句話說，這n個數加合後，將向其高位進位，最高可進至該位前的第(k-1)位。其餘各列數相加後情況也是如此。我們對上述的列的數據同時相加，分別得到相加後的本位和對高位的進位。這樣，相加後得數的任意一位應由以下幾個數加合而成與該位位數相同的n個數相加得出的本位，以及低於該位的各列數各自相加後對該位的進位。易知，有可能向該位進位的數列的位最低可至該位後k-1位，更低位的數列加合後向該位無進位，或說向該位的進位恆為零。故該位數將由1個本位數和k-1個低位對該位的進位數共k個數組成。因此，n個m位二進位數的相加運算就可以轉換為k個m+k-1位二進位數的相加運算。k＜n。
同理，若k又滿足2l-1≤k＜2l則我們可以把這k個m+k-1位二進位數的相加運算轉換成L個多位二進位數的相加運算，L＜k。依此類推，最終將之轉換為二個多位二進位數的相加運算。
從以上敘述可以知道，只要我們算出所有每列數據相加後的得數，就可經過若干步驟，將上述n個m位的二進位數的相加運算轉換成二個多位二進位數的相加運算。對任意一列數據，當n較小時我們可以列出真值表，運用邏輯函數法直接得出相加後的二進位數的得數。但當n較大時，用邏輯函數法將因為表達式過於複雜而難以實現。我們注意到，對每一列數據的相加運算的運算結中果將取決於該列數中值為1的數的個數，只要知道了值為1的數的數量，將可以決定該列數相加後所得的本位和對高位的進位。如何知道某列數中值為1的數的數目呢？在此我們採用如下方法，以某一列有n個數為例先將這n個數置放於某n位寄存器中，然後對該寄存器的各個數進行邏輯運算，將其中值為1的數全部集中放在n個輸出端的低位，值為0的數全部放在n個輸出端的高位，且值為1的數的數量與n個輸入端所含的1的數量相同。然後對n個輸出端的所有相鄰位各自分別兩兩進行異或運算。最低位再和「1」異或。最高位和「0」異或。所有各個異或的輸出中必有也僅有一個輸出為「1」。根據該位輸出信號的位置就可知道n個數中值為「1」的數的數量。由此進一步判斷出它們相加後所得的進位和本位，並將它們送至適當位置，以準備下一輪的簡化運算。
本發明的化簡運算連加器電路的技術方案是一種二進位數連加運算的化簡運算連加器電路，包括若干級的化簡電路和一個最終的加和電路，其中每一級的作用在於將數量較多的連加運算轉換為數量較少的二進位數的連加運算，最終加和電路的作用多個多位二進位數的連加運算經過若干次化簡後，轉換成兩個二進位數的相加運算，然後用現有的計算兩個二進位數相加運算的加法器，算出最終結果。
所述若干級的化簡電路的作用是對所有各列數據同時分別進行運算，對任意一列而言，列中的所有數據相加得到本位及對高位的進位，並把這些本位和進位分別送到與它們位數相符合的下一級化簡運算電路的適宜的數據列中；每個列中的數的相加運算電路至少包括列數據排列電路，每一列數中的「1」的數目的判斷電路，列中各數相加後的本位和進位的判斷電路及將本位和各個進位送到進行下一次化簡運算時將要使用的適宜的數據列中的傳送電路。
所述數據排列電路，將列中值為「1」的數據排列到該列的低位段，該列數「1」的數量不發生改變；當列中的數的數量較少時，根據真值表設計電路，該電路能一次完成數據排列的工作，當列中的數的數量較多時，可將列中的數按從低位到高位的順序，分割成幾組，對各組的數，分別同時進行數據排列，將各組中的各自所有的「1」，分別排列到各組的低位段，然後依然是從低位到高位，每兩個相鄰的數據小組構成一個大組，對各大組的數，分別同時進行數據排列，將各大組中所有的「1」分別排列在各大組的低位段，然後依然是從低位到高位，每兩個相鄰的大組構成一個更大的數據組，對它們再次進行排列，--------，一直到列中所有的「1」被排列在該列的低位段。
所述判斷電路對於已完成數據排列的各個列中所有兩兩相鄰的數據進行異或運算，且最低位還要和「1」進行異或，最高位還要和「0」進行異或，根據輸出為「1」的異或門的位置即得到列中「1」的數量及列中所有數相加後所得到的本位以及對高位的進位。
所述傳送電路作用是將本次化簡所得到的本位及對高位的進位分別放在下一次化簡運算所使用的數據列中與其位權相符的數據列裡，每一個新的數據列中的各個數據在新的連加運算式中屬於相同位權的數據。
本發明的方法可用於所有可一次性轉換為二進位連加運算的運算式的運算；本發明的方法可實現通用的二進位數連加加法器。
本發明的應用範圍1、乘法我們知道二個二進位數的乘法運算可以轉換為多個二進位數的相加運算，故本法可以算二個二進位數的相乘運算。
2、多項式的代數和只要每一項中乘法運算的次數不超過一次，則該多項式的代數和可直接由多個二進位數的和表達出來，故可用本法計算。
3、連乘運算以m＝x·y·z為例，先用本算法計算x·y，當將x·y用本法化簡成二個多位二進位數相加運算x·y＝a+b時，再與z相乘m＝(x·y)·z＝a·z+b·z這樣，又變成了多個二進位數的相加運算，再次運用本算法可算出最終結果，以上運算省了一次二個二進位數的加合運算，即未將a+b算出結果後再與z相乘，故節省了運算時間。
4、n太大時的處理方法當n太大時，運算電路將變得較為複雜，可將n分成兩部份或三部份，分別同時進行一次化簡運算後，再把結果加在一起，以便進行第二次化簡。
以對存放任一列數的寄存器Ri的運算電路為例圖1-1是16位寄存器低位數ri，3ri，2ri，1ri，0將「1」移位到該四位低位的邏輯電路圖；圖1-2是16位寄存器將數ri，7、ri，6、ri，5、ri，4中「1」移位到該四位低位的邏輯電路圖；圖1-3是16位寄存器將數ri，11、ri，10、ri，9、ri，8中「1」移位到該四位低位的邏輯電路圖；圖1-4是16位寄存器將數ri，15、11ri，14、ri，13、ri，12中「1」移位到該四位低位的邏輯電路圖；圖2-1是在圖1-1、1-2基礎上，ri，7、ri，6、ri，5、ri，4、ri，3ri，2ri，1ri，0中所有的「1」移位到該八位低位的邏輯電路圖；圖2-2是在圖1-3、1-4基礎上，ri，15、11ri，14、ri，13、ri，12、ri，11、ri，10、ri，9、ri，8中所有的「1」移位到該八位低位的邏輯電路圖；圖3-1與圖3-2是在圖2-1、圖2-2基礎上將Ri中16個數中所有的「1」排在該十六位低位的邏輯電路圖；圖4是在圖3-1與圖3-2基礎上，對Ri中含有「`1」的數量進行判斷、進而決定所有位上的數相加後所得本位和進位、並送至各個五位的K寄存器相應位的邏輯電路圖；圖5-1與圖5-2是對任一K寄存器KJ(j＝0，1，2，3，4)中含有「1」的數量進行判斷的邏輯電路圖；圖6是在圖5-1與圖5-2基礎上，對KJ寄存器中所有位上相同的數相加後所得的本位和進位進行判斷，並送至各個三位Q寄存器相應位的邏輯電路圖；圖7是將任一Q寄存器Qm(m＝0，1，2)中所有位相加後所得的本位和進位進行判斷，並送至S寄存器相應位的邏輯電路圖；圖8是通用二進位數連加器的設計框圖；圖9是n個多位二進位數連加的化簡框圖；圖10是n個多位二進位數連加，在n較大時的化簡框圖；具體實施方式
實施方式1參照圖9，為更清楚地說明本化簡方法及連加器電路的設計方法，在這裡取n為16，16個16位二進位數的相加計算為例(所使用的寄存器都預先清零)。
我們將各列數 存放於16位寄存器Ri(i＝0，1，2，……15)中，例如將a0，b0……p。16個數放於R0中。
第一次化簡；對所有列進行並行邏輯運算，因為n＝16，24＝16＜25，可將16個二進位數相加運算轉換為5個二進位數的相加運算，見圖1-1，1-2，1-3，1-4，2-1，2-2，3-1，3-2，及圖4所示。以任一列Ri為例，其各位記為ri，15，ri，14，……ri，0分別存放pi，oi，……bi，ai。
參見圖1-1～圖1-4，在圖1-1～圖1-4中，將Ri內容分成4組，分別為ri，15，ri，14，ri，13，ri，12；ri，11，ri，10，ri，9，ri，8，；ri，7，ri，6，ri，5，ri，4；ri，3，ri，2，ri，1，ri，0。
圖1-1功能此圖輸入為A3(ri，3)，A2(ri，2)，A1(ri，1)，A0(ri，0)，輸出為B3，B2，B1，B0，4個輸出信號中值為「1」的被集中放在四個輸出的低位。「1」的數量與A3，A2，A1，A0中所含的「1」數量相同。
圖1-1對應的真值表是表1。
由表1的真值表所得表達式如下B0＝A3+A2+A1+A0B1＝(A3+A2+A1)·(A3+A2+A0)·(A3+A1+A0)·(A2+A1+A0)B2＝A3·A2·A1+A3·A2·A0+A3·A1·A0+A2·A1·A0B3＝A3·A2·A1·A0圖1-2，圖1-3，圖1-4功能同圖1-1完全相同。
圖2-1功能輸入為B7，B6，B5，B4，B3，B2，B1，B0，輸出為C7，C6，C5，C4，C3，C2，C1，C0，8個輸出信號中值為「1」的被集中排在其低位上。「1」的個數與8個輸入信號中所含的「1」的數量相同。圖2-1是將高4位的數同時向低位移動，要移動幾位是由低4位數中「1」的個數所決定。例如，已知低4位只有表1 與圖1-1對應的真值表
一個「1」，B1B0＝1，則高4位數均向低位移3位。
圖2-2功能輸入為B15，B14，B13，B12，B11，B10，B9，B8，輸出為C15，C14，C13，C12，C11，C10，C9，C8，功能與圖2-1完全相同。
圖3-1與圖3-2功能此二圖輸入為C15，C14，C13，C12，C11，C10，C9，C8，C7，C6，C5，C4，C3，C2，C1，C0，輸出為D15，D14，D13，D12，D11，D10，D9，D8，D7，D6，D5，D4，D3，D2，D1，D0，16個輸出信號中值為「1」的集中在低位，值為「1」的數的數量與16個輸入中值為「1」的數的個數相同，設計思路與圖2-1相同。
圖4功能輸入為D15，D14，D13，D12，D11，D10，D9，D8，D7，D6，D5，D4，D3，D2，D1，D0，將相鄰的輸入分別進行異或運算。並且最低位D0還要與「1」異或，最高位即D15還要與「0」信號異或，這樣共得到17個異或運算的輸出。分別記為E16，E15，E14，E13，E12，E11，E10，E9，E8，E7，E6，E5，E4，E3，E2，E1，E0。其中有且僅有一個為1。例如，當E7＝1時，表明D15，D14，D13，D12，D11，D10，D9，D8，D7，D6，D5，D4，D3，D2，D1，D0，這16個輸入中共總有7個「1」，這16個數相加後的值為00111，表明相加後，本位值為「1」(在此本位為第i位)。並且向其前一位(第i+1位)，前兩位(第i+2位)，分別有為「1」的進位。向其前第3位，第4位的進位均為0。電路中將其本位和進位分別送至各個寄存器中合適的位置，見圖4所示，故第i列的16個數相加後進位最多可進至其前第4位。亦即相加後第i+1、i+2、i+3、i+4、均可能有其進位。在圖4中，各個5位KJ(J＝0，1，2，……19)寄存器存放第一次化簡的結果。例如，ki，0是指Ki寄存器的最低位。ki，0中存放Ri中所有數據相加後所得的本位。Ki，1中存放Ri-1中所有數據相加後所得的對i-1前一位即第i位的進位。
ki，2中存放Ri-2中所有數據相加後所得的對i-2位的前2位即第i位的進位。
ki，3中存放Ri-3中所有數據相加後所得的對其(即第i-3位)前3位(即第i位)的進位。
ki，4中存放Ri-4中所有數據相加後所得的對其前4位即第i位的進位。
其它5位寄存器中存放數據的規律與Ki寄存器的相同。
總之，經電路圖1、圖2、圖3、圖4的運算，16個二進位數據的相加運算被轉化成了5個二進位數的相加運算。這5個二進位數的所有位上的數據全部存在各個K寄存器中，位權相同的數組成列，被放在同一寄存器中。
第二次化簡參見圖5，圖6將5個二進位數據的相加運算轉換為3個二進位數的相加運算。
圖5-1及5-2功能對任一K寄存器如KJ中的各位進行相加運算，電路的輸入信號記為G4、G3、G2、G1、G0。輸出為H5、H4、H3、H2、H1、H0，6個輸出信號中有且僅有一個為「1」。它反映了G4、G3、G2、G1、G05個輸入中值為1的數的數量。如H3＝1，表明，5個輸入中3個為1，兩個為0。
圖5-1、5-2電路是直接用邏輯函數法設計出來的，當然我們仍然可以使用前述設計思路將KJ中值為1的數集中移到低位，用異或運算判斷1的數量，然後將其對應的本位和進位送至Q寄存器中。
與圖5-1、5-2對應的真值表是表2。
由表2的真值表所得出的邏輯表達式如下H0＝G4+G3+G2+G1+G0H1＝G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0H2＝G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0H3＝G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0H4＝G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0+G4·G3·G2·G1·G0H5＝G4·G3·G2·G1·G0圖6功能輸入為H5、H4、H3、H2、H1、H0，此圖是將相加後得的本位和進位送至各個3位Q寄存器中。
第三次化簡，參見圖7將3個二進位數的相加運算轉換為2個二進位數的相加運算。
圖7功能化簡方法與第二次化簡一樣即先用邏輯函數法直接判斷1的個數，然後將其對應的本位和進位送至2位S寄存器中。
與圖7對應的真值表是表3。
表2 與圖5-1、圖5-2對應的真值表
表3 與圖7對應的真值表
由表3的真值表所得邏輯表達式如下L0＝J2+J1+J0L1＝J2·J1·J0+J2·J1·J0+J2·J1·J0L2＝J2·J1·J0+J2·J1·J0+J2·J1·J0L3＝J2·J1·J0在此我們也可以利用標準全加器電路來運算。
實施方式2通用二進位連加器的設計參見圖8為使連加器具備以下功能，即只要n在允許的範圍內，都可以進行化簡運算，並得出結果，且當n較小時，所花的計算時間要比n較大時所花的時間少，我們可以按照圖8所示的方案來設計能實現上述功能的通用二進位連加器，(框圖中n的最大取值為63，實際設計時n的最大取值當然不局限於此)為使連加器既可以化簡當n較大時的二進位數的連加運算，又可以在計算數量n較小時計算的速度更快一些。為此我們根據n的範圍把化簡電路的輸入端數量進行規定
① n＝3情形下化簡一次的電路例如三個相加的二進位數每列的數都有三個，它們被放在ri，3、ri，2、ri，1、ri，0中。當然ri，3此時必定為「0」。我們對ri，3、ri，2、ri，1、ri，0中「1」的數量進行判斷，然後確定其相加後的進位、本位，並將本位、進位送至相應合適位置，從而將三個數相加轉換為二個數相加。
② 4≤n＜8情形下化簡一次的電路我們用寄存器中的低8位來存放在n個相加的二進位相同位上的n個數，判斷它們相加後的本位和進位。從而相加運算轉換成為三個數的相加運算。
③ 8≤n＜16情形下化簡一次的電路我們用寄存器中的低16位來存放這n個數，化簡運算後，轉化為4個數的相加運算，屬4≤n＜8情形。
④ 16≤n＜32時，依此類推。
圖8為n個二進位數相加的流程圖，假定此連加器最多可加63個數，即n的範圍為2≤n＜64。參照此圖，可進行n較大，例如n多達63時的連加運算，又可以在n較小時進行連加運算，速度能相對快一些。
實施方式3參見圖10當多個二進位數連乘時，不算出中間的乘積結果，將兩個二進位數的相乘化簡為二個二進位數的相加，不算出相加結果，直接與第三個數相乘，再應用本算法將其化簡為兩個二進位數的相加運算，--------，直到最後一次乘法運算時，再化為二個二進位數相加運算後，再進一步算出最終結果。
儘管描述本發明的特定實施例介紹了本發明，但應理解到，精精通本領域的人員，可以對本發明進行形式上的和細節上的各種修改，而不脫離本發明的方案與範圍。
權利要求
1.一種二進位數並行連加運算的化簡方法，其特徵在於所有相加的二進位數中具有相同位權的數據組成列，通過同時對每一列欲加的數進行相加運算得到各自相加後的本位和對高位的進位，將運算結果轉換成由較少的幾個多位二進位數的連加運算，再對所述連加運算重複上述處理過程，將運算結果轉換為由更少的幾個多位二進位的連加運算，繼續對新的運算重複上述過程，一直到將運算轉換為二個多位的二進位的相加運算，每次化簡前後連加的二進位數的數量滿足如下的約束關係，n個二進位數的連加運算，若n滿足2k-1≤n＜2k，化簡後，可轉換成k個二進位數的連加運算；最後再用現有的計算二個多位二進位相加運算的加法器，算出最終結果。
2.根據權利要求1所述的二進位數並行連加運算的化簡方法，其特徵在於當多個二進位數連乘時，不算出中間的乘積結果，將兩個二進位數的相乘化簡為二個二進位數的相加，不算出相加結果，直接與第三個數相乘，再應用本算法將其化簡為兩個二進位數的相加運算，--------，直到最後一次乘法運算時，再化為二個二進位數相加運算後，再進一步算出最終結果。
3.一種實現權利要求1所述的二進位數並行連加運算的化簡方法的連加器電路，其特徵在於該電路包括若干級的化簡電路和一個最終的加和電路，其中每一級的作用在於將數量較多的連加運算轉換為數量較少的二進位數的連加運算，最終加和電路的作用多個多位二進位數的連加運算經過若干次化簡後，轉換成兩個二進位數的相加運算，然後用現有的計算兩個二進位數相加運算的加法器，算出最終結果。
4.根據權利要求3所述的一種實現權利要求1所述的二進位數並行連加運算的化簡方法的連加器電路，其特徵在於所述若干級的化簡電路的作用是對所有各列數據同時分別進行運算，對任意一列而言，列中的所有數據相加得到本位及對高位的進位，並把這些本位和進位分別送到與它們位權相符合的下一級化簡運算電路的適宜的數據列中；每個列中的數的相加運算電路至少包括列數據排列電路，每一列數中的「1」的數目的判斷電路，列中各數相加後的本位和進位的判斷電路及將本位和各個進位送到進行下一次化簡運算時將要使用的適宜的數據列中的傳送電路。
5.根據權利要求4所述的一種實現權利要求1所述的二進位數並行連加運算的化簡方法的連加器電路，其特徵在於所數的述數據排列電路，將列中值為「1」的數據排列到該列的低位段，該列數「1」的數量不發生改變；當列中的數的數量較少時，根據真值表設計電路，該電路能一次完成數據排列的工作，當列中的數的數量較多時，可將列中的數按從低位到高位的順序，分割成幾組，對各組的數，分別同時進行數據排列，將各組中的各自所有的「1」，分別排列到各組的低位段，然後依然是從低位到高位，每兩個相鄰的數據小組構成一個大組，對各大組的數，分別同時進行數據排列，將各大組中所有的「1」分別排列在各大組的低位段，然後依然是從低位到高位，每兩個相鄰的大組構成一個更大的數據組，對它們再次進行排列，--------，一直到列中所有的「1」被排列在該列的低位段。
6.根據權利要求4所述的一種實現權利要求1所述的二進位數並行連加運算的化簡方法的連加器電路，其特徵在於所述判斷電路對於已完成數據排列的各個列中所有兩兩相鄰的數據進行異或運算，且最低位還要和「1」進行異或，最高位還要和「0」進行異或，根據輸出為「1」的異或門的位置即得到列中「1」的數量及列中所有數相加後所得到的本位以及對高位的進位。
7.根據權利要求4所述的一種實現權利要求1所述的二進位數並行連加運算的化簡方法的連加器電路，其特徵在於所述傳送電路作用是將本次化簡所得到的本位及對高位的進位分別放在下一次化簡運算所使用的數據列中與其位權相符的數據列裡，每一個新的數據列中的各個數據在新的連加運算式中屬於相同位權的數據。
全文摘要
本發明涉及一種計算機二進位運算方法，特別是涉及一種二進位數連加運算的化簡方法。本發明還涉及一種二進位連加運算化簡方法的連加器運算電路。本發明將多個多位二進位數的連加運算通過邏輯運算逐級減量，最終變換成二個多位二進位數的相加運算，而後，採用傳統算法將二個多位二進位數加合，得出結果。本方法可用於所有可一次性轉換為二進位連加運算的運算式的運算；本方法可實現通用的二進位數連加加法器。
文檔編號G06F7/40GK1567175SQ03145028
公開日2005年1月19日 申請日期2003年6月19日 優先權日2003年6月19日
發明者周育人 申請人:周育人