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
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.
被引用:0
點閱:317
評分:
下載:17
書目收藏:0
