# Probabilistic Shaping for Finite Blocklengths: Distribution Matching and Sphere Shaping
## 4 Distribution Matching and Sphere Shaping Architectures
### Sphere Shaping Architecture (Indirect Method)
Sequences on the same shell can be sorted, e.g., lexicographically. To this end, a trellis which is different from that of ESS is constructed [23; 65]. Based on this trellis, two different indexing algorithms are proposed in [23]. The first one, (Algorithm 1 in [23]), which was proposed around the same time as ESS [22], has performance and complexity similar to ESS. The second one, (Algorithm 2 in [23]), which is the well-known shell mapping (SM), is based on the divide-and-conquer (D&C) principle, and enables a tradeoff between the computational and storage complexities (Section 4.3 in [10]). The D&C principle was used to enumerate sequences from the Leech lattice earlier in [59]. The basic principle is to successively divide an \(n\)-dimensional indexing problem into two \(n/2\)-dimensional problems, creating a \(\log_{2}n\)-step operation. Consequently, SM demands the storage of a \((\log_{2}n+1)\)-by-\(L\) matrix, where each element is again at most \((k+1)\)-bit long. The required storage and computational complexity of SM is discussed in Section 6. In their initial proposals, shaping matrices of ESS [22], SM [23] and (Algorithm 1 in [23]) are computed with full-precision (FP). To decrease the required storage for these algorithms, a bounded-precision (BP) implementation method is proposed in [65]. The idea is that any number can be expressed in base-2 as \(m\cdot 2^{p}\). Here \(m\) and \(p\) are called the mantissa and the exponent, stored using \(n_{\text{m}}\) and \(n_{\text{p}}\) bits, respectively. Then each number in a shaping matrix, i.e., in the trellis, is rounded down to \(n_{\text{m}}\) bits after its computation, and stored in the form \((m,p)\). The invertibility of ESS and SM functions is preserved with this approach [65]. We note that the BP implementation can also be used to realize (Algorithm 1 in [23]). The BP implementation decreases the memory required to store an element of the shaping trellis from \((k+1)\) bits to \(n_{\text{m}}+n_{\text{p}}\) bits. Typical values of \(n_{\text{m}}\) and \(n_{\text{p}}\) are a few bytes. The required storage and the computational complexity of BP implementation is discussed in Section 6. The disadvantage of this approximation is that the numbers in the trellis, and thus, the number of represented sequences decreases, causing a rate loss. However, this rate loss is shown to be upper-bounded by \(-\log_{2}(1-2^{1-n_{\text{m}}})\) bit/1-D [65]. **Example 7** (Bounded-precision rate loss). : _If the shaping set \(\mathcal{A}^{\bullet}\) in Example 6 is constructed with BP using \(n_{m}=9\) bit mantissa and \(n_{p}=7\) bit exponents, the resulting rate loss is upper-bounded by 0.0056 bit/1-D. For ESS and SM, the actual rate losses are 0.0021 and 0.0003 bit/1-D, respectively. Since the shaping rate with FP was \(R_{s}=1.7538\), these rate losses keep \(R_{s}>1.75\), and consequently, keep \(k=112\). Therefore, we claim that when more than a few bytes are used to store mantissa, BP rate loss is smaller than the loss due to the rounding operation in (8). Consequently, the operational rate \(k/n\) is not affected. However, the required memory to store an element of the shaping matrix drops from \((k+1)=113\) bits to \(n_{m}+n_{p}=16\) bits._  
Both ESS and SM index the same set of sequences for fixed \(n\), \(\mathcal{A}\) and \(E^{\bullet}\). However, the way they order sequences is different. Due to the round-down operation in (8), only the sequences with indices smaller than \(2^{k}\) are actually utilized. The remaining ones, i.e., the ones at the end of the ordered list, are unused. For SM, all these sequences have the highest possible energy \(E^{\bullet}\). On the other hand for ESS, these sequences are at the end of the lexicographical list and are not necessarily from the outermost shell. Thus operationally, average symbol energy of SM is no greater than that of ESS, for a fixed set of parameters. This difference could be important for ultra short blocklengths, however, for blocklengths larger than a few dozens, it becomes insignificant.