Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 35
Encontrada(s) 1 página(s)

e-Archivo. Repositorio Institucional de la Universidad Carlos III de Madrid
Publication Artículo científico (JournalArticle)

The Error Probability of Generalized Perfect Codes via the Meta-Converse

  • Vázquez Vilar, Gonzalo
  • Guillén I Fàbregas, Albert
  • Verdú, Sergio
We introduce a definition of perfect and quasi-perfect codes for discrete symmetric channels based on the packing and covering properties of generalized spheres whose shape is tilted using an auxiliary probability measure. This notion generalizes previous definitions of perfect and quasi-perfect codes and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to coincide with the estimate provided by the meta-converse lower bound. We illustrate how the proposed definition naturally extends to cover almost-lossless source-channel coding and lossy compression., This work was supported in part by the European Research Council (ERC) under Grant 714161 and Grant 725411, in part by the Spanish Ministry of Economy and Corupetitiveness under Grant TEC2016-78434-C3 and Grant DCI-2015-27020, in part by the National Science Foundation under Grant CCF-1513915, in part by the Center for Science of Information, and in part by tbe NSF Science and Technology Center under Grant CCF-0939370.
e-Archivo. Repositorio Institucional de la Universidad Carlos III de Madrid
Publication Contribución de congreso (ConferenceOutput)

Saddlepoint approximations of lower and upper bounds to the error probability in channel coding

  • Font Segura, Josep
  • Vázquez Vilar, Gonzalo
  • Martínez, Alfonso
  • Guillén I Fàbregas, Albert
  • Lancho Serrano, Alejandro
This paper has been presented at: 52nd Annual Conference on Information Sciences and Systems (CISS), Saddlepoint approximations of the meta-converse and random-coding union bounds are derived. These bounds accurately characterize the channel coding minimum error probability for symmetric memoryless channels in a wide range of system parameters. The proposed approximations are simple to compute and yield a unified analysis of both hypothesis-testing lower bounds and random-coding upper bounds., This work has been funded in part by the European Research Council under ERC grant agreement 725411, by the Spanish Ministry of Economy and Competitiveness under grants TEC2013-41718-R, FJCI-2014-22747, IJCI-2015-27020, and TEC2016-78434-C3 (AEI/FEDER, EU), and by the Spanish Ministry of Education, Culture and Sport under grant FPU14/01274.
e-Archivo. Repositorio Institucional de la Universidad Carlos III de Madrid
Publication Contribución de congreso (ConferenceOutput)

Saddlepoint Approximation of the Error Probability of Binary Hypothesis Testing

  • Vázquez Vilar, Gonzalo
  • Guillén i Fàbregas, Albert
  • Koch, Tobias Mirco
  • Lancho Serrano, Alejandro
We propose a saddlepoint approximation of the error probability of a binary hypothesis test between two i.i.d. distributions. The approximation is accurate, simple to compute, and yields a unified analysis in different asymptotic regimes. The proposed formulation is used to efficiently compute the meta-converse lower bound for moderate block-lengths in several cases of interest., This work has been funded in part by the European Research Council (ERC) under grants 714161 and 725411, by the Spanish Ministry of Economy and Competitiveness under grants TEC2013-41718-R, RYC-201416332, IJCI-2015-27020 and TEC2016-78434-C3 (AEI/FEDER, EU), by the Madrid Autonomous Community under grant S2103/ICE-2845 and by the Spanish Ministry of Education, Culture and Sport under grant FPU14/01274.
e-Archivo. Repositorio Institucional de la Universidad Carlos III de Madrid
Publication Contribución de congreso (ConferenceOutput)

The Error Probability of Generalized Perfect Codes

  • Vázquez Vilar, Gonzalo
  • Guillén I Fàbregas, Albert
  • Verdú, Sergio
