TW501344B - Complex-valued multiplier-and-accumulator - Google Patents

Description

501344 &、發明說明Ο) 產業上之利用領域 本發明之可雙⑻倍綱度之複(實)絲加器，可適用於 各式數位訊號處理n讀加運算。如有限脈波㈣舰$、無限脈 波響應渡波H、B紐器、相義數、迴_分運算、時域 與頻域間的數值轉換等等，或是在數位通訊系統中，數位等化器、 複數濾波器等等。 發明背景 乘加器在數位訊號處理器中為核心的處理單元，由於可程式數 位訊號處聽醜用，如影像、音訊、語音、軌中，常使用有限 脈波響應攄波H、無限脈波響應濾波器，匹配驗器、相關係數運 算、迴旋積分運算、時域頻域間峨值轉換等等。因此能夠高速運 算兩個高維度向量___加運抑，就成域佩號處理器 不可或缺的部份。 力速乘加器的方法有三類，第一類為乘加器演算法的最佳化； ^£^5人之_運算延遲_並以適當管線化加速，

第5頁

II L、發明說明（2) 例如各式的布司（B〇〇th)乘法器。第二類為數位訊號處理器的辅助 功能；在程式程序控制單元中，相乘累加運算常會以一種計數 器輔助，⑽避免每次需要_乘加資料結束條件所造成的額外非 累加運算’因此數位訊號處理器可全速執行乘加運算。此外由於相 乘累加的兩組向量長度常會不同，如有限脈波響應據波器、對應滤 波器等’因此固定長度的係數輸人向量就會以循環的方式讀入，因 數位訊號處理Hit巾會提供環狀循環定址的対來加速對此循環 資料的讀取。以上_方式為加速乘加·的傳财法，降低在硬 體上或軟體上觸外運算使縣純發揮最大的效能。 器架構㈣二類，此_構基本誠平行運算的多讎加器來做加 速運算以單筆才曰令多筆資料處理⑶响恤贈i〇n仙出咖

Data)的方式來做其處理器架構。但是單是增加運算硬體也會造成 成本的增加’而且在不同精確度運算時，所需的運算時間相同無 法對硬體有最佳的使収率。因此第三_平練加運算器就触 出所謂副字組(SUb，d)平行數位訊號處理器。由於各種應用所需

紅合來說，以副字組平行(Subw〇rd parallel)運算的乘加器架 構能夠有效地提昇數位訊號處理中的乘加運算效率，但是由於在不 同精確度下，仍需要額外去處理資料對齊的問題。

發明目標 本發明之首要目的係揭示—種全新改㈣乘加雜構，使得乘 加運算的更具有雜，_是翻概贿聽財之複數乘 501344 五、發明說明（4) 本發明的另一目的係揭示複數乘加器之不同精確度運算，也就 是副字組平行(Subword Parallel)運算。因此在單倍精確度數值做 運算時，可藉由平行的方式使用雙倍精確度的硬體來達成加速乘加 的目的 本發明的另一目標，係揭示複數乘加器可以解決在一般在副字 組平行(Subword Parallel)運算器中資料對齊的問題，以減少額外 的硬體及軟體運算。 凡是熟悉該技藝的人士在閱讀下列經由不同圖解所展示之較佳 實施例詳細說明後，無疑地將非常清楚本發明所揭示之目的和優 點。本發明將在下文中配合圖示做詳細說明。 發明之詳細說明 本發明提出-種新的架構，可以適用於不同資料格式；包含複 (實)數與雙(單)倍精確度的乘加運算，且可避免在單倍精確度運算 時所需的資料對齊處理。本發明之織，可以制多種不同方式之 發明說明（6) --—----- 此四個副字組乘積(pp〇)(ppl)(pp2)(pp3)可以用左移相加的方 式，將乘積pp〇與左移N/2位元的乘積ppl及pp2與左移N位元的 卯3相加’可得到雙倍精確度乘法之積。又將此四個副字組乘積兩 力並加上組複數累加器，就可以形成一組單倍精確度之複數 乘加器’如圖四。如此就可每一種週期可以平行運算四個單倍精確 複數乘加運算。 此新型複數乘加器的架構與現有專利與產品不同的是在於 、月b普遍使用在通訊系統中複數值的乘加運算，也可以運在 般數位訊號處理中的實數運算。現有的專利不是做專做 複數運算就是做實數運算。 ―、可以用於尚精確度的乘加運算，也可以用於低精確度的乘 加運算，並且在低倍精確度乘加運算時，可以百分之百地 有效率使用硬體。而現有的複數乘法器或實數乘法器在做 副字組平行運算時，通常無法全部硬體充份使用。 二、低倍精確度乘加運算時，不必做一般副字組平行

