臺灣博碩士論文加值系統

令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$.

1 Introduction 1
1.1 Permutation Arrays and Their Applcations 1
1.2 Frequency Permutation Arrays 4
1.3 Our Results 5
1.4 Organization of the Thesis 6

2 Preliminaries 7
2.1 Notations 7
2.2 CodingTheory 11
2.3 ComputationalComplexity 13

3 Explicit Lower and Upper Bounds 17
3.1 Gilbert Type and Sphere Packing Bounds 17
3.2 Enumerate Permutations in a Ball 22
3.3 Compute the Ball Size 27

4 Constructions and Related Bounds 33
4.1 An Explicit Construction 33
4.2 Recursive Constructions 34

5 Codes with Efficient Encoding and Decoding 41
5.1 Encoding Algorithm 41
5.2 Unique Decoding Algorithm 43
5.3 Local Decoding Algorithm 44
5.4 List Decoding Algorithm 46
5.5 Private Information Retrieval 48

6 Complexity Issues 51
6.1 Complexity Problems Related to FPAs 51
6.2 Minimum Distance of Subgroup Codes 53
6.3 Cameron-Wu's Reduction 68

7 Conclusion and Future Works 71
7.1 Conclusion 71
7.2 Future Works 71
7.3 Code-Anticode Type Bounds 73
7.4 Steganography 73
7.5 CoveringRadius 74

A Tables of Ball Size 83
B Program Codes 93
B.1 Computing the Ball Size in Python3 93

