Results 1 to 2 of 2

Math Help - Sum Distinct Algorithm

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    1

    Sum Distinct Algorithm

    Dear

    I know basic sum distinct set is Z =(1 2 4 8 16 32 64 and so on) which follows the equation like : Nth element = (n-1)th element + (n-2) element + 1. But since I would like to implement this sum distinct property in wireless sensor network in binary format. To represent 64 in binary I need (1000000) 7 bits.

    Are there any other sum distinct set can be possible so that I need less number of bits?


    Let say, we have sensor node: X1,X2,X3,X4,X5,X6, X7 total 7 nodes. Our coding scheme is as follows : X1=1,X2=2,X3=4,X4=8,X5=16=,X6=32, X7=64. So when any node has any sensing event it will transmit the preassign code. Ans we allow simultaneous transmission. So if all the nodes are transmitting over the air they will sum up which is the summation of Z i.e 127. If any one of the node are not transmitting let say X5, we will get 127-16 = 111 at the receiver side. Since receiver does not have any other information except summation and pre-coding scheme, how can we now which one is the node not transmitting? This is very easy for this sum distinct set by subtracting the total sum to receive sum i.e. 127-111 = 16 so node X5 is not transmitting. What is the problem so that I am not interesting with this solution? This is because it needs lot of bits and which leads a bandwidth problem for wireless sensor networks (WSNs).

    I would like you to help me how can I design another sum distinct set which has same property that I said earlier with minimum number of binary bit.


    Are their any relation with this problem with lattice sphere packing or coverage problem?

    Please suggest me some Engineering mathematical literature to formalize the problem and design the algorithm.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    I know basic sum distinct set is Z =(1 2 4 8 16 32 64 and so on) which follows the equation like : Nth element = (n-1)th element + (n-2) element + 1.
    The equation is: nth element = 2 * (n - 1)th element.

    You probably googled for "distinct subset sums." I found these two articles (PDF). Apparently, there is Erdős conjecture that for some constant c, the maximum of an n-element set with distinct subset sums is at least c * 2^n. As you noted, there are n-element sets where the maximum is 0.5 * 2^n. The second article above proves that there are sets where the maximum is < 0.22002 * 2^n for sufficiently large n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: December 19th 2011, 09:34 AM
  2. Distinct Subgroups
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 12th 2011, 04:36 AM
  3. three distinct
    Posted in the Algebra Forum
    Replies: 2
    Last Post: July 7th 2008, 11:35 PM
  4. distinct value of
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: May 19th 2008, 10:38 PM
  5. distinct permutations.............
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 15th 2007, 07:07 AM

Search Tags


/mathhelpforum @mathhelpforum