501344

五、發明說明（7) 行運算時’每次乘加運算會產生三各時段的累加乘積；亦 即目前時間、前一時間及灸一時間，因此用在平行運算時 可免除資料對不齊時的運算。 經由適當的多工運算，此-運算器可用於雙(單)倍精確度之 複(實)數乘加運算，使乘加器的使用更具彈性。 如果連續四對實數輸入至此四個單倍精讀度複數乘加器的實數 和虛數如伽所示，經賴單的多頌資料搬移，断以在一二週 期内平行執行十六個單倍精確度之實數乘加運算。 雖然每組乘加器的輸人是彼此相_，但透過運算結果推論可 知，每次的運算除了包含目前輸出之累加乘積外，也包含之前及之 後時_所_加乘積，_每次乘加循猶只要將之後時 間輸出累加和’移至之前時間輸出累加和之累加暫存器中即可。 輕算即可，對位不齊的運 501344

算可以不必計算，因為在對齊資料的運算中就可以計算出其累加 積，所以在一般副字組平行(Subword Parallel)運算器所需額外的 資料對齊處理，在此一複數乘加器中可以省去。 N X N雙倍精確度複數乘加器 在本發明中以一種N X N雙倍精確度之複數乘法器為主體架構 如圖一所示，AR實數暫存器一（1)、BR實數暫存器二(3)、M虛數·_ 暫存器一（2)、BI虛數暫存器二(4)，以及ACCR實數累加暫存器 (201)，ACCI虛數累加暫存器（203)，ACC-AUX輔助累加暫存器（2〇2)。 其中有四個N X N雙倍精確度之實數乘法器來計算ar實數 乘BR實數(3)積、AI虛數(2)乘BI虛數(4)積、AR實數(1)乘BI虛 數(3)積及AI虛數(2)乘BR實數(4)積。其中實數乘實數積與虛數 乘虛數積累加在ACCR實數累加暫存器（201)，實數乘虛數積與虛數 乘實數積累加在ACCI虛數累加暫存器（203)内，此時多工器MUX1 選取乘積P2(l〇3)，則可以形成最基本之複數累加器。

第12頁 ^U1J44 五、發明說明（9) ' -----— N X N雙倍精確度實數乘加器 雙倍精確度實數的絲運算，亦可經_—之N X N雙倍精確 Y(n)^C(k)-X(n^k) k=z〇 度複數乘加器來運算。_二中—種κ _有限脈波響應據波器為 例子。 其中c(k)為璩波器係數，x(k)為輸入訊號，γ(η)為輸出訊號。 每-人複數乘加器的運算可以輸入兩對連續的實數取樣c(k) c(k+i) 及X(n-k) X(n-k-l)，而每次乘加的循環只要做偶數索引值對偶數 索引值對齊資料的運算即可。在圖二中顯示κ=6時，前三次運算可 得輸出Υ(η-2)的累加積，後三次運算可以得輸出γ(η)的累加積， 所以每Κ/2 :欠運算可以算出輸出γ，又每次的運算也會得到前一種 輸出Y(n-l)所需之—半累加積，以及後〜種輸出γ(η+ι)所需之一 半累加積。所以在做雙倍精確度實數運算時，圖一(a)中的_多 工器設為選取〇，並且在每次乘加循環之前，將後_時間的輸出累 加值，圖-(a)中之ACCI(203)，移至前一時間的輪出累加暫存器， 圖-中之AO>AUX(2G2)。所以在時間n可以算出輸出γ(η)(3〇1)及 Y(n-1)(302)的m。因此可以省略偶數索引值對奇數索引值之不對

