# Trellis Tone Modulation Multiple-Access for Peer Discovery in D2D Networks
## 3 Trellis Tone Modulation Multiple-Access
### Overview of Trellis Tone Modulation  
The modulation technique of TTMMA is introduced in this section. First, let \(\mathbf{w}=(w_{1},w_{2},\ \cdots,\ w_{L})\) be a binary discovery message of length \(L\). The message includes the parity of cyclic redundancy check (CRC) codes. Each UE uses an OFDM resource grid that consists of \(M\) subcarriers and \(N\) symbols for the transmission of the discovery message, where the \(M\times N\) resource grid is called a discovery resource unit (DRU). The discovery signal of UE \(U\) generated from \(\mathbf{w}\) is then represented by a \(M\times N\) matrix \(\mathbf{X}=[\mathbf{x}_{1},\ldots,\mathbf{x}_{N}]\), where \(\mathbf{x}_{k}\) is the \(\kappa\)-th column vector of \(\mathbf{X}\). Each column of \(\mathbf{X}\) indicates the frequency domain representation of the corresponding OFDM symbol generated from UE \(U\). Since we use the single-tone transmission, each column of \(\mathbf{X}\) has a Hamming weight of 1. The nonzero entries take the value of \(\sqrt{P}\), where \(P\) is symbol power of transmission. Let an \(N\)-tuple \(\mathbf{t}=(t_{1},\ldots,t_{N})\) be the sequence of tone index, that is corresponding to the index of the nonzero entry in each column of \(\mathbf{X}\). The signal \(\mathbf{X}\) is determined if and only if \(\mathbf{t}\) is determined. The message is fragmented into \(N\) parts as \(\mathbf{w}=(\mathbf{w}_{1}:\mathbf{w}_{2}:\ldots:\mathbf{w}_{N})\) where \(\mathbf{w}_{1}\) is a \(b_{0}\)-tuple and others are \(b\)-tuples. The first tone index \(t_{1}\) is determined by first \(b_{0}\) bits, \(\mathbf{w}_{1}\). The consecutive tone indices are determined by the recursive relation. \[t_{k}=f_{T}(t_{k-1},\mathbf{w}_{k}),\ 2\leq k\leq N \tag{1}\]  
where \(f_{T}:\{1,2,\ldots,N\}\times\{0,1\}^{b}\rightarrow\{1,2,\ldots,N\}\) is called the tone transition function. Note \(N=\frac{L-b_{0}}{b}+1\). Let us regard the tone indices as the states of the modulator. The tone transition function \(f_{T}(\cdot)\) is fully characterized by a trellis diagram; therefore, we refer to our modulation scheme as a trellis tone modulation (TTM). We determine the trellis diagram by its incident matrix called the trellis matrix. The trellis matrix \(\mathbf{T}= \begin{bmatrix}t_{ij}\end{bmatrix} \in[0,1]^{M\times M}\) is a binary matrix in which the number of rows and columns is equal to \(M\). The number of \(1\)s in each row and the number of \(1\)s in each column are all equal to \(d\) and \(d=2^{b}\) for a positive integer \(b\). Ones in \(\mathbf{T}\) indicate a possible transition from the state of the column index to the state of the row index. If \(t_{p,q}=1\) and state \(q\) in the pre-state set and state \(p\) in the post-state set are then connected by an edge in the trellis diagram. The row and column weight \(d\) of \(\mathbf{T}\) is referred to as the degree of the trellis diagram. Since the degree \(d=2^{b}\), \(b\) bits can be encoded to the \(d\) state transitions via the corresponding edges, the trellis diagram can be regarded as a directional bipartite graph that we would call the \"trellis graph\". Figure 2 exhibits an example of a trellis matrix and the corresponding trellis diagram, where \(M\) is 12 and \(d\) is 4. The number of states \(M\) and the degree \(d\) of the trellis diagram are design parameters. The degree \(d\) is less than or equal to the number of states \(M\). If \(d\) is larger, the trellis conveys more message bits and the transmission efficiency is increased. However, the demodulation complexity also increases. Therefore, a tradeoff occurs between the transmission or bandwidth efficiency and the demodulation complexity and the parameters are determined in order to meet the system requirements. When constructing a trellis matrix using predetermined design parameters, the length of the cycle should be maximized as much as possible in order to improve demodulation performance.