TWI325240B - Method for determining cholesky factor, method for recovering data from data signals and method for use in solving linear equation - Google Patents

Description

1325240 九、發明說明： 【發明所屬之技術領域】 » 本發明一般係與解決線性系統有關。明確地 1，本發明係關於使用陣列處理來解決線性系統 問題。 【先前技術】 由一線Λ气統方案可用以解決許多的工程問題。其 Β*镂、為，在使用分碼多重接取（CDMA)的分 二通信/統中進行多重使用者信號的聯 此系統中，多位使用者會在相同 固度的時間區間（時間槽）中同時傳送多重通 多重？訊都是以不同的展開碼進行傳 ‘中一種m值學個叢訊都會經歷一頻道響應。 ^便是聯1伯二盆i的叢訊之中將資料還原的方 接收。圖Γ所示"的便=用者資料會同時被 可使用於使用者設備或基種地糸:'。聯合债測接收器 收。所接收到的信號合被收彳5號的形式被接 並且由-個或彡個請降至基頻， -接收向量£。頻羊道 信叢訊部分來估算該等叢 a使用一連串的通 測元件1〇〇則會使用經過的頻道響應。聯合伯 展開碼以及經過估算< ^异，已知的使用者叢訊 使用者原來所傳“#知:^^所有 示 聯合偵測問題的模型通常可以方程式丨來表

Ad+n=r i是傳輸資料向量；r是接收向詈.方程式1 # -a rAwrxn- A 一 收门里，这疋附加的白高 進仃卷積计异之後所構成的ΜΧΝ矩陣。 解方程式1的方式有兩插， 法，另一種則# | 種種是零強制（ZF) 程式2為一奉取均誤差(―法。方 飞』為ZF方案，其中假設a近似於跫。 ύτ=(ΑΗΑ)-ιΑΗτ " 方程式3及4為一 MMSE法。 方耘式2 d=R-'AHr R=AHA+a2I 方程式3 ^ 2 9 ^ 方程式4 σ疋雜訊II的變異數，以彳是等同矩陣。 岸及古：工出:戈已經知道展開碼、頻道響 Λ交異數的平均值，而且所接收的向量也是 二因此只有資料向量注是未知的變數。 =Λ 1^夂方，（例⑹直接矩陣倒置）都過度 i 降低複雜度的方式便是克洛斯基分 【Λ Λ基演算法可將對稱正有限矩陣(例如』或 Ρ ί式5,方式分解成一下三角矩陣G以及一 上一角矩陣G 。 ^R=GGH 方程式5

—對稱正有限矩陣3可以方程式6的方式，將A 矩，乘以其共軛轉置（赫密遜（hermetian))矩陣八^更 可產生。 ^=AhA . 方程式6 為簡單起見，可以方程式7定義F。 方程式7 可分別將方 A1 。 因此’針對21?及MMSE兩種方式 程式1改寫成方程式8及9。 方程式8 方程式9

Rd= r 為解出方程式8或9，可依照方程式1〇的方式使 用克洛斯基因數。 GGHd= r —: 方程式10 一變數y可以方程式11來定義。 GHd=v 方程式11 使用變數y，可將方程式10改寫成方程式12。 Gy= γ 方程式12 分可Ϊ取Π亥資f向量而必須進行的最複雜的部 =的”，利用已經推導出來的= 陣（例如X或r)產生G矩陣。 喇丨r矩 g=cholesky(2或 R) . n 利用G矩陣，可以方程式14的方式私式3 8中進行G矩陣的正向替換解出y。 在方私式 y=FORWARD SUB (G,r) . 利用G矩陣的轉置矩陣，gh，可 $ &式’14 方式，在方程式U中進行逆向替換冑出=程式b的 d=BACKWARD SUB (〇Η ν) 〜 針對矩陣2或R(針對矩陣R可以雷方^式15 $行），可以下面的演算法決定出方2=f 士 斯基因數G。 枝式13的克洛

對於i=l:N 對於 j = max(l,i-P):i_i 1325240 . λ = ηιΐη〇 + Ρ,Ν) &ΐ：λ,ΐ = ^ΐ：λ,ΐ-^*; · ai:>,j ； 最後； X = min(i+P,N) ^ΐ：λ?ΐ=^ΐ：λ5ΐ/» 最後； G= 2 或 R ; ad，e代表的是矩陣2或R在d列e行的元素。「：」代 表的是「從…到…」運算子，例如「從j到N」；而 籲 （·广代表的則是一共軛轉置（赫密遜）運算子。 另一種解克洛斯基因數的方式則是使用N個 平行向量處理器。每個處理器各映對到矩陣2或R 其中一行。每個處理器中的行可以一變數μ來定 t 義，其中μ=1:Ν。針對μ=1:Ν而言，該平行處理器子 * 常式可看成下面的子常式。 - j=i 當』<μ recv(gj:N, left) • 若 μ<Ν send (gj：N, right) end for αμ:Ν,μ ~αμ:Ν,μ~§;ί/8μ:Ν j=j+l end for αμ: Ν,μ — αμ : Ν,μ/ ^αμμ 若μ<Ν send (αμ:Ν,μ, right) 1325240 end for recv( . , left)是從左方處理器接收的運算子；send( · right)是傳送至右方處理器的運算子；而红l則是來 自鄰近處理器的數值。 ’、 圖2a-2h所示的便是此子常式。圖2a所示的係聯 合偵測元件的向量處理器及相關的記憶體單元方 塊圖。每個處理器501至50N (50)都係在該矩陣的行 上面進行操作。因為矩陣G係一下三角矩陣，而矩 陣2或R以其下三角部分便可作完整的定義，因此 只需要使用到下三角元素（ak，丨）即可。 圖2 b及2 c所不的係該等處理器對其下方的單 元可能進行的兩種函數。在圖2b中，下尖三角函數 52會對μ處理器50下方的單元（&叫至&Νμ)執行方程式 16 及 17。 V— αμ..Ν，μ / R 方程式 16 :=ν 方程式17 「<-」代表的是同時指派，「：=」代表的是循 序指派；而V則是已經傳送給右方處理器的數值。 在圖2c中，右尖三角函數52會對μ處理器50下方 的單元執行方程式18及19。 ν<-μ 方程式18 3μ:Ν，μ · —^μ:Ν，μ νμΥμ:Ν 方程式 19

