# Probabilistic Shaping for Finite Blocklengths: Distribution Matching and Sphere Shaping
## 6 Approximate Complexity Discussion
### Storage Requirements  
AC-CCDM, which employs an extension of [53] to nonbinary-output, associates an interval in \([0,1)\) to each binary input sequence and to each constant composition amplitude sequence (Section IV in [52]). In simplified terms, the final interval is computed by recursively splitting the initial interval into \(n_{a}\) subintervals. The algorithm only requires the storage of the interval and the source statistics (i.e., the composition) which can be realized with \(\log n\) bits (Here we assume that the memory required to store the interval is negligible, and roughly \(\log_{2}n\) bits are enough to store the composition which consists of numbers that add up to \(n\)). Thus, we denote the storage complexity of AC-CCDM by \(\mathcal{O}(\log n)\). A similar reasoning can be used to determine the storage complexity of SR-DM (Section IV in [58]) which is also \(\mathcal{O}(\log n)\). In MPDM, in addition to the requirements of the underlying CCDM algorithm, a composition is chosen based on a prefix of the binary input sequence. For this purpose, a prefix code and the corresponding Huffman tree is constructed (Section III-C in [55]). To store the binary-tree, a LUT can be used. The size of this table depends on the number of utilized compositions. For practical scenarios, the number of compositions is on the order of a few hundreds as shown in the following example. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{2}{c}{**Direct Method**} & \multicolumn{2}{c}{**Indirect Method**} \\  & \multicolumn{2}{c}{**(Distribution Matching)**} & \multicolumn{2}{c}{**(Energy-Efficient Signal Space)**} \\ \cline{2-5}  & **AC-CCDM**[52] & **SR-DM**[58] & **ESS**[22] **and (Algorithm 1 in [23])** & **SM**[23] \\ \hline Serialism & \multirow{2}{*}{\(k+n\)} & \multirow{2}{*}{\(\min(n_{1},n-n_{1})+1\)} & \multirow{2}{*}{\(k+n\)} & \multirow{2}{*}{\(k+\log_{2}n\)} \\ (no. of loop iter.) & & & & \\ \hline Storage & \multirow{2}{*}{\(\mathcal{O}(\log n)\)} & \multirow{2}{*}{\(\mathcal{O}(\log n)\)} & FP: \(\mathcal{O}(n^{2})\) & FP: \(\mathcal{O}(n^{2}\log n)\) \\ Complexity & & & BP [65]: \(\mathcal{O}(n^{2}\log n)\) & BP [65]: \(\mathcal{O}(n\log^{2}n)\) \\ \hline \multirow{3}{*}{
\begin{tabular}{c} Computations (per 1-D) \\ \end{tabular} } & \multirow{3}{*}{\(n_{a}\) divisions, multiplications} & \multirow{3}{*}{Sh: \((n_{a}-1)\) BCs} & \multirow{3}{*}{Sh: \(n_{a}\) additions} & \multirow{3}{*}{Sh: \(L\) multiplications, comparisons} \\  & and comparisons & & (and \(L\) comparisons/additions \\ \end{tabular} (and \(L\) comparisons/additions ) & & & \\ \cline{1-1}  & & per \(n\)-D for [23, Algorithm 1]) & Dsh: \(L\) multiplications and additions \\ \hline \hline \end{tabular}  
* SM requires a division per dimension for shaping as well. (Sh.Shaping, Dsh: Deshaping, BC: Binomial Coefficient).  
\end{table} 
Table 3: Serialism, required storage and computational complexity. **Example 9** (MPDM, number of compositions). : _We consider \(\mathcal{A}=\{1,3,5,7\}\), \(n=216\) and target rates \(k/n=1.5\) and 1.75 bit/1-D. To obtain these rates, MPDM uses 318 and 593 different compositions, respectively. Assuming that numbers in a composition can be stored using at most \(\lceil\log_{2}n\rceil\) bits, at most 10,176 and 18,976 bits of memory are required to store the corresponding LUTs, respectively. Note that these are the parameters that are used for the simulations considered in Figure 11._  
FP implementations of ESS and (Algorithm 1 in [23]) require the storage of an \(n\)-by-\(L\) matrix where each element is at most \(\lceil nR_{\mathrm{s}}\rceil\)-bits long. Therefore, following Remark 2, the storage complexity of these algorithms is \(\mathcal{O}(n^{3})\) for fixed \(R_{\mathrm{s}}\). FP SM can be realized by storing a \(\log_{2}n\)-by-\(L\) matrix [23], which has complexity \(\mathcal{O}(n^{2}\log n)\). We note here that these values are in alignment with (Table I in [23]). **Example 10** (FP SpSh, required storage).