TW577211B - Turbo decoding method and apparatus for wireless communications - Google Patents

Description

發明範疇 本發明係有關於通信領域，而更明確而言，係有關無線 通信。 發明背景 錯誤控制碼可提供在接收端上使用的一連串資料符號通 信冗餘’用以在出現雜訊與干擾中將資料符號的原始序列 再生。在CDMA無線通信系統中，具Viterbi解碼器的捲積 碼於功率文限通道與干擾受限通道上已廣泛用來達成可靠 的通# °私為加速碼的一新類型的錯誤修正碼可進一步提 冋傳統碼的效率。在一接收器上的加速碼的解碼處理包括 有關接收器的複雜與密集計算的反覆演算法。 因此’在使用加速碼的通信系統中，有關一改良解碼器 的技藝是需要的。 發明概述 在一通k系統中，用以解碼一連串加速編碼資料符號之 方法及裝置。本發明的各種不同觀點是以由各種不同節點 與連接分枝所組成的圖式表示。節點是包括通道節點、符 號即點、狀態節點、與計算節點等不同類型。連接節點的 刀枝允许從一節點到另一節點的訊息流。節點與分枝能經 由軟體、硬體、或兩者組合實施。一節點是透過傳送具有 根據輸入訊息值的一值的輸出訊息而更新。在一具體實施 例中’通道節點Rx、心和！^是根據一接收的通道輸出而更 新，而且來自符號節點的輸出訊息會被初始化。該等符號 節點是與通道節點RX、\和1通信。計算節點C*D的更

本紙張尺度iteg g家料(CNS)織格(2ι()χ;^) 577211

新是根據_觸發排程而執行。在—具體實施例中，計算節 ••占C和D的更新可於所有可能時間同時觸纟。觸發排程可 重複：獲知解碼處理的一或多個重複。在一或多個重複 之後付號即點可保持該等解碼符號的一值。結果，解碼 處理可有效率、正確、與迅速地執行。 圖式之簡單說明 本發月的特徵、目的、與優點可從下面連同附圖的詳細 描述而變得更顯然，相同參考數字係表示類似元件，並 中： 〃 圖1係描述根據本發明的各種不同具體實施例來操作的 通信系統； 圖2係描述一編碼器的方塊圖； 圖3係描述一格柵圖； 圖4係描述一加速編碼器的方塊圖； 圖5係描述一解碼器的方塊圖； 圖6係根據本發明的各種不同具體實施例而描述在用以 解碼一連串的編碼資料符號的各種不同類型節點之間的資 訊流圖；及 圖7係根據本發明的各種不同具體實施例而描述在用以 解碼一連串編碼資料符號的各種不同類型節點之間的一般 資訊流圖式。 較佳具體實施例之詳細說明 本發明的各種不同具體實施例係結合在根據劃碼多工存 取（CDMA)技術而操作的無線通信系統，且該劃碼多工存

L--—__-5- 本紙張尺度適用中國國家標準(CNS) A4規格(2_ι〇χ297公爱)- 577211 A7 B7 五、發明説明（3 ) 取技術 已在丁elecommunication Industry Association (TIA)、Third Generation Partnership Project (3GPP)與 Third Generation Partnership Project 2 (3 GPP2)出版的各 種不同標準中揭示及描述。此標準包括TIA/EIA-95標準、 TIA/EIA-IS-856標準、IMT-2000標準（包括cdma2000標準 與WCDMA標準），其在此僅列出供參考。標準的副本可在 網址http://www.3qpp2.org上透過存取全球資訊網而獲 得，或窝信到 TIA，Standards and Technology Department， 2500 Wilson Boulevard, Arlington, VA 22201, United States of America。通常視為在此僅列出供參考WCDMA標 準的此標準可透過與 3GPP Support Office，650 Route des Lucioles-Sophia Antipolis，Valbonne-France聯絡而獲得。 一般而言，一新改良方法與一伴隨裝置的提供可有效率 將在通信系統中的一連串編碼資料符號解碼。在此描述的 一或多個具體實施例是在一數位無線資料通信系統的本文 中發表。雖然在本文的使用是有利的，但是本發明的不同 具體實施例可合併在不同環境或結構。大體上，在此描述 的各種不同系統能使用軟體控制的處理器、積體電路、或 非連續邏輯而形成。本專利參考的資料、指令、命令、資 訊、信號、符號、與晶片能有利地以電壓、電流、電磁 波、磁場或粒子、光學場或粒子、或組合表示。此外，在 每個方塊圖中顯示的方塊係表示硬體或方法步驟。 圖1是在通道上操作的包括一發射器及一接收器的通信 系統1 0方塊圖。在傳輸端，系統1 〇包括編碼器i 2，用來 ___________-6-__ 本紙張尺度適用中國國家標準(CNS) A4規格(21〇 X 297公釐） 裝 訂

577211

接收一編碼操作的輸入資料序列。編碼器1 2是將一編碼資 料序列輸出給調變器14。調變器14是調變在載波信號上的 編碼資料序列。調變器14是將結果信號提供給發射器ι6。 發射器16包括在一額外白色高斯雜訊（Awgn)通道1 7上傳 送信號所需的一功率放大器及一天線。一接收器1 8可接收 仏號。接收的信號是透過一解調變器丨9來解調變，且並轉 送給一解碼器2 〇。解碼器2 〇可輸出輸入資料序列的評估。 凋變器1 4、發射器1 ό、接收器1 8、與解調變器1 9的操作 是根據在相關技藝中的已知技術。 編碼器12包括一捲積編碼器，其是以對應許多輸入資料 位元（k)所產生碼字中的編碼符號（η)量的一編碼率（k/n) 來編碼。一限制長度（K)亦定義成在資料的捲積編碼中所 使用移位暫存器的長度。捲積編碼器是以具二進位係數與 長度K- 1的一有限脈衝反應濾波器來操作。編碼器具有2 到（K-1)個可能狀態的平方。 請即參考圖2，其係顯示根據具體實施例而使用在系統 10的一捲積編碼器100的方塊圖。編碼器1〇〇是輸入資料符 號Xi及輸出由編碼符號&和Yi組成的碼字。因此，編碼是 在一編碼率1 /2 ^下標，，丨"是表示時間範例的索引。一編碼 器110是根據多項式來編碼輸入的資料符號&，以產生資 料符號Yi。多項式可根據一捲積碼。此一多項式的實施包 括一進位正反器111和112。二進位正反器ηι*η2可以分 別在狀態"D 0 ’’和” 〇丨” ^狀態D 〇和D丨在任何時間可以是 狀態"〇"或"1"。在系統10，編碼的資料符號&和Yi是在 本紙張尺度適用中國國家標準(CNS)^ii7210 x 297公复了

