The Hong Kong University of Science and Technology
Department of Computer Science


PhD Thesis Defence


"The Channel Capacity of One and Two-dimensional Constrained Codes"

By

Mr. Xuerong Yong


Abstract

This topic belongs to the area of Information Theory. The work is on
channel capacities of the Codes for Mass Data Storage/Transmission Systems
and involves Combinatorics, Matrix Theory, Graph Spectra, Probability, and
Numerical Analysis.

Constrained codes are sets of sequences in which certain patterns are
forbidden or, alternatively, required, to occur. A two dimensional
constrained code is a set of arrays with this property.  Such codes, at
least in the one-dimensional case, are widely used in digital and optical
data recordings. Due to this applicability, these codes and their channel
capacities, which intuitively can be interpreted as the maximum amount of
information that can be stored or transmitted per bit in communications,
have been extensively studied.

Recently, much interest has started focusing on two-dimensional run-length
limited codes; these are two-dimensional constrained (0,1)-arrays that
satisfy specific one-dimensional run-length limited constraints both
horizontally and vertically. Research into these types of codes is
currently in its infancy but very active. There is much concerning then
that is still not well-understood.

In this thesis, we first describe the framework of the topic and then
summarize and comment the recent representative work. We then come to our
work: (1) establish theoretical results about the channel capacity of 2-D
constrained codes; (2) develop new techniques for analyzing and computing
the capacity. The techniques and idea can be used to consider various
other codes.


Date:				Monday, 29 July 2002

Time:				2:00p.m.-4:00p.m.

Venue:				Room 1505
				Lifts 25-26

Chairman:			Dr. Jeffrey Chasnov (MATH)

Committee Members:		Dr. Mordecai Golin (Supervisor)
				Dr. Cunsheng Ding
				Prof. William Steiger
				Prof. Shiu-Yuen Cheng (MATH)
				Prof. Raymond Wai-Ho Yeung (Inf. Engg., CUHK)


**** ALL are Welcome ****