Kenneth Zeger - US grants

Vector Quantization (VQ) is a source coding technique that is emerging as a fundamental component in many speech and video coding systems, particularly for low rate efficient transmission over limited capacity communication channels. The principal investigator is investigating and developing combined VQ and channel coding algorithms that substantially advance the current performance achievable with respect to the overall reproduction quality of the signal in a narrowband channel or packet network environment. In many applications limited bandwidth constraints make impractical the use of traditional channel coding techniques. The algorithms being studied will combine basic VQ compression techniques for voice and video applications with new channel coding schemes that use little or no redundancy information. The project will examine in depth and develop new source/channel techniques for VQ, exploiting combined quantization and modulation, packet error recovery, index permutations, and selective bit protection. In addition, a theoretical analysis of the performance of VQ in the presence of channel noise for asymptotically high resolution quantizers is being studied, which can lead to better understanding for quantizer design procedures.

WPC< 2 B J Z Courier #| x @W x 6 X @ `7 X @ HP LaserJet 4 (935-Mail) INTHP4-1.PRS x @ \ E X @ 2 6 V > Z Courier ? x x x , @W x 6 X @ `7 X @ HP LaserJet 4 (935-Mail) INTHP4-1.PRS x @ \ E X @ 2 * F Z : #| x INT 9315271 Zeger The primary objective of this U.S. Hungary research project between Dr. Kenneth Zeger of the University of Illinois and Dr. Gabor Lugosi of the Technical University of Budapest is to examine source coding problems and classification problems where it is desirable to conduct coding and classification together, for the same source. The researchers will study neural classification and consistency issues, universal vector quantization and empirical computer design. Efforts should lead to a better understanding of empirically designed lossy source coders, universal lossy source coders and statistical pattern classification. Results are expected to yield rate of convergence information for these techniques and may be applied to areas such as computer imaging in nuclear medicine. This research in computer communications fulfills the program objectives of advancing science and engineering by enabling leading experts in the U. S. and Eastern Europe to combine complementary talents and pool research resources in areas of strong mutual interest and competence.

9415860 Zeger The goal of the project is to develop effective joint source-channel coding techniques. The main objectives are to achieve a deep theoretical understanding of combined source-channel codes and to develop practical algorithms that can effectively be used in real applications such as low-bandwidth video compression and low-delay speech coding. Very narrow bandwidth transmission channels, such as mobile cellular telephony, require efficient coding schemes to protect the transmitted source information from the corruptive effects of channel errors. Some previous work on joint source-channel coding has yielded limited success at protecting source coded information. In particular, low complexity techniques are needed for low delay real time implementations. This project will investigate channel coding techniques for source coding applications with an emphasis on image, video, and speech coding applications. A summary of the topics to be investigated is: Classes of low-complexity redundancy free codes for discrete memoryless channels; error control coding will be incorporated into the source code design and the index assignment problem will be addressed for codes with redundancy. High resolution quantizer theory will be studied for sources transmitting across noisy channels. Some preliminary results give useful formulas for randomized index assignments, but a much stronger theory is needed for optimal index assignment. Lattice codes will be studied both for quantization and channel coding. A goal will be to develop efficient encoding algorithms for lattice source codes (respectively, decoding algorithms for channel codes). Preliminary results so far have yielded very fast algorithms for the Leech lattice, as well as some of the best-known low dimensional lattices. Efficient decoding techniques will be developed for channel codes in Euclidean space using specific source coding information. In particular, trellis decoding algorithms and theory will be studied for unequal input probabilities and unequal error protection. This is currently an unsolved problem though extensions of techniques from traditional decoding algorithms have yielded some limited preliminary success. ***

The 1998 IEEE Information Theory Workshop is sponsored by the Information Theory Society of the IEEE will be held in San Diego, CA on February 8-11, 1998. The primary objective of the Workshop is to present new perspectives and results in a broad range of research areas in information and its applications. There will be six technical sessions, held serially covering the following topics: 1) Information Theory: 50 Years and Beyond, 2) Universal and Lossless Source Coding, 3) Channel Coding Applications, 4) CDMA, 5) Channel Coding Theory, and 6) Lossy Source Coding. Each session will include six invited speakers, each internationally recognized for contributions in the respective research areas. In addition, there will be a plenary lecture each morning, as well as a special evening lecture. There is also a session for contributed recent research results. The purpose of the award is to provide financial support from NSF for travel grants to U.S> scientists and engineers who could not otherwise attend the Workshop for lack of funding.