Vk代表的是與第k個處理器50之右方數值相關 的數值。 圖2d-2g所示的係一 4x4的矩陣G之資料流與函 數。如圖2d-2g所示，針對每個階段1至4的處理來 說，都會脫離最左邊的處理器50，而下尖三角函數 52則會從左邊移往右邊。為貫現圖2d-2g，該下尖三 1325240 ，形能夠以執行該下尖三角函數的方式，實際 朝右處理器或虛擬取代朝右處理器。 代 如圖2h的階段1所示，可於第四個處理哭％ 面增加（N-4)個朝右處理器％並且在每個處理4灸 的下矩陣對角線中增加（Ν-4)個單元，便可將^ 兀素擴大成NxN的矩陣及N個處理器5〇。在此=^ 中的處理會於N個階段中進行。 置 不論是利用向量處理器來實現克洛斯基 解’或是將其直接分解成純量處理器，兩種方

效率都非常差，因為在每個處理階段女 量的處理資源閒置不用。 促丨曰有大 糸統 因此，吾人希望以替代的方式來解決線性 的問題。 【發明内容】 本發明提供的是用以解決線性系統的處理元 素。其中一種具體實施例是將該矩陣對角線上的矩 陣兀素投影在純量處理元素中，以便決定出克洛斯 基因，。另一種具體實施例則是使用二維的純量陣 列決疋出克洛斯基因數。第三種具體實施例則是使 用可重組的純量線性陣列決定出克洛斯基因數，並 且進行正向替換及逆向替換。對有限帶寬的矩陣來 ，，必須，少該等具體實施例中所使用的處理器數 量。將該等處理器摺疊便可減少該等具體實施例中 所使用的處理器數量。另一種具體實施例則是使用 可重組的處理元素決定出克洛斯基因數，並且進行 正向替換及逆向替換。 1325240 【實施方式】 符& ΐ 3at Γ所示的係用以進行克洛斯基分解以 且^ 矩陣的N個純量處理器54ι至54n (54)之較佳 具體貫施例。雖然本方式可擴大成如圖城3二： 矩陣G，不過，為簡化起見，將針對4x4 的矩陣G進行說明及解釋。 ”^所Ϊ :係用以執行前面的演算法之三維 ;;。為簡化起見，圖乜所示的係用以 :f 陣、▼寬為3之示意’。每個節點所 執仃的函數顯示於圖4b_4et。圖仆中 行的是方程式20及21。 《 w双巩 y ^-λ/^7 V 方程式20 方程式21 t代表的是同時指派。ain係從低階至該節點的 ^二^二則是傳送至高階的輸出。圖4c是用以 執仃方私式22及23的平方函數。 Υ<_Ζ 方程式22 〜nk|2 方程式23 圖4d是用以執行方程式24、乃及％的八角函數。 y<—w 方程式24 X<r- a in /w 方程式25 a〇u々X 方程式26 圖4e是用以執行方程式27、28及29的圓形函數。 y*^w ^ , 3 方程式27 X<_Z 方程式28 〜一 方程式29 圖5a所不的係用以將4χ4矩陣G之向量式克洛 斯基分解之第一階段映對至二維的純量式方法之 1325240

第一階段的示意圖。如圖5a所示，每個 52、54都會映對到至少一個純量處理器 及62。每個純量處理器56、58、60、62都合盥一 a._ 記憶體單元有關。每個處理器56、58、6〇 : 62所執J 行的函數顯示於圖5b-5e中。圖5b顯示的係用以執行 方程式30及31的五角函數56。 y — E 方程式30 〜:=y 方程式31 :=代表的是一循序指派。y代表的是傳送至一下方 處理器的一數值。圖5c顯示的係用以執行方裎式 32、33及34的一八角函數58。 y<_W 方程式32 X —方程式33 a,:/ ：=x 方程式34 w代表的是傳送自一上方處理器的一數值。圖兄顯 示的係用以執行方程式35及36的—正方形函數6〇。 y- 方程式35 -ΙζΓ 方程式36 X，代表的是傳送至右方處理器的數值。圖5e顯示的 係用以執行方程式37 ' 38及39的圓形函數62。 y"~W 方程式37

—Z 方程式38 _ 方程式39 圖0a-6d所不的係在四個循序階段（階段1至 2該等if處理器56、58、6〇、62中的資料流動 所示’每當執行過-個階段之後， 處理循環，若是-般的情形，則必須進二固=