裝 訂

577211 A7

AWGN通道17上傳送給接收器j =然它疋不需要’μ可了解到最佳解碼器的碼特性或 f =格柵圖上呈現碼。-格栅圖是-編碼器狀態圖的 典窮魏。在格栅的—位準上的節點（狀態）係透過經由對 應到如狀態圖決定的-輸入位元的一分枝的傳送，而可從 先前位準的節點(狀態)到達。例如狀態度量、路徑度量血 分枝度量的數個類型度量能使用在解碼處理。最可能的路 徑能以某些較高程度來選取。對應該選擇路徑的每個分枝 符號的碼字是最有可能的傳輸碼字組。 請即參考圖3，-格柵20〇是在解碼器2〇上用來將接收的 編碼資料符號Xi*Yi解碼。格柵2〇〇係分別顯示狀態空間 201、202和203、在時間y、，] ”和” i+1，，的正反器⑴和 112的狀怨。四個可能狀態211、212、213和2丨4是與具體 實施例所示的每個狀態空間有關。例如，狀態2ii、212、 213和214係分別表示在可能狀態”〇〇"、”1〇"、，|〇1，，和|，11|· 的正反器111和112的狀態。從一空間狀態的狀態轉變成另 一狀態空間的另一狀態是透過不同的可能碼字分枝顯示β 每個分枝係表示編碼符號&和Yi的特殊選擇。例如，碼字 分枝π ο 1n係表示資料符號Xi的” 0，，值、與資料符號Yi的，· i " 值。碼字分枝” 〇 1 ”係表示正反器u丨和112在時間範例上從 一狀態2間的狀態213轉變成在下一時間範例的另一狀態 空間的狀態2 11、及從在時間範例上的一狀態空間的狀態 214轉變成在下一時間範例上的另一狀態空間的狀態214。 對於一比率1/2而言，在每個狀態的每個狀態可由至少兩 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公爱) 577211 A7 B7 五、發明説明（ 可能碼字分枝到達。 根據各種不同具體實施例，在解調變器1 9中的一相關器 可根據通道輸出而決定每個接收編碼資料符號的機率。與 每個接收編碼資料符號有關的機率是儲存在一記憶體元 件。每個資料符號Xi和Yi的決定機率可用來決定一分枝度 量（通道度量）。 普遍已知為MAP演算法之一演算法是使用在解碼處理。 格栅200的解碼處理包括以向前與反向方式而同時從初始 狀態空間與最後狀態空間來決定狀態度量與路徑度量。一 軟決定可在對應在格柵狀態空間的時間來判斷如分枝所示 的編碼資料符號Xi和Yi的值。若要進行編碼資料符號Xi和 Yi值的軟決定，每個分枝的雙重度量（DM)可決定。一分枝 的DM是根據一前向狀態度量（FSM)、一向後狀態度量 (BSM)與一分枝度量（BM)。DM可以是FSM、BSM和BM的 總數。一分枝的BM是根據通道輸出而決定。 一狀態的FSM可根據一前向路徑度量（FPM)。在一分枝 結束的FPM是等於在分枝開始點上狀態的FSM與分枝BM的 加總。在格柵初始狀態空間上狀態的FSM可能是已知或預 先決定。除了在格柵初始狀態空間的狀態之外，一狀態的 FSM是等於從初始狀態空間開始與狀態結束的路徑FPM最 小值。一狀態的BSM是根據向後路徑度量（BPM)。一分枝 結束的BPM是等於分枝開始點上狀態的BSM與分枝的 BM。在格柵最後狀態空間的狀態BSM是已知或預先決 定。除了在格栅的最後狀態空間的狀態之外，一狀態的 -9- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 裝 訂 577211 A7 B7 五、發明説明 BSM是等於在狀態開始與在最後狀態空間的狀態結束的路 徑BPM的一般最小值。如此’從一初始狀態與一最後狀態 的狀態空間的FSM、BSM、與BM能以連續方式決定，直到 來自兩方向的路徑到達相對端，以決定所有分枝的dm為 止。一分枝的DM是根據在來自向前方向的分枝結束上狀 態的FSM、在來自反向方向的分枝結束上的狀態bsm、與 分枝的BM。 裝 在兩連續狀態空間之間的分枝DM可組成兩群。由具一 Xi付號碼字的分枝所組成的第一群是等於” ” β由具一 Xi 符號碼字分枝所組成的第二群是等於”丨”。一般最小量的 第一群（GMBO)與一般最小量的第二群（(}1^31)可決定^ Xi 符號的軟決定會是在GMBO與GMB 1之間的差。碼字的其他 負料符號的軟決定可同樣透過將分枝分成兩群而決定。第 訂

群具有等於” 0 ’’的資料符號，且第二群是等於„ 1 ,，。資料 符號的軟決定是等於在GMB0與GMB1之間的差。 格柵的每個分枝係表示由許多資料符號所組成的碼字。 例如，對於一編碼率1/2而言，在格栅2〇〇所示每個分枝中 的碼字係表示資料符號&與1的值。如果發射器的編碼器 是以編碼率1/3傳送編碼的資料符號，三個資料符號便會 f每個輸入資料符號產生。在此一範例中，每個分枝的碼 字係表示三個資料符號' 叫即參考圖4，其係顯示一傳統編碼率1 /3加速編碼器 400的一般方塊圖。一般而言，一編碼率加速編碼器包 括土少兩平行編碼器。加速編碼器400包括一第一組成碼

