LOZENGE TILING CONSTRAINED CODES
Abstract
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:
PDFReferences
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:
math/9801059
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:
//www.citebase.org/abstract?id=oai:arXiv.org:cs/0601069
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.
Refbacks
- There are currently no refbacks.
ISSN: 0353-3670 (Print)
ISSN: 2217-5997 (Online)
COBISS.SR-ID 12826626