TWI285475B - Method for simplifying a Viterbi decoder - Google Patents

Description

1285475 九、發明說明·· 【發明所屬之技術領域】 本發明係指一種簡化維特比解碼器（Viterbi)的方法，尤指一 種根據部分響應（Partlal ResP〇nse)之階數(Tap)以減少維特比解碼 為之暫存選擇模組個數並避免解碼訊號較原始訊號延遲進而提高 維特比解碼器解碼效率的方法。 【先前技術】 口P 刀备應敢大相似（Partial Response Maximum Likelihood)訊 唬處理方法已被廣泛應用於各種數位訊號處理中，其係利用部分 響應對原始峨進行調變以透過通道輸出調變訊號至綱最大相 (Maximum Likelihood Sequence

Estimation，MLSE)。最大相似性序列估測的技術同樣地被廣泛應 用於各種數位解碼中，其中轉比檢·(術旧咖伽r)即為 實現以最大她性序細f卜序顺積編碼（_Ghjtk)nc〇des) 的一種電路。 如業界所習知’-般通訊通道中具有附加性白高斯雜訊 (Additive white GaussiannGise，AWGN)或是其他干擾源而為 I降憾麻號時發生錯誤賴率，大錄的通域統都會對傳 送的貧料先進行編碼，例如，利用特殊的演算法來旋積㈣ 1285475 °當接收機進行解碼 到的資料是否正確， 奴傳达的貞料’使得傳送資制位元數增加 則’就可財]㈣算法的雜來_所接收 甚至可以還原發生錯誤的位元。 明麥考弟1圖，第i圖為一f知維特比解瑪器！能方 ==維特比解碼器10包含有一分支輸入器12、一加法比^ -Μ、，衡量值記憶體模組16及 輸出捕β 2〇。分支輸入器u可接收一 至加法比較選擇器14中；加法比較選擇器14可藉維特比演算 法以根據最大她性相_ (MaximumLikeiih(K)dSequ_ H’ MLSE)計算出由分支輸入器12輪出之序列訊號加 =j衡量值（PathMetric)並將計算所得的路徑衡量值輪出至路 I里值雜體模組16 ;同時，加法比較選擇器14並計算複數個 狀值以輸人至路徑記憶雜組18。 路徑記憶體模組I8包含有複數個暫存選擇模組串聯於一序 歹！輪出延擇益20可根據路徑記憶體模、组18輸出之訊號判斷— ^輪出訊號DTb。關於維特比解碼器ω的運作情形，以下以部 分響應（PartialResp刪）之階數(Tap)等於三，pR〇,2，⑽情形為 例此日守維特比解碼器10具有四個狀態，且分支輸入器η將經 1285475 編碼的序列訊號DTi分為丄 ^ 刀马/、個为支亚輸入至加法比較選擇器14 一繼續參考第2圖及第3同^ 0 _ 乐3圖。弟2圖為習知具有四種狀態soo、

