Search

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict avoiding codes. In this paper, we prove some nonexistence results for nonsingular perfect splitter sets. We also give some necessary conditions for the existence of purely singular perfect splitter sets. Finally, we apply these results to purely singular perfect $B[-1,k](m)$ and $B[-2,k](m)$ sets for small $k$. In particular, we solve completely the problems left by Schwartz (European J. Combin., vol. 36, pp.130–142, Feb. 2014). [ABSTRACT FROM AUTHOR]

Snake-in-the-box codes under Kendall’s \tau -metric are studied in the rank modulation scheme for flash memories, where codewords are a subset of permutations in S_{n} with minimal Kendall’s \tau -distance two, and two cyclically consecutive codewords are connected via a push-to-the-top operation. Studies so far restrict the push-to-the-top operations only on odd indices, resulting in a snake consisting of permutations with the same parity, and thus, the minimal distance constraint is easily satisfied. Asymptotically optimal snake codes have been constructed this way in S2n+1 . As for S2n+2 , this framework keeps the last element fixed, and thus, a snake in S2n+2 is equivalent to a snake in S2n+1 , which is rather trivial. If one wants to do better, then it is inevitable to have some push-to-the-top operations on even indices, resulting in a combination of odd and even permutations in the snake, which increases the difficulty to guarantee the minimal Kendall’s $\tau $ -distance constraint. Thus, Horovitz and Etzion pose the open problem to prove or disprove that the size of the largest snake in ({1}/{4})|S_{2n+2}| . [ABSTRACT FROM PUBLISHER]

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude. [ABSTRACT FROM PUBLISHER]

For a Gray code in the scheme of rank modulation for flash memories, the codewords are permutations, and two consecutive codewords are obtained using a push-to-the-top operation. We consider the snake-in-the-box code under Kendall’s \tau -metric, which is a Gray code capable of detecting one Kendall’s \tau -error. We answer two open problems posed by Horovitz and Etzion. First, we prove the validity of a construction given by them, resulting in a snake of size M2n+1=({(2n+1)!}/{2})-2n+1 . Second, we come up with a different construction aiming at a larger snake of size M2n+1=({(2n+1)!}/{2})-2n+3 . The construction is applied successfully to S7 . [ABSTRACT FROM PUBLISHER]

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict-avoiding codes. The study of k -radius sequences was motivated by some problems occurring in large data transfer. It is observed that the existence of splitter sets yields k -radius sequences of short length. In this paper, we obtain several new results contributing to splitter sets and k -radius sequences. We give some new constructions of perfect splitter sets, as well as some nonexistence results on them. As a byproduct, we obtain some new results on optimal conflict-avoiding codes. Furthermore, we provide several explicit constructions of short k -radius sequences for certain values of n , by establishing the existence of k -additive sequences. In particular, we show that for any fixed k , where fk (n) denotes the shortest length of an n -ary $k$ -radius sequence. This result partially affirms a conjecture posed by Bondy, Lonc, and Rzążewski. [ABSTRACT FROM AUTHOR]

Permutation codes have been shown to be useful in power line communications, block ciphers, and multilevel flash memory models. Construction of such codes is extremely difficult. In fact, the only general lower bound known is the Gilbert–Varshamov type bound. In this paper, we establish a connection between permutation codes and independent sets in certain graphs. Using the connection, we improve the Gilbert–Varshamov bound asymptotically by a factor \log (n), when the code length n goes to infinity. [ABSTRACT FROM PUBLISHER]

Splitter sets have been widely studied due to their applications in flash memories, and their close relations with lattice tilings and conflict avoiding codes. In this paper, we give necessary and sufficient conditions for the existence of nonsingular perfect splitter sets, ${B}[-{k}_{1},{k}_{2}]({p})$ sets, where $0\le {k}_{1}\leq {k}_{2}=4$. Meanwhile, constructions of nonsingular perfect splitter sets are given. When perfect splitter sets do not exist, we present four new constructions of quasi-perfect splitter sets. Finally, we give a connection between nonsingular splitter sets and Cayley graphs, and as a byproduct, a general lower bound on the maximum size of nonsingular splitter sets is given. [ABSTRACT FROM AUTHOR]