Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Problems of Information Transmission
Erschienen in: Problems of Information Transmission 3/2020

01.07.2020 | Information Theory

The Sphere Packing Bound for Memoryless Channels

verfasst von: B. Nakiboğlu

Erschienen in: Problems of Information Transmission | Ausgabe 3/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Sphere packing bounds (SPBs)—with prefactors that are polynomial in the block length—are derived for codes on two families of memoryless channels using Augustin’s method: (possibly nonstationary) memoryless channels with (possibly multiple) additive cost constraints and stationary memoryless channels with convex constraints on the composition (i.e., empirical distribution, type) of the input codewords. A variant of Gallager’s bound is derived in order to show that these sphere packing bounds are tight in terms of the exponential decay rate of the error probability with the block length under mild hypotheses.
Nächster Artikel Symmetric Block Designs and Optimal Equidistant Codes

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
According to [12, p. 183], the SPB for the constant composition codes appears in [9] with an incomplete proof. The first complete proof of the SPB for the constant composition codes is provided in [10].
 
2
In [28], we have derived refined SPBs (which are optimal in terms of the prefactor for nonsingular cases) for all of the cases considered in [3‐13, 17, 21, 22] using Augustin information measures via [26].
 
3
[31, p. 413] reads "An important feature of the lower bound, which will be derived, is that no assumption of constant-composition codewords is made, not even as an intermediate step.”
 
4
Augustin [24, Section 33] has an additional hypothesis, \(\mathop{\bigvee}\limits_{x\in {\mathscr{X}}}\rho (x)\le {1\mkern-4mu{\rm I}}\), which excludes certain important cases such as the Gaussian channels.
 
5
Note that \(\sum \limits_{t=L}^{M}\left(\begin{array}{c}M\\ t\end{array}\right){s}^{t}{(1-s)}^{M-t}=\left(\begin{array}{c}M\\ L\end{array}\right){s}^{L}\sum \limits_{t=0}^{M-L}\frac{L!\,(M-L)!}{(L+t)!\,(M-L-t)!}{s}^{t}{(1-s)}^{M-L-t}\le \left(\begin{array}{c}M\\ L\end{array}\right){s}^{L}\) for all s ∈ [0, 1].
 
6
In particular, \(\|{q}_{\alpha }-{q}_{\eta }\| \le \sqrt{8\ln \frac{\epsilon }{\epsilon -(1-\epsilon )| \alpha -\eta | }}\), because \(\,\|\, {q}_{\alpha }-{q}_{\eta }\,\|\, \le \sqrt{4{D}_{1/2}({q}_{\alpha }\,\|\, {q}_{\eta })}\) by [36, Theorem 31], D1/2(qα ∥ qη) = nD1/2(qα,t ∥ qη,t) by [36, Theorem 28] and the definition of qα, \({D}_{1/2}({q}_{\alpha ,t}\,\|\, {q}_{\eta ,t})\le 2\ln \frac{2}{2-\,\|\, {q}_{\alpha ,t}-{q}_{\eta ,t}\,\|\, }\) by [26, equation (9)], and \(\,\|\, {q}_{\alpha ,t}-{q}_{\eta ,t}\,\|\, \le 2\frac{1-\epsilon }{\epsilon }| \eta -\alpha | \) by the definition of qα.
 
7
The constraint \(\sum\limits_{i}{\varrho }_{\alpha ,i}=\varrho \) determines λα uniquely, because the expression on the right-hand side of (78) is a nonincreasing function of λα.
 
8
Note that \({C}_{\alpha ,\varLambda ,\varrho }={C}_{\alpha ,{\varLambda }^{\le \varrho }}\) and \({q}_{\alpha ,\varLambda ,\varrho }={q}_{\alpha ,{\varLambda }^{\le \varrho }}\) for the Poisson channel \({\varLambda }^{\le \varrho }\colon\{f\in {\mathscr{F}}:\:\rho (f)\le \varrho \}\to {\mathcal{P}}({\mathcal{Y}})\) considered in [27, Example 10].
 
9
Blahut mentions only the first equality explicitly.
 
