Pasar al contenido principal

MISMATCHED-DECODING ANALYSIS OF FINITE-LENGTH INFORMATION TRANSMISSION, WITH APPLICATIONS TO COMMUNICATIONS AND DATA COMPRESSION

RYC-2011-08150

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Contratación e Incorporación de RRHH
Subprograma Subprograma Ramón y Cajal (RYC)
Convocatoria Ramón y Cajal
Año convocatoria 2011
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Formación e Incorporación de Investigadores
Centro beneficiario UNIVERSITAT POMPEU FABRA CCT
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

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

Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Multi-class source-channel coding

  • Bocharova, Irina E.
  • Guillén i Fábregas, A. (Albert)
  • Kudryashov, Boris D.
  • Martínez, Alfonso, 1973-
  • Tauste Campo, Adrià, 1982-
  • Vazquez-Vilar, Gonzalo
This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases., This work was supported in part by the European Research Council under Grant 259663, in part by the Spanish Ministry of Economy and Competitiveness under Grant FPDI-2013-18602, Grant RYC-2011-08150, Grant TEC2012-38800-C03-03, and Grant TEC2013-41718-R, and in part by the European Union’s 7th Framework Programme under Grant 303633 and Grant 329837.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Expurgated random-coding ensembles: exponents, refinements and connections

  • Scarlett, Jonathan
  • Peng, Li
  • Merhav, Neri
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies expurgated random-coding bounds and exponents for channel coding with a given (possibly suboptimal) decoding rule. Variations of Gallager's analysis are presented, yielding several asymptotic and nonasymptotic bounds on the error probability for an arbitrary codeword distribution. A simple nonasymptotic bound is shown to attain an exponent of Csiszár and Körner under constant-composition coding. Using Lagrange duality, this exponent is expressed in several forms, one of which is shown to permit a direct derivation via cost-constrained coding that extends to infinite and continuous alphabets. The method of type class enumeration is studied, and it is shown that this approach can yield improved exponents and better tightness guarantees for some codeword distributions. A generalization of this approach is shown to provide a multiletter exponent that extends immediately to channels with memory., This work was supported in part by the European Research Council under Grant 259663, 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 and Grant TEC2012-38800-C03-03. The work of N. Merhav was supported by the Israel Science Foundation under Grant 412/12.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Mismatched decoding: error exponents, second-order rates and saddlepoint approximations

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper considers the problem of channel coding with a given (possibly suboptimal) maximum-metric decoding rule. A cost-constrained random-coding ensemble with multiple auxiliary costs is introduced, and is shown to achieve error exponents and second-order coding rates matching those of constant-composition random coding, while being directly applicable to channels with infinite or continuous alphabets. The number of auxiliary costs required to match the error exponents and second-order rates of constant-composition coding is studied, and is shown to be at most two. For independent identically distributed random coding, asymptotic estimates of two well-known non-asymptotic bounds are given using saddlepoint approximations. Each expression is shown to characterize the asymptotic behavior of the corresponding random-coding bound at both fixed and varying rates, thus unifying the regimes characterized by error exponents, second-order rates, and moderate deviations. For fixed rates, novel exact asymptotics expressions are obtained to within a multiplicative 1+o(1) term. Using numerical examples, it is shown that the saddlepoint approximations are highly accurate even at short block lengths., This work was supported in part by the European Research Council under Grant 259663, 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 Grants RYC-2011-08150 and TEC2012-38800-C03-03.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Extremes of error exponents

  • Guillén i Fábregas, A. (Albert)
  • Land, Ingmar
  • Martínez, Alfonso, 1973-
