最大相似度檢測方法與系統的製作方法

2023-08-07 10:15:36

專利名稱：：最大相似度檢測方法與系統的製作方法
技術領域：
：本發明涉及一種無線通訊技術，特別是涉及一種最大相似度檢測方法與系統。
背景技術：
：近年來，無線通訊需求快速增長，在頻譜有限的情形下，探討高頻譜效益的通訊技術便因應而生。多輸入多輸出(MultipleInputMultipleOutput,簡稱為MIMO)是近年來最熱門的技術，其借著在傳送端架設多個天線，在同頻段中同時傳送多份數據來提高傳輸效率。顯然地，這些傳送信號將會在接收端互相干擾，但若同樣在接收端架設多個天線進行接收，便可進行信號分離與檢測。MIMO技術至今已被廣泛使用在新興技術規格中，例^口，電才幾及電子工考呈師學會(InstituteofElectricalandElectronicEngineers，簡稱為IEEE)802.11n以及802.16e。圖1示出了典型的MIMO傳收信號模型。假設傳送端有M根傳送天線，接收端有M根接收天線，則其基頻等效信號模型為其中，complexformulaseeoriginaldocumentpage5fi代表接收端的噪聲，A代表信道的轉換函數，^表示第y個傳送天線到第/個接收天線的信道響應。在基頻信號模型中，"s、6、^都是複數向量，其可以轉換成實數信號模型，該實數信號模型表示為y=Hs+n亦即，formulaseeoriginaldocumentpage6MIMO接收機的任務便是根據接收信號y檢測出傳送信號s。一般而言，最大可靠度檢測(MLD)被視為最佳的訊號檢測方法，但其複雜度與傳送端天線個數(M)以及信號調變階數(MJ呈指數增加。例如，傳送端有4個天線，即信號s含有4個符元，每個符元採用64-QAM調變，則接收端必須針對644種可能逐一檢測才能找出最大可靠度(MaximumLikelihood,簡稱為ML)的解。因此，許多複雜度較低的次佳(Sub-optimal)算法(例如縱式貝爾實驗室多層次空-時技術(VerticalBellLaboratoriesLayeredSpace-Time,簡稱為V陽BLAST)、強制歸零(ZeroForcing,簡稱為ZF)、最小均方誤差(MinimumMeanSquareError,簡稱為MMSE)...等等)被發展出來。然而，一種稱為球狀解碼(SphereDecoding,簡稱為SD)的方法使得MLD的複雜度可以大幅降低。以實數信號模型為例，SD能夠低複雜度的關鍵在於，SD則允許檢測器逐一計算部份符元的部份成本函數，因此可以及早排除一些已經明顯超出成本限制的信號組合。以下以數學方法說明MLD基本上可以轉換成另一個等效形式formulaseeoriginaldocumentpage6其中符號"八〃表示所有符元向量s的集合，而llH(s'^"U是轉換後的成本函數。若將所有^4的集合稱為網格(lattice),則s可視為其對應網格點(LatticePoint)的坐標(Coordinates)。MLD便是搜尋所有可能的網格點坐標s,找出一個和H^距離(Norm)最小的網格點。因此，可將H^當作一個球心，當定義一個適當的半徑(Radius)r後，便可建立一個多維空間的抽象球面。MLD便是搜尋球面裡距離球心H§zf最近的網格點的坐標，如圖2所示。若再進一步化簡MLD的等效式，其可表示為formulaseeoriginaldocumentpage7R為一上三角矩陣(UpperTriangularMatrix)，可由QR分解(QRDecomposition)或查爾斯基因子分解(CholeskyFactorization)來耳又4尋。由於設定一個上限值一來限制搜尋範圍，則其成本函數formulaseeoriginaldocumentpage7由上列方程式可看出，整體歐式距離(EuclideanDistance,簡稱為ED)基本上是由M(=2tV,)個歐式距離增量(EuclideanDistanceIncrement,筒稱為EDI)^所構成，其中，formulaseeoriginaldocumentpage7而累積到第m層的部份歐氏距離(PartialEuclideanDistance，筒稱為PED)可以定義成formulaseeoriginaldocumentpage7由於《只與k""'+"…^]有關，因此很容易可以將SD的搜尋過程轉化成遞歸的(Recursive)樹狀搜尋(TreeSearch)結構，如圖3所示。此外，根據Schnorr-Euchner(SE)列舉法，定義'一如下formulaseeoriginaldocumentpage7當搜尋至第m層時，SE會優先對^+'硬式決策後的點^"'+'"^(^"'+'搜尋，之後會以^"'+'為中心呈Z型(Zigzag)來列舉節點。如此可確保每一層所列舉的節點順序，其EDI是由小到大排列的，因此SE可加快平均搜尋速度。如上所述，球狀解碼中的PED是隨著搜尋的深度而單調增加，且階層的搜尋順序影響解碼效率甚大。
發明內容基於上述目的，本發明實施例披露了一種最大相似度檢測方法。處理接收數據以取得多個參數，並設定一初始半徑。根據所述參數執行一搜尋程序，並以一限制函數決定每一階層部份歐氏距離的上限值，依據所述上限值判斷一子網格是否超過一搜尋範圍。本發明實施例還披露了一種最大相似度檢測系統，包括一前處理單元、一組成單元與一搜尋單元。該前處理單元用以處理接收數據以取得多個參數，並設定一初始半徑。根據所述參數執行一搜尋程序，並以一限制函數決定每一階層部份歐氏距離的上限值，依據所述上限值判斷一子網格是否超過一搜尋範圍。本發明實施例還披露了一種通訊裝置，包括一處理單元，其用以處理接收數據以取得多個參數，並設定一初始半徑。根據所述參數執行一搜尋程序，並以一限制函數決定每一階層部份歐氏距離的上限值，依據所述上限值判斷一子網格是否超過一搜尋範圍。圖1示出了典型MIMO數據模型的示意圖。圖2示出了球狀解碼的示意圖。圖3示出了深度優先搜尋的示意圖。圖4示出了根據階層排序並利用QR分解或Cholesky分解產生上三角矩陣的示意圖。圖5示出了虛擬程序代碼(Pseudocode)的示意圖。圖6示出了歐式距離增量的示意圖。圖7示出了本發明實施例的最大相似度檢測方法的步驟流程圖。圖8示出了改善的解碼延遲的示意圖。圖9示出了本發明實施例的部份歐氏距離(PED)限制函數(ConstraintFunction)的示意圖。圖10示出了利用本發明方法的DF-SE而有較高的比例可完成搜尋的示意圖。圖11-14示出了在2x2、3x3與4x4情形下，本發明的BER與理論上最佳BER的比較圖。圖15-17示出了利用本發明方法大量減少節點搜尋數(複雜度)的統計圖。圖18示出了習知方法與本發明方法間差異的示意圖。圖19示出了決定信道排序索引向量與產生上三角角矩陣R的實施方法示意圖。圖20示出了本發明實施例的最大相似度檢測系統的架構示意圖。附圖符號說明610~組成單元630前處理單元650~搜尋單元H矩陣R上三角矩陣具體實施例方式為了使本發明的目的、特徵、及優點能更明顯易懂，下文特舉較佳實施例，並結合附3至圖20詳細說明。本發明說明書提供不同的實施例來說明本發明不同實施方式的技術特徵。其中，實施例中的各組件的配置是為了說明之用，並非用以限制本發明。且實施例中圖式標號的部分重複，是為了筒化說明，並非意指不同實施例的間的關聯性。本發明實施例披露了一種最大相似度檢測(MLD)方法與系統。為了降低搜尋MLD的複雜度，球狀解碼(SD)方法被引入MIMO中。SD是先限定一個合理的半徑r,並且只搜尋半徑為r的球面裡的網格點。然而，若把原來前文所述的H矩陣的行向量適當交換(等效於將傳送天線的索引(Index)順序交換)，則可在不影響搜尋結果的情形下大幅降低搜尋的時間。另一方面，若SD搜尋的球面半徑越小，包含的網格點便越少，因此搜尋速度可以越快。再者，由於搜尋的過程中，每往下一層搜尋，PED的值是單調增加的，這表示越上層的PED越小於r2。因此，可以將越上層的子網格(Sub-lattice)限制在越小的球面裡，如此便可更進一步加快搜尋速度。如上所述，本發明藉由對H矩陣的行向量交換與設定PED限制條件以加快搜尋速度。深度優先的算法可搭配Schnorr-Euchner列舉(Enumeration)來達到相當有效率的搜尋，其原理是在每一層只往下拜訪讓EDI最小的子節點，當搜尋至最底層後，若所得的ED小於目前r2,則將一更新為ED。當搜尋至最底層或搜尋至某層的PED已經大於—時，便停止往下搜尋，轉而往上搜尋讓上一層EDI次小的母節點，如圖3所示。DF的一個特點是當每找到一個距離球心更近的網格點，球面半徑就可以縮成該網格點與球心的距離。藉由樹狀搜尋的觀點來解釋SD,可知若能在越上層就終止某節點的後續搜尋，則可省下的搜尋量越多。因此，本發明在SD求取上三角矩陣R的QR分解過程中輔以排序，使得上三角矩陣R的越右下角的對角元素越大越好(由於上三角矩陣R的對角元素相乘必為定值，所以等效於左上角的元素越小越好)，如圖4所示。搜尋樹越上層對應到越右下角的《"'，由於complexformulaseeoriginaldocumentpage10當右下角的；"'越大時，^'l越有機會變得較大，因此在上層的PED就越容易超過給定的球面限制，亦即可以越快終止後續的搜尋。此外，在一個完整的搜尋路徑中，PED—定是從上層到下層逐漸增加的，因此可以用較小的球面半徑來限制較上層的PED，如此一來便可將上層節點搜尋範圍縮小，大幅減少可能的搜尋路徑。為了交換H矩陣的行向量，可根據通道矩陣行向量的長度大小來進行排序，長度越小的行向量排在矩陣H的越左邊。藉由改良D.Wubben等人提出的算法"Efficientalgorithmfordecodinglayeredspace-timecodes"可求得滿足上述需求的三角矩陣R,並且保證QR分解後的《m—定是所有排列方法中最大的。為了達到減少總搜尋路徑的目的，現有技術利用圖5中的偽碼(PseudoCode)來實現。參考圖5，利用修正項Fk來調整各層PED上的半徑限制，故同樣能夠使PED的限制值在越上層越小。此修正值的增量(Fk+1-Fk)與噪聲功率以及R的對角元素rk,k成正比，即必須事先估算噪聲功率。然而，經由模擬發現EDI與rk，k(等同於偽碼中的lk,k)幾乎沒有強烈的比例關係，如圖6所示。此外，在DF(depth-first)搜尋過程中，—會逐漸縮小，但此修正項Fk並不能隨之進行調整。因此，本發明是根據目前的—對維度越小的子網格分配半徑越小的子球面，此分配函數可事先定義，並可依系統或應用需求做適當調整。借著這樣的方法，不需要事先知道噪聲功率或是上三角矩陣R的對角元素，此外子球面半徑可隨搜尋過程逐漸縮小，可更快地完成搜尋。圖7示出了本發明實施例的最大相似度檢測方法的步驟流程圖，其說明如下。而本發明與已知方法的差異可參考圖18。為了方便說明，以下提出一個DF的具體實施例，但其並不用以限定本發明。用SD的樹狀搜尋算法來實現MLD時，需要先算出一個強迫歸零(Zero-forcing)的向量(步驟S701)。獲得此向量的作法為^=(H"H)ft"。當iV產A^且S為一滿秩(FullRank)矩陣時，可簡化成=6,。當對§"作硬式決策(HardDecision)後，可得到一組初始解=slice(U(步驟s702)。如上文所述，將1^-^1|2當作一初始r2,或者利用DF搜尋到的第一個解的ED來當作初始r2(步驟S703)。另外，決定一信道排序索引向量(ChannelOrderingIndexVector)，並且利用圖19所示的流程求得一個上三角矩陣R，以使得HHl^RHR(步驟S704),其中H的行向量已經過排序索引向量進行排序。就上三角矩陣R來說，其對角元素能儘量符合左上角的值較小，右下角的值較大的需求，故可改善解碼延遲，如圖8所示。在決定一後，根據定義好的PED限制函數cww/ra/"fj^""/o"(m)將一乘以對應函數值，並取得各層的PED上限值(或視為包含子網格的子球面半徑)(步驟S705)。在接下來的搜尋過程中，利用一成本函數來檢視子網格的PED是否已經超出搜尋範圍(步驟S706),該成本函數如下所示上述限制函數的一個實施例如圖9所示。當搜尋到一較佳解時，便會得到一個更小的r2,各個子球面的半徑也會跟著縮小(步驟S707)。本發明實施例的最大相似度檢測方法決定搜尋樹的階層排序，並且根據成本函數與分配函數來搜尋階層中的節點，以避免無謂的搜尋，其中該搜尋樹的階層排序系藉由產生強迫歸零矩陣與QR分解中的排序程序來決定。該成本函數表示一網格點到一^^心的距離，而該分配函數則有助於減少在較低維度的子網格的搜尋時間。此外，該分配函數可為一單調增加函數或任何輸出值不大於1的函數。本發明實施例的最大相似度檢測方法令解碼延遲分布有大幅提升與改善。在要求的解碼延遲限制下，利用本發明方法的DF-SE有較高的比例可以完成搜尋，如圖IO所示。另外，本發明提出的限制式PED作法，其位錯誤率(BitErrorRate,簡稱為BER)效能在2x2和3x3的情形下幾乎不會退化，而在4x4的情形下也只在64-QAM時有孩i乎其孩i的退化，如圖11-14所示。此外，利用本發明方法的DF-SE在複雜度上有相當明顯的減少，如圖15-17所示。圖20示出了本發明實施例的最大相似度檢測系統的架構示意圖。本發明實施例的最大相似度檢測系統包括一組成單元610、一前處理單元630與一搜尋單元650。組成單元610取得SNR、RTC、M、A^、M。…等參數來決定作用於每一階層的限制函數。前處理單元630根據一強迫歸零向量計算一初始解與一初始半徑，藉由QR分解產生一上三角矩陣，並且取得一排序索引向量。搜尋單元650搜尋一較佳解以更新球狀半徑r，並根據PED函數將一乘以一對應的比例因子，以取得每一層PED的上限值，並且利用該上限值判斷一子網格是否超出搜尋範圍。根據一較佳解得到的較小的—可減少在後續搜尋時每一子球狀表面的半徑。下文將"^兌明階層排序的詳細實施流程。在一開始求強迫歸零解(^"『H)H、)的過程中，可先利用運算過程中的中間產物來判斷排序後的矩陣H的第一個與最後一個行向量應該為何。基本上是以HHH對角元素值最小的索引值來選擇第一個行向量。例如，考慮一個矩陣H為複數的型式formulaseeoriginaldocumentpage12。可以發現第四個對角元素4.4262最小，因此選擇矩陣H的第四個行向量當作排序後的第一個行向量(first—layer—idx=4)。接著計算(HHH)":0.194-0.17950駕4Z0.1166+0.1116,.0.0070+0.1048i'-0.1795+0.0784Z0.3646-0.2322-0.1728'.-0.0858-0.1532,'0.11660.1116''0.0070隱0.1048/-0.2322+0.1728!'-0.0858+0.1532!.0.6632-0.1372+0.1180i-0.1372-0.1180Z0.5560可以發現第一個對角元素0.194最小，因此選擇矩陣H的第一個行向量當做排序後的最後一個行向量(last—layer—idx-l)。值得注意的是，若矩陣H是經由複數矩陣轉換而成的實數矩陣，則其維度變成兩倍，且對角元素會有重複現象，當最小的對角元素有兩個時，可任挑其中一個對角元素。借著這樣的方法，挑出的第一個和最後一個行向量，一定是在所有排序結果中讓求得的上三角矩陣的最左上角的對角元素值最小的，同時也是讓最右下角的對角元素值最大的。在決定出第一個和最後一個行向量後，借著排序QR分解(sorted一QRD)來決定其它階層順序的排列，其過程可在Gram-Schmidth或是HouseholderQRD算法過程中對行向量長度輔以排序來讓上三角矩陣R的對角元素儘量達到越右下越大的效果。如此一來，上層的階層有較大的機會累積到較大的PED值，因此在上層就超出球面的機會越大，意即不良的訊號組合就越早被排除掉。接著，對^作硬式決策後可得到一組初始解^=51^(^)。可以將lHd-Dl當作一初始限制半徑r,而在DFS中，r也可以待搜尋到最下層後再決定。因此，在前置處理過程中將可得到初始的球半徑r,上三角矩陣R、通道矩陣行向量的排序索引向量p以及零強迫解§"。SD的解碼過程可視為樹狀搜尋，維度為n的任一子網格(Sub-lattice)皆有一串深度為n的節點組合(或視為深度為n的路徑)與之對應。深度優先的搜尋過程是先以下層中讓PED增量(也就是EDI)最小的那個節點優先搜尋，讓第m層PED增量最小的節點為其中，formulaseeoriginaldocumentpage13持續往下搜尋到最下層時，可以得到初始(或更新)的一。.有了r2,便可根據定義的限制函數，依照比例分配到不同層當作各層的半徑限制。傳統方法在各層的搜尋過程仍以r2當做衡量是否超出搜尋球體的依據。然而，藉由限制函數可以在不同階層用不同的球體大小來限制搜尋範圍，當某一節點超出限制函數所分配的半徑大小，便終止該節點後續的搜尋。需注意到，在搜尋過程中，當有新的一被計算出，各層的限制半徑便可一併隨著更新，但各層限制半徑並非一定要一併隨著更新，且限制函數也不必維持固定。本發明實施例的最大相似度檢測方法可應用於一通訊裝置(未顯示)中。該通訊裝置可包括一處理單元(未顯示)，用以執行該最大相似度檢測方法。此外，該通訊裝置可為一移動臺(MobileStation)、一基地臺(BaseStation)、一存取點(AccessPoint)、一便攜裝置(PortableDevice)或是一桌上型計算機(Desktop),而該處理單元可為一數字訊號處理(DigitalSignalProcessing,簡稱為DSP)單元或一專用集成電路(ApplicationSpecificIntegratedCircuit,簡稱為ASIC)。本發明更提供一種記錄介質(例如光碟片、磁碟片與抽取式硬碟等等)，其是記錄一計算機可讀取的權限籤核程序，以便執行上述的最大相似度檢測方法。在此，儲存於記錄介質上的權限籤核程序，基本上是由多個程序代碼片段所組成的(例如建立組織圖程序代碼片段、籤核窗體程序代碼片段、設定程序代碼片段、以及部署程序代碼片段)，並且這些程序代碼片段的功能對應到上述方法的步驟與上述系統的功能方塊圖。雖然本發明已以較佳實施例披露如上，然其並非用以限定本發明，本領域技術人員在不脫離本發明的精神和範圍的前提下可作各種的更動與潤飾，因此本發明的保護範圍以本發明的權利要求為準。權利要求1.一種最大相似度檢測方法，包括下列步驟處理接收數據以取得多個參數；設定初始半徑r；根據限制函數決定每一階層PED的上限值；以及根據所述參數執行搜尋程序，並依據所述上限值判斷子網格是否超過搜尋範圍。2.如權利要求1所述的最大相似度檢測方法，其中，處理該接收數據的步驟還包括下列步驟計算強迫歸零向量；對通道矩陣H執行排序與QR分解產生上三角矩陣R;以及取得信道排序索引向量。3.如權利要求1所述的最大相似度檢測方法，其中，決定該初始半徑r的步驟還包括下列步驟決定初始解，並根據成本函數計算該初始半徑r。4.如權利要求3所述的最大相似度檢測方法，該初始解可對該強迫歸零向量執行硬式決策來取得。5.如權利要求3所述的最大相似度檢測方法，該初始解可為搜尋過程中第一次取得的候選解。6.如權利要求2所述的最大相似度檢測方法，其中，經過排序的H經QR分解後所得的該上三角矩陣R的左上至右下的對角元素比未經過排序的更趨於由小排到大。7.如權利要求1所述的最大相似度檢測方法，其中，每一層的PED上限值表示限制於每一對應維度的子網格的子球狀半徑。8.如權利要求2所述的最大相似度檢測方法，其還包括計算該強迫歸零向量，同時決定矩陣的第一與最後行索引，使得排序後的矩陣其QR分解後的上三角矩陣R的左上對角元素為所有可能排序結果中的最小者，而該上三角矩陣R的右下對角元素為所有可能排序結果中的最大者。9.如權利要求1所述的最大相似度檢測方法，其中，該PED限制函數為根據樹深而單調增加的函數。10.如權利要求1所述的最大相似度檢測方法，其還包括下列步驟當搜尋至最低階層時，自該較佳解取得更新半徑r;以及利用該限制函數更新各階層PED上限值，使得較小維度的子網格能限制在較小子球面內。11.如權利要求IO所述的最大相似度檢測方法，其中，當取得該更新半徑r時，可調整該限制函數。12.—種最大相似度檢測系統，包括前處理單元，其用以處理接收數據以取得多個參數，並且決定初始半徑r;以及搜尋單元，其用以根據限制函數決定每一階層PED的上限值，根據所述參數執行搜尋程序，並依據所述上限值判斷子網格是否超過搜尋範圍。13.如權利要求12所述的最大相似度檢測系統，其還包括組成單元，用以決定應用至每一階層的該限制函數。14.如權利要求12所述的最大相似度檢測系統，其中，該前處理單元還包括計算強迫歸零向量；對通道矩陣H執行排序與QR分解產生上三角矩陣R;以及取得信道排序索引向量。15.如權利要求14所述的最大相似度檢測系統，其中，該前處理單元還包括決定初始解，並根據成本函數計算該初始半徑r。16.如權利要求15所述的最大相似度檢測系統，該初始解可對該強迫歸零向量執行硬式決策來取得。17.如權利要求15所述的最大相似度檢測系統，該初始解可為搜尋過程中第一次取得的候選解。18.如權利要求14所述的最大相似度檢測系統，其中，經過排序的H經QR分解後所得的該上三角矩陣R的左上至右下的對角元素比未經過排序的更趨於由小排到大。19.如權利要求12所述的最大相似度檢測系統，其中，每一層的PED上限值表示限制於每一對應維度的子網格的子球狀半徑。20.如權利要求14所述的最大相似度檢測系統，其還包括計算該強迫歸零向量，同時決定矩陣的第一與最後行索引，使得排序後的矩陣其QR分解後的上三角矩陣R的左上對角元素為所有可能排序結果中的最小者，而該上三角矩陣R的右下對角元素為所有可能排序結果中的最大者。21.如權利要求12所述的最大相似度檢測系統，其中，該PED限制函數為根據樹深而單調增加的函數。22.如權利要求12所述的最大相似度檢測系統，其還包括下列步驟當搜尋至最低階層時，該前處理單元自該較佳解取得更新半徑r;以及利用該限制函數更新各階層PED上限值，使得較小維度的子網格能限制在較小子球面內。23.如權利要求22所述的最大相似度檢測系統，其中，當取得該更新半徑r時，可調整該限制函數。24.—種通訊裝置，包括處理單元，其用以處理接收數據以取得多個參數，並設定初始半徑r,根據所述參數執行搜尋程序，並以限制函數決定每一階層部份歐氏距離的上限值，依據所述上限值判斷子網格是否超過搜尋範圍。25.如權利要求24所述的通訊裝置，其中，該通訊裝置可為移動臺、基站、存取點、便攜裝置或是桌上型計算機。全文摘要一種最大相似度檢測方法。處理接收數據以取得多個參數，並設定一初始半徑。根據所述參數執行一搜尋程序，並以一限制函數決定每一階層部分歐氏距離的上限值，依據所述上限值判斷一子網格是否超過一搜尋範圍。文檔編號H04B7/02GK101207404SQ200710162150公開日2008年6月25日申請日期2007年12月21日優先權日2006年12月21日發明者丁邦安,許仁源,謝雨滔,陳慶鴻申請人:財團法人工業技術研究院