# Probabilistic Shaping for Finite Blocklengths: Distribution Matching and Sphere Shaping
## 4 Distribution Matching and Sphere Shaping Architectures
### Sphere Shaping Architecture (Indirect Method)  
In this section, a review of SpSh algorithms is provided. All ensuing algorithms target a certain rate, i.e., the number of unique output sequences, rather than a PMF. To this end, for a given \(\mathcal{A}\), \(n\) and target \(k\), the maximum-energy constraint \(E^{\bullet}\) is selected as the minimum value such that the corresponding set \(\mathcal{A}^{\bullet}\), as defined in (4), satisfies \(|\mathcal{A}^{\bullet}|\geq 2^{k}\). This set consists of all \(2^{m}\)-ASK amplitude lattice points on the surface of or inside the \(n\)-sphere of square radius \(E^{\bullet}\) as shown in Figure 6. (We use \"\(2^{m}\)-ASK amplitude lattice\" for the \(n\)-fold Cartesian product of \(\{1,3,\ldots,2^{m}-1\}\) with itself, i.e., \(\mathcal{A}^{n}\).) We note that possible sequence energy values for these points, i.e., squared radii of the \(n\)-dimensional shells that the sequences are located on, are \(\{n,n+8,\ldots,E^{\bullet}\}\), and the maximum-energy constraint can be written as  
\[E^{\bullet}=n+8(L-1) \tag{15}\]  
where \(L\) denotes the number of these \(n\)-dimensional shells (Since the AWGN channel capacity in (1) is computed starting with the assumption that the signal points outside the \(n\)-sphere of squared radius \(nP\) cannot be transmitted, i.e., the average power constraint, one could argue that referring to \"sphere shaping\" as the \"indirect\" method is inaccurate. However, this constraint only prevents the use of the signal points outside the sphere, and does not prescribe the use of all the ones inside. Therefore, we choose to follow the nomenclature introduced by [PERSON] and [PERSON] in [19], which formulates the problem as \"achieving the capacity of a channel of which the capacity-achieving input distribution is Gaussian\"). **Remark 2**. : _We see from the sphere-hardening result discussed, e.g., by [PERSON] and [PERSON] in (Section 5.5 in [98]), that \(E^{\bullet}\approx nE\) for large \(n\). Following [PERSON] et al. (Section III-A [23]) and approximating the required average energy to transmit \(R\) bit/I-D by \(c2^{2R}\), we can write \(E^{\bullet}\approx nc2^{2R}\) where \(c\) is some constant. Therefore, for a fixed rate \(R\) and for large \(n\), we assume that \(L\) in (15) depends linearly on \(n\)._  
**Example 6** (Sphere shaping). : _The sphere shaping set \(\mathcal{A}^{\bullet}\subset\mathcal{A}^{n}\) for the parameters \(n=64\), \(\mathcal{A}=\{1,3,5,7\}\) and \(E^{\bullet}=768\), i.e., \(L=89\), has the shaping rate \(R_{s}=1.7538\) bit/I-D. The input length of the corresponding amplitude shaper is \(k=112\) bits. The average PMF is \(P_{A}(a)=[0.42,0.32,0.18,0.08]\) over \(\mathcal{A}\), where the average energy per dimension is \(E=11.6316\)._  
In the following, we explain two different algorithms to realize SpSh: Enumerative sphere shaping (ESS) and shell mapping (SM). Provided with identical parameters, these two address the same set \(\mathcal{A}^{\bullet}\) of sequences where the difference is in the bits-to-amplitudes mapping. ESS starts from the assumption that the energy-bounded amplitude sequences, i.e., \(a^{n}\in\mathcal{A}^{\bullet}\), can be ordered lexicographically. Therefore, the index of an amplitude sequence is defined to be the number of sequences which are lexicographically smaller. To represent \(n\)-amplitude sequencesinside a sphere, an energy-bounded enumerative amplitude trellis is constructed (Section III-B in [48]). Operating on this enumerative trellis, \(n\)-step recursive algorithms are devised to realize the lexicographical index-sequence mapping in an efficient manner [22; 65]. These algorithms demand the storage of an \((n+1)\)-by-\(L\) matrix, i.e., the trellis, where each element can be up to \((k+1)\)-bit long. The required storage and computational complexity of ESS is discussed in Section 6. Another way of ordering \(n\)-amplitude sequences inside a sphere is to sort them based on their energy, i.e., based on the index of the \(n\)-dimensional shell that they are located on.