# A special invertible k-bits to n-bits mapping

1. Sep 29, 2011

### ait.abd

I want a sequence of $n$ bits without all $1$'s in the output. What is the minimum number of bits $k$ given $n$ that can be used in any linear or non-linear invertible mapping that will produce such a sequence at output. For example, consider $n=3$. I want to create a mapping that has all $2^3=8$ minus $111$ sequence. What is the minimum number of bits $k$ required that will produce such a mapping? In this example, for a linear mapping, I can see that $k=2$. But with $k=2$, I am loosing $3$ sequences at the output and the overhead of this mapping $k/n$ is huge. Is there any other method or non-linear mapping that does this job with an overhead of $k/n>2/3$. I need a specific answer to $n=4$ or general answer with any $n$ (reasonable range for me is $n=2$ to $n=16$. Please guide me to any keywords that may help in my search for the answer.

2. Sep 29, 2011

### Stephen Tashi

You haven't defined the domain of mapping.
You haven't explained what it means to "use" bits in the mapping.

3. Sep 30, 2011

### ait.abd

Domain of mapping is $S=\{\text{All } 2^k \text{ sequences of k-bits}\}$.
Range of the mapping is $T=\{2^n-1 \text{ sequences of n-bits i.e. All sequences of n-bits excluding the all 1's sequence}\}$
By using I mean defining a mapping S to T. In case of linear mapping, the answer is straightforward that the maximum number of bits $k$ required are $n-1$. My question is whether there are any non-linear invertible mappings/transforms that take $k$ bits and output a sequence of length $k$ bits (not $n$) that doesn't contain all 1's sequence. I don't see any linear mapping fulfilling this criterion as $k \le (n-1)$ is always true for linear mappings/transform.
*I may not be using mapping and transform words in the strict sense. By mapping or transform I mean is there any $t = f(s); t \in T, s \in S; t=t_1,t_2,t_3,...,t_k; s=s_1,s_2,s_3,...,s_n; s_p,t_p \in \{0,1\}$

4. Sep 30, 2011

### Stephen Tashi

There are no invertible mappings like that. An invertible mapping has to be 1-to-1. The range can't have a smaller cardinality than the domain.