This paper has been presented at : IEEE International Symposium on Information Theory 2018, We introduce a definition of perfect and quasi-perfect codes for symmetric channels parametrized by an auxiliary output distribution. This new definition generalizes previous definitions and encompasses maximum distance separable codes. The error probability of these codes, whenever they exist, is shown to attain the meta-converse lower bound., This work has been funded in part by the European Research Council (ERC) under grants 714161 and 725411, by the Spanish Ministry of Economy and Competitiveness under Grants TEC2016-78434-C3 and IJCI-2015-27020, by the National Science Foundation under Grant CCF-1513915 and by the Center for Science of Information, an NSF Science and Technology Center under Grant CCF-0939370.
e-Archivo. Repositorio Institucional de la Universidad Carlos III de Madrid
Publication Artículo científico (JournalArticle)

Nearest Neighbor Decoding and Pilot-Aided Channel Estimation for Fading Channels

  • Taufiq Asyhari, A.
  • Koch, Tobias Mirco
  • Guillén i Fàbregas, Albert
The material in this paper was presented in part at the 2011 IEEE International Symposium on Information Theory (ISIT), Saint Petersburg, Russia, 31 July-5 August 2011 and the 49th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, USA, 28-30 September 2011., We study the information rates of noncoherent, stationary, Gaussian, and multiple-input multiple-output (MIMO) flat-fading channels that are achievable with nearest neighbor decoding and pilot-aided channel estimation. In particular, we investigate the behavior of these achievable rates in the limit as the signal-to-noise ratio (SNR) tends to infinity by analyzing the capacity pre-log, which is defined as the limiting ratio of the capacity to the logarithm of the SNR as the SNR tends to infinity. We demonstrate that a scheme estimating the channel using pilot symbols and detecting the message using nearest neighbor decoding (while assuming that the channel estimation is perfect) essentially achieves the capacity pre-log of noncoherent multiple-input single-output flat-fading channels, and it essentially achieves the best so far known lower bound on the capacity pre-log of noncoherent MIMO flat-fading channels. Extending the analysis to fading multiple-access channels reveals interesting relationships between the number of antennas and Doppler bandwidth in the comparative performance of joint transmission and time division multiple-access., The work of A.T.A was supported in part by the Yousef Jameel Scholarship at the University of Cambridge. T. K. received funding from the European's Seventh Framework Programme (FP7/2007-2013) under grant agreement No. 252663, from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement number 714161), and from the Spanish Ministerio de Economía y Competitividad under grant RYC-2014-16332. The work of A.G.i.F. has been funded by the European Research Council under ERC grant agreements 259663 and 725411.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

A sphere-packing exponent for mismatched decoding

  • Kangarshahi, Ehsan Asadi
  • Guillén i Fábregas, A. (Albert)
Comunicació presentada a 2021 IEEE International Symposium on Information Theory (ISIT), celebrat del 12 al 20 de juliol de 2021 de manera virtual., We derive a sphere-packing error exponent for mismatched decoding over discrete memoryless channels. We find a lower bound to the probability of error of mismatched decoding that decays exponentially for coding rates smaller than a new upper bound to the mismatch capacity. For rates higher than the new upper bound, the error probability is shown to be bounded away from zero. The new upper bound is shown to improve over previous upper bounds to the mismatch capacity., This work was supported in part by the European Research Council under Grant 725411.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Asymptotics of the random coding error probability for constant-composition codes

  • Font-Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
Comunicació presentada a 2019 IEEE International Symposium on Information Theory (ISIT), celebrada del 7 al 12 de juliol de 2019 a Paris, França., Saddlepoint approximations to the error probability are derived for multiple-cost-constrained random coding ensembles where codewords satisfy a set of constraints. Constantcomposition inputs over a binary symmetric channel are studied as a particular case. For codewords with equiprobable empirical distribution, the analysis recovers the same error exponent and pre-exponential polynomial decay as the uniform i.i.d. ensemble and provides an explicit formula for the loss in prefactor (thirdorder term) incurred by the constant-composition ensemble., This work has been funded in part by the European Research Council under grant 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Large deviations behavior of the logarithmic error probability of random codes

  • Tamir, Ran
  • Merhav, Neri
  • Weinberger, Nir
  • Guillén i Fábregas, A. (Albert)
