TW566009B - System for generating pseudorandom sequences - Google Patents

Description

566009 A7 B7 五、發明説明（彳） 相關申請案交互參考 此申請案主張於2001年4月6日立案之臨時專利申請編號 60/282,349之優先權。 發明背景 本發明一般而言關於無線通訊系統。特別是，本發明關 於劃時雙工（TDD)及劃頻雙工（FDD)系統，其使用正交可變 展開因子（OVSF)碼及Hadamard碼，用以展開傳輸用的資料 ’並包含供產生這種碼的一改進系統。 許多種的通訊系統，例如FDD及TDD通訊系統，其使用 一或多個系列的虛擬隨機碼來展開通訊碼。這些碼係同時 用於傳送器及接收器中，並在整個通訊系統中的許多地方 。數種常用的碼系列包含OVSF碼及Hadamard碼。 圖1所示為一OVSF碼的碼樹，其可保持不同頻道之間的 正交性。該OVSF碼可使用圖i的碼數來定義，藉此該頻道 化碼可唯一地表示成Cch，SF，k，而其中盯為該碼的展開因子 ，且k為該碼編號，叱hSF_h在該碼樹中的每個層級定義 了長度SF的頻道化碼，其對應於圖1的展開因子 該頻道化碼的產生方法係定義成：

裝 訂

CcM〇 ~ ^

CcA2,0 CcM,o CchA,0 •i r _Ccii，2，l - _CchX〇 — Cch，l，0_ -1叶 -4-

566009 A7 B7 五、發明説明（2

Cc/i，2(n+丨)，〇 「 Cdi，2(n+l)，l Ccft、2(n+l)，2 Cc/j,2(n+l)，3 = ^c/7,2(n+I ),2(n+l )-2

C vh,2\Q C C 、·Α，2，·,0 ΧΛ c

在每個頻道化碼字元的最右側數值係對應於在時間中第 一次傳送的晶片。要使用的〇7^碼為該展開因子，所利用 的頻道數及該頻道種類之函數。 一種供產生OVSF碼的方法係利用以上的數學描述。但是 ，這種矩陣操縱在運算上很昂貴，且需要相當快速及昂貴 的硬體來執行。此外，當一運算單元為此目的而固定於硬 體’其通常不能用於其它目的。此可加入到系統複雜度， 並造成整體系統設計中不必要的複雜及昂貴。 因此’其需要一方便的裝置來快速地及有效率地產生 OVSF碼’其也需要這種裝置來可適應於其它種類的碼之產 生，例如Hadamard序列。 發明概要 本發明同時包含可以快速及有效率地-產生〇VSF碼的系 統及方法，其使用包含所需要碼的碼樹腳之識別的一暫存 器，及順序通過該腳的一計數器。該系統可依需求產生該 碼，而需要非常少的硬體資源。 此外，相同系統及方法可適合來產生Hadamard序列。 -5- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐) 566009 五、發明説明（ 圖1所示為一先 (OVSF)碼。 圖式簡單說明 月’J技藝碼樹’用於正交可 變展開因子 圖2所示為根據本發明之產生0VSF碼的系 圖3 A所示為一種 之系統 用以產生具有一展開因子為4的〇vSF碼 圖3B所示為一種用以產生具有一 之系統。 生 展開因子為8的OVSF碼 圖4所不為具有展開因子為8的〇vsf碼樹之第七碼的產 圖5所示為該結構的擴充性。 圖6所示為一先前技藝的Hadamard碼的碼樹。 圖7所示為本發明之另一具體實施例，用以同時產生

