# Probabilistic Shaping for Finite Blocklengths: Distribution Matching and Sphere Shaping
## 4 Distribution Matching and Sphere Shaping Architectures
### Distribution Matching Architectures (Direct Method)
Note that the prefix and payload length are balanced such that the overall shaping operation is fixed-length. It has been shown in [55] that compared to CCDM, pairwise MPDM with such a tree structure gives an approximately fourfold reduction in required blocklength to obtain the same information rate. In addition, pairwise MPDM has also been demonstrated to give significant achievable rate and SNR improvements for a fixed blocklength over CCDM for the AWGN channel [94] and the optical fiber channel [95]. **Example 5** (MPDM). : _We consider the same target PMF and \(n=216\) as in Example 4. Pairwise MPDM with tree structure utilizes 945 compositions whose average is again \([95,69,37,15]\). The shaping rate (7) of the matcher that produces sequences with these compositions is \(R_{s}=1.7315\) bit/1-D. The corresponding input length (8) is \(k=374\) which is 7 bits more than that of CCDM which is a 1.9% rate increase._  
CCDM has initially been realized with AC, which is sequential in the input length, i.e., at most \(k\) serial operations must be carried out for shaping, and \(n\) for deshaping (Note that this describes the worst-case serialism if the DM operation cannot be terminated early, which could be the case when the remainder of the output sequence follows at some point with certainty. Also, this metric does not incorporate the complexity of the computations inside each step as discussed in Section 6). Since the serialism of the AC method can be challenging to achieve for high-throughput CCDM operation, means to run several DMs in parallel have been proposed. For BL-DM [57] or PDM [51] where the target distribution is a product distribution, the parallelization factor is \(\log_{2}n_{a}=m-1\) since one binary-alphabet DM is used for each bit level. This approach has been numerically shown to have reduced rate loss compared to a single nonbinary DM, yet comes at the expense of having the DM output limited to compositions that are generated from a product distribution. In [58], a different parallelization technique has been proposed, which operates on amplitudes rather than on bit levels. For each of the \(n_{a}-1\) out of \(n_{a}\) amplitudes, a binary-alphabet DM is operated in parallel, with the first DM determining the position of the first amplitude, the second DM where to position the second amplitude within those positions that have not been occupied by the preceding, i.e., the first, amplitude. These DM operations can be run in parallel and only the final step of combining the subsequences into the nonbinary output sequence is sequential. We note that both bit-level DM and parallel-amplitude DM are compatible with MPDM. The schemes discussed in the preceding paragraphs can be considered as extensions to the CCDM architecture that either nest various CCDMs for improved performance (MPDM) or transform a nonbinary CCDM into several binary CCDMs to achieve a larger parallelization (bit-level and parallel-amplitude DM). In [58], subset ranking (SR) has been proposed as an alternative to the conventional AC algorithm for CCDM as shown in the bottom layer of Figure 1. SR solves the CCDM indexing problem by representing a binary-alphabet sequence as a constant-order subset that determines the position of either binary symbol. For a given sorting, such as lexicographical, the rank of such a subset is found by \"enumerating\" all preceding sequences which is used for source coding in [96, 97], and for shaping in [22, 65]. This mapping from sequence to (binary) rank is called unranking in the combinatorics literature and acts as deshaping. The ranking operation from bits to sequence is shaping. The advantage of SR over AC is that the number of serial operations is significantly reduced (Section V in [58]).