This work studies the deviations of the error exponent of the constant composition code ensemble around its expectation, known as the error exponent of the typical random code (TRC). In particular, it is shown that the probability of randomly drawing a codebook whose error exponent is smaller than the TRC exponent is exponentially small; upper and lower bounds for this exponent are given, which coincide in some cases. In addition, the probability of randomly drawing a codebook whose error exponent is larger than the TRC exponent is shown to be double-exponentially small; upper and lower bounds to the double-exponential exponent are given. The results suggest that codebooks whose error exponent is larger than the error exponent of the TRC are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables., The research of R. Tamir and N. Merhav was supported by Israel Science Foundation (ISF) grant no. 137/18. The research of N. Weinberger was partially supported by the MIT–Technion fellowship, and the Viterbi scholarship, Technion. The research of A. Guillen i F ´ abregas was funded in part by the European Research Council under ERC grant 725411 and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R. This paper was presented in part at the 2019 IEEE International Symposium on Information Theory, Paris, France, 7-12 July, 2019.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Importance sampling for coded-modulation error probability estimation

  • Font Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper proposes an efficient simulation method based on importance sampling to estimate the random-coding error probability of coded modulation. The technique is valid for complex-valued modulations over Gaussian channels, channels with memory, and naturally extends to fading channels. The simulation method is built on two nested importance samplers to respectively estimate the pairwise error probability and generate the channel input and output. The effect of the respective number of samples on the overall bias and variance of the estimate of the error probability is characterized. For a memoryless channel, the estimator is shown to be consistent and with a small variance, growing with the square root of the code length, rather than the exponential growth of a standard Monte Carlo estimator., This work has been funded in part by the European Research Council under ERC grant agreement 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Typical random coding exponent for finite-state channels

  • Cocco, Giuseppe
  • Guillén i Fábregas, A. (Albert)
  • Font Segura, Josep
Comunicació presentada a 2022 IEEE International Symposium on Information Theory (ISIT), celebrat del 26 de juny a l'1 de juliol de 2022 a Espoo, Finlàndia., We derive a lower bound on the typical random-coding (TRC) exponent of pairwise-independent codeword ensembles used over a finite-state channel (FSC) at rates below capacity. Under some conditions, we also show that the probability of selecting a code from the ensemble with an error exponent larger than our lower bound tends to one as the codeword length tends to infinity. Our result, presented here for the FSC, also applies to compound channels., This work has been funded in part by the postdoctoral fellowship programme Beatriu de Pinos, funded by the Catalan Secretary of Universities ´ and Research, by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 801370, and by the European Research Council under ERC grant agreement 725411.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

A single-letter upper bound to the mismatch capacity

  • Kangarshahi, Ehsan Asadi
  • Guillén i Fábregas, A. (Albert)
