# Multi-Dimensional Sparse-Coded Ambient Backscatter Communication for Massive IoT Networks
## 3 Sparse Codes
### Design of Factor Graph  
The role of the constellation mapping function is to modulate \(M\)-ary data into \(K_{1}\geq\log_{2}M\)-dimensional symbols which can easily be generated by simply switching \(\tilde{M}\) load impedances at \(N\) tags. In the next step, \(K_{1}\)-dimensional symbols are spread to \(K\)-dimensional sparse codewords to minimize the MAI among \(N\) tags and to enable NOMA. To do so, we should determine the system parameters \(K_{1}\) and \(K\) to meet the following condition as  
\[\log_{2}M\leq K_{1}\leq K\leq N,\quad\text{where }\binom{K}{K_{1}}\geq N. \tag{17}\]  
Given \(K_{1}\) and \(K\) satisfying the above condition, we can design a factor graph \(\tilde{\mathbf{G}}_{0}=\{\tilde{g}_{0,k,n}\}_{\forall k,n}\in\mathbb{B}^{K \times N}\) with \(K_{1}\) non-zero elements in each column as depicted in Figure 6. For instance, the conventional TD-AmBC can be considered as a special case of sparse codes with \(K_{1}=1\) with orthogonal allocation of non-zeros in codebooks, which is not spectrally efficient as the tags backscatter for a small fraction of time only and remain idle for the rest of time. On the other hand, for \(K_{1}\geq 2\), there are \(K_{1}\)-fold increase in the duty cycle of tags \(D=\frac{K_{1}}{K}\) and \(N_{1}=\frac{NK_{1}}{K}\)-fold increase in the spectral efficiency (i.e., there are \(N_{1}\) non-zeros in each row (time slot)). It is noteworthy that prolonging the duty cycle of tags by increasing \(K_{1}\) can constitute the multi-dimensional signal space which is beneficial for achieving both diversity gain \(K_{1}\) for \(M=2\) or multiplexing gain \(V=\log_{2}M\) for \(M\geq 4\). In addition, since codebooks are generated with low-density (sparse), the length of codewords \(K\) can be decreased to overload a massive number of tags \(N\geq K\) for boosting the data rate of AmBC. As shown in the Figure 6, the time slots required for \(N=10\) tags can be compressed to \(K=5\), achieving the overloading gain \(\lambda=\frac{N}{K}=2\). However, the parameters \(K_{1}\) and \(K\) can degrade the energy harvesting efficiency of tags by controlling \(D\). As \(D\) increases, the tags should be activated for a long period of time when uploading their data to the reader, consuming more power at their RF circuits. Therefore, these parameters should be carefully determined to coordinate the communication range, data rate, energy harvesting efficiency of the AmBC system.  
Given \(N\), \(K_{1}\) and \(K\), the factor graph is formed to minimize the number of interfering tags in every time slot by designing the sparse factor graph matrix \(\tilde{\mathbf{G}}_{0}\). The optimization problem of \(\tilde{\mathbf{G}}_{0}\) can be formulated as [39]  
\[\min_{\tilde{\mathbf{G}}_{0}\in\mathbb{B}^{K\times N},\,\hat{d}>0} \max\sum_{n=1}^{N}\tilde{g}_{0,k,n}-\epsilon\hat{d}\] (18) s.t. \[\sum_{k=1}^{K}\tilde{g}_{0,k,n}=K_{1},\quad n=1,\cdots,N,\] \[\sum_{k=1}^{K}|\tilde{g}_{0,k,n_{1}}-\tilde{g}_{0,k,n_{2}}|\geq \hat{d},\quad\forall n_{1}\
eq n_{2},\quad n_{1},n_{2}=1,\cdots,N,\]  
where \(\epsilon>0\) is the penalty coefficient and \(\hat{d}\) the minimum Euclidean distance among column vectors in the matrix \(\tilde{\mathbf{G}}_{0}\). The near-optimal algorithm for design of the factor graph can be found in [39], and the codebooks \(\left\{\mathbf{B}_{0}(m)\right\}_{m\in\{1,\cdots,M\}}\) can be generated from the constellation mapping matrix \(\tilde{\mathbf{F}}\) and the factor graph \(\tilde{\mathbf{G}}_{0}\). Specifically, in the \(m\)-th codeword \(\mathbf{B}_{0}(m)=\{\tilde{b}_{0,k,n}(m)\}_{\forall k,n}\), the element \(\tilde{b}_{0,k,n}(m)\) can be calculated by  
\[\tilde{b}_{0,k,n}(m)=\begin{cases}\tilde{f}_{m}(k_{1}^{\prime}),&\quad\text{ if }\tilde{g}_{0,k,n}=1,\quad k_{1}^{\prime}=\sum_{k^{\prime}=1}^{k}\tilde{g}_{0,k^{ \prime},n},\\ 0,&\quad\text{otherwise}.\end{cases} \tag{19}\]