Hadamard及 OVSF碼。 圖8所示為具有展開因子為8的Hadamard碼樹之第四碼的 產生。 圖9所示為本务明之第二具體實施例用以產生虛擬隨機 碼。 較佳具體實施例之詳細說-明 目前的較佳具體實施例係參考圖面在以下說明，其中類 似的編號代表整個圖面中類似-的元件。此外，本發明的較 佳具體貫施例將參考OVSF及Hadamard碼。但是，本技藝專 業人士必須瞭解到相同的原理可應用到其它系列的碼，而 本發明必須不能夠嚴格地限制於此處所述的範例具體實施 -6- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 566009 五、發明説明（ 例 請參考圖2,所示為—種用以產生虛擬隨機序列的系統1〇 。該糸統10包含—位元位置計數器12，一多工器14，一展 開因子選擇器16，一位元別的細閘18, 一索引選擇哭2〇 及-鹰閘22。該計數器12為一自由運行二進位計數器， 其可提=一輸出到該多工器14的第一輸入。該計數器12初 始化為零，並在產生所f要的〇VSF碼時"自由”地運行。一 碼，產生係依照需要來重覆許多次，藉以展開該資料。對 於母個需要產生該碼的場合，該計數器即初始化為零。另 夕一卜古該計數器！2可被允許來自由地運行，藉此未使用的最 问有效位兀可被忽略。此選擇性將在稍後詳細說明。 該展開因子選擇器16提供一輸出到該多工器㈣第二輸 入’其可識別來自該計數器12中有多少位元必須由該多工 =輸出。對於〇S VF碼產生，該多工器】4亦倒轉該輸出位 几順序’使得該輸出位元即具有倒轉的順序。此係 在圖3A及3B中，以該多工器μ内的點線來圖形化地說明。 请再參考圖2,該索引選擇器2〇輸出該索引的二 ’或該碼樹的"分支"，其為所想要產生者。舉例而言，： ::所:’如果需要一展開因子為4,其亦需要產生該碼樹 ，，-刀支"亥索引選擇器2〇將輸出該號碼2的一兩位元的 二進位序列，其為1G。類似地，.如果其需要-展開因子8 及5亥碼樹的第四分支，該索引選擇器20輸出該號碼3的—一 位70的二進位序列，其為。 一 該索引選擇器20的輸出及該多工器14的輸出可由該位元 本紙張尺度適用悄_標準(CNS) A4規格(21^ 297公釐） 566009 A7

=的閘18來AND運算在—起。此為一輸出到該X⑽問 22八貝際上為一 X〇R”樹，，，其包含複數個XOR閘，其為 本技藝專業人士所熟知。 根據本發明的系統1〇係詳細顯示在圖3八及化中，其說明 I該系統10根據所想要的展開因子之不同的功能性架構。 這些圖面顯示來自該計數器12的多重位元輸出Cl.CN，及來 自該索引選擇器20的該多重位元輸出Ii-Im。請參考圖3A， 如果想要一展開因子4,該展開因子選擇器16控制該多工器 14 ,使侍该多工器14僅輸出來自該計數器a的前兩個位元 位置C 1及C2中所需要的位元到該AND閘1 8。來自該計數 获12的位几位置C3_Cn基本上可，’歸零”或忽略。每個来自該 什數β 1 2的所需要的位元，其係成反向順序，並與來自該 索引遠擇器20的所需要的位元做位元別的邏輯AND運算。 牟例而σ來自δ玄计數益12的第一位元C 1與來自該索引選 擇20的第二位元込做邏輯AND運算；而來自該計數器η 的第二位元C2與來自該索引選擇器20的第一位元l做邏輯 及運算。一旦所有來自該計數器1 2所想要的位元已經與來 自該索引選擇器20的所需要位元進行位元別的and運算， 該AND閘18即輸出到該}(011閘22。該乂〇11閘22的輪出為具 有該所想要位元的碼序列。該碼序列的每個新位元係在該 計數器12序列化時來產生。 請參考圖3B所示的第二具體實施例，如果想要一展開因 子馬8，該多工器14輸出來自該計數器12的前三個位置c ’ C2及C3之位元到該and閘18。來自蹿計數器12的苐一位.. -8 - 本紙張尺度適用巾g S家標準(CNS) A4^(21G X 297公爱) ' -----

裝 訂

4 566009 A7

元匕會與來自該索引選擇器2〇的第三輸出i3進行αν〇運算 。颂似地，.來自該計數器⑽第二位元與來自該索引選擇 器^0的第二位元12進行AND運算。最後，來自該計數器12 的第二位7LC3及與來自該索引選擇器2〇的第一位元“進行 AND運^p。一旦來自該計數器12的所有想要的位元已經與 末自該索引選擇器2〇所想要的位元進行位元別and運算， 該AND閘1 8輸出到該x〇R閘22。該x〇R閘22的輸出為二想 要的碼序列。 Λ 雖然根據本發明所製作的系統1〇可以用來產生具有任何 長度的s具有展開因子之〇从81：碼，為了簡化起見，前述的 範例將可參考一展開因子為8來解釋。此需要一三位元的展 開因子選擇器16，一三位元的計數器12來序列通過該位元 ，一三輸入AND閘18 ,及一三輸入x〇r^ 22 ,如圖4所示。 對此範例其亦可參考下表1-3 : _ _ -9· 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 展開因子 所需要的SF 位元數目 2 1 4 2 8 3- 16 4 32 5 64 6 128 7 256 8 表1 566009 ， A7 B7 五、發明説明（7 ) 索引 分支 Is 12 II 第一 0 0 0 第二 0 0 1 第三 0 1 0 第四 0 1 1 第五 1 0 0 第六 1 0 1 第七 1 1 0 第八 1 1 1 表2 1展開因子 C3 C2 C, 0 0 0 0 0 1 0 1 0 0 1 _ 1 1 0 0 1 0 1 1 1 0 1 1 1 表3 -10- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 566009 A7 B7 ) 五、發明説明（8 對此範例，其需|^ > 產生具有一展開因子為8的碼序列，其 包含圖1所示的碼樹之楚丄『 ， ” 财之苐七腳，如該星號所標示。此在圖i 中識別為Cch 8 6，其^ j /、马 i，-1，-1，1，1，-1，-1，1。由表 i，因 為所想要的展開因子A 8 、 丁马8所想要的位兀數為3。由表2，因 為其想要產生該碼樹的笛 > 八士 i 〇 - ί的弟七刀支，如表2所示的該索引選擇 器之輸出將為該二進位序歹"，1，〇。然後該二進位計數器 12即順序通過—二進位計數由〇 (〇,〇,〇)到7 (1，u υ，如表 3所示。 。。該序列cch，8,6的第一位元將可藉由AND運算來自該計數 °°的以進位序列000來產生，（其在倒轉時仍產生〇〇〇) 與來自》索引選擇器2G的該二進位序列nq。該位元的 XOR造成一輸出為〇。該第二輸入001被倒轉產生1〇〇，並與 來自該索引選擇器20的該二進位序列no做AND運算，而產 生100。這些位元的X0R可造成一輸出為丨。類似地，該第 三輸入010被倒轉產生010,而在與110進行AND及x〇R運算 時，造成一輸出為1。該第四輸入0 u被倒轉產生u 〇，而在 與110進行AND及XOR運算時，造成一輸出為〇。該第五輸 入100被倒轉產生〇(Π，而在與11〇進行AND及x〇R運算時， 造成該輸出為0。該第六輸入101被倒轉產-生101，而在與11〇 進行AND及XOR運算時，造成一輸出為丨。該第七輸入 被倒轉產生011，而在與110進行AND及X〇r運算時，造成 一輸出為1。最後，該第八輸入ln被倒轉產生m，而在與 110進行AND及XOR運算時，造成一輸出為〇。 、 由於此重覆的過程，該序列輸出將為〇,丨，丨，〇, 〇,丨，丨，^ -11 - 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐) 五、發明説明（9 ) (請注意最右方位元係在時間中首先 續地對映，藉此一輸出丨即 二輪出即後 。因此，用於展開的序列為乂Γ_ 7 對映到1 符合於圖1所示的該0_碼樹的第七腳’H 1。此係 想意:外請 乃卜4糸統可為，，過大，，，如圖5所示，蕤士 其所不需要的該計數器12的位元，及該索引選❹2〇= 上可以忽略°如圖5所示’因為僅需要四個位itC|_c4:位 M5-CN係在通過該多工器14時被停止，或被”歸零”。4 ’僅有想要的位元C|.C4由該多工器14重新排序。在—類似 的方式中’僅有位元U_I4將由該AND閘"處理"，因為該綱 閘的剩餘部份將由於缺少來自相對應的位元之輸入 而被"歸零”。該輸出形成該職閘22，其將為所想要二馬 序列位元。 請參考圖6，所示為一 Hadamard序列的碼樹。此瑪樹的碼 將根據本發明的另一具體實施例來產生，其示於圖7。 請參考® 7，所示為—種產生數種虛擬隨機序列的系統 1〇〇。如圖2所示的具體實施例中，該系統〗〇〇包含一位元位 置計數器12，一多工器14，一展開因子選擇器16, 一位元 別AND閘，一索引選擇器20，及一又〇11閘22。但是，此具 體實施例包含一模式開關60，_其在用以產生〇^盯碼的第一 模式與用以產生Hadamard碼的第二模式之間切換。當該模 式選擇開關60在一第一位置，該系統1 〇〇之運作方式相同於 圖2所示的系統1 〇，藉此該多工器i 4倒轉來自該位元位置計 -12-