We derive a single-letter upper bound to the mismatched-decoding capacity for discrete memoryless channels. The bound is expressed as the mutual information of a transformation of the channel, such that a maximum-likelihood decoding error on the translated channel implies a mismatched-decoding error in the original channel. In particular, it is shown that if the rate exceeds the upper-bound, the probability of error tends to one exponentially when the block-length tends to infinity. We also show that the underlying optimization problem is a convex-concave problem and that an efficient iterative algorithm converges to the optimal solution. In addition, we show that, unlike achievable rates in the literature, the multiletter version of the bound cannot not improve. A number of examples are discussed throughout the paper., This work was supported in part by the European Research Council under Grant 725411 and in part by the Spanish Ministry of Economy and Competitiveness under Grant TEC2016-78434- C3-1-R.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Multi-class cost-constrained random coding for correlated sources over the multiple-access channel

  • Rezazadeh, Arezou
  • Font Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies a generalized version of multi-class cost-constrained random-coding ensemble with multiple auxiliary costs for the transmission of N correlated sources over an N-user multiple-access channel. For each user, the set of messages is partitioned into classes and codebooks are generated according to a distribution depending on the class index of the source message and under the constraint that the codewords satisfy a set of cost functions. Proper choices of the cost functions recover different coding schemes including message-dependent and message-independent versions of independent and identically distributed, independent conditionally distributed, constant-composition and conditional constant composition ensembles. The transmissibility region of the scheme is related to the Cover-El Gamal-Salehi region. A related family of correlated-source Gallager source exponent functions is also studied. The achievable exponents are compared for correlated and independent sources, both numerically and analytically., This work has been funded in part by the European Research Council under grant 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Mismatched multi-letter successive decoding for the multiple-access channel

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies channel coding for the discrete memoryless multiple-access channel with a given (possibly suboptimal) decoding rule. A multi-letter successive decoding rule depending on an arbitrary non-negative decoding metric is considered, and achievable rate regions and error exponents are derived both for the standard MAC (independent codebooks), and for the cognitive MAC (one user knows both messages) with superposition coding. In the cognitive case, the rate region and error exponent are shown to be tight with respect to the ensemble average. The rate regions are compared with those of the commonly considered decoder that chooses the message pair maximizing the decoding metric, and numerical examples are given for which successive decoding yields a strictly higher sum rate for a given pair of input distributions., This work was supported in part by the European Research Council through ERC under Grant 259663 and Grant 725411, in part by the European Union’s 7th Framework Programme under Grant 303633, and in part by the Spanish Ministry of Economy and Competitiveness under Grant RYC-2011-08150, Grant TEC2012-38800-C03-03, and Grant TEC2016-78434-C3-1-R
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Mismatched binary hypothesis testing: error exponent sensitivity

  • Boroumand, Parham
  • Guillén i Fábregas, A. (Albert)
We study the problem of mismatched binary hypothesis testing between i.i.d. distributions. We analyze the tradeoff between the pairwise error probability exponents when the actual distributions generating the observation are different from the distributions used in the likelihood ratio test, sequential probability ratio test, and Hoeffding’s generalized likelihood ratio test in the composite setting. When the real distributions are within a small divergence ball of the test distributions, we find the deviation of the worst-case error exponent of each test with respect to the matched error exponent. In addition, we consider the case where an adversary tampers with the observation, again within a divergence ball of the observation type. We show that the tests are more sensitive to distribution mismatch than to adversarial observation tampering., This work was supported in part by the European Research Council under Grant 725411 and in part by the Spanish Ministry of Economy and Competitiveness under Grant PID2020-116683GB-C22.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

A Recursive quantizer design algorithm for binary-input discrete memoryless channels

  • Dabirnia, Mehdi
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
The optimal quantization of the outputs of binary-input discrete memoryless channels is considered, whereby the optimal quantizer preserves at least a constant α-fraction of the original mutual information, with the smallest output cardinality. Two recursive methods with top-down and bottom-up approaches are developed; these methods lead to a new necessary condition for the recursive quantizer design. An efficient algorithm with linear complexity, based on dynamic programming and the new necessary optimality condition, is proposed., This work has been funded in part by the European Research Council under grant 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Multilayer codes for synchronization from deletions and insertions

  • Abroshan, Mahed
  • Venkataramanan, Ramji
  • Guillén i Fábregas, A. (Albert)
Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder's sequence X differs from the decoder's sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size., This work was supported in part by the European Research Council under Grant 725411 and in part by the Spanish Ministry of Economy and Competitiveness under Grant TEC2016-78434-C3-1-R.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

A dual-domain achievability of the typical error exponent

  • Cocco, Giuseppe
  • Guillén i Fábregas, A. (Albert)
  • Font Segura, Josep