ABSTRACT NCR-9714696 Zeger, Kenneth Institution: University of California - San Diego Title: Low Complexity Joint Source and Channel Coding ________________________________________________________________ The goal of the project is to develop effective joint source-channel coding techniques. The main objectives are to achieve a deep theoretical understanding of combined source-channel codes and to develop practical algorithms that can effectively be used in real applications such as low-bandwidth image compression and low-delay speech coding. Very narrow bandwidth transmission channels, such as in mobile cellular telephony, require efficient coding schemes to protect the transmitted source information from the corruptive effects of channel errors. In particular, low complexity techniques are needed for low delay real time implementations. This project will investigate joint source-channel coding techniques with an emphasis on image, video, and speech coding applications. Both packetized and non-packetized transmission systems will be studied. A summary of the topics to be investigated is given below: -- Variable Rate Source Coding for Noisy Channels. -- Optimal Tradeoff Between Source Coding and Channel Coding. -- Feedback Control for Progressive and Region Selective Image Transmission for Wireless Communication Channels. -- Structured Index Assignment, Vector Quantization, and Channel Coding

This workshop is intended to bring together a group of researchers to discuss and recommend future directions in the field of source-channel coding.
Specifically, the goals of the workshop are:
Provide a contextual basis for understanding the array of applications in which source-channel coding can play a central role;
Assess the potential impact of source-channel coding technology in those applications;
Identify and characterize the major research issues associated with the design, development, and deployment of source-channel coding technology;
Develop a conceptual framework for future crosscutting research activities in this inherently interdisciplinary area.

TITLE: Image Coding with Constraints

ABSTRACT

This project studies image and video coding schemes for emerging and future
networks. The study concentrates on certain specific types of image coding
including facsimile, still imagery, and video. Networks of the future will
consist of hybrid combinations of wired and wireless components. Commercial
products such as digital cameras, cell phones, and PDAs will send and/or
receive images of various types over a wide range of network channel
conditions. The networks impose constraints such as: low data rate and
high/unpredictable packet losses. The devices impose constraints including
small batteries, small displays, low delay, limited memory, and limited
processing power. Together, these constraints make the design of inexpensive
and efficient image transmission devices of the future a very challenging task.
In addition to designing such systems, a solid theoretical understanding of the
achievable qualities and limitations is important to know.

The main objectives of this research are to achieve deep theoretical
understanding of source and channel coding for images transmitted on lossy
networks and to develop practical algorithms that can be effectively used in
real applications. The work exploits the diverse backgrounds of the PIs in
image and video coding and combined source/channel coding. The investigation
involves code design, theoretical analysis, and computer simulation.
The main topics investigated for constrained image coding include:

(1) Robust facsimile transmission,
(2) Robust low rate video source coding,
(3) Error correction, resilience, and concealment.

This project studies the theory of multidimensional channels and investigates effective coding techniques for such channels. The coding techniques are of three types: error-correction channel coding, constrained coding, and joint source-channel coding. Emphasis is placed on applications to two-dimensional magnetic and optical recording as well as three-dimensional holographic storage. These are the storage devices of the future. An important application of this research within the next few years is the storage of massive amounts of
still imagery and video on two-dimensional media. This will likely extend to three-dimensional and four-dimensional (the fourth dimension is wavelength) devices over the next 5 to 10 years. Such multidimensional devices will require a shift in paradigm, since most of the existing theory for
error-correcting codes, constrained codes, and source-channel codes was developed in the context of one-dimensional applications. There is much to be gained by coding for multidimensional channels, but the problems associated with such channels are considerably more challenging than their one-dimensional
counterparts.

