TWI381653B

TWI381653B - 二階重排多項式交織器位址產生裝置與方法

Info

Publication number: TWI381653B
Application number: TW098130766A
Authority: TW
Inventors: Shuenn Gi Lee; Chung Hsuan Wang; Wern Ho Sheen
Original assignee: Ind Tech Res Inst; Univ Nat Chiao Tung
Priority date: 2009-09-11
Filing date: 2009-09-11
Publication date: 2013-01-01
Also published as: TW201110566A; US8332701B2; US20110066914A1

Description

二階重排多項式交織器位址產生裝置與方法

本發明係關於一種二階重排多項式(quadratic permutation polynomial，QPP)交織器(interleaver)位址產生(address generation)裝置與方法。

近年來，行動通訊(3GPP LTE)系統大多以QPP交織器(Interleaver)來取代3G行動通訊系統中實體層渦輪碼(Turbo code)的交織器，藉以大幅改善解碼器的解碼速度。QPP交織器除了具有記憶體無競爭(Contention Free)的優點外，在硬體的複雜度及解碼性能上皆有不錯的表現。QPP交織器使得渦輪解碼裡輕易地避免在最大事後機率(Maximum A Posterior Probability，MAP)演算法算出最大事後機率之後，記憶體寫入碰撞的問題，同時，利用多個移動視窗(Sliding Window)來達成平行運算(Parallelism)以加快解碼器的運算速度。

常見的渦輪碼交織器設計大多將計算出的交織器位址事先儲存在一記憶體或一位址表格(address table)中，例如第一A圖與第一B圖的串列與平行架構。第一A圖的串列架構中，當一滑動視窗(sliding window)110輸出一筆外來資訊(extrinsic information)110a後，需要交織器位址時，就讀出一位址表格120裡一相對應的交織器位址，當作外來資訊110a要被填入記憶體130的位址。

第一B圖的平行架構中，當一組滑動視窗平行輸出多筆外來資訊後，需要交織器位址時，就讀出一位址表格121裡多個相對應的交織器位址，並搭配一組資料多工器(data multiplxer)125的選擇，當作此多筆外來資訊要被填入多個記憶體的相對應的位址。

以LTE渦輪碼為例，其解碼長度的範圍可由40至6144位元，也就是說每一碼段(code segment)裡的位元數可由40至6144。對於188種解碼長度的規格，此記憶體需儲存188組長度是40至6144位元之間的交織器位址。這需要花費不少的記憶體容量。

例如，美國專利號US6845482揭露一種利用一個產生質數索引資訊(index information)的元件以及如第二圖的五種查表(look-up table)來產生渦輪碼交織器之記憶體位址的技術。此記憶體位址產生技術產生與W-CDMA標準相容的渦輪碼之交錯位址(interleaved address)。對於W-CDMA標準可支援的所有可能的碼段大小，表格210儲存所有可以用到的質數，共有52個質數。表格220儲存四種列間排列序列(inter-row permutation sequence)221-224。表格230儲存52個跨列基本序列(intra-row base sequence)，表格230裡每一質數P對應一跨列基本序列，此跨列基本序列的長度為P-1。表格240儲存此52個跨列基本序列的起始位址(starting address)。表格250儲存52個質數序列(prime number sequence)，每一質數序列的長度為20。

美國專利公開號US2008/0115034揭露一種QPP交織器的範例，應用於渦輪碼的編解碼。第三圖中，此QPP交織器300包括一交織器記憶體(interleaver memory)310、一位址產生器(address generator)320、以及一控制單元(control unit)330。控制單元330裡的模數計數器(modulo-counter)331提供輸入索引(input index)n給位址產生器320。位址產生器320之輸出序列的第n個值Π(n)可以描述成下列型式：Π(n)=(f₁ n+f₂ n² )mod k，n=0,1,...,k-1，其中，Π(n)是第n個交織輸出位置(interleaved output position)，f₁ 與f₂ 是QPP係數，k是輸入序列的資訊區塊長度(information block length)，mod是模數運算。而計算出的Π(n)值則儲存於交織器記憶體310中，當需要時再從交織器記憶體310串列讀出。

本揭露的實施範例可提供一種QPP交織器位址產生裝置與方法。

在一實施範例中，所揭露者是一種QPP交織器位址產生裝置。此裝置包含一基礎遞迴單元(basic recursive unit)、以及表示為第一至第L遞迴單元的L個遞迴單元，L≧2。此裝置根據一QPP函數Π(i)=(f₁ i+f₂ i² )mod k，i=0,1,...,k-1，輸入數個可配置參數，並藉由此基礎遞迴單元，依序產生出多個交織器位址，藉由此第一至第L遞迴單元平行產生出L組相對應的交織器位址，其中，此基礎遞迴單元與第j遞迴單元於每一次產生交織器位址時，也分別輸出至此第一遞迴單元與第j+1遞迴單元，Π(i)是此裝置產生的第i交織位址，f₁ 與f₂ 是QPP係數，k是一輸入序列的資訊區塊長度，1≦j≦L-1。

