Achieving uniform side information gain with multilevel lattice codes over the ring of integers

Juliana G. F. Souza, and Sueli I. R. Costa · 2025

Read Achieving uniform side information gain with multilevel lattice codes over the ring of integers by Juliana G. F. Souza, and Sueli I. R. Costa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-14921.txt.

Introduction

Souza and Costa wrote a 2025 letter on index coding, where a broadcaster serves receivers who each already hold some messages as side information. Good codes cut what the sender transmits by using what receivers know. The pair build a scheme from a layered lattice construction over the integers, with a remainder-style encoding, named CRT lattice index coding. They derive a ceiling for the gain side information can give and state when it is the same for every receiver, a trait called uniform gain. Examples show the scheme in action.

Catalog record

CREATORJuliana G. F. Souza, and Sueli I. R. Costa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-14921

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Achieving uniform side information gain with multilevel lattice codes over the ring of integers Juliana G. F. Souza, and Sueli I. R. Costa Abstract The index coding problem aims to optimise broadcast communication by taking advantage of receiver-side information to improve transmission efficiency. In this letter, we explore the application of Construction π A \pi_{A} lattices to index coding. We introduce a coding scheme, named CRT lattice index coding , using Construction π A \pi_{A} over ℤ \mathbb{Z} to address the index coding problem. It is derived an upper bound for side information gain of a CRT lattice index code and conditions for the uniformity of this gain. The efficiency of this approach is shown through theoretical analysis and code design examples. I Introduction The index coding problem, introduced by Birk and Kol [ 1 ] , exploits receiver side information to optimize broadcast efficiency. It aims to encode messages, meeting all receiver’s demands at the highest possible rate. Researchers have studied the capacity region of the AWGN broadcast channel [ 2 , 3 ] , and the design of codes that exploit side information for transmission gains [ 4 , 5 , 6 , 7 ] in the scenario where the transmitter does not have knowledge of each receiver side information. Lattice-based strategies have been effective in communication scenarios, including achieving AWGN channel capacity and good performance on wiretap transmissions, and relay networks, among others. The use of lattices for index coding was first proposed by Natarajan et al. [ 5 , 8 ] , where nested lattice codes over principal ideal domains (PIDs) were considered, assuming that all receivers demand all messages. Extensions of this approach include lattices from algebraic number fields [ 6 ] and from cyclic division algebras [ 7 ] . In this letter, we propose an index coding scheme using Construction \pi_{A} lattices over \mathbb{Z} , called CRT lattice index coding , focusing on code designs to provide uniform side information gain. It is somehow natural to explore this construction in this context, as mentioned in [ 9 , 10 , 11 ] . Construction \pi_{A} lattice is a special case of Construction A from codes over rings that can be factorised as a product of rings by the Chinese Remainder Theorem (CRT), providing lattice codes with the benefit of multilevel encoding and multistage decoding with reduced decoding complexity. The remainder of this work is organised as follows. Section II covers preliminaries on lattices and lattice codes. We introduce the index coding problem in Section III. In Section IV it is proposed the CRT lattice index coding construction and derived an upper bound for its side information gain when this construction is obtained from same rank codes. Section V presents cases in which uniform side information gain is achieved. Conclusions and perspectives are described in Section VI. II Preliminaries II-A Lattices and lattice codes We summarise next some concepts and properties related to lattice codes [ 12 , 13 ] . In this work, the distance and norm considered are Euclidean. A lattice \Lambda is a discrete subset of \mathbb{R}^{n} generated by all linear integer combinations of a set of independent vectors \{v_{1},\ldots,v_{m}\} . m is called the lattice rank and we deal here only with full-rank lattices ( m=n ). A matrix B whose columns are the vectors v_{i} is called a generator matrix of \Lambda . The volume of a (full-rank) lattice is given by \text{vol}(\Lambda)=|\det(B)| . Given a point z\in\mathbb{R}^{n} and a lattice \Lambda\subset\mathbb{R}^{n} , we define Q_{\Lambda}(z) as the closest lattice point to z , also called the quantization of z , Q_{\Lambda}(z)=x\in\Lambda;\ ||z-x||\leq||z-y||\quad\forall y\in\Lambda, (1) and ties must be chosen. The Voronoi region of a lattice \Lambda , \mathscr{V}_{\Lambda} , is the set of all points in \mathbb{R}^{n} that are mapped to the origin under Q_{\Lambda} , \mathscr{V}_{\Lambda}(0)=\mathscr{V}_{\Lambda}=\{z\in\mathbb{R}^{n};\|z\|\leq\|z-y\|\ \forall y\in\Lambda\}. Considering a sublattice \Lambda^{\prime}\subset\Lambda , the set \Lambda/\Lambda^{\prime} is called a Voronoi constellation and it is associated with the elements of \Lambda inside the Voronoi region of \Lambda^{\prime} . The minimum distance d_{\text{min}}(\Lambda) and the centre density \delta(\Lambda) of a lattice \Lambda are defined, respectively, as d_{\text{min}}(\Lambda)=\min_{0\neq x\in\Lambda}||x||\ \ \text{and}\ \ \delta(\Lambda)=\dfrac{\left(d_{\min}(\Lambda)/2\right)^{n}}{\text{vol}(\Lambda)}. (2) The kissing number , K(\Lambda) , of a lattice is the number of lattice points having the minimum non-vanishing norm. A linear code over \mathbb{Z}_{q} , the ring of integers modulo q , is a subset \mathscr{C}\subset\mathbb{Z}_{q}^{n} which is an additive subgroup of \mathbb{Z}_{q}^{n} . The rank of a code, \text{rank}(\mathscr{C}) , is the minimum number of generators of \mathscr{C} . For q=p (prime number) a linear code is a vector subspace of dimension k\leq n , called a (n,k)- linear code. A code \mathscr{C}\subset\mathbb{Z}_{q}^{n} is said to be a free linear code if it has a basis over \mathbb{Z}_{q} . A method for obtaining lattices from linear codes is the Construction A , [ 12 , 13 ] . Consider the mapping \rho:\mathbb{Z}\rightarrow\mathbb{Z}_{q} , the natural modulo q reduction and \sigma:\mathbb{Z}_{q}\rightarrow\mathbb{Z} , the standard inclusion map, extended to vectors component-wise. Given a linear code \mathscr{C}\subset\mathbb{Z}_{q}^{n} , the Construction A lattice associated with \mathscr{C} , denoted by \Lambda_{A}(\mathscr{C}) , is defined as \Lambda_{A}(\mathscr{C})=\rho^{-1}(\mathscr{C})=\sigma(\mathscr{C})+q\mathbb{Z}^{n}. (3) It is shown that \Lambda_{A}(\mathscr{C}) is a full-rank lattice, q\mathbb{Z}^{n}\subset\Lambda_{A}(\mathscr{C})\subset\mathbb{Z}^{n} , \text{vol}(\Lambda)=q^{n}/|\mathscr{C}| , where |\mathscr{C}| is the cardinality of the code \mathscr{C} and d_{\min}(\Lambda_{A}(\mathscr{C}))=\min\{d_{\min}(\mathscr{C}),q\} , [ 13 ] . Huang and Narayanan introduced Construction \pi_{A} lattices, in [ 9 ] . It is a special case of Construction A and generates lattices over various integer rings.It relies on a ring isomorphism given by the Chinese Remainder Theorem (CRT) [ 9 , (23)] , [ 6 , 7 , 11 ] . Definition 1 (Construction \pi_{A} lattice, [ 9 ] ) . Let p_{1},\ldots,p_{r} be distinct primes and let q=\prod_{j=1}^{r}p_{j} . Consider l_{j},n to be integers such that l_{j}\leq n and let G_{j} be a generator matrix of an (n,l_{j}) -linear code over \mathbb{Z}_{p_{j}} for j\in\{1,\ldots,r\} . Construction \pi_{A} consists of the following steps: 1) Define the discrete codebooks \mathscr{C}_{j}=\{\mathbf{x}=G_{j}\cdot u:u\in\mathbb{Z}_{p_{j}}^{l_{j}}\} for j\in\{1,\ldots,r\} . 2) Construct \mathscr{C}=\phi^{-1}(\mathscr{C}_{1}\times\ldots\times\mathscr{C}_{r}) where \phi^{-1}:\mathbb{Z}_{p_{1}}^{n}\times\cdots\times\mathbb{Z}_{p_{r}}^{n}\rightarrow\mathbb{Z}_{q}^{n} is the CRT ring isomorphism. 3) Tile \mathscr{C} to the entire \mathbb{R}^{n} to form \Lambda_{\pi_{A}}(\mathscr{C})=\sigma(\mathscr{C})+q\mathbb{Z}^{n} . Due to their multilevel structure, Construction \pi_{A} lattices allow multistage decoding, where each class representative is decoded sequentially at each level. III Problem Statement Consider a scenario with r independent messages w_{1},\ldots,w_{r} from alphabets W_{1},\ldots,W_{r} . These messages are jointly encoded into a codeword x=f(w_{1},\ldots,w_{r})\in\mathscr{C} , where \mathscr{C}\subset\mathbb{R}^{n} is an n -dimensional constellation. The received signal at receiver l , l=1,...,L is y_{l}=x+z_{l},\quad z_{l}\sim N(0,\sigma^{2}). Each receiver l knows a subset w_{S_{l}}=\{w_{j}:j\in S_{l}\} of the messages, with S_{l}\subset\{1,\ldots,r\} , and estimates (\hat{w}_{1}^{(l)},\ldots,\hat{w}_{r}^{(l)}) of (w_{1},\ldots,w_{r}) using y_{l} and w_{S_{l}} . This setup is illustrated in Figure 1 . The rates of the j -th message, the side information rate, and the transmission rate are, R_{j}=\frac{1}{n}\log_{2}|W_{j}|\ \text{bits/dim},\quad R_{S_{l}}=\sum_{j\in S_{l}}R_{j}\ \text{bits/dim},\quad R=\sum_{j=1}^{r}R_{j}\ \text{bits/dim}, respectively. Let \mathscr{C}_{S_{l}} denote the subcode of \mathscr{C} restricted to w_{S_{l}} . The minimum Euclidean distance in \mathscr{C} is denoted by d_{0} , and in \mathscr{C}_{S_{l}} by d_{S_{l}} . The squared minimum distance gain for w_{S_{l}} is defined as, 10\log_{10}\left(d_{S_{l}}^{2}/d_{0}^{2}\right)\ \text{dB}. The side information gain at receiver l is given by [ 5 , 10 ] , \Gamma(\mathscr{C},S_{l})=\frac{10\log_{10}\left(d_{S_{l}}^{2}/d_{0}^{2}\right)}{R_{S_{l}}}\

Read the complete text