12 =:母個階段都需要進行一個處理循環。如圖5a 2不’總共需要十個（10)純量處理器方能決定出一 理的曰矩陣G。對一 NXN的矩陣來說，所需要的處 理态數1如方程式4〇所示。 所需要的純量處理器數量方程式40 示咅，6e:6j^ :的係一 5乘5帶狀矩陣之處理流程 矩;m方理器係以實線來表示。該帶狀 上方的tit二。如圖6e所示，第一階段中係由 中的丄i主ΐ ΐ器進行作業。如圖6f所示，階段1 H中=處理器已經決定出…“以及 使用。 22 %2及化，該等數值可供階段2來 ^43、《44 )六 ’在階段2 々43及八4。 客43與《53以 在階段2中係由（《22、《32、％、3 、 個處理哭進杆你普 42 中备、JL二Ϊ作業。如圖6g(階段3)所示 二决疋出A2、知與 在圖6h (階段4)中，闽值外3 及中間值/ 、7 β圖中已、及決定出g33、g43與知以 經決』if盘:圖& (階段5)中，圖中已 段）中則可Γ生。。=圖6i(最後一個階 入之矩性關係，作業時並不需要未載 出。 下方處理器，因而圖中亦未將其示 如圖7所示，圖6a_6d的簡圖 陣。如該圖所示，最了擴大成一 NxN矩 j數。八角函數處理器孓！3器56會中執行-五角 亦會延伸至主斜二S s在弟—仃中往下延伸， 器64(圖中以兩個电人二用，的正方/五角處理 σ圖形表不）。其餘的處理器66 13 Γ ϊ Ϊ途?八角/圓形處理器66 (圖中以兩個 ΐ 6 f 此種結構僅需要使用純量處理 =，便可在N個處理循環中決定出一個ΝχΝ的矩 G 〇 f p如^該矩/車的頻帶係有限的寬度的話，例如 ，那麼便可減 >、處理元素的數量。 果P等於N-1的話，那麼便合请査 突，田从\了丨沒便曰遺棄〜的左下方處理 :。如果Ρ專於Ν-2的話，那麼便會再遺棄兩個 态（aN_i丨及 aN2)。 少幼ΐ ί Ϊ配ί *圖8心及9績外進一步地解釋減 v 處理兀素數量的情況。圖心如所示的係圖 6d中四個（4)純量處理器實現方式之一維執行 如ί8&所示，在每個同時連接之間都會插入圖 ^政^遲兀素68。圖8e的延遲元素68會依照方程式 41將輸入y延遲成一序列輸出X。 Υ· X — 方程式41 對每個從tl開始的處理循環來說，該等處理 會=對角線（其代表的是執行面）所示般的方式進 二為作說明，在時間I時，僅有αη的處理器 作月i ·行作業。在t2時，僅有0121的處理器58能進行 你^，在t3時，僅有α31及0122的處理器58、60能進行 2 ί 此類推，直到階段4中，在k時，便僅有〇c44 ❿=f态56能進行作業。因此，整個處理在N個階 1又中…共需要N2個時脈循環。 准一^由二維的純量處理陣列便能夠對多個矩陣 社H I路處理。如圖8a-8d所示，該等處理器可在特 行面中，t^tie，進行作業。對一特定的階 Ϊ ΐ Ϊ &在同一時間能夠處理與執行面數量相同的 里。為作說明’針對階段1，會沿著對角線 14 tl處理一第一矩陲。 陣會遞送至平面而脈循環而言，第一矩 f陣。此種管路處理方用以處理-第二 任何數量的矩陣。管路處 f也進行，用以處理 :諸存所有矩陣的資料是，其必須 程使未受到任何阻礙。κ矩陣貝料可用性之排 都經由階段1 ，矩陣便會二以以；處理之後， 列：ΐ;!Γ。/用管路處理，可；幅地以： 的、.心机里，並且增加處理器的使用率。门乂陴 因為在每個時脈循 處理器56、58、6〇、二循上中f不會使用到全部的 可藉由於整個執行面中丘虽^處理1個矩陣時， 56、An 中/、用的方式，減少處理元素 以減'丨、，二6i的數量。圖如及外所示的係兩種用 凡素的較佳實現方式。如圖9-示，ί 角線垂ΐ ΐ ί56、58都有一條沿著該等矩陣的對 的處理ί ί；4執行面的直線。因為每一條垂直線中 粁作查态门、58、60、62係在不同的處理循環中進 η，因此可以下方所投影的單處理器66、64來 一 =函數56、58、60、62。處理函數56及60係由 斫的組合函數64來執行。處理函數58及62則係由 新的組合函數66來執行。延遲元素68以及處理器之 間的連接線同樣會進行投影。雖然圖中最左邊的處 理元素係一雙函數的元素66，不過，對非帶狀的矩 陣而言’亦可將該元素簡化成僅需執行八角函數 58 ° 圖10a所示的係將圖9a擴大成一 ΝχΝ的矩陣g。 如圖10a所示’總共需要ν個處理器66、64方能處理 該NxN的矩陣G。如圖3a所示，可以N個純量處理器 15 40 54來執行圖l〇a的處理函數0火 時’可以與頻帶⑺相同數二為帶狀矩陣 該矩陣G。 里的純f處理器來處理 在圖3a的實現方式中，备 =循環才會使用到。偶數處隔-個 %中作業，而奇數處理界里益會在其令一個循 f。為作說明，圖9a的處理、曰2= '個循環中作 :在時間t2、Mt6作業，而處;里弟二個) 業。因此，利用該處理陣列 W 及4作 =便能夠決定出么的圖輸= 使；^ T起來，此種方式能夠大幅地提高^4理器的 現方^縮re的,處理時間，可使用圖外的實 J線之間的延遲元素移除時=間里1 的處理器58、6〇則 f 2;，=，《22及叫 該陣列出沿著垂i ϊ ®外同時顯示將 斤示，延遲元素68的數量已經減 (NP-(P2 pv2^列，NXN的矩陣G之處理時間為 LV:)2)。因此’可大幅地縮短單-矩陣G的處 理陣^都可及扑實現方式的另一項優點是每個處 ^ ^ 4. LIVel t ί 3fflbr^ 因為下斜- 士 1 a ^ ^ 跣圖3a及3b來說’ 線，所以，合7是圖％及9b最左邊的垂直 遺棄。以圖% 1；^由忒專垂直線投影產生的處理器 ” "a作說明，該矩陣的頻帶中，a4i、a3丨 1325240 予ΐϊίΐ^58、62為零值。因此，不必使用到 取左邊杈影至處理器66的兩個投影來 理。從而，該等實現方式可縮放成與該矩c 等的大小。 干艰▼相 圖9c-9n所示的係針對一頻帶為3、相間 具，延遲兀素、5乘5的帶狀矩陣之每個處理循環之 時序，。圖中所示的係在每個時間週期中，與 處理器相關的數值。作業中的處理器係以實^ 示。如該等附圖所示，該項處理係從圖氕、階 = 時間〇的左上方處理器（\)經由該陣列朝圖％、 1 的^V7方，理& (δ55)來進行。如該等附®所示， 由於该矩陣的帶狀特性關係，作 狀矩陣的左下方處理器，因而圖中亦未Td 圖9o-9z所示的係針對用以處理一 5乘5的 ，卩之線性陣列（例如圖9b)的每個處理 =記憶體存取示意圖。如圖所示，由於以 、陣之頻帶為3，因此僅需要三個處理器即可。 圖出，僅需要三個處理器便能處理該 I肖，陣。圖中同時顯不出，每個階段都具有非常 尚的處理器使用效率，其效率會隨著N/p而增加。 ^降低該等處理元素的複雜度，該等（被選出 1)70素並不會執行除法及平方根函數。因為與加 =^減法及乘法比較起來，在ASIC中比較難以實現 除法及平方根計算。 、 ，一會執行除法或平方根計算的兩個函數為 ^及◊角函數56、58。對特定的階段來說，如圖 a所示，五角及八角函數56、58全都是在某一 p皆 ^ =單仃中來執行。明確地說，對該等行來^兒，最 上方的是五角函數56，而其下面則是八角函數％。 1325240 而不必直接儲存任何a.m向下流至整行， 使用W輪入產生乂輪出;。回角函數口同樣會 中的正方形及圓形函數6() ί至％。在％計算 可。出個:Λ函數之x輸出的數值即 其W輸人數值，每，角、函H :數58之aij除以 同，而該值即為五角函上==輸^ —Φ 4J, ^ |ΤΑ *4- / Τ '^荆出值。因此，唯 角函數58的的時I根函數的時候便是在計算八 八角函]:ί二3::角::之、角函數的X值為該 Τ幻I示决的話’便僅需要決 =亞 的平方根值之倒數，而出f八角函數之％ 此便可僅讓該八角處理器不二行；值、’如 後面的正向替換及逆向替換而 \此彳乍法對於 為在該等演算法中的^ 、 σ亦相虽地方便，因 數，因此可進—+地務都變成倒數的倍 15d的X輸出）中的;兀素（即圖以與