577211

401與一第二組成碼々ο]與一碼交錯器403。資料符號&是 以一輸入410輸入加速編碼器4〇(^第一組成碼4〇1會輸入 資料符號Xi，以產生編碼的資料符號Yi。碼交錯器403會接 收用以資料符號Xi，用以交錯資料符號以產生資料符號

Xk。資料符號Xk是由重新配置的資料符號Xi所組成。第二 組成碼402可編碼資料符號Xk及輸出資料符號Zk。用於第 一及第二組成碼4〇 1和402的編碼資料符號的多項式可相同 或不同。在第一及第二組成碼4〇1和4〇2的編碼是根據圖2 所示的捲積碼1 1 0。 誣料苻號Xi、Yi、與Zk會傳遞給一收縮處理方塊（未在圖 顯示），用以傳取用以傳輸的資料符號。選擇是根據一收 縮圖案。選取的資料符號是完全來自資料符號Xi' I和 zk。在系統10中，選取的資料符號是傳遞給調變器14，用 以調變及傳送給接收器18。解碼器20可接收資料符號\、 Yi和zk的雜訊部份。 1 請即參考圖5，一解碼器500的方塊圖是用於解碼資料符 號Xi、Yi*Zk的雜訊部份，以產生資料符號&的評估。解 碼器500是使用在系統10的解碼器20。編碼資料符號Xi、Yi 和4的雜訊部份是傳遞給一資料符號選擇器方塊^。，以 選取用以路由給在一輸入542上的解碼器方塊5G1的資料符 號2和Yi的雜訊部份。資料符號&的雜訊部份是内部傳遞 ^交錯器599 ’以局部再生資料符號&的雜訊部份。資料 符號Xk*Zk的局部產生雜訊部份是傳遞給在一輸入“❻上 的解碼器方塊5〇2。解碼器5〇1係根據如圖描述及顯示驗 巧張尺度適财®料料(CNS)威格(⑽χ 29?公爱

裝 訂

五、發明説明（9 ) 的一解碼處理來解碼資料符號\和1的雜訊部份。解碼器 501會在一輸出550上產生資料符號&的評估。解碼器5〇2 係根據例如圖描述及顯示MAP的一解碼處理來解碼資料符 號Zk*Xk的雜訊部份。解碼器5〇2會在一輸出56〇上產生資 料符號Xk的評估。在解碼器501和5〇2的解碼處理是連續執 行。在το成每個重複之後，資訊可從解碼器5〇丨傳遞給解 碼器502。在技藝中熟諳此技者可了解到在如圖描述及顯 示的各種不同具體實施例的解碼器是在編碼資料符號的雜 訊部份上工作。 若要增加資料符號Xi評估可信度以保持一真值，在輸出 550的資料符號&評估會傳遞給一交錯器53〇，以便在解碼 器502的一輸入532上產生資料符號心的評估。解碼器5〇2 是使用在輸入532上的資料符號义的評估與在輸入54〇上的 資料符號的評估，以便在輸出56〇上產生資料符號心的新 評估。在輸出560上的資料符號心的評估是傳遞給一解交 錯器531，以便於加速碼4〇〇中將交錯器43〇的交錯功能處 理反向，且在一輸入541上產生資料符號&的評估。在輸 入541上的資料符號Xi的評估是與在輸入542上的資料符號 評估一起使用，以便在輸出550上產生資料符號兄的一新 評估。處理可重複，直到資料符號幻評估的可信度到達一 可接丈的位準為止。同樣地，解碼資料符號&的處理是耗 時，且不會於通信系統〗〇的應用中，以適時方式產生資料 符號Xi的正確評估。 請即參考圖6 , —繪圖600是根據使用在通信系統⑺中本 ____-12- 本纸張尺度適财國國家標準(CNS) A4規格(210 X 297公爱) 577211 A7

發明的各種不同具體實施例來表示_解碼器的信號與資訊 w。在繪圖600中描述的解碼操作適於解碼一連串資料符 號且泫等貝料符號是根據加速碼而在一發射器中編碼。 在圖4顯不的加速編碼器4〇〇是根據加速碼而用以編碼一連 串貝料付號的具體實施例。結合本發明具體實施例的例如 解碼器20之-解碼器可從本發明的各種不同觀點明顯獲 =。本發㈣-具體實施例可提供用錢^具高可信度的 資料符號XiiL確評估的快速解·作。若要遵循在根據本 發明各種不同具體實施例繪圖_中的信號與資訊流的各 種不同觀點，數個觀點要被定義。透過資料符號&形成的 一連串資料符號會是-長度N個二進位符號。N的值可以是 任何有限數值。對於具有在1與？^之間的，，丨”值而言，第一 組成碼4〇1的時間索引會是” Γ，。資料符號1和心=是一長 度Ν個二進位符號。對於具有在1與1^之間的"而言，第 二組成碼402的時間索引是，，k，’。在碼交錯器4〇3的交錯之 後，"k"的值會是時間索引"丨"的影像^ 請即參考圖6，一符號Xi節點601是在時間，，丨，，上與第一組 成碼401輸入的資料符號有關的一符號節點。一符號γ節 點602是在時間”丨”上與第一組成碼4〇1輸出的資料符號= 的一符號節點。一符號/k節點603是在時間"k"上與第二組 成碼402輸出的資料符號有關。在時間，，“丨，，和π丨"上與第'一 組成碼401有關的格柵狀態節點是分別以一狀•能s節點 604與一狀態3丨節點6〇5表示。在時間” "和”。上^^二 組成碼402格栅有關的狀態節點是分別以一狀賤〇 ”纟〃點