法器再、屋由四個_子組乘積做左移相加的運算即可麟Ν χ n雙 倍精雜實數乘法之積。此設計的目的是為了能夠在單倍精確度複 數運算時_四解倍精顧·之積，來《加之積。 做單倍精確度複數運算時，將原本圖三高位元值顾丨了⑽與 腦(1703)分別重新定義為單倍精確度之實數腿與職，原本低位 兀值AXIX1702)與BXL(1704)分別重新定義為單倍精確度之虛數 與BXI。如此可重新架構如圖四，實數乘實數積(AXRxBXR)*虛數乘 虛數積(AXIxBXI)累加可得單倍精確度複數累加之實數值，實數乘 虛數積(AXRxBXI)與虛數乘實數積(AXIxMR)累加可得單倍精確度 複數累加之虛數值。因此原本圖一(a)中的四個N X N雙倍精確产 複數乘法器C0(501)〜C3(504)可重新構成如圖四之四個平行運算之 N/2 X N/2早倍精嫁度複數乘加器’每^一種乘加器内均有一組複數 累加器 acc0(901)〜acc3(904)。 以K階有限脈衝響應濾波器為例，其運算程序與N X N雙倍精 確度實數模式時的有限脈衝響應濾波器相同（圖二），除了雙倍精確

度的C(n)是單倍精確度實數CR(n)及虛數α(η)的組合；雙倍精確 度的X(n)是單倍精讀度實數狃⑹及虛數幻⑹的組合。同樣地， 每K/2次運算可以算出輸出γ，又每次的運算也會得到前一種輸出 Y(n 1) (1〇〇2)所需之一半累加積，以及後一種輸出γ(η+ι)所需之 一半累加積。在每次乘加循環之前，將後一種輸出累加值acc3(9〇4) 移至刖一個輸出累加暫存器acc2(9〇3)，如箭頭（12(^)0202)所示。 如此，每次乘加循環之後acc0(901)與accl⑽2)相加可得目前. 輸出 Y(n)(1001)，acc2(9〇3)為前一時間輸出 γ(η-ΐ)(ι〇〇2)。同樣 地，可以省略偶數索引值對奇數索引值不對齊資料的運算，因此每 次平均可執行四個Ν X Ν單倍精確度之複數乘加運算。 Ν/2 X Ν/2單倍精確度實數乘加器 若要用此一架構執行Ν/2 X Ν/2單倍精確度實數之κ階有限脈 || 波響應濾波器時，其運算程序可以用圖五來說明（Κ=4)。其中每次 輸入以連續四個單倍精確度之濾波器係數C(n)及連續四個單倍精確 度之輸入取樣X(n)，每次運算會同時產生十六個Ν/2 X N/2單倍精 確度乘法器之積，觀察目前t=n (2202)與前四時間t=n-4 (2201)的