Hit同的處理器64來執行，因此，可以ί 如圖_ 10b所二=f理器66、64， Γ ^; /Λ ™ν6ΓΛ""； …方根倒數結果會在所有的處理器66之中^送。， 11a及Ub對應於圖10&及101)。將該 70獨立出*，可簡化其它處理器“、數6二以口數 雖然可以一倒數電路及一平方招 :二 ，不過較佳 :(騰)的方式來實現，此方式的記 當決定出克洛斯基 η _ 山一队、〜〈俊，便可以圖12a =中所示的正向替換方式來決定乂。該正向替換 /貝·?τ* /ίτ如下·

for j=l:N end

Sjj -Συ

對帶狀矩陣來說’其演算法如下： for j= 1 :N for i=j+l:min(j + p,N) ri= ri - Gjjrj ； end for ； end for ； y=rj ; gLK對應的是該克洛斯基矩陣G中L列K行的元素。 圖12a及12b所示的係使用純量處理器對一 4χ4的 矩陣G進行正向替換的兩種實現方式。處理器72、 74會執行，兩種函數’圖Uc中的星狀函數72以及圖 12d中的菱狀函數74。星狀函數72執行的是方程式42 及43。 方程式42 方程式43 y<-w X<-Z-W*gij 1325240 菱狀函數74執行的是方程式44及45。 X<~Z/g，J 方程式 44 y<-x 方程式45 插入im處理元素之同時指派連接線之間 列谁—沪=素，並且對垂直於其執行面…至y的陣 中衫，如此便可將該陣列投影在一線性陣列 偭:所接收到的向量值輸入該陣列之 ί 1 i 1從該陣列輸出少,_少4。因為菱狀函數74僅會 在主對角線上執行，因此，如圖14a所示，可將該 =個（4)處理元素陣列擴大成使用 ΐ=ΝΧΝ的矩陣。此陣列所需要的處理時= #用ί為ί個處玉里元素僅會於相fa14理循環中才 H Ϊ ’ f ί ’如圖12b所示，可將-半的延遲元 m除 '如圖13b所示，可將所投影的線性陣列擴 ίίϋΓ。的N x N矩陣。此陣列所需要的處理時間為 所示的係依照圖13b之投影陣列的處 =素循裱所進行的作業情形。在圖&的第一循 衣中（t丨），會將η載入左邊的處理器1(?4)，並且 ^及^決定出少，。在圖14b的第二循環中（t2)，合將厂 ，2載人，並且對如、〜及〜加以處理之後便曰可決2 2 ::乂在圖He的第三循環中⑹’會將^载入： 亚1载入&丨、尽42、A2、A3之後便可決 =定的出第:循環中⑹一 一處理之3後便 處理的二乘以:以= 二個零值項目（帶寬為3)的矩陣之帶狀特性。/、頁 20 為顯示出正向及克洛斯基分解能夠使用相同 、，處理元素’所以圖12f將從階段6開始進行。階段 係接續圖9c-9n的最後一個階段。 同樣地，從圖1Α-Πρ可看出，圖9o-9z的處理哭 =可延伸用以執行正向替換。該等圖都係從階段°°6 j始’接續克洛斯基分解的五個階段。每個處理循 缞所執行的處理係從階段6、時間〇 (圖l2k)進行 、時間4 (圖120)，然後產生最後的結果（圖 、，當利用正向替換決定出變數y之後，便可利用 ，向替換來決定資料向量。逆向替換可以下面的子 韦式來進行： for j=N: 1

\ '=川 J end 對帶狀矩陣來說，則可使用下面的子常式 for j=N: 1 yj=yj/G"J * for i=min(l,j-P)：j-i yi = yi-Gljyj end for ； end for ； d=y ; (·)*代表的是複數共軛函數。 克洛斯基因數G所決定出來的表=疋^對該 軛值。YL則是y的對應元素。 〜兀/、之複數共 針對一 4x4的矩陣來說，亦 所示的星狀及菱狀函數7 6、7 8，二用曰如圖…及!讣 以純置處理器來實 21 之S： 1325240 現逆向替換。不過’如圖15c及15d所示，該等函數 都係以矩陣G之數值的複數共軛值來進行的。因 此’方程式42-45會分別變成46-49。 y<-w X <- z - w * g*. 方程式46 方程式47 方程式48 y<~x 方程式49

於處理器7 6、7 8之間的同時指派連接線中配置 延遲元素68之後’便可將圖15a的陣列沿著整個執 行面投影至一線性陣列中。如圖16a所示，此陣列 可擴大成一 ΝχΝ的矩陣。將父向量數值載入圖16a的 陣列之後，便可輸出資料向量益。此陣列需要個 時脈循環方能決定出4。因為相間處理器係在相間 時脈循環中進行作業，因此可同時決定出兩個红。 因為圖16a中的每個處理器76、78僅會於在相 間時脈循環中進行作業，因此，如圖15b所示，可 f相間的延遲元素移除。如圖16b所示，圖i5b的投 影陣列可擴大用以處理一 NxN的矩陣。此陣 ^ N個時脈循環方能決定出辽。 圖17a-17d所示的係依照圖1讣之投影陣 =素％、78之循環所進行的作業情开》車在Ί Ϊ ί ϊ Ϊ %中（tl)，會將少4載人，並且對g.44加以處 f =後便可決定出A。在圖17b的第二循環中 ;:2及少3載入，並且對g、及心3加以處理之(後)便 入？ ί f i3。*在圖，的♦第三循環中⑹，會將yi載 、、办定屮'ΗO' g42、。2及6加以處理之後便可 ^ A ^ ^ ^在圖I%的第四循環中（t4)，對g%3及〆44加 以處理之後便可決定出di。 從圖15e-15j可看出，圖12e_12j的處理器可延伸