[1] S. Arora, L. Babai, J. Stern, Z. Sweedyk, “The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations,” Journal of Computer and System Science, vol. 54, 1997, pp. 317–331.
[2] S. Arora, B. Barak, Computational Complexity, Cambridge University Press, 2009. [3] A. A. Babaev, “Procedures of Encoding and Decoding of Permutations,” Cybernetics and
Systems Analysis, vol. 20, pp. 861–86 1984.
[4] E. R. Berlekamp, R. J. McEliece, H. C.A. van Tilborg, “On the Inherent Intractibility of Certain Coding Problems,” IEEE Transactions on Information Theory, pp. 384–386,
1978. [5] I. Blake, “Permutation Codes for Discrete Channels,” IEEE Transactions on Information
Theory, vol. 20, pp. 138–140, 1974. [6] C. Buchheim, P. J. Cameron, T. Wu, “On the Subgroup Distance Problem,” Discrete
Mathematics, vol. 309, pp. 962–968, 2009. [7] P. J. Cameron, T. Wu, “The Complexity of the Weight Problem for Permutation and
Matrix Groups,” Discrete Mathematics, vol. 310, pp. 408–416, 2010. [8] P. Cappelletti, C. Golla, P. Olivo, E. Zanoni, Flash Memories, Kluwer Academic Pub-
lishers, 1999.
[9] J.-C. Chang, R.-J. Chen, T. Kl?憝e, S.-C. Tsai, “Distance-Preserving Mappings from Binary Vectors to Permutations,” IEEE Transactions on Information Theory, vol. 49, pp. 1054–1059, 2003.
[10] J.-C. Chang, “Distance-Increasing Mappings from Binary Vectors to Permutations,” IEEE Transactions on Information Theory, vol. IT-51, pp. 359–363, 2005.
[11] J.-C. Chang, “Distance-Increasing Mappings from Binary Vectors to Permutations that Increase Hamming Distances by at Least Two,” IEEE Transactions on Information Theory, vol. 52, pp. 1683–1689, 2006.
[12] C. J. Colbourn, T. Kl?憝e, “Permutation Arrays for Powerline Communication and Mutually Orthogonal Latin Squares,” IEEE Transactions on Information Theory, vol. 50, pp. 1289–1291, 2004.
[13] D. R. de la Torre, C. J. Colbourn, and A. C. H. Ling, “An Application of Permutation Arrays to Block Cipher,” Congressus Numerantium, vol. 145, pp. 5–7, 2000.
[14] M. Deza, S. A. Vanstone, “Bounds on Permutation Arrays,” Journal of Statistical Plan-
ning and Inference, vol. 2, pp. 19–209, 1978.
[15] I. Dinur, “Approximating SVP∞ to within almost Polynomial Factors is NP-hard,” Combinatorica, vol. 23, pp. 205–243, 2003.
[16] K. Efremenko, “3-Query Locally Decodable Codes of Subexponential Length,” in Proceedings of ACM Symposium on Theory of Computing, pp. 39–44, 2009.
[17] S. Huczynska, G. L. Mullen, “Frequency Permutation Arrays,” Journal of Combinatorial Designs, vol. 14, pp. 463–478, 2006.
[18] J. Fridrich and D. Soukal, “Matrix Embedding for Large Payloads,” IEEE Transactions on Information Forensics and Security, vol. 1, pp. 390–395, 2006.
[19] D. Inoue, T. Matsumoto, “A scheme of Standard MIDI Files steganography and its evaluation,” Security and Watermarking of Multimedia Contents IV, pp. 194–205, 2002.
[20] A. Jiang, R. Mateescu, M. Schwartz, J. Bruck, “Rank Modulation for Flash Memories,” in Proceedings of IEEE International Symposium on Information Theory, pp. 1731–1735, 2008.
[21] A. Jiang, M. Schwartz and J. Bruck, “Error-Correcting Codes for Rank Modulation,” in Proceedings of IEEE International Symposium on Information Theory, pp. 1736–1740, 2008.
[22] S. Khot, “Hardness of Approximating the Shortest Vector Problem in Lattices,” Journal of the ACM, Vol. 52, pp. 789–808, 2005.
[23] T. Kl?憝e, “Spheres of Permutations under the Infinity Norm - Permutations with Limited Displacement,” Reports in Informatics, Dept. of Informatics, Univ. Bergen, Report no. 376, 2008.
[24] T. Kl?憝e, “Frequency Permutation Arrays within Distance one,” Reports in Informatics, Dept. of Informatics, Univ. Bergen, Report no. 382, 2009.
[25] T. Kl?憝e, “Lower Bounds on the Size of Spheres of Permutations under the Chebychev
Distance,” Designs, Codes and Cryptography, vol. 59, pp. 183–191, 2011.
[26] T. Kl?憝e, T.-T. Lin, S.-C. Tsai, W.-G. Tzeng, “Permutation Arrays Under the Chebyshev Distance,” IEEE Transactions on Information Theory, vol. 56, pp. 2611–2617, 2010.
[27] M. Kwan, The GIF Shuffle, http://www.darkside.com.au/gifshuffle/
[28] T.-T. Lin, S.-C. Tsai, W.-G. Tzeng, “Efficient Encoding and Decoding with Permutation Arrays,” in Proceedings of IEEE International Symposium on Information Theory, pp. 211-214, 2008.
[29] A. M. McLoughlin, “The Complexity of Computing the Covering Radius of a Code,” IEEE Transactions on Information Theory, vol. 30, pp. 800–804, 1984.
[30] C. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Co, 1995.
[31] K. W. Shum, ”Permutation Coding and MFSK Modulation for Frequency Selective Channel,” IEEE Personal, Indoor and Mobile Radio Communications, vol. 13, pp. 2063– 2066, Sept. 2002.
[32] M. Schwartz, “Efficiently Computing the Permanent and Hafnian of some Banded Toeplitz Matrices,” Linear Algebra and its Applications, vol. 430, pp. 1364–1374, 2009
[33] C. Sims, “Computational Methods in the Study of Permutation Groups”, Computational Problems in Abstract Algebra, pp. 169–183, 1970.
[34] D. E. Stevenson, “PNG Palette Permuter,” in Proceedings of the 11th annual SIGCSE, Conference on Innovation and Technology in Computer Science Education, pp. 143–147, 2006.
[35] T. G. Swart, H. C. Ferreira, “Decoding Distance-Preserving Permutation Codes for Power-Line Communications,” in Proceedings of IEEE AFRICON, pp. 1–7, 2007.
[36] D. Slepian, “Permutation Modulation,” Proceedings of the IEEE, vol. 53, pp. 228–236, Mar. 1965.
[37] I. Tamo, M. Schwartz, “Correcting Limited-Magnitude Errors in the Rank-Modulation
Scheme,” IEEE Transactions on Information Theory, vol. 56, pp. 2551–2560, Jun. 2010.
[38] L. Trevisan, “Some Applications of Coding Theory in Computational Complexity,” Quaderni di Matematica, vol. 13, pp. 347–424, 2004.
[39] J. H. van Lint, R. M. Wilson, A Course in Combinatiorics 2nd ed., Cambridge University Press, 2001.
[40] A. Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Transactions on Information Theory, vol. 43, pp. 1757–1766, 1997.
[41] A. J. H. Vinck, J. Häring, “Coding and Modulation for Power-Line Communications,” in Proceedings of International Symposium on Power Line Communications, pp. 265-272, Apr. 2000.
[42] A. J. H. Vinck, J. Häring, T. Wadayama, “Coded M-FSK for Power Line Communications,” in Proceedings of IEEE International Symposium on Information Theory, p. 137, 2000.
[43] A. J. H. Vinck, “Coded Modulation for Powerline Communications,” AEU International Journal of Electronics and Communications, vol. 54, pp. 45–49, 2000.
[44] Z. Wang, A. A. Jiang, J. Bruck, “On the Capacity of Bounded Rank Modulation for Flash Memories,” in Proceedings of IEEE International Symposium on Information Theory, pp. 1234–1238, 2009.
[45] S. Yekhanin, “Towards 3-query Locally Decodable Codes of Subexponential Length,” Journal of the ACM, vol. 55, pp. 1–16, 2008.