Comunicació presentada a 2021 IEEE International Symposium on Information Theory (ISIT), celebrat del 12 al 20 de juliol de 2021 de manera virtual., For random-coding ensembles with pairwise-independent codewords, we show that the probability that the exponent of a given code from the ensemble being smaller than an upper bound on the typical random-coding exponent is vanishingly small. This upper bound is known to be tight for i.i.d. ensembles over the binary symmetric channel and for constant-composition codes over memoryless channels. Our result recovers these as special cases and remains valid for arbitrary alphabets and channel memory, as well as arbitrary ensembles with pairwise independent codewords., This work has been funded in part by the postdoctoral fellowship programme Beatriu de Pinos, funded by the Secretary of Universities and Research (Government of Catalonia), by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 801370, and by the European Research Council under ERC grant agreement 725411.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

Minimum probability of error of list M-ary hypothesis testing

  • Kangarshahi, Ehsan Asadi
  • Guillén i Fábregas, A. (Albert)
We study a variation of Bayesian M-ary hypothesis testing in which the test outputs a list of L candidates out of the M possible upon processing the observation. We study the minimum error probability of list hypothesis testing, where an error is defined as the event where the true hypothesis is not in the list output by the test. We derive two exact expressions of the minimum probability or error. The first is expressed as the error probability of a certain non-Bayesian binary hypothesis test and is reminiscent of the meta-converse bound by Polyanskiy, Poor and Verdú (2010). The second, is expressed as the tail probability of the likelihood ratio between the two distributions involved in the aforementioned non-Bayesian binary hypothesis test. Hypothesis testing, error probability, information theory., European Research Council (Grant 725411); Spanish Ministry of Economy and Competitiveness (Grant PID2020-116683GB-C22).
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Error exponents of discrete memoryless channels under small mismatch

  • Patel, Priyanka
  • Molina Oliveras, Francesc|||0000-0002-3188-5599
  • Guillén Fàbregas, Albert|||0000-0003-2795-1124
This paper investigates achievable error exponents of i.i.d. and constant-composition codes for a decoder whose decoding metric is close to the channel probability law in terms of relative entropy. We derive approximations of the worst-case achievable error exponents as functions of the radius of a small relative entropy ball centered at the decoding metric, and characterize the error terms of the underlying approximations. © 2024 IEEE., This work was supported in part by the European Research Council under Grant 725411 and by the Spanish Ministry of Economy and Competitiveness under Grant PID2020-116683GB-C22. Francesc Molina is also supported by the Spanish Ministry of Universities through Margarita Salas Fellowship.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Nearest neighbor decoding for a class of compound channels

  • Molina Oliveras, Francesc|||0000-0002-3188-5599
  • Patel, Priyanka
  • Guillén Fàbregas, Albert|||0000-0003-2795-1124
We study Gaussian i.i.d. codebooks and nearest neighbor decoding over continuous-alphabet channels. We define a class of compound channels that are within a small radius relative entropy ball centered at the nearest neighbor decoding metric. We derive approximations to the worst-case achievable rates and find the penalty terms proportional to the square root of the ball radius. © 2024 IEEE., This work was supported by the European Research Council under Grant 725411 and by the Spanish Ministry of Economy and Competitiveness under Grant PID2020-116683GB-C22. Francesc Molina is also supported by the Spanish Ministry of Universities through Margarita Salas Fellowship., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A single-letter upper bound to the mismatch capacity

  • Kangarshahi, Ehsan Asadi
  • Guillén i Fábregas, A. (Albert)