y12的該位讀出之位元财。但是，當該模式開關6〇 ,—位置時’ 5亥位元的重新排序並未由該多工器14執 二’且該位元係經由該多卫器14直接傳送_位元別細 此係示於圖8,藉此通過該多工器14的該直虛線說明 该：元係經由該多工器14直接傳送，而不用重新排序。 一種產生一 Hadamard碼的範例將參考圖8來解釋。由此範 ，’其需要產生具有-展開因子為8的碼序列，其包含該碼 數的第四腳’如圖6所示’其以星號標示。此序列在圖6中 顯示為〇, 1，1，"，1 U。由表（，因為所想要的展開因 子想要的位元數為3。由表2,因為其想要產生該碼樹 的第四分支，如表2所示的該索引選擇器之輸出將為該二進 位序列0’ 1，1。然後該二進位計數器丨2即序列通過該二進 位計數由0(0,0,0)到7(1，丨，丨），如表3所示。 相同的AND及XOR運算程序即如所述地參考該〇vsf碼 的產生來執行，了來自該計數器12的位元並未倒轉。此 j成來自該系統100的輸出為〇,丨，10, u丨，〇。此可正確地 苻合該Hadamard碼預結構的第四腳，如圖6所示。這些輸出 可視需要來對映，藉此一輸出丨係對映到負丨，而一輸出〇 係對映到1。 一糸統200的第二具體實施例用以產生數種虛擬隨機序 列，其不於圖9。此系統200包_含該索引選擇器2〇，該位元 別AND閘18及該XOR 22。但是，該位元位置計數器12，該 夕工器14及該展開因子選擇器μ已經由一數目產生器Μ] 及一選擇器204所取代。該數目產生器2〇2儲存一預定序列 -13 - 本紙張尺度適用中國國家標準(CNS) A4规格(210X 297公釐) 11 五、發明説明 的數目，例如儲存在表3中的數目， 因此，該數.目產生器202可依序輸出二=這二數目; 或另外可輪出該"重新排列"的位元 、丈目 間爽馮摞 叛出的位元序列之