Interesting technical problems arise due to the spatially dependent nature of errors in multidimensional storage media. New error-correcting codes and interleaving techniques are needed to effectively protect data stored on such media. The physical properties of optical and holographic recording channels call for a new theory of constrained coding in multiple dimensions. New joint source-channel coding techniques and theory are needed to maximize the recovered source fidelity for images and video stored on multidimensional
devices while keeping the storage density as high as possible. Inparticular, the storage capacity of multidimensional devices can be greatly increased at the expense of a less reliable recovery of the stored imagery/video than is current practice for the storage of data. This project studies the tradeoff
between increased storage capacity and quantitative loss in fidelity of the reproduced source signal. The main topics being investigated for multidimensional channels are: (1) Error-correcting codes, (2)
Interleaving techniques, (3) Soft-decision decoding, (4) Capacity computation for constrained channels, (5)~Encoders and decoders for specific constraints, (6) Joint source-channel coder design.

This project studies the theory of multidimensional
channels and develop effective coding techniques for such
channels. The coding techniques investigated are of three
types: error-correction channel coding, constrained coding,
and joint source-channel coding. Emphasis is placed on
applications to two-dimensional magnetic and optical
recording as well as three-dimensional holographic
recording. These are the storage devices of the future.

The investigation involves code design, theoretical analysis,
and computer simulation.

The main topic areas investigated for multidimensional
channels are:

Interleaving techniques in two and three dimensions
Multidimensional codes correcting cluster errors
Constrained coding and defect avoidance for
multidimensional media - Progressive source coding for
multidimensional channels - Index assignment for
multidimensional channels

Multidimensional storage devices require a completely new
theory and new technical breakthroughs, since most of the
existing theory for error-correcting codes, constrained
codes, and source-channel codes was developed in the context
of one-dimensional applications. The problems associated
with multidimensional channels are usually much more
challenging than their one-dimensional counterparts.

In particular, interesting technical problems arise due to
the spatially dependent nature of errors and constraints in
multidimensional recording media. New error-correcting codes
and interleaving techniques are needed to effectively
protect data stored on such media. The study of constrained
coding for multidimensional channels is still in its infancy
, and needs substantial further research to blossom into a
theory. Joint source-channel coding techniques are needed
to maximize the recovered source fidelity for images and
video stored on multidimensional devices.

This project studies the mathematical and algorithmic theory of the newly emerging field of network coding. Network coding offers the promise of improved performance over traditional network routing techniques.
Emphasis is placed on the fundamental theory of communication in networks that allow coding in addition to routing. Applications include improved throughput in packet networks and power savings in wireless ad hoc
networks. Specific subtopics studied include network solvability, linear coding, non-linear coding, the algebraic structure of symbol alphabets, multicast communications, point-to-point communications, and
bi-directional coding and routing. The theory of network coding is still in its infancy and little is known about practical algorithms for exploiting coding in real networks, such as the Internet.

The objectives are to achieve a deep mathematical understanding of network coding and to develop practical algorithms that can be effectively used in real applications. The work exploits the diverse mathematical and
computer science backgrounds of the PIs. The investigation involves mathematical analysis, algorithm design, and computer simulation. The main topic areas investigated are: (i) Applications of matroid theory to
network coding; (ii) Algorithms for network solvability, capacity computation, and code design; (iii) Theory and algorithms for bi-directional networks; (iv) Theory and design of robust networks.

This project studies the emerging field of network coding in several new directions. Network coding offers the promise of improved performance over conventional network routing techniques, by allowing network nodes to mathematically combine information prior to retransmission. Over the next decade, it has the potential to become a pervasive technology that could radically change the way information is communicated. In particular, network coding principles can significantly impact the next-generation wireless, ad hoc, and sensor networks, in terms of both energy efficiency and throughput.

While most of the existing network coding theory assumes error-free links, in practice these links are usually noisy. In fact, error-correction coding for such noisy links is sub-optimal when it is separated from network coding --- to maximize the throughput of a network, channel and network coding must be
combined. Thus, one of the main research topics studied in this project is joint network and channel coding. The project focuses on the following subtopics: (i) Reverse concatenation of network and channel coders (ii) Joint network/channel coding at the node level (ii) Global network/channel coding at the network level The second main research topic is broadcast-mode network coding. This concerns applications in ad hoc wireless networks. Subtopics include: (i) Linear network coding (ii) Network capacity (iii) Iterative design
of broadcast-mode network codes.

