Abstract
Consider a wireless network where several users are transmitting simultaneously. Each receiver observes a linear combination of the transmitted signals, corrupted by random noise, and attempts to recover the codewords sent by one or more of the users. Within the context of network information theory, it is of interest to determine the maximum possible data rates as well as efficient strategies that operate at these rates. One promising recent direction has shown that if the users utilize a lattice-based strategy, then a receiver can recover an integer-linear combination of the codewords at a rate that depends on how well the real-valued channel gains can be approximated by integers. In other words, the performance of this lattice-based strategy is closely linked to a basic question in Diophantine approximation. This chapter provides an overview of the key findings in this emerging area, starting from first principles, and expanding towards state-of-the art results and open questions, so that it is accessible to researchers with either an information theory or Diophantine approximation background.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The 1 + term from the capacity expression \(C=\frac {1}{2}\log (1+P)\) is lost to compensate for the dependence between x k and \({\mathbf e}_k={\mathbf x}_{k}-\tilde {\mathbf {y}}_k\). However, if we set H = 1 to model a point-to-point AWGN channel, we find that (2.15) is equal to the AWGN capacity \(1/2 \log (1 + P)\) as desired. See [36], [10, Lemma 2] for more details.
- 2.
Specifically, it can be shown that there is a choice of rates R 1, …, R K satisfying \(\sum _k R_k = \frac {1}{2}\log {\mathrm {det}}( {\mathbf I} + P {\mathbf H}^{\mathsf T} {\mathbf H})\) that satisfies the capacity region constraints from Theorem 2.2 and any choice of rates with a higher sum rate \(\sum _k R_k > \frac {1}{2}\log {\mathrm {det}}( {\mathbf I} + P {\mathbf H}^{\mathsf T} {\mathbf H})\) will violate these capacity constraints.
- 3.
- 4.
Up to a small correction term, due to the fact that the effective user x interference,k has power (K − 1)P instead of P. See [31] for more details.
References
Adiceam, F., Beresnevich, V., Levesley, J., Velani, S., Zorin, E.: Diophantine approximation and applications in interference alignment. Adv. Math. 302, 231–279 (2016)
Ahlswede, R.: Multi-way communication channels. In: Proceedings of the 2nd International Symposium on Information Theory, Prague, pp. 23–52. Publishing House of the Hungarian Academy of Sciences, Hungarian (1971)
Arikan, E.: Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans. Inf. Theory 55(7), 3051–3073 (2009)
Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(1), 625–635 (1993)
Beresnevich, V., Bernik, V., Budarina, N.: Systems of small linear forms and Diophantine approximation on manifolds. Ar**v e-prints (2017). http://arxiv.org/abs/1707.00371
Berrou, C., Glavieux, A.: Near optimum error correcting coding and decoding: Turbo-codes. IEEE Trans. Commun. 44(10), 1261–1271 (1996)
Cadambe, V.R., Jafar, S.A.: Interference alignment and the degrees of freedom for the K-user interference channel. IEEE Trans. Inf. Theory 54(8), 3425–3441 (2008)
Cadambe, V.R., Jafar, S.A.: Interference alignment and the degrees of freedom of wireless X networks. IEEE Trans. Inf. Theory 55(5), 2334–2344 (2009)
Chung, S.Y., Forney, G.D., Richardson, T.J., Urbanke, R.: On the design of low-density parity-check codes within 0.0045 db of the Shannon limit. IEEE Commun. Lett. 5(2), 58–60 (2001)
Cioffi, J.M., Dudevoir, G.P., Eyuboglu, M.V., Forney, G.D.: MMSE decision-feedback equalizers and coding. I. Equalization results. IEEE Trans. Commun. 43(10), 2582–2594 (1995)
Cover, T., Thomas, J.: Elements of Information Theory, 2nd edn. Wiley-Interscience, Hoboken, (2006)
Domanovitz, E., Erez, U.: Outage probability bounds for integer-forcing source coding. In: Proceedings of the IEEE Information Theory Workshop (ITW 2017). Kaohsiung, Taiwan (2017)
Domanovitz, E., Erez, U.: Outage behavior of integer forcing with random unitary pre-processing. IEEE Trans. Inf. Theory 64(4), 2774–2790 (2018)
El Gamal, A., Kim, Y.H.: Network Information Theory. Cambridge University, Cambridge (2011)
Erez, U., Zamir, R.: Achieving \(\frac {1}{2}\log {(1 + \mbox{SNR})}\) on the AWGN channel with lattice encoding and decoding. IEEE Trans. Inf. Theory 50(10), 2293–2314 (2004)
Gallager, R.: Low-density parity-check codes. IRE Trans. Inf. Theory 8(1), 21–28 (1962)
Guess, T., Varanasi, M.K.: An information-theoretic framework for deriving canonical decision-feedback receivers in Gaussian channels. IEEE Trans. Inf. Theory 51(1), 173–187 (2005)
He, W., Nazer, B.: Integer-forcing source coding: Successive cancellation and source-channel duality. In: Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT), pp. 155–159 (2016)
Hussain, M., Levesley, J.: The metrical theory of simultaneously small linear forms. Functiones et Approximatio Commentarii Mathematici 48(2), 167–181 (2013)
Jafar, S.A.: Interference alignment—a new look at signal dimensions in a communication network. In: Foundations and Trends in Communications and Information Theory, vol. 7. NOW Publishers, Boston (2011)
Jafar, S.A., Shamai (Shitz), S.: Degrees of freedom region for the MIMO X channel. IEEE Trans. Inf. Theory 54(1), 151–170 (2008)
Liao, H.: Multiple access channels. Ph.D. thesis, University of Hawaii, Honolulu (1972)
Maddah-Ali, M.A., Motahari, A.S., Khandani, A.K.: Communication over MIMO X channels: Interference alignment, decomposition, and performance analysis. IEEE Trans. Inf. Theory 54(8), 3457–3470 (2008)
Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Cambridge, (2002)
Motahari, A.S., Oveis-Gharan, S., Maddah-Ali, M.A., Khandani, A.K.: Real interference alignment: Exploiting the potential of single antenna systems. IEEE Trans. Inf. Theory 60(8), 4799–4810 (2014)
Nazer, B., Gastpar, M.: Compute-and-forward: harnessing interference through structured codes. IEEE Trans. Inf. Theory 57(10), 6463–6486 (2011)
Nazer, B., Cadambe, V.R., Ntranos, V., Caire, G.: Expanding the compute-and-forward framework: unequal powers, signal levels, and multiple linear combinations. IEEE Trans. Inf. Theory 62(9), 4879–4909 (2016)
Niesen, U., Maddah-Ali, M.A.: Interference alignment: from degrees-of-freedom to constant-gap capacity approximations. IEEE Trans. Inf. Theory 59(8), 4855–4888 (2013)
Ordentlich, O., Erez, U.: Precoded integer-forcing universally achieves the MIMO capacity to within a constant gap. IEEE Trans. Inf. Theory 61(1), 323–340 (2015)
Ordentlich, O., Erez, U.: Integer-forcing source coding. IEEE Trans. Inf. Theory 63(2), 1253–1269 (2017)
Ordentlich, O., Erez, U., Nazer, B.: The approximate sum capacity of the symmetric K-user Gaussian interference channel. IEEE Trans. Inf. Theory 60(6), 3450–3482 (2014)
Richardson, T., Urbanke, R.: Modern Coding Theory. Cambridge University, Cambridge (2008)
Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423, 623–656 (1948)
Tse, D., Viswanath, P.: Fundamentals of Wireless Communication. Cambridge University Press, Cambridge (2005)
Wu, Y., Shamai (Shitz), S., Verdú, S.: Information dimension and the degrees of freedom of the interference channel. IEEE Trans. Inf. Theory 61(1), 256–279 (2015)
Zamir, R.: Lattice Coding for Signals and Networks. Cambridge University, Cambridge (2014)
Zhan, J., Nazer, B., Erez, U., Gastpar, M.: Integer-forcing linear receivers. IEEE Trans. Inf. Theory 60(12), 7661–7685 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Nazer, B., Ordentlich, O. (2020). Characterizing the Performance of Wireless Communication Architectures via Basic Diophantine Approximation Bounds. In: Beresnevich, V., Burr, A., Nazer, B., Velani, S. (eds) Number Theory Meets Wireless Communications. Mathematical Engineering. Springer, Cham. https://doi.org/10.1007/978-3-030-61303-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-61303-7_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-61302-0
Online ISBN: 978-3-030-61303-7
eBook Packages: EngineeringEngineering (R0)