Bane Vasić, Anantha R. Krishnan

DOI Number
First page
Last page


While the field of one-dimensional constrained codes
is mature, with theoretical as well as practical aspects of codeand
decoder-design being well-established, such a theoretical
treatment of its two-dimensional (2D) counterpart is still unavailable.
Research has been conducted on a few exemplar
2D constraints, e.g., the hard triangle model, run-length limited
constraints on the square lattice, and 2D checkerboard
constraints. Excluding these results, 2D constrained systems
remain largely uncharacterized mathematically, with only loose
bounds of capacities present. In this paper we present a lozenge
constraint on a regular triangular lattice and derive Shannon
noiseless capacity bounds. To estimate capacity of lozenge tiling
we make use of the bijection between the counting of lozenge
tiling and the counting of boxed plane partitions.

Full Text:



B. H. Marcus, P. H. Siegel, and J. K. Wolf, “Finite-state modulation

codes for data storage,” IEEE Journal of Selected Areas in Communication,

vol. 10, no. 1, pp. 5–37, 1992.

J. J. Ashley and B. H. Marcus, “Two-dimensional low-pass filtering

codes,” IEEE Transactions on Communications, vol. 46, pp. 724–727,

Jun 1998.

Z. Nagy and K. Zeger, “Capacity bounds for the hard-triangle model,”

Proceedings of International Symposium on Information Theory 2004,

p. 162, 2004.

I. Demirkan and J. K. Wolf, “Block codes for the hard-square model,”

IEEE transactions on Information Theory, vol. 51, no. 8, p. 2836, Aug

A. Kato and K. Zeger, “Partial characterization of the positive capacity

region of the two-dimensional asymmetric run length constrained channels,”

IEEE Transactions on Information Theory, vol. 46, no. 7, p. 2666,

Nov 2000.

——, “On the capacity of two-dimensional run-length constrained

channels,” IEEE Transactions on Information Theory, vol. 45, no. 5,

p. 1527, July 1999.

Z. Nagy and K. Zeger, “Bit-stuffing algorithms and analysis for runlength

constrained channels in two and three dimensions,” IEEE Transactions

on Information Theory, vol. 50, no. 12, p. 3146, Dec. 2004.

P. Siegel and J. Wolf, “Bit-stuffing bounds on the capacity of 2-

dimensional constrained arrays,” in International Symposium on Information

Theory, August 16 - August 21 1998, p. 323.

Z. Nagy and K. Zeger, “Asymptotic capacity of two-dimensional channels

with checkerboard constraints,” IEEE Transactions on Information

Theory, vol. 49, no. 9, p. 2115, 2003.

T. Etzion and K. G. Paterson, “Zero/positive capacities of twodimensional

runlength constrained arrays,” in In Proc. 2001 IEEE Intl.

Symp. on Inform. Theory, 2004, p. 269.

S. Khatami and B. Vasic, “Generalized belief propagation detector for

TDMR microcell model,” IEEE Transactions on Magnetics, vol. 45,

no. 10, p. submitted, October 2012.

A. Krishnan, R. Radhakrishnan, B. Vasic, A. Kavcic, W. Ryan, and F. Erden,

“2-d magnetic recording: Read channel modeling and detection,”

IEEE Trans. on Magn., vol. 45, no. 10, pp. 3830 –3836, Oct. 2009.

L. Pan, W. E. Ryan, R. Wood, and B. Vasic, “Coding and detection for

rectangular-grain TDMR models,” IEEE Trans. Magn., vol. 47, no. 6,

pp. 1705–1711, Jun. 2011.

R. J. Baxter, “Hard hexagons: exact solution,” Journal of Physics A:

Mathematical and General, vol. 13, no. 3, p. L61, 1980. [Online].

Available: http://stacks.iop.org/0305-4470/13/i=3/a=007

A. Krishnan, R. Radhakrishnan, and B. Vasi´c, “Read channel modeling

for detection in two-dimensional magnetic recording systems,” IEEE

Transactions on Magnetics, vol. 45, no. 10, pp. 3679–3682, October

P. A. MacMahon, Combinatory Analysis (Volume II), reprint. New

York: Chelsea Publishing Company, 1990.

H. Cohn, M. Larsen, and J. Propp, “The shape of a typical boxed plane

partition,” New York Journal of Mathematics, vol. 4, p. 137, 1998.

[Online]. Available: http://www.citebase.org/abstract?id=oai:arXiv.org:


G. David and C. Tomei, “The problem of calissons,” American Mathematics

Monthly, vol. 96, no. 5, pp. 429–431, 1989.

P. W. Kasteleyn, “The statistics of dimers on a lattice: The number of

dimer arrangements on a quadratic lattice,” Physica, vol. 12, pp. 1209–

, 1961.

S. Desreux and E. Remila, “An optimal algorithm to generate tilings,”

Journal of Discrete Algorithms, vol. 4, no. 1, pp. 168 – 180, 2006.

M. Luby, D. Randall, and A. Sinclair, “Markov chain algorithms

for planar lattice structures (extended abstract),” IEEE Symposium

on Foundations of Computer Science, pp. 150–159, 1995. [Online].

Available: citeseer.ist.psu.edu/luby95markov.html

D. L. Kreher and D. R. Stinson, Combinatorial Algorithms: Generation,

Enumeration and Search. CRC Press, 1999, pp. 97–101.

B. Ryabko, “Fast enumeration of combinatorial objects,” Math.

and Applications, vol. 10, p. n2, 1998. [Online]. Available: http:


T. M. Cover, “Enumerative source coding,” IEEE transactions on

Information Theory, vol. IT-19, no. 1, p. 73, Jan 1973.

M. Khatami and B. Vasic, “Constrained coding and detection for TDMR

using generalized belief propagation,” in Proc. IEEE Int. Comm. Conf.,

Sydney, Australia, Jun. 10–14 2014.

E. W. Barnes, “The theory of the G-Function,” Quart. J. Pure Appl.

Math, vol. 31, pp. 264–314, 1900.


  • There are currently no refbacks.

ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626