The project develops a mathematical and algorithmic foundation for the field of network computing. The project ties together ideas from network coding with computational problems. While some special cases of network computing have been recently studied, this project carries out a unified study of the field of network computing. The project exploits the promise of improved performance using non-linear codes over traditional network routing and linear coding techniques. Emphasis is placed on computing in networks that allow coding in addition to routing. Applications of network computing include sensor networks and wireless networks. The broad fields studied are: (1) theory and algorithms, and (2) alternative network computing models.

The main objectives of the project are to achieve a deep mathematical understanding of network computing capacity and solvability and to develop practical algorithms that can be used effectively to improve performance in real applications. The investigation involves mathematical analysis, algorithm design, and computer simulation. The main topic areas investigated are: (1) Capacity computability and alphabet size, (2) Iterative design of network computing algorithms, (3) Limiting the number of network nodes that can perform coding, (4) Average computation rate in network coding, (5) Bi-directional and broadcast-mode network computing.

Zeger
DMS-1009954

The project develops foundations for the recently booming
applied mathematics field of network coding. Network coding
offers the promise of improved performance over traditional
network routing techniques used in practical engineering
applications. Emphasis is placed on the fundamental theory of
communication in networks that allow coding in addition to
routing. Applications include improved throughput in packet
networks and power savings in wireless ad hoc networks. The work
exploits the diverse mathematical, engineering, and computer
science background from the investigator's previous work and
involves mathematical analysis, algorithm design, and computer
simulation. The main topic areas investigated are: the role of
alphabet size and error correcting codes in network coding,
techniques for computing or bounding network capacities,
determining the scalar or vector solvability of networks,
theoretically achievable rates under a limitation of the number
of network nodes that can perform coding, and bi-directional
networks.

This project has applications to practical engineering
problems involving packet switched networks, such as sensor
networks, military battlefield networks, and local area networks.
The most prominent example is the Internet, which is used on a
daily basis by billions of people for sending email, downloading
images and video, transferring data, and many other applications.
This project studies the theoretical foundations of how
information can be sent across such networks using mathematical
combinations of data rather than just routing of data.
Specifically, the project studies the fundamental limits of data
transmission, the best methods to transmit such data, and
variations on the types of networks used. The project includes
graduate student participation as well as some undergraduate and
high school student contributions, with emphasis on the
interconnection between mathematics, engineering, and computer
science.

This project develops techniques for finding non-Shannon information inequalities and strives to geometrically characterize the space of vectors whose components are the entropies of subsets of jointly distributed discrete random variables. Specific sub-topics include the geometric description of inner and outer entropic region bounds, such as: the Shannon space, the Ingleton space, the common information space, the linearly representable space, and the copy region space. In addition, a unified approach to many important mathematical questions with engineering applications is studied using information theoretic inequality implications. Special cases include: random variable conditional independence implications, entropic region membership, information inequality identification, and network coding capacity bounding.

The problems in this field are of interest as fundamental theoretical questions and are also strongly motivated by communications applications in the area of network coding. Most of the study is analytic in nature, but the project also exploits computer assisted discovery and verification of new non-Shannon information inequalities for four and more random variables using techniques based upon auxiliary variables.

The discovery of new non-Shannon information inequalities provides improved bounds on the set of all entropic points. Such improved bounds lead to better bounds on the transmission capacity of networks. Calculating the capacity of a network is traditionally an extremely difficult, and usually intractible, problem. New inequalities also shed light on the basic understanding of both probability and information theory fundamentals. As information theory has proven to be an important and practical field over the last half century, a firm theoretical basis for it is necessary.

There are some broader impacts resulting from the proposed activity: The project involves active participation of graduate students, undergraduates, and also high school students, commensurate with their backgrounds and abilities. Graduate student participation provides training for careers in academia and industry. Undergraduate participation encourages research as a career and steers students towards academia and research in general.