Introduction
Many communication problems involve sending information from one function to another by sending $$$0$$$s and $$$1$$$s (binary) or some number smaller than $$$b$$$ (base $$$b$$$). In these problems, we often need to change the information that we want to send from one base to another.
This can be particularly tricky when the information that we want to send is a sequence of numbers. A common way to do so is to send each number one by one using $$$\lceil \log_b (k) \rceil$$$ digits where $$$b$$$ is the base we can send information in and the elements of the sequence are between $$$0$$$ and $$$k - 1$$$. The problem with this is that if we are sending $$$l$$$ numbers, we are possibly wasting some digits as $$$l\lceil \log_b (k) \rceil \ge \lceil l\log_b (k) \rceil$$$.
In this blog, I will be demonstrating a way to encode $$$n$$$ sequences $$$a_0, a_1, \ldots, a_{n - 1}$$$, each sequence $$$a_i$$$ consisting of $$$l_i$$$ non-negative integers $$$0 \le a_{i, 0}, a_{i, 1}, \ldots, a_{i, l_i - 1} < k_i$$$. The sequences will be encoded into a single sequence $$$x$$$ of length $$$m$$$ consisting of non-negative integers $$$0 \le x_0, x_1, \ldots, x_{m - 1} < b$$$, where $$$m = \lceil\sum_{i=0}^{n - 1} l_i\log_b k_i\rceil$$$. Conveniently, the inverse operation to decode sequence $$$x$$$ back into $$$n$$$ sequences $$$a_0, a_1, \ldots, a_{n - 1}$$$ follows a very similar structure which I will show below.