This paper determines the range of feasible values of standard error exponents for binary-input memoryless symmetric channels of fixed capacity C and shows that extremes are attained by the binary symmetric and the binary erasure channel. The proof technique also provides analogous extremes for other quantities related to Gallager's E 0 function, such as the cutoff rate, the Bhattacharyya parameter, and the channel dispersion., This work was supported in part by the International Joint Project 2008/R2 of the Royal Society, in part by the Australian Research Council under ARC Discovery Grant DP0986089, and in part by the European Research Council under ERC grant agreement 259663. A. Martinez was supported in part by the Ministry of Economy and Competitiveness (Spain) under Grant RYC-2011-08150 and in part by the European Union’s 7th Framework Programme (PEOPLE-2011-CIG) under Grant 303633.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Multiuser random coding techniques for mismatched decoding

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth's achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth's achievable rate region is given, and the latter is shown to immediately extend to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters., This work was supported in part by the European Union Seventh Framework Program under Grant 303633, in part by the Spanish Ministry of Economy and Competitiveness under Grant RYC-2011-08150, and Grant TEC2012-38800-C03-03, and in part by the European Research Council under Grant 259663.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Bayesian M-Ary hypothesis testing: the meta-converse and Verdú-Han bounds are tight

  • Vazquez-Vilar, Gonzalo
  • Tauste Campo, Adrià, 1982-
  • Guillén i Fábregas, A. (Albert)
  • Martínez, Alfonso, 1973-
Two alternative exact characterizations of the minimum error probability of Bayesian M-ary hypothesis testing are derived. The first expression corresponds to the error probability of an induced binary hypothesis test and implies the tightness of the meta-converse bound by Polyanskiy et al.; the second expression is a function of an information-spectrum measure and implies the tightness of a generalized Verdú-Han lower bound. The formulas characterize the minimum error probability of several problems in information theory and help to identify the steps where existing converse bounds are loose., This work was supported in part by the European Research Council under Grant 259663, in part by the Spanish Ministry of Economy and Competitiveness under Grant FPDI-2013-18602, Grant RYC-2011-08150, and Grant TEC2012-38800-C03-03, and in part by the European Union’s 7th Framework Programme under Grant 303633 and Grant 329837.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Multiuser coding techniques for mismatched decoding

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies multiuser coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, error exponents are obtained which are tight with respect to the ensemble average, and positive within the interior of Lapidoth’s achievable rate region. In the special case of maximum-likelihood decoding, the ensemble tightness of the exponent of Liu-Hughes is proved. Alternative expressions for the error exponents and rate regions are given, including expressions obtained using Lagrange duality which extend immediately to general alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to two types of superposition coding. The standard version is shown to yield an achievable rate which is at least as high as that of Lapidoth’s expurgated parallel coding rate after the optimization of the parameters. A refined version of superposition coding is shown to achieve rates at least as good as the standard version for any set of random-coding parameters, and it is shown that the gap between the two can be significant when the input distribution is fixed., This work was supported in part by the European Union Seventh Framework Program under Grant 303633, in part by the Spanish Ministry of Economy and Competitiveness under Grant RYC-2011-08150, and Grant TEC2012-38800-C03-03, and in part by the European Research Council under Grant 259663.
Repositorio Digital de la UPF
Publicación 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
Publicación Artículo científico (JournalArticle)

Second-order rate region of constant-composition codes for the multiple-access channel

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies the second-order asymptotics of coding rates for the discrete memoryless multiple-access channel (MAC) with a fixed target error probability. Using constant-composition random coding, coded time-sharing, and a variant of Hoeffding's combinatorial central limit theorem, an inner bound on the set of locally achievable second-order coding rates is given for each point on the boundary of the capacity region. It is shown that the inner bound for constant-composition random coding includes that recovered by independent identically distributed random coding, and that the inclusion may be strict. The inner bound is extended to the Gaussian MAC via an increasingly fine quantization of the inputs., This work was supported in part by the European Research Council under Grant 259663, 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 and Grant TEC2012-38800-C03-03.
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Asymptotics of the error probability in quasi-static binary symmetric channels

  • Font-Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
