 |
Coding Day 2009  |
| Ben-Gurion University |
Coding Day 2009
Abstracts and Bios
On the optimality of universal classifers for finite-length individual test sequences Specifications
Jacob Ziv, Technion Institute
Abstract:
An empirical informational divergence (relative entropy) between two individual sequences has been introduced in [1]. It has been demonstrated that if the two sequences are independent realizations of two finite-order, finite alphabet, stationary Markov processes, the proposed empirical divergence measure (ZMM), converges to the relative entropy almost surely. This leads to a realization of an empirical, linear complexity universal classifier which is asymptotically optimal in the sense that the probability of classification error vanishes as the length of the sequence tends to infinity. if the normalized KL-divergence between the two measures is positive [2].
It is demonstrated that for finite-length sequences that are realizations of finite-alphabet, vanishing memory processes with positive transitions, a version of the ZMM [1] is not only asymptotically optimal as the length of the sequences tends to infinity, but is also essentially optimal in the sense that the probability of classification error vanishes if the length of the sequences tends to infinity for a large sub-class of such measures if the length of the sequences is larger than some positive integer N0 . At the same time no universal classifier can yield an efficient discrimination between any two distinct processes in this class, if the length of one of the two sequences N is such that logN < logN0.
It is also demonstrated that there are some classification algorithms which are asymptotically optimal as N tends to infinity, but are not essentially optimal.
A variable-length divergence measure is defined, that tends to the KL-divergence as N tends to infinity.
A new universal classification algorithm is shown to optimal in the sense that the probability of classification error vanishes over the entire class of pairs of finite-alphabet, vanishing memory measures with positive transitions, and a positive variable-length divergence, if logN > logN0, while no efficient classification is possible by any universal classifier if logN < logN0.
Bio:
Jacob Ziv was born in Tiberias, Israel, on November 27, 1931. He re- ceived the B.Sc., Dip. Eng., and M.Sc. degrees, all in Electrical Engineering, from the Technion-Israel Institute of Technology, Haifa, Israel, in 1954, 1955 and 1957, respectively, and the Sc.D. degree from the Massachusetts Institute of Technology, Cambridge, U.S.A., in 1962.
From 1955 to 1959, he was a Senior Research Engineer at the Scientific Department, Israel Ministry of Defense, where he engaged in research and development of communication systems. From 1961 to 1962, while studying for his doctorate at M.I.T., he joined the Applied Science Division of Melpar, Inc., Watertown, MA, where he was a Senior Research Engineer doing research in communication theory. In 1962 he returned to the Scientific Department, Israel Ministry of Defense, as Head of the Communications Division and also served as an Adjunct of the Faculty of Electrical Engineering, Technion-Israel Institute of Technology. From 1968 to 1970 he was a Member of the Technical Staff of Bell Laboratories, Inc., Murray Hill, NJ. He joined the Technion full time in 1970 and since 2006 he is a Technion Distinguished professor Emeritus.
He was Dean of the Faculty of Electrical Engineering from 1974 to 1976 and Vice President for Academic Affairs from 1978 to 1982. From 1977 to 1978, 1983 to 1984, and 1991 to 1992 he was on Sabbatical leave at the Information Research Department, Bell Laboratories, Murray Hill, NJ, USA.
He was the Chairman of the Israeli Universities Planning and Grants Committee from 1985 to 1991. (The Planning and Grant Committee is the interphase between The Government of Israel and the Universities; it prepares the budget, presents it to the government and allocates it to the Universities; it is in charge of development and means and practices in the Universities.)
He is a Member of the Israel National Academy of Sciences and Humanities and has served as its President from 1996 till 2005.
His research interests include data-compression, information theory and statistical communication.
Low Density Lattice Codes: From Theory to Practice
Meir Feder, Tel-Aviv University
Abstract:
Low density lattice codes (LDLC) are recently proposed lattice codes that can be decoded by linear-time iterative decoding and approach the capacity of the additive white Gaussian noise (AWGN) channel. In LDLC a codeword x is generated directly at the n-dimensional Euclidean space as a linear transformation of a corresponding integer message vector b, i.e., x = Gb, where H=G^{-1} is restricted to be sparse. In LDLC the messages are pdf's of the component of the real codeword x. In order to make LDLC practical for application we proposed parametric representation of the pdf's, making the decoding algorithm very efficient in storage and computations. Furthermore, for practical application, the infinite lattice should be combined with a shaping algorithm, that maps information bits to lattice points and ensures that the power of the lattice codewords is properly constrained. This work also proposes several efficient and practical shaping algorithms for LDLC. One technique establishes the notion of "systematic lattice codes". As a result, LDLC are not only interesting theoretically, but can practically outperform any other proposed scheme for spectrally efficient communication.
Bio:
Professor Meir Feder received the B.Sc. and M.Sc. degrees (Summa Cum Laude) in Electrical Engineering from Tel-Aviv University, Tel-Aviv, Israel, in 1980 and 1984, respectively. He received the Sc.D. degree from the Massachusetts Institute of Technology (MIT), Cambridge, MA., USA. Since October 1989 he is with the department of Electrical Engineering - Systems, School of Electrical Engineering Tel-Aviv University, where he is now a Professor. He was a visiting Professor at MIT and in addition he had visiting positions at Bell laboratories and Scripps Institute of Oceanography. While serving in the Israeli defense Forces, Professor Feder was awarded the 1978 "creative mind" award of the chief Intelligence officer. He received the 1993 best paper award of the Information Theory Society. He was the recipient of the 1994 prize of Tel-Aviv University for excellent young scientists, the 1994 award of the Electronic Industry in Israel (awarded by the president of Israel), and the 1995 research prize in applied electronics of the Ex-Servicemen Association in London, awarded by Ben-Gurion University. In 1993-1996 he served as an Associate Editor for data compression for the IEEE Transactions on Information Theory. He is a Fellow of the IEEE for his contribution to universal data prediction and universal compression. During his academic career, Prof. Feder was closely involved in the high-tech industry with numerous companies, including working with Intel on the MMX architecture and designing efficient multimedia algorithms for it. In 1998 he co-founded Peach Networks, a provider of server-based interactive TV system via the cable network, which was acquired in 2000 by Microsoft. In 2000 he co-founded Bandwiz, a provider of massive content delivery systems for enterprise networks. He is currently the Chief Scientist of Amimon, a company he co-founded in 2004. Amimon's technology is based on a unique video modem development, and is the leading provider of ASICs for wireless high-definition A/V connectivity at the home.
Bit Interleaving Coded Modulation-Past, Present and Future
Ephraim Zehavi, Bar-Ilan University
Abstract:
Bit-Interleaved Coded Modulation (BICM) has become an area of significant research effort in the last twenty years as practical coding and modulation techniques for various communication systems, in particular for systems operating over wireless fading channel. This research has lead to the development of novel, practical, and robust transmission techniques through a number of papers on various topics and techniques related to BICM. In the talk we concentrate on addressing fundamental concepts, motivation and analytical framework arising in BICM. We then proceed to examine the adaptation BICM technique in various communication systems a long with the development turbo code and LDPC and MIMO. Finally, we summarize our conclusions and discuss some possible research directions using BICM approach.
Bio:
To be announced
Coding theory and PAPR control in OFDM
Simon Litsyn, Tel-Aviv University
Abstract:
Advantages of multi-carrier OFDM systems over single-carrier ones explain their broad acceptance for various telecommunication standards. Architecture of OFDM systems allows a relatively simple implementation. Nonetheless, still a major barrier for implementing OFDM in low-cost wireless applications is its nonconstant signal envelope making the transmission sensitive to nonlinear devices in the communication path. A reasonable measure of the quality of signals is the ratio between the peak power values to their average power (PAPR). Thus the goal of the peak-power control is to diminish the influence of transmit signals with high PAPR on the performance of the transmission system. We will discuss relations between methods of analysis and design of signals with low PAPR and problems from coding theory.
Bio:
Simon Litsyn was born in Khar'kov, U.S.S.R., in 1957. He received the M.Sc. degree from Perm Polytechnical Institute, Perm, U.S.S.R., in 1979, and the Ph.D. degree from Leningrad Electrotechnical Institute, Leningrad, U.S.S.R., in 1982, both in electrical engineering. Since 1991, he has been with the Department of Electrical Engineering - Systems, Tel Aviv University, Tel Aviv, where he is a Professor. His research interests include coding and information theory, communications, and applications of discrete mathematics. He authored "Covering Codes" (Elsevier, 1997) and "Peak Power Control in Multicarrier Communications" (Cambridge University Press, 2007).
Dr. Litsyn received the Guastallo Fellowship in 1992. In 2000-2003, he served as an Associate Editor for Coding Theory for the "IEEE Transactions on Information Theory". Since 2006 he is an Associate Editor of "Advances of Mathematics in Communications", and since 2009 is an Associate Editor of AAECC: "Applicable Algebra in Engineering, Communications and Computing".
Multiplication Free Holographic Coding
Shlomi Dolev, Ben-Gurion University
Abstract:
Holographic coding has the very appealing property of allowing the gain of partial information on the data, from any part of the coded information. We present holographic coding schemes based on the Walsh orthogonal codes. The schemes only use additions for coding and decoding. We propose randomizing the data so that the coefficient of the Walsh code will be approximately uniform in order to ensure, with high probability, a monotonic gain of information. The data is xored with randomly chosen data from random data that has been stored during a preprocessing stage. We suggest schemes to cope with erasures in the scope of Walsh codes. We suggest parity based schemes to support the erasure correcting of the Walsh coefficient which can tolerate a bounded number of erasures using no multiplications. We then suggest a scheme based on Preparata use of discrete Fourier coefficients extending the data with zeros. Lastly, we present schemes that can withstand almost any number of erasures.
Joint work with Sergey Frenkel
Bio:
Shlomi Dolev received his B.Sc. in Engineering and B.A. in Computer Science in 1984 and 1985, and his M.Sc. and D.Sc. in computer Science in 1990 and 1992 from the Technion Israel Institute of Technology. From 1992 to 1995 he was at Texas A&M University as a visiting research specialist. In 1995 he joined the Department of Mathematics and Computer Science at Ben-Gurion University where he is now a full professor. He was a visiting researcher/professor at MIT, DIMACS, and LRI, for several periods during summers. Shlomi is the author of the book ``self-stabilization'' published by the MIT Press. He published more than one hundred and fifty journal and conference scientific articles, and served in the program committee of more than fifty conferences including: the ACM Symposium on Principles of Distributed Computing, and the International Symposium on DIStributed Computing. He is an associate editor of the IEEE Transactions on Computers, the AIAA Journal of Aerospace Computing, Information and Communication and a guest editor of the Distributed Computing Journal and Theoretical Computer Science. His research grants include IBM faculty awards, Intel academic grants, and the NSF. Shlomi established the computer science department at Ben-Gurion University, and served as the first chair of the department, where he now holds the Rita Altura trust chair in computer science. His current research interests include distributed computing, distributed systems, security and cryptography and communication networks; in particular the self-stabilization property of such systems. Recently, he is also involved in optical computing research.