向量至排列之保距映射之建構與分析

Abstract

一個從長度為n的所有q元向量所成之集合，到 {1, 2, … , N} 所有可能排列所成之集合(N □ n)的映射，若任二個向量所對應之排列彼此之間的漢明距離(Hamming distance) 大於或等於原本向量之間的漢明距離，稱之為『保距映射』(distance-preserving mapping)。有一種特殊的『保距映射』，會讓排列之間的漢明距離絕對大於原本向量之間的漢明距離，除非在不可能的情況之下。這種映射稱之為『增距映射』(distance-increasing mapping)。在本論文中，我們提出數個建構方法，以建構從二元向量(binary vectors)至排列的『增距映射』。跟早期發表的方法比起來，這些方法具有某些優點。另外，我們也會提出幾個建構方法，以建構從三元向量(ternary vectors)至排列的『保距映射』與『增距映射』。這是在文獻中，第一次有人提出源自三元向量的『保距映射』與『增距映射』之建構方法。這些建構方法的一項貢獻是它們可以用來提升一個下限量 — 『排列陣列』(permutation arrays)，又稱為『排列碼』(permutation codes) 的大小的最大下限。在設計一個以電源線為媒介的通訊系統時，『排列碼』是一種很有用的碼。

A mapping from the set of all q-ary vectors of length n to the set of all permutations of {1, 2, … , N} where N □ n is called a distance-preserving mapping (DPM) if every two vectors are mapped to permutations with the same or even larger Hamming distance than that of the vectors. A distance-increasing mapping (DIM) is a special DPM such that the distances of mapped permutations are strictly increased except when that is obviously not possible. In this dissertation, we propose several constructions of DIMs from binary vectors. These constructions possess some advantages over previous proposed constructions. In addition, we also propose constructions of DPMs and DIMs from ternary vectors. This is the first time that constructions of DPMs and DIMs from ternary vectors are proposed in the literature. A contribution of these constructions is their application to the improvement of the lower bounds on the maximal size of permutation arrays (or permutation codes), which are useful in the design of a power line communication system.