在另一實施範例中，所揭露者是關於一種QPP交織器位址產生方法，應用於一通訊系統上的編解碼器。此方法包含：根據一QPP函數Π(i)=(f₁ i+f₂ i² )mod k，輸入多個可配置參數；藉由一基礎遞迴單元，依序產生出多個交織器位址；以及藉由L個遞迴單元，以第一至第L遞迴單元表示，平行產生出L組相對應的交織器位址，L≧2，其中，此基礎遞迴單元與第j遞迴單元於每一次產生交織器位址時，也分別輸出至此第一遞迴單元與第j+1遞迴單元，Π(i)是此方法產生的第i個交織位址，f₁ 與f₂ 是QPP係數，k是一輸入序列的資訊區塊長度，如此，讓此輸入序列之資訊填入多個相對應之記憶體的位址，0≦i≦k-1，1≦j≦L-1。

茲配合下列圖示、實施範例之詳細說明及申請專利範圍，將上述及本發明之其他目的與優點詳述於後。

本發明的實施範例中可提供一種QPP交織器位址產生裝置與方法。此QPP交織器位址產生技術採用的硬體設計可直接計算交織器位址，並可平行輸出或串列輸出交織器位址的計算結果。

第四圖是QPP交織器位址產生裝置的一個範例示意圖如所示，與所揭露的某些實施範例一致。第四圖中，QPP交織器位址產生裝置400根據QPP函數Π(i)=(f₁ i+f₂ i² )mod k，輸入數個可配置參數(configurable parameter)430，例如{k、(f₁ +f₂ )mod k、2f₂ mod k、2Mf₂ mod k、f₁ M mod k、f₂ M² mod k}或是{k、f₁ +f₂ 、2f₂ 、2Mf₂ 、以及f₁ M+f₂ M² }，來平行輸出交織器位址Π(i+jM)或串列輸出交織器位址Π(i)，其中，Π(i)是QPP交織器位址產生裝置400產生的第i交織器位址，f₁ 與f₂ 是QPP係數，0≦i≦k-1，1≦j≦L-1，k是一輸入序列的資訊區塊長度，M是將此輸入序列的資訊輸出之滑動視窗的寬度，L是一次平行輸出之交織器位址Π(i+jM)的個數。

QPP交織器位址產生裝置400可同時當成交織器與反交織器位址產生器來使用，以反交織器位址產生器來使用時，只需將輸出的交織器位址當成讀取一記憶體的位址即可。

QPP交織器位址產生裝置400可串列輸出或平行輸出交織器位址的原理先說明如下。因為QPP函數Π(i)=(f₁ i+f₂ i² )mod k，i=0,1,...,k-1，所以Π(i+m)=(f₁ (i+m)+f₂ (i+m)² )mod k=(Π(i)+f₁ m+f₂ m² +2 mf₂ i)mod k，當m=1時，

Π(i+1)=(Π(i)+f₁ m+f₂ +2f₂ i)mod k，i=0,1,...,k-1　(1)

所以，QPP交織器位址產生裝置400可根據遞迴公式(1)，直接依序算出交織器位址Π(0),Π(1),Π(2),...。

當m=M,2M,3M,...時，

Π(i+M)=(Π(i)+f₁ M+f₂ M² +2f₂ i)mod k，i=0,1,...,k-1　(2)

所以，QPP交織器位址產生裝置400可根據如遞迴公式(2)，而直接平行算出交織器位址Π(i),Π(i+M),Π(i+2M),...。以M=32為例，交織器位址產生裝置400可平行輸出數個序列，其中第一序列{Π(i+M)}為Π(32),Π(33),Π(34),...;第二序列{Π(i+2M)}為Π(64),Π(65),Π(66),...;第三序列{Π(i+3M)}、第四序列{Π(i+4M)}、...等；依此類推。M是每一序列的元素個數，也就是滑動視窗的寬度。

承上述，QPP交織器位址產生裝置400的架構如第五圖的範例所示，並與所揭露的某些實施範例一致。第五圖的範例中，QPP交織器位址產生裝置400包含一基礎遞迴單元520、以及L個遞迴單元，此L個遞迴單元以第一遞迴單元511至第L遞迴單元51L來表示，L是大於1的整數。基礎遞迴單元520可用來產生串列輸出，依序計算出交織器位址Π(0),Π(1),Π(2),...,Π(M-1)，交織器位址之初始值Π(0)可設定為一整數的常值，例如0。而第一遞迴單元511至第L遞迴單元51L可用來平行計算出交織器位址，即第一組串列Π(M),Π(M+1),...,Π(2M-1)；第二組串列Π(2M),Π(2M+1),...,Π(3M-1)；至第L組串列Π(LM),Π(LM+1),...,Π((L+1)M-1)。

基礎遞迴單元520與第j遞迴單元於每一次產生交織器位址時，也分別輸出至第一遞迴單元511與第j+1遞迴單元，例如基礎遞迴單元520於每一次產生交織器位址時，輸出至第一遞迴單元511，而第一遞迴單元511於每一次產生交織器位址時，輸出至第二遞迴單元512，而第二遞迴單元512於每一次產生交織器位址時，輸出至第三遞迴單元513，以此類推。此平行計算輸出的數量L也就是滑動視窗的數量。

若滑動視窗的寬度M為2的次冪(power)，例如M=2ⁿ ，則可利用計算出的交織器位址的n個最低有效位元(Least Significant Bit，LSB)來當成所有填入外來資訊之記憶體的位址。

