# Hide45: A Method for Optimal Payload Data Hiding in Base45 Encoded Strings
## 5 Proposed Algorithm
Starting from the observation that if a sequence \(\mathsf{S}_{0}\) in \(\mathcal{E}\) is associated to a sequence \(\mathsf{S}_{1}\) in \(\mathcal{D}\) it may reversibly carry one bit of extra data (during decoding \(\mathsf{S}_{0}\) means a 0 valued bit payload and restore \(\mathsf{S}_{0}\), \(\mathsf{S}_{1}\) means a 1 valued bit payload and restore \(\mathsf{S}_{0}\)), then if a sequence \(\mathsf{S}_{00}\) in \(\mathcal{E}\) is associated to the sequences \(\mathsf{S}_{01},\mathsf{S}_{10},\mathsf{S}_{11}\) in \(\mathcal{D}\) then during encoding/decoding two bits of extra data may be embedded/extracted depending on which one of the four sequences is used and the original sequence \(\mathsf{S}_{00}\) can be restored during decoding. In the present paper, we propose to optimize the construction of the set \(\mathcal{E}\) according to the frequency distribution of the data and having the following characteristics:  
* The mapping \(\eta\) may associate a sequence in \(\mathcal{W}\) to \(2^{k}-1,k\in\mathbb{N}\), sequences in \(\mathcal{D}\), thus, in general, \(\mathbf{card}(\mathcal{D})\geq\mathbf{card}(\mathcal{E})\) and \(\eta\) is not one-to-one anymore: a sequence in \(\mathcal{W}\) may carry \(k\) bits if it is associated to \(2^{k}-1\) sequences in \(\mathcal{D}\);
* Given the relative frequencies \(f_{i}\) of the binary strings in \(\mathcal{B}\), the objective is to associate \(n_{i}\) bits of payload to the \(i\)-th sequence to maximize the average payload \(p\) per binary sequence: \[p=\sum_{i\in\mathcal{B}}n_{i}f_{i}.\] (1) As an example, consider the encoding proposed in [20] for Base45 [21]: two octets are mapped on three symbols from a base 45 alphabet, thus having \(45^{3}=91\),125 configurations. Two octets result in \(2^{16}=65\),536 binary configurations each having its own relative frequency \(f_{i}\). A one-to-one mapping from binary configuration to Base45 configuration leaves \(45^{3}-2^{16}=91\),\(125-65\),\(536=25\),589 Base45 configurations unused. Assigning \(n_{i}\) bits payload to the \(i\)-th binary configuration the average payload \(p_{45}\) per binary string is:  
\[p_{45}=\sum_{i=0}^{2^{16}-1}n_{i}f_{i} \tag{2}\]  
which must be maximized. Assigning \(k\) bits payload to a binary configuration requires to use \(2^{k}\) Base45 configurations: one Base45 sequence is the one normally assigned whilst the \(2^{k}-1\) are taken from the unused 25,589 Base45 sequences. This poses a constraint on the previous value (2):  
\[\sum_{i=0}^{2^{16}-1}2^{n_{i}}\leq 45^{3}=91\text{,}125. \tag{3}\]  
It is obvious that the 25,589 sequences must be assigned to the highest frequency binary configurations maximizing (2). Another way to write constraint (3) is to look only at the unused sequences; if any configuration \(i\) is assigned \(n_{i}\) bits, it requires in total \(2^{n_{i}}-1\) extra configurations excluding itself. For example, if \(n_{i}=0\) we assign \(2^{0}=1\) configurations to \(i\) (only itself), and it requires \(2^{0}-1=0\) extra sequences; this is correct, since no payload will be carried by configuration \(i\). Knowing that the total number of extra (unused) sequences is 25,589 we can then write:  
\[\sum_{i=0}^{2^{16}-1}(2^{n_{i}}-1)\leq 25\text{,}589 \tag{4}\]which is equivalent to Equation (3) since:  
\[\sum_{i=0}^{2^{16}-1}(2^{n_{i}}-1)\leq 25,589 \Leftrightarrow \sum_{i=0}^{2^{16}-1}2^{n_{i}}-\sum_{i=0}^{2^{16}-1}1\leq 25,589\] \[\Leftrightarrow \sum_{i=0}^{2^{16}-1}2^{n_{i}}-2^{16}\leq 25,589\] \[\Leftrightarrow \sum_{i=0}^{2^{16}-1}2^{n_{i}}\leq 25,589+2^{16}\ \Leftrightarrow\ \sum_{i=0}^{2^{16}-1}2^{n_{i}}\leq 91,125\]  
that is exactly the aforementioned constraint. In the following Section 5.1 we present the optimization method used to assign unused configurations in \(\mathcal{D}\) and, consequently, bits to the legal Base45 sequences with the purpose of maximizing the average payload \(p_{45}\) per pair of octets (2).