We derive a single-letter upper bound to the mismatched-decoding capacity for discrete memoryless channels. The bound is expressed as the mutual information of a transformation of the channel, such that a maximum-likelihood decoding error on the translated channel implies a mismatched-decoding error in the original channel. In particular, it is shown that if the rate exceeds the upper-bound, the probability of error tends to one exponentially when the block-length tends to infinity. We also show that the underlying optimization problem is a convex-concave problem and that an efficient iterative algorithm converges to the optimal solution. In addition, we show that, unlike achievable rates in the literature, the multiletter version of the bound cannot not improve. A number of examples are discussed throughout the paper., This work was supported in part by the European Research Council under Grant 725411 and in part by the Spanish Ministry of Economy and Competitiveness under Grant TEC2016-78434- C3-1-R.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Importance sampling for coded-modulation error probability estimation

  • Font Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper proposes an efficient simulation method based on importance sampling to estimate the random-coding error probability of coded modulation. The technique is valid for complex-valued modulations over Gaussian channels, channels with memory, and naturally extends to fading channels. The simulation method is built on two nested importance samplers to respectively estimate the pairwise error probability and generate the channel input and output. The effect of the respective number of samples on the overall bias and variance of the estimate of the error probability is characterized. For a memoryless channel, the estimator is shown to be consistent and with a small variance, growing with the square root of the code length, rather than the exponential growth of a standard Monte Carlo estimator., This work has been funded in part by the European Research Council under ERC grant agreement 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Multi-class cost-constrained random coding for correlated sources over the multiple-access channel

  • Rezazadeh, Arezou
  • Font Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies a generalized version of multi-class cost-constrained random-coding ensemble with multiple auxiliary costs for the transmission of N correlated sources over an N-user multiple-access channel. For each user, the set of messages is partitioned into classes and codebooks are generated according to a distribution depending on the class index of the source message and under the constraint that the codewords satisfy a set of cost functions. Proper choices of the cost functions recover different coding schemes including message-dependent and message-independent versions of independent and identically distributed, independent conditionally distributed, constant-composition and conditional constant composition ensembles. The transmissibility region of the scheme is related to the Cover-El Gamal-Salehi region. A related family of correlated-source Gallager source exponent functions is also studied. The achievable exponents are compared for correlated and independent sources, both numerically and analytically., This work has been funded in part by the European Research Council under grant 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Multilayer codes for synchronization from deletions and insertions

  • Abroshan, Mahed
  • Venkataramanan, Ramji
  • Guillén i Fábregas, A. (Albert)
Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder's sequence X differs from the decoder's sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size., This work was supported in part by the European Research Council under Grant 725411 and in part by the Spanish Ministry of Economy and Competitiveness under Grant TEC2016-78434-C3-1-R.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Nearest neighbor decoding for a class of compound channels

  • Molina Oliveras, Francesc
  • Patel, Priyanka
  • Guillén Fàbregas, Albert
We study Gaussian i.i.d. codebooks and nearest neighbor decoding over continuous-alphabet channels. We define a class of compound channels that are within a small radius relative entropy ball centered at the nearest neighbor decoding metric. We derive approximations to the worst-case achievable rates and find the penalty terms proportional to the square root of the ball radius. © 2024 IEEE., This work was supported by the European Research Council under Grant 725411 and by the Spanish Ministry of Economy and Competitiveness under Grant PID2020-116683GB-C22. Francesc Molina is also supported by the Spanish Ministry of Universities through Margarita Salas Fellowship., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Mismatched multi-letter successive decoding for the multiple-access channel

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies channel coding for the discrete memoryless multiple-access channel with a given (possibly suboptimal) decoding rule. A multi-letter successive decoding rule depending on an arbitrary non-negative decoding metric is considered, and achievable rate regions and error exponents are derived both for the standard MAC (independent codebooks), and for the cognitive MAC (one user knows both messages) with superposition coding. In the cognitive case, the rate region and error exponent are shown to be tight with respect to the ensemble average. The rate regions are compared with those of the commonly considered decoder that chooses the message pair maximizing the decoding metric, and numerical examples are given for which successive decoding yields a strictly higher sum rate for a given pair of input distributions., This work was supported in part by the European Research Council through ERC under Grant 259663 and Grant 725411, in part by the European Union’s 7th Framework Programme under Grant 303633, and in part by the Spanish Ministry of Economy and Competitiveness under Grant RYC-2011-08150, Grant TEC2012-38800-C03-03, and Grant TEC2016-78434-C3-1-R
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Typical random coding exponent for finite-state channels

  • Cocco, Giuseppe
  • Guillén i Fábregas, A. (Albert)
  • Font Segura, Josep