基礎遞迴單元520輸入可配置參數，例如{Π(0)、f₁ +f₂ 、2f₂ }或是{f₁ +f₂ 、2f₂ }，並產生輸出串列Π(0),Π(1),Π(2),...。而每一第i遞迴單元分別輸入可配置參數，例如{Π(i+m₁ )、h(i)、2m₂ f₂ }或是{k、2Mf₂ 、f₁ M+f₂ M² }，1≦i≦L，m₁ 、m₂ 是預定的整數，h(i)是一預定的遞迴函數，m₁ 、m₂ 、h(i)將再詳細說明。此L個遞迴單元並平行產生出L個串列，{Π(i+M)}、{Π(i+2M)}、...、{Π(i+LM)}。換句話說，透過基礎遞迴單元520可實現一種串列交織器位址產生器，而藉由第一至第L遞迴單元可實現一種並列交織器位址產生器。以下是本揭露之QPP交織器位址產生裝置與方法的兩個實施範例的說明。

第一實施範例中，基礎遞迴單元的設計原理是依遞迴公式(1)，並引用遞迴函數g(i)，i=0,1,...,k-1，其中Π(i+1)=(Π(i)+g(i))mod k，g(i)=(f₁ +f₂ +2f₂ i)mod k，且g(i+1)=g(i)+2f₂ 。

所以，基礎遞迴單元可輸入一組可配置參數，如{Π(0)、f₁ +f₂ 、2f₂ }，來依序產生交織器位址Π(0),Π(1),Π(2),...等，其中基礎遞迴單元之硬體結構與時序控制的範例分別如第六A圖與第六B圖所示，並與所揭露的某些實施範例一致。

第六A圖的範例中，可用三個多工器611-613、兩個暫存器621與622、以及兩個2-輸入-相加後取餘數電路631與632，並搭配兩控制訊號init_1與init_2來實現此基礎遞迴單元。第六B圖的範例中，說明兩控制訊號init_1與init_2的時序控制，以及兩個暫存器621與622依此時序控制所暫存的交織器位址Π(i)與函數值g(i)。

2-輸入-相加後取餘數電路是一般取餘數的電路，例如兩加法運算元A和B，經加法運算後，取除數K之後的餘數，即(A+B)mod K，可用兩個加法器和一多工器來實現。以下請一併參考第六A圖與第六B圖，以說明基礎遞迴單元之內部元件之間的運作。

第六A圖中，基礎遞迴單元透過多工器611-613、2-輸入-相加後取餘數電路631、與2-輸入-相加後取餘數電路631，輸入一組可配置參數如{Π(0)、f₁ +f₂ 、2f₂ }後，如第六B圖所示，首先，觸發控制訊號init_1(即init_1的邏輯值為高(high))，此時第六A圖中，多工器613將輸入的參數Π(0)輸出至暫存器622。然後在控制訊號init_1的觸發邊緣降為低值時，觸發控制訊號init_2(即init_2的邏輯值為高(high))，此時第六A圖中，多工器612將輸入的參數f₁ +f₂ ，也就是函數值g(0)，輸出至2-輸入-相加後取餘數電路632。當暫存器622內的Π(0)輸出時，Π(0)同時也饋回2-輸入-相加後取餘數電路632。換句話說，分別藉由觸發控制訊號init_1與init_2，來設定Π(0)與g(0)的初始值。此時，多工器611也會將輸入的參數f₁ +f₂ ，輸出至2-輸入-相加後取餘數電路631。

然後，2-輸入-相加後取餘數電路632的兩加法運算元，即g(0)與Π(0)，經由模數運算後，產生下一個交織器位址Π(1)。而2-輸入-相加後取餘數電路631的兩加法運算元，即f₁ +f₂ 與2f₂ ，經由模數運算後，產生f₁ +f₂ +2f₂ ，也就是g(1)，並輸出至暫存器621。交織器位址Π(1)經由多工器613，再分別被輸出至第一遞迴單元511與暫存器622。換句話說，當Π(1)被輸出至第一遞迴單元511時，暫存器622儲存著Π(1)，而暫存器621儲存著g(1)。

接下來，當暫存器622裡的Π(1)輸出時，Π(1)同時饋回2-輸入-相加後取餘數電路632。而當暫存器621裡的g(1)饋回多工器611時，g(1)同時經由多工器612後輸出至2-輸入-相加後取餘數電路632。多工器611將g(1)輸出至2-輸入-相加後取餘數電路631。因此，2-輸入-相加後取餘數電路632的兩加法運算元，即g(1)與Π(1)，經由模數運算後，產生下一個交織器位址Π(2)。而2-輸入-相加後取餘數電路631的兩加法運算元，即g(1)與2f₂ ，經由模數運算後，產生g(2)並輸出至暫存器621。交織器位址Π(2)經由多工器613，再分別被輸出至第一遞迴單元511與暫存器622。換句話說，當Π(2)被輸出至第一遞迴單元511時，暫存器622儲存著Π(2)，而暫存器621儲存著g(2)。

依此類推，對於每一個i，i=0,1,2,...,M-1，當暫存器622裡的Π(i)輸出後，2-輸入-相加後取餘數電路632的兩加法運算元，即g(i)與Π(i)，經由模數運算後，產生下一個交織器位址Π(i+1)。而2-輸入-相加後取餘數電路631的兩加法運算元，即g(i)與2f₂ ，經由模數運算後，產生g(i+1)並輸出至暫存器621。交織器位址Π(i+1)經由多工器613，再分別被輸出至第一遞迴單元511與暫存器622。

第一實施範例中，第一遞迴單元511至第L遞迴單元51L的設計原理與硬體結構。第一實施範例中，第一遞迴單元511至第L遞迴單元51L是依遞迴公式(2)，並引用另一遞迴函數h(i)來設計。說明如下。

