一種高速並行分段交錯維特比解碼方法

2023-05-08 09:34:31

專利名稱：一種高速並行分段交錯維特比解碼方法
技術領域：
本發明涉及一種高速並行分段交錯維特比(Viterbi)解碼方法，是針對卷積編碼 的高速並行Viterbi解碼方法，主要用於對解調後數據進行高速維特比解碼，糾正信道傳 輸過程產生的錯誤。
背景技術：
卷積碼是一種應用非常廣泛的信道編碼，主要用於糾正信道傳輸中產生的隨機錯 誤。卷積碼主要有三種較好的解碼算法(1) 1963年由Massey提出的門限解碼，這是一種利用碼代數結構的代數解碼方 法，類似於分組碼中的大數邏輯解碼；(2) 1961年由Wozencraft提出，1963年由Fano改進的序列解碼，這是基於碼樹圖 結構上的一種準最佳的概率解碼；(3) 1967年Viterbi提出的Viterbi算法，這是基於碼的網格圖(Trellis)基礎上 的一種最大似然算法，是一種最佳概率解碼方法。代數解碼僅用於簡單的卷積碼，優點是解碼電路簡單而且延時小，適用於高速應 用；缺點是編碼增益一般都不大，而且只能適用於硬判決解碼。序列解碼和Viterbi解碼都 屬於概率解碼，由於它們不僅基於碼的代數結構，而且利用了信道的統計特性，因而能充分 發揮卷積碼的特點，使解碼錯誤概率達到很小。Viterbi解碼在碼的約束度較小時，比序列 解碼算法效率更高，速度更快，解碼器也更簡單。因此Viterbi解碼得到了廣泛應用，特別 是在空間通信系統中。CCSDS建議採用3比特量化的Viterbi解碼。Viterbi解碼算法的原理是將接收碼和本地生成碼比較，基於卷積碼的網格圖表 示法，依據接收到的信息作為先驗信息，從所有可能的路徑中選擇出最可能的序列作為輸 出。Viterbi解碼器一般由三部分組成(1) BMU (分支度量值單元)；(2) ACSU (加比選單元)；(3) SMU (倖存路徑存儲單元)。如附圖1所示，由於Viterbi解碼算法中存在反饋迴路，如果只利用現有Viterbi 解碼算法本身的並行結構，Viterbi解碼器的速率將受到限制，目前一般單路Viterbi解碼 器的解碼速率最高只能達到300Mbit/s左右。要實現更高速率的Viterbi解碼器，就需要 在Viterbi解碼算法中引入額外的並行結構。但是由於Viterbi解碼過程是一個連續的譯 碼過程，必須接收連續輸入的比特流，在網格圖上按照最大似然原理尋找編碼序列，這就導 致無法直接將輸入數據轉換為並行數據進行並行解碼處理。上述問題造成了在目前技術 基礎下，Viterbi解碼算法能夠實現的最高解碼速率有一個上限，這個上限取決於器件水平 以及解碼算法的優化程度。此時，即使還有足夠多的硬體資源可用，但由於無法並行實現， Viterbi解碼器的解碼速率也無法再提高。為了解決該難題，通常採取的措施是在發送端 採用多個卷積編碼器，再結合多進位調製，接收端解調後同樣採用多個Viterbi解碼器進行解碼，這樣也相當於進行了並行解碼。但是上述措施並沒有從根本上解決問題，當單路 Viterbi解碼需要較高的速率時，上述措施將失效，且成本投入變大，浪費了資源。

