Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A special invertible k-bits to n-bits mapping

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

    Stephen Tashi

    User Avatar
    Science Advisor

    You haven't defined the domain of mapping.
    You haven't explained what it means to "use" bits in the mapping.
     
  4. Sep 30, 2011 #3
    Domain of mapping is [itex]S=\{\text{All } 2^k \text{ sequences of k-bits}\}[/itex].
    Range of the mapping is [itex]T=\{2^n-1 \text{ sequences of n-bits i.e. All sequences of n-bits excluding the all 1's sequence}\}[/itex]
    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 [itex]k[/itex] required are [itex]n-1[/itex]. My question is whether there are any non-linear invertible mappings/transforms that take [itex]k[/itex] bits and output a sequence of length [itex]k[/itex] bits (not [itex]n[/itex]) that doesn't contain all 1's sequence. I don't see any linear mapping fulfilling this criterion as [itex]k \le (n-1) [/itex] 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 [itex]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\} [/itex]
     
  5. Sep 30, 2011 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A special invertible k-bits to n-bits mapping
Loading...