令m=m₁ +m₂ ，因此從遞迴公式(2)Π(i+M)=(Π(i)+f₁ M+f₂ M² +2f₂ i)mod k，可得Π(i+m₁ +m₂ )=(Π(i+m₁ )+f₁ m₂ +2m₁ m₂ f₂ +f₂ m₂ ² +2m₂ f₂ i)mod k，令h(i)=(f₁ m₂ +2m₁ m₂ f₂ +f₂ m₂ ² +2m₂ f₂ i)mod k，故可得h(i+1)=(h(i)+2m₂ f₂ )mod k。

以m₁ =0,M,2M,...；且m₂ =M=32為範例時，可得

Π(i+m₁ +m₂ )=Π(i+0+M)，即Π(32),Π(33),Π(34),...

Π(i+m₁ +m₂ )=Π(i+M+M)，即Π(64),Π(65),Π(66),...

Π(i+m₁ +m₂ )=Π(i+2M+M)，即Π(96),Π(97),Π(98),...

因此，第一遞迴單元511至第L遞迴單元51L中，每一遞迴單元51j的一組輸入參數可設計為{Π(i+m₁ )、h(0)、2m₂ f₂ }，h(0)=(f₁ m₁ +2m₁ m₂ f₂ +f₂ m₂ ² )mod k，而其內部結構如第七圖的範例所示，並與所揭露的某些實施範例一致。

第七圖的範例中，每一遞迴單元51j可用兩個多工器711與712、兩個暫存器721與722、以及兩個2-輸入-相加後取餘數電路731與732，並搭配控制訊號init_1來實現。遞迴單元51j透過多工器711與712、2-輸入-相加後取餘數電路731、與2-輸入-相加後取餘數電路732，輸入一組可配置參數如{Π(i+m₁ )、h(0)、2m₂ f₂ }後，首先，當i=0時，觸發控制訊號init_1(即init_1的邏輯值為高(high))，此時多工器712將輸入的參數h(0)輸出至2-輸入-相加後取餘數電路732。而多工器711將輸入的參數h(0)輸出至2-輸入-相加後取餘數電路731。換句話說，藉由觸發控制訊號init_1，來設定h(0)的初始值。

然後，2-輸入-相加後取餘數電路732的兩加法運算元，即Π(i+m₁ )與h(0)，經由模數運算後，產生交織器位址Π(i+m)並輸出至暫存器722。

2-輸入-相加後取餘數電路731的兩加法運算元，即參數h(0)與參數2m₂ f₂ ，經由模數運算後，產生h(1)並輸出至暫存器721。

暫存器722內的交織器位址Π(i+m)輸出後，當i≧1時，暫存器721內的h(i)輸出至多工器712，h(i)同時饋回多工器711。而多工器712將h(i)輸出至2-輸入-相加後取餘數電路732。2-輸入-相加後取餘數電路732的兩加法運算元，即h(i)與參數Π(i+m₁ )，經由模數運算後，產生下一個交織器位址Π(i+1+m)。交織器位址Π(i+1+m)輸出至下一個遞迴單元，即遞迴單元51(j+1)，Π(i+1+m)同時輸出至暫存器722。

換句話說，遞迴單元51j輸出交織器位址Π(i+m)後，2-輸入-相加後取餘數電路731的兩加法運算元，即h(i)與參數2m₂ f₂ ，經由模數運算後，產生下一個h(i+1)並輸出至暫存器721；而2-輸入-相加後取餘數電路732的兩加法運算元，即h(i+1)與參數Π(i+1+m₁ )，經由模數運算後，產生下一個交織器位址Π(i+1+m)並輸出至下一個遞迴單元，而暫存器722儲存著交織器位址Π(i+1+m)。

第二實施範例中，基礎遞迴單元的設計原理是依遞迴公式(1)，其中，輸入可配置參數{f₁ +f₂ 、2f₂ }，其結構如第八圖的範例所示，並與所揭露的某些實施範例一致。第八圖的範例中，基礎遞迴單元可包含一多工器810、兩暫存器821與822、以及兩個2-輸入-相加後取餘數電路831與832。可配置參數，f₁ +f₂ 與2f₂ ，輸入基礎遞迴單元後，再藉由多工器810、暫存器821與822、以及兩個2-輸入-相加後取餘數電路831與832，而直接依序算出交織器位址Π(0),Π(1),Π(2),...。暫存器821與822的初始值可分別設定為0與Π(0)。暫存器821與822裡的值可在時脈邊緣(clock edge)時進行更換。

第二實施範例中，第一至第L遞迴單元的設計原理是依遞迴公式(2)，其硬體結構的一個範例示意圖如第九圖所示，並與所揭露的某些實施範例一致。第九圖的範例中，第j遞迴單元91j可先分別輸入可配置參數，如2Mf₂ 與f₁ M+f₂ M² ，再經由一暫存器920、以及兩個2-輸入-相加後取餘數電路931與932，而依序算出交織器位址，也就是第j串列{Π(i+jM)}。暫存器920裡的值為2(j-1)M² f₂ ，例如j=1時，遞迴單元911之暫存器裡的值為0；而j=2時，遞迴單元912之暫存器裡的值為2M² f₂ 。

