## 3 The Proposed Framework  
Suppose one wants to represent binary strings of fixed length \(n\) with sequences of fixed length \(s\) using the \(a\) symbols from an alphabet \(\Psi\) (for example, the 45 printable symbols of the Base45 system [10]). Then, the following constraint must be satisfied:  
\[2^{n}\leq a^{s}. \tag{1}\]  
The passive redundancy (i.e., the number of sequences of \(s\) symbols from \(\Psi\) not representing any binary string of length \(n\)) of this encoding according to [20] is:  
\[r=a^{s}-2^{n}. \tag{2}\]  
Note that in the rest of the paper we will assume that the binary strings of length \(n\) have all the same probability as is the case for compressed and/or encrypted data. Thus, the exceeding \(r\) sequences that do not represent one of \(2^{n}\) binary strings may be used to embed extra data bits in the flow of symbols from \(\Psi\): these bits may carry, for example, a watermark, a signature, a message authentication code, a cyclic redundancy check, or any extra information an application may need. Let us consider a generic sequence of \(s\) symbols from the alphabet \(\Psi\), and define the following sets:  
* \(\mathbf{T}\), the set of all possible sequences of \(s\) symbols, having cardinality \(a^{s}\);
* \(\mathbf{C}\), the subset of \(\mathbf{T}\) containing the sequences used to encode the \(2^{n}\) binary strings (obviously having cardinality \(2^{n}\)): the mapping is defined with a bijective function \(\beta\);
* \(\mathbf{E}\), the subset of \(\mathbf{T}\) containing the exceeding \(r\) sequences that are not used to represent the binary strings. The sets \(\mathbf{C}\) and \(\mathbf{E}\) constitute a partition of \(\mathbf{T}\). To exploit the redundancy in this coding the set \(\mathbf{C}\) is further partitioned into two subsets:  
* \(\mathbf{E}^{\prime}\), a subset of cardinality \(r\) containing the sequences put in one-to-one correspondence with the sequences in \(\mathbf{E}\) by a bijective mapping function \(\varphi\);
* \(\mathbf{N}^{\prime}\), the subset of the remaining sequences in \(\mathbf{C}\) having no corresponding sequence in \(\mathbf{E}\). In the present work every sequence in \(\mathbf{C}\) is put in relation with at most one sequence in \(\mathbf{E}\). Moreover, we assume that the encoding is frugal in the sense that \(\text{card}(\mathbf{C})\) is not lower than \(\text{card}(\mathbf{E})\). The extension to a mapping allowing for more than one sequence in \(\mathbf{E}\) to be associated to some sequence in \(\mathbf{C}\) is left as a further development, as it will be discussed in the conclusions. \begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**Base**} & **No. of Encoded** & **No. of Representable** & **Available** \\  & **Binary Strings** & **Binary Strings** & **Configurations** \\ \hline Base16 [13] & \(2^{8}\) & \(2^{8}\) & 0 \\ Base32 [13] & \(2^{40}\) & \(2^{40}\) & 0 \\ Base45 [10] & \(2^{16}\) & \(45^{3}\) & 25,589 \\ Base62 [18] & \(2^{16}\) & \(32\times 62^{2}\) & 57,472 \\ Base62 [18] & \(2^{31}\) & \(4\times 62^{5}\) & 1,517,047,680 \\ Base62 [19] & \(2^{6}\) & 62 & 0 \\ Base64 [13] & \(2^{24}\) & \(2^{24}\) & 0 \\ Base85 [11,12] & \(2^{32}\) & \(85^{5}\) & 142,085,829 \\ Base91 [14] & \(2^{13}+12\) & \(91^{2}\) & 77 \\ Base91 [15] & \(2^{13}+89\) & \(91^{2}\) & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of the main encodings’ capacity. bits per binary string (bpbs) may be embedded in the output sequence. The corresponding payload per byte (bit per byte, bpb) can be computed as:  
\[q=\frac{8p}{n}. \tag{4}\]  
The payload referred to the output symbols (bit per symbol, bps) is:  
\[o=\frac{p}{s}. \tag{5}\]  
For example, Base45 as defined in [10] encodes \(n=16\) bits in \(s=3\) symbols (with \(a=45\)) thus \(p=0.390457\) bpbs, \(q=0.195229\) bpb, \(o=0.130152\) bps. In case of Base85, \(n=32\), \(s=5\), \(a=85\) leading to \(p=0.033082\) bpbs, \(q=0.008270\) bpb, \(o=0.006616\) bps.