New Bounds and Constructions for Granular Media Coding

作者：Sharov Artyom; Roth Ron M

来源：IEEE Transactions on Information Theory, 2015, 61(8): 4227-4238.

DOI：10.1109/TIT.2015.2445758

• Asymmetric error-correcting codes
• convex optimization
• Gilbert-Varshamov bound
• grain-correcting codes
• grain-detecting codes
• granular media
• linear programming
• lower bounds
• magnetic recording
• Markov chain
• upper bounds

Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert-Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the asymptotic rate of [tau n]-grain-correcting codes of length n on the interval [0, 0.0668]. One of the two newly presented upper bounds improves on the best known upper bounds on the asymptotic rate of [tau n]-grain-correcting codes of length n on the interval tau is an element of (0, 1/8] and meets the lower bound of 1/2 for tau >= 1/8. Moreover, in a nonasymptotic regime, both upper bounds improve on the previously best known results on the largest size of t-grain-correcting codes of length n, for certain values of n and t. Constructions of 1-grain-correcting codes based on a partitioning technique are presented for lengths up to 18. Finally, a lower bound of 1/2 log(2) n on the minimum redundancy of infinity-grain-detecting codes of length n is presented.

• 出版日期2015-8