第十圖是一範例架構示意圖，說明QPP交織器位址產生裝置400如何使多個滑動視窗平行輸出多筆資料至記憶體。參考第十圖，QPP交織器位址產生裝置400根據輸入的數個可配置參數430，如{k、(f₁ +f₂ )mod k、2f₂ mod k、2Mf₂ mod k、f₁ M mod k、f₂ M² mod k}或是{k、f₁ +f₂ 、2f₂ 、2Mf₂ 、以及f₁ M+f₂ M² }，產生交織器位址Π(i)、Π(i+M)、Π(i+2M)、...、Π(i+LM)，並輸出記憶體選擇(memory selection)資訊1020至一資料多工器1010，此記憶體選擇資訊1020是Π(i)、Π(i+M)、Π(i+2M)、...、Π(i+LM)之部分位元的資訊，例如最高有效n位元(MSB n bits)的資訊。資料多工器1010接收多個滑動視窗840平行輸出的多筆資料1030，以及來自QPP交織器位址產生裝置400的記憶體選擇資訊1020後，就會將多筆資料1030之每一筆資料輸出至所選擇之記憶體的一相對應的記憶體位址，這些相對應的記憶體位址1050可從QPP交織器位址產生裝置400直接算出之交織器位址來得到。

以k=40，M=8=2³ 為例，第十一圖說明QPP交織器位址產生裝置400如何使五個滑動視窗平行輸出的多筆資料被填入QPP交織器位址產生裝置400所產生的記憶體位址。第十一圖的範例中，輸入序列的資訊區塊長度k=40，每一滑動視窗的寬度M=8。當QPP交織器位址產生裝置400平行算出交織器位址Π(i)、Π(i+8)、Π(i+16)、...、Π(i+40)時，同時輸出Π(i)、Π(i+8)、Π(i+16)、...、Π(i+40)之最高有效3個位元的資訊至資料多工器1010。資料多工器1010同時接收五個滑動視窗平行輸出的五筆資料，以及Π(i)、Π(i+8)、Π(i+16)、...、Π(i+40)之最高有效3位元1120的資訊後，將此五筆資料平行輸出至五塊記憶體之記憶體位址內，此五塊記憶體是由Π(i)、Π(i+8)、Π(i+16)、...、Π(i+40)之最高有效3位元來決定，其記憶體位址1150是由Π(i)之最低有效3位元(LSB 3bits)來決定，也就是說，此五筆資料平行輸出至五塊不同記憶體，而此五塊不同記憶體皆分別以相同記憶體位址來儲存此五筆資料。

換句話說，當M=2ⁿ 時，如第十二圖之QPP交織器位址產生裝置的範例所示，基礎遞迴單元520算出的交織器位址Π(i)中，其最低有效n位元是提供給所有記憶體的位址用，而其最高有效n位元是提供給一資料多工器，例如某一對數-對應處理器之資料多工器，來選擇一記憶體；而每一遞迴單元j，j=0,1,...,31，算出的交織器位址Π(i+jM)中，其最高有效n位元是提供給一資料多工器，例如另一對數-對應處理器之資料多工器，來選取一記憶體。n可視為記憶體之位址匯流排(address buses)的位元數，也就是說，每一記憶體有2ⁿ 個記憶體位址。

第十三圖的範例中，以k=40、M=2³ 、f₁ =3、f₂ =10為例，說明透過QPP交織器位址產生裝置算出的交織器位址，如何決定出記憶體位址，與所揭露的某些實施範例一致。假設Π(0)=0，基礎遞迴單元根據遞迴公式(1)，依序算出Π(1)=13，Π(2)=6，Π(3)=19，Π(4)=12，Π(5)=25，Π(6)=18，以及Π(7)=31。當i=0，Π(0)=0=(000000)₂ 時，其最低有效3位元是(000)₂ ，提供給記憶體0-4的位址用。其最高有效3位元是(000)₂ ，資料多工器依此將滑動視窗0輸出的資料傳送至記憶體0。

i=0時，遞迴單元1根據遞迴公式(2)，算出Π(8)=24=(011000)₂ ，其最高有效3位元是(011)₂ =3，資料多工器依此將滑動視窗1輸出的資料傳送至此記憶體3。遞迴單元2根據遞迴公式(2)，算出Π(16)=8=(001000)₂ ，其最高有效3位元是(001)₂ =1，資料多工器依此依此將滑動視窗2輸出的資料傳送至記憶體1。遞迴單元3根據遞迴公式(2)，算出Π(24)=32=(100000)₂ ，其最高有效3位元是(100)₂ =4，資料多工器依此將滑動視窗3輸出的資料傳送至記憶體4。遞迴單元4根據遞迴公式(2)，算出Π(32)=16=(010000)₂ ，其最高有效3位元是(010)₂ =2，資料多工器依此將滑動視窗4輸出的資料傳送至記憶體2。

類似地，i=1時，Π(1)=13==(001101)₂ ，因此提供最低有效3位元(101)₂ 給記憶體0-4的位址用，其最高有效3位元是(001)₂ ，資料多工器將滑動視窗0輸出的資料傳送至記憶體1。遞迴單元1-4平行算出Π(9)=(100101)₂ ，Π(17)=(010101)₂ ，Π(25)=(000101)₂ ，Π(33)=(011101)₂ ，資料多工器將滑動視窗1-4輸出的資料平行傳送至記憶體4，2，0，3。所以，在i=7時，可平行傳送最後的5筆資料至記憶體0-4。每一記憶體有8個位址，被寫入8筆滑動視窗輸出的資料。

