排列碼與其高效率之編解碼演算法

Abstract

(n,d) Permutation array 是Sn的子集並且其中任兩個元素的距離大於d(對任意的metric,如hamming).permutation array 常應用在電力傳輸系統當中.我同時考慮了hamming distance 以及 l∞-norm 來當做距離函數,並且構造了(n,d)permutation array. 對hamming distance我們給出了第一個3-DPMH.對l∞-norm, 我不只給出了DPM∞也給出了一個直接的方法構造(n,d) permutation array.更重要的是,這些permutation array都有高效率之編解碼演算法.

An (n,d) permutation array (PA) is a subset of Sn with the property that the distance (under any distance metric, such as hamming) between any two permutations in the array is at least d, which becomes popular recently for communication over power line. We use both hamming distance and l∞- norm to measure the distance between permutations, and give constructions of permutations arrays under those two metrics. For the hamming distance, we give the first explicit construction of 3-DPMH. For the l∞-norm, we give the first explicit construction of DPM∞ and a direct construction of (n, d) permutation array with l∞-norm without using other binary code. Furthermore, all have efficient encoding and decoding algorithms.