專利名稱：：以Booth算法為基礎(chǔ)的乘法運算方法與乘法裝置的制作方法
技術(shù)領(lǐng)域：
：本發(fā)明涉及一種乘法的裝置與其運算方法，特別是以Booth算法為基礎(chǔ)的乘法的裝置與運算方法。
背景技術(shù)：
：離散余弦轉(zhuǎn)換(DiscretecosineTransform；DCT)與反離散余弦轉(zhuǎn)換(InverseDiscretecosineTransform；IDCT)分別被用于處理數(shù)據(jù)的壓縮與解壓縮上，其中一種有名的離散余弦轉(zhuǎn)換(DCT)與反離散余弦轉(zhuǎn)換(IDCT)技術(shù)是以Lee的算法(Lee’salgorithm)為基礎(chǔ)的快速傅利葉轉(zhuǎn)換(FastFourierTransform；FFT)。圖1A以Lee的算法應(yīng)用于交錯互換(shuttleexchange)電路實作的簡單示意圖，其中離散余弦轉(zhuǎn)換共分成第一階段運算、第二階段運算、第三階段運算與第四階段運算等四階段運算，將8個平行輸入的數(shù)據(jù)數(shù)值X0，X1，...，X7經(jīng)離散余弦變換后產(chǎn)生平行輸出的數(shù)據(jù)數(shù)值Y0，Y1，...，Y7。在圖lA中共分為兩個區(qū)塊離散余弦轉(zhuǎn)換交換處理器1與后處理器2。離算余弦轉(zhuǎn)換交換處理器1由12個相似的處理單元3所構(gòu)成，此處理單元以蝴蝶電路(butterflycircuits)的架構(gòu)來設(shè)計，其后再連接以五個加法單元4與一個定點系數(shù)乘法單元5(fixed-coefficientmultiplicationunit)所構(gòu)成的后處理器2。每一個處理單元3包含一個加法器31、一個減法器32與一個定點系數(shù)乘法器5，在各處理單元3的定點系數(shù)乘法器中，有4個以符號A表示，2個以符號B表示，2個以符號C表示，另外以符號D、E、F與G來表示的各有一個。這些以符號A、B、C、D、E、F與G來表示的定點系數(shù)乘法器其輸入的系數(shù)值分別為12cos(π/4),12cos(π/8),12cos(3π/8),]]>12cos(π/16),12cos(3π/16),12cos(7π/16)]]>與12cos(5π/16)]]>。如果在設(shè)計上不考慮個別的加法單元、減法單元與乘法單元，圖1A不需采用任何控制裝置，這種的不用控制裝置的離散余弦轉(zhuǎn)換數(shù)據(jù)流相依(DCTdata-flowdependence)設(shè)計可直接設(shè)計成為一個數(shù)據(jù)流架構(gòu)(data-flowarchitecture)。相對于圖1A，圖1B為以Lee的算法實作于反離散余弦轉(zhuǎn)換電路的簡單示意圖，其中反離散余弦轉(zhuǎn)換共分成第一階段運算、第二階段運算、第三階段運算與第四階段運算等四階段運算，將8個平行輸入的數(shù)據(jù)數(shù)值z0，z1，...，z7經(jīng)離散余弦變換后產(chǎn)生平行輸出的數(shù)據(jù)數(shù)值x0，x1，...，x7。在圖1B中共分為兩個區(qū)塊反離散余弦轉(zhuǎn)換交換處理器7與前處理器6。反離算余弦轉(zhuǎn)換交換處理器7由12個相似的處理單元8所構(gòu)成，這些處理單元以蝴蝶電路架構(gòu)所設(shè)計，其連接于以五個加法單元9與一個定點系數(shù)乘法單元10(fixed-coefficientmultiplicationunit)所構(gòu)成的前處理器6之后。每一個處理單元8包含一個加法器81、一個減法器82與一個定點系數(shù)乘法器，在各處理單元8的定點系數(shù)乘法器中，有4個以符號A表示，2個以符號B表示，2個以符號C表示，另外以符號D、E與G來表示的各有一個。這些以符號A、B、C、D、E、F與G來表示的定點系數(shù)乘法器其輸入的系數(shù)值皆與圖1A相同。另一種有名的離散余弦轉(zhuǎn)換/反離散余弦轉(zhuǎn)換上的算法為Chen算法，在離散余弦轉(zhuǎn)換/反離散余弦轉(zhuǎn)換上有關(guān)于Lee算法與Chen算法的相關(guān)細節(jié)可參照美國專利US5,452,466、US5,841,682與US6,317,676。在一般運算中，乘法相較于加法，無論在空間與時間上需要數(shù)倍以上的成本，特別是實現(xiàn)乘法所需要的硬件電路成本比實現(xiàn)加法所需要的硬件電路成本高很多。根據(jù)上述，可知在離散余弦轉(zhuǎn)換與反離散余弦轉(zhuǎn)換需花費大部份的成本在乘法運算上，因此許多乘法器的改良被普遍地應(yīng)用在離散余弦轉(zhuǎn)換與反離散余弦轉(zhuǎn)換上。其中一種有名的乘法器是以Booth算法為基礎(chǔ)，其細節(jié)可參考美國專利US5,485,413d。如圖2A所示，在Booth算法中，首先如步驟220所示，將乘數(shù)依Booth算法轉(zhuǎn)換成一組包含多個乘數(shù)系數(shù)的乘數(shù)系數(shù)組。接下來，如步驟240所示，再依據(jù)所挑選出的乘數(shù)系數(shù)組與一被乘數(shù)以Booth算法來產(chǎn)生復(fù)數(shù)個部份乘積。最后如步驟260所示，加總各部份乘積以產(chǎn)生被乘數(shù)與乘數(shù)相乘的乘積。因此上述的乘法方法可被設(shè)計一乘法器，如圖2B所示，由一系數(shù)產(chǎn)生裝置22將乘數(shù)211轉(zhuǎn)換成一組乘數(shù)系數(shù)組221，此乘數(shù)系數(shù)組221包含多個乘數(shù)系數(shù)222。接下來，再由部份乘積產(chǎn)生裝置24依據(jù)這些乘數(shù)系數(shù)222與被乘數(shù)212來產(chǎn)生數(shù)個部份乘積242，最后再由加總裝置26將各部份乘積242加總以得出被乘數(shù)212與乘數(shù)211相乘的乘積262。此乘數(shù)系數(shù)的數(shù)目比乘數(shù)的位元總數(shù)還少，因此依據(jù)乘數(shù)系數(shù)所產(chǎn)生的部份乘積的數(shù)量比依據(jù)乘數(shù)的各位元所產(chǎn)生的部份乘積少上許多，使得在空間上與效能上的成本都能大量節(jié)省。上述的離散余弦轉(zhuǎn)換與反離散余弦轉(zhuǎn)的乘法運算約有7種，但都具有多數(shù)個構(gòu)成單元，也相對應(yīng)到多數(shù)個計算步驟與總類。因此如果能將用于離散余弦轉(zhuǎn)換與反離散余弦轉(zhuǎn)的乘法運算進一步簡化，將可以節(jié)省許多成本。
發(fā)明內(nèi)容本發(fā)明的目的在于克服現(xiàn)有技術(shù)的不足與缺陷，提出一種以Booth算法為基礎(chǔ)的乘法運算方法與裝置，用以減少乘數(shù)系數(shù)以簡化乘法運算。為達上述目的，本發(fā)明提出一種乘法運算方法，依據(jù)一乘數(shù)索引(multiplicationindex)來挑選一組乘數(shù)系數(shù)組(multiplicationcoefficientsets)，此乘數(shù)系數(shù)組由已知的復(fù)數(shù)組乘數(shù)系數(shù)中所挑選出來，每一組乘數(shù)系數(shù)中各包含以Booth算法由一已知乘數(shù)所轉(zhuǎn)換出的多個乘數(shù)系數(shù)，再依據(jù)所挑選出的乘數(shù)系數(shù)組與一被乘數(shù)以Booth算法來產(chǎn)生復(fù)數(shù)個部份乘積，最后加總各部份乘積以產(chǎn)生一輸出值。本發(fā)明也提出一種乘法裝置，包含一系數(shù)產(chǎn)生單元，依據(jù)一乘數(shù)索引于復(fù)數(shù)組系數(shù)中挑選出一組系數(shù)作為一乘數(shù)系數(shù)組，此乘數(shù)系數(shù)組包含復(fù)數(shù)個系數(shù)，此乘數(shù)系數(shù)組包含復(fù)數(shù)個依據(jù)乘數(shù)索引值所相應(yīng)的一已知乘數(shù)值以Booth算法所產(chǎn)生的系數(shù)；一部份乘積產(chǎn)生單元，依據(jù)乘數(shù)系數(shù)組與一被乘數(shù)以Booth算法計算出復(fù)數(shù)個部份乘積；以及一加總單元，用以加總各部份乘積以產(chǎn)生一輸出值。圖1A與圖1B為現(xiàn)有技術(shù)的裝置示意圖；圖2A、圖2B分別為現(xiàn)有技術(shù)中Booth算法的流程示意圖與功能方塊示意圖。圖3為本發(fā)明的一具體實施例的流程示意圖；圖4為本發(fā)明的另一具體實施例的功能方塊示意圖。圖中符號說明211乘數(shù)212被乘數(shù)22系數(shù)產(chǎn)生單元221乘數(shù)系數(shù)組222乘數(shù)系數(shù)24部份乘積產(chǎn)生單元242部份乘積2421高位元組2422低位元組26加總單元262乘積41乘數(shù)索引42系數(shù)產(chǎn)生單元46加總單元461高位元乘積462低位元乘積4621進位值463輸出值具體實施例方式本發(fā)明一些實施例詳細描述如下。然而，除了詳細描述外，本發(fā)明還可以廣泛地在其它的實施例施行，且本發(fā)明的范圍不受限定，其以權(quán)利要求書的范圍為準(zhǔn)。再者，為提供更清楚的描述及更易理解本發(fā)明，附圖內(nèi)各部分并沒有依照其相對尺寸繪圖，某些尺寸與其它相關(guān)尺度相比已經(jīng)被夸張；不相關(guān)的細節(jié)部分也未完全繪出，以求圖標(biāo)的簡潔。在Booth算法的乘法運算中，其主要的特征是將乘數(shù)(multiplicator)轉(zhuǎn)換為復(fù)數(shù)個系數(shù)作為乘數(shù)系數(shù)，再依據(jù)這些乘數(shù)系數(shù)產(chǎn)生復(fù)數(shù)個部份乘積(partofproduct)，最后加總(summing)所有部份乘積以得出完成運算的乘積。因此，本發(fā)明以Booth算法的運算特征來做乘法的改良，其是基于在某些特定應(yīng)用環(huán)境中，乘數(shù)的各種可能的數(shù)值都為已知時(即只有固定的一些可能乘數(shù)值)，可以先將乘數(shù)的每一種可能的數(shù)值指定至一相應(yīng)的乘數(shù)索引值，并且事先依乘數(shù)的每一種可能的數(shù)值來計算出一組相應(yīng)的乘數(shù)系數(shù)。因此，依此乘數(shù)索引值便能直接得出相應(yīng)的一組乘數(shù)系數(shù)，而不需如現(xiàn)有技術(shù)需在得知乘數(shù)后再進行系數(shù)轉(zhuǎn)換，故可節(jié)省系數(shù)轉(zhuǎn)換的成本，同時也增進了運算的效能。此外，因為乘數(shù)的各種可能的數(shù)值都為已知，故乘數(shù)索引可以較少的位元來表示，例如，原本乘數(shù)以二進制(binary)表示時，共有16個位元，其可能的數(shù)值共有216種，然而實施上所會使用的已知數(shù)值僅有8種，便可以用3個位元來表示所有可能的乘數(shù)。另外，在乘積的輸出上，有時并不一定需要將完整乘積輸出，而僅需要將部份的位元輸出即可。例如，乘數(shù)或被乘數(shù)具有小數(shù)時，輸出值可以是以乘積取至小數(shù)點后幾位元，其余小數(shù)部份皆舍去。另外，也可能乘積僅需要將小數(shù)點前幾位元輸出即可，例如乘積所能表示的值可達到40位元，然而所有可能的乘積最多僅需23個位元就能表示，因此輸出23個位元即可。此外，如上述，若乘積的輸出僅為其中的部份位元組，可以將部份乘積中相對于輸出的位元組及其它更高位的位元作為一高位元組，其余較低的位元作為一低位元組，分別將所有部份乘積中高位元組與低位元組各自加總，用以分別得出高位元乘積與低位元乘積，其中低位元乘積中包含一進位值，此進位值由低位元乘積中相對原低位元組以外的其它位元所組成，用以進位來與高位元乘積加總，據(jù)此，便可以用高位元乘積與進位值的總合中的部份位元組作為乘積的輸出值。因此在低位元組的加總過程中，除了進位值外，低位元乘積中的其它位元皆不需要保留，可節(jié)省成本。本發(fā)明可適用于整數(shù)、浮點數(shù)(floatingpointvalue)、定點數(shù)(fixedpointvalue)或者其它數(shù)值型態(tài)(type)，并也適用于各種不同的數(shù)值表示方式，如2進制、4進制、10進制、16進制等，數(shù)值型態(tài)與數(shù)值表示方式在本發(fā)明并不受限制。此外，乘數(shù)系數(shù)組的挑選方式可以是依據(jù)系數(shù)索引從一查表(lookuptable)中來挑選，此查表中記錄著各種乘數(shù)索引與相應(yīng)的乘數(shù)系數(shù)的相應(yīng)關(guān)系，此查表的實施方式可以儲存在存儲器中、能保持狀態(tài)的電路或其它儲存媒體中，通過乘數(shù)索引作為地址索引或控制信號，以輸出相應(yīng)的一組乘數(shù)系數(shù)，更可以直接以邏輯電路(logicalcircuit)所達成。在此對查表的舉例說明是為了讓乘數(shù)系數(shù)的挑選方式能夠更容易了解，并非用于限制本發(fā)明的實施方式，本發(fā)明對由乘數(shù)索引挑選出乘數(shù)系數(shù)組的實施方式并不加以限制。綜合上述，本發(fā)明的一具體實施例是一種Booth算法的乘法運算方法，如圖3所示。首先，步驟320依據(jù)一乘數(shù)索引挑選一組乘數(shù)系數(shù)組，此乘數(shù)系數(shù)組由已知的復(fù)數(shù)組乘數(shù)系數(shù)中所挑選出來。每一組乘數(shù)系數(shù)中各包含以Booth算法所轉(zhuǎn)換出的多個乘數(shù)系數(shù)。也就是說，所有可能的乘數(shù)值都為已知，各由一個乘數(shù)索引所相應(yīng)，并且以Booth算法轉(zhuǎn)換出相應(yīng)的一組乘數(shù)系數(shù)，也因此每一乘數(shù)索引也與一組乘數(shù)系數(shù)相應(yīng)。此外，不同的乘數(shù)值所轉(zhuǎn)換出的一組乘數(shù)系數(shù)有可能相同，也因此不同的乘數(shù)索引也有可能與相同的一組乘數(shù)系數(shù)相應(yīng)。然后，如步驟340所示，依據(jù)所挑選出的乘數(shù)系數(shù)組與一被乘數(shù)以Booth算法來產(chǎn)生復(fù)數(shù)個部份乘積，也就是依序?qū)⒈怀藬?shù)與乘數(shù)系數(shù)組的每一個乘數(shù)系數(shù)相乘，以產(chǎn)生多個部份乘積。接下來，如步驟360所示，加總各部份乘積以產(chǎn)生一輸出值。此輸出值可以是經(jīng)所有部份乘積加總所得的乘數(shù)與被乘數(shù)相乘的乘積，也可以是現(xiàn)有所述以乘積的部份位元的組合來產(chǎn)生。本實施例的其它細節(jié)已于上述的說明中詳述，在此不再贅述。本發(fā)明的另一較佳實施例是一種Booth算法的乘法裝置，如圖4所示，包含一系數(shù)產(chǎn)生單元42、一部份乘積產(chǎn)生單元24與一加總單元46。系數(shù)產(chǎn)生單元42依據(jù)一乘數(shù)索引41從已知的復(fù)數(shù)組乘數(shù)系數(shù)222中挑選出一組作為乘數(shù)系數(shù)組221，每一組乘數(shù)系數(shù)中各包含以Booth算法由一已知乘數(shù)221所轉(zhuǎn)換出的多個乘數(shù)系數(shù)222。接下來，再由部份乘積產(chǎn)生單元24依據(jù)乘數(shù)系數(shù)組221與一被乘數(shù)212以Booth算法進行計算，以計算出多個部份乘積242。最后，再經(jīng)由加總單元46將各部份乘積242加總以產(chǎn)生一輸出值463。其中輸出值463的產(chǎn)生方式可以是依先前所述，將部份乘積242分為高位元組2421與低位元組2422，再由加總單元46分別將各部份乘積242的高位元組2421與低位元組2422各自加總，來分別產(chǎn)生高位元乘積441與低位元乘積442，然后依據(jù)高位元乘積441與低位元乘積442來產(chǎn)生輸出值443。其中低位元乘積442中包含上述的進位值4421，輸出值443更可以依先前所述，由高位元乘積441與進位值4421的總和來產(chǎn)生。本實施例的其它細節(jié)已于上述的說明中詳述，在此不再贅述。據(jù)此，本發(fā)明的再一具體實施例可以是將上述的Booth算法的乘法裝置應(yīng)用于離散余弦轉(zhuǎn)換/反離散余弦轉(zhuǎn)換上，例如作為Lee算法中的定點系數(shù)乘法器，其中的乘法運算以定點系數(shù)作為乘數(shù)，這些乘數(shù)為余弦函數(shù)值、或正弦函數(shù)值，例如乘數(shù)可能為12cos(π/4),12cos(π/8)]]>12cos(3π/8),12cos(π/16),12cos(3π/16),12cos(7π/16)]]>與12cos(5π/16)]]>等等。此外，本具體實施例亦可作為Chen算法中的定點系數(shù)乘法器，并且更可將上述的離散余弦轉(zhuǎn)換/反離散余弦轉(zhuǎn)換應(yīng)用于數(shù)字影音播放軟件或設(shè)備上，如VCD播放器、DVD播放器、HDTV或其它相關(guān)軟件或設(shè)備。本實施例的其它細節(jié)已于上述的說明中詳述，在此不再贅述。以上所述僅為本發(fā)明的較佳實施例，并非用以限定本發(fā)明的保護權(quán)利；同時以上的描述，對于本
技術(shù)領(lǐng)域：
的專門人士應(yīng)可明了及實施，因此其它未脫離本發(fā)明所揭示的精神下所完成的等效改變或修飾，均應(yīng)包含在權(quán)利要求書的范圍中。權(quán)利要求1.一種Booth算法的乘法運算方法，其特征在于，包含挑選一組乘數(shù)系數(shù)組，該乘數(shù)系數(shù)組依據(jù)一乘數(shù)索引于復(fù)數(shù)組系數(shù)中挑選出來，該乘數(shù)系數(shù)組包含復(fù)數(shù)個系數(shù)，依據(jù)該乘數(shù)索引所相應(yīng)的一已知乘數(shù)值以Booth算法所產(chǎn)生；產(chǎn)生復(fù)數(shù)個部份乘積，該些部份乘積依據(jù)該乘數(shù)系數(shù)組與一被乘數(shù)以Booth算法計算所產(chǎn)生；以及加總該復(fù)數(shù)個部份乘積以產(chǎn)生一輸出值。2.如權(quán)利要求1所述的Booth算法的乘法運算方法，其中，上述的該乘數(shù)系數(shù)的挑選是以該乘數(shù)索引參照一查表后得出，該查表記錄多數(shù)個可能的乘數(shù)索引與多數(shù)個可能的乘數(shù)系數(shù)組的對應(yīng)關(guān)系。3.如權(quán)利要求1所述的Booth算法的乘法運算方法，其中，上述復(fù)數(shù)個部份乘積加總總值是該乘數(shù)索引值所相應(yīng)的該已知乘數(shù)值與該被乘數(shù)的一乘積。4.如權(quán)利要求1所述的Booth算法的乘法運算方法，其中，上述的部份乘積是二進制值，包含一高位元組與一低位元組，其中該輸出值是以所有該部份乘積的該高位元組被加總產(chǎn)生一高位元乘積，并且與所有該部份乘積的該低位元組加總得出總和中超出該低位元組的一進位值加總后所產(chǎn)生，其中該輸出值是該高位元乘積與該進位值的總和中的部份位元的組合。5.一種Booth算法的乘法裝置，其特征在于，包含一系數(shù)產(chǎn)生單元，依據(jù)一乘數(shù)索引于復(fù)數(shù)組系數(shù)中挑選出一組系數(shù)作為一乘數(shù)系數(shù)組，該乘數(shù)系數(shù)組包含復(fù)數(shù)個依據(jù)該乘數(shù)索引所相應(yīng)的一已知乘數(shù)值以Booth算法所產(chǎn)生的系數(shù)；一部份乘積產(chǎn)生單元，依據(jù)該些乘數(shù)系數(shù)組與一被乘數(shù)以Booth算法計算出復(fù)數(shù)個部份乘積；以及一加總單元，用以加總該復(fù)數(shù)個部份乘積以產(chǎn)生一輸出值。6.如權(quán)利要求5所述的Booth算法的乘法裝置，更包含一查表，其中該乘數(shù)系數(shù)的挑選是以該乘數(shù)索引參照該查表后得出，該查表記錄多數(shù)個可能的乘數(shù)索引與多數(shù)個可能的乘數(shù)系數(shù)組的對應(yīng)關(guān)系。7.如權(quán)利要求5所述的Booth算法的乘法裝置，其中，上述復(fù)數(shù)個部份乘積加總的總值是該乘數(shù)索引值所相應(yīng)的該已知乘數(shù)值與該被乘數(shù)的一乘積。8.如權(quán)利要求5所述的Booth算法的乘法裝置，其中，上述的部份乘積是二進制值，包含一高位元組與一低位元組，該加總裝置是將所有該部份乘積的該高位元組加總產(chǎn)生一高位元乘積，并且將所有該部份乘積的該低位元組加總得出總和中進位出該低位元組的一進位值后，以該高位元乘積與該進位值加總后產(chǎn)生該輸出值，其中該輸出值是該高位元乘積與該進位值的總和中的部份位元的組合。9.如權(quán)利要求5所述的Booth算法的乘法裝置，其是應(yīng)用于離散余弦轉(zhuǎn)換/反離散余弦轉(zhuǎn)換，且該乘數(shù)索引為一余弦函數(shù)值。10.如權(quán)利要求9所述的Booth算法的乘法裝置，其中，上述的余弦函數(shù)值選自下列之一12cos(π/4),12cos(π/8),12cos(3π/8),]]>12cos(π/16),12cos(3π/16),12cos(7π/16)]]>與12cos(5π/16).]]>全文摘要本發(fā)明涉及一種以Booth算法為基礎(chǔ)的乘法裝置與運算方法，依據(jù)一乘數(shù)索引挑選一組乘數(shù)系數(shù)組，此乘數(shù)系數(shù)組是由已知的復(fù)數(shù)組乘數(shù)系數(shù)中所挑選出來，每一組乘數(shù)系數(shù)中各包含以Booth算法由一已知乘數(shù)所轉(zhuǎn)換出的多個乘數(shù)系數(shù)，再依據(jù)所挑選出的乘數(shù)系數(shù)組與一被乘數(shù)以Booth算法來產(chǎn)生復(fù)數(shù)個部分乘積，最后加總各部分乘積以產(chǎn)生一輸出值。文檔編號G06K9/36GK1591319SQ20041003430公開日2005年3月9日申請日期2004年4月9日優(yōu)先權(quán)日2003年12月3日發(fā)明者葉丁坤,蔡政銘,王瑞麟申請人:威盛電子股份有限公司