第十四圖是一範例圖表，說明上述40筆經由滑動視窗輸出的資料，亦即資料輸入索引i=0,1,2,...,39，相對應的交織器位址Π(i)、其二位元表法、其最低有效3位元、以及記憶體。從第十四圖中可以看出，針對特定滑動視窗寬度(此例為8)在計算上不需使用複雜的電路，如乘法器，並且輸出資料填入的記憶體0-4的位址皆相同。

本揭露之直接計算輸出資料之記憶體位址與習知技術利用大量記憶體的架構相較，可大幅減低硬體面積，例如應用在行動通訊(3GPP LTE)系統上時，可降低晶片面積。由於硬體的低複雜度，M的值與L的值也容易配合滑動視窗的輸出順序來做調整和設計。

承上述，第十五圖是QPP交織器位址產生方法的一範例流程圖，與所揭露的某些實施範例一致。參考第十五圖，根據QPP函數Π(i)=(f₁ i+f₂ i² )mod k，輸入多個可配置參數，如步驟1510所示。步驟1520中，藉由一基礎遞迴單元，依序產生出多個交織器位址，即Π(0),Π(1),Π(2),...。步驟1530中，藉由L個遞迴單元，以第一至第L遞迴單元表示，平行產生出L組相對應的交織器位址，其中，此基礎遞迴單元與第j遞迴單元於每一次產生交織器位址時，也分別輸出至此第一遞迴單元與第j+1遞迴單元，Π(i)是此方法產生的第i個交織位址，f₁ 與f₂ 是QPP係數，k是一輸入序列的資訊區塊長度，如此，讓此輸入序列之資訊填入多個相對應之記憶體的位址，0≦i≦k-1，1≦j≦L-1。

步驟1520中，基礎遞迴單元可根據遞迴公式(1)直接算出Π(0),Π(1),Π(2),...。而步驟1530中，第一遞迴單元至第L遞迴單元可根據遞迴公式(2)，平行算出L組相對應的序列，第j組交織器位址也就是第j串列{Π(i+jM)}，如前述及第五圖的範例所示，不再說明。

當M=2ⁿ 時，如前述第十二圖、第十三圖的範例所示，基礎遞迴單元算出的每一交織器位址Π(i)中，可利用其最低有效n位元是作為所有記憶體的位址用，而其最高有效n位元則可提供給一資料多工器，來從多個記憶體中選擇一記憶體。於每一次遞迴計算時，第一遞迴單元至第L遞迴單元平行算出的L個交織器位址中，其最高有效n位元可提供給一資料多工器，來選擇出L個相對應的記憶體。藉由最高有效n位元所選出的記憶體，以及最低有效n位元所指定的位址，輸入序列的每一筆資訊就可以被寫入一相對應之記憶體位址內。

綜上所述，本揭露之實施範例可提供一種QPP交織器位址產生裝置與方法，可直接計算交織器位址，並可平行輸出或串列輸出交織器位址的計算結果，根據此交織器位址的計算結果，透過一資料多工器，輸入序列的每一筆資訊就可以被填入一相對應之記憶體位址內。此設計不需使用複雜的電路，如乘法器，也無需花費儲存交織器位址的記憶體容量。可降低硬體的低複雜度，也容易配合滑動視窗的輸出順序來做調整和設計，可應用在如行動通訊系統上的編解碼器。

惟，以上所述者僅為本揭露之實施範例，當不能依此限定本發明實施之範圍。即大凡本發明申請專利範圍所作之均等變化與修飾，皆應仍屬本發明專利涵蓋之範圍。

110‧‧‧滑動視窗

110a‧‧‧外來資訊

120‧‧‧位址表格

130‧‧‧記憶體

121‧‧‧位址表格

125‧‧‧一組資料多工器

210、220、230、240、250‧‧‧表格

221-224‧‧‧列間排列序列

300‧‧‧QPP交織器

310‧‧‧交織器記憶體

320‧‧‧位址產生器

330‧‧‧控制單元

331‧‧‧模數計數器

400‧‧‧QPP交織器位址產生裝置

f₁ 、f₂ ‧‧‧QPP係數

K‧‧‧輸入序列的資訊區塊長度

M‧‧‧k的一個除數

430‧‧‧數個可配置參數

520‧‧‧基礎遞迴單元

Π(i)‧‧‧第i交織器位址

L、M‧‧‧大於1的整數

511-51L‧‧‧第一至第L遞迴單元

611-613‧‧‧多工器

621、622‧‧‧暫存器

Init_1、Init_2‧‧‧控制訊號

631、632‧‧‧2-輸入-相加後取餘數電路

711、712‧‧‧多工器

721、722‧‧‧暫存器

h(i)‧‧‧遞迴函數

731、732‧‧‧2-輸入-相加後取餘數電路

810‧‧‧多工器

821、822‧‧‧暫存器

831、832‧‧‧2-輸入-相加後取餘數電路

920‧‧‧暫存器

931、932‧‧‧2-輸入-相加後取餘數電路器

1210‧‧‧資料多工器

1220‧‧‧記憶體選擇資訊

1030‧‧‧多筆資料

1040‧‧‧多個滑動視窗

1050‧‧‧記憶體位址

1120‧‧‧最高有效3位元

1150‧‧‧記憶體位址

1510‧‧‧根據QPP函數Π(i)=(f₁ i+f₂ i² )mod k，輸入多個可配置參數

