Abstract
一個線性塊碼 (Linear Block Code) 的籬圖尺寸 (trellis size)大小， 反映出了使用 Viterbi Algorithm來進行解碼的複雜度。而將一個線性塊 碼的座標位置重新排列(permutation) 後，可以得到另一個具有相同功能 的等效碼 (equivalent code) ，但是其籬圖結構 (trellis structure) 可能會因此而改變。換言之，重排 (permutation) 作用 (action) 在一 個線性塊碼，可以改變其籬圖尺寸 (trellis size) 大小。而要能製作出 一個有效率的解碼器出來，首先就是要找出具有最小籬圖尺寸 (minimal trellis size)的等效碼出來，此種稱之為最佳對等碼 (optimal equivalent code)。然而，若由列舉所有的重排 (permutation) 的方式 來找尋，則將因為重排 (permutation)的數量過於龐大 (對於長度為 n 的塊碼而言，將有 n! 可能的重排數)，而使得此種方式變成不切實際。 本文即是要發展一套理論，再以此為基礎提出一套演算法則，以便能很有 效率地找出最佳對等碼。在此所提的方法，是將一重排 (permutation) 分割成 k 部份 (k 為塊碼的 dimension )，在一一找出最佳重排 (optimal permutation) 的 k 部份出來後，再將其組合成一個重排。為 了要能分析此種演算法則，文中定義並發展了許多新的觀念，如 index sequences, chain of subsets, support chain, ... 等。最後再將此法 則應用到找尋長度小於 31 的循環碼 (cyclic codes，共計有 80 種不同 的碼)，的最佳對等碼 (optimal equivalent code) 。在附錄中並列舉出 已經找到的這些最佳對等碼，這些可以作為設計解碼器時的參考資料。 The absolute trellis size of a linear block code determines the minimum possible complexity of the maximum likelihood decoding algorithm using a trellis. Moreover, an optimal permutation together with the corresponding optimal equivalent code, whose trellis size is just the absolute trellis size, should be found out before implementing the decoder. An efficient algorithm to find out such an optimal permutation and its corresponding optimal equivalent code for any given linear block code is developed in this thesis. Its reality is confirmed by the development of several new concepts and athe algorithm will be terminated in one iteration. This algorithm could also begin with an estimate of the absolute trellis size of the given linear block code, either by an upper bound or by a lower bound. The more accurate the estimate is, the less iterations the search algorithm spends on. And, the exact absolute trellis size of the given code can also be an output of the algorithm. For this purpose, a new lower bound of the absolute trellis size is presented, which is related to the generalized Hamming weight hierarchy of the given linear block code and is the best lower bound up to now.