Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was generously introduced to the LFSR here not long ago. I am looking to take that a little further.

I want to generate an Maximum length sequence of k-weight n-bit numbers in such a way that the sequence looks random but generates all possible values.

k-weight: I mean that the n-bit number has only k set bits.

share|improve this question
    
I don't understand. A maximum length sequence consists of single bits. An $m$-sequence of length $2^\ell-1$ has the property that all combinations of $\ell$ consecutive bits (with the exception of all zeros) occur exactly once within the period. So the length of an $m$-sequence is of the form $2^\ell-1$. The number of $n$-bit words with weight $k$ is ${n\choose k}$. This number is rarely of the form $2^\ell-1$. –  Jyrki Lahtonen Aug 14 '13 at 8:26
    
@JyrkiLahtonen - Apologies for misleading you - I am familiar with using an LFSR using taps defined by a primitive polynomial to generate all n-bit numbers in a pseudo-random order. I was under the impression that was an MLS. What I am looking for is a mechanism that generates just the k-weight n-bit numbers. –  OldCurmudgeon Aug 14 '13 at 8:30
    
Ok. Sorry I was being a bit hasty as well. Need to think about this. I would be somewhat surprised, if an LFSR can do what you hope, but it sounds like you would welcome any ways of producing weight $k$ vectors in a random order. –  Jyrki Lahtonen Aug 14 '13 at 8:32
add comment

2 Answers

up vote 1 down vote accepted

The combinatorial number system provides an easily computatble bijection between the $\binom nk$ combinations of $k$ elements chosen among an $n$-set (which of course you may interpret as $k$-weight $n$-bit numbers) and the first $\binom nk$ natural numbers. Using this translates your problem into generating a sequence of numbers $a_i$ in the range $0\leq a_i<\binom nk$ with similar properties, and I think you alread know how to handle that using linear feedback shift registers.

There might be a slight complication in that $\binom nk$ could be hard to realise as the cycle length of an LFSR. But I think this can be resolved by generating numbers in a slightly larger range, and simply skip to the next whenever a number outside the desired range is generated; in the remaining "good" cases one can find the combinatorial number system representation of the generated number. On the other hand I can also imagine that for your application this skipping is not acceptable; after all one could also choose to simply generate all $n$-bit numbers and skip those that are not $k$-weight, which should work similarly (even though this is less efficient). If indeed this problem is prohibitive for you, the whole difficulty would be to find a pseudo-random sequence of cycle length exactly $\binom nk$, as mentioned in the first comment by Jyrki Lahtonen.

share|improve this answer
    
I've implement the Tahir Siddique algorithm referred to in your link and it projects 0,1,2, ... to an n-bit k-weight sequence. I can now use an LFSR to generate the inputs and we're done. Thankyou! Perfect! The algorithm generates 2^n-1 for too-high inputs so I can easily filter them out. Sorry for paraphrasing your answer. –  OldCurmudgeon Aug 14 '13 at 10:33
    
Thank you for implicitly indicating that somebody had used the WP page to publish their own (not very readable) code for something as simple as computing $\binom{c_k}k+\cdots+\binom{c_2}2+\binom{c_1}1$, and attach his(?) name to it. As this is not at all appropriate, I have removed the code from the WP article. –  Marc van Leeuwen Aug 14 '13 at 11:38
add comment

Here's the Java code I eventually went with. Comments/corrections welcome.

// n = digits, k = weight, m = position.
public static BigInteger combinadic(int n, int k, BigInteger m) {
  BigInteger out = BigInteger.ZERO;
  for (; n > 0; n--) {
    BigInteger y = nChooseK(n - 1, k);
    if (m.compareTo(y) >= 0) {
      m = m.subtract(y);
      out = out.setBit(n - 1);
      k -= 1;
    }
  }
  return out;
}

// Algorithm borrowed (and tweaked) from: http://stackoverflow.com/a/15302448/823393
public static BigInteger nChooseK(int n, int k) {
  if (k > n) {
    return BigInteger.ZERO;
  }
  if (k <= 0 || k == n) {
    return BigInteger.ONE;
  }
  // ( n * ( nChooseK(n-1,k-1) ) ) / k;
  return BigInteger.valueOf(n).multiply(nChooseK(n - 1, k - 1)).divide(BigInteger.valueOf(k));
}

It certainly generates k-bit numbers when given a number between ${0}$ and ${n \choose k}$.

I chose an LFSR using a tap of order sufficient to exceed ${95 \choose 15}$ (an order 57 primitive polynomial) and rejected any that did not contain the correct number of bits. With this mechanism, generating the first 1,000 n=95 k=15 combinations produced 285 rejects, a perfectly acceptable rate for me.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.