頻率排列碼

Abstract

令n為正整數m與λ的乘積。一個長度為n、最小距離為d的頻率排列碼(frequency permutation array，簡稱FPA)是一個包含若干個由m個符號各重複出現λ次所形成的排列，並且其中相異的兩個排列的距離至少為d。FPA是排列碼(permutation array，簡稱PA)的一般化，PA即是FPA取λ=1時的特例。目前PA已有許多領域的應用，諸如電力線通訊、快閃記憶體資料儲存以及密碼學。FPA具有比PA更大的設計彈性，因此在各方面應用上均有較PA更高的潛力。

在本篇論文中，吾人透過估計特定半徑內的頻率排列個數，證明了在柴比雪夫距離(Chebyshev distance)下，FPA元素數量之Sphere-packing類型上界以及Gilbert-Varshamov類型下界。此外，吾人亦提出兩個有效率的演算法，用以正確計算出特定半徑內的頻率排列個數。其中之一能在O((2dλ取dλ)^(2.376)logn)的時間複雜度以及O((2dλ取dλ)^(2))的空間複雜度完成計算。另外一個則僅需O((2dλ取dλ)(dλ+λ取λ)n/λ)的時間與O((2dλ取dλ))的空間資源便能完成。當λ與d均為常數時，這兩個演算法均能有效率的求出特定半徑內的頻率排列個數。

吾人發明數個建造FPA的方法，並藉由此推導出對應的FPA元素數量下界。這些建造的方法中，有些類型的FPA具有高效率的編碼與解碼方式，而其中一個更具有區域可解碼演算法以及列表可解碼演算法。吾人展示了如何在僅讀取λ+1個符號的情況下，解出一個資訊符號，以及針對一個任意給定的排列，如何找出所有特定距離內FPA中的元素。此外，藉由區域可解碼演算法，吾人亦造出一個私密資料取回的安全協定。

吾人透過研究子群碼(subgroup code)的性質，證明了在一般情況下，計算出任一FPA的最小距離是困難的。子群碼是PA的一個特例，其中任兩個元素，在函數合成的運算下，具有封閉性。吾人證明，在柴比雪夫距離下，計算子群碼的最小距離，等價於計算其中非(non-identity permutation)之最小權重。更進一步的，吾人證明了後者係為一NP-complete問題，以及對任一常數ε，逼近子群碼之最小距離至2-ε的倍率，亦為NP-hard。

Let $m$ and $\lambda$ be positive integers. A frequency permutation array (FPA) of length $n=m\lambda$ and distance $d$ is a set of permutations on a multiset over $m$ symbols, where each symbol appears exactly $\lambda$ times and the distance between any two elements in the array is at least $d$. FPA generalizes the notion of permutation array (PA), which is a special case of FPA by choosing $\lambda=1$. PAs are known for various applications in power line communication, flash memories and cryptography. FPAs are more flexible than PAs, since the length and the symbol set size of a PA must be equal. FPAs are potentially better than PAs in various of applications. For example, FPAs have higher information rate than PAs do when their symbol sets are the same.

In this thesis, under Chebysheve distance, we prove a Gilbert-Varshamov type lower bound and a sphere-packing type upper bound on the cardinality of FPA via bounding the size of balls of certain radii. Moreover, we propose two efficient algorithms that compute the ball size under Chebyshev distance. The first one runs in $\bigO{{{2d\lambda}\choose{d\lambda}}^{2.376}\log n}$ time and $\bigO{{{2d\lambda}\choose{d\lambda}}^{2}}$ space. The second one runs in $\bigO{\binom{2d\lambda}{d\lambda}\binom{d\lambda+\lambda}{\lambda}\frac{n}{\lambda}}$ time and $\bigO{\binom{2d\lambda}{d\lambda}}$ space. For small constants $\lambda$ and $d$, both are efficient in time and use constant storage space.

We give several constructions of FPAs, and we also derive lower bounds from these constructions. Some types of our FPAs come with efficient encoding and decoding capabilities. In addition, we show one of our designs is locally decodable and list decodable. In other words, we illustrate how to decode a message bit by reading at most $\lambda+1$ symbols, and how to find the list of all codewords within a certain distance. Furthermore, we propose an FPA-based private information retrieval scheme, which follows from the locally decodable property.

On the other hand, we show that it is hard in general to determine the minimum distance of an arbitrary FPA by investigating subgroup codes. Subgroup permutation codes are permutation arrays exhibiting group algebra structures with the composition operator. Under Chebyshev distance, we prove that to determine the minimum distance of a subgroup code is equivalent to finding the minimum weight of non-identity codewords in a subgroup permutation code. Moreover, we prove the latter is $\NP$-complete and it is $\NP$-hard to approximate the minimum distance of a subgroup code within the factor $2-\epsilon$ for any constant $\epsilon>0$.