Comunicació presentada a 2017 IEEE International Symposium on Information Theory (ISIT), celebrada del 25 al 30 de juny de 2017 a Aachen, Alemania., This paper provides an asymptotic expansion of the error probability, as the codeword length n goes to infinity, in quasi-static binary symmetric channels. After the leading term, namely the outage probability, the next two terms are found to be proportional to log n n and 1 n respectively. Explicit characterizations of the respective coefficients are given. The resulting expansion gives an approximation to the random-coding union bound, accurate even at small codeword lengths., This work has been funded in part by the European Research Council under ERC grant agreement 259663 and by the Spanish Ministry of Economy and Competitiveness under grants RYC-2011-08150, FJCI-2014-22747, and TEC2016-78434-C3-1-R.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Asymptotics of the error probability in quasi-static binary symmetric channels

  • Font-Segura, Josep
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
Comunicació presentada a 2017 IEEE International Symposium on Information Theory (ISIT), celebrada del 25 al 30 de juny de 2017 a Aachen, Alemania., This paper provides an asymptotic expansion of the error probability, as the codeword length n goes to infinity, in quasi-static binary symmetric channels. After the leading term, namely the outage probability, the next two terms are found to be proportional to log n n and 1 n respectively. Explicit characterizations of the respective coefficients are given. The resulting expansion gives an approximation to the random-coding union bound, accurate even at small codeword lengths., This work has been funded in part by the European Research Council under ERC grant agreement 259663 and by the Spanish Ministry of Economy and Competitiveness under grants RYC-2011-08150, FJCI-2014-22747, and TEC2016-78434-C3-1-R.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Multiuser coding techniques for mismatched decoding

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies multiuser coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, error exponents are obtained which are tight with respect to the ensemble average, and positive within the interior of Lapidoth’s achievable rate region. In the special case of maximum-likelihood decoding, the ensemble tightness of the exponent of Liu-Hughes is proved. Alternative expressions for the error exponents and rate regions are given, including expressions obtained using Lagrange duality which extend immediately to general alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to two types of superposition coding. The standard version is shown to yield an achievable rate which is at least as high as that of Lapidoth’s expurgated parallel coding rate after the optimization of the parameters. A refined version of superposition coding is shown to achieve rates at least as good as the standard version for any set of random-coding parameters, and it is shown that the gap between the two can be significant when the input distribution is fixed., This work was supported in part by the European Union Seventh Framework Program under Grant 303633, in part by the Spanish Ministry of Economy and Competitiveness under Grant RYC-2011-08150, and Grant TEC2012-38800-C03-03, and in part by the European Research Council under Grant 259663.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Artículo científico (JournalArticle)

Mismatched decoding: error exponents, second-order rates and saddlepoint approximations

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper considers the problem of channel coding with a given (possibly suboptimal) maximum-metric decoding rule. A cost-constrained random-coding ensemble with multiple auxiliary costs is introduced, and is shown to achieve error exponents and second-order coding rates matching those of constant-composition random coding, while being directly applicable to channels with infinite or continuous alphabets. The number of auxiliary costs required to match the error exponents and second-order rates of constant-composition coding is studied, and is shown to be at most two. For independent identically distributed random coding, asymptotic estimates of two well-known non-asymptotic bounds are given using saddlepoint approximations. Each expression is shown to characterize the asymptotic behavior of the corresponding random-coding bound at both fixed and varying rates, thus unifying the regimes characterized by error exponents, second-order rates, and moderate deviations. For fixed rates, novel exact asymptotics expressions are obtained to within a multiplicative 1+o(1) term. Using numerical examples, it is shown that the saddlepoint approximations are highly accurate even at short block lengths., This work was supported in part by the European Research Council under Grant 259663, 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 Grants RYC-2011-08150 and TEC2012-38800-C03-03.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Multiuser random coding techniques for mismatched decoding

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth's achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth's achievable rate region is given, and the latter is shown to immediately extend to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters., This work was supported in part by the European Union Seventh Framework Program under Grant 303633, in part by the Spanish Ministry of Economy and Competitiveness under Grant RYC-2011-08150, and Grant TEC2012-38800-C03-03, and in part by the European Research Council under Grant 259663.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Multi-class source-channel coding

  • Bocharova, Irina E.
  • Guillén i Fábregas, A. (Albert)
  • Kudryashov, Boris D.
  • Martínez, Alfonso, 1973-
  • Tauste Campo, Adrià, 1982-
  • Vazquez-Vilar, Gonzalo
