ספר חדש של פרופ' רם זמיר

הספר מסכם תקופת מחקר של מעל עשרים שנה, והרבה חוקרים מהארץ (ובפרט מאוניברסיטת תל אביב) תרמו לרעיונות ולתוצאות שמופיעים בו: מאיר פדר, גרגורי פולטירב, סימון ליצין, שלמה שמאי, אורי ארז, יובל קוכמן, טל פילוסוף, אמיר אינגבר ועוד רבים. התיכנות והציורים נעשו על ידי עילי ביסטריץ.

Lattice Coding for Signals and Networks

A Structured Coding Approach to Quantization, Modulation and Multi-user Information Theory

Ram Zamir, Cambridge University Press, August 2014

Unifying information theory and digital communication through the language of lattice codes, this book provides a detailed overview for students, researchers and industry practitioners.

It covers classical work by leading researchers in the field of lattice codes and complementary work on dithered quantization and infinite constellations, and then introduces the more recent results on “algebraic binning” for side-information problems, and linear/lattice codes for networks. It shows how high-dimensional lattice codes can close the gap to the optimal information theoretic solution, including the characterization of error exponents.

The solutions presented are based on lattice codes, and are therefore close to practical implementations, with many advanced setups and techniques, such as shaping, entropy coding,

side-information and multi-terminal systems. Moreover, some of the network setups shown demonstrate how lattice codes are potentially more efficient than traditional random coding solutions, for instance when generalizing the framework to Gaussian networks.

Interesting facts about lattices

The Nobel prize in chemistry in 2011 was awarded to the materials scientist Dan Shechtman, for his discovery in 1982 of quasicrystals. Until that time, everyone assumed that the atoms of an ordered solid material must form a threedimensional lattice. Materials with such a periodic structure are characterized by

a point-like diffraction pattern (i.e., a spatial Fourier series) which can only possess a 2nd, 3rd, 4th and 6th order symmetry; in contrast, the diffraction pattern of quasicrystals may have an unrestricted (typically 5th, 8th, 10th or 12th) order symmetry [158].

The seventeenth century astronomer Johannes Kepler conjectured that the FCC lattice forms the best sphere packing in three dimensions. While Gauss showed that no other lattice arrangement is better, the perhaps harder part – of excluding non-lattice arrangements – remained open until a full (computer-aided) proof was

given in 1998 by Hales.

The early twentieth century mathematician Hermann Minkowski used lattices to relate n-dimensional geometry with number theory – an area he called “the geometry of numbers” [36]. The Minkowski–Hlawka theorem (conjectured by Minkowski and proved by Hlawka in 1944) will play in Chapter 7 the role of Shannon’s random coding technique for proving the existence of “good” lattice codes.

Although lattice codes are not mentioned in Shannon’s work, he was certainly interested in sphere packing in high dimensions. 9 A story says that when David Slepian was about to retire from Bell Laboratories, he invited his close colleague AaronWyner to pick his favorite books from his office (before giving all of them to

his other lab mates).Wyner hesitated to take the offer before Slepian left, and when he finally came to make his choice most books were already taken. Yet one book on the shelf caught his eye, “An introduction to the geometry of N dimensions,” from 1929, by Sommerville. Opening it, Wyner found “C. E. Shannon” handwritten on the inside cover.

The relation between error-correcting codes, sphere packing and lattices (called construction A in this chapter) was studied by Leech and Sloane [153], and Conway and Sloane [49, chapter 5] in the 1970s and 1980s. They were motivated by several discoveries in the mathematical literature during the 1960s, like the 2m-dimensional

Barnes–Wall lattices and the ultradense Leech lattice in 24 dimensions; see the introduction by Forney [83]. Another notable motivation was provided by Ungerboeck’s invention of trellis-coded modulation by set partition in 1982 [259], and de Buda’s asymptotic analysis of lattice-based codes [57, 58] in the late 1970s and 1980s. In a series of works through the 1980s and 1990s, Forney [83, 84, 85, 86, 87, 94] established

tools to characterize and evaluate lattice codes, towards their implementation in digital communication.

ITU-T standard V.34 for voice-band telephone channel modems at 33.6 kbits per second uses a four-dimensional constellation selected from the D4 lattice; see the book by Tretter [256]. In the wireless communication domain (in standards like 802.11 [WiFi] and LTE), the set of possible coded signals corresponds to a finite segment from some high-dimensional lattice. Lattice (“algebraic”) codebooks are

also used for data compression; one recommendation for the ITU-T 729.1 speech coding

standard uses the Gosset lattice E8 as the codebook for code-excited linear prediction (CELP) [104, 144]. And obviously, the analog-to-digital (A/D) convertor at the interface of any signal compression scheme is a scalar lattice quantizer.

Some of the stronger public-key algorithms today use lattice-based cryptography, a concept that was initiated by Ajtai in 1996 [6]. Actual systems based on lattices were proposed immediately after Ajtai’s discovery by Goldreich et al. [108] and Hoffstein et al. [121] (the NTRU algorithm was patented in the late 1990s). These

systems rely on the asymmetry of coding and decoding, and on the difficulty of finding a “good” basis for a given lattice. It is easy to translate an integer vector to a lattice point and to perturb it slightly, but it is hard to find the closest lattice point to the perturbed vector – unless the decoder has a “good” basis; see the book by

Micciancio and Goldwasser [186] and the survey paper by Micciancio and Regev [188].