Si〇如之維特比演算法的狀態圖（StateDiagram);第3 圖為此時對應的路徑記憶體模組21之示意圖。 ^如第2圖所示’每一狀態下都有不同輸入值0或1 (亦即原始 σ ;、斗）玉曰產生相對應的輸出值（亦即編碼訊號），其中輸出值 可為4、2、_2、_4。當簡碼峨送人軌通道後，該編碼訊號 可能會受到干擾而加法比較選擇器14即可根據維特比演算法得出 最接近原始_的結果。_巾，物晴模㈣包含有十 一個暫存選擇模組22用以對包含有十個位元的輸入訊號進行解 碼，每-暫存選擇模組22包含有四個暫存器24及兩個選擇器％、 28。、選擇器26、28可根據加法比較選擇器14輪出之選擇訊號％、 Μ決定所要輸出的訊號。而加法比較選擇器14計算選擇訊號如、 S1時係根據計算每-狀態之路飾量值而得，請參考下列方程心 P(t，S00)=mm{(P(t],S00)+B(t，，)，(p^ P(t,S0irP(M5S00)+B(tr2) P(t,Sl〇rP(M,Sll)+B(v2) P(t,siirmin{(P(M?S0l)+B(t?2))5(^ SO-O for (P(t.i3〇〇)+B(tr4))<(P(t.i?si〇)+B(tr2)) ~1 for otherwise 1285475 S1=0 for (P(M,soi)+B(t,2))<(P(,l5S11)+B(t 4)) =1 for otherwise 其中，PW表示路徑衡量值，B(t)表示路徑值。 上述Mis雛験其相騎作係為—#麵胃知之技術， 故不在本文帽細敘述。只要持續上述的動作(計算路徑衡量值 與決定選擇訊號SO、S1)達到終端節點就可決定出解竭訊號㈣。 舉例來說’沿續第2圖及第3圖的例子，請參考第4圖。第4 I ?! ^10 ^ DTo k 乂不♦糊中，原始訊號Sii經過部分響應編碼後產生 序列訊號DTi並輸入具四狀態的維特比解 特_· 10«前述的轉比演算法即 DTo。由第4圖中可知，序 斤夕 以皮h #bOTo較原始訊號Sii延遲兩值元 (P序列訊號DTo較原始訊號Sii少第 說，習知維特比解碼器1〇盔法 70，也就疋 元訊號。其中，卿罐m 原始訊號sii中的啟始兩位 器10之輪軸Η所二 第3圖令之維特比•馬 输出尚未收_導致，只要輪人健之接收· 可解出正確之原始訊號Sii。 7b 即 習知維特比演曾 再者，如果接收到的序列訊號DTi报長時， 丄285475 :的記._就相t大’抑卩路徑記憶雜組 :暫，組22以得到令人滿意的收;：多 饥竭讀相當的資如得 ^乃.'‘'可避免地車父原始訊號延遲數個位元》舉例來〜、 :::=Γ含2°個暫存麵組，‘ ’仁仍1縣_；延遲數三個位元。 器中解碼訊號延遲問題及暫存選 解碼器無法提升效率且耗費過多 總而言之，習知維特比解碼 擇模組需求問題造成習知維特比 資源。 【發明内容】 因此’本發明之主要目的即在於提供一種於維特比 (Vtobi)解碼^巾高效轉碼的方法。 、本1月揭路-種於—維特比（Viterbi)解碼器中高效率解碼的 -匕3以下步驟.⑻轉—已知之部分響應⑽耐 Response) ’趣_部分響紅酸蚊—錄暫存選擇 板姐之個數’⑼分析衫餘暫存選賴組之—輸出減以決定一 啟始輸入财u，以及⑻根據—向前循跡狀態及該啟始輸入訊號於 1285475 ____—序麵梅特比解碼。 【實施方式】 g為改善習知維特比解碼器延遲問題及暫存選擇敎需求問 通，树明以狀態的觀點對維特比解碼器接收訊號進行解碼，請 參考第5圖。第5圖為本發明簡化維特比（vite 5〇的示意圖。_5G包含以下步驟： 步驟500 :開始。 ν!^ 502 ·取得一已知之部分響應，並根據該部分響應之階數 (Tap)以決定多餘暫存選擇模組之個數(a redundant number of register selector modules，Nrs)。 步驟504 :分析該多餘暫存選擇模組之一輸出訊號以決定一啟 始輸入訊號。 步驟506 :根據該多餘暫存選擇模組之個數Nrs及該啟始輸入 訊號以決定一尚效率維特比解碼器並根據該高效率維 特比解碼器的向前循跡狀態對輸入至該高效率維特比 解碼器之一序列資料進行解碼。 步驟508 :結束。 本發明流程50係以狀恶的觀點改善習知維特比解碼器的解碼 效率，請參考以下說明。回到第3圖，其中第3圖中之部分響應 10 1285475 為PR(1，2，1);對於路徑記憶體模組18的第一級暫存選擇模組^⑴ 而言，路徑記憶體 is的第-級暫存選擇才莫組22〇1輪出訊號 必為（0,0，1，1)。 因此，只要直接以（0,0,1,1)當作路徑記憶||模組18的第二 級暫存選觀組2202之啟始輸人峨即可帛化路徑記憶體模組 18的配置（也就是省略路徑記憶體模組18的第一級暫存選擇模組 22〇1)。其中，第3圖中之部分響應為呗⑵）；根據步驟5〇2， 取得-已知部分響應、PR(1，2，1)之後，根據該部分響應謂數丁叩 (於本實施例中，Tap，，可決定多餘暫存選擇模組之個數他。 其中’多餘暫存選擇模組之個數Nrs係利用一運算原則所推管而 出。該運算原則：

I

Nrs=Tap-A: 2 < A: <Tap 其中k為整數，在本實施例中，部分響應之階數丁叩為3，而匕 為2 ;因此多餘暫存選擇模組之個數Nrs係為丨（也就是省略路穫 記憶體模組18的第一級暫存選擇模組22〇1)。如此，決定一高效 率維特比解碼器；其中，該高效率維特比解碼器比原本之維特比 解碼省略了路控記憶體模組18的第一級暫存選擇模組220!。 其中，分析該多餘暫存選擇模組之一輸出訊號即可決定_啟始 1285475 輸入訊號。就本實施例而言，多餘暫存選擇模組之個數此係為1 (也就是省略路徑記憶體模組18的第—級暫存選擇模組纖’），· 而原本所省略之路徑記顏模組18的第—級暫存選擇模组咖 輸出為⑽山〇’因此（0,0，u)即被設定為該高效率維特比解 碼器之輸人峨’㈣高效率轉轉碼器之啟始輸人訊號。由 於啟始輸人訊號已決定，_高效率轉轉碼器之第-級暫存 選擇模謂2 (為原本維特比解碼器之第二級暫存選擇模組）中 之四個暫存器24即可省略。 前循跡狀態對輸 碼 '娜好餘暫存選擇模組之個數崩及該啟始輸入訊號，即 碰率轉比解抑趣據該高鱗轉_碼器的向 入至該高效率維特比解碼器之-序列資料進行解 狀態：：二:4第6 __流程5°設計之! 向前猶跡狀態圖: ^ 圖可知，當以狀態觀點進行解碼時，^ 侍接收訊號^^的第一 ’了 同理，請表考第二，出為。Η 維特比解碼器對’幻圖為依據本發明流程5G設計之四狀: DT〇 ° 圖中接收訊號DTi進行解碼所得之輸出訊号 、思、圖。由第 圓了知，原始訊號的前兩位元可被解竭而专 1285475 含於輪出訊號DTo中。 對於習知Μ度乡魏触柄機（HD_DVDMve)的維特 比j碼器而言’其維特比解碼器需要2〇個暫存選擇模組才可解^ 可靠的輸出訊號但仍無法解出原始訊號的前三位元。請參考第δ 圖’第8圖為依據本發職程5G設計職密度多功驗位光碟機 (HD-DVDDrive)的維特比解碼器之路徑記憶體模組⑽的示音 圖。其中，第8圖中之部分響應為呵⑴圳：根據步義；； ^ PR(1,2,2,2,1)^ , P (於本员知例中，Tap = 5)，可決定多餘暫存選擇模組之個數 二。其中，多餘暫存鞠緣之個數_期—運算原則所推 异而出。該運算原則：

Nrs=Tap->t 2<k< Tap 其中让為整數；因此，在本實施例中，部分響應之階數Tap為5 而k為2 ;因此，多餘暫存選擇模組之個數Nrs係為3。五人豹 二存選擇模組之個數咖係為2，如 暫存^擇#、、、且，但亦—省硬體的目標。 82用以接收由維特比解碼 器的加法比較選擇器輪 1285475 观〜防以決定輸出訊號。請參考第9圖，由於習知高⑼ 能數位光碟機（HD_DVDDrive)的轉轉碼器的第—‘二 擇模組輪出訊號為⑽⑴觀叫）、第二級暫存選擇麵= 訊號為（〇,〇,〇，u，〇,〇,u，u、第三級暫存選擇模組輸出訊別 (0,0,0,0,0，1，1，1，1，1) 〇 因此，只要將第8圖所示之路徑記憶體模、挺80的第一級暫存 選擇模組82的啟始輸人訊號設定為⑽卿，1Λ1，⑴即可= 存選擇模⑽的個數減少為17.個。此外，由於啟始輸入訊號已日 決定，則路徑記憶體餘80的第—級暫存選擇模組82中之十個 f存，（未緣示於圖中）即可省略。同理，依據本發明流程5〇設 相间讀多功能數位光碟機的轉比解碼器還可以解出原始訊 號的前三位元。^ ^ ^ ^ ^ ^ ^ 〜 因此’相較於f知技術，本發明流程50提供-種簡化維特比 解瑪器的方法。簡言之，本發明流程50除可減少維特比解碼器中 ，傻記憶體模組的暫存選擇模組個數外，還可避免解碼時延遲問 題，大幅地提升維特比解·解碼的效率並可降低系統資源以節 省生產成本。 以上所述僅為本發明之較佳實施例 ’凡依本發明申請 14 1285475 專利範圍所做之均 盒範圍。 等Μ彳匕與修飾’皆應屬本發明專利之涵 【圖式簡單說明】 弟/圖為習知維特崎之魏方塊示意圖。 弟2圖為f知具有_狀態之維特比演算法離態圖（State Diagram) 〇 I圖為第2圖之維特比演算法對應的路徑記憶體模組之示意圖。 弟4圖為習知四狀態維特比解石馬器之接收訊號與解碼訊號之比較 示意圖。 !5圖為本發物_桃_的_。 弟6圖為本*明四狀態維特比解碼器依據第*圖中接收訊號的第 …一位缝的向麵雜態®。 · 第7圖為本發明四狀特 ^ 一 ^ 狩比解碼為之接收訊號與解碼訊號之比 弟8 1為本發，密度多贿數位光碟機⑽-DVDDrive)的維 ^、比解碼②之路徑記‘_模_示意圖。 弟9圖為習知高密户多匕 又刀月匕數位光碟機（HD_DVDDrive)的維特 比解碼器之第一級一 m 乐二級暫存選擇模組輸出訊號之示意 1285475 【主要元件符號說明】 10維特比解碼器 14加法比較選擇器 16路徑衡量值記憶體模組 21路徑記憶體模組 24暫存器 50流程 S00、S(H、S10、S11 狀態 DTi、DTo、Sii、S0(t)、Sl(t) 12分支輸入器 18、80 路徑記憶體模組 20輸出選擇器 22、82 暫存選擇模組 26、28 選擇器 500、502、504、506、508 步驟

SfO〜Sf5訊號 16

Claims (1)

1285475 十、申請專利範圍·· 1. 一種簡化一維特比（viterbi)解碼器的方法，其包含以下步 驟： 取知已知之σ[5分響應（partiai ReSp〇nse)，並根據該部分響 應之階數(Tap)以決定-多餘暫存麵模組之個數； 分析該多餘暫存娜模組之—輸出赠以決定—啟始輸入訊 號，·以及 根據-向前循跡狀態及該啟始輸入訊號於該維特比解碼器冲 對一序列資料進行維特比解碼。 2. 如中請專利範圍第！項所述之方法，其中該多餘暫存選擇模 組之個數係該部分響應之階數減掉一特定值。 3. 如申請專利範圍第2項所述之方法，其中該特定值至少係厂 至多為該部分響應之階數減1。 4. 如中請專利範圍第i項所述之方法，其中該啟始輸入訊號係 為该多餘暫存選擇模組之輸出訊號。 5. 如申請專利範圍第i項所述之方法，其中該維特比解碼器係 設於-rij密度h力能數位柄機（HD_DVD)内，用以對兮 17 1285475 序列資料進行維特比解碼。 6. 如申請專利範圍第5項所述之方法，其中該維特比解碼器之 路徑記憶體模組包含有17個暫存選擇模組。 7. 如申請專利範圍第5項所述之方法，其中該維特比解碼器之 路徑記憶體模組的第一級暫存選擇模組其啟始輸入訊號為 (0,0,0,0,0，1，1，1，1，1)〇 十一、圖式Z 18