22 1325240 用以對帶狀矩陣執行逆向替換。圖l5e中顯示出於 左下角具有三個零值項目的矩陣之帶狀特性。；

該等時序圖都係從階段7開始，其係接續在正 替換的階段6後面。該等處理係從階段7、時間^ 15f)開始，結束於階段7、時間4 (圖⑺）。在階严' 時間4(圖I5j)之後，便可決定出所有的資料屯至^/ 同樣地，從圖1讣-1祚可看出，圖12k-i2p的處5理 器亦可延伸用以執行逆向替換。該等圖都係從階严 \開始，接續在正向替換的階段6後面。每個處理循 環所執行的處理係從階段7、時間〇 (圖15k) 一 行到產生最後的結果（圖15p)。如圖9c_9n、12e-12. 及15e-15j所示，可將二維陣列中的處理器數 J >、，以便執行帶狀矩陣的克洛斯基分解、正向及逆 向替換。如圖9ο-9ζ、l2k-12p所示，可將線性陣 理器數量從矩陣的維度值減少成帶狀矩陣的 ▼丸值。 如圖1心及18b所示，為簡化正向及逆向替換中 個別處理元素72、74、76、78的複雜度’可將除 =數80從該等元素72、74、76、78之中獨立出來^ 圖18a及18b分別對應於圖16a及16b。雖 J向替換的處理元素72、74、76、78相關的= =，冋，不過，該等元素72、74、76、78所執行的 ，數邠完全相同。最右邊的處理器74、78會利 /态80來執行除法函數。該除法器8〇可以查的 =式來實施，利用該表決定出一倒數值，再由^右 ，的處理器74 ' 78將該倒數值使用於乘法運算 為在正向及逆向替換期間，克洛斯基計算f ^倒數值已經存在記憶體之中，因此，欲進 及逆向替換之倒數值乘法運算時便可利用已經儲 存在記憶體中的倒數值。 因為三種計苜，内 換）的資料流完全程（決定矩陣G、正向及逆向替 同的可重組陣列來執行頻：P，：以’可以相 19b所示’該可重 =王。P二種函數。如圖19a及 夠執行用以決定矩乂的每個處理元素84、82都能 向及逆向替換。！l 士車f的函數並且亦能夠執行正 正方以及菱狀函ίί邊二處理器82能夠執行五角/ 能夠執行圓形/八自 78。其它的處理器84則 行克洛斯基分解時角以最及右星當進 圓形/八角函數t 其，，處理器84則會以 換時，最右邊的處理考么虽進 '正向及逆向替 進行作業，而1 ;更a利用菱狀函數74、78 -進行作業較佳 =理; 組以執行必要的函數y二2、84都可進行重 理元素82'84都能s亥可重組陣列，每個處 算術函數並且能夠執彳^f ?替換中的兩項 5，因此，每個處理元素.’Hi 2四項函 及適當，制邏輯或其它構元(⑽)以 的複ί二1可的Ξ別處理元素8 2、8 4 函數功能86抽出，由倒數及 =方根 :圖，及施所示，較佳的係，該_。 件86迠夠以正向及逆向替換曰 根兀 p決定出欲使用於乘法運算中的倒取數值，=J，器 取右邊的處理器資料決定出欲使用於乘法j f 且傳送給該等處理器84的平方根值倒數:值法以 24

4U ^ 以查值表的方式來決定該甸數值以及該倒 I ' 0方根。或者，該倒數及平方根函數方塊86 亦可此疋一除法電路加上一平方根電路。 田為進一步地減少處理器82、84的數量，可利用 ，璺技術:圖21&及21b所示的便係摺疊技術示意 :4技術中，並不需要在線性系統方案中使 J、旦素82、84，對^條摺疊來說，僅需要較 乂^()的處理元素即可。為作說明，如果P為九個 L ίΓ器82、84的話，那麼，在三條（3)摺疊中， Γ-ί三個(3)處理器82、84即可。摺疊技術的缺 ==，過縮短的陣列的處理時間會隨著倍數值q 效i。口對而ϋ點Λ是通常都可提高處理器的使用 s 條摺璺來說，處理時間便會變成三倍。 料^ : 在最小的處理器數量及所允許的處理資 取大處理時間之間作取捨，以便選擇出摺疊的 ^ 21a所示的係雙向摺疊示 豐中的四個處理开杏％ 口 T —條社 圖lib之陣列中+ 1 2、763、704/78便可執行 76、76、—個元素的函數。處理元素76ι、 & U I 3、# 4 8之間並未放置延遲元素，取而代之 條摺疊的資H Π =2、873、874(87)儲存每 铬声饰-上^ 雖然可如圖12a的實現方式般於备 體Γ6)，ϋ連都放置延遲元素（雙峰記憶 記憶體來取代遲兀素。亦可以兩組單埠 疊1位址第中上1目';2個處理11的f料會儲存在摺 陣的資料亦、合Ά關Λ雙埠記憶體87内。來自該矩 J s攸s己憶體單元88r884(88)輸入至該等 ί Γ_\761·763、764/78之中。因為資料並不會在摺 =1處理764/78與摺疊3處理器76間環繞， 在該等處理哭之Μ τ、,从 因此 過，m * 士 。。 間並不必使用雙埠記憶體87。不 摺蟲在摺疊1與摺疊2的處理器761以及摺疊2盥 接® 3的處理器76 /78 箱1付u ra «/、 虛堍夾仲本-α 要有一個位址，因此以 ίΪίΪΐ雙埠記憶體87°在第二摺疊中，每個處 該在摺疊2的記憶體位址内。來自 76 η/的貝科亦會輸入至摺疊2的處理器76ι-763、 的、二J二摺豐2的處理器761的資料係來自摺疊1 的处π态、761，而該兩個處理器76丨實際上係相同 麵-1 tb並不需要此條連接線（不過圖中仍然將其 L ^ ΛΛ ^在第二指疊中，每個處理器的資料會 介:在摺疊3的記憶體位址内。來自該矩陣的資^ 晶、《輸入至摺疊3的處理器76丨_763、764/78之中。摺 的處理器76V78的資料係來自摺疊2的處理器 卿^1，因此亦不需要此條連接線。在下—個處理 白丰又中’該項程序則會重複摺疊1 〇 圖22a所示的係將圖21a之雙向摺疊實現方式 =大成N個處理器76i_76n i、76n/78。該等處理器 、76N/78可依照功能設計成〆線性陣列，用 以存取該雙埠記憶體87或兩組單埠記憶體。 ^ 圖^2115所示的係圖Ub之陣列的單向摺疊示意 ，。在第一摺疊中’每個處理器的資料會儲存在^ J相^的摺疊1之雙埠記憶體位址内。雖然，摺疊、】 处理器764/78與摺疊3處理器76!實際上會互相i連 接’不過，作業中並沒有資料會在該等處理器之間 直接傳輸。因此，兩者間的記憶體埠864可少^ I d 疊2的4理器764/78則係以料處理器 間的壞狀連接線有效地耦合至摺疊1的處理器

26 1325240 76丨。同樣地，摺疊3的處理器704/7 至摺疊2的處理器76厂 』日令议地耦合 圖22b所示的係將圖21b之單向摺 擴大成N個處理器之示意 、 式 可依照功能設計成圍繞該雙以構 逆向現克洛斯基分解、正向及 必須能夠執行克洛斯Α八經764/78處理益） 理器的函數，而且每都逆向替換的處 2U及21b中的處理哭7J f :都必二匕功能。如圖 處理器所增加心要T二； ?η/用alu來實現摺疊技術，盆中-： 5 764/78處理器)必須能夠執行十-項！ 術函數（正向及逆向替 ? π 丁一項异 有八項），而i它& ΐ換有項，而克洛斯基分解 即可。八匕的處理器則僅需要執行六項函數 ^ ^ ^ ^ ^ ^ Μ PE^ ^ f, 向替換所定義的全:卜m分解、正向替換及逆 將除法器隔離在其；：二函二:使用此托時，已經 以產生X與時广分f’其中-時間分段用 數部。標示符另一時間分段則用以產生虛 信號二1分別用以表示實數及虛數部。 相同。信b號aq與^數定義中所定義的 行讀取及/或寫人的在特定處理循環中進 一個狀態。括弧中的々t 體位置的目前狀態及下 會使用的信號。、稱則代表第二個時間分段中 27 1325240 此較佳的處理元素可適用於 過，吾人仍然希望能夠對PE1作::7 :PE中’不 其與其它的PE不同，所執行的 ^理：因為 94丨至948的每個輸人中如果標示有、「法函^多:: 其僅供PE1使用；如果標示有「_ ^的活，代表 供PE1以外的所有！>E來使用；如果」、/舌，「代表?可 則代表其可供所有PE來使用。除:」的話， 片段之外，isqr輸入都係連接至灾 而/貫p數時間 數時間片段中，該輸入則是連接^值’而在PE1的實 根倒數的函數之輸出： ^施，…備-合宜的固定點字； 如圖23所示’乘法器96合 輸出相乘。乘法器962會將多工哭9二二丨爻942的 乘。加/減*電路99會將乘法器9:及3 2 在-起。減法器99會將加/減法 5合 器945的輸出結合在一起：出及多工 至多工器94S之令。 咸法為"的輸出則會輸入 【圖式簡單說明】 圖1所示的係一聯合伯測接收器之簡圖。 圖2a-2h所示的係利用向詈虚 斯基因數的示意圖。。里處理益來決定克洛

