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.