裝 訂

-13- 11577211 A7 B7 五、發明説明（ 606與一狀態Gk i節點6〇7表示。在時間"丨十，、”i”和 "κι”，與第一組成碼4〇1有關的計算節點是分別以一c 1 節點608、Ci節點609和‘節點61〇表示。在時間 k和k+ 1 ,與第二組成碼4〇2有關的計算節點是分別以

Dw節點611、DjJLfit612*Dk+i節點613表示。一通道心節 點614是與接收的資料符號&有關。一通遒、節點615是X』 接收的資料符號1有關。一通机節點616是與接收 料符號Zk有關。 在圖:00中，一分枝是連接兩節點。一分枝可將訊息從 一來源節點運送到一目的地節點。大體上，如果以和0是任 何兩節點，標記法Μ(α，ρ)係表示從一節點以到一節點0的 訊息。例如，一分枝651是將例如1節點601的一符號節點 連接到例如Ci節點609的計算節點。分枝651是將訊息從一 訂 來源節點Xi 601運送到一目的&Ci節點6〇9。因此，透過分 枝651運送的訊息是以M(Xi，Ci)表示。連接到符號節點 6〇1符號節點602與符號節點603的分枝是運送由單一數 值所組成的訊息。連接到符號節點的一分枝能以硬體、韌 體或軟體、或其組合、以暫存器或變數、或上述組合實 施。透過暫存器所保留的值或變數係表示由分枝所運送的 訊息。 連接到狀態Si節點605、狀態SM節點604、狀態節點 606與狀態〜607節點的分枝可運送由一排列數值所組成的 訊息。一排列數值具有的長度是等於在與連接狀態節點有 關格柵中的狀態數目。與對應的組成碼有關的編碼器可建 本紙張尺度適用中國國家標準(CNS) A4規格(21〇X297公釐) .14· 12 12 五 、發明説明（ :::目例如，组成碼4〇1在每個時間的每 :::有四個狀態。因此1目排列由四個數目所組成， 的每個狀態有一數目。連接到一狀態節點的分 、㈣或款.體、或組合、—排列的暫存器或變 八姑:貫抱。透過暫存器所保留的值或變數係表示由 分枝所運送的訊息。 如 通常’-節點能以具許多輸人與輸出的邏輯電路形式硬 -貫施。節點亦能以函式或副常式形式的軟體/勃體實 j…節點不必然在任何時刻要儲存或保留任何資訊。一 節點是透過一輸入的訊息更新。當-節點被"更新"時，節 點可根據在它輸人分枝上的訊息目前值而輸出在所有它的 輸出分枝上的訊息。—節點的輸出分枝上的訊息類型亦是 因節點的類型而定。 通道節點614-16是透過接收與對應資料符號有關的一通 道輸出而更新。在解調變器19中的相關器可輸出每個資料 符號的通道輸出。例如，與資料符號'和心有關的通 道輸出可分別更新通道節點614、615和616。當一通道節 點更新時，一訊息便會從通道節點傳遞給相關的符號節 點j例如，在資料符號&的情況，在與資料符號&有關的 通道節點614上接收一 &通道輸出之後，通道節點614是透 過將一訊息從通道節點614傳遞給符號節點6〇1而更新。從 通道節點614到符號節點60丨的訊息傳遞是等於記錄可能性 率：符號Xi通道輸出的M(7^) = i〇gg^g| 。例如， -15- 本纸張尺度適用中國國家標準(CNS) A4規格(210X297公爱) 577211 A7 B7

如果符號Xi*BPSK調變，以致於1是當作一正電壓傳輸， 且〇是當作一負電壓傳輸，且在AWGN通道上接收的電壓 是當作由實數ri所表示的電壓，那麼訊息便等於： = 乂· ’其中 Es/N。係表示通道的 符號SNR。對於在時間上的資料符號而言，通道節點只需 更新一次。通道節點可透過接收通道輸出而更新。 一符號節點可透過在一連接分枝上接收訊息而更新。一 付號節點是連接到許多節點。例如，符號節點6〇1是連 接到通道節點614，Ci節點609與Dk節點612。當一符號節 點更新時，輸出訊息便可透過輸入訊息的加總而決定。下 節點α的輸出有Λ力可的依/列從·t)自 是來自連接到節點α的其他節點（β')的所有輸入訊息。來 自觸發節點CC更新的輸入訊息Μ(ρ，α)不是使用在決定從節 點CX到節點β的輸出訊息Μ(α，ρ)。S符號節點^⑷的情 況，當訊息是在輸入分枝650、653、和659上接收時，節 點便會更新。分枝650會運送來自Ci節點6〇9的訊息 Μ%%)。分枝653會運送來自％節點6丨2的訊息 iVKDA)。分枝659會運送來自通道節點的訊息 M(R，Xi)。到〇〖節點609的輸出訊息是在分枯 〜 到Dk節點612的輸出訊息是在分枝652上運送。如果更=是 由於在分枝650上接收一訊息呢夂），_輸出訊： 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公爱)

裝 訂

-16- 577211

