基於樹狀或籬柵圖之迴旋碼解碼演算法

Abstract

本論文主要提出新的迴旋碼解碼演算法能夠透過樹狀或籬柵圖來做解碼。傳統的循序解碼法(sequential decoding)是沿著樹狀做解碼，所得到的效能只能是次佳的。基於這個理由，促使我們企圖去尋找一種能夠達到最佳效能的演算法。因此，我們提出一種在白色高斯環境下能達到最佳效能的樹狀解碼演算法。這種演算法稱做分支與邊界法(branch-and-bound)，此方法主要是能夠很有效的搜尋到最佳的解。另外，在低的訊號雜音比環境下，為了能夠降低搜尋的複雜度，我們提出的新的量度(metric)並且建議使用兩階段演算法。再來，次佳的演算法被提出來，是基於降低複雜度的考量。最後，我們發現分支與邊界法也可以在籬柵圖上做搜尋，因此我們將這種搜尋的原理應用到維特比(Viterbi)演算法上做解碼。一般認為迴旋碼的維特比演算法複雜度是一個固定的量且正比於編碼訊號的長度。而我們提出來的調整型維特比演算法（modified-Viterbi）不僅可以降低複雜度且不會犧牲原有的效能。

This thesis proposed new tree-based and trellis-based decoding algorithms for convolutional codes. Traditional sequential approaches for decoding convolutional codes operate along a tree, yielding only suboptimal performance. This motivate us to explore new approaches to enhance the decoder performance. We propose a tree-based algorithm that achieve the optimal (maximum likelihood) performance in additive white Gaussian noise (AWGN) channels. To reduce the complexity in low signal-to-noise ratio environments, a new metric and a two-stage algorithm are suggested. Suboptimal approaches are also proposed to reduce the decoder complexity. Finally, we apply the branch-and-bound principle to develop a trellis-based Viberti-like decoding algorithm. Conventional Viterbi algorithm has a constant complexity proportional to the codeword length. The proposed modified Viterbi algorithm can reduce the decoder complexity without sacrifice the error rate performance.