維特比解碼器的高速相加-比較-選擇的製作方法

2023-04-24 08:34:36

專利名稱:維特比解碼器的高速相加-比較-選擇的製作方法
背景技術：
I.發明領域本發明一般涉及Viterbi(維特比)算法的應用，尤其涉及一種經改進的系統與方法，用於在執行Viterbi算法時完成高速率相加-比較-選擇(ACS)蝶形操作。
II.相關技術的說明Viterbi算法作為一種卷積編碼信號的解碼方法於1967年首次出現，以後在數據通信、數據記錄與數位訊號處理領域中得到廣泛採納。該算法已成功地解決了各種數字估算問題，包括減少了存貯媒體的記錄誤差、消除了碼元間於擾，增強了字符與文本識別能力。
這樣，Viterbi算法已成為卷積編碼數據最主要的糾錯解碼方法。對於這樣的應用，根據一連串觀察，Viterbi算法決定了以最小誤差量度通過表徵所有可能編碼器狀態格構的路徑。這一最短路徑例示了卷積編碼器最可能生成的序列。

圖1A示出一種典型的卷積編碼器。卷積編碼器100包括一個8位分接的移位寄存器110和一對異或型加法器120，後者把輸入數據位U(D)105序列轉換成輸出碼元C0(D)、C1(D)125序列。具體而言，圖1A是一例1/2速率代碼，對每個輸入數據位U(D)105產生兩個輸出碼元C0(D)、C1(D)25。注意，圖示的特定碼率與卷積編碼器100的配置僅為舉例，並不限制本發明各實施例的操作或範圍，因而本發明諸實施例可以使用1/3或3/4等不同的碼率。
根據發生器碼多項式G0(D)、G1(D)限定的特定移位寄存器結構，編碼器100對輸入位流U(D)105通過移位和異或相加而產生各輸出碼元C0(D)、C1(D)125。在此情況下，圖1A示出的移位寄存器互連，提供1/2速率發生器碼多項式 多項式G0(D)的係數與輸入數據序列U(D)105卷積而生成輸出卷積碼元C0(D)125。同樣地，圖1A示出了1/2速率發生器碼多項式 其係數與輸入數據序列U(D)105卷積後，生成輸心卷積碼元C1(D)125。編碼器100的約束長度K大於寄存器110中的延遲單元數；對於編碼器100，K為9。對於輸入編碼器100的每一數據位，輸出碼元C0(D)、C1(D)125取決於輸入的位和前一K-1輸入位。因此，編碼器100產生的輸出碼元C0(D)、C1(D)125，能跨越2k-1個可能的編碼器狀態。
在一典型通信系統中，輸出碼元C0(D)、C1(D)125接著調製並通過噪聲信道(未示出)發送。解碼器最終收到含噪的卷積編碼數據流，並應用利用卷積碼特性的Viterbi算法最終確定輸入數據序列U(D)105。
卷積碼的一個優點是其可為對稱碼樹提供高度重複的結構。從理論上講，卷積碼能生成無限的碼元序列。然而，由於其對稱性，在確定最可能路徑時要求估算狀態數，導致輸入數據序列U(D)105減少為2k-1(此時為256)種狀態。另外，在解碼這種對稱碼時，只關心進入256種可能編碼器狀態中每種狀態的最可能(即保存)的局部路徑，所有其它路徑可能不再深究。這是由於通過某一狀態的最可能全局路徑必須跟隨通過該狀態的保存局部路徑的緣故。
為了起到具有一組狀態轉換的有限狀態機的作用，Viterbi解碼器依賴於這些碼特徵。根據從收到的噪雜卷積編碼數據流得到的觀察結果，解碼器假設每一種可能的編碼器2k-1狀態，確定編碼器從其中的每一種狀態轉換到下一組可能的2k-1編碼器狀態的概率。
轉換概率用稱為量度的量表示，這種量度正比例於概率值的負算法。顯然，量度越小，則出現的概率越大。量度有兩類狀態量度與分支量度。狀態量度也稱為路徑量度，代表發送的碼元組通過特定狀態的相對概率。分支量度代表從一特定源狀態到一發送的特定目標狀態轉換的條件概率(假定源狀態正確)。
Viterbi算法可以歸納如下把時間分成d個樣本，每一時間樣本K有n個可能的狀態SiK(其中i是來自
的整數，K為來自
整數)。對於K＞1，路徑可從任一p個先前狀態Sjk-1(j為來自
的整數)到達各狀態。對每種狀態，在這些P條可能的路徑中間識別量度最小的路徑，並連同量度值存貯起來。
初始化對開始的時間樣本(K＝1)，對各狀態Si1存貯的量度初始化。在開始狀態已知的情況下，可將此時的量度置零，其它狀態Si1的量度置成大的數。這一方法迫使算法後面的迭代只選擇從期望的開始狀態出發的路徑。迭代對每個時間樣本
訪問所有的狀態Sik。在每一狀態Sik，把導向該狀態的每條路徑j的量度計算為(a)先前狀態Sjk-1的量度與(b)從狀態Sjk-1導向狀態Sjk的分支的量度bmjk之和。導向各狀態Sjk的P路徑，在該狀態選擇並存貯最低量度的路徑(即倖存者路徑)，還把該路徑的量度存貯為該狀態的量度smik。
回鏈在訪問了最後時間樣本的所有狀態時，識別出最低狀態量度的狀態Sik。從存儲器裡讀出該狀態的倖存者路徑，由此識別出時間樣本d-1的相應狀態。從存儲器裡讀出這後一種狀態的倖存者路徑，重複回鏈過程，直到識別出包含導向狀態Sid的路徑(即最可能通過狀態時間陣列的路徑)的所有狀態。
這樣，在任何時間k，Viterbi算法都計算導向狀態Snk的路徑的量度，確定倖存者路徑(n個狀態Snk的每個狀態有一條)，並且存貯n條倖存者路徑及它們各自的量度。對於每個考慮的目標狀態而言，這樣相當於存貯導向它的源狀態。因此，任何一種Viterbi算法的實施，都要求應用圖1B所示的相加-比較-選擇(Add-Compare-Select)(ACS)單元150來執行這些操作。ACS單元150負責計算狀態量度值，還運用ACS蝶形操作表徵源與目標狀態間的關係。圖2示出了單次ACS蝶形操作155。
蝶形操作155包括可能對編碼器100中兩個特定源狀態出現的唯一可能的狀態轉換。這部分是由於這樣一個事實，即在任一指定時刻，編碼器100的狀態是編碼器前一狀態右移1位。下一(右移)信息位決定了從源狀態作何種轉換，並將呈現為目標狀態的最高有效位(MSB)。這樣，只有兩個可能的源狀態可轉換的目標狀態。因此，由圖2可以看出，根據輸入數據位U(D)的值，編碼器100隻能從源狀態「x0」轉換到目標狀態「0x」或「1x」，和從源狀態「x1」轉換到目標狀態「0x」或「1x」。要注意，記號「x0」與「x1」表示該源狀態的最低有效位(LSB)分別為「0」與「1」，上位用「x」表示；記號「0x」與「1x」分別表示目標狀態的MSB為「0」或「1」，下位用「x」表示。項「x」不管包含在源狀態裡還是目標狀態裡，都代表同一值(如7位值)。
圖2還揭示，從源狀態到目標狀態的每次轉換，都會產生一組假設碼元H0(D)、H1(D)
其實當編碼器100沿ACS蝶形155的平行分支工作時(如從「x0」轉換到「0x」，或從「x1」轉換到「1x」)，都對兩條平行分支產生碼元H0(D)、H1(D)125。這一特徵的部分原因是一般卷積碼的重複特徵，而且使用了將其MSB和LSB置成1(即對G0(D)與G1(D)兩者而言，g0與g8都等於1)的發生器碼多項式。以同樣方式，在編碼器100沿ACS蝶155任一對角分支操作時(如從「x0」轉換到「1x」，或從「x1」轉換到「0x」)，就生成碼元