叫344 五 、發明說明（13) 所有乘積可以發現，每一次運算的十六個乘積中，有四個乘積可以 累加目前輸出以矩形框標明之Y(n)(2301)，有三個乘積可以累加前 一時間輪出用菱形框標明之Υ(η-1)(2302)，有兩個乘積可以累加前 兩個時間輸出用橢圓標明之Υ(η-2)(2303)，有一個乘積可以累加前 二個時間輪出用梯形標明之Y(n-3)(2304);另一方面從前四個時間 ΐ=η-4 (2201)的運算來看，也有三個乘積可以用以累加後一種時間 之輪出Υ(η-3) (2304)，有兩個乘積可以累加後兩個時間之輸出 Υ(η-2)(2303)，有一個乘積可以甩以累加後三個時間的輸出γ(η-1)(2302)。依此規則，用多工的方式可將複數乘加器重新架構成Ν/2 X Ν/2單倍精確度的實數乘加器如圖六。在每次乘加循環前，將累 加後一時間輸出的暫存器accl2(i413)内容移到累加前三個時間輸 出的暫存器accl 1(1412)，如箭頭(1603);將累加後二時間acc6(i407) 輸出的暫存器内容移到累加前二時間輸出的暫存器acc4(14〇5)，如 箭頭(1601);將累加後三個時間輪出的暫存器咖7⑽8)内容移到 累加前一時間輸出的暫存器acc5(14〇6)，如箭頭（16〇2)。如此一來， 在每次乘加循環後可以同時產生四個輸出：γ(η)(麗）由acc〇(遍） 和acc2(1403)相加而得；Υ(η—υ⑽2)由accl〇4〇2)和批5〇4⑹

II

I

第17頁 501344 五、發明說明（14) 一 1^*--—__ 相加而得：Υ(η-2)(1503)為 acc4⑽5) ; γ(η—3)(15〇4)為 acclK·)。由於每四個時間點才需要執行一次乘加循環，因此 可以免除非四倍數對齊_的運算，並且在可在—次乘加運算中同 時執行十六次的單倍精確度之實數乘加運算。 本發明之副字組複數乘加器可運作在四個不同的模式，對一種 典型乘加運算的K階有限脈衝響應濾波器來說，其執行效能（見圖 七)在N/2 x N/2單倍精確度實數乘加運算時，可從典型複數乘加 器所需的K個乘加週期減至κ/16個乘加週期。 本發明提出一種新的架構，可以用以不同資料格式（包含複(實） 數與雙(早)倍精確度）的乘加運算，且可避免在單倍精碟度運算時 所需的資料對齊處理。當本構想提出並落實時，對本領域猶有涉獵ο 者可以用多種方式實現。因此以下專利細也將涵蓋與本發明觀念 相同的不同實現方式。

501344 圖式簡單說明 圖式說明： 圖一(a) N X N雙倍精確度複(實)數乘加器架構圖 圖一(b) N X N雙倍精確度乘法器做副字組拆解成四個單倍精 確度乘法器 圖二N X N雙倍精確度實數乘加器於K階有限脈波響應濾波 運算程序圖 圖三N X N雙倍精確度乘法器之單倍精確度分割 圖四N/2 X N/2單倍精確度複數乘加器架構圖 圖五N/2 X N/2單倍精確度實數乘加器於K階有限脈波響應 濾波運算程序圖 圖六N/2 X N/2單倍精確度實數乘加器架構圖 圖七複數乘加器中不同模式效能摘要 圖號說明 1……AR實數暫存器一 2......AI虛數暫存器一 3……實數暫存器二

第19頁 501344 圖式簡單說明 4.......虛數暫存器二 101.. . P0 乘積一 102.. ..P1 乘積二 103.. . P2乘積三 104…P3乘積四 201.. ..ACCR實數累加暫存器 202.. .. ACC - AUX輔助累加暫存器 30L...Y(n)輸出 203.. ..ACCI虛數累加暫存器 302.. ..Y(n-1)輸出 401.. ..Ml累加器 402.. ..M2累加器 403.. ..M3累加器 404.. ..MUX1 多工器 501.. ..C1雙倍精確度乘法器 502.. .乂2雙倍精確度乘法器 503.. .. C3雙倍精確度乘法器

第20頁 501344 圖式簡單說明 504.. .. C4雙倍精確度乘法器 510.. ..AX雙倍精確度乘數 511.. ..BX雙倍精確度乘數 512.. .. AXH雙倍精確度乘數高位元 513.. .. AXL雙倍精確度乘數低位元 514.. ..BXH雙倍精確度乘數高位元 515.. ..BXL雙倍精確度乘數低位元 520.〜SM0單倍精確度乘法器 521.. .. SM1單倍精確度乘法器 522.. ..5.2單倍精確度乘法器 523.. .. SM3單倍精確度乘法器 524.. ..ρρ0部份乘積 525····ρρ1部份乘積 526.…ρρ2部份乘積 527.. ..ρρ3部份乘積 530.. ..5.0左移Ν/2位元器 531._SH1左移Ν/2位元器

第21頁 501344 圖式簡單說明 532.. ..左移N位元器 533.. .. WAD 加法器 534.…ΑΧ X BX雙倍精確度乘法積 2001.. .MAC Input乘加器輸入值 2002.. .Product 乘積 2003.. .AR BR AI BI對應暫存值 2004.. .P0〜P3四個乘積 2101.. .現在輸出累加積 2102.. .前一輸出累加積 2103.. .後一輸出累加積 1701.. .AXH被乘數高位元 1702 ...AXL被乘數低位元 1703···ΒΧΗ 乘數位7〇 1704.. .BXL乘數低位元 1801…部份乘積一 1802…部份乘積二 1803…部份乘積三

第22頁 501344 圖式簡單說明 1804··.部份乘積四 1901.. .乘法 1902.. .加法 1.. .... AR實數暫存器一 2 .......AI虛數暫存器一 3 .......BR實數暫存器二 4.. .....BI虛數暫存器二 601.. .. CR(k)濾波器係數實部一 602.. .. CI(k)濾波器係數虛部一 603.. .. CR(k+l)濾波器係數實部二 604.. .. CI(k+l)濾波器係數虛部二 605.. ..XR(n-k)輸入實部一 606.. ..XI(n-k)輸入虛部一 607.. ..XR(n-k-l)輸入實部二 608….XI(n-k-Ι)輸入虛部二 701〜716...A0〜A15單倍精確度乘法器 801〜808...B0〜B7累加器

第23頁 501344 圖式簡單說明 901〜904…accO〜acc3複數累加暫存器 1001.. .Y(n)輸出 1002···Υ(η -1)輸出 1101〜1104...SO〜S3輸出加法器 1201.. .實數資料搬移 1202.. .虛數資料搬移 2201.. .t=n-4前四時刻 2202.. .ΐ=η目前時刻 2301.. .目前輸出累加積 2302.. .前一輸出累加積 2303…前二輸出累加積 2304.. .前三輸出累加積 1.. . AR實數暫存器一 2.. .ΑΙ虛數暫存器一 3.. .BR實數暫存器二 4.. .ΒΙ虛數暫存器二 701〜716...Α0〜Α15單倍精確度乘法器

第24頁 501344 圖式簡單說明 801〜808...B0〜B7累加器 1101〜1104...S0〜S4輸出加法器 1301.. .C(k)濾波器係數一 1302.. .C(k+1)濾波器係數二 1303·..C(k+2)濾波器係數三 1304.. .C(k+3)濾波器係數虛部四 1305 …X(n-k)輸入一 1306 ...ΧΟι-k~l)輸入二 1307…X(n-k-2)輸入三 1308…X(n-k-3)輸入四 1401〜1413...acc0〜accl2累加暫存器 1501···Υ(η)輸出一 1502···Υ(η-1)輸出二 1503…Υ(η-2)輸出三 1504···Υ(η - 3)輸出四 1601〜1603…暫存器資料搬移