加^ ^及3b所示的係用以進行克洛斯基分解的IV 個純董處理器之較佳具體實施例。 刀解的N # » f ίa ί ^斤示的係用以闡述克洛斯基分解之= 維靶例不意圖。 #〈— 圖5a-5e所示的係用以將執行克洛斯基分解之 28 丄 向f處理器映對至純量處理器的範例示意圖。 * # ^ ^_6(1是用以闡述純量陣列之處理流程的非 I狀矩陣’而圖6e-6j則是用以闡述純量陣列之處理 程的帶狀矩陣。 圖7所不的係沿著k軸將圖牦的投影擴大成一 ΝχΝ的矩陣之示意圖。 ，8a-8d所示的係用以闡述利用2D純量陣列中 之純里處理器之間的延遲的處理流程之示意圖。 圖8e所不的係一延遲元素示意圖及其相 方程式。 少圖9a所示的係將圖8a_8d的純量處理器陣列投 影至四個純量處理器之1D陣列的示意圖。 θ圖9b所不的係將相間處理器之間具有延遲之 純，處理器陣列投影至四個純量處理器之1〇陣列 的不意圖。 圖9c-9n所示的係對相間處理器之間具有延遲 之π狀矩陣進行克洛斯基分解之處理流程。 圖9ο·9ζ所示的係針對處理帶狀矩陣之一線性 陣列進行記憶體存取之示意圖。 =5，斤示的係將圖如及9b的投影陣列擴 大成N個純量處理器。 ’、 圖11a及lib所示的係將一倒數/ 圖l〇a及10b的陣列中分離出來。 根山數從 圖12a所示的係將每個處理器之間具有延 -正向替㈣列投影至四個，純量處③器之示意圖。 圖12b所示的係將相間處理器具有延遲之一正 向替換陣列投影至四個純量處理器之示意 圖12c及12d所示的係正向替換之一…星Θ狀及菱 29 1325240 狀函數所執行的方程式之示意圖。 圖12e所示的係對相間處理哭 派之帶狀矩陣進行-正向替“處Λ具同時指 圖12M2j所不的係對相間處理哭之η 1 士 遲之帶狀矩陣進行一正向替理=具有延 所示的係針對處理帶狀矩陣之 向替換線性陣列進行記憶體存取之示旁矩陣之-正 圖13a及13b所示的传脾ρ；! , 1 η， ° 擴大成Ν個純量處理器。'、’回a 2b的投影陣列 圖14a-14d所示的係圖12b 程示意圖。 〜仅〜丨早列的處理流 ^ ^ ^ t ^ ^ ^ ^ ^ ^ . 边向#換陣列技影至四個純量處理器之示音 圖15b所示的係將相間處 :: 一逆向替換陳列措旦彡=处里如之間具有延遲之 逆2換陣列杈衫至四個純量處理器之示意圖。 圖15c及15d所不的係逆向替換之一 狀函數所執行的方種式之示意圖。、 曼 f 15 e所示的係對相間處理器之間具有同時指 派之▼狀矩陣進行逆向替換之處理流程。 、"戶!示的係對相間處理器之間具有延 遲之V狀矩陣進仃逆向替換之處理流程。 圖15k-15P所示的係針對處理帶狀矩陣之一逆 向替換線性陣列進行記憶體存取之示意圖。 圖16&及16b所示的係將圖15a及15b的投影陣列 擴大成N個純量處理器。 圖17a-17d所不的係圖i5b之投影陣列的處理流 程示意圖。 圖18a及18b所示的係具備分離的除法函數之 1325240 圖13a、13b、16a及16b中所示之陣列。 圖19a及19b所示的係用以決定矩陣G、正向替 換及逆向替換之一可重組陣列示意圖。 圖20a及20b所示的係從該可重組陣列中分離 出倒數/平方根函數的示意圖。 圖21a所示的係一雙向摺疊。 圖21b所示的係一單向摺疊。 圖22a所示的係利用N個處理器實現雙向摺疊 的方式。 圖22b所示的係利用N個處理器實現單向摺疊 的方式。 圖23所示的係一簡單的可重組處理元素之較 佳時間分段不意圖。 【元件符號說明】 50, 76, 78, 82, 84 處理器 52 54 56 58 60 62 64 66 68 70 72 下尖三角函數 右尖三角函數 五角函數 八角函數 正方函數 圓形函數 正方/五角處理器 八角/圓形處理器 延遲元素 倒數/平方根電路 星狀函數 菱狀函數

