|
INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING AND COMMUNICATIONS INDIAN INSTITUTE OF SCIENCE, BANGALORE 18-21 JULY, 2010 |
|
SPCOM 2010 |
|
Plenaray speaker Talks
Mylswamy Annadurai Title: Engineering and Science Aspects of Chandrayaan I
Syed A. Jafar Title: On Asymptotic Interference Alignment Abstract: We take an in-depth look at the asymptotic interference alignment scheme introduced by Cadambe and Jafar for the K user interference channel. The strengths and limitations of this scheme are illustrated through a variety of examples extending from wireless networks to network coding applications.
Sanjoy Mitter Title: Towards a Unified View of Inference, Communication and Control Abstract: Technological advances in the control of processes over a communication network have necessitated the development of a unified theory of communication and control. This is currently not available in full generality but steps towards this can and have been taken. In this lecture, I attempt to present, in summary form, some of these developments.
Aditya Murthy Title: CAPACITY LIMITS OF INFORMATION PROCESSING IN THE BRAIN Abstract: Although brains and computers are both considered archetypical examples of information processing systems, profound differences in performance styles exist. For example, while computers perform mathematical calculations extremely rapidly and accurately, humans are typically slow and prone to errors. Conversely, humans are extremely good at object recognition tasks such as face recognition that most advanced computers are poor at. Such differences in processing styles seem to suggest fundamental differences in the way computational operations are performed; while the architecture of computers allows information processing to be serial and centrally controlled,the brain is often thought of as implementing parallel and distributed processing. These intuitions notwithstanding, there is a body of evidence that suggests that the brain, like computers also utilizes a centralized serial architecture for information processing during some tasks. Evidence of this derives from behavioral experiments that indicate that our brains may be limited in its capacity to process large amounts of information simultaneously. In this talk I will review evidence of such serial capacity limited architecture. I will also discuss some recent experiments from our laboratory that suggest mechanisms by which the brain may implement such bottlenecks in information processing.
Invited speaker Talks
Anish Arora Title: Symmetric Dialog Codes for Confidential Communications without Shared Secrets Abstract: Cooperative jamming enables secure communication between two radios without using shared secrets.We design an efficient randomized coding scheme that uses cooperative jamming within the context of conventional modulation-demodulation schemes to achieve concurrent two-way secure communication.
Vivek.S.Borkar Title: Stochastic Approximation with `Bad' Noise Abstract: It is well known that the noise processes in the Internet and several other situations arising in communications exhibit long range dependent and heavy tailed behaviour, a fact which has also been theoretically justified through limit theorems such as that of Mikosch, Resnick, Rootzen and Stegeman. Motivated by this, we consider stability and convergence properties of stochastic approximation algorithms when the noise includes a long range dependent component (modeled by a fractional Brownian motion) and a heavy tailed component (modeled by a symmetric stable process), in addition to the usual 'martingale noise'. This is motivated by the emergent applications in communications.
Suhas Diggavi Title: On Source-Channel Separation in Networks Abstract: We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, and the channels in this network are synchronized, orthogonal and memoryless (i.e., noisy graphs). The extracted pure network source-coding problem has to incorporate user interactions and the corresponding causality constraints, which suggests a distinct research direction into interactive network source coding that has not received much attention in the literature. The separation result in this paper is a companion to results of a similar flavor established recently in [11] for the case of independent sources over communication networks with more general multiuser channels.
Christina Fragouli Title: Algebraic Techniques for Linear Deterministic Networks Abstract: We here summarize some recent advances in the study of linear deterministic networks, recently proposed as approximations for wireless channels. This work started by extending the algebraic framework developed for multicasting over graphs in [10] to include operations over matrices and to admit both graphs and linear deterministic networks as special cases. Our algorithms build on this generalized framework, and provide as special cases unicast and multicast algorithms for deterministic networks, as well as network code designs using structured matrices.
Babak Hassibi Title: Entropy Vectors and Optimal Network Codes Abstract: It is known that a large class of wired acyclic memoryless networks can be reduced to convex optimization over the entropy region [1]. However characterizing the entropy region remains an open problem for 4 or more number of random variables. Therefore in order to obtain achievable rates and the corresponding network codes analytically, the best one can do is to consider inner or outerbounds for the entropy region. We study the linear coding capacity of networks through matroidal innerbound in this regard. Since a complete analytical characterization of entropy region seems to be far from reach, the next best thing is to come up with numerical methods. We present a numerical approach through MCMC methods that enables one to find the best rates and the corresponding optimal codes.
Tor Helleseth Title: Algebraic Attacks on the More Generalized Clock-Controlled Alternating Step Generator Abstract: The More Generalized Clock-Controlled Alternating Step Generator, MGCCASG, is a clock-controlled sequence generator proposed by Kanso in 2004. This generator consists of three feedback shift registers with lengths l, m and n bits. The first register is clocked regularly and controls the clocking of the two others. At each time unit t, the two other shift registers are clocked r(t) times (or not clocked) (resp. s(t) times or not clocked) depending on the clock-control bits in the first register. The values of r(t) and s(t) are determined according to the values of WB and WC bits of the first register respectively. The special case when (r(t)= r; r> 1) and (s(t)= s; s> 1) is the Alternating Step(r, s) Generator proposed by Kanso, and the special case when r(t)= s(t)=1 is the original and well known Alternating Step Generator. Kanso claims there is no efficient attack against the MGCCASG since the positions and the values of the WB and WC bits are kept secret and therefore, r(t) and s(t) are unknown. In this paper, we present an algebraic attack on this structure using 4M bits of the output sequence to find the secret key with a computational complexity 2M+l+6 of O(lM2(WB + WC )) and where M = max(m, n). In the case when m=n=l=64 and WB = WC=8, our attack can find the secret key using 256 output bits and a complexity of O(2156)steps, while the author claims that the best attack needs O(2665:8)steps and the exhaustive search needs O(2774:8) steps.
Navin Kashyap Title: Codes for Storage of Data on a 1-d Granular Magnetic Medium Abstract: Conventional magnetic recording media are composed of tiny fundamental magnetizable units, called "grains",that are random in size and shape. Data are stored on a medium in the form of bits written into evenly spaced bit cells. Writing involves uniformly polarizing all the grains within a bit cell. In the push towards terabit-density magnetic recording, bit cells get smaller and smaller, their size eventually becoming commensurate with the size of an individual grain. At this stage, lack of precise knowledge of grain boundaries becomes a bottleneck. This lack of knowledge manifests itself in the form of an error mechanism in which bits of data get overwritten by their neighbours on the medium. We consider a one-dimensional version of this error model, and derive several properties of codes that correct this type of error.
P.R. Kumar Title: Secure topology discovery through network-wide clock synchronization Abstract: Clock synchronization is a fundamental service for many applications in wireless sensor networks. Because of its critical importance, several protocols have been proposed to achieve clock synchronization. However, most of them are not designed to work in adversarial environments, where security attacks occur. In particular, a man-in-the-middle attack, where the attacker tampers with the properties of a link, could prevent the proper operation of the clock synchronization protocol, therefore affecting every application that relies on the clock synchronization service. We present a secure network-wide clock synchronization protocol which also allows the nodes to securely discover the network topology by detecting and isolating links that behave inconsistently. This protocol is based on detecting attacks using timing information alone under certain conditions. We have developed an implementation of this protocol where we have shown that any inconsistent link found in the network is effectively eliminated
Ravi Kannan Title: Probability Inequalities and concentration results Abstract: Take n i.i.d. points from the unit square in the plane. The minimum length of a tour visiting each point precisely once is highly concentrated around its mean. The study of how optimal solutions to combinatorial problems on i.i.d. points behave has been pursued by Mathematicians, Computer Scientists and Physicists. Concentration results bounding tails by those of the normal density with the correct variance is the ideal aim and has been accomplished after much effort for many problems; the starting point is that for i.i.d. points, random variables like the number of points in sub-regions will have normal tails. We will describe two new probability inequalities which help us prove such concentration results under a wider class of heavy-tailed distributions arising in the modern setting. Some possible future applications to other problems will also be described.
Satyanarayana V. Lokam Title: On Locally Decodable Codes Abstract: A Locally Decodable Code (LDC) allows the recovery of a single symbol of a message by reading a few positions of a corrupted encoding of the message. They were formally defined by Katz and Trevisan in 2000. Such codes have numerous applications and connections such as transforming worst-case hardness to average-case hardness, probabilis-tically checkable proof systems, reliable storage, private information retrieval, and randomness extractors. In this talk, we will review the current state of bounds on thelength of LDC's. We will sketch the main ideas in some of the proofs. We will also discuss some open questions.
D. Manjunath Title: On the Timing Channel in a Queue Inferencing Setting Abstract: Queue inferencing is the estimation of the waiting times from the transactional information of a queue, i.e., from the busy periods and service times. There are similarities between queue inferencing and decoding over a timing channel in a packet communication link.We analyze the timing channel achievable rates in the queue inferencing setting for continuous time queues with vacations and for discrete time queues.
Ravi.R.Mazumdar Title: Some new results on the stability of Markovian stochastic network models Abstract: In this paper we provide some new insights on the stability of some Markovian stochastic network models. More precisely we show how a variation of a positive recurrence criterion for multidimensional Markov chains due to Rosberg(JAP, Vol. 17, No. 3, 1980) can be developed to generalize the necessary and sufficient conditions for stability for multiclass Markovian networks with class independent routing and any work conserving service discipline. We also discuss the stability of a coupled processor model of interest in wireless networks.
Upamanyu Madhow Title: On the theory of multiGigabit transceiver implementations Abstract: The analog-to-digital converter (ADC) is the fundamental bottleneck to scaling mostly digital communication transceiver architectures to multiGigabit speeds: high-precision, high-speed ADCs are too costly, too power-hungry, or simply not available. One possible approach to this problem is to use drastically lower ADC precision in the receiver. However, the insertion of a severe nonlinearity in the transceiver chain implies that we must comprehensively rethink signal processing for communication, which is largely based on linear models. After reviewing what Shannon theory tells us, we discuss recent results on demodulation, automatic gain control, and transmit precoding.
Krishna Narayanan Title: Using Rate Distortion Theory for Designing and Analyzing Soft Decision Decoding Algorithms for Reed-Solomon Codes Abstract: One popular approach to soft-decision decoding of Reed-Solomon (RS) codes is based on the idea of using multiple trials of a simple RS decoding algorithm in combination with successively erasing or flipping a set of symbols or bits in each trial. In this paper, we present a framework based on rate-distortion (RD) theory to analyze such multiple-decoding trials for RS codes. By defining an appropriate distortion measure between an error pattern and an erasure pattern, it is shown that, for a single errors-and-erasures decoding trial, the condition for successful decoding is equivalent to the condition that the distortion is smaller than a fixed threshold. This connection to RD theory enables us to use tools usually used for solving the quantization problem such as covering codes, random code book generation and rate-distortion exponent for designing and analyzing soft decision decoding algorithms. These approaches provide a very good trade-off perfomance-versus-complexity. Further, the framework is fairly general and can be used to understand the performance of multiple trials of different algorithm, such as for instance, the Koetter-Vardy algorithm.
Shrikanth Narayanan Title: Speechlinks: models and methods for enriching automated speech to speech translation. Abstract: Translating speech from one language to another can be formulated as a statistical mapping problem, typically composed as a series of sub problems of transcribing speech to text, translating the text from the source language to the target language, and mapping the translated text to speech. Advances in speech and spoken language processing have however opened up opportunities for looking beyond the pipelined automatic speech translation process chain that primarily relies on word level representations, largely ignoring other rich information present in speech and spoken discourse. This talk will describe some methods and models for capturing, modeling and transferring rich contextual information conveyed through speech prosody, discourse, and user state behavior to aid robust speech to speech translation. Open challenges and ongoing work will be highlighted.
Jong-Seon No Title: Peak to Average Power Ratio Reduction for OFDM Systems With Low Complexity Abstract: Orthogonal frequency division multiplexing(OFDM) has gained popularity as a standard for various high data rate wireless communication systems due to the spectral bandwidth efficiency, robustness to frequency selective fading channels, etc. However, its high peak-to-average power ratio (PAPR) causes significant in-band distortion and high out-of-band radiation when it passes through a nonlinear device such as a high power amplifier (HPA). This paper reviews the main PAPR reduction schemes and introduces their modifications for achieving low-complexity required for practical implementation in wireless communication systems.
Sandeep Pradhan Title: On the optimal performance of nested linear codes for point-to-point communication Abstract: In this talk, we report the existence of nested linear codes that asymptotically approach the Shannon capacity cost function and Shannon rate-distortion function in the arbitrary discrete memoryless case. Such codes can be used as building blocks to construct optimal coding systems in multiterminal communication setting.
Kannan Ramchandran Title: Network codes for distributed storage Abstract: Data centers, peer-to-peer networks, and distributed wireless networks are increasingly driving the need for reliable distributed networked storage. In this talk we will highlight the opportunities and challenges for coding in these distributed storage systems. While MDS erasure-codes (e.g. Reed-Solomon codes or more recently fountain codes) have been the traditional choice in classical storage systems, they can be quite bandwidth-inefficient in distributed networked storage systems when faced with the added systems requirement of recovering from individual node failures in the network. Specifically, when a node fails, and a new node has to replace it, what is the minimum amount of data transfer needed from the surviving system nodes to restore the system functionally to its targeted level of reliability? We describe how network-coding based regeneration codes can be used to provide the optimally tradeoff between the network storage cost and the network repair bandwidth. We will then describe the challenges in designing deterministic network codes that provide exact repair, i.e. where the repaired nodes need to be exact replacements for the failed ones, and overview recent progress in this area.
Raghuveer M. Rao Title: Risk Minimization Approach for Optimizing Vector Bilateral Filter Range Kernel Parameters Abstract: A statistical approach is presented for determining the optimal parameters of a vector bilateral filter for suppressing noise in a multi-band image. A closed-form solution to obtaining Stein's unbiased estimate of the vector bilateral filter-based image estimation risk is derived. The values of the parameters are then determined by minimization of the estimated risk, which can be seen as maximization of the estimated signal to noise ratio. Experimental results show that the optimized vector bilateral filter provides better denoising performance on multi-band images than application of conventional 2D bilateral filtering to each individual band image separately. The proposed parameter optimization method also provides estimates of noise intensity that are close to the actual, and the performance in terms of obtaining tradeoff between noise suppression and edge preservation is improved significantly.
Robert Schober Title: Cooperative BICM-OFDM: Sub-carrier and Power Allocation Abstract: In this paper, we consider amplify-and-forward cooperative diversity for wireless systems employing bit-interleaved coded modulation (BICM) and orthogonal frequency division multiplexing (OFDM). In the second hop, multiple relays transmit concurrently over disjoint sets of sub-carriers. We propose uniform and non-uniform sub-carrier allocation schemes, which guarantee full diversity if all involved channels have identical lengths. The non-uniform allocation scheme also guarantees full diversity if the involved channels have different lengths. In addition, we formulate a power allocation problem for minimization of an upper bound on the worst-case pairwise error probability of the considered cooperative diversity scheme and provide an efficient solution using geometric programming. Simulation results confirm the effectiveness of the proposed sub-carrier and power allocation schemes.
Andrew Thangaraj Title: Multistage Relaying using Interference Networks Abstract: One of the key technologies in next generation systems for achieving high throughput and providing better coverage is relaying. Relaying has attracted a high level of recent research interest with several papers focusing on various aspects of communicating using relays with different constraints and assumptions. In this work, we are concerned with the capacity of multistage relaying from one source to one destination through an arbitrary network of half duplex relays.
Emre Telatar Title: Polar coding: a brief tour Abstract: Arikan's 'polar coding' is a technique to achieve the symmetric capacity of binary input memoryless channels. In this talk I will attempt to describe this technique, and briefly discuss its extensions to q-ary input channels, multiple access channels and rate-distortion coding. The underlying principle of polar coding allows one to view randomness from a different vantage. I will try to illustrate this with a recent result of Sasoglu: when a binary ergodic process is transformed by Arikan's 'polar transform' the resulting process, in the limit, consists only of fair coin flips or constants.
Rüdiger Urbanke Title: To be Announced
Sriram Vishwanath Title: Sum-Capacity of K-User Degraded Gaussian Interference Networks Abstract: This paper determines the sum capacity of degraded Gaussian K-user interference channels (IFCs). To this end, the paper first develops a family of genie-MAC (multiple access channel) outer
Pramod Viswanath Title: Approximately Optimal Schemes for Broadcasting in Gaussian Networks Abstract: We study Gaussian broadcast networks: a single communicating independent messages with several destinations. Our main contribution is a communication scheme that achieves reliable data rates that are within a constant gap (at all SNR and channel conditions) away from the cut-set outer bound. The proposed scheme builds on deterministic code constructions for the unicast Gaussian network by carefully combining it with an appropriate deterministic broadcast channel outer code.
|
