Browsing by Author "Rini, Stefano"

Now showing 1 - 20 of 29

A General Framework for MIMO Receivers with Low-Resolution Quantization
(2017-01-01)
Rini, Stefano
;
Barletta, Luca
;
Eldar, Yonina C.
;
Erkip, Elza
;
交大名義發表
The capacity of a discrete-time, multi-input multioutput (MIMO) channel with output quantization is investigated for different receiver architectures. A general framework for low-resolution quantization is proposed in which the antenna outputs are processed by analog combiners and sign quantizers are used for analog-to-digital conversion. The configuration of the analog combiners is chosen as a function of the channel realization so that the transmission rate can be maximized over the set of available configurations. To exemplify the proposed approach, four analog receiver architectures are considered: (a) sign quantization of the antenna outputs, (b) single antenna selection, (c) multiple antenna selection, and (d) linear processing of the antenna outputs. In each scenario, capacity is investigated as a function of the transmit power, the number of transmit/receive antennas and sign quantizers. In particular, it is shown that architecture (a) is sufficient to approach the optimal high signal-to-noise ratio (SNR) performance for a MIMO receiver in which the number of receive antennas is larger than the number of sign quantizers. Numerical evaluations of the average performance are presented for the case in which the channel gains are i.i.d. Gaussian distributed.
A Unified Graphical Approach to Random Coding for Single-Hop Networks
(2016-01-01)
Rini, Stefano
;
Goldsmith, Andrea
;
電信工程研究所
;
Institute of Communications Engineering
A unified graphical approach to random coding for any memoryless, single-hop, K-user channel with or without common information is defined through two steps. The first step is user virtualization. Each user is divided into multiple virtual sub-users according to a chosen rate-splitting strategy. This results in an enhanced channel with a possibly larger number of users for which more coding possibilities are available and for which common messages to any subset of users can be encoded. Following user virtualization, the message of each user in the enhanced model is coded using a chosen combination of coded time-sharing, superposition coding, and joint binning. A graph is used to represent the chosen coding strategies. Nodes in the graph represent codewords, while edges represent coding operations. This graph is used to construct a graphical Markov model, which illustrates the statistical dependence among codewords that can be introduced by the superposition coding or joint binning. Using this statistical representation of the overall codebook distribution, the error probability of the code is shown to vanish through a unified analysis. The rate bounds that define the achievable rate region are obtained by linking the error analysis to the properties of the graphical Markov model. This proposed framework makes it possible to numerically obtain an achievable rate region by specifying a user virtualization strategy and describing a set of coding operations. The union of these rate regions defines the maximum achievable rate region of our unified coding strategy. The achievable rates obtained based on this unified graphical approach to random coding encompass the best random coding achievable rates for all memoryless single-hop networks known to date, including broadcast, multiple access, interference, and cognitive radio channels, as well as new results for topologies not previously studied, as we illustrate with several examples.
A Unified Graphical Approach to Random Coding for Single-Hop Networks
(2016-01)
Rini, Stefano
;
Goldsmith, Andrea
;
電信工程研究所
;
Institute of Communications Engineering
A unified graphical approach to random coding for any memoryless, single-hop, K-user channel with or without common information is defined through two steps. The first step is user virtualization. Each user is divided into multiple virtual sub-users according to a chosen rate-splitting strategy. This results in an enhanced channel with a possibly larger number of users for which more coding possibilities are available and for which common messages to any subset of users can be encoded. Following user virtualization, the message of each user in the enhanced model is coded using a chosen combination of coded time-sharing, superposition coding, and joint binning. A graph is used to represent the chosen coding strategies. Nodes in the graph represent codewords, while edges represent coding operations. This graph is used to construct a graphical Markov model, which illustrates the statistical dependence among codewords that can be introduced by the superposition coding or joint binning. Using this statistical representation of the overall codebook distribution, the error probability of the code is shown to vanish through a unified analysis. The rate bounds that define the achievable rate region are obtained by linking the error analysis to the properties of the graphical Markov model. This proposed framework makes it possible to numerically obtain an achievable rate region by specifying a user virtualization strategy and describing a set of coding operations. The union of these rate regions defines the maximum achievable rate region of our unified coding strategy. The achievable rates obtained based on this unified graphical approach to random coding encompass the best random coding achievable rates for all memoryless single-hop networks known to date, including broadcast, multiple access, interference, and cognitive radio channels, as well as new results for topologies not previously studied, as we illustrate with several examples.
Capacity of Discrete-Time Wiener Phase Noise Channels to Within a Constant Gap
(2017-01-01)
Barletta, Luca
;
Rini, Stefano
;
交大名義發表
;
National Chiao Tung University
The capacity of the discrete-time channel affected by both additive Gaussian noise and Wiener phase noise is studied. Novel inner and outer bounds are presented, which differ of at most 7.36 bit-per-channel-use for all channel parameters. The capacity of this model can be subdivided in three regimes: (i) for large values of the frequency noise variance, the channel behaves similarly to a channel with circularly uniform iid phase noise; (ii) when the frequency noise variance is small, the effect of the additive noise dominates over that of the phase noise, while (iii) for intermediate values of the frequency noise variance, the transmission rate over the phase modulation channel has to be reduced due to the presence of phase noise.
Capacity Outer Bound and Degrees of Freedom of Wiener Phase Noise Channels with Oversampling
(2017-01-01)
Barletta, Luca
;
Rini, Stefano
;
交大名義發表
;
National Chiao Tung University
The discrete-time Wiener phase noise channel with an integrate-and-dump multi-sample receiver is studied. A novel outer bound on the capacity with an average input power constraint is derived as a function of the oversampling factor. This outer bound yields the degrees of freedom for the scenario in which the oversampling factor grows with the transmit power P as P-alpha. The result shows, perhaps surprisingly, that the largest pre-log that can be attained with phase modulation at high signal-to-noise ratio is at most 1/4.
Coding Theorems for the Compress and Estimate Source Coding Problem
(2017-01-01)
Kipnis, Alon
;
Rini, Stefano
;
Goldsmith, Andrea J.
;
電機工程學系
;
Department of Electrical and Computer Engineering
We consider the remote source coding setting in which a source realization is estimated from a lossy compressed sequence of noisy observations. Unlike in the optimal remote source coding problem, however, the encoder is bound to use good codes with respect to the observation sequence, i.e., codes that are optimal for the lossy reconstruction of the observation, rather than the remote source. This encoding strategy is denoted as the compress-and-estimate (CE) scheme. For the case of an i.i.d source observed through a memoryless channel, we show that the distortion in the CE scheme is characterized by a single-letter expression, referred to as the CE distortion-rate function (CE-DRF). In particular, we show that the CE-DRF can be attained by estimating the source from the output of a remote encoder employing any sequence of good codes with respect to the observation sequence. In addition, we show that the limiting distortion in estimating any finite sub-block of the source realization from the output of a remote encoder employing good codes, averaged over all sub-blocks, is also bounded by the CE-DRF.
Comparison-limited Vector Quantization
(2019-01-01)
Chataignon, Joseph
;
Rini, Stefano
;
電機工程學系
;
Department of Electrical and Computer Engineering
A variation of the classic vector quantization problem is considered, in which the analog-to-digital (A2D) conversion is not constrained by the cardinality of the output but rather by the number of comparators available for quantization. More specifically, we consider the scenario in which a vector quantizer of dimension d is comprised of k comparators, each receiving a linear combination of the inputs and producing zero/one when this signal is above/below a threshold. Given a distribution of the inputs and a distortion criterion, the values of the linear combination and threshold are to be configured so as to minimize the distortion between the quantizer input and its reconstruction. This vector quantizer architecture naturally arises in many A2D conversion scenarios in which the quantizer's cost and energy consumption are severely restricted. For this novel vector quantizer architecture, we propose an algorithm to determine the optimal configuration and provide the first performance evaluation for the case of uniform and Gaussian iid sources.
Complete Fix-Free Codes for the Statistical Dictionary-Based String Matching Problem
(2019-01-01)
Suri, Meer
;
Rini, Stefano
;
電機工程學系
;
Department of Electrical and Computer Engineering
In the dictionary based string matching problem, the positions in which a short sequence of symbols, query, occurs in a longer sequence, source, have to be retrieved. To improve the query search efficiency, the source can be pre-processed to build an inverted index, that is a table storing positions of occurrences of certain substrings in the text. Given an inverted index, various algorithms can be utilized to retrieve the position of the query in the source. In the literature, motivated by text retrieval and web search applications, the small v/s small (SvS) algorithm is often considered for the case in which the substrings stored are k-gram codes, i.e. all possible substrings of length k. In [9] we have proposed a novel approach to the string matching problem by letting the strings generating the inverted index be a variable length code, i.e. posting code, to be optimally design for a given performance metric. Posting codes [9] generalize classic k-gram codes and enable new query retrieval algorithms with potentially lower complexity than the SvS algorithm. In this paper, we propose a new query retrieval algorithm, the forward-backward SvS (FB-SvS) algorithm which can be applied when the posting code is a complete fix-free code. The complexity of the FB-SvS algorithm for various fix-free codes is investigated and numerical experiments using the human DNA sequence as the source are presented.
Compress-and-Estimate Source Coding for a Vector Gaussian Source
(2017-01-01)
Song, Ruiyang
;
Rini, Stefano
;
Kipnis, Alon
;
Goldsmith, Andrea J.
;
交大名義發表
We consider the remote vector source coding problem in which a vector Gaussian source is estimated from noisy linear measurements. For this problem, we derive the performance of the compress-and-estimate (CE) coding scheme and compare it to the optimal performance. In the CE coding scheme, the remote encoder compresses the noisy source observations so as to minimize a local distortion measure, independent from the joint distribution between the source and the observations. In reconstruction, the decoder, having full knowledge of the joint distribution of the source and observations, estimates the original source realization from the lossy-compressed noisy observations. For the CE scheme in the vector Gaussian case, we show that, if the code rate is less than a specific threshold, then the CE coding scheme attains the same performance as the optimal coding scheme. For code rates above this threshold, we introduce lower and upper bounds on the performance gap between the CE and the optimal scheme. The case of a two-dimensional Gaussian source observed through two noisy measurements is studied to illustrate the behavior of the performance gap.
DISTRIBUTED CONVEX OPTIMIZATION WITH LIMITED COMMUNICATIONS
(2019-01-01)
Rao, Milind
;
Rini, Stefano
;
Goldsmith, Andrea
;
交大名義發表
;
National Chiao Tung University
In this paper, a distributed convex optimization algorithm, termed distributed coordinate dual averaging (DCDA) algorithm, is proposed. The DCDA algorithm addresses the scenario of a large distributed optimization problem with limited communication among nodes in the network. Currently known distributed subgradient descent methods, such as the distributed dual averaging or the distributed alternating direction method of multipliers, assume that nodes can exchange messages of large cardinality. Such an assumption on the network communication capabilities is not valid in many scenarios of practical relevance. To address this setting, we propose the DCDA algorithm as a distributed convex optimization algorithm in which the communication between nodes in each round is restricted to a fixed number of dimensions. We bound the rate of convergence under different communication protocols and network architectures for this algorithm. We also consider the extensions to the cases of imperfect gradient knowledge and when transmitted messages are corrupted by additive noise or are quantized. Numerical simulations demonstrating the performance of DCDA in these different settings are also provided.
Distributed Sub-gradient Algorithms with Limited Communications
(2019-01-01)
Rini, Stefano
;
Rao, Milind
;
Goldsmith, Andrea
;
交大名義發表
;
National Chiao Tung University
We consider the distributed convex optimization scenario in which nodes in a network collectively find the minimum of a function utilizing only local communications and computations. Various sub-gradient algorithms have been developed for this optimization setting for the case in which the global function factorizes as the sum of local functions to be distributed to the nodes in network, including the distributed (i) online gradient descent, (ii) Nesterov gradient descent, and (iii) dual averaging algorithms. Generally speaking, these subgradient algorithms assume that, in each communication round, nodes can exchange messages of size comparable to that of the optimization variable. For many high-dimensional optimization problems, this communication requirement is beyond the capabilities of the communication network supporting the distributed optimization. For this reason, we propose a dimensionality reduction technique based on random projections to adapt these distributed optimization algorithms to networks with communication links of limited capacity. In particular, we analyze the performance of the proposed dimensionality reduction technique for the three algorithms above, i.e. (i)-(iii). Numerical simulations are presented that illustrate the performance of the proposed approach for these three algorithms.
Joint Constellation and Code Design for the Gaussian Multiple Access Channel
(2017-01-01)
Liang, Yu-Chung
;
Rini, Stefano
;
Kliewer, Jorg
;
交大名義發表
;
National Chiao Tung University
The joint design of both transmit constellation and low-density parity-check codes (LDPC) for the two-user, symbol-synchronous, binary-input Gaussian multiple access channel is considered. A transmission scheme is proposed to approach the symmetric capacity without the use of time-sharing or rate-splitting by joint decoding of the noisy sum of two LDPC codewords. This scheme relies on an extension of the classic belief propagation (BP) algorithm which allows for the simultaneous decoding of two LDPC codewords. We use a Gaussian approximation (GA) of the message distribution to investigate the convergence of the decoding process and derive a linear programming technique for joint code design. We also implement a superposition modulation scheme to achieve higher rate. This code design is applied to different input constellation choices which attain the symmetric capacity in different SNR regimes. It is shown that, quite surprisingly, in the moderate SNR regime the best performance is obtained by an asymmetric constellation.
LDPC Coded Multiuser Shaping for the Gaussian Multiple Access Channel
(2019-01-01)
Balatsoukas-Stimming, Alexios
;
Rini, Stefano
;
Kliewer, Jorg
;
交大名義發表
;
National Chiao Tung University
The joint design of input constellation and low-density parity-check (LDPC) codes to approach the symmetric capacity of the two-user Gaussian multiple access channel is studied. More specifically, multilevel coding is employed at each user to construct a high-order input constellation and the constellations of the users are jointly designed so as to maximize the multiuser shaping gain. At the receiver, each layer of the multilevel coding is jointly decoded among users, while successive cancellation is employed across layers. The LDPC code employed by each user in each layer is designed using EXIT charts to support joint decoding among users for the prescribed per-layer rate and SNR. Numerical simulations are provided to validate the proposed constellation and LDPC code designs.
Multiterminal Compress-and-Estimate Source Coding
(2016)
Kipnis, Alon
;
Rini, Stefano
;
Goldsmith, Andrea J.
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
We consider a multiterminal source coding problem in which a random source signal is estimated from encoded versions of multiple noisy observations. Each encoded version, however, is compressed so as to minimize a local distortion measure, defined only with respect to the distribution of the corresponding noisy observation. The original source is then estimated from these compressed noisy observations. We denote the minimal distortion under this coding scheme as the compress-and-estimate distortion-rate function (CE-DRF). We derive a single-letter expression for the CE-DRF in the case of an i.i.d source. We evaluate this expression for the case of a Gaussian source observed through multiple parallel AWGN channels and quadratic distortion and in the case of a non-uniform binary i.i.d source observed through multiple binary symmetric channels under Hamming distortion. For the case of a Gaussian source, we compare the performance for centralized encoding versus that of distributed encoding. In the centralized encoding scenario, when the code rates are sufficiently small, there is no loss of performance compared to the indirect source coding distortionrate function, whereas distributed encoding achieves distortion strictly larger then the optimal multiterminal source coding scheme. For the case of a binary source, we show that even with a single observation, the CE-DRF is strictly larger than that of indirect source coding.
On Capacity of the Dirty Paper Channel with Fading Dirt in the Strong Fading Regime
(2014-01-01)
Rini, Stefano
;
Shamai (Shitz), Shlomo
;
交大名義發表
;
National Chiao Tung University
The classic "writing on dirty paper" capacity result establishes that full state pre-cancellation can be attained in Gelfand-Pinsker problem with additive state and additive white Gaussian noise. This result holds under the assumption that both the transmitter and the receiver have perfect knowledge of the channel. We are interested in characterizing capacity under the more realistic assumption that only partial channel knowledge is available at the transmitter. To this end we study the "dirty paper channel with slow fading dirt", a variation of the dirty paper channel in which the state sequence is multiplied by a slow fading value known only at the receiver. For this model we establish two approximate characterizations of capacity, one for the case in which fading takes only two values and one for the case in which fading takes M possible values but these values are greatly spaced apart. For both results, a naive strategy in which the encoder pre-codes against different fading realizations in different time slots is sufficient to approach capacity.
On Capacity of the Writing Onto Fast Fading Dirt Channel
(2018-11-01)
Rini, Stefano
;
Shamai Shitz), Shlomo
;
電機工程學系
;
Department of Electrical and Computer Engineering
The Writing onto Fast Fading Dirt (WFFD) channel is investigated to study the effect of partial channel knowledge on the performance of interference pre-cancellation. The WFFD channel is the Gel'fand-Pinsker channel in which the channel output is the sum of the channel input, white Gaussian noise, and a fading-times-state term. The fading-times-state term is obtained as the product of the channel state sequence, known only at the transmitter, and a fast fading process, known only at the receiver. We consider the case of Gaussian-distributed channel states and derive an approximate characterization of capacity for different classes of fading distributions, both continuous and discrete. In particular, we prove that if the fading distribution concentrates in a sufficiently small interval, then capacity is approximately equal to the AWGN capacity times the probability of such interval. We also show that there exists a class of fading distributions for which having the transmitter treat the fading-times-state term as additional noise closely approaches capacity.
On MIMO Channel Capacity with Output Quantization Constraints
(2018-01-01)
Khalili, Abbas
;
Rini, Stefano
;
Barletta, Luca
;
Erkip, Elza
;
Eldar, Yonina C.
The capacity of a Multiple-Input Multiple-Output (MIMO) channel in which the antenna outputs are processed by an analog linear combining network and quantized by a set of threshold quantizers is studied. The linear combining weights and quantization thresholds are selected from a set of possible configurations as a function of the channel matrix. The possible configurations of the combining network model specific analog receiver architectures, such as single antenna selection, sign quantization of the antenna outputs or linear processing of the outputs. An interesting connection between the capacity of this channel and a constrained sphere packing problem in which unit spheres are packed in a hyperplane arrangement is shown. From a high-level perspective, this follows from the fact that each threshold quantizer can be viewed as a hyperplane partitioning the transmitter signal space. Accordingly, the output of the set of quantizers corresponds to the possible regions induced by the hyperplane arrangement corresponding to the channel realization and receiver configuration. This connection provides a number of important insights into the design of quantization architectures for MIMO receivers; for instance, it shows that for a given number of quantizers, choosing configurations which induce a larger number of partitions can lead to higher rates.
On the Capacity of the Carbon Copy onto Dirty Paper Channel
(2017-09-01)
Rini, Stefano
;
Shamai (Shitz), Shlomo
;
電機工程學系
;
Department of Electrical and Computer Engineering
The "carbon copy onto dirty paper" (CCDP) channel is the compound "writing on dirty paper" channel in which the channel output is obtained as the sum of the channel input, white Gaussian noise and a Gaussian state sequence randomly selected among a set possible realizations. The transmitter has non-causal knowledge of the set of possible state sequences but does not know which sequence is selected to produce the channel output. We study the capacity of the CCDP channel for two scenarios: 1) the state sequences are independent and identically distributed; and 2) the state sequences are scaled versions of the same sequence. In the first scenario, we show that a combination of superposition coding, time-sharing, and Gel'fand-Pinsker binning is sufficient to approach the capacity to within 3 bits per channel use for any number of possible state realizations. In the second scenario, we derive capacity to within 4 bits per channel use for the case of two possible state sequences. This result is extended to the CCDP channel with any number of possible state sequences under certain conditions on the scaling parameters, which we denote as "strong fading" regime. We conclude by providing some remarks on the capacity of the CCDP channel in which the state sequences have any jointly Gaussian distribution.
On the Capacity of the Carbon Copying onto Dirty Paper Channel
(2016)
Rini, Stefano
;
Shamai (Shitz), Shlomo
;
交大名義發表
;
National Chiao Tung University
Costa\'s "writing on dirty paper" capacity result establishes that full state pre-cancellation can be attained in the Gel\'fand-Pinsker channel with additive state and additive Gaussian noise. The "carbon copy onto dirty paper" channel is the extension of Costa\'s model to the compound setting: here a common message is to be decoded at M receivers, each observing the sum of the channel input, Gaussian noise and one of M possible state sequences. As in the Gel\'fand-Pinsker channel, the state sequences are anti-causally known at the encoder, which can thus pre-code its transmissions so as to minimize the adverse effects of the channel states. In this paper we derive the capacity to within 2.25 bits-per-channel-use of the M-user "carbon copying onto dirty paper" channel in which the state sequences are Gaussian distributed with the same variance and the same pairwise correlation.
On the Capacity of the Dirty Paper Channel with Fast Fading and Discrete Channel States
(2016)
Rini, Stefano
;
Shamai (Shitz), Shlomo
;
交大名義發表
;
National Chiao Tung University
Interference pre-cancellation as in the "writing onto dirty paper" channel crucially depends on the transmitter having exact knowledge of the way in which input and channel state combine to produce the channel output. The presence of even a small amount of uncertainty in such knowledge, gravely hampers the ability of the encoder to pre-code its transmissions against the channel state. This is particularly disappointing as it implies that interference pre-coding in practical systems is effective only when the channel estimates have very high precision, a condition which is generally unattainable in wireless environments. In this paper we show that state decoding, instead of state pre-cancellation, can be approximately optimal for a channel with discrete states when only partial channel knowledge is available. More specifically, we consider a variation of the "writing onto dirty paper" channel in which a discrete-valued state sequence is multiplied by a fast fading process and derive conditions on the fading distribution for which state decoding closely approaches capacity. This channel model is a special case of the Gelf\'and-Pinsker channel and our results show an instance of this problem in which state decoding is approximately optimal.