A special invertible k-bits to n-bits mapping

[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.

 

[Stephen Tashi]

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.

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

 

[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\}$

 

[Stephen Tashi]

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.

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.

 

[blue_raver22]

The minimum number of bits k required in any linear or non-linear invertible mapping to produce a sequence of n bits without all 1's in the output depends on the specific mapping used. In general, for a linear mapping, the minimum value of k is equal to n-1. This means that for n=3, the minimum value of k is 2, as you have already observed.

However, as you have also noted, using a linear mapping with k=2 means that there will be a loss of 3 sequences at the output. This is because with k=2, there are only 2^2=4 possible input combinations, but n=3 requires 2^3=8 possible output sequences. This loss is significant and may not be desirable in some cases.

There may be other non-linear mappings that can achieve the desired output without such a high loss. However, it is difficult to determine a specific value of k that will work for all cases of n. This will depend on the specific mapping used and the input-output relationship it follows.

One possible approach could be to use a combination of linear and non-linear mappings. This may help reduce the overhead and achieve the desired output without significant loss. Alternatively, you could also explore different types of mappings, such as bijective or affine mappings, to see if they can achieve the desired output with a lower overhead.

In terms of keywords that may be helpful in your search, you could look into "invertible mappings", "linear mappings", "non-linear mappings", "bijective mappings", and "affine mappings". Additionally, including the specific values of n and k in your search may also yield more targeted results.

In conclusion, the minimum number of bits k required in any linear or non-linear invertible mapping to produce a sequence of n bits without all 1's in the output will depend on the specific mapping used and the desired input-output relationship. Further exploration and experimentation with different types of mappings may help in finding a suitable solution for your specific needs.