Analyzing the codes that avoid specified differences by binary tree

ABSTRACT

The error probability of certain magnetic recording systems can be characterized by the difference patterns between the sequences that may be recorded. In [9] it is shown that the number of these sequences increases exponentially with their length and the capacity, the maximum growth rate of such sequences, is proven to be the logarithm of the joint spectral radius of a set of certain (0, 1) matrces. But approximating the joint spectral radius of a set of (0, 1) matrices is known to be NP-hard [11] (This is also stated in [9]).In this correspondence, we study these sequences using binary tree. Compared with the previous work, we get around the computation of the joint spectral radius. The number of sequences that avoid a certain set of difference patterns is proven to satisfy linear recurrence relations. From this we characterize the codes that have the maximum/minimum capacities. Our computation of capacities is straight-forward and therefore has less complexity than the previous ones.

REFERENCES

• 1: S. Altekar, "Detection and coding techniques for magnetic recoding channels," Ph.D. dissertation, University of California, San Diego, CA, August, 1997.
• 2: V. Blondel and J. Tsitsiklis, "Boundedness of finitely generated matrix semigroups is undecidable," Preprints, Jan. 1999.
• 3: Martin Cohn, On the channel capacity of read/write isolated memory, Discrete Applied Mathematics, v.56 n.1, p.1-8, Jan. 9, 1995 [doi>10.1016/0166-218X(93)E0131-H]
• 4: Mordecai J. Golin , Xuerong Yong , Yuanping Zhang , Li Sheng, New upper and lower bounds on the channel capacity of read/write isolated memory, Discrete Applied Mathematics, v.140 n.1-3, p.35-48, 15 May 2004 [doi>10.1016/j.dam.2003.02.001]
• 5: Kees Schouhamer-Immink, Coding Techniques for Digital Recorders, Prentice Hall Professional Technical Reference, 1991
• 6: R. Karabed, P. Siegel, and E. Soljanin, "Constrained coding for binary channel with high intersymbol interference," IEEE Trans. Information Theory, vol. 45, no. 1, pp. 1777--1997, Sept. 1999.
• 7: B. Moision, P. Siegel, and E. Soljanin, "Distance-enhancing codes for digital recoding," IEEE Trans. Magn., vol. 34, pp. 69--74, Jan. 1998.
• 8: B. Moision, P. Siegel, and E. Soljanin, "Error event charaterization and coding for the equalized Lorentizan channel," in Pro. 1998 IEEE Int. Symp. Inform. Theory, p. 77, Cambridge, Massachusetts, 1998.
• 9: B. Moision, A. Orlitsky, and P. Siegel, "On the codes that avoid specific differences," IEEE Trans. Information Theory, vol. 47, no. 1, pp. 433--442, Jan. 2001.
• 10: E. Soljanin, "Writing sequences on the plane," IEEE Trans. Information Theory, vol. 48, no. 6, pp. 1344--1354, June, 2002.
• 11: J. Tsitsiklis and V. Blondel, "The Lyapunov exponent and joint spectral radius of pairs of matrices are hard-when not imposibble-to compute and to approximate," Math. Control. Signals, Syst., vol. 10, pp. 31--40, 1997.

INDEX TERMS

Keywords:
capacity, constrained code, magnetic recording, rooted binary tree