This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases., This work was supported in part by the European Research Council under Grant 259663, in part by the Spanish Ministry of Economy and Competitiveness under Grant FPDI-2013-18602, Grant RYC-2011-08150, Grant TEC2012-38800-C03-03, and Grant TEC2013-41718-R, and in part by the European Union’s 7th Framework Programme under Grant 303633 and Grant 329837.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Expurgated random-coding ensembles: exponents, refinements and connections

  • Scarlett, Jonathan
  • Peng, Li
  • Merhav, Neri
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies expurgated random-coding bounds and exponents for channel coding with a given (possibly suboptimal) decoding rule. Variations of Gallager's analysis are presented, yielding several asymptotic and nonasymptotic bounds on the error probability for an arbitrary codeword distribution. A simple nonasymptotic bound is shown to attain an exponent of Csiszár and Körner under constant-composition coding. Using Lagrange duality, this exponent is expressed in several forms, one of which is shown to permit a direct derivation via cost-constrained coding that extends to infinite and continuous alphabets. The method of type class enumeration is studied, and it is shown that this approach can yield improved exponents and better tightness guarantees for some codeword distributions. A generalization of this approach is shown to provide a multiletter exponent that extends immediately to channels with memory., This work was supported in part by the European Research Council under Grant 259663, 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 and Grant TEC2012-38800-C03-03. The work of N. Merhav was supported by the Israel Science Foundation under Grant 412/12.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Second-order rate region of constant-composition codes for the multiple-access channel

  • Scarlett, Jonathan
  • Martínez, Alfonso, 1973-
  • Guillén i Fábregas, A. (Albert)
This paper studies the second-order asymptotics of coding rates for the discrete memoryless multiple-access channel (MAC) with a fixed target error probability. Using constant-composition random coding, coded time-sharing, and a variant of Hoeffding's combinatorial central limit theorem, an inner bound on the set of locally achievable second-order coding rates is given for each point on the boundary of the capacity region. It is shown that the inner bound for constant-composition random coding includes that recovered by independent identically distributed random coding, and that the inclusion may be strict. The inner bound is extended to the Gaussian MAC via an increasingly fine quantization of the inputs., This work was supported in part by the European Research Council under Grant 259663, 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 and Grant TEC2012-38800-C03-03.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bayesian M-Ary hypothesis testing: the meta-converse and Verdú-Han bounds are tight

  • Vazquez-Vilar, Gonzalo
  • Tauste Campo, Adrià, 1982-
  • Guillén i Fábregas, A. (Albert)
  • Martínez, Alfonso, 1973-
Two alternative exact characterizations of the minimum error probability of Bayesian M-ary hypothesis testing are derived. The first expression corresponds to the error probability of an induced binary hypothesis test and implies the tightness of the meta-converse bound by Polyanskiy et al.; the second expression is a function of an information-spectrum measure and implies the tightness of a generalized Verdú-Han lower bound. The formulas characterize the minimum error probability of several problems in information theory and help to identify the steps where existing converse bounds are loose., This work was supported in part by the European Research Council under Grant 259663, in part by the Spanish Ministry of Economy and Competitiveness under Grant FPDI-2013-18602, Grant RYC-2011-08150, and Grant TEC2012-38800-C03-03, and in part by the European Union’s 7th Framework Programme under Grant 303633 and Grant 329837.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Extremes of error exponents

  • Guillén i Fábregas, A. (Albert)
  • Land, Ingmar
  • Martínez, Alfonso, 1973-
This paper determines the range of feasible values of standard error exponents for binary-input memoryless symmetric channels of fixed capacity C and shows that extremes are attained by the binary symmetric and the binary erasure channel. The proof technique also provides analogous extremes for other quantities related to Gallager's E 0 function, such as the cutoff rate, the Bhattacharyya parameter, and the channel dispersion., This work was supported in part by the International Joint Project 2008/R2 of the Royal Society, in part by the Australian Research Council under ARC Discovery Grant DP0986089, and in part by the European Research Council under ERC grant agreement 259663. A. Martinez was supported in part by the Ministry of Economy and Competitiveness (Spain) under Grant RYC-2011-08150 and in part by the European Union’s 7th Framework Programme (PEOPLE-2011-CIG) under Grant 303633.