第25頁

Claims (1)

1. ^υΐ344 ^υΐ344 丄 --—Mpu 9Q1053fifl 六、申請專利範圍 、'申請專利範圍 ----邊正— 4·如申請專利範，項所述之雙倍精確度複數累 倍精確度之細⑽叫彳爾輪咖 度之軸’卿姊財糊_ =確 5·如申請專概嶋雜咖 縣時，每個雙倍射度之乘絲巾之_單倍财 十仃運异之早倍精確度之複數累加器。 6. 如申請軸_ 3項所述之雙倍精確度複數軸，在單倍數 實數乘加時的運算時’四個雙倍精讀度之乘法器中之十六個單 倍精確度之乘法器乘積’可以經由多工的方式重新架構成十六 個平行運异之單倍精續度之實數累加器。 7. 封用以不同資料格式（包含複(實)數與雙(單)倍精確度）的 乘加器’其中所謂用在雙倍精妨複數乘加騎運算方式包括 ——— 一對雙倍精確度複數為四個雙倍精確度值輸入以四個雙倍數實 數乘法1§做魏紐料：此職倍精確度紐，實數乘實數 積與虛數乘虛數積共同累加成複數累加的實數和，實數乘虛數 ^虛數乘實數積共同累加成複數累加的虑數和〇 麵咖脑九一"丨~一 -- 第27頁 501344 案號 '申請專利範圍 8·如申請專利範圍第7項所述之可用以不同資料格式（包含複(實） 數與雙(單)倍精確度）的乘加器，其中所謂用在雙倍精確度實 數乘加運算時的運算方式包括：兩對各自連續的雙倍精確度實 數為四個雙倍精確度值輸入至第二項複數乘法器，以四個雙 倍數實數乘法器做複數乘法運算；經由適當多工，每次可得兩 個輸出值。 9·如申請專利範圍第7項所述之可用以不同資料格式（包含複（實） 數與雙(單)倍精確度)的乘加器，此兩對雙倍精確度實數做 對應至第二項複數乘法可得目前輸出之累加積、上一輸出之累 加積及下一個輸出（累加積；每一次乘加循環前，將下一個輸 出累加積移至上一個輸出累加暫存器中。 1〇.如申請專利範圍第7項所述之可用以不同資料格式（包含複(實） 數與雙(單)倍精魏)的乘加器，兩對輸入訊號每兩個時刻做 乘加楯環運算即可，對齊處理可免除。 申明專利範圍第7項所述之可用以不同f料格办包含複(實） ^錢(單)倍精確度)的乘加器’其中所謂四個雙倍精確度之 方式包括：每個雙倍精確廑之垂法器之兩讎 第28頁

   ，可分成高位元與低位元_單射餘；兩倾數兩兩以 早倍精確度實數乘法器之四個相乘積用左移相加的方式可得 雙倍精確度之乘法之乘積。 12.如申凊專利範圍第7項所述之可用以不同資料格式（包含複(實） 數與雙(單)倍精確度)的乘加器，其中所謂用在單倍精確度 複數乘加運算時的運算方式包括1倍精確度之乘法器之設 计方式，將高(低)位元單精確度值設為單精確度複數中之實 (虛)數；高位乘高位乘積與低位乘低位乘積累加可得累加實數 部份，高位乘低位乘積與低位乘高位乘積累加可得累加虛數部 份。 13·如申請專利範圍第7項所述之可用以不同資料格式（包含複(實） 數與雙(單)倍精確度)的乘加器、，四組單精確度複數乘加器各 有-對複數g加1 ’軸喻平行鮮的喻單精確度複數 乘加器；兩對各自連續的單倍精雜複數為四個雙倍精確度 值輸入至上述之四個單精確度之複數累加器中。 14.如申請專利範圍第7項所述之可用以不同資料格式⑶含複⑻

   第29頁 甲_專利範圍 ^兩組賴加H賴目_累加值…組為上一 :出累力—為下-個輪出累加值;經由適當多工每 :可得目前詢加值及上-時物累加值；每一次乘加 “侧，將下-個輸出累加積移至上—個輸出累加暫存 做—絲域猶算即可，對齊處’ 理可免除。 如申請專利侧第7項所述之可用以柯 數與雙⑻倍精確度)的乘加器，其中所謂用在單::::實) =日㈣’输、自物單倍精確^ 貝數為_雙倍精確度錄人至上述之喃單精確度之複數 累純中’可算出目前輸出累加積，上—個、上兩個、上三 個二—個、下兩個、下三個輸出累加積；經由適當多工— 累rmr輪出值；每一次乘加循環前’將下一個輪出 '、、上二個輪出累加暫存器中，將下兩個輪出累加秒 料上兩個輸出累加暫存器中，將下三個輪出累加積移至貝 上一個輪出累加暫存器中；四對輸入訊號每四個一 乘加•衣運算即可，對齊處理可免除。 人