## 2 Fundamentals of Probabilistic Shaping  
### Constant Composition Distribution Matcher  
The function of constant composition distribution is to convert binary bit sequences \(B^{k}=b_{1}b_{2}\ldots b_{k}\) into amplitude sequences \(A^{n}=a_{1}a_{2}\ldots a_{n}\) in a one-to-one, reversible mapping. The term \"constant composition\" has two meanings: the length of the input bit sequence and the output amplitude sequence are both fixed, as is the composition of the output amplitude sequence, which means the probability of each amplitude occurring is constant.  
Specifically, the input sequence \(B^{k}\) is a uniformly distributed binary sequence of length \(k\). If we define a set of amplitudes \(\chi=\{\alpha_{1},a_{2},\ldots,\alpha_{i}\}\), then the output sequence \(A^{n}\) is of length n and the probability of each amplitude will be \(P_{A}(\alpha_{i})=\frac{n_{a_{i}}}{n}\), indicating that the amplitude \(\alpha_{i}\) will occur \(n_{a_{i}}\) times in this sequence with length n. Use \(\Gamma_{P_{A}}^{n}\) to denote the set of all sequences of length n with a probability \(P_{A}\) of each amplitude. For example, for a 4 ASK signal, \(\chi=\{1,3\}\); when n = 4, P(1) = 3/4, P(3) = 1/4, \(\Gamma_{P_{A}}^{n}=\{1113,1131,1311,3111\}\), the CCDM needs to map the amplitude sequence in \(\Gamma_{P_{A}}^{n}\) with a sequence of binary bits of length k, \(k=\log_{2}\Gamma_{P_{A}}^{n}=2\), such as the following mapping: \(00\Leftrightarrow 1113,01\Leftrightarrow 1131,10\Leftrightarrow 1311,11 \Leftrightarrow 3111\).  
The key steps for constructing a CCDM are as follows: specify the probability \(P_{A}(\alpha_{i})\) of the amplitude \(\alpha_{i}\) and the length n of the output amplitude sequence; the number of input bits for CCDM of a set \(\Gamma_{P_{A}}^{n}\) is given by (1). \(\lfloor\cdot\rfloor\) is rounded down. Since CCDM is an invertible mapping, the size of the codebook \(C_{ccdm}\) should be \(2^{k}\); select a subset of \(\Gamma_{P_{A}}^{n}\) as the codebook and establish the mapping relation \(f_{ccdm}\) to finish one-to-one mapping of the input and output sequences: \(\{0,1\}^{k}\xleftarrow{f_{ccdm}}C_{ccdm}\subseteq\Gamma_{P_{A}}^{n}\).  
\[k=\left\lfloor\log_{2}\Gamma_{P_{A}}^{n}\right\rfloor=\left\lfloor\log_{2} \frac{n!}{\prod\limits_{i=1}^{n}n_{a_{i}!}}\right\rfloor,\;n_{a_{i}}=n\cdot P _{A}(\alpha_{i}), \tag{1}\]  
Any finite length distribution matcher exists a rate loss problem. The rates of CCDM are \(R=k/n\) (bit/symbol), which means that each symbol in the output amplitude sequence carries \(k\) bits of information. Under the corresponding probability distribution, the information that each symbol is theoretically able to carry is \(H(A)\), with a rate loss of (2).  
\[R_{loss}=H(A)-R=H(A)-\frac{k}{n}, \tag{2}\]  
Similar to the above 4 ASK signal, P(1) = 3/4, P(3) = 1/4, H(A) = 0.8113 bit/symbol; when \(n=20\), \(\left\lfloor\log_{2}\Gamma_{P_{A}}^{n}\right\rfloor=13\), \(R_{loss}=0.8113-0.65=0.1613\); when \(n\) reaches 10,000, R = 8106/10,000 = 0.8106 bit/symbol. So, CCDM is an asymptotically optimal mapping scheme when the output sequence length \(n\rightarrow\infty\), R \(\rightarrow\) H(A). When n is relatively small, CCDM has a large rate of loss.