31 74 1325240 80 除法函數 86 倒數及平方根元件 88 記憶體單元 90 多重叢訊 92 天線 94 解調變器 94}-948 多工器 96 類比至數位轉換器 96^902 乘法器 98 加/減法電路 99 減法器 100 聯合偵測元件 a). 32

Claims (1)

1325240 穷年3月日修正本 十、申請專利範圍： J 1. -種用以決定-N乘N矩陣之-克洛雜因_方法該方法 包含： X 提供一處理元素的陣列； 藉由該陣列的處理元素’接收該矩陣之連續對角線 的元素；以及 ' 使用該處理元素決定該克洛斯基因數中一相應對角線的元 φ 素。 2. 如申請專利範圍第！項的方法，其中提供該處奴素的陣列， 使得該處理元素為純量處理元素。 .3·如申請專利範圍第1或2項的方法，其中該矩陣且有— 頻帶卜並且Ρ小於Ν，其中僅提供ρ處理元素於該處理元素 的陣列。 4. 如申請專利範圍第i或2項的方法，其中該處理元素的陣列是 #用以決定一矩陣是A ’其中A係為將頻道響應以及與-聯合 伯測接收別目關狀已知制碼進行卷積計算之後所產生的一 矩陣，且AH*A的共軛轉置(赫密遜）。 5. 如申請專利顧第丨或2項財法，其中該處理元素的陣列是 用以決疋-轉為AHA+s2I，其中A係為將頻道響應以及與一 聯合_接收器相關聯之已知展_進行卷積計算之後所產生 的-矩陣，S2是雜訊的一變異數，【則是一等同矩陣且Μ是 A的共軛轉置(赫密遜）。 33 丄325240 6. 種用於將來自以一接收向量的方式被接收到的複數資料传號 之資料還原的方法，其包含·· U 使用一處理元素的陣列’藉由決定一 N乘N矩陣的—克洛 斯基因數，以決定該接收向量的資料；以及 該陣列的各該處理元素接收該Ν·Ν矩陣之一對角線的元 素’並且決定該克洛斯基gj數中—相應對角線的元素。 7. 如申請專職㈣6項的方法，其中純量處觀素是作為該等 處理元素。 8. 如申請專利範圍第6或7項的方法，其中該矩陣且有一 ==魅！>小於N，其中僅提供p處理元素於該處理元素的 如申請專纖圍第6或7項财法，其中該處理元素的陣列是 用以決定-矩陣為AhA，其中A係'為將頻道響應以及與一聯合 谓測接收H相關聯之已知展開碼進行卷積計算之後所產生的一 矩陣’且Ah是a的共轉置(赫密遜）。 10. 如申請專利範圍第6或7項的 扪万法，其中該處理元素的陣列是 用以決定一矩陣為AHA+sq，且 ，、甲A係為將頻道響應以及與聯 δ、=接_關聯之已知展_進行卷積計算之後所產生的 一矩陣，其中s2是雜訊的— β 芡異數’I則是一等同矩陣，且Ah 是A的共軛轉置(赫密遜）β 11. 如申請專利範圍第6或7項的 在其疋藉由一使用者設備而 34 以—接收向量的方式被接收到的複數資料 6或7項的方法，其是藉由一基地站而執行， 接收向里的方式被接收到的複數資料信號之 、、種用以決&N乘N轉之—克洛斯基因數並且將所決定的克 各斯基因朗於正向及逆的換巾啸出—雜方程式的方 法’該方法包括： 提供最多N個純量處理元素的-陣列； 藉由該純量處理元細_，自該N乘N轉接收元素， 各純量處理元隸肋蚊魏洛聰隨並且肋執行正向 及逆向替換；以及 輪出來自該純量處理元素陣列的該接收向量之資料。

執行’用於還原來自 信號之資料。 12·如申請專利範圍第 用於還原來自以一 資料。 、申明專利摩巳圍第I3項的方法’其中各純量處理器係用以處理 ^由用來歧就洛舰隨域行正向及逆㈣換之陣列所 處理之一矩陣的一對角線。 里的方式被接收到的複數資料信號之 15. 一種用以還原以一接收向 資料的方法，其包含： 糟由決定-矩陣之一克洛斯基因數以及將該決定的 克洛斯基隨祕正向及逆姑換，以決定雜收向量之資 料’進而藉由使用最多N個純量處理元素的—陣顺決定該接 35 I32524U 收資料信號的該資料，包含： 藉由該、··屯里處理元素的陣列，自該n.n矩陣與該接收向 量接收元素； 將各純量處理元素用於決定該克洛斯基因數以及進行正向 及逆向替換；以及 輸出來自該純量處理元素陣列的該接收向量之資料。 16.如申請專利額第15項的方法，其中各純量處理器係用以處理 欲由用來決雜克輯翻數且執行正向及逆㈣換之陣列所 處理之一矩陣的一對角線。 Π.如申請專利範圍第15或16項的方法，其中該矩陣具有 -頻帶P並且p小於N ’其巾僅提供p處理元素於該處理元素 的陣列。 18. 如申請專利範圍第15或16項的方法更包含： 在一裝置中執行-平方根及倒數函數，該裂置_合至該 陣列的一單一純量處理器；以及 使用該__純量處理糾定該克洛斯基錄，不執行 平方根及倒數函數。 19. 如申請專利範圍第18項的方法，其中_查值表翻於該平方根 及倒數函數。 ms請專概圍第15或16項的方法，其巾各處理元素用以執 订處理該N乘N矩陣的複數條對角線。 36 Γ。項的方法，其中對於複數倍其中之-，各 〜陣之一單一對角線的元素。 線性配置，處H該Γ方法’其中該純量處理器依照功能成 數。 幻兩方向的資料以決定該克洛斯基因 23.2請專利翻第15或16項的方法，其帽由使用各純量處 _姆齡的延遲元素明時處理兩N乘N矩陣。 .如申請專利範圍第15或16項的方法，其是藉由一使用者設備 而執仃，用於還原來自以一接收向量的方式被接收到的複數資 料信號之資料。 、 25. 如申請專利範圍第15或16項的方法，其是藉由_基地站而執 行，用於還原來自以一接收向量的方式被接收到的複數資料信 號之資料。 26. —種用以決定一 :^乘!^矩陣之一克洛斯基因數的方法該方法 包含： 提供一純量處理元素的陣列’其經配置為使得各處理元素 與該N乘N矩陣的一元素相關聯；以及 使用與該N乘N矩陣的一元素相關聯的各處理元素，以決 定該克洛斯基因數的一對應元素。 27.如申請專利範圍第26項的方法’其中各純量處理元素獨特與該 N乘N矩陣的一元素相關聯。 37 1325240 5請^_26或27項的方法，其中該陣列在複數階段 ，麟在各義巾，域理—過一 第26或27_杨㈣個矩陣在 3〇.歹=^，圍第28項的方法’其中多個w陣在該陣 k於权下—隨前，在該複 理所有該多個N__。 的P“又處 3^如申請專利範圍第30項的方法，其中對於 的各N乘N矩陣，在進 又N矩陣 儲存。 進入下认則’將各階段的一處理結果 兑一=於解出-線性方程式的方法，其藉由決 洛斯基因數以及將該決定的克洛斯基因數用於正向及逆 向替換用啸出該線性方程式，該方法包含·· 提供最多N個純量處理元素的一陣列，· 藉由該純量處理元素的陣列，接 素與該線性方程式，· 收來自該N乘N矩陣的元 使用各純量處理元素，僅執行減法與乘 ， 克洛斯基因數以及執行正向及逆向替換； # ’以、、定該 使關合至該陣列的一平方根裝置以執行平方根運瞀以 及使用輕合至該陣列的-除法裝置以執贿法運算以:定該 38 1325240 克洛斯基因數；以及 輸出來自該純量處理元素的該線性方程式之結果。 33. 如申請專利範圍第32項的方法，其中該陣列的各純量處理器處 理該N乘N的一對角線，以決定該克洛斯基因數並且執行正向 及逆向替換。 34. 如申請專利範圍第33項的方法，其中該N乘N矩陣具有一頻 帶P並且P小於N，其中僅提供p處理元素於該處理元素的陣 _ 列。 35. 如申請專利範圍第34項的方法，其中一查值表係用於執行平方 根及倒數運算。 • 36.如申請專利範㈣33項的方法’其中_查值表制於執行平方 根及倒數運算。 37. 如申請專利範圍第33項的方法，其是藉由—接收器而執行，用 於還原來自以一接收向量的方式被接收到的複數資料作號之次 • 料。 。儿貝 38. 如申請專利範圍第33 _方法，其是藉由一使用者設備而執 行，用於還原來自以一接收向量的方式被接收到的複數資料作 號之資料。 ° 39. 如申請專利範圍第33項的方法，其是藉由一基地站而執行，用 於還原來自以一接收向量的方式被接收到的複數資料信號之， 料。 貝 39 4〇.一種用於決定-N乘N矩陣之-克洛斯基因數以及將該決定的 克洛斯基因數用於正向及逆向替換用以解出一線性方程式的方 法’其包含： 提供最多N個純量處理元素的一陣列； 藉由該純量處理元素的陣列，接收來自該N乘N矩陣的元 素； 使用各純量處理元素，以決定該克洛斯基因數以及執行正 向及逆向替換； 使用僅輕合至該純量處理器之一的一裝置，以執行一有效 的平方根與倒數運算，以及不使用該陣列的任何純量處理器以 執行一有效的平方根與倒數運算；以及 輸出來自該純量處理元素的該線性方程式之結果。 41. 如申請專利範圍第4〇項的方法，其中該陣列的各純量處理器處 理該N乘N的—對角線，以決定該克洛斯基因數並且執行正向 及逆向替換。 42. 如申請專利範圍第4〇或41項的方法，其中該1^乘^^矩陣具有 頻▼P並且P小於N，其中僅提供P處理元素於該處理元素 的陣列。 43. 如申請專利範圍第42項的方法，其中一查值表係用於執行平方 根及倒數運算。 44. 如申請專利範圍第4〇或41項的方法，其是藉由一接收器而執 4C 行，用於還原來自 、 一接收向量的方式被接收到的複數資料信 浼之資料。 45=請專利軸4()或41 _方法，其是藉由一使用者設備 ▲"崎還原來自以—接收向量的方式被接收到的複數資 料信號之資料。 ❹申__㈣或41項的方法，其是藉由—基地站 订’用於還原來自以一接收向量的方式被接收到的複數資 號之資料。 、寸1s