## 2 Materials and Methods
### Non-Uniquely-Decodable Data Coding
input \(\mathcal{A}\) sequence can be achieved with \(\frac{2(d-1)}{d\cdot 2^{d}}\) bits overhead per each original bit._  
Figure 1.6 The representation of the code-word lengths to specify the code-word boundaries on the NPF stream. Proof. : Total overhead can be computed by subtracting the original length \(n\) from the sum of the space consumption described in Lemmas 1 and 2. Dividing this value by the \(n\) returns the overhead per bit as shown below. Figure 1.7  
Table 1 summarizes the amount of extra bits introduced by the proposed encoding per each original bit in \(\mathcal{A}\). A large overhead, which seems significant for small \(d\), e.g., \(d<8\), may inhibit the usage of the method. However, thanks to the to the exponentially increasing denominator (\(2^{d}\)) in the overhead amount that the extra space consumption quickly becomes very small, and even negligible. For instance, when \(d=8\), the method produces only 6.8 extra bits per a thousand bit. Similarly, the overhead becomes less than 3 bits per \(100K\) bits, and less than 2 bits per a million bits for the values of \(d=16\) and \(d=20\), respectively. Thus, for \(d\geq 8\), an input uniformly i.i.d. bit sequence can be represented with a negligible space overhead by the proposed non-UD encoding scheme. Experimental Verification of the Space Usage Results  
During the calculations of the payload and disambiguation information sizes as well as the overhead, the input data has been assumed to be independently and identically distributed. In practice, the input to the proposed method is supposed to be the output of an entropy coder, where the distribution of \(d\)-bits long items in such a file may deviate from the perfect assumptions. We would like to evaluate whether such entropy-encoded files still provide enough good uniformity close to the theoretical claims based on uniformly i.i.d. assumption. Therefore, we have conducted experiments on different compressed files to observe how much these theoretical values are caught in practice. We have selected 16 publicly available files.The first ten files are available from [[http://corpus.canterbury.ac.nz](http://corpus.canterbury.ac.nz)]([http://corpus.canterbury.ac.nz](http://corpus.canterbury.ac.nz)) and [[http://people.unipmn.it/manzini/lightweight/corpus/](http://people.unipmn.it/manzini/lightweight/corpus/)]([http://people.unipmn.it/manzini/lightweight/corpus/](http://people.unipmn.it/manzini/lightweight/corpus/)). The multimedia files are from [[https://github.com/johndyger/mediaelement-files](https://github.com/johndyger/mediaelement-files)]([https://github.com/johndyger/mediaelement-files](https://github.com/johndyger/mediaelement-files)), where the first ten are _gzip_ compressed data from different sources and the remaining six are multimedia files of _mp3_, _mp4_, _jpg_, _webm_, _ogv_, and _fw_ formats. The first \(d\cdot 2^{d}\) bits of each file is inspected for distinct values of \(d=\{8,12,16,20\}\), and the corresponding observed payload and disambiguation information sizes are computed as well as the overhead bits in each case. Table 2 includes the comparisons of the observed and theoretical values on each analyzed dimension. The payload size, which is the total length of the concatenated NPF code-words, and the disambiguation information size, which is the total length of the prefix-free encoded code-word lengths, are both observed to be compatible with the theoretical claims. This is also reflected on the overhead bits as a consequence. Thus, in terms of space consumption, the experimental results on compressed data support the theoretical findings based on perfect uniformly i.i.d. input data assumption.