Μ(Χι，ί：0便不會在分枝651上傳送；因此，只有在分枝652 上的輸出訊息M(Xi，Dk)會傳送。從符號節點到通道節點是 沒有輸出訊息。如果更新是由於在分枝659上接收一訊息 M(R，X〇 ,在分枝652上傳送給仏節點612的訊息便具有來 自通道節點Rx 614的訊息M(Ci，Xi)與來自Ci節點6〇9的訊息 Μ(ΙΙ，Χ0的提供。同樣地，如果更新是由在分枝659上接收 一訊息M(R，Xi)，在分枝651上傳送給。節點6〇9的訊息便 具有來自通道節點Rx614的訊息M(Dk，Xi)與來自仏節點612 的訊息M(R，Xi)的提供。 在一具體實施例中，與一通常時間實例有關的輸入訊息 本值疋同時在節點到達。因此，輸出訊息是透過具有與一 通常時間實例有關的所有輸入訊息而觸發。當訊息未實質 同時在每個節點到達時，與時間實例有關的輸入訊息便不 會觸發與另一時間實例有關的輸出訊息。 一狀態節點亦可透過在連接的分枝上接收一訊息而更 新。若要更新一狀態節點，狀態節點可將從一輸入分枝的 連接計算節點接收的一訊息傳遞給在輸出分枝上的另一連 接計算節點。狀態節點只連接到計算節點。狀態節點基本 上是將輸入訊息從一計算節點傳遞給另一計算節點。狀態 Si節點605是連接到計算q節點609與Ci+1節點610。狀態 Si」節點604是連接到(：丨-!節點608與Ci節點609。當狀態Si節 點605是在輸入分枝665上透過從Q節點609接收一訊息 M(Ci，Si)而更新時，訊息M(Ci，Si)便會在輸出分枝667上當 作訊息M(Si，Ci+1)而傳送給Ci+1節點610。當狀態S#點605 _______ -17-_ 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐） 广 —_ B7 五、發明説明（15 ) 是在輸入分枝668上透過接收一訊息M(Ci+1，Si)而更新時， 訊息M(Ci+1，Si)便會在輸出分枝666上當作一訊息M(Si，Ci) 傳遞給Ci節點609。當更新狀態SM節點604、狀態以6〇7、 與狀態節點606時，類似操作便會執行。 為了要描述在計算節點的輸出訊息評估，關於與組成碼 有關的格柵的一些標記法將描述。格柵的每個分枝是將一 狀態s連接到狀態t，且在第一及第二組成碼4〇1和4〇2的情 況是以兩個二進位符號標示^只有雙些對的狀態是在格柵 連接在與乐一組成碼4 01有關的格概中的每個分枝是以 (f[s，t]，g[s，t])表示。同樣地，與第二組成碼402有關的格 栅的每個分枝是將一狀態s連接到狀態t，且是以 (f’[s，t]，g’[s，t])表示。f[s，t]係表示有規律的符號（即是 Xi)，且g[s，t]係表示與第一組成碼401有關的核對符號（即 疋Yi和Zk)。f’ [s，t]係表示有規律的符號（即是X丨），且 g'[s，t](即是Yi*zk)係表示與第二組成碼4〇2有關的核對符 號°在技藝中熟諳此技者可了解到資料符號Χί是有規律的 符號，且Yi和Zk是與一加速碼有關的核對符號。 從計算節點到狀態節點的輸出訊息是一排列數值的形 式。如前述，狀態節點是將訊息從一計算節點傳遞給另一 計算節點。因此，來自狀態節點的輸出訊息亦是一排列數 值的形式。排列的長度是等於在格柵的每狀態空間中的狀 態數目。例如，在從計算節點Ci 6〇9到狀態Si節點605的訊 息MCChSi)情況中，M(Ci，Si)[s]係表示在訊息中 的排列數目的第s個元件。同樣地，M(Si，Ci)[s]係表示從 一· -18- 本紙張尺度適用中國國冢標準(CNS) A4規格(210X297公董 1 ~--- 577211 A7 B7 五、發明説明（ 狀態節點到計算節點的訊息M( Si，Ci)的第s個元件。來自計 算Ci節點609的輸出訊息是依下列評估： M(CA)W = log Σβχρ[^+ M(xnC{)^s[s,t] M(yi7c.)] = log d]十似(心 c, )[m ㈣ A? Cv,, c,)] 一 log 其中加總是局限在狀態s和t，以致在從狀態s“到·狀態t的 格柵中有一分枝。從計算Ci節點609到符號節點Yi 602的輸 出訊息不會存在，即使是在圖示的一分枝657(在虛線）。 既然符號節點Yi 602是將一訊息只傳送給Ci節點609，所以 節點Yi 602不會從Ci節點609接收訊息。同樣地，來自計算 節點Dk 612的訊息是依下列評估：

AfC〇*，c^)|>] = i〇g exp[M (σλ.,, Dk + f[s, ΐ] M(xk,Ck) + gy% r] M (zk, Dk)] Μ^,σ^)[ί]=，ΐ〇β X exp[M (σ,, Dk )[t] (xk, C,) + g^sj) M (zk, Dk)] 一 log [exp[Af (o*h，A )l>] + M (A，At) W 十〆[·Μ] M (¾，)] /ww · ^exp[A/ (cr^j, Dk )[i] + ΛΓ (σΛ, Dk )[t] + g'[s7t) M (zk, Dk)] rua)^〇 . -19- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐） 577211

從計异節點Dk 609到符號節點Zk的輸出訊息是不存在， 即使一分枝654(在虛線）顯示。既然符號節點心6〇3是只將 一訊息傳送給Dk節點603 ,所以節點Zk6〇3不會從以節點 603接收一訊息。 上述計算是使用下列定義的基本數學運算： ,«j=i〇g

可容易看出上述η個排列運算能以二進位運算的串聯杏 施： $ 裝 Φ(υι5υ25Λ5πη) = φ(υι?φ(υ25φ(υ3,Λ,φ(υη.ΐ5υη))) 此外，二進位運算能以下式實施·· 訂 Φ( 1,U2) Μαχ(υι5υ2)+1〇§[1+6χρ(.|υ1.υ2|)]=Μαχ(υΙ,υ2)+ψ(|υ1-υ2|) 在實施方面，函數Ψ(丨U1i2丨）是接近使用一小的查表。 當一計算節點被”觸發”時，下列步驟便會依序發生：（1)

更新連接到計算節點的所有狀態節點與符號節點，且 更新計算節點本身。 根據各種不同具體實_的訊息傳遞解碼演算法是由更 新：有通运節點所組成，然後根據一觸發排程來觸發該等 計=節點。典型上’計算節點是在解碼處理期間根據排程 數久而觸發。纟自計算節點的輸出訊息會被初始化， 程更新觸發。

對於初始化處理而言 是初始化設定成0。 ，從所有計算節點到符號節點的訊 從所有計算節點到狀態節點的輸出

577211 A7 B7 五、發明説明（18 ) 訊息的每個元件是初始化設定成-l〇g(M)，其中μ是在格栅 的每個狀態空間中的狀態數量。如果構成的編碼器在編碼 之前已知是在零狀態，那麼處理便會在時間” 〇”初始化， 對於在格柵區段中的所有非零狀態s而言， M ( C。，S 〇) [ 0 ] = M ( D。，σ 〇) [ 0 ] = 〇，且 μ ( C。，S。）[ s ]= M(D〇，aG)[S] = -co。同樣地，如果構成的編碼器在編碼結束 時於零狀態是已知，處理可於所有非零狀態s初始化成 M(Cn + 1，Sn)[0] = M(Dn+1，cjn)[〇] = 〇 和 m(Cn+1，Sn)[s] = M(Dn+卜aN)[s]=-〇o 〇 請即參考圖7，一繪圖700係根據本發明的各種不同具體 實施例而描述在對應不同時間實例的不同節點之間訊息 流。與編碼的資料‘號Xi、Yi*Zk有關的通道輸出是儲^ 在解凋:器1 9的圮憶體元件^同樣地，在不同時間實例， 與編碼的資料符號Xi、Yi*Zk有關的通道輸出可同時於解 碼處理使用。與對應時間實例”卜丨”、”丨”和” i+1，，的資料符 號XN1、Xi和Xi+1有關的通道輸出是傳遞給符號節點。 狀態Si.2、siel、Si和si+1節點702亦形成連接計算的c, 2、 Cm、Ci、Ci+1、與 Ci+2 節點 704。狀態 σΐς·2、ak i、^和 σκ+1節點705亦形成連接計算的Dk2、Dki、Dk、^與 Dk+ 2節點706。與對應時間實例”丨]”"丨"和"丨+ 1，，的資料 付號Yh、Yi和Yi+ !有關的通道輸出是傳遞給符號節點 707。與對應時間實例” k·丨，，、，· k，，和"κ +丨，，的資料符號z 、zk和ζκ+1有關的通道輸出是傳遞給符號節點7〇8。雖= 繪圖700係描述對應三個時間實例的訊息傳遞流，但是^

裝 訂

577211 A7

-22- 技蟄中？諳此技者可了解到繪圖700可擴大包括1到N的所 有^ 2男例根據一具體實施例，所有計算節點704和706 本貝疋同時觸發。同樣地，在一步驟中，所有計算節點是 更新一次。每次所有計算節點更新時，解碼處理便會在解 碼重複上芫成。計算節點704和706的同時觸發會重複，以 達成解碼處理的一或多個重複。 在另-具體實施例中，計算節點能以‘ &，q，…，‘ Cn-i，Cn.2, Cn.35 ...3 C2) Cl, C〇, D〇, Dl, D2) ..., Dn, Dnm，Dn.2, Dn.3, ···，d2, Dn D。的序列觸發，以獲得具完 全MAP解碼的傳統加速解碼演算法的單一重複。計算節點 c〇’ Cl5 C2，…，cNW序列係分成數個重疊子方塊，且節點 =在每個讨塊中連續觸纟，但{同時跨越所有子方塊·。 第一組成碼的滑動方塊MAp解碼的近似值可獲得。節點 D〇、Di、D2、…、Dn能以相同方式觸發，以獲得具滑動方 塊MAP解碼的標準加速解碼演算法的近似值。 大體上，一部分（重疊）計算節點的任意收集重疊）可定 義，且一部分觸發序列亦能定義。在每個部分中，節點能 以任何順序、或同時發生。或者，一序列可指定而符合在 一部分觸發序列中的每個計算節點的觸發器。不同部分能 以任何順序、或同時觸發。當所有計算節點觸發一次時， -解碼重複便可定義而發生…完全解碼處理包括數個重 複。在數個重複觸發第一組成碼的計算節點之後，第二組 成碼的計算節點可同樣被觸發器。根據具體實施例，在預 先疋義的重複數量足後，處理亦能完成。根據具體實施 I紙張尺度適財@ g家標準(CNS) A4規格(21QX297^Jy

裝 訂

577211

例’在以動態方式的許多重複之後，處理亦會完成。各一 接受組的有規律的資料符號（X i)在可接受的品質位準上產 生時，處理便完成《在每個重複之後，在符號節點601 上的資料符號Xi值便會經過循環冗餘檢查（CRC)。如果通 過CRC檢查，解碼操作便完成，且不需要額外重複。

