2-Correcting Lee Codes: (Quasi)-Perfect Spectral Conditions and Some Constructions
Sihem Mesnager, Chunming Tang, Yanfeng Qi · IEEE Transactions on Information Theory · 2018
Let p be an odd prime. Recently, Camarero and Martínez (in “Quasi-perfect Lee codes of radius 2 and arbitrarily large dimension”, IEEE Trans. Inform. Theory, vol. 62, no. 3, 2016) constructed some p-ary 2-quasi-perfect Lee codes for p ≡ ±5 (mod 12). In this paper, some infinite classes of p-ary 2-quasi-perfect Lee codes for any odd prime p with flexible length and dimension are presented. More specifically, we provide a new method for constructing quasi-perfect Lee codes. Our approach uses subsets derived from some quadratic curves over finite fields (in odd characteristic) to obtain two classes of 2-quasi-perfect Lee codes defined in the space Zpnfor n = pk+1/2 (with p ≡ 1, -5 (mod 12) and k is any integer, or p ≡ -1, 5 (mod 12) and k is an even integer) and n = pk-1/2 (with p ≡ -1, 5 (mod 12), k is an odd integer and pk> 12). Our codes encompass the p-ary (p ≡ ±5 (mod 12)) 2-quasiperfect Lee codes constructed by Camarero and Martínez. Furthermore, we prove that the related Cayley graphs are Ramanujan or almost Ramanujan using Kloosterman sums. This generalizes the work of Bibak, Kapron, and Srinivasan (in “The Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs”, IEEE Trans. Inform. Theory, vol. 62, no. 11, 2016) from the case p ≡ 3 (mod 4) and k = 1 to the case of any odd prime p and positive integer k. Finally, we derive some necessary conditions with the exponential sums of all 2-perfect codes and 2-quasi-perfect codes, and present a heuristic algorithm for constructing 2-perfect codes and 2-quasi-perfect codes. Our results show that, in general, the Cayley graphs associated with 2-perfect codes are Ramanujan. From the algorithm, some new 2-quasi-perfect Lee codes different from those constructed from quadratic curves are given. The Lee codes presented in this paper have applications in constrained and partial-response channels, flash memories, and decision diagrams.