Hada I 〇VSF碼，將輸出—第—序列；而對於 要使Γ;Γ ’將輸出一第二序列。雖然此具體實施例有必 碼樹所記憶體，其記憶體將小於儲存整個虛擬隨機 :树h要者。此外，雖然此具體實施例已經來考且有一 =:Γ的虛擬隨機碼來解釋’任何想要的序列；預先 健存在該數目產生器202中。

表'4 當本發明已藉由較佳具體實施例來說明，對於本技藝專 業人士將可瞭解在以下申請專利範圍所述的本發明範^内 可有其它變化。 -14-

Claims (1)

1. 566009 申請專利範園 ι· 一種用以產生一正交可鐵虽日 包含· 乂了 W開因子（OVSF)石馬之系統，其 一二進位計數器，用以提供—二進位計數，其 數個序列化的Μ位元二進位數目· Α =重新排序裝置，用以由最低有效位 位權性地重新排序每個該二進位數目的位元； 一索引選擇器，用以提供該 識別；及 肩SF碼的一 Μ位兀二進位 裝 1輯簡化裝置’其具有來自該計數器的 及來自該索引選擇器的一第— 、， 輸入 此所想要的OVSF碼即由該輪出所輸出。 出，猎 2· —種用以產生一組二進位碼乂 器，每個二進位碼具有2、元進位瑪之碼產生 一計數器，用以在一平杆古Α — ’每個連續計㈣增加1;向順序地輸出Μ位元計數 別 索引選擇器’用以在—平行方向輪出_μ位元碼識 來 一Μ邏輯閉的平行陣列’其每個具 自該計數器的-平行位元之輸出及為 引選擇器的—平行位元之一第二輸=及及為來自該索 一結合於該邏輯閘的該平行陣列之 ^ 簡化網路，用以在每次一平行M位元計：的避輯閘之 邏輯閘極陣料，？卩由該計數器輸出 ^到該平行 得由該_元碼識別所辨識的該二進位峰3=之: •15- 本紙張尺度適用中國國豕標準(CNS) A4規格(210X297公爱） 申請專利範圍 產生。 4 3’二申二’二利範圍第2項之妈產生器，進-步包含位元重 個、置’其輕合於該計數器的該輸出’用以接收每 心^計數1此該職元計數由最低有效位元排列 _ 7有放位兀’亚藉此該位元重新排序裝置由最高有 夕位元到最低有效位元來重新排序。 種產生一想要的虛擬隨機碼之系統，其包含： 進位计數器’用以提供複數個Μ位元序列二進位 该》石馬； 索引選擇器’用以輸出所想要的虛擬隨機碼之以位 元碼識別； 々至少Μ邏輯閘，其每個具有來自該二進位計數器的一 第一輸入，及來自該索引選擇器的一第二輸入，且每個 具有一輸出；及 — XOR樹，用以X〇R運算該輸出來提供一 X〇R後的輸 出，藉此該想要的虛擬隨機碼即由該x〇R後的輸出所輸 出。 5·如申請專利範圍第4項之系統，進一步包含位元重新排 序裝置，用以由最低有效位元重新到最高有效位元來排 序該二進位計數的位元。 6· —種由一組n二進位碼來產:生一個別二進位碼之碼產生 器，每個二進位碼具有Μ位元； 一計數器順序地輸出Μ位元二進位數目，每個連續的 二進位數目係增加1 ; -16 本纸張尺度適用中國國家標準(CNS) Α4規格(210X297公釐） 566009 A8 B8 C8

   -索引選擇器，用以輸出一M位元碼； 遨輯閘陣列’其具有來自該計數器的一第一輸入及 來自該索引選擇器的一第二輸入，並具有一輸出； ，-結合㈣邏輯閘陣列之輸出的邏輯閘之簡化網路 用以在每_人一 ；^位元二進位數目輸入到該邏輯閘時， 即由該計數器輪出-單-碼位元，使得由該Μ位元碼識 別所辨識的該二進位碼在炉遞迴之後產生。 7·如申請專利範圍第6項之碼產生器，進一步包含一位元 ^新排序裝置，其_合於該計數器的該輸出，用以接收 母個具有由最低有效位元到最高有效位元排序之位元 的Μ位兀數目’藉此該位元重新排序裝置由最高有效位 兀到最低有效位元來重新排序該位元。 8.如申請專利i圍第7項之碼產生器，*一步包含一轉合 到4位兀重新排序裝置的開關，藉此當該開關在一第一 位置時，該位元重新排序裝置係耦合到該計數器的該輪 出/以重新排序該二進位數目的位元，且當該開關在一 第一位置時，該位元重新排序裝置係由該計數器的該輸 出解除耦合，且該二進位數目的位元並未重新排序。 9·種產生一想要的虛擬隨機碼之系統；其包含： 一進位數目產生器，用以提供一包含複數個Μ位元 一進位數目的二進位計數； 索引選擇器’用以提供該想要的虛擬隨機碼的一 Μ ，位元二進位識別；及 遴輯簡化裝置，其具有來自該計數器的一第一輸入 •17 六、申請專利範園 及來自該索引選擇器的一第二 、， 此所想要的虛擬隨機碼即由該輸出所：：有-輸出；藉 10. —種用以產生一組二推 器，其每個具有2、元；’’’、的個別二進位碼之碼產生 數s — ?產生器，用以輸出複數個_元二進位 數目’母個連續的二進位數目為一預定序列之進位 二索引選擇器，用以輪出-Μ位元碼識別； - Μ賴㈣平行陣列，其每個具有 5:進位數目為-個位元的-第-輸入，及來自；t 別為一個位元的一第二輸入；及 4 结合於該邏輯問的該平行陣列之輸出的邏輯問之 ;;陣=$以在母次一二進位數目輸入到該平行邏輯 =陣列％ ’即由該計數器輸出一單一碼位元，使得由兮 ⑷立疋碼識別所辨識的該二進位 X 如申請專利範圍第10項之……之後產生。 — 項之碼產生益’糟此該預定序列為 :進位數目的序列，每個二進位數目係 位數目上增加1。 ^ 逆 12· -種用以產生一想要正交可變展開因子（〇w)碼之 統，其包含： _ “ 一二進位數目產生器計數器1以提供-Μ位元二進 位數目的預定序列； ： 一索引選擇器，用以輸出該想要的〇VSF碼的一 碼識別； 兀 至少Μ個邏輯閘，其每個具有來自該二進位數目產生

   、紙張尺度適种® S家標準(CNS) Α4規格(210 X 297公釐) 8 8 8 8 A B c D 566009 六、申請專利範圍 器的一第一輸入，及來自該索引選擇器的一第二輸入， 且其每個具有一輸出；及 一 XOR樹，用以XOR運算該輸出來提供一 XOR後的輸 出；藉此該想要的Ο V S F碼即由該X 0 R後的輸出所輸出。 -19- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐）