## 2 Materials and Methods
### Non-Uniquely-Decodable Data Coding
The number of distinct \(b_{i}\) values represented by a code-word of length \(\ell\) is \(2^{\ell}\) for \(1\leq\ell<d\), and two of the \(b_{i}\) values require \(\ell=d\) bit long code-words as stated in Proposition 1. Thus, \(C_{\ell}=\frac{r}{2^{d}}\cdot 2^{\ell}\) for \(1\leq\ell<d\), and \(C_{d}=\frac{r}{2^{d}}\cdot 2\). The length of the \(NPF(\mathcal{B})\) bit-stream can then be computed by  
\[|NPF(\mathcal{A})| = \frac{r}{2^{d}}\cdot\left(1\cdot 2+2\cdot 2^{2}+\ldots+(d-1)\cdot 2 ^{d-1}+d\cdot 2\right) \tag{1}\] \[= \frac{r}{2^{d}}\cdot\left(2d+\sum_{i=1}^{d-1}i\cdot 2^{i} \right)=\frac{r}{2^{d}}\cdot\left(2d+2^{d}\cdot(d-2)+2\right)\] (2) \[= \frac{r}{2^{d}}\cdot\left(2^{d}(d-2)+2(d+1)\right)\] (3) \[= r\cdot d-r\cdot\left(2-\frac{d+1}{2^{d-1}}\right)\] (4) \[= r\cdot\left(d-2+\frac{d+1}{2^{d-1}}\right)\] (5) \[= \frac{n}{d}\cdot\left(d-2+\frac{d+1}{2^{d-1}}\right)\] (6) \[= n\cdot\left(1-\frac{2}{d}+\frac{2(d+1)}{d\cdot 2^{d}}\right) \tag{7}\]  
Figure 1: A simple sketch of the non-prefix-free coding of an input bit sequence \(\mathcal{A}\), where \(\mathcal{B}\) is the representation of \(\mathcal{A}\) with the block length \(d=3\). \(\Sigma^{\prime}\) is a random permutation of the corresponding alphabet \(\Sigma\), and \(W\) is the non-prefix-free code-word set generated for \(\Sigma^{\prime}\) according to Definition 2. The disambiguation information \(DisInfo(\mathcal{A})\) is computed according to Lemma 2. While computing the summation term in Equation (2), we use the formula from basic algebra that \(\sum_{i=1}^{p}i\cdot 2^{i}=2^{p+1}(p-1)+2\), and substitute \(p=d-1\). The NPF coding represents the \(n\) bits long input sequence \(\mathcal{A}\) with \(n\cdot\big{(}\frac{2}{d}-\frac{2(d+1)}{2^{d}}\big{)}\) bits. However, since non-prefix-free codes are not uniquely decodable, \(NPF(\mathcal{A})\) cannot be decoded back correctly in absence of the code-word boundaries. Therefore, we need to represent these boundary positions on \(NPF(\mathcal{A})\) as well. Lemma 2 states an efficient method to achieve this task. **Lemma 2**. : _The expected number of bits to specify the code-word boundaries in the \(NPF(\mathcal{A})\) is \(n\cdot\big{(}\frac{2}{d}-\frac{4}{d\cdot 2^{d}}\big{)}\), where \(|\mathcal{A}|=n=r\cdot d\)._  
Proof. : Due to Proposition 1 there are \(2^{\ell}\) distinct code-words with length \(\ell\) for \(\ell\in\{1,2,\ldots,d-1\}\) and 2 code-words (sets) are generated for \(\ell=d\). Since each \(d\)-bits block has equal probability of appearance on \(\mathcal{A}\), the number of occurrences of code-words having length \(\ell\in\{1,2,\ldots,d-1\}\) is \(\frac{r}{2^{d}}\cdot 2^{\ell}\). The most frequent code-word length is \((d-1)\), which appears at half of the \(r\) code-words as \(\frac{r}{2^{d}}\cdot 2^{d-1}=\frac{r}{2}\). It is followed by the code-word length \((d-2)\) that is observed \(\frac{r}{4}\) times. When we examine the number of code-words with length \(\ell\in\{1,2,\ldots,d-1\}\), we see that this distribution is geometric, as depicted in Figure 1.0 The optimal prefix-free codes for the code-word lengths are then \(\{1,01,001,\ldots,0^{d-2}1,0^{d-1}\}\), which correspond to code-word lengths \(\{d-1,d-2,d-3,\ldots,1,d\}\) respectively. Thus, code-word length \(\ell=(d-i)\in\{1,2,\ldots,d-1\}\), which appears \(\frac{r}{2^{d}}\cdot 2^{d-i}\) times on \(\mathcal{A}\), can be shown by \(i\) bits. We use \((d-1)\) consecutive zeros to represent the code-word length \(\ell=2\) as the number of occurrences of \(d\)-bits long code-words is equal to the number of 1 bit long code-words on \(\mathcal{A}\). Notice that the representation of the code-word lengths are prefix-free that can be uniquely decoded. Total number of bits required to represent the individual lengths of the code-words can be computed by  
Figure 1.1 Figure 1.2 (9) Figure 1.3 (10) Figure 1.4 (11) Figure 1.5  
**Theorem 1**. : _The non-UD encoding of \(n\) bit long i.i.d.