虛擬隨機序列中決定初始化狀態之方法及裝置的製作方法

2023-05-27 23:26:21

專利名稱：虛擬隨機序列中決定初始化狀態之方法及裝置的製作方法
技術領域：
本發明是關於一種用以一位移伺服器排列由一給予之初始狀態決定結束狀態之方法及裝置，該結束狀態具有n位且迭代N次，該給予之初始狀態具有n位。本發明亦關於虛擬隨機序列之生產，其系透過N位位移，且尤其是用以作為CDMA基礎之行動無線系統中之展開序列(CDMA碼分多重存取)。
在行動無線系統中，由基地臺或是行動臺所產生的訊號在被發送前會被修改幾次，為了在行動無線網絡中更能分辨不同胞元，CDMA系統使用展開序列，以每一使用者在每一邏輯頻道系被分配一值為-1和+1的不同序列，被分配至個別使用者的信號能因此被接收，且能與其它信號分離，且能被重建，此即視為碼分多重存取(CDMA)。相反地，在TDMA(時分多重存取)系統中的信號系以時間相互分離。重要的CDMA傳輸系統係為IS-95系統，其系用於美國和歐洲系統，且已經列入第三代夥伴計畫中，UMTS所使用編碼的詳細說明可於1999年發行的「3GPP展開和調變(FDD)」第三代夥伴計畫TS 25.213找到。
所有被使用的展開碼可被追溯回位值為0和1的序列，舉例來說，這些序列可為所謂的虛擬隨機序列，其系由清晰的自動校正和交叉校正特徵來識別。當一個虛擬隨機序列系以如同一個位值為0和1序列的理論表現來表示的話，該展開序列實際上是使用值為+1和-1的序列表示，在每一例中該位值0在實際展開序列中會並成+1的值。
虛擬隨機序列系藉由一迭代法則定義，其系該迭代於主體GF(2)中執行，亦即於該計算主體中以元素0和1執行。虛擬隨機序列的理論基礎及該清楚的迭代規則係為關於該主體GF(2)之不可約質數多項式理論，這個理論的說明及其於行動無線領域的應用能，舉例來說，於J.S.Lee，L.E.Miller所著，Boston/London之Artrch House在1998年所出版之「CDMA系統工程手冊」中找到，尤其是第六章。
每一個別虛擬隨機序列系由該初始化狀態獨特地定義，亦即藉由該序列的第一個值，以及藉由用以迭代程序的多項式。在本例中，於行動無線應用中之該多項式以及由此之迭代規則不是定義給整個網絡，要不然就是一小部分不同的多項式大體上系用以，舉例來說，於UMTS系統中所謂的變頻碼之定義。每一個別虛擬隨機序列之該初始化狀態系不同，且系頻繁地以編碼數目來定義。
因次關聯的虛擬隨機序列必須於一基地臺或是於一行動臺產生，其係為了一個給定的編碼數目及一各同樣地預設的迭代規則。當傳輸時，所產生之該序列必須用以編碼該信號，另一方面，在接收模式方面，虛擬隨機序列的使用能夠用以辨別該所需信號及分辨來自其它使用者的信號。如果已知該搜尋信號之初始值，另一個序列值便能藉由簡單緩存器的運算產生，而不會有任何困難，在該過程中，注意力一方面必須集中在欲被發送的信息及接收之間的同步化，另一方面，則在欲被發送的信息及重建序列的同步化。
然而，在不同的行動無線應用方面，該序列的開始及緩存器的初始狀態並非已知，這種情況就是，舉例來說，當該編碼系準備於一不同於該信號發送本身的時間開始時，這種情況會於在UMTS中所謂的壓縮模式中發生。有關於該模式之更多信息可於1999年出版之「3GPP實體頻道及傳輸頻道映至實體頻道(FDD)」第三代夥伴計畫TS 25.211中找到。
當該編碼數目並未直接定義該初始化緩存器內容，而是藉由於使用之該虛擬隨機序列中一特定數目之位定義一位移時，該序列之開始及該緩存器之初始化狀態亦為未知的。舉例來說，當一信號繫於UMTS中之行動部分接收，該編碼數目N系被定義，其系根據3GPP標準，如同一虛擬隨機序列由N位位移。有關該編碼數目及關聯之虛擬隨機序列之間的關係之相關信息尤其系包含於1999年發行的「3GPP展開和調變(FDD)」第三代夥伴計畫TS 25.213第5.2章節中。
為了計算該情況之該緩存器之該初始化狀態，其中序列系遭受一N位額外的位移或是額外的偏移，該序列可於該原始開始時間激活，且接著能被迭代N次。該所需由N位位移之之序列能以此方式達成。
這個解決方式系被根據習知的前述系統所採用，在輸出該所需的虛擬隨機序列之前，該位移緩存器結構之該緩存器內容就被迭代N次了，輸出該由N位位移之實際虛擬隨機序列之程序並不會開始，直到該先前之迭代步驟已經被執行。這個程序的缺點系在於，所需運算之數量與所需位移N之大小成比例，所需運算之數量因此會有不同，如同該資料於該時間之一函式，而這會使得控制整個時間序列變得更困難。另一個缺點系在於當所需的位移N很大時，計算複雜度及需求時間的總量會變得非常的大，於UMTS系統之接收期間，於該行動臺中該偏移發生於範圍為N＝0至N＝262142間，因為該所需虛擬隨機序列之產生必須等待，直到該所需偏移達成，這表示於發送和接收中會有一不可接受的延遲。
因此本發明之目的在於以一直接方式計算一給定初始化狀態之該結束狀態，迭代N次數，及/或由N位位移之虛擬隨機序列。
本發明之目的之達成系藉由一種用以決定一結束狀態之方法，其系具有n位和迭代N次，如同權利要求第1項所主張，及藉由一種裝置用以決定決定一結束狀態之方法，其系具有n位和迭代N次，如同權利要求第14項所主張，並藉由該裝置的使用以產生一展開序列，如同權利要求第20項所主張。
根據本發明之方法，其系用以一位移伺服器排列由一給予之初始狀態決定結束狀態之方法，該結束狀態具有n位且迭代N次，該給予之初始狀態具有n位。該迭代規則系藉由一特徵多項式給予f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn其中c1，c2，...，cn-1∈{0；1}於第一步中，該多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn之決定系藉由如下多項式之係數的反映f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn這些係為剩餘組[xN+j-1]mod f*之典型，次數小於n系接著被決定為j＝1，...，n。該初始化狀態之位序列系接著由一矩陣相乘，該矩陣之j-th列及j-th行系藉由剩餘組[xN+j-1]mod f*之典型之係數給予，其中j＝1，...，n。
根據本發明之方法第一次能明確地計算一位移緩存器配置之狀態，其系藉由一特徵多項式定義，且在執行N迭代之後獲得。在習知技術中，該位移緩存器之N迭代必須預先執行以便決定該結束狀態，因為，在某些案例中，上至N＝262142之預先迭代必須被執行，以便製造行動無線除拴之不同的所需編碼，計算該結束狀態、迭代N次之能力明確地省下非常多的時間。本發明提供該能力已產生一特定編碼序列，透過該偏移N位移，差不多沒有任何延遲。
決定於剩餘組[xN+j-1]mod f*中典型之程序，其系次數小於n，能藉由快速算法執行，以在一非常短的時間剩餘組運算，舉例來說，系藉由平方和乘法演算。在本例中，該計算複雜度和所需的時間以決定於該剩餘組[xN+j-1]mod f*之典型系對數地與N相關，這表示說該編碼序列之所需偏移位移有一對數關係式。當執行N預先迭代時，如同在習知技術中所必須一樣，該計算複雜度和所需的時間以執行該預先迭代會隨N線性增加，由於與N之對數關係式，根據本發明之解決方法會造成所需計算大大地縮短，尤其是N值很大時。
由位移緩存器配置所產生之虛擬隨機序列，尤其對於行動無線傳輸之資料封包之發射器末端編碼及接收器末端解碼更是需要。依照習知之解決方法，執行N預先迭代之需要導致於傳輸和接收過程中有不可接受的延遲。在本例中，類似此類的延遲能以根據本發明之解決方法在結束狀態避免，其系迭代N次，系藉由一矩陣乘積決定，且不需要如過去一般的迭代。
透過N位位移之編碼序列系根據3GPP標準由編碼號碼N表示，本發明因此能產生所有於3GPP標準行動無線傳輸所定義之編碼，而無須浪費任何時間。當編碼信號系由無線傳輸，一情況也會發生於該編碼意圖於不同於其自身之開始時間開始，舉例來說，這情況會發生於UMTS行動無線標準中所謂的壓縮模式時，於壓縮模式中信號編碼之該位移緩存器配置之正確的初始化狀態，能因此由根據本發明之方法產生，其能即刻地產生一位移緩存器配置狀態，其系已經迭代N次。
本發明適用於由一具有回饋之時脈位移緩存器配置所產生編碼序列之所有應用，在本例中，於該位移緩存器中所提供之回饋系藉由下列特徵多項式定義f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn該位移緩存器內容，其具有n位，系藉由具有位之一時脈信號透過該位移緩存器位移，其系位移出該位移緩存器配置，回饋至該位移緩存器配置之輸入，此類之位移緩存器配置系用以編碼和解碼目的。根據本發明之之方法對於一給定該位移緩存器配置之初始化狀態，能夠計算在N次位移運算之後達成之結束狀態，或是在N時脈脈衝後被用於該位移緩存器之結束狀態。
根據本發明之結束狀態之計算需要一矩陣之計算，以及藉由該矩陣該初始化狀態之乘積，該矩陣元素之計算，以及該矩陣乘積執行之過程於本例中系藉由一處理器執行，尤其是藉由一數位訊號處理器，該計算之結束狀態能接著用無該位移緩存器配置之初始化，其系以硬體之形式，本發明能可靠地決定該編碼產生之初始化狀態之不同需求，其僅需些許之計算。
本例中，剩餘組[xN]mod f*，[xN+1]mod f*，...，[xN+n-1]mod f*之典型之優勢在於每一皆藉由一適當之算法明確地計算，尤其是藉由一平方和乘積算法。對於Monomen之剩餘組[xm]mod f*之計算，其中m係為一自然數，不同算法會有一範圍，每一算法產生該剩餘組之典型之係數，其次數系小於n。本例中執行這些算法計算複雜度及所需時間端示於m之對數，所需之該矩陣元素以執行根據本發明之方法能因此快速地被產生，即便N值非常的大。
在本例中，使用平方和乘積算法尤其具有優勢，基於在剩餘組[x]mod f*中之典型，[xm]mod f*之典型能非常快速地被計算，其系藉由使用一平方和乘積法，其中m係為一自然數。如此類之平方和乘積算法系明確地於本專利申請之說明書中描述，該算法僅包含幾行，能輕易地執行且產生可靠的結果，其系在剩餘組[xm]mod f*中典型之係數。
根據本發明之一較佳實施例，在該剩餘組[xN]mod f*該典型僅藉由一適當的算法明確地計算，尤其是藉由一平方和乘積算法。相對地，該剩餘組[xN+j-1]mod f*之典型，其中j＝2，...，n系藉由該剩餘組[xN]mod f*之典型之係數以(n-1)迭代計算獲得。
取代必須決定[xN+j-1]mod f*之典型之矩陣中的所有N列，該矩陣系藉由使用一平方和乘積算法所決定，在本發明知本實施例之平方和乘積算法系僅於矩陣中之第一列執行，於維持該矩陣之(n-1)列中該矩陣元素系接著由(n-1)次迭代計算這些係數產生，於第(j+1)列之矩陣元素能總是由第j列之矩陣元素所決定。此步驟在呼叫該算法n次期間之優勢係為決定矩陣元素之過程之計算更簡單化，計算步驟之數量以決定該矩陣元素更進一步減少，以致於該結束狀態，其已經迭代N次，能於一甚短時間內計算。
本例中，該剩餘組[xN+j-1]mod f*之典型的優勢，其中j＝2，...，n，系在於可藉由MSRG(模數位移緩存器產生器)型式之一位移緩存器配置之(n-1)次迭代計算獲得，其系來自該剩餘組[xN]mod f*之典型之係數，其系以該位移緩存器配置之迭代規則，該配置支給予系藉由特徵多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn為了由該剩餘組[xN+j-1]mod f*之典型之係數獲得該剩餘組[xN+j]mod f*之典型之係數，亦即由第j列取得第(j+1)列，這些係數之一計算迭代系被執行，對應於透過該MSRG型式之一位移緩存器位移這些係數，MSRG型式之位移緩存器之結構系藉由特徵多項式定義f*(x)＝1+cn-1·x+cn-2·x2+...+xn然而，該矩陣元素之迭代決定通常並不藉由以硬體形式之位移緩存器配置執行，而是純由軟體計算執行或是藉由一處理器，舉例來說一數位訊號處理器。
該第一矩陣列之明確地計算，亦即該剩餘組[xN]mod f*之典型之係數，以及該維持係數之迭代衍生，代表了計算所有矩陣元素最快和最簡單的方法。
其優點系在於具有n位且被迭代N次之該結束狀態，用以作為該初始化狀態以產生一被N位位移之虛擬隨機序列。由具有回饋且以一不可約多項式描述的位移緩存器配置所產生之一序列二進位值，系視為一虛擬隨機序列。一虛擬隨機序列先是由該位移緩存器配置之初始化狀態，及第二是由該位移緩存器配置特徵多項式來定義。如果該結束狀態，其已經以根據本發明之方法計算且已經迭代N次，系用來作為初始化狀態以產生一虛擬隨機序列，則這表示該虛擬隨機序列能於所需點立即開始，其系透過N位位移，進一步之序列值會接著以該初始化狀態為基礎產生。
其優點系在於具有n位且被迭代N次之該結束狀態，被作為初始化狀態寫入一具有n位移緩存器胞元之位移緩存器配置。已經迭代N次之結束狀態系藉由根據本發明之方法計算，且接著被寫入以硬體形式之該位移緩存器配置，因為已經迭代N次之已計算過之結束狀態，在執行N次迭代之後精確地對應於該位移緩存器配置之狀態，便有可能基於該計算之初始化狀態產生所需已經透過N位位移之虛擬隨機序列，而不再需要去分辨該狀態是否已經藉由該位移緩存器配置之N預先迭代或是計算達成。
其優點系在於該位移緩存器配置係為一SSRG型式之位移緩存器配置，其具有n位移緩存器胞元，且其結構系藉由特徵多項式給予f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn如果該位移緩存器配置係為硬體形式，該SSRG(簡單位移緩存器產生器)型式具有超越MSRG(模數位移緩存器產生器)之優勢系在於，SSRG型式之一位移緩存器胞元系直接位移到下一個位移緩存器胞元，另一方面，在MSRG型式中，XOR閘極系連接於個別位移緩存器胞元之間，且當其移動到下一個緩存器胞元時，這些修改了一位移緩存器之容量，該緩存器胞元容量在SSRG型式之位移緩存器中並不會被修改，且如此類之位移緩存器配置能因此以如同緩存器胞元之一數組之簡單方式執行。
由位移緩存器配置產生之虛擬隨機序列能於該位移緩存器配置之最後一個緩存器胞元選定，用以向前移動該位移緩存器配置容量之每一個時脈脈衝導致一個新的二進位值被寫入至該位移緩存器配置之最後一個緩存器胞元。因此，根據用以計時該位移緩存器配置之該時脈頻率，於該虛擬隨機序列中之該不同序列值系藉由讀取該位移緩存器配置中最後一個緩存器胞元而連續獲得。
其優勢系在於該方法能被用以於CDMA傳輸系統中產生一具有N位偏移之展開序列，尤其是於基於UMTS或是IS-95傳輸標準之CDMA傳輸系統中。可藉由位移緩存器配置產生之虛擬隨機序列及回饋尤其適用於行動無線系統，因為其關聯性對數用以作為CDMA基礎之系統的展開序列會非常出色，展開序列係為值為-1和+1的有限序列。當一資料序列被傳輸時，於該資料序列中的每一值會與該展開序列相乘，在該接收器末端，這些信號可接著被分辨，且可選擇性地被解碼，其系根據施用於其上的展開碼。
為了能於該接收器末端明確地解碼該展開碼編碼之信號，該使用之展開序列必須已經定義其自動關聯對數，除此之外，其必須能徹底地分辨使用不同展開序列編碼的信號。為了達成此點，用於信號傳輸之不同展開序列必須定義交叉關聯對數，虛擬隨機序列系皆適用作為自動關聯對數和交叉關聯對數，展開序列能因此藉由於CDMA傳輸系統中具有回饋之位移緩存器配置產生。
根據本發明之方法能用以產生初始化狀態，當輸出該展開序列時，其能以第n序列值而非以第一序列值開始，本發明因此允許該已經由N位位移之展開序列產生，亦即具有一N位偏移之展開序列。
根據本發明之一較佳實施例，該方法系用以產生不同擾碼，其繫於UMTS標準中定義。編碼密碼係為展開序列，尤其系用以分辨由不同基地臺傳輸至一行動臺之信號，根據本發明之解決方法系適用於擾碼之產生，其系由N位位移，亦即擾碼具有N位的偏移，根據本發明之解決方法能於ad-hoc模式下產生大量的不同擾碼。
根據本發明之一較佳實施例，該展開編碼繫於不同於CDMA傳輸系統中信號傳輸之時間開始，該系統具有結束狀態，其系具有n位且迭代N次，系被用以作為初始化狀態以產生該時間位移之展開序列。這讓傳輸和接收過程之時機有很大的彈性，尤其是於UMTS標準中之壓縮模式能以低複雜度執行。
其優勢系在於一展開序列之偏移能以一給予之編碼數目及一結束狀態定義，該結束狀態系具有n位且被迭代N次，系被用以作為初始化狀態以產生展開序列，其系關聯於該編碼數目N。這表示其可以一簡單方法尋址一大量之編碼，用以識別一編碼之該編碼數目N繫於同時用以作為編碼生產之不可或缺的參數，且可直接用以編碼產生，而不需要任何花費時間的轉換程序。
本發明於下文伴隨一些實施例及圖式說明做更詳細的描述，其中第1圖所示為一SSRG(簡單位移緩存器產生器)型式之位移緩存器電路圖；第2圖所示為根據本發明之n×n矩陣TN之圖式，其在當與該初始狀態相乘時，直接產生該位移之虛擬隨機序列之生產之該初始化狀態，其已經迭代N次；第3圖所示為一表，其中所需運算之數目系基於習知方法及根據本發明之方法所需的偏移N互相比較。
第1圖所示為一SSRG(簡單位移緩存器產生器)型式之位移緩存器之結構，該位移緩存器具有n緩存器胞元R1，R2，...，Rn-1，Rn，其中一胞元之緩存器內容可假設為0或1之值。時脈脈衝系經由一般之時脈線1施用於該緩存器胞元，一緩存器胞元之內容系與每一時脈脈衝傳輸至下一個緩存器胞元。為了達成此目的，一緩存器胞元之輸出系連接至下一個緩存器胞元之輸入，舉例來說，該緩存器胞元R1之輸出連接至該緩存器胞元R2之輸入，這表示說一開始就存在之該位序列系由一緩存器胞元或是一位位置以每一時脈脈衝位移至正確位置。
能於緩存器胞元Rn之輸出被引出之信號3系一些XOR閘極4，6，9，11修改，以便產生信號12，其系施用於該第一緩存器胞元R1之輸入。能於Rn輸出處被引出的信號3系被修改以便產生由係數c1，c2，...，cn-2，cn-1管理之信號12，其可每一假設該值為0或1。當ci(其中i＝1，2，...，n-1)具有該值為0時，這表示能於該緩存器胞元Ri輸出處被引出之該信號不具有對回饋信號之任何影響，如果，舉例來說，cn-1＝0的話，則該信號3系不需要由能於該緩存器胞元Rn-1輸出處被引出之該信號13修改。施用於該XOR閘極4之輸入處之該信號3系通過該XOR閘極4之輸出而沒有任何修改，以致於該信號5與該信號3對應，如果該係數cn-1＝0的話，則該XOR閘極4能因此亦被發射，且能以介於該信號3和信號5之間之一直接連結取代。
另一方面，如果一係數ci(其中i＝1，2，...，n-1)具有該值為1時，則能於該緩存器胞元Ri輸出處被引出之該信號就會對該回饋信號有貢獻，如果，舉例來說，c2＝1的話，則前述回饋信號8繫於該XOR閘極9中與能於該緩存器胞元R2輸出處被引出之該信號14有XOR連結，因此會導致該修改之回饋信號10，因為XOR連結能描述為一以模數二之增加，該XOR閘極4，6，...，9，11繫於第1圖中顯示為模數二加法器。
第1圖中所示型式之位移緩存器的遞歸規則系藉由一特徵多項式管理，其形式係為f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn其係數c1，c2，...，cn-1與第1圖所示係數對應，且尤其能假設該值為0或1，不可約之多項式系用以作為信號之編碼和解碼目的之多項式f(x)，不可約之多項式特徵系在於其不可表示為至少兩因子之乘積，該兩因子本身在主體GF(2)方面亦為多項式之一大於零之次數。不可約多項式不能因此因子化為更低次數之多項式。
讓我們假設該緩存器胞元R1，R2，...，Rn-1，Rn之該初始值在時間零時係為x1(0)，x2(0)，...，xn(0)，該緩存器x1(t+1)，x2(t+1)，...，xn(t+1)在時間t+1時能分別由該緩存器於時間t時之值x1(t)，x2(t)，...，xn(t)得到，其系使用下列遞歸規則xn(t+1)＝xn-1(t)，xn-1(t+1)＝xn-2(t)，. .
. .
. .
x2(t+1) ＝x1(t)，x1(t+1)＝c1·x1(t)+c2·x2(t)+...+cn-1·xn-1(t)+xn(t)在此使用之加法步驟係為一模數二加法，亦即一XOR運算，如果f(x)係為一不可約之多項式，則一所謂的虛擬隨機序列xn(0)，xn(1)，xn(2)，xn(3).....
能於該位移緩存器之輸出處被引出，如同信號3一樣。一個新的序列值會與該時脈信號1之每一時脈脈衝於該位移緩存器之輸出處出現。
如同第1圖所示能被產生之該隨機虛擬序列硬體具有適當信號編碼之的關係式對數，如此類之虛擬隨機序列因此用以作為傳輸器末端及接收器末端展開序列之產物，其繫於如UMTS或IS-95之CDMA方法中。於第1圖中說明之該位移緩存器結構因此代表該適當的硬體以於行動臺及基地臺產生展開序列，其系使用一CDMA方法作為該傳輸標準。
該緩存器向量
xn(t)xn-1(t)x2(t)x1(t)]]>代表該緩存器胞元R1，R2，...，Rn-於時間t之內容，如果該n×n矩陣T系定義為T=010000010100011cn-1cn-2c2c1]]>則該遞歸規則可公式化如下xn(t+1)xn-1(t+1)x2(t+1)x1(t+1)=Txn(t)xn-1(t)x2(t)x1(t)]]>該n×n矩陣T系也視為該對數遞歸矩陣，該編碼序列之一單一迭代可因此被表示為該矩陣T，其系乘上該緩存器向量。在一對應的方法中，於透過一偏移N之該編碼序列中一位移可表示為緩存器向量，其系乘上矩陣TN\
xn(t+N)xn(t+N)x2(t+N)x1(t+N)=TNxn(t)xn-1(t)x2(t)x1(t)]]>然而該矩陣T之該第N次方之直接計算可能會比習知之該位移緩存器執行N預先迭代還要複雜的多。
該矩陣TN將於下文中決定，其系藉由一較快且較不複雜之方法。其系基於該n×n矩陣T*，其係為該矩陣T之移項矩陣，該矩陣T*係為T*=0001100cn-101000c2001c1]]>本發明系基於藉由該移項矩陣T*之乘法運算對應獨立變量x於該多項式環形模數f*之該剩餘組環形之乘法運算之觀察，該多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn於本例中系藉由該多項式係數之反映而來，該多項式係為f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn此亦可寫成f*(x)＝xnf(x-1)T*之乘法運算相同於x模數f*之乘法運算之事實可如下解釋每一剩餘組模數f*係為「cannonic base」[1]，[x]，...，[xn-1]模數f*之一線性組合，因此足以顯示T*運算系基於相同方式，如同x模數f*之乘法運算。
等值層級[1]模數f*之給予系藉由向量10000]]>乘上T*之後，其結果為向量01000]]>其系同於等值層級[x]模數f*。此可以同方式施用於所有的等值層級[1]，[x]，...，[xn-2]模數f*，最後一個等值層級[xn-1]模數f*系同於向量00001]]>其繫於乘上T*期間被映至向量1cn-1c2c1]]>且其同於等值層級[1+cn-1x+cn-2x2+...+c1xn-1]mod f*。然而，此等值層級系精確地與該層級[xn]模數f*相同，因為[xn]mod f*＝＝[xn+f*]mod f*＝
＝[xn+1+cn-1·x+cn-2·x2+...+c1·xn-1+xn]mod f*＝＝[1+cn-1·x+cn-2·x2+...+c1·xn-1]mod f*在本例中，「+」在每一例中表示在對應的主體GF(2)中兩元素之加法，這表示「+」即為「XOR」。
T*對每一元素之乘法運算系因此與x模數f*之乘法運算相同，且T*之乘法運算系因此與T*對每一多項式之乘法運算相同。
(T*)N之乘法運算系因此也與xN模數f*之乘法運算相同。
這些對數亦能被用以決定該矩陣(T*)N，矩陣(T*)N描述一線性轉換，其系能改變該多項式[xj-1]mod f*(其中j＝1，2，...，n)成為乘上xN模數f*之多項式[xN+j-1]mod f*。在本案中，該多項式[xj-1]modf*，更精確地說是其次數小於n之多項式且代表剩餘組[xj-1]mod f*，系以第j個單位向量代表，該多項式[1]mod f*系因此藉由該第一單位向量表示100]]>且該多項式[x]mod f*系由該第二單位向量表示010]]>依此類推，這些單位向量藉由矩陣(T*)N之乘法運算改變該第一單位向量成為行位向量[xN]mod f*，該第二單位向量成為行位行位向量[xN+1]mod f*，且通常來說，第j個單位向量成為該行位向量[xN+j-1]modf*。該矩陣(T*)N之結構因此如下(T*)N＝|[xN]mod f*，[xN+1]mod f*，...，[xN+n-1]mod f*|這種標記表示於該矩陣(T*)N中該第j個行位系藉由具有較低次數之剩餘組[xN+j-1]mod f*之典型之係數所形成，如果該矩陣系藉由右邊的第j個單位向量乘上，則將會導致所需的行位向量[xN+j-1]mod f*。
移項和取冪之運算可在該矩陣T內交換，因此(T*)N＝(TN)*該欲決定之矩陣TN因此係為TN=(tj,k)j,k=1,2,...,n=[xN]modf*[xN+1]modf*[xN+n-1]modf*]]>於該矩陣TN中之該第j列系藉由具有較低次數之剩餘組[xN+j-1]mod f*之典型之係數所形成，該矩陣TN之結構系示於第2圖中。
以此方法決定之矩陣TN現在可根據迭代規則取代xn(t+N)xn-1(t+N)x2(t+N)x1(t+N)=TNxn(t)xn-1(t)x2(t)x1(t)]]>用以計算已經迭代N次之狀態之迭代規則因此變成
xn(t+N)xn-1(t+N)x2(t+N)x1(t+N)=[xN]modf*[xN+1]modf*[xN+n-1]modf*xn(t)xn-1(t)x2(t)x1(t)]]>為了計算於矩陣TN中第j列之矩陣元素(tj，k)k＝1，2，...，n，必須決定多項式之係數，該多項式一方面系屬於該剩餘組[xN+j-1]mod f*，另一方面其次數系小於n，此點可由一個所謂的平方和乘法算法完成。此類的算法能使用該剩餘組多項式g＝[x]mod f*，其系用以作為該算法之輸入變量，以決定該剩餘組多項式[xM]mod f*，其中M係為一未定義之自然數。
讓我們假設M＝MrMr-1Mr-2...M1M0係為該自然數M之一二進位代表，其最顯著之位係為Mr＝1，該對應之平方和乘法算法系接著寫成如下1.設y←g2.對i來說系從r-1降至02.1設y←y2mod f*2.2如果Mi＝1，則設y←g·y mod f*3.輸出y該平方運算法繫於第2.1行執行，而該乘法運算繫於第2.2行執行，其系提供Mi＝1之條件，該運算「·」於本例中亦表示兩剩餘組之相乘，且導致該結式剩餘組之典型。一旦該算法已經完成，該輸出y係為具有最低次數之剩餘組[xM]mod f*之典型，所需計算步驟之數量，以及因此所需之計算時間，皆決定於M的對數。
該矩陣TN之矩陣元素系根據本發明之一第一實施例所決定，其繫於每一列執行一次平方和乘法算法，該平方和乘法算法對於M＝N+j-1系因此被呼叫出，以便計算第j列之矩陣元素，其系由該剩餘組多項式[xN+j-1]mod f*之係數給定，所有的矩陣元素能因此藉由執行該平方乘法算法n次以決定。
作為此之一變形，根據本發明之一第二實施例，僅於該矩陣之第一列之該矩陣元素(t1，k)k＝1，2，...，n系由該平方和乘法算法決定，同時於第2至n列之該矩陣元素系藉由於第一列之矩陣元素之迭代以獲得。在本發明之此實施例中，該平方和乘法算法只要呼叫一次，因此本發明之本實施例更減少了計算複雜度。
因此，首先，該平方和乘法算法以M＝N呼叫，以便決定於該矩陣TN中之該第一列(t1，1，t1，2，...，t1，n-1，t1，n)，此列包含該剩餘組[xN]mod f*典型之係數，亦即[xN]mod f*＝[t1，1+t1，2·x+t1，3·x2+...+t1，n·xn-1]mod f*該矩陣TN之第一列現在應該當作基礎，用以迭代地決定接下來於該矩陣中之列，每一次都必須執行兩步驟，以便接下來由第(j-1)列決定第j列之元素。在第一步驟中，於該第(j-1)列中之該矩陣元素系向右移一項，其系對應x之乘法運算，因此，對j＝2，3，...，n來說(tj，1，tj，2，tj，3，...，tj，n-1，tj，n)＝(0，tj-1，1，tj-1，2，...，tj-1，n-1)在本例中，於該第(j-1)列中之最後一個元素，該矩陣元素tj- 1，n系移出矩陣外，然而，族果該矩陣元素tj-1，n系等於1，此矩陣元素tj-1，n系提供回饋，且因此修改於第j列中之矩陣元素。在第二步驟中，因此首先便需要先確定tj-1，n是否等於1，如果tj-1，n系等於1的話，便會執行該反映多項式f*(x)及於第j列(tj，1，tj，2，tj，3，...，tj，n-1，tj，n)之該矩陣元素(於第一步驟所獲得)之一XOR加法，該反映多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn亦能被寫為f*(x)＝f1+f2·x+f3·x2+...+fn+1·xn且因此能以該位向量(f1，f2，...，fn-1，fn，fn+1)表示，接下來之XOR加法必須因此於tj-1，n＝1之情況執行tj，k＝tj，k f-k其中k＝1，2，...，n表示於該第j列不同的元素，且其中該運算「」系表示XOR加法。
於該矩陣中之所有矩陣元素TN＝(tj，k)j，k＝1，2，...，n都能以此方式決定。
移項至右邊及f*之XOR加法之兩步驟於本例中精確地與MSRG(模數位移緩存器產生器)位移緩存器於每一時脈脈衝會執行的運算相同。然而，決定該矩陣元素所需要之迭代只不過在以一處理器計算時才執行。
本發明最重要之的應用系在於傳輸系統之展開序列的產生，該傳輸系統系基於一CDMA傳輸方法操作。該展開序列係為虛擬隨機序列，其不是藉由一SSRG型式之位移緩存器配置產生，不然就是由一數位訊號處理器產生。
本發明得以計算該位移緩存器配置之內容，其在執行N次迭代後會產生結果。該初始化狀態，其已經以N位位移，接著能被寫至於位移緩存器配置中之位移緩存器胞元，該位移緩存器配置接著使用該初始化狀態作為基礎，用以一虛擬隨機序列之產生，其系以N位位移，且能用以作為一展開序列。
可用在UMTS行動無線之編碼的定義包含在1999年發行的「3GPP展開和調變(FDD)」第三代夥伴計畫TS 25.213，這裡尤其以編碼之傳輸信號定義了所謂的密碼形式的編碼，這些擾碼尤其系用以分辨由不同基地臺發送至一行動臺(下行通路)之間的信號。在本例中，於該下行通路模式中使用不同的編碼，亦即對於一信號由該基地臺至該行動臺之傳輸，會比一信號由該行動無線使用者至該基地臺之傳輸(上行通路)要多。除此之外，不同的邏輯頻道系以不同的擾碼來編碼，舉例來說，用以作為封包之資料合併傳輸，以及用以發射器和接收器之間的配合。在本例中，每一種狀況可能會由一族密碼中選出，其系一族內之編碼，僅以他們的編碼數目區隔。
實質上，UMTS之中存在三個不同形式的擾碼，每一種包含一序列之複數，所謂的長編碼包含38400數目且在一10ms之時間訊框之內無迭代。除此之外，還有一種所謂的短編碼，每256字符就迭代一次，以及所謂的碼頭，其包含4096。長擾碼系最複雜且在UMTS標準中以虛擬隨機序列定義。在下行模式中，亦即當信號由該基地臺傳輸至該行動臺，兩個不同之虛擬隨機序列系與關聯不可約的多項式一起使用，該多項式其次數系18，且係為f(x)＝1+x7+x18及f(x)＝1+x5+x7+x10+x18。
假設無偏移的情況發生，該初始化狀態，亦即該位移緩存器配置之該初始緩存器內容，系明白地由第三代夥伴計畫技術說明書定義，該具有數目N之擾碼會由考慮到額外的N位偏移之編碼獲得。
當使用一種平方和一種乘法方法用以於多項式環中剩餘組之計算，根據本發明之該方法可以被執行以便決定已經單單以位移運算迭代N次之狀態。習知方法中，亦即N預先迭代之程序，同樣地能以位移運算執行。
第3圖所示為一表格，其係指出對於偏移N之不同值，習知方法所需的運算數量(中間行位)，以及根據本發明之方法所需的運算數量(右手邊行位)。當實際執行時，所需運算數量大約與所需時間成比例，如同可見的，習知方法只有在偏移值非常小的時候才夠快，新方法的一個主要優點系在於所需運算數量系對數地與所需偏移N相依，此導致了計算複雜度和所需時間明顯地減少。除此之外，計算複雜度和所需時間跟習知方法相比，能預先被相當大量地計算，這是一個關鍵性的進步，尤其是對於行動無線應用上來說，其系總是必須及時執行。
權利要求
1.一種方法，其系用以一位移緩存器配置之一結束狀態之決定，其系具有n位且系迭代N次，該決定系來自該位移緩存器配置之一給定之初始狀態，其系具有n位，其系使用該位移緩存器配置之迭代規則，其系藉由特徵多項式f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn給定，其中c1，c2，...，cn-1∈{0；1}，其特徵系在於下列步驟a)該多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn之決定，其係為該多項式f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn係數之反映；b)對於j＝1，...，n，剩餘組[xN+j-1]mod f*之代表之決定，其次數系小於n；以及c)該初始化狀態之位序列之乘法運算，其系藉由一矩陣，對於j＝1，...，n，其第j列或是第j行系藉由剩餘組之代表之係數給定，該剩餘組系如步驟b)[xN+j-1]mod f*中所決定。
2.如權利要求第1項所述之方法，其特徵系在於該剩餘組之代表[xN] mod f*，[xN+1]mod f*，...，[xN+n-1]mod f*每一系明確地以一合適的算法計算，尤其是以一平方和乘法算法。
3.如權利要求第1項所述之方法，其特徵系在於僅有該剩餘組之代表[xN]mod f*系明確地以一合適的算法計算，尤其是以一平方和乘法算法，其特徵亦在於該剩餘組之代表[xN+n-1]mod f*其中j＝2，…，n系由剩餘組[xN]mod f*之代表之係數之(n-1)計算迭代所獲得。
4.如權利要求第3項所述之方法，其特徵在於該剩餘組織該等代表[xN+j-1]mod f*其中j＝2，…，n系藉由一MSRG型式之位移緩存器配置之(n-1)計算迭代所獲得，其系來自該剩餘組之代表[xN]mod f*之係數，其中該位移緩存器配置之迭代規則系藉由該特徵多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn給定。
5.如前述權利要求之其中一項所述之方法，其特徵系在於該結束狀態，其系具有n位及系迭代N次，系用作一初始化狀態，用以產生位移N位之一虛擬隨機序列。
6.如前述權利要求之其中一項所述之方法，其特徵系在於該結束狀態，其系具有n位及系迭代N次，系當作初始化狀態寫入一位移緩存器配置，其系包含n位移緩存器胞元(R1，R2，...，Rn)。
7.如權利要求第6項所述之方法，其特徵系在於該位移緩存器配置係為一SSRG型式之位移緩存器配置，其包含n位移緩存器胞元(R1，R2，...，Rn)，且其結構系藉由特徵多項式f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn給定。
8.如前述權利要求之其中一項所述之方法，其特徵系在於該方法系被使用，以便於CDMA傳輸系統中產生具有一N位偏移之一展開序列，尤其是基於UMTS或IS-95傳輸標準之CDMA傳輸系統。
9.如權利要求第8項所述之方法，其特徵系在於該方法系用以擾碼之產生，其繫於UMTS標準中定義。
10.如權利要求第8或9項所述之方法，其特徵系在於該展開序列系用以該傳輸信號之傳輸器末端展開編碼。
11.如權利要求第8或9項所述之方法，其特徵系在於該展開序列系用以該接收信號之接收器末端解碼。
12.如權利要求第8至11項之其中一項所述之方法，其特徵系在於該展開編碼繫於該CDMA傳輸系統中與具有該結束狀態之該信號傳輸於不同時間開始，該結束狀態系用以作為該初始化狀態，其系用以該時間位移展開序列之產生，該結束狀態具有n位且系被迭代N次。
13.如權利要求第8至11項之其中一項所述之方法，其特徵系在於一給定之編碼數目定義具有該結束狀態之一展開序列之該偏移，該結束狀態具有n位且系被迭代N次，該結束狀態系用以作為該初始化狀態，其系用於該展開序列之產生，該展開序列系關聯於該編碼數目N。
14.一種裝置，其系用以一位移緩存器配置之一結束狀態之決定，其系具有n位且系迭代N次，該決定系來自該位移緩存器配置之一給定之初始狀態，其系具有n位，其系使用該位移緩存器配置之迭代規則，而藉由特徵多項式f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn給定，其中c1，c2，...，cn-1∈{0；1}，其中裝置系被提供用於該多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn之決定，其系藉由該多項式f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn係數之反映；裝置系被提供用於該剩餘組之決定，且對於j＝1，...，n，且在每一例中決定該剩餘組[xN+n-1]mod f*之代表，其次數系小於n；裝置系被提供用於該初始化狀態之該位序列之乘法運算，其系藉由該矩陣，對於j＝1，...，n，其第j列或是第j行系藉由剩餘組[xN+n-1]mod f*之代表之係數給定，其次數系小於n；
15.如權利要求第14項所述之裝置，其特徵系在於用於剩餘組決定之裝置在每一例中明確地計算該剩餘組之代表[xN]mod f*，[xN+1]mod f*，...，[xN+n-1]mod f*其系藉由一合適的算法，尤其是藉由一平方和乘法算法的裝置。
16.如權利要求第14項所述之裝置，其特徵系在於用於剩餘組決定之裝置明確地僅計算如次剩餘組之代表[xN]mod f*其系藉由一合適的算法，尤其是藉由一平方和乘法算法，且其特徵亦在於用於剩餘組決定之裝置獲得該剩餘組之代表[xN+n-1]mod f*其中j＝2，...，n，其系由該剩餘組之代表[xN]mod f*之係數由(n-1)計算迭代獲得。
17.如權利要求第16項所述之裝置，其特徵系在於用以剩餘組決定之裝置獲得該剩餘組之代表[xN+n-1]mod f*其中j＝2，...，n，其系藉由一MSRG型式之位移緩存器配置之(n-1)計算迭代所獲得，其系來自如次剩餘組之代表[xN]mod f*之係數，其中該位移緩存器配置之迭代規則系藉由該特徵多項式f*(x)＝1+cn-1·x+cn-2·x2+...+xn給定。
18.如權利要求第14至17項之其中一項所述之裝置，其特徵系在於該裝置用以決定一結束狀態，其系具有n位及系迭代N次，系當作初始化狀態將該結束狀態寫入一位移緩存器配置，其系包含n位移緩存器胞元(R1，R2，...，Rn)。
19.如權利要求第18項所述之裝置，其特徵系在於該位移緩存器配置係為一SSRG型式之位移緩存器配置，其包含n位移緩存器胞元(R1，R2，...，Rn)，且其結構系藉由特徵多項式f(x)＝1+c1·x+c2·x2+...+cn-1·xn-1+xn給定。
20.如權利要求第14至19項所述之一種裝置之使用，其系用以於一CDMA傳輸系統中具有N位之一偏移之一展開序列之產生，尤其是在對應傳輸標準UMTS或是IS-95其中之一之一CDMA傳輸系統中。
21.如權利要求第20項所述之使用，其特徵系在於該展開序列系用於待傳輸信號之傳輸器末端展開編碼。
22.如權利要求第20項所述之使用，其特徵系在於該展開序列系用以該接收信號之接收器末端解碼。
23.如權利要求第20至22項之其中一項所述之使用，其特徵系在於該展開編碼繫於該CDMA傳輸系統中與具有該結束狀態之該信號傳輸於不同時間開始，該結束狀態系用以作為該初始化狀態，其系用以該時間位移展開序列之產生，該結束狀態具有n位且系被迭代N次。
24.如權利要求第20至22項之其中一項所述之使用，其特徵系在於一給定之編碼數目定義具有該結束狀態之一展開序列之該偏移，該結束狀態具有n位且系被迭代N次，該結束狀態系用以作為該初始化狀態，其系用於該展開序列之產生，該展開序列系關聯於該編碼數目N。
全文摘要
根據本發明之方法可以由一給定的初始狀態，以計算方式決定一位移緩存器配置之狀態，該狀態具有n位且系被迭代N次。此允許產生具有任何所需偏移N之虛擬隨機序列，而不需要因為此目的而執行先前迭代。一矩陣，其第j列，其中j＝1，...，n系藉由代表該剩餘組[x
文檔編號H04B1/707GK1559110SQ02818965
公開日2004年12月29日 申請日期2002年7月23日 優先權日2001年9月26日
發明者R·登克, R 登克 申請人:因芬尼昂技術股份公司