ISBN: 1-933019-02-6 128pp April 2005
Abstract
Revolutionary developments which took place in the 1980's have
transformed cryptography from a semi-scientific discipline to a
respectable field in theoretical Computer Science. In particular,
concepts such as computational indistinguishability,
pseudorandomness and zero-knowledge interactive proofs were
introduced and classical notions as secure encryption and
unforgeable signatures were placed on sound grounds. The
resulting field of cryptography, reviewed in this survey, is
strongly linked to complexity theory (in contrast to “classical”
cryptography which is strongly related to information theory).
Contents
1 Introduction and Preliminaries Part I Basic Tools
2 Computational difficulty and One-way Functions
3 Pseudorandomness
4 Zero-knowledge Part II Basic Applications
5 Encryption Schemes
6 Signature and Message Authentication Schemes
7 General Cryptographic Protocols
Acknowledgements
References
ISBN: 1-933019-00-X 192pp June 2004
Abstract
Random matrix theory has found many applications in physics,
statistics and engineering since its inception. Although early
developments were motivated by practical experimental problems,
random matrices are now used in fields as diverse as Riemann
hypothesis, stochastic differential equations, condensed matter
physics, statistical physics, chaotic systems, numerical linear
algebra, neural networks, multivariate statistics, information
theory, signal processing and small-world networks. This article
provides a tutorial on random matrices which provides an overview
of the theory and brings together in one source the most
significant results recently obtained. Furthermore, the
application of random matrix theory to the fundamental limits of
wireless communication channels is described in depth.
Contents
1 Introduction
2 Random Matrix Theory
3 Applications to Wireless Communications
4 Appendices
Acknowledgements
References
ISBN: 1-933019-01-8 158pp October 2004
Abstract
Wireless communication system design was until recently thought
to have been limited in practice by time and bandwidth. The
discovery that space, obtained by increasing the number of
transmit and receive antennas, can also effectively generate
degrees of freedom, and hence expand the range of choices made
available to the design offers system designers important new
opportunities. This paper focuses on the main aspects of single-user
multiple-antenna theory, with the goal of presenting a
comprehensive, yet compact, survey, emphasizing its mathematical
aspects. After describing channel models, we compute the
capacities they achieve, we briefly overview “space-time”
codes, and we describe how suboptimum architectures can be
employed to simplify the receiver.
Contents
1 Introduction
2 Preliminaries
3 Channel models
4 Channel capacity
5 Influence of channel-state information
6 Coding for multiple-antenna systems
7 Some practical coding schemes
8 Suboptimum receiver interfaces
9 The fundamental tradeoffAppendix
A Complex random variables and vectors
B Results from information theory
C Random matrices
D Numerical calculation of error probabilities
E Two proofs
Acknowledgments
References
Notations and Acronyms
ISBN: 1-933019-32-8 248pp July 2006
Abstract
This article is focused on the performance evaluation of linear
codes under optimal maximum-likelihood (ML) decoding. Though the
ML decoding algorithm is prohibitively complex for most practical
codes, their performance analysis under ML decoding allows to
predict their performance without resorting to computer
simulations. It also provides a benchmark for testing the sub-optimality
of iterative (or other practical) decoding algorithms. This
analysis also establishes the goodness of linear codes (or
ensembles), determined by the gap between their achievable rates
under optimal ML decoding and information theoretical limits. In
this article, upper and lower bounds on the error probability of
linear codes under ML decoding are surveyed and applied to codes
and ensembles of codes on graphs. For upper bounds, we discuss
various bounds where focus is put on Gallager bounding techniques
and their relation to a variety of other reported bounds. Within
the class of lower bounds, we address de Caen’s based bounds
and their improvements, and also consider sphere-packing bounds
with their recent improvements targeting codes of moderate block
lengths.
Contents
1 A Short Overview
1.1 Introduction
1.2 General approach for the derivation of improved upper bounds
1.3 On Gallager bounds: Variations and applications
1.4 Lower bounds on the decoding error probability
2 Union Bounds: How Tight Can They Be?
3 Improved Upper Bounds for Gaussian and Fading Channels
4 Gallager-Type Upper Bounds: Variations, Connections and
Applications
5 Sphere-Packing Bounds on the Decoding Error Probability:
Classical and Recent Results
6 Lower Bounds Based on de Caen’s Inequality and Recent
Improvements
7 Concluding Remarks
Acknowledgements
References
Updates
ISBN: 1-933019-23-9 84pp December 2005
Abstract
The fundamental theorems on the asymptotic behavior of
eigenvalues, inverses, and products of banded Toeplitz matrices
and Toeplitz matrices with absolutely summable elements are
derived in a tutorial manner. Mathematical elegance and
generality are sacrificed for conceptual simplicity and insight
in the hope of making these results available to engineers
lacking either the background or endurance to attack the
mathematical literature on the subject. By limiting the
generality of the matrices considered, the essential ideas and
results can be conveyed in a more intuitive manner without the
mathematical machinery required for the most general cases. As an
application the results are applied to the study of the
covariance matrices and their factors of linear models of
discrete time random processes.
Contents
1 Introduction
2 The Asymptotic Behavior of Matrices
3 Circulant Matrices
4 Toeplitz Matrices
5 Matrix Operations on Toeplitz Matrices
6 Applications to Stochastic Time Series
Acknowledgements
References
Updates
ISBN: 1-933019-07-7 88pp December 2004
Abstract
Algebraic number theory is having an increasing impact in code
design for many different coding applications, such as single
antenna fading channels and more recently, MIMO systems.
Extended work has been done on single antenna fading channels,
and algebraic lattice codes have been proven to be an effective
tool. The general framework has been settled in the last ten
years and many explicit code constructions based on algebraic
number theory are now available.
The aim of this work is to provide both an overview on algebraic
lattice code designs for Rayleigh fading channels, as well as a
tutorial introduction to algebraic number theory. The basic facts
of this mathematical field will be illustrated by many examples
and by the use of a computer algebra freeware in order to make it
more accessible to a large audience.
Contents
1 Introduction
2 The Communication Problem
3 Some Lattice Theory
4 The Sphere Decoder
5 First Concepts in Algebraic Number Theory
6 Ideal Lattices
7 Rotated -lattices Codes
8 Other Applications and Conclusions
References