 |
TITLE: On Expanded Cyclic and Reed-Solomon Codes
SPEAKER: Yingquan Wu (Link_A_Media)
DATE: 2:00 - 3:00 PM, Monday, April 19, 2010
LOCATION: Tahoe, 3U
ABSTRACT:
This talk has a threefold purpose. The first is to present a new
description of expanded cyclic codes defined in $\GF(q^m)$. The
proposed explicit description of the expanded generator matrix and the
expanded parity check matrix maintains the symbol-wise algebraic
structure and thus retains many important original characteristics.
The second purpose is to characterize expanded cyclic codes utilizing
the proposed expanded generator matrix (a similar analysis may be
carried out on the proposed expanded parity check matrix). We focus on
exploring the properties of component words of a codeword as well as
their reciprocal relations. We reveal that the existence of a zero
component word is dictated by conjugate roots of the parity check
polynomial, but not to its non-conjugate roots. We show that each
generator (parity check) matrix can be divided into block-bidiagonal
submatrixes associated with conjugate roots of the parity check
(generator) polynomial.
Finally we shed light on new insights of binary expanded Reed-Solomon
codes, which are of particular mathematical and practical interest. We
first show an explicit way of constructing superior subspace subcodes
utilizing the composite basis which exhibit a higher dimension than
the counterpart subfield subcodes. We next demonstrate that the
effective dimension of expanded parity check (generator) matrix, which
dictates the complexity of maximum-likelihood soft-decision decoding,
can be noticeably reduced by employing block-bidiagonal structures of
submatrixes associated with conjugate roots of the generator (parity
check) polynomial. We finally conclude that the fixed-rate binary
expanded Reed-Solomon codes are asymptotically "bad", regardless of
basis realization, in the sense that the ratio of minimum distance
over code length diminishes with code length going to infinity. We
assert "badness" for three scenarios, namely, $(i)$ (conventional)
fixed starting spectral null for all rates; $(ii)$ centered spectral
null for rates above $\frac{1}{3}$; and $(iii)$ dynamic spectral null
for rates above $\frac{11}{21}$. Our conclusion overturns the
prevailing conjecture that binary expanded Reed-Solomon codes,
particularly high-rate ones, are asymptotically "good" codes, while
deviating from the ensemble of generalized Reed-Solomon codes which
asymptotically achieve the Gilbert-Varshamov bound.
BIOGRAPHY:
Dr. Yingquan Wu was born in the People's Republic of China. He
received both the B.S. and M.S. degrees in mathematics from Harbin
Institute of Technology, P.R. China in July 1996 and July 1997,
respectively. In August 2000, he received the M.S. degree in
electrical engineering at the State University of New York at
Buffalo. In October 2004, he received the Ph.D. degree in electrical
and computer engineering at the University of Illinois at
Urbana-Champaign.
Dr. Wu at present works at Link_A_Media Devices Corp., Santa Clara,
CA, where he has been developing algorithms and architectures for
error control coding and digital signal processing. Dr. Wu's research
interests lie in the areas of algebraic coding theory, soft-decision
decoding techniques, and the efficient VLSI design of general
communication algorithms.
|
|
|
printable version