裝 在技藝中熟諳此技者可進一步了解到與在此揭示的具體 實施例有關的各種不同說明的邏輯方塊、模組、電路、與 運算法步驟能以電子硬體、電腦軟體、或兩者組合實施。 為了要清楚描述硬體與軟體的互換性，上述各種不同說明 的元件、方塊、模組、電路、與步驟通常是從他們的功能 觀點描述。此功能是否能以硬體或軟體實施是因整個系統 的特殊應用與設計限制而定。熟諳此技者能以每個特殊應 訂

用的不同方式貫施，但是此實施決定並未達背本發明的範 圍。 在此揭示具體實施例中描述的各種不同說明邏輯方塊、 模組、與電路能以一般目的處理器、一數位信號處理器 (DSP)、一應用特殊積體電路（ASIC)、一場可程式閘陣列 (FPGA)或其他可程式邏輯裝置、非連續閘或電晶體邏輯、 非連續硬體元件、或設計執行在此描述功能的任何組合來 實施或執行。一般目的處理器可以是一微處理機；或者， 處理器可以是任何傳統處理器、控制器、微控制器、或狀 態機器。一處理器亦能以例如一 Dsp與一微處理機、複數 個微處理器、連同一 DSP核心的一或多個微處理器、或任 何其他此結構的計算裝置組合實施。