1520‧‧‧藉由一基礎遞迴單元，依序產生出多個交織器位址

1530‧‧‧藉由L個遞迴單元，以第一至第L遞迴單元表示，平行產生出L組相對應的交織器位址，其中，此基礎遞迴單元與第j遞迴單元於每一次產生交織器位址時，也分別輸出至此第一遞迴單元與第j+1遞迴單元，Π(i)是此方法產生的第i個交織位址，f₁ 與f₂ 是QPP係數，k是一輸入序列的資訊區塊長度，如此，讓此輸入序列之資訊填入多個相對應之記憶體的位址，0≦i≦k-1，1≦j≦L-1

第一A圖是一個範例示意圖，說明在一串列架構中，藉由一位址表格輸出交織器位址，以將外來資訊填入相對應的記憶體位址。

第一B圖是一個範例示意圖，說明一平行架構中，藉由一位址表格輸出交織器位址，以將外來資訊填入相對應的記憶體位址。

第二圖是可用來產生渦輪碼交織器之記憶體位址之表格的一個範例示意圖。

第三圖是一種QPP交織器的一個範例示意圖。

第四圖是QPP交織器位址產生裝置的一個範例示意圖，與所揭露的某些實施範例一致。

第五圖是QPP交織器位址產生裝置之架構的一個範例示意圖，與所揭露的某些實施範例一致。

第六A圖是一第一實施範例中，基礎遞迴單元之硬體結構的一個範例示意圖，與所揭露的某些實施範例一致。

第六B圖是第六A圖之基礎遞迴單元中，控制訊號之時序控制的一個範例示意圖，與所揭露的某些實施範例一致。

第七圖是一第一實施範例中，第一遞迴單元至一第L遞迴單元之硬體結構的一個範例示意圖，與所揭露的某些實施範例一致。

第八圖是一第二實施範例中，基礎遞迴單元之硬體結構的一個範例示意圖，與所揭露的某些實施範例一致。

第九圖是一第二實施範例中，第一遞迴單元至一第L遞迴單元之硬體結構的一個範例示意圖，與所揭露的某些實施範例一致。

第十圖是一範例架構示意圖，說明QPP交織器位址產生裝置如何使多個個滑動視窗平行輸出多筆資料至記憶體，與所揭露的某些實施範例一致。

第十一圖是一範例架構示意圖，說明QPP交織器位址產生裝置如何使五個滑動視窗平行輸出的多筆資料被填入記憶體，與所揭露的某些實施範例一致。

第十二圖說明QPP交織器位址產生裝置中，每一疊代單元算出的交織器位址之位元的用途，與所揭露的某些實施範例一效。

第十三圖以k=40、M=2³ 、f₁ =3、f₂ =10為例，說明透過QPP交織器位址產生裝置算出的交織器位址，如何決定出記憶體的位址，與所揭露的某些實施範例一致。

第十四圖是一範例圖表，說明第十三圖中之滑動視窗輸出資料相對應的交織器位址Π(i)、其二位元表法、其最低有效3位元、以及記憶體，與所揭露的某些實施範例一致。

第十五圖是QPP交織器位址產生方法的一範例流程圖，與所揭露的某些實施範例一致。

400‧‧‧QPP交織器位址產生裝置

L、M‧‧‧大於1的整數

520‧‧‧基礎遞迴單元

511-51L‧‧‧第一至第L遞迴單元

Claims

