3

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.

Community
  • 1
OldCurmudgeon
  • 585
  • 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 08: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 08: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 08:32

2 Answers2

1

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.

Marc van Leeuwen
  • 115,048
  • 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
0

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.

OldCurmudgeon
  • 585