# Probabilistic Shaping for Finite Blocklengths: Distribution Matching and Sphere Shaping
## 6 Approximate Complexity Discussion
### Computational Complexity  
To comment on the computational complexity of the amplitude shaping algorithms, we will mainly consider the number of required arithmetic operations or computations of binomial coefficients (BC). The caveat here is that this approach only gives a rough estimate since the complexity of an operation depends heavily on the specific case that it is executed in. As an example, the seemingly simple operation of comparing the sizes of two numbers can be computationally challenging for large numbers. On the other hand the notoriously expensive division operation reduces to a simple shift in registers for some specific divisors. As explained in Section 6.2, AC-CCDM can be realized by splitting an interval into \(n_{a}\) per 1-D. This requires at most \(n_{a}\) multiplications. For each multiplication, one of the multipliers is found by a division using the statistics of the composition. Finally, at most \(n_{a}\) comparisons are carried out. We note that practical discussions such as \"numerical precision\", \"gaps between intervals\" and \"rescaling\" are omitted here, and the reader is referred to [56; 107; 106] for details. An approximate implementation of AC-CCDM is proposed in [68] where computations are realized with fixed-point operations. However, this implementation also requires multiplications,divisions and comparisons of large integer numbers. In addition, an implementation of AC-DM based on finite-precision arithmetic is provided in [72]. SR-CCDM, in contrast to AC, is based on calculating BCs. Thus, the number of required arithmetic operations depends a lot on how this computation is implemented or whether the BCs can be pre-computed and stored. When ESS and (Algorithm 1 in [23]) are implemented with FP, at most \(n_{a}\) additions (subtractions) of numbers from the corresponding shaping matrix are required per 1-D. These numbers are at most \(\lceil nR_{\mathrm{s}}\rceil\)-bit long. Thus, the computational complexity of these algorithms is \(\mathcal{O}(n)\). FP implementation of SM however, requires at most \(L\) multiplications of numbers from the shaping matrix. Therefore, the computational complexity of SM is \(\mathcal{O}(n^{3})\). **Example 12** (FP SpSh, computational complexity). : _Based on Example 6, at most four 113-bit additions per 1-D are necessary to realize ESS and (Algorithm 1 in [23]). On the contrary, for SM algorithms, at most 89 113-bit multiplications per 1-D are required._  
With BP approach, ESS and (Algorithm 1 in [23]) can be implemented with at most \(n_{a}\) additions of \(n_{\mathrm{m}}\)-bit numbers per 1-D. Then their computational complexity is \(\mathcal{O}(\log n)\). On the other side, BP SM can be realized with at most \(L\) multiplications of \(n_{\mathrm{m}}\)-bit numbers per 1-D. Therefore, the complexity of SM is now \(\mathcal{O}(n\log^{2}n)\). **Example 13** (BP SpSh, computational complexity). : _When Example 6 is now constructed with \(n_{m}=9\) and \(n_{p}=7\), ESS and (Algorithm 1 in [23]) require at most four 9-bit additions per 1-D. Correspondingly, if SM is realized with \(n_{m}=6\) and \(n_{p}=7\), at most 89 6-bit multiplications are necessary per 1-D._  
Table 3 summarizes serialism, required storage and computational complexity of discussed shaping algorithms as classified in Figure 1. The main conclusion from Table 3 is that for DM, AC and SR provide a tradeoff between serialism and computational complexity. However, we note that SR can only be used for binary-output DM. On the other hand for SpSh, SM and ESS create a tradeoff between required storage and computational complexity. The selection among different algorithms then depends on the actual resources that are available for shaping in practice, and thus, we refrain from making definitive suggestions here. We conclude this paper by showing in Figure 12, the maximum required storage versus maximum number of computations required to implement BP and FP SpSh, and BP AC-CCDM (BP AC-CCDM refers to the finite-precision implementation of AC-CCDM as discussed in [72]).