Comunicació presentada a 2022 IEEE International Symposium on Information Theory (ISIT), celebrat del 26 de juny a l'1 de juliol de 2022 a Espoo, Finlàndia., We derive a lower bound on the typical random-coding (TRC) exponent of pairwise-independent codeword ensembles used over a finite-state channel (FSC) at rates below capacity. Under some conditions, we also show that the probability of selecting a code from the ensemble with an error exponent larger than our lower bound tends to one as the codeword length tends to infinity. Our result, presented here for the FSC, also applies to compound channels., This work has been funded in part by the postdoctoral fellowship programme Beatriu de Pinos, funded by the Catalan Secretary of Universities ´ and Research, by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 801370, and by the European Research Council under ERC grant agreement 725411.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

A sphere-packing exponent for mismatched decoding

  • Kangarshahi, Ehsan Asadi
  • Guillén i Fábregas, A. (Albert)
Comunicació presentada a 2021 IEEE International Symposium on Information Theory (ISIT), celebrat del 12 al 20 de juliol de 2021 de manera virtual., We derive a sphere-packing error exponent for mismatched decoding over discrete memoryless channels. We find a lower bound to the probability of error of mismatched decoding that decays exponentially for coding rates smaller than a new upper bound to the mismatch capacity. For rates higher than the new upper bound, the error probability is shown to be bounded away from zero. The new upper bound is shown to improve over previous upper bounds to the mismatch capacity., This work was supported in part by the European Research Council under Grant 725411.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Minimum probability of error of list M-ary hypothesis testing

  • Kangarshahi, Ehsan Asadi
  • Guillén i Fábregas, A. (Albert)
We study a variation of Bayesian M-ary hypothesis testing in which the test outputs a list of L candidates out of the M possible upon processing the observation. We study the minimum error probability of list hypothesis testing, where an error is defined as the event where the true hypothesis is not in the list output by the test. We derive two exact expressions of the minimum probability or error. The first is expressed as the error probability of a certain non-Bayesian binary hypothesis test and is reminiscent of the meta-converse bound by Polyanskiy, Poor and Verdú (2010). The second, is expressed as the tail probability of the likelihood ratio between the two distributions involved in the aforementioned non-Bayesian binary hypothesis test. Hypothesis testing, error probability, information theory., European Research Council (Grant 725411); Spanish Ministry of Economy and Competitiveness (Grant PID2020-116683GB-C22).
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A Recursive quantizer design algorithm for binary-input discrete memoryless channels

  • Dabirnia, Mehdi
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
The optimal quantization of the outputs of binary-input discrete memoryless channels is considered, whereby the optimal quantizer preserves at least a constant α-fraction of the original mutual information, with the smallest output cardinality. Two recursive methods with top-down and bottom-up approaches are developed; these methods lead to a new necessary condition for the recursive quantizer design. An efficient algorithm with linear complexity, based on dynamic programming and the new necessary optimality condition, is proposed., This work has been funded in part by the European Research Council under grant 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Large deviations behavior of the logarithmic error probability of random codes

  • Tamir, Ran
  • Merhav, Neri
  • Weinberger, Nir
  • Guillén i Fábregas, A. (Albert)
This work studies the deviations of the error exponent of the constant composition code ensemble around its expectation, known as the error exponent of the typical random code (TRC). In particular, it is shown that the probability of randomly drawing a codebook whose error exponent is smaller than the TRC exponent is exponentially small; upper and lower bounds for this exponent are given, which coincide in some cases. In addition, the probability of randomly drawing a codebook whose error exponent is larger than the TRC exponent is shown to be double-exponentially small; upper and lower bounds to the double-exponential exponent are given. The results suggest that codebooks whose error exponent is larger than the error exponent of the TRC are extremely rare. The key ingredient in the proofs is a new large deviations result of type class enumerators with dependent variables., The research of R. Tamir and N. Merhav was supported by Israel Science Foundation (ISF) grant no. 137/18. The research of N. Weinberger was partially supported by the MIT–Technion fellowship, and the Viterbi scholarship, Technion. The research of A. Guillen i F ´ abregas was funded in part by the European Research Council under ERC grant 725411 and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R. This paper was presented in part at the 2019 IEEE International Symposium on Information Theory, Paris, France, 7-12 July, 2019.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Error exponents of discrete memoryless channels under small mismatch

  • Patel, Priyanka
  • Molina Oliveras, Francesc
  • Guillén Fàbregas, Albert