發明內容
本發明的技術解決問題是克服現有技術的不足，提供了一種高速並行分段交錯 維特比(Viterbi)解碼方法，此解碼方法提出了單路Viterbi解碼過程的並行解碼方法，大 大提高了解碼速率。本發明的技術解決方案是一種高速並行分段交錯維特比解碼方法，步驟如下(1)將虛擬比特插入輸入數據中，之後進入步驟(2)；所述輸入數據為卷積編碼器 各支路輸出交錯排列後經1 8串並轉換形成的Sbit並行數據；(2)復位第i個Viterbi解碼器之後進入步驟(3)，所述i為大於等於1且小於等 於m的自然數，i初始化為1，m為Viterbi解碼器的數量，且m彡2 ；(3)將步驟(1)中得到的數據寫入第i個Viterbi解碼器的輸入FIFO中，當寫入 1個字節後啟動步驟(7)，步驟(7)與步驟(3)並行；當共寫入了 n-J個字節之後，進入步驟 (4)；所述η為每個Viterbi解碼器單次解碼處理的數據長度，且η > 6k，k為卷積編碼器的 約束長度；所述J為連續兩個Viterbi解碼器單次解碼處理的數據的交錯長度；(4)復位第i+Ι個Viterbi解碼器之後進入步驟(5)；(5)將步驟(4)中寫入n-J個字節之後的第一個字節寫入第i個Viterbi解碼器 的輸入FIFO和第i+Ι個Viterbi解碼器的輸入FIFO中之後啟動步驟(7)，步驟(7)與步 驟(5)並行；當將步驟(4)中寫入n-J個字節之後的共計J個字節的數據同時寫入第i個 Viterbi解碼器的輸入FIFO和第i+Ι個Viterbi解碼器的輸入FIFO中之後，再將寫入J 個字節之後的n-2J個字節的數據第i+Ι個Viterbi解碼器的輸入FIFO中，之後進入步驟 (6)；(6)判斷i是否等於m，若等於，則復位第1個Viterbi解碼器並將步驟(5)中寫 入n-2J個字節數據之後的J個字節的數據同時寫入第i個Viterbi解碼器的輸入FIFO和 第1個Viterbi解碼器的輸入FIFO中，之後令i = 1，返回步驟(3)；若不等於，則將i+Ι賦 值給i，之後返回步驟⑷；(7)當前Viterbi解碼器的輸入FIFO非空時由該Viterbi解碼器開始進行解碼並 將解碼結果存入該Viterbi解碼器對應的輸出FIFO中，當該Viterbi解碼器將其輸入FIFO 中的數據解碼完成之後進入步驟(8)；(8)讀取當前Viterbi解碼器的輸出FIFO中的數據並輸出，當該Viterbi解碼器 的輸出FIFO讀空之後，讀取下一個Viterbi解碼器的輸出FIFO中的數據並輸出。所述步驟(1)中插入虛擬比特按照如下步驟進行(a)根據虛擬比特參數判斷是否需要插入虛擬比特，若需要插入，則將輸入數據 按照打孔圖樣插入虛擬比特並寫入數據輸出緩存中，同時，將對應打孔圖樣的虛擬比特指 示信號同步寫入指示信號緩存中，之後進入步驟(b)；若不需要插入，則將輸入數據直接輸 出；所述虛擬比特參數和打孔圖樣根據所使用的卷積碼編碼類型確定；(b)判斷步驟(a)中所述數據輸出緩存是否為空，若為空，則返回步驟(a)；若不為空，則同時讀取數據輸出緩存和指示信號緩存中的數據，並輸出。本發明與現有技術相比的有益效果是(1)本發明通過採用多級並行分段交錯Viterbi解碼方法，解決了卷積編碼拆分 為若干段獨立碼流之後，無法並行解碼的問題，使得在Viterbi解碼器的基礎上可以將輸 入數據轉換為並行數據進行並行Viterbi解碼處理，大大加快了解碼速率，使得現有技術 當中Viterbi解碼算法能夠實現的最高解碼速率有一個瓶頸的問題得到了妥善的解決。(2)本發明通過在虛擬比特插入時同步生成虛擬比特指示信號，不僅能夠適應 CCSDS標準規定的各種卷積編碼打孔模式，而且可以方便的擴展為其它打孔模式。(3)本發明通過採用模塊化設計，需要提高並行度時，直接增加Viterbi解碼器的 數量，修改相關參數即可進一步提高解碼速率。