如上所述，ACS150單元計算目標狀態量度tm0x、tm1x。ACS150邏輯存貯源狀態量度Smx0、Smx1，它們與接收的一組碼元導向源狀態「x0」與「x1」的概率有關。再看圖1B，在收到一組碼元後，分支量度單元140計算分支量度值bmij與bmij。ACS150把對應於兩種導向特定目標狀態的每一種轉換的分支量度bmij、bmij同相應的源狀態量度Smx0、Smx1「相加」。分支量度bmij、bmij代表從一特定源狀態轉換到一出現的特定目標狀態的條件概率。分支量度bmij表明收到的碼元與ACS150假設的碼元H0(D)、H1(D)125匹配得如何緊密，而分支量度bmij則表明收到的碼元與
匹配得如何緊密。分支量度bmij、bmij的值只取決於收到的碼元對與假設的碼元對H0(D)、H1(D)之間的距離。
對兩種目標狀態的每種狀態，ACS150對導向該目標狀態的源狀態量度-分支量度對之和作比較。然後，ACS150「選擇」由最小量度和代表的最可能對各目標狀態的轉換，並把它分配給該目標狀態作為目標狀態量度tm0x、tm1x。
如上所述，對導向目標狀態的兩種轉換的每一種，ACS150邏輯都把分支量度bmij、bmij加到源狀態量度Smx0、smx1裡，並判定從產生更小量度和的轉換進入該目標狀態的最可能的路徑。於是，選擇該更小的量度和，並變成新的目示狀態量度tm0x、tm1x。ACS150還把該狀態量度(即與導向各目標狀態的最可能路徑有關的代價)存入狀態RAM145裡。如圖1B所示，在回鏈存儲單元160的路徑存儲器中，選擇最小量度和會導致存貯1位的量，稱為判定位。由獲勝源狀態量度的LSB指示的判定位，識別出在兩種轉換中被選擇的一種轉換。
回鏈存儲單元160存貯對應於最可能進入各目標狀態的轉換的判定位。對於約束長度k＝9的編碼器100，將生成2k-1或256個對應於編碼器100各256個可能狀態的判定位。一旦產生和存貯預定狀態數量所有這類信息的陣列，後鏈單元160就在最有可能向正確路逕行進的狀態(即其中對應於最小代價的最新時間單位的狀態)起動，然後通過讀到最後的PX256(即P×2k-1)判定位及時後鏈選擇P位，P是路徑存儲器的有效回鏈深度。由於判定位代表假設為已通過編碼器100的最可能一組位，所以是解碼器能輸出的最佳數據。結果，鏈路在判定歷史中返回得更深，則選擇的路徑與正確路徑歸併的可能性更大。因此，回鏈深度P越高，性能就越佳，不過流水線與存貯延遲也更大。因此，通常把回鏈深度P設置為編碼器100約束長度K的3~10倍。對於K＝9的編碼器，一般把回鏈深度P設置為64。
ACS處理循環規定了ACS單元150對收到的預定數量的碼元計算新目標狀態量度tm0x、tm1x的周期。對於1/2速率卷積碼，每對收到的碼元要求1個處理循環作量度計算。處理循環的長度等於對兩組收到的碼元的所有編碼器狀態作ACS蝶形操作所需的時鐘循環數。例如，如圖2所示，為了執行編碼器100所有256個狀態的操作，具有單個ACS蝶形的Viterbi解碼器，一般要求每一收到的碼元有128次時鐘循環。為了提高處理速度，可以使用部署了多個ACS蝶形的ACS蝶形陣列結構減少一個處理循環的時鐘循環次數。
一例這樣的結構就是圖3所示的8×1ACS蝶形陣列300。通過構建8個並聯的平行ACS蝶形單元155，陣列300將處理速度提高到8倍。對一組收到的碼元，在單次時鐘循環中，8×1蝶形陣列300用所有8個蝶形單元155讀出16個源狀態，並計算16個相應的目標狀態量度tm0x、tm1x。如上所述，ACS單元155接收每個源狀態的狀態量度和四種可能的轉換的每一種的分支量度bmij、bmij。分支量度bmij、bmij只取決於收到碼元對和假設符號對H0(D)、H1(D)或 的值，而且是兩者之間距離的測量值。圖3中作為源與目標狀態一部分包括在內的「X」，代表通過從0計算到15的16次時鐘循環記錄的四位數位保持符(即X＝(X0，X1，X2，X3)。這樣，對於兩組收到的碼元，8×1蝶形陣列300在32次時鐘循環中(即每個收到的碼元為16次時鐘循環)，對編碼器100所有256個可能的狀態計算目標狀態量度tm0x、tm1x。
8×1蝶形陣列結構300的一個缺點在於，對每組收到的碼元，必須讀出16個源狀態量度，而且必須對16次時鐘循環的每次循環同時產生要求的分支量度。這樣，為適應這種操作，8×1蝶形陣列300要求極大的存儲器帶寬。
另一例陣列結構是圖4的4×2ACS蝶形陣列400。該陣列400可像8×1蝶形陣列300那樣同樣程度地提高速度，卻是用2組並聯的4隻ACS蝶形單元155實現的。蝶形陣列400通過暫存中間目標狀態量度tm0x、tm1x，緩和了存儲器帶寬問題。例如，在單次時鐘循環內，陣列400的第一級讀出8種源狀態並計算8個相對的目標狀態量度tm0x、tm1x。然而，蝶形陣列400並不立即存貯中間目標狀態量度tm0x、tm1x。相反地，仍在該時鐘循環內，蝶形陣列400將中間目標狀態重新排列，作為源狀態饋入第二級，接著對下一組收到的碼元計算8個相應的目標狀態量度tm0x、tm1x。這樣，像8×1蝶形陣列300一樣，在32次時鐘循環範圍內，蝶形陣列400能對兩組收到的碼元計算目標狀態量度tm0x、tm1x。
由於無需向ACS150狀態存儲器讀或寫中間目標狀態量度(即第一級目標量度tm0x、tm1x)，所以4×2ACS蝶形陣列400具有縮減ACS150狀態存儲器帶寬的顯著優點。再者，中間目標狀態值聯合流入下一級，避免了延遲，帶寬要求最小。
然而，4×2ACS蝶形陣列400並非沒有局限性。例如，縮減狀態存儲器帶寬的優點完全依賴於這樣一個事實，即陣列400在單次時鐘循環內執行2級ACS150操作。這條嚴格的路徑嚴重限制了更高的時鐘速度。
另外，無論是8×1ACS蝶形陣列300還是4×2ACS蝶形陣列400，在回鏈操作方面都存在性能問題。如上所述，回鏈單元160負責存貯ACS陣列產生的判定位，並且通過存貯的判定位作回鏈而產生解碼的判定位。對於約束長度k＝9的編碼器(如編碼器100)，解碼器裡的ACS陣列將對每組收到的碼元生成2k-1或256個判定位(即對256個可能的編碼器狀態的每個狀態生成1個判定位)，而回鏈存儲單元160通常包含深度p＝64字組(塊)的後鏈路徑存儲器。
在32次處理循環後，每次循環計算兩組收到碼元的目標狀態量度，回鏈單元160從最新的處理循環開始(如64個路徑存儲字組最右邊的存儲字組B0)如圖5A所示。回鏈單元160從回鏈存儲字組B0內的256個判定位裡識別出對應於最低量度值R0狀態的判定位。該狀態定義為最佳狀態BS0，具有一個8位地址，如圖5B所示。回鏈單元160讀出該最佳狀態判定位，然後把它左移入BS0最低有效位(即bs0)而將該值引入BS0地址，如圖5所示。圖5B示明，BS0地址中的其它位值(即bs6-bs1)也被左移，導致丟失BS0最高有效位(即bs7)而表示一新地址BS1。如圖5A所示，BS1是回鏈存儲器塊B1中最佳狀態值R1的地址。接著，回鏈單元160讀出對應於BS1地址的判定位值，將該值左移入BS1地址而生成下一地址BS2，它對應於回鏈存儲器塊B2的最佳狀態。
重複這種讀與左移操作，直到處理了所有的回鏈存儲字組(即P＝64字組)。一般而言，回鏈操作像規定的回鏈長度P那樣作多次讀出，此時，例如要作64次讀出，以便回跟蹤期望的路徑並生成解碼的判定位。然而，這種多次讀出會影響解碼處理的效率與性能。
因此，要求有一種在實施Viterbi算法時能有效地作高速ACS蝶形操作的系統與方法。

發明內容
與本發明原理相符的系統與方法，針對上述提出的要求，提供的系統與方法在實施Viterbi算法時可執行高速ACS蝶形操作。
按本發明原理在這裡實施並概括描述的系統與方法，包括存貯多個源狀態量度的第一存儲單元。第一存儲單元耦合至復用器，後者根據奇偶次時鐘循環能在第一與第二操作路徑之間作選擇。該復用器耦合至相加-比較-選擇機構，後者對每個源狀態量度計算目標狀態量度。第二存儲單元耦合至相加-比較-選擇機構和復用器，用於暫存目標狀態量度，而第三存儲單元存貯的預定邏輯位對應於導致最低值目標狀態量度的源狀態。因此，復用器在偶數時鐘循環期間選擇第一操作路徑，並把源狀態量度從第一存儲單元供給相加-比較-選擇機構，以生成目標狀態量度。在奇數時鐘循環期間，復用器選擇第二操作路徑訪問第二存儲單元，把上次計算的目標狀態量度用作中間源狀態量度，使相加-比較-選擇機構根據該中間源狀態量度生成目標狀態量度。
附圖簡介結合在此並構成本說明書一部分的諸附圖，示出了本發明一實施例，並與說明書一起說明本發明的目的、優點和原理。附圖中圖1A是字組級的示意圖，示出K＝9、速率＝1/2的卷積編碼器。
圖1B是示出ACS和回鏈單元的系統級框圖。
圖2是示出ACS蝶形操作的轉換圖。
圖3是示出8×1ACS蝶形陣列的轉換圖。
圖4是示出4×2ACS蝶形陣列的轉換圖。
圖5A、5B是示出回鏈操作的功能框圖。
6A、6B是示出本發明一實施例的示意圖。
較佳實施例的詳細描述以下對本發明作詳細描述所參照的附圖，示出了符合本發明的較佳實施例。在不違背本發明的精神與範圍的情況下，其它實施例也可行，並且可對這些實施例作修改。因此，以下詳述並不限制本發明，本發明的範圍由所附權項規定。
本領域的技術人員很清楚，下述的本發明可在圖示實例中以許多不同的軟體、固件與硬體實施例來實施。用於實施本發明的實際軟體代碼或專用控制硬體並不限制本發明。因此，在描述本發明的操作與行為時，並不特指實際的軟體代碼或專用硬體元件，本領域的技術人員應該理解，可以按這裡的描述設計出軟體和控制硬體來實施本發明較佳的實施例。
圖6A、6B示出本發明一實施例。該例利用了一種8×1ACS蝶形陣列600，運用8個平行ACS蝶形單元155提供8倍的處理速度。與如此提高速度的其它方式不同，蝶形陣列600在不同的時鐘循環內工作，既限制了每次時鐘循環的計算量，又降低了存儲器帶寬要求。
參照圖6A，在偶數時鐘循環期間，蝶形陣列600用所有8個蝶形單元155讀出由4位計數器X標識的16個新的源狀態，然後對當前格構層計算16個對應的目標狀態量度tm0x、tm1x。在偶數時鐘循環以後(即在奇數時鐘循環期間)，蝶形陣列600對下一格構層把偶數循環目標狀態用作奇數源狀態。這樣，蝶形陣列600就將偶數循環目標狀態量度tm0x、tm1x採納為奇數源狀態量度值Smx0、Smx1，然後根據量度值Smx0、Smx1，對相應的格構層計算奇數目標狀態量度tm0x、tm1x。
這樣，圖6A所示改進8×1ACS蝶形陣列600，要完全處理兩組收到的由K＝9編碼器生成的碼元，需要32次時鐘循環。在偶數時鐘循環期間，蝶形陣列600讀出用增數的4位計數X標識的16個新的源狀態，並對第一組收到的碼元計算16個對應的目標狀態量度tm0x、tm1x。對奇數時鐘循環，蝶形陣列600把偶數循環目標狀態用作新的源狀態，並對第二組收到的碼元計算奇數目標狀態量度tm0x、tm1x。這樣，蝶形陣列600每一時鐘循環只執行一層的ACS，從而克服了4×2蝶形陣列400的單次時鐘循環多層ACS計算問題。
圖6B示出支持圖6A所示8×1改進型ACS蝶形陣列600的Viterbi解碼器電路650。所有狀態的源狀態量度Smx0、Smx1都存貯在狀態RAM145中。根據圖示情況，從偶數時鐘循環期間讀狀態RAM145開始描述Viterbi解碼電路650的操作。一般技術人員很容易明白，該實施例同樣可從奇數時鐘循環期間讀狀態RAM145開始描述。同樣地，可在奇數循環期間作所有讀操作，在偶數循環期間作所有寫操作，反之亦然。
這樣，在偶數時鐘循環期間，將復用器MUX670配置成從對應於第一組收到碼元的RAM145中選擇16個連續狀態的源態量度信息。源狀態信息直接供給ACS單元150，後者包括8×1ACS蝶形陣列600。然後，蝶形陣列600計算相應的16個目標狀態量度tm0x、tm1x，這些量度反饋給狀態RAM145和MUX670。接著，把計算的目標狀態信息暫存在寄存器680中，蝶形陣列600防止存貯的狀態信息返回存儲器，從而改善了8×1ACS蝶形陣列300的存儲器帶寬問題。
在奇數時鐘循環期間，復用器MUX670選擇前一時鐘循環計算並鎖存在寄存器680裡的目標狀態量度信息。該目標狀態量度信息然後被8×1ACS蝶形陣列600用作新的源狀態量度Smx0、Smx1。接著，蝶形陣列600處理該源狀態量度信息，產生對應於第二組收到碼元的目標量度信息。然後，把該目標量度信息存入狀態存儲器RAM145，將被用作下一迭代的源狀態量度。這種處理對第一與第二組收到碼元重複32次時鐘循環，以對其中每二組收到碼元生成256個判定值。在32次時鐘循環後，Viterbi解碼電路650以下面兩組收到碼元啟動該全過程。
通過減少生成解碼判定位所需的讀次數，Viterbi解碼電路650還提高了回鏈操作的性能。如上所述，回鏈單元160負責存貯ACS陣列生成的判定位。再者，在二次時鐘循環(即奇偶次時鐘循環)後，改進的8×1ACS蝶形陣列600生成32個判定位。Viterbi解碼電路650讓這32個判定位以單個32位存儲字存貯，這樣就把奇偶時鐘循環期間生成的判定位以同一存儲字存貯。
因此，如相對回鏈操作描述的那樣，為了建立回鏈時間的開始點，首先用最佳狀態從最後一次處理循環開始識別最低量度的狀態(即最佳狀態判定位值)。由於每個存儲字有32位，所以每次處理循環有16個字(兩組收到的碼元)，每個32位存儲字有一獨特的8位地址。一實施例用最佳狀態地址的4位選擇要讀的存儲字，另外4位則確定在該32位存儲字中要讀的16位。具體而言，若最佳狀態BS0有8位地址(bs7~bs1、bs0)，該實施例就選用位(bs5、bs4、bs3、bs2)在存儲字組B。內選擇一特定存儲字，並依靠位(bs7、bs6、bs1、bs0)選擇最佳狀態判定位R0。將最佳狀態判定位R0左移入BS0LSB(bs6、bs5、bs4、bs3、bs2、bs1、bs0、R0)，形成新的最佳狀態地址BS1。
由於ACS計算對兩組收到碼元進行，因而對剛讀出的判定位而言，導向目標狀態的源狀態具有它們貯存在同一32位存儲字內的判定位。因此，該實施例選用位(bs6、bs1、bs0、R0)來選擇另一半32位存儲字的下一個最佳狀態判定位R1。所以，該最佳狀態判定位從32位存儲字的一半位中選出，而選出的位有助於確定在另一半32位存儲字中哪一個判定位是下一個最佳狀態判定位。因此，正確地回鏈到期望的路徑並生成解碼的判定位所需的讀次數可減少一半。這樣，對一路徑存儲器深度P＝64存儲字組的回鏈單元160而言，只要求讀32次。
上述描述的本發明較佳實施例提供了示例與說明，但並非將本發明限制於揭示的精確形式。根據上述技術或通過本發明的實踐，可以作出更改與變化。如很容易把這裡揭示的實施例結構擴展成16×1陣列或32×1陣列，每次時鐘循環可以生成32或64種狀態。另外，不是對兩組收到的碼元操作，實施例還能對若干組收到的碼元操作。因而要指出，本發明的範圍由權項及其等同物限定。
權利要求
1.一種對實施維特比算法作相加-比較-選擇蝶形操作的方法，其特徵在於，所述方法包括下述步驟在偶數時鐘循環期間，從對應於第一組收到碼元的存儲器第一部分中讀出多個源狀態量度；對每個所述源狀態量度計算目標狀態量度；把所述目標狀態量度暫存入存儲器第二部分；確定哪一個所述目標狀態量度含最低值；把對應於所述最低值目標狀態量度的預定邏輯位存入存儲器第三部分；在奇數時鐘循環期間，從所述存儲器第二部分中讀出所述目標狀態量度，並把所述讀出的目標狀態量度用作多個對應於第二組收到碼元的中間源狀態量度；對每個所述中間源狀態量度計算中間目標狀態量度；確定哪一個所述中間目標狀態量度含有最低值；把對應於所述最低值中間目標狀態量度的預定邏輯位存入所述存儲器第三部分。
2.如權利要求
1所述的方法，其特徵在於，應用約束長度K對所述第一與第二組收到碼元作編碼，其中，K是大於或等於1的整數。
3.如權利要求
2所述的方法，其特徵在於，執行所述相加-比較-選擇蝶形操作，直到對各所述第一與第二組收到碼元訪問了2k-1種目標狀態的每種狀態。
4.如權利要求
3所述的方法，其特徵在於，用8×1相加-比較-選擇蝶形結構作所述相加-比較-選擇蝶形操作。
5.如權利要求
4所述的方法，其特徵在於，所述多個源狀態量度包括一組16種連續源狀態的量度，所述16種連續源狀態組在增加偶數時鐘循環期間連續選出。
6.如權利要求
5所述的方法，其特徵在於，所述計算目標狀態量度包括把所述源狀態量度加到對應於兩種可能轉換的每種轉換的分支量裡，比較每個所述源狀態量度與分支量度之和，和選擇最小和值，將它定為目標狀態量度。
7.如權利要求
6所述的方法，其特徵在於，所述計算中間目標狀態量度的步驟包括把所述中間源狀態量度加到對應於兩種可能轉換的每種轉換的分支量度裡，比較每個所述中間源狀態量度與分支量度之和，和選擇最小和值並將它定為中間目標狀態量度。
8.如權利要求
7所述的方法，其特徵在於，所述相加-比較-選擇蝶形操作用於對卷積編碼數據作解碼。
9.如權利要求
8所述的方法，其特徵在於，所述存儲器第三部分設置在包含多個存儲字組的回鏈存儲裝置中，每個所述存儲字組對每次所述偶數與奇數時鐘循環包含所述預定邏輯位。
10.如權利要求
8所述的方法，其特徵在於，還包括一種回鏈操作，以便生成多個解碼的位值。
11.如權利要求
10所述的方法，其特徵在於，所述回鏈操作步驟包括對所述回鏈存儲裝置中最新的所述存儲字組，識別含最低值的所述預定邏輯位；使所述最低值邏輯位與一特定地址相關聯；讀取所述預定邏輯位；和將所述最低值邏輯位值移入所述特定地址的最低有效位，並將所述特定地址內的所有值左移一位位置，以便在所述回鏈存儲裝置中確定對應於下一個存儲字組的下一個特定地址。
12.一種對維特比算法實施方案作相加-比較-選擇蝶形操作的系統，其特徵在於，所述系統包括用於存貯多個源狀態量度的存儲器第一部分；與所述存儲器第一部分耦合的復用器，用於在偶數時鐘循環期間選擇第一操作路徑，在奇數時鐘循環期間選擇第二操作路徑；與所述復用器耦合的存儲器第二部分，用於臨時存貯目標狀態量度；與所述存儲器第二部分和所述復用耦合的相加-比較-選擇機構，用於對每個所述源狀態量度計算目標狀態量度；和存儲器第三部分，用於存貯對應於含最低值的被計算目標狀態量度的預定邏輯位；其中，所述復用器在偶數時鐘循環期間選擇第一操作路徑，並將所述源狀態量度從所述存儲器第一部分提供給所述相加-比較-選擇機構，以生成對應於第一組收到碼元的目標狀態量度；和所述復用器在奇數時鐘循環期間選擇第二操作路徑，以便從所述存儲器第二部分讀取目標狀態量度，並將所述讀取的目標狀態量度用作中間源狀態量度，以便所述相加-比較-選擇機構根據對應於第二組收到碼元的所述中間源狀態量度生成中間目標狀態量度。
13.如權利要求
12所述系統，其特徵在於，所述第一與第二組收到碼元用約束長度K編碼，其中，K是大於或等於1的整數。
14.如權利要求
13所述的系統，其特徵在於，執行所述相加-比較-選擇蝶形操作，直到對每個所述第一與第二組收到碼元訪問了每個2k-1種目標狀態。
15.如權利要求
14所述的系統，其特徵在於，用8×1相加-比較-選擇蝶形結構作所述相加-比較-選擇蝶形操作。
16.如權利要求
15所述的系統，其特徵在於，所述多個源狀態量度包括一組16種連續源狀態的量度，所述組的16種連續狀態在增加偶數時鐘循環期間連續選出。
17.如權利要求
12所述的系統，其特徵在於，所述相加-比較-選擇機構通過下述執行所述相加-比較-選擇操作把所述源狀態量度加到對應於每個兩種可能轉換的分支量度裡，比較每個所述源狀態量度與分支量度之和，以及選擇最小和值並把它定為目標狀態量度。
18.如權利要求
17所述的系統，其特徵在於，所述相加-比較-選擇蝶形操作用於對卷積編碼數據作解碼。
19.如權利要求
18所述的系統，其特徵在於，所述存儲器第三部分設置在包含多個存儲字組的回鏈存儲裝置中，每個所述存儲字組對每次所述奇偶數時鐘循環含有所述預定邏輯位。
20.如權利要求
19所述的系統，其特徵在於，所述回鏈存儲裝置生成多個解碼的位值。
21.如權利要求
20所述的系統，其特徵在於，所述回鏈存儲裝置對最新的所述存儲字組識別含最低值的所述預定邏輯位，把所述最低值邏輯位與特定地址相關聯，讀取所述預定邏輯位，而且將所述最低值邏輯位的值移入所述特定地址的最低位，把所述特定地址內所有值左移一位位置，以便在所述回鏈存儲裝置中確定對應於下一存儲字組的下一特定地址。
專利摘要
本發明揭示一種在Viterbi算法實施方案中作相加-比較-選擇(ACS)蝶形操作的系統，包括存貯多個源狀態量度的第一存儲單元(145)；根據奇偶數時鐘循環可在第一與第二操作路徑之間作選擇的復用器(670)；對每個源狀態量度計算目標狀態量度的ACS機構(600)；與ACS機構和復用器耦合併用來臨時存儲目標量度的第二存儲器。因此，復用器在偶數時鐘循環期間選擇第一操作路徑，並把源狀態量度從第一存儲器提供給ACS機構而生成目標狀態量度。在奇數時鐘循環期間，復用器選擇第二操作路徑訪問第二存儲器，並將上一次計算的目標狀態量度用作中間源狀態量度。
文檔編號G06F11/10GKCN1168224SQ00814538
公開日2004年9月22日 申請日期2000年10月23日
發明者D·漢斯奎因, D 漢斯奎因 申請人:高通股份有限公司導出引文BiBTeX, EndNote, RefMan