This paper investigates achievable error exponents of i.i.d. and constant-composition codes for a decoder whose decoding metric is close to the channel probability law in terms of relative entropy. We derive approximations of the worst-case achievable error exponents as functions of the radius of a small relative entropy ball centered at the decoding metric, and characterize the error terms of the underlying approximations. © 2024 IEEE., This work was supported in part by the European Research Council under Grant 725411 and by the Spanish Ministry of Economy and Competitiveness under Grant PID2020-116683GB-C22. Francesc Molina is also supported by the Spanish Ministry of Universities through Margarita Salas Fellowship., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

A dual-domain achievability of the typical error exponent

  • Cocco, Giuseppe
  • Guillén i Fábregas, A. (Albert)
  • Font Segura, Josep
Comunicació presentada a 2021 IEEE International Symposium on Information Theory (ISIT), celebrat del 12 al 20 de juliol de 2021 de manera virtual., For random-coding ensembles with pairwise-independent codewords, we show that the probability that the exponent of a given code from the ensemble being smaller than an upper bound on the typical random-coding exponent is vanishingly small. This upper bound is known to be tight for i.i.d. ensembles over the binary symmetric channel and for constant-composition codes over memoryless channels. Our result recovers these as special cases and remains valid for arbitrary alphabets and channel memory, as well as arbitrary ensembles with pairwise independent codewords., This work has been funded in part by the postdoctoral fellowship programme Beatriu de Pinos, funded by the Secretary of Universities and Research (Government of Catalonia), by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 801370, and by the European Research Council under ERC grant agreement 725411.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Asymptotics of the random coding error probability for constant-composition codes

  • Font-Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
Comunicació presentada a 2019 IEEE International Symposium on Information Theory (ISIT), celebrada del 7 al 12 de juliol de 2019 a Paris, França., Saddlepoint approximations to the error probability are derived for multiple-cost-constrained random coding ensembles where codewords satisfy a set of constraints. Constantcomposition inputs over a binary symmetric channel are studied as a particular case. For codewords with equiprobable empirical distribution, the analysis recovers the same error exponent and pre-exponential polynomial decay as the uniform i.i.d. ensemble and provides an explicit formula for the loss in prefactor (thirdorder term) incurred by the constant-composition ensemble., This work has been funded in part by the European Research Council under grant 725411, and by the Spanish Ministry of Economy and Competitiveness under grant TEC2016-78434-C3-1-R.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Mismatched binary hypothesis testing: error exponent sensitivity

  • Boroumand, Parham
  • Guillén i Fábregas, A. (Albert)
We study the problem of mismatched binary hypothesis testing between i.i.d. distributions. We analyze the tradeoff between the pairwise error probability exponents when the actual distributions generating the observation are different from the distributions used in the likelihood ratio test, sequential probability ratio test, and Hoeffding’s generalized likelihood ratio test in the composite setting. When the real distributions are within a small divergence ball of the test distributions, we find the deviation of the worst-case error exponent of each test with respect to the matched error exponent. In addition, we consider the case where an adversary tampers with the observation, again within a divergence ball of the observation type. We show that the tests are more sensitive to distribution mismatch than to adversarial observation tampering., This work was supported in part by the European Research Council under Grant 725411 and in part by the Spanish Ministry of Economy and Competitiveness under Grant PID2020-116683GB-C22.