577211 A7 B7 五、發明説明（

在此揭示的具體實施例中描述的方法或演算法步驟能直 接以處理器執行的硬體、軟體模組、或兩者組合而具體實 施。一軟體模組可在隨機存取記憶體、快閃記憶體、ROM 記憶體、EPROM記憶體、EEPROM記憶體、暫存器、硬 碟、可移除磁碟、光碟、或在技藝中已知儲存媒體的任何 其他形狀。一儲存媒體範例係耦合到處理器，以致於處理 器可將資訊讀取及寫到儲存媒體。或者，儲存媒體可整合 到處理器。處理器與儲存媒體可在ASIC。ASIC可在一使 用者端。或者，處理器與儲存媒體能在使用者端以非連續 元件存在。

較佳具體實施例的先前描述的提供允許在技藝中熟諳此 技者製造或使用本發明。這些具體實施例的各種不同修改 對於在技藝中熟諳此技者是顯然的，且在此定義的一般原 理可運用在其他具體實施例，而無需使用創作性設施。因 此，本發明並未局限於在此顯示具體實施例，而是符合在 此揭示的原理與新特徵的範圍。 -24- 本纸張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐)

Claims (1)

1. 、申請專利範圍 •一種用以在通信系統中解碼在通道上傳送的一連串加速 編碼資料符號之方法，該方法包含： 根據一接收的通道輸出來更新通道節點Rx，Ry和; 將來自符號節點Xi，丫{和zk的輸出訊息初始化，其中 該等符號節點Xi，Yi*Zk*與等通道節點Rx、1和心通 信；及 根據一觸發排程來觸發與不同時間實例有關的計算節 點c和D的更新，其中一計算節點Ci是與該等符號節點Xi 和Yi通信，且一計算節點Dk是與該等符號節點&和4通 信。 2·如申請專利範圍第丨項之方法，其中該計算節點^是與 一第一组成碼有關的狀態節點心和心^通信，且該計算節 ··’’占Dk疋與一第一組成碼有關的狀態節點^^和通信， 其中v亥等第一及第二組成碼是結合該通信系統的一加速 碼’用以編碼該序列的編碼資料符號。 3·如申請專利範圍第丨項之方法，其進一步包含： 在該等計算節點C和D的該等觸發更新的至少一重複 之後，接受在該符號節點Xi上符號Xi的值當作一符號& 的解碼值。 1 4· ^申請專利第！項之方法，其中該觸發排程包括本 質在不同時間實例上同時觸發該等計算節點〇和〇。 5.如申請專利範圍第w之方法，其中該觸發排程包括以 一連串c0, Cl，C2,…，Cn，Cni，Cn.2, Cn.3， ，c2, 丨’ C。，D。’ Dl’ D2, ...，Dn，i，〇ν·2, I，…，D2, •25- 、申請專利範圍 D】，D0而在不同時 如争請專利二=觸發^等計算節點c和D。 在時間實例c。e c , ”進一步包含. 成至少兩部分j2, ...，Cn上將該計算節點C劃分 同時間實例上以」4觸發排程包括在每個部分中於不 7如申y， 來觸發更新計算節點c。 .如申Μ專利範圍第6項 在每個部分中決定係進-步包含： 該觸發更I Μ時間實例上的該序列，用以 8·如申4專利範圍第6 上觸^h ,貝《万法，其中孩在不同時間實例 9 ίΠί少兩部分中的計算節點C是同時發生。 .Γο範圍第㈣之方法，其中在不同時間實例c。， b 2,…，CN上的計算節點c的該至少兩部分具有至 —通常計算節點時間實例。 10.如申請專利範圍第丨項之方法，其進—步包本. 4Γ同時間實例D°，D'，D一 DN上將計算節點D劃 刀成土V兩邵分’其中該觸發排程包括在每個部分中於 不同時間實例上觸發在—序列中的計算節點D。 u.如申請專利範圍第10項之方法，其進一步包含： 在每個部分中於不同時間實例上決定用以^ 的該序列。 文新 12.如申請專利範圍第1〇項之方法，其中該於不同時間實例 上的觸發該至少兩部分中的計算節點D係同時發生。 13·如申請專利範圍第1〇項之方法，其中於時間實\d〇，Di， 〇2, ···，DN上的計算節點D的該等部份具有至少一’通^ -26- 577211 A8 B8 C8 _________D8_ 六、申請ί利範i — 〜 计鼻郎點時間例證。 14.如申請專利範圍第！項之方法，其中該更新包括加總輪 入訊息，以產生一輸出訊息，及輸出用以更新的該輸出 訊息。 15·如申請專利範圍第1項之方法，其中根據該接收通道輪 出的該更新該等通道節點Rx、Ry*Rz包括： 在泫通道節點Rx上接收該與一符號\有關的通道輪 出； 在該通道節點Ry上接收該與一符號\有關的通道輸 出； 在該通道節點Rz上接收該與一符號Yk有關的通道輸 出； 根據該接收的通道輸出，將來自該通道節點&的該符 號Xi的可能性傳遞給該符號節點Xi; 根據該接收的通道輸出，將來自該通道節點Ry的該符 號Yi的可能性傳遞給該符號節點Yi ;及 根據該接收的通道輸出，將來自該通道節點Rz的該符 號zk的可能性傳遞給該符號節點Zk。 16·如申請專利範圍第之方法，其中該將來自符號節點 Xi、Yi和Zk的輸出訊息初始化包括： 將來自該符號節點Xi的一訊息傳遞給該計算節點c的 該計算節點Ci，其中該訊息是根據在該符號節點&上的 輸入訊息加總； 將來自該符號節點Xi的一訊息傳遞給該計算節點D的 -27- 本紙張尺度制中@ a家標準(CNS) A4規格(210 X 297公爱)~" ： -- 577211 六 申請專利範圍 A8 B8 C8

   該計算節點Dk，纟中該訊息是根據在該符號節點Xi上的 輸入訊息加總； 將來自該付號節點Yi的一訊息傳遞給該計算節點q， 其中該W息根據資料符號γ i的該可能性；及 將來自薇符號節點4的一訊息傳遞給該計算節點0的 該計算節點Dk，纟中該訊息是根據資料符號^的該可能 性。

   17·如申叫專利範圍第1項之方法，其中該資料序列包括"N，， 個符號，其中在該序列中的每個符號可透過一下標，，^ ,， 或"kn識別，其中該下標”丨”和” k，，是在解碼處理中的時 間實例參考。 訂 18. —種用以解碼在通道上通信的一連串加速編碼資料符號 之裝置，其包含： 通道節點Rx、Ry*Rz，用以接收通道輸出；

   符號節點Xi、Yi* Zk ,用以與該等通道節點rx、心和 Rz通信； 狀態節點Si和SM ’其係與在一加速碼中的一第一組 成碼有關； 狀怨節點σσ w，其係與在該加速碼的一第二組成 碼有關； 一計算節點Ci，用以與該等符號節點Xi*Yi通信；及 一計算節點Dk，用以與該等符號節點Xi*Zk通信，其 中該計算節點Ci是與該等狀態節點心和心.i通信，且該計 -28- 本纸張尺度適用中國國家標準(CNS) A4规格(210 X 297公羡) 577211 A8 B8 C8 -— — D8 六、申請專利範^ ' 鼻節點Dk是與該等狀態節點〜和〇4通信； 计算節點Ci+丨，用以與該狀態節點Si通信； 一计算節點Ch，用以與該狀態節點Si i通信； "十算節點Dk-i，用以與該狀態節點σk通信，·及 一计算節點Dh，其係與該狀態節點Gk+ i通信，其中 在不同時間實例上的該等計算節點^和D的配置可根據 一更新觸發排程而用於更新。 19.如申請專利範圍第18項之裝置，其中該更新觸發排程包 括以-連串c。，c丨，c2,…，Cn，Cn小〜，Cn。，…， c2, Cl5 c〇5 d〇5 ou d25 ..., DN, DN.l5 dn.25 dn.3, ..., D 2， D 1， D 〇而觸發更新該等計算節點c和D。 20·如申請專利範圍第丨8項之裝置，其中該更新觸發排程包 括以在至少兩部分的劃分計算節點cG，Cl，C2,…，。的 一序列、及在一劃分計算節點D〇, Dl5 D2，…，DN的一序 列來觸發更新。 21·如申請專利範圍第丨8項之裝置，其中該一連串資料包括 ΠΝ"個符號，其中在該序列的每個符號是透過對應用於 該等狀態節點與該等計算節點下標的一下標，，丨”或‘‘k,，而 識別。 22. —種用以解碼供在通道上通信的一連串加速編碼資料符 號而建構之處理器，其包含： 通道節點Rx、1^和Rz，用以接收通道輸出； 符號節點Xi、Yi*Zk，用以與該等通道節點Rx、Ry* Rz通信； -29- 本纸張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 577211 A8 B8 C8 _____D8_______ 六、申請專利範圍 狀態節點Si* SM，其係與在一加速碼中的一第一組 成碼有關； 狀態節點〜和CJH，其係與在該加速碼的一第二組成 碼有關； 一計算節點Ci，用以與該等符號節點通信；及 一計算節點Dk，用以與該等符號節點Xi* Zk通信，其 中該計算節點Ci是與該等狀態節點Si*SM通信，且該計 算節點Dk是與該等狀態節點通信； 一計算節點Ci+i，用以與該狀態節點Si通信； 一計算節點CN1，用以與該狀態節點Sh通信； 一計算節點DK+1，用以與該狀態節點〜通信；及 一計算節點Dk.!，用以與該狀態節點σκ+ι通信，其中 在不同時間實例上的該等計算節點C和d的配置可根據 一更新觸發排程而用於更新。 23·如申請專利範圍第22項之處理器，其中該更新觸發排程 包括以一連串C〇, Cl，c2,…，CN，cN小 cN 2, Cn 3，， C2, c丨，c。’ D。，D丨，D2,…，DN，Dn 丨，Dn 2, Dn 3，， 〇2, Dl5 D〇而觸發更新該等計算節點c和 24·如申請專利範圍第22項之處理器，其中該—連串資料包 括Ν個付號，其中在該序列的每個符號是透過對應用 於該等狀態節點與該等計算節點下標的一下標，，丨”或讣，， 而識別。 25·-種用以解碼在通道上通信的_連串加速編碼資料符號 之裝置，其包含： -30- 本紙張尺度適用中國國家標準(CNS) Α4規格(210X297公爱) ' -------- 577211 A8 B8 C8 D8

   六、申請專利範圍 供通道節點用之Rx、Ry和Rz的裝置，用以接收通遒輪 出； 符號節點Xi、Yi* Zk的裝置，用以與該等通道節點 Rx、Ry*Rz通信； 狀態節點S,•和SM的裝置，其係與在一加速碼中的一 第一組成碼有關；

   狀態節點σ 1^和σ k. 1的裝置，其係與在該加速碼的一第 二組成碼有關； 一計算節點q的裝置，用以與該等符號節點Xi和Yi通 信；及 一計算節點Dk的裝置，用以與該等符號節點Xi和Zk通 信，其中該計算節點Ci是與該等狀態節點Si*SM通信， 且該計算節點Dk是與該等狀態節點通信； 一計算節點Ci+1的裝置，用以與該狀態節點Si通信； 一計算節點CU1的裝置，用以與該狀態節點sM通信；

   一計算節點DK+1的裝置，用以與該狀態節點以通信； 及 一计其節點Dk+1的裝置，用以與該狀態節點σ ^通 信，其中在不同時間實例上的該等計算節點C和〇的配 置可根據一更新觸發排程而用於更新。 -31- 本紙張尺度適用中國國家標準(CNS) Α4規格(210X297公釐)