10
Recently, Yang argued that Blahut’s method can be used to derive the SPB if the minimax equality given in [54, equation (3.63)] holds. Thus, as a result of our analysis we can conclude that [54, equation (3.63)] does not holds in general. This fact can be derived using the absence of the minimax equality for G(R, W, p, q) without relying on the reasoning in [54] as well.
 
Literatur
1.
Nakiboğlu, B., The Augustin Center and the Sphere Packing Bound for Memoryless Channels, in Proc. 2017 IEEE Int. Symp. on Information Theory (ISIT’2017), Aachen, Germany, June 25–30, 2017, pp. 1401–1405.
2.
Elias, P., Coding for Noisy Channels, IRE Conv. Rec., 1955, vol. 4, pp. 37–46. Reprinted in Key Papers in the Development of Information Theory, Slepian, D., Ed., New York: IEEE Press, 1974, pp. 102–111.
3.
Elias, P., Coding for Two Noisy Channels, Information Theory: Third London Symposium (London, England, Sept. 1955), Cherry C., Ed., London: Butterworth Sci., 1956, pp. 61–74.
4.
Dobrushin, R.L.Asymptotic Estimates of the Probability of Error for Transmission of Messages over a Discrete Memoryless Communication Channel with a Symmetric Transition Probability Matrix, Teor. Veroyatn. Primen., 1962, vol. 7, no. 3, pp. 283–311 [Theory Probab. Appl. (Engl. Transl.), 1962, vol. 7, no. 3, pp. 270–300].
5.
Altuğ, Y. and Wagner, A.B., On Exact Asymptotics of the Error Probability in Channel Coding: Symmetric Channels, arXiv:1908.11419[cs.IT], 2019.
6.
Altuğ, Y. and Wagner, A.B., Refinement of the Sphere Packing Bound for Symmetric Channels, in Proc. 49th Annu. Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Sept. 27–30, 2011, pp. 30–37.
7.
Shannon, C.E., Gallager, R.G., and Berlekamp, E.R., Lower Bounds to Error Probability for Coding on Discrete Memoryless Channels. I, II, Inform. Control, 1967, vol. 10, no. 1, pp. 65–103; no. 5, pp. 522–552.MathSciNetCrossRef
8.
Gallager, R.G., Information Theory and Reliable Communication, New York: Wiley, 1968.MATH
9.
Fano, R.M., Transmission of Information: A Statistical Theory of Communications, New York: M.I.T. Press, 1961.CrossRef
10.
Haroutunian, E.A., Bounds for the Exponent of the Probability of Error for a Semicontinuous Memoryless Channel, Probl. Peredachi Inf., 1968, vol. 4, no. 4, pp. 37–48 [Probl. Inf. Transm. (Engl. Transl.), 1968, vol. 4, no. 4, pp. 29–39].MathSciNet
11.
Omura, J.K., A Lower Bounding Method for Channel and Source Coding Probabilities, Inform. Control, 1975, vol. 27, no. 2, pp. 148–177.MathSciNetCrossRef
12.
Csiszár, I. and Körner, J., Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge, UK: Cambridge Univ. Press, 2011, 2nd ed.CrossRef
13.
Altuğ, Y. and Wagner, A.B., Refinement of the Sphere-Packing Bound: Asymmetric Channels, IEEE Trans. Inform. Theory, 2014, vol. 60, no. 3, pp. 1592–1614.MathSciNetCrossRef
14.
Nakiboğlu, B., A Simple Derivation of the Refined SPB for the Constant Composition Codes, in Proc. 2019 IEEE Int. Symp. on Information Theory (ISIT’2019), Paris, France, July 7–12, 2019, pp. 2659–2663.
15.
Wyner, A.D., Capacity and Error Exponent for the Direct Detection Photon Channel. II, IEEE Trans. Inform. Theory, 1988, vol. 34, no. 6, pp. 1462–1471.MathSciNetCrossRef
16.
Burnashev, M.V. and Kutoyants, Yu.A., On the Sphere-Packing Bound, Capacity, and Similar Results for Poisson Channels, Probl. Peredachi Inf., 1999, vol. 35, no. 2, pp. 3–22 [Probl. Inf. Transm. (Engl. Transl.), 1999, vol. 35, no. 2, pp. 95–111].MathSciNetMATH
17.
Shannon, C.E., Probability of Error for Optimal Codes in a Gaussian Channel, Bell Syst. Tech. J., 1959, vol. 38, no. 3, pp. 611–656.MathSciNetCrossRef
18.
19.
20.
21.
22.
Lancho, A., Östman, J., Durisi, G., Koch, T., and Vazquez-Vilar, G., Saddlepoint Approximations for Short-Packet Wireless Communications, IEEE Trans. Wireless Commun., 2020, vol. 19, no. 7, pp. 4831–4846.CrossRef
23.
Augustin, U., Error Estimates for Low Rate Codes, Z. Wahrsch. Verw. Gebiete, 1969, vol. 14, no. 1, pp. 61–88.MathSciNetCrossRef
24.
25.
Nakiboğlu, B., The Sphere Packing Bound via Augustin’s Method, IEEE Trans. Inform. Theory, 2019, vol. 65, no. 2, pp. 816–840.MathSciNetCrossRef
26.
Nakiboğlu, B., The Augustin Capacity and Center, Probl. Peredachi Inf., 2019, vol. 55, no. 4, pp. 3–51 [Probl. Inf. Transm. (Engl. Transl.), 2019, vol. 55, no. 4, pp. 299–342].MATH
27.
Nakiboğlu, B., The Rényi Capacity and Center, IEEE Trans. Inform. Theory, 2019, vol. 65, no. 2, pp. 841–860; see also arXiv:1608.02424[cs.IT] (extended version).MathSciNetCrossRef
28.
Nakiboğlu, B., A Simple Derivation of the Refined Sphere Packing Bound under Certain Symmetry Hypotheses, Turkish J. Math., 2020, vol. 44, no. 3, pp. 919–948.MathSciNetCrossRef
29.
Gallager, R.G., A Simple Derivation of the Coding Theorem and Some Applications, IEEE Trans. Inform. Theory, 1965, vol. 11, no. 1, pp. 3–18.MathSciNetCrossRef
30.
Poltyrev, G.Sh., Random Coding Bounds for Discrete Memoryless Channels, Probl. Peredachi Inf., 1982, vol. 18, no. 1, pp. 12–26 [Probl. Inf. Transm. (Engl. Transl.), 1982, vol. 18, no. 1, pp. 9–21].MathSciNetMATH
31.
Blahut, R.E., Hypothesis Testing and Information Theory, IEEE Trans. Inform. Theory, 1974, vol. 20, no. 4, pp. 405–417.MathSciNetCrossRef
32.
Blahut, R.E., Information Bounds of the Fano–Kullback Type, IEEE Trans. Inform. Theory, 1976, vol. 22, no. 4, pp. 410–421.MathSciNetCrossRef
33.
Blahut, R.E., Principles and Practice of Information Theory, Reading, MA: Addison-Wesley, 1987.MATH
34.
Vazquez-Vilar, G., Martinez, A., and Guillén i Fàbregas, A., A Derivation of the Cost-Constrained Sphere-Packing Exponent, in Proc. 2015 IEEE Int. Symp. on Information Theory (ISIT’2015), Hong Kong, China, June 14–19, 2015, pp. 929–933.
35.
Dudley, R.M., Real Analysis and Probability, Cambridge: Cambridge Univ. Press, 2002.CrossRef
36.
van Erven, T. and Harremoës, P., Rényi Divergence and Kullback–Leibler Divergence, IEEE Trans. Inform. Theory, 2014, vol. 60, no. 7, pp. 3797–3820.MathSciNetCrossRef
37.
Rudin, W., Principles of Mathematical Analysis, New York: McGraw-Hill, 1976, 3rd ed.MATH
38.
39.
40.
Dalai, M., Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels, IEEE Trans. Inform. Theory, 2013, vol. 59, no. 12, pp. 8027–8056.MathSciNetCrossRef
41.
Dalai, M., Some Remarks on Classical and Classical-Quantum Sphere Packing Bounds: Rényi vs. Kullback–Leibler, Entropy, 2017, vol. 19, no. 7, p. 355 (11 pp.).MathSciNetCrossRef
42.
Dalai, M. and Winter, A., Constant Compositions in the Sphere Packing Bound for Classical-Quantum Channels, IEEE Trans. Inform. Theory, 2017, vol. 63, no. 9, pp. 5603–5617.MathSciNetMATH
43.
Cheng, H.-C. and Hsieh, M.H., Moderate Deviation Analysis for Classical-Quantum Channels and Quantum Hypothesis Testing, IEEE Trans. Inform. Theory, 2018, vol. 64, no. 2, pp. 1385–1403.MathSciNetCrossRef
44.
Cheng, H.-C., Hsieh, M.H., and Tomamichel, M., Quantum Sphere-Packing Bounds with Polynomial Prefactors, IEEE Trans. Inform. Theory, 2019, vol. 65, no. 5, pp. 2872–2898.MathSciNetCrossRef
45.
Altuğ, Y. and Wagner, A.B., Refinement of the Random Coding Bound, IEEE Trans. Inform. Theory, 2014, vol. 60, no. 10, pp. 6005–6023.MathSciNetCrossRef
46.
Scarlett, J., Martinez, A., and Guillén i Fàbregas, A., Mismatched Decoding: Error Exponents, Second-Order Rates and Saddlepoint Approximations, IEEE Trans. Inform. Theory, 2014, vol. 60, no. 5, pp. 2647–2666.MathSciNetCrossRef
47.
Honda, J., Exact Asymptotics for the Random Coding Error Probability, in Proc. 2015 IEEE Int. Symp. on Information Theory (ISIT’2015), Hong Kong, China, June 14–19, 2015, pp. 91–95.
48.
Burnashev, M.V. and Holevo, A.S., On the Reliability Function for a Quantum Communication Channel, Probl. Peredachi Inf., 1998, vol. 34, no. 2, pp. 3–15 [Probl. Inf. Transm. (Engl. Transl.), 1998, vol. 34, no. 2, pp. 97–107].MathSciNetMATH
49.
Telatar, E., Capacity of Multi-antenna Gaussian Channels, Eur. Trans. Telecommun., 1999, vol. 10, no. 6, pp. 585–595.MathSciNetCrossRef
50.
Vu, M., MISO Capacity with Per-Antenna Power Constraint, IEEE Trans. Commun., 2011, vol. 59, no. 5, pp. 1268–1274.CrossRef
51.
Cao, P.L., Oechtering, T.J., Schaefer, R.F., and Skoglund, M., Optimal Transmit Strategy for MISO Channels with Joint Sum and Per-Antenna Power Constraints, IEEE Trans. Signal Process., 2016, vol. 64, no. 16, pp. 4296–4306.MathSciNetCrossRef
52.
Loyka, S., The Capacity of Gaussian MIMO Channels under Total and Per-Antenna Power Constraints, IEEE Trans. Commun., 2017, vol. 65, no. 3, pp. 1035–1043.CrossRef
53.
Cheng, H.-C. and Nakiboğlu, B., Refined Strong Converse for the Constant Composition Codes, in Proc. 2020 IEEE Int. Symp. on Information Theory (ISIT’2020), Los Angeles, CA, June 21–26, 2020, pp. 2149–2154.
54.
Yang, W., Fading Channels: Capacity and Channel Coding Rate in the Finite-Blocklength Regime, PhD Thesis, Communication Systems Group, Dept. of Signals and Systems, Chalmers Univ. of Technology, Gothenburg, Sweden, 2015.
Metadaten
Titel
The Sphere Packing Bound for Memoryless Channels
verfasst von
B. Nakiboğlu
Publikationsdatum
01.07.2020
Verlag
Pleiades Publishing
Erschienen in
Problems of Information Transmission / Ausgabe 3/2020
Print ISSN: 0032-9460
Elektronische ISSN: 1608-3253
DOI
https://doi.org/10.1134/S0032946020030011

Weitere Artikel der Ausgabe 3/2020

Problems of Information Transmission 3/2020 Zur Ausgabe

Automata Theory

Gaussian Two-Armed Bandit: Limiting Description

Coding Theory

On Geometric Goppa Codes from Elementary Abelian p-Extensions of

Coding Theory

Symmetric Block Designs and Optimal Equidistant Codes

Large Systems

Research on Fractional Critical Covered Graphs

Neuer Inhalt

    Bildnachweise