[發(fā)明專利]高基除法器及方法

無效

• 申請?zhí)枺?/td>: 00121760.7
• 申請日: 2000-06-04
• 公開（公告）號: CN1287307A
• 公開（公告）日: 2001-03-14
• 發(fā)明（設(shè)計）人: 平入孝二
• 申請（專利權(quán)）人: 索尼株式會社
• 主分類號: G06F7/52
• 分類號: G06F7/52;G06F17/10
• 代理公司: 上海專利商標(biāo)事務(wù)所
• 代理人: 錢慰民

本發(fā)明涉及一個對于使用由二進(jìn)制數(shù)給出的被除數(shù)和除數(shù)的除法采用恢復(fù)除法的除法器，特別涉及用于被除數(shù)的基2^k除法以便一次得出k個位的商的高基除法器及其方法。

已知的恢復(fù)除法是一個減法器系統(tǒng)(例如，參見由Mitsuaki?Narita翻譯的JohnL.Hennessy,David?A.Paterson的文章，計算機結(jié)構(gòu)和設(shè)計,lstvolume,pp.191-199,Nikkei?BPCo.April1996)。

基2恢復(fù)除法每次從上一位獲得一個一位的商。

在這種情況下，當(dāng)被除數(shù)是N位時，最少需要N次計算。例如，當(dāng)被除數(shù)是32位時，必須最少執(zhí)行32次計算。

當(dāng)以這種方式一次得到一位的商時，計算次數(shù)變得太大，因此存在一種通過將一次計算得出的商的位數(shù)增大到2位或更多來減少計算次數(shù)的方法。這被稱為高基除法。

當(dāng)一次獲得k位時，將該操作稱為基2^k除法。例如，當(dāng)執(zhí)行32位被除數(shù)的基4除法時，在每次計算得出2位的商，計算的最小次數(shù)降為16。同樣，如果基為8，則計算次數(shù)變?yōu)?1。

下面將詳細(xì)說明基2和基4恢復(fù)除法。

基2恢復(fù)除法

在這里，將被除數(shù)表示為A，將除數(shù)表示為B。A和B是N位帶符號的二進(jìn)制數(shù)(2的補碼)。

注意，在下面的說明中出現(xiàn)的MSB表示二進(jìn)制數(shù)中的最高有效位，在M位二進(jìn)制數(shù)的情況下表示第(M-1)位。

寄存器包括用于存儲商的符號的符號寄存器(一個數(shù)位)、用于存儲除數(shù)B的B寄存器(N個數(shù)位)、用于存儲余數(shù)的R寄存器(N個數(shù)位)以及用于存儲商的Q寄存器(N個數(shù)位)。

所有寄存器都被初始化為0。

下面要說明的除法例程被分成三級：第一、第二和第三級STG1至STG3。

第一級STG1是一個預(yù)備級，第三級STG3是一個用于校正所得商的符號的末級，第二階段STG2是除法的中心級。

每級STG1、STG2、STG3在進(jìn)入寄存器的入口處結(jié)束。一級中的操作序列在一個周期中執(zhí)行。

[例程]

第一級STG1

(1)參看被除數(shù)A和除數(shù)B的符號位(MSB)，將商的符號提前得出，并存儲在符號寄存器中。在這里，在為負(fù)時Sign=1。

(2)得出被除數(shù)A的絕對值，并輸入Q寄存器。

(3)得出除數(shù)B的絕對值，并輸入B寄存器。

第二級STG2-1

(1)計算R-B=diff(N個數(shù)位)。

(2)當(dāng)diff不為負(fù)(diff的MSB為“0”)時，可以從余數(shù)中減去除數(shù)。

此時，商判斷數(shù)據(jù)Judge=1，新余數(shù)是diff=R-B=Re(N個數(shù)位)。

另一方面，當(dāng)diff為負(fù)時，不能從余數(shù)中減去除數(shù)。

此時，商判斷數(shù)據(jù)Judge=0，新余數(shù)是R=Re(N個數(shù)位)。

(3)通過合并Re、Q和Judge，并向左移一位，得出R寄存器的值NEXT_R和下一個Q寄存器的值NEXT_Q。

即，

NEXT_R={Re的第(N-2)到第0個數(shù)位，Q的第(N-1)個數(shù)位}

NEXT_Q={Q的第(N-2)到第0個數(shù)位，Judge}

(4)分別將NEXT_R和NEXT_Q輸入R、Q寄存器。

第二級STG2-2

上述操作(1)到(4)在一個周期內(nèi)完成。

將上述操作重復(fù)N次。

第三級STG3

(1)計算R-B=diff(N個數(shù)位)。

(2)當(dāng)diff不為負(fù)(diff的MSB為“0”)時，可以從余數(shù)中減去除數(shù)。

此時，商判斷數(shù)據(jù)Judge=1，新余數(shù)是diff=R-B=Re(N個數(shù)位)。

另一方面，當(dāng)diff為負(fù)時，不能從余數(shù)中減去除數(shù)。

此時，商判斷數(shù)據(jù)是Judge=0，新余數(shù)是R=Re(N個數(shù)位)。

(3)通過合并Re和Q并向左移一位，得出R寄存器的值NEXT_R和下一個Q寄存器的值NEXT_Q。

即，

NEXT_R={Re的第(N-2)到第0個數(shù)位，Q的第(N-1)個數(shù)位}

NEXT_Q={Q的第(N-2)到第0個數(shù)位，Judge}

一直到這里的說明都與第二級STG2相同。

(4)通過參看符號寄存器校正商的符號，并得出最后的商。

即，

Sign=1(當(dāng)為負(fù)時)：LAST_Q=～NEXT_Q+1(采用2的補碼)。

注意，“～”表示反相。