圖1為Viterbi解碼器組成圖；圖2是本發明虛擬比特插入流程圖；圖3是本發明高速分段交錯Viterbi解碼方法流程圖。
具體實施例方式下面結合附圖對本發明的具體實施方式
進行進一步的詳細描述。卷積碼是一種信道編碼格式，它是應用最廣泛的信道編碼之一，維特比(Viterbi) 解碼算法是一種有效的卷積碼解碼算法。卷積碼的主要用途是克服衰落信道中產生的隨機 錯誤，它還常常作為外碼與RS碼級聯使用，以便獲得更大的編碼增益。伴隨著空間通信技 術的發展，數據傳輸碼速率不斷提高，Viterbi解碼速率也需要相應提高以適應發展需求。 本發明主要解決Vlterbi解碼器實現中如何提高解碼速率的問題，通過採用本發明提出的 解碼方法，可以大幅度提高解碼速率，兼容各種卷積編碼打孔模式，能夠直接應用於高碼速 率遙感衛星地面接收系統。本發明一種高速並行分段交錯維特比(Viterbi)解碼方法步驟如圖3所示(1)將虛擬比特插入輸入數據中，之後進入步驟(2)；所述輸入數據為卷積編碼器 各支路輸出交錯排列後經1 8串並轉換形成的Sbit並行數據；數據發送端的卷積編碼器 輸出數據格式為I 支路 C1C1C1C1 ；Q支路C2C2C2C2或C2C2C2C2 (下劃線表示取反，下同)。I路和Q路數據將送往調製器調製後發射；解調器將採用逆過程恢復I路和Q路 數據。本解碼方法的輸入數據為8bit並行數據，該Sbit並行數據指下述格式C1C2C1C2C1C2C1C2或Cl位Cl位Cl位Cl位經過1 8串並轉換後形成的各支路輸 出交錯排列的並行數據。解碼器採用軟判決解碼時，該並行數據需要相應的擴展為軟判決
量化位數。(2)復位第i個Viterbi解碼器之後進入步驟(3)，所述i為大於等於1且小於等 於m的自然數，i初始化為1，m為Viterbi解碼器的數量，且m彡2 ；(3)將步驟(1)中得到的數據寫入第i個Viterbi解碼器的輸入FIFO中，當寫入
51個字節後啟動步驟(7)，步驟(7)與步驟(3)並行，意思是步驟(3)繼續正常運行，但是步 驟(7)也同時運行，兩個是相互獨立的進程，同時運行；當共寫入了 n-J個字節之後，進入步 驟(4)；所述η為每個Viterbi解碼器單次解碼處理的數據長度，且η > 6k，k為卷積編碼 器的約束長度；所述J為連續兩個Viterbi解碼器單次解碼處理的數據的交錯長度；(4)復位第i+Ι個Viterbi解碼器之後進入步驟(5)；(5)將步驟(4)中寫入n-J個字節之後的第一個字節寫入第i個Viterbi解碼 器的輸入FIFO和第i+Ι個Viterbi解碼器的輸入FIFO中之後啟動步驟(7)，步驟(7)與 步驟(5)並行；當共將步驟(4)中寫入n-J個字節之後的J個字節的數據同時寫入第i個 Viterbi解碼器的輸入FIFO和第i+Ι個Viterbi解碼器的輸入FIFO中之後，再將寫入J個 字節之後的n-2J個字節的數據寫入第i+Ι個Viterbi解碼器的輸入FIFO中，之後進入步 驟(6)；(6)判斷i是否等於m，若等於，則復位第1個Viterbi解碼器並將步驟(5)中寫 入n-2J個字節數據之後的J個字節的數據同時寫入第i個Viterbi解碼器的輸入FIFO和 第1個Viterbi解碼器的輸入FIFO中，之後令i = 1，返回步驟(3)；若不等於，則將i+Ι賦 值給i，之後返回步驟⑷；步驟(2)至(6)即為分段交錯Viterbi解碼過程的數據分段交錯過程，它是為了 解決Viterbi解碼算法無法直接並行處理的問題。基本原理是先將輸入數據先進行串並 轉換，將時鐘頻率降低，然後將輸入數據分段交錯後分配給多個解碼器核，從而實現並行處 理。每個解碼器中設置數據緩衝區，將輸入數據緩存後再解碼。數據交錯的目的在於保留 一定長度的前一段數據，進而保留相關信息，否則下一段解碼過程將出現錯誤。最小的相關 長度應該是約束長度除以碼率。對於卷積(2，1，7)碼為7/(1/2) = 14在滿足最小分段長度和交錯深度的條件下，如果將分段長度確定為η = 6Byte = 48bits > 42bits (解碼截尾長度)，交錯長度確定為J = 2Byte = 16bits > 14bits。此 時，由於交錯過程造成的數據冗餘，需要多個Viterbi解碼器同時處理才能保證連續解碼。 假定使用10個Viterbi解碼器，當每個解碼器解碼速率為100Mbit/S的前提條件下，整個 Viterbi解碼器總的解碼速率將可達到100X10 = 1000Mbit/S但由於數據交錯造成了冗餘，因此實際解碼速率將低於該值，降低的比例將取決 於交錯長度與分段長度之比。在最後一個解碼器完成數據輸入後，數據切回到第一個譯 碼器，此時該解碼器應已經完成所緩存數據的解碼，並復位到初始狀態，以便接收下一段數 據。每個解碼器輸入新的數據前均應復位，以便回到初始狀態。根據上述分析，設分段長度為n，交錯長度為J，所需的解碼器數量為m，回溯深度 為t。如果確定交錯長度為J = 2Byte，輸入到某一解碼器的輸入數據所需處理時間為 8n+42 ；該解碼器下一次輸入新數據的間隔為(n-k) m-J ；則應滿足下述關係8n+t 彡(n-J) m-J
η和m均不應過大，否則FPGA實現時硬體消耗會太大。η和m均應為自然數，mmin =8+1 = 9。當取m = 10時可得η = 32。可以根據所需的解碼速率和晶片容量選擇合適 的分組長度和並行解碼器數量。為了在每個解碼器輸入新數據前使其可靠的復位，可以多冗餘!·個時鐘周期，用 於產生復位信號，並確保解碼器可靠工作。讀出解碼數據字寬為8bit，所以共需(n-2)/2個 時鐘周期，因此8n+r+t+(n-l)/2 彡(n-J)m當 m = 10 時，取 r = 14 可得 η = 50。(7)當前Viterbi解碼器的輸入FIFO非空時由該Viterbi解碼器開始進行解碼並 將解碼結果存入該Viterbi解碼器對應的輸出FIFO中，當該Viterbi解碼器將其輸入FIFO 中的數據解碼完成之後進入步驟(8)；上述過程中使用Viterbi解碼器進行解碼為本領域的公知技術，就是普通常用的 Viterbi解碼器以及解碼方法。(8)讀取當前Viterbi解碼器的輸出FIFO中的數據並輸出，當該Viterbi解碼器 的輸出FIFO讀空之後，讀取下一個Viterbi解碼器的輸出FIFO中的數據並輸出。上述過程是分段交錯並行Viterbi解碼過程中的數據拼接過程，各Viterbi解碼 器的輸出為串行比特流，數據拼接器根據各Viterbi解碼器的數據輸出FIFO的「滿」信號 驅動，按照8bit字寬從各個FIFO依次讀出解碼後數據並輸出。如圖2所示，插入虛擬比特按照如下步驟進行(a)根據虛擬比特參數判斷是否需要插入虛擬比特，若需要插入，則將輸入數據 按照打孔圖樣插入虛擬比特並寫入數據輸出緩存中，同時，將對應打孔圖樣的虛擬比特指 示信號同步寫入指示信號緩存中，之後進入步驟(b)；若不需要插入，則將輸入數據直接輸 出；所述虛擬比特參數和打孔圖樣根據所使用的卷積碼編碼類型確定；上面所述打孔圖樣 為CCSDS標準規定的卷積編碼所擁有的打孔模式，如果卷積編碼模式已知，則打孔模式、打 孔圖樣即為已知。(b)判斷步驟(a)中所述數據輸出緩存是否為空，若為空，則返回步驟(a)；若不為 空，則同時讀取數據輸出緩存和指示信號緩存中的數據，並輸出經過大量仿真及工程測試，使用該方法可使Viterbi解碼速率達到800Mbit/s，優 於目前文獻中發表的同類型解碼器的性能指標，在需要時可以進一步通過增加並行度提高 性能。本發明說明書中未作詳細描述的內容屬於本領域的公知技術。
權利要求
一種高速並行分段交錯維特比解碼方法，其特徵在於步驟如下(1)將虛擬比特插入輸入數據中，之後進入步驟(2)；所述輸入數據為卷積編碼器各支路輸出交錯排列後經1∶8串並轉換形成的8bit並行數據；(2)復位第i個Viterbi解碼器之後進入步驟(3)，所述i為大於等於1且小於等於m的自然數，i初始化為1，m為Viterbi解碼器的數量，且m≥2；(3)將步驟(1)中得到的數據寫入第i個Viterbi解碼器的輸入FIFO中，當寫入1個字節後啟動步驟(7)，步驟(7)與步驟(3)並行；當共寫入了n J個字節之後，進入步驟(4)；所述n為每個Viterbi解碼器單次解碼處理的數據長度，且n＞6k，k為卷積編碼器的約束長度；所述J為連續兩個Viterbi解碼器單次解碼處理的數據的交錯長度；(4)復位第i+1個Viterbi解碼器之後進入步驟(5)；(5)將步驟(4)中寫入n J個字節之後的第一個字節寫入第i個Viterbi解碼器的輸入FIFO和第i+1個Viterbi解碼器的輸入FIFO中之後啟動步驟(7)，步驟(7)與步驟(5)並行；當將步驟(4)中寫入n J個字節之後的共計J個字節的數據同時寫入第i個Viterbi解碼器的輸入FIFO和第i+1個Viterbi解碼器的輸入FIFO中之後，再將寫入J個字節之後的n 2J個字節的數據第i+1個Viterbi解碼器的輸入FIFO中，之後進入步驟(6)；(6)判斷i是否等於m，若等於，則復位第1個Viterbi解碼器並將步驟(5)中寫入n 2J個字節數據之後的J個字節的數據同時寫入第i個Viterbi解碼器的輸入FIFO和第1個Viterbi解碼器的輸入FIFO中，之後令i＝1，返回步驟(3)；若不等於，則將i+1賦值給i，之後返回步驟(4)；(7)當前Viterbi解碼器的輸入FIFO非空時由該Viterbi解碼器開始進行解碼並將解碼結果存入該Viterbi解碼器對應的輸出FIFO中，當該Viterbi解碼器將輸入FIFO中的數據解碼完成之後進入步驟(8)；(8)讀取當前Viterbi解碼器的輸出FIFO中的數據並輸出，當該Viterbi解碼器的輸出FIFO讀空之後，讀取下一個Viterbi解碼器的輸出FIFO中的數據並輸出。
2.根據權利要求1所述一種高速並行分段交錯維特比解碼方法，其特徵在於，所述步 驟(1)中插入虛擬比特按照如下步驟進行(a)根據虛擬比特參數判斷是否需要插入虛擬比特，若需要插入，則將輸入數據按照打 孔圖樣插入虛擬比特並寫入數據輸出緩存中，同時，將對應打孔圖樣的虛擬比特指示信號 同步寫入指示信號緩存中，之後進入步驟(b)；若不需要插入，則將輸入數據直接輸出；所 述虛擬比特參數和打孔圖樣根據所使用的卷積碼編碼類型確定；(b)判斷步驟(a)中所述數據輸出緩存是否為空，若為空，則返回步驟(a)；若不為空， 則同時讀取數據輸出緩存和指示信號緩存中的數據，並輸出。
全文摘要
一種高速並行分段交錯維特比(Viterbi)解碼方法，通過採用多級並行分段交錯Viterbi解碼方法，使解碼速率大大提高，通過在虛擬比特插入時同步生成虛擬比特指示信號，不僅能夠適應CCSDS標準規定的各種卷積編碼打孔模式，而且可以方便的擴展為其它打孔模式，通過採用模塊化設計，在需要時可以進一步通過增加並行度提高性能，本發明通過大量軟體仿真實驗和實際測試結果表明，使用本發明高速並行分段交錯Viterbi解碼方法可使Viterbi解碼速率達到800Mbit/s，優於目前文獻中發表的同類型解碼器的性能指標。
文檔編號H03M13/27GK101969311SQ20101029787
公開日2011年2月9日 申請日期2010年9月29日 優先權日2010年9月29日
發明者張拯寧, 戰勇傑 申請人:航天恆星科技有限公司