一種二階重排多項式(QPP)交織器位址產生裝置，該裝置包含：一基礎遞迴單元；以及L個遞迴單元，表示為第一至第L遞迴單元，L≧2;該裝置根據一QPP函數Π(i)=(f₁ i+f₂ i² )mod k，輸入多個可配置參數，並藉由該基礎遞迴單元依序產生出多個交織器位址，藉由該第一至第L遞迴單元平行產生出L組相對應的交織器位址，其中，該基礎遞迴單元與該第j遞迴單元於每一次產生交織器位址時，也分別輸出至該第一遞迴單元與該第j+1遞迴單元，Π(i)是該裝置產生的第i個交織器位址，f₁ 與f₂ 是QPP係數，k是一輸入序列的資訊區塊長度，0≦i≦k-1，1≦j≦L-1，mod是模數運算。
如申請專利範圍第1項所述之交織器位址產生裝置，該位址產生裝置藉由該第一至第L遞迴單元中第j遞迴單元，產生出一相對應的第j串列{Π(i+jM)}，j=1,…,L，M=k/L。
如申請專利範圍第2項所述之交織器位址產生裝置，其中該M等於2ⁿ ，n為一正整數。
如申請專利範圍第1項所述之交織器位址產生裝置，其中該基礎遞迴單元包括k1個多工器、k2個暫存器、以及k3個2-輸入-相加後取餘數電路，並且根據k4個可配置基礎參數，與藉由該k1個多工器、該k2個暫存器、以及該k3個2-輸入-相加後取餘數電路，依序產生出該多個交織器位址，k1、k2、k3、k4皆為正整數，且k2≧2，k3≧2，k4≧2。
如申請專利範圍第2項所述之交織器位址產生裝置，其中該第j遞迴單元包括n1個多工器、n2個暫存器、以及n3個2-輸入-相加後取餘數電路，並且根據一組可配置參數，藉由該n1個多工器、該n2個暫存器、以及該n3個2-輸入-相加後取餘數電路，產生出該相對應的第j串列{Π(i+jM)}，n1≧0，且n2≧1，n3≧2。
如申請專利範圍第3項所述之交織器位址產生裝置，其中該交織器位址Π(i)之最低有效n位元是作為該輸入序列之多筆資料填入所有記憶體的位址，i=0,1,…,k-1。
如申請專利範圍第3項所述之交織器位址產生裝置，其中該L個遞迴單元每一次疊代平行產生出的L個交織器位址之最高有效n位元是提供給一資料矩陣多工器，來選取L個相對應的記憶體。
如申請專利範圍第3項所述之交織器位址產生裝置，其中該基礎遞迴單元根據一遞迴公式直接依序算出該交織器位址Π(i)，i=0,1,…,k-1，而該L個遞迴單元根據另一遞迴公式平行產生出該L組相對應的交織器位址。
如申請專利範圍第1項所述之交織器位址產生裝置，該裝置藉由該L個遞迴單元，來實現一種並列交織器位址產生器。
如申請專利範圍第1項所述之交織器位址產生裝置，該裝置藉由該基礎遞迴單元，來實現一種串列交織器位址產生器。
如申請專利範圍第1項所述之交織器位址產生裝置，該裝置也是一種反交織器位址產生裝置，其中該產生出的多個交織器位址是該反交織器位址產生裝置用來讀取一記憶體的位址。
如申請專利範圍第4項所述之交織器位址產生裝置，其中k1等於3，k2等於2，k3等於2，k4等於3，並且該基礎遞迴單元還搭配兩個控制訊號來運作。
如申請專利範圍第4項所述之交織器位址產生裝置，該裝置還包括L個2-輸入-相加後取餘數電路，且k1等於1，k2等於2，k3等於2，k4等於2。
如申請專利範圍第5項所述之交織器位址產生裝置，其中n1等於2，n2等於2，n3等於2，該組可配置參數包括三個可配置參數，並且該第j遞迴單元還搭配一個控制訊號來運作。
如申請專利範圍第5項所述之交織器位址產生裝置，其中n1等於0，n2等於1，n3等於2，並且該組可配置參數包括兩個可配置參數。
一種二階重排多項式(QPP)交織器位址產生方法，應用於一通訊系統上的編解碼器，該方法包含：根據一QPP函數Π(i)=(f₁ i+f₂ i² )mod k，輸入多個可配置參數，f₁ 與f₂ 是該QPP函數的係數，k是一輸入序列的資訊區塊長度，0≦i≦k-1，mod是模數運算；藉由一基礎遞迴單元依序產生出多個交織器位址；以及藉由L個遞迴單元，以第一至第L遞迴單元表示，平行產生出L組相對應的交織器位址，L是大於1的整數；其中，該基礎遞迴單元與第j遞迴單元於每一次產生交織器位址時，也分別輸出至該第一遞迴單元與第j+1遞迴單元，Π(i)代表該方法產生出的第i交織器位址，以讓該輸入序列之資訊填入多個相對應之記憶體位址。
如申請專利範圍第16項所述之交織器位址產生方法，其中該第一至第L遞迴單元中每一第j遞迴單元，根據一第二遞迴公式與一第二組可配置參數，平行產生出一相對應的第j串列{Π(i+jM)}，j=1,…,L，M=k/L，L是大於1的整數，1≦i≦L。
如申請專利範圍第17項所述之交織器位址產生方法，其中該第二組可配置參數是{Π(i+m₁ )、h(0)、2m₂ f₂ }與{k、2Mf₂ 、f₁ M+f₂ M² }之其中一組可配置參數，m₁ 、m₂ 是預定的整數，h(0)=(f₁ m₁ +2m₁ m₂ f₂ +f₂ m₂ ² )mod k。
如申請專利範圍第16項所述之交織器位址產生方法，其中該基礎遞迴單元根據一第一組可配置參數與一第一遞迴公式，依序產生出串列{Π(i)}，i=0,1,…,M-1。
如申請專利範圍第19項所述之交織器位址產生方法，其中該第一組可配置參數是{Π(0)、f₁ +f₂ 、2f₂ }與{f₁ +f₂ 、2f₂ }之其中一組可配置參數。
如申請專利範圍第16項所述之交織器位址產生方法，其中該多個可配置參數是{k、(f₁ +f₂ )mod k、2f₂ mod k、2Mf₂ mod k、f₁ M mod k、f₂ M² mod k}與{k、f₁ +f₂ 、2f₂ 、2Mf₂ 、以及f₁ M+f₂ M² }之其中一組可配置參數。
如申請專利範圍第17項所述之交織器位址產生方法，其中該M等於2ⁿ ，n為一正整數。
如申請專利範圍第22項所述之交織器位址產生方法，其中該基礎遞迴單元算出的每一交織器位址Π(i)中，Π(i)為N個位元，N為大於等於n的正整數，其最低有效n位元是作為該多個相對應之記憶體的位址用，而其最高有效(N-n)位元是用來從該多個相對應之記憶體中選出一記憶體。
如申請專利範圍第22項所述之交織器位址產生方法，其中該基礎遞迴單元算出的每一交織器位址Π(i)，Π(i)為N個位元，N為大於等於n的正整數，其中該第一至第L遞迴單元平行算出的L個交織器位址中，其最高有效(N-n)位元是用來選出L個相對應的記憶體。
如申請專利範圍第17項所述之交織器位址產生方法，其中該輸入序列之資訊是透過L個滑動視窗平行輸出的，而M是滑動視窗的寬度。