how do i write a c program to generate 44 patterns

each pattern are 32bits long, and meet three condition

1. orthogonal to each other, that mean between any tow patterns, there are 16bit are the same(0 or 1) and the other 16 bits are different(if one is 0, the other is 1)

2. every sequence should be even. it mean it has the same number of 0 and 1

3. every sequence should not have more than four consecutive identical bits

each pattern are 32bits long, and meet three condition

1. orthogonal to each other, that mean between any tow patterns, there are 16bit are the same(0 or 1) and the other 16 bits are different(if one is 0, the other is 1)

2. every sequence should be even. it mean it has the same number of 0 and 1

3. every sequence should not have more than four consecutive identical bits

For each additional pattern, loop on all the possible bit patterns and check conditions #2 and #3, iterating to the next pattern if they are not met. Otherwize, check condition #1 vs all the previously accepted patterns.

It would take someting like 2^32 * (44^2)/2 loops.

it seems that there are c(32, 16) = 32! different patterns of 32 bits of 16 1's and 16 0's. offhand, i don't know how many of these have a greatest consecutive run length of 4 bits of either type, but it certainly pares down the number of bit patterns that are valid.

for any one potential pattern, there seem to be many ways to alter the pattern in the attempt to find 43 other patterns based on this one that meet your criteria. namely:

[C(16,0)]^2 ways to change zero bits (the original pattern)

+ [C(16,1)]^2 ways to change two bits (one of which is a 0, the other a 1)

+ [C(16,2)]^2 ways to change four bits ...

+ ...

+ [C(16,16)]^2 ways to change all thirty-two bits (the original pattern NOT'ted)

since combinations fold up, (c(16, 16) == c(16, 0)), there are

2 * (sum from i=0 to i=7 of C(16, i))

ways to change any one given pattern. (i.e., lots of ways (!))

of course, not each modification will still fit your criteria (runs of four, orthogonal to each other sequence).

(i don't know whether that analysis will help in your assignment...)

nonetheless, since i don't know what you've been working on, and what general approach is expected of you, the best i can suggest is randomized algorithms. use a random alg to generate the initial pattern. if, while generating 32 0's & 1's, you find that the number doesn't match your criteria, start over. if it does, you have an initial pattern.

once you have an initial pattern, you can either run it as a brute force combinatrics alg, or again, as a randomized alg. if randomized, choose an even number from 2 to 16; that's the number of bits you're going to change. pick that many positions (assuring that you pick the same number of 1's and 0's), flip those bits, and see if your new number meets your criteria.

my instinct tells me that as you see the types of numbers that are generated, you'll get a feel for the sorts of numeric patterns in sets of numbers generated; this'll help you pare down your random algs' selection process.

also, you may want to look at the CLR Algorithms book; there's some good stuff in there (i can give you page references if you're not already using that text).

Larry

But only C(16,8)^2 of them will be orthogonal

2 * (sum from i=0 to i=7 of C(16, i)^2) will be the number that are not orthogonal

But as I said, there doesn't seem to be a set of more than 32 mutually orthogonal patterns.

A question can only have one answer.

What happened here is a rare display of professional courtesy in which no "expert" rushed to lock the question with an incomplete answer.

You can ask one of the participants to submit an answer, which you would then grade.

thanks for finishing the analysis... got a little lazy, i guess.. ;^)

ginaa: assuming this is an assignment (?), what have you been working on recently? if not, why not try the randomized approach, at least for generation of the initial pattern?

alexo: actually, i've seen this type of "expert" behavior more on some forums (sic) than others... interesting, the sub-cultures in EE...

Larry

not all will have 44 patterns which match the criteria, but certainly, they will not all be orthogonal.

perhaps you could modify your first approach: once you find a legal pattern, go that route, attempting to find patterns which are orthogonal to it. however, also continue looking for alternate solutions: other patterns which are legal but not orthogonal to other sets you've generated. to avoid excessive work while searching & backtracking, you could set up a data structure identifying which patterns you've already attempted.

larry

0000 1000 0100 0010 1011 1101 1110 1111 (base 2)

which evaluates to 138,591,727 (base 10). The largest legal pattern is the bitwise "not" of this:

1111 0111 1011 1101 0100 0010 0001 0000 (base 2)

which evaluates to 4,156,375,568 (base 10).

ginaa, you can not have more than 32 ortogonal 32-bit patterns.

( I have not mathemaic proof for this fact, but I am almoust sure )

I have a simple algorithm that bilds ortogonal patterns for given init pattern.

I send you here 32 patterns that I got when zero-pattern was taken as a first.

As you see, we have a problem with your third condition - only 16 patterns from 32

satisfied him. Now I have not algorithm to choose good init pattern, it is need to

try different things. I can send you my algorithm, it's something very stupid. I don't

know exactly it's working time, I think it's something about five hours.

1 - 00000000000000000000000000

2 - 00000000000000001111111111

3 - 00000000111111110000000011

4 - 00000000111111111111111100

5 - 00001111000011110000111100

6 - 00001111000011111111000011

7 - 00001111111100000000111111

8 - 00001111111100001111000000

9 - 00110011001100110011001100

10 - 00110011001100111100110011

11 - 00110011110011000011001111

12 - 00110011110011001100110000

13 - 00111100001111000011110000

14 - 00111100001111001100001111

15 - 00111100110000110011110011

ginaa, you can not have more than 32 ortogonal 32-bit patterns.

( I have not mathemaic proof for this fact, but I am almoust sure )

I have a simple algorithm that bilds ortogonal patterns for given init pattern.

I send you here 32 patterns that I got when zero-pattern was taken as a first.

As you see, we have a problem with your third condition - only 16 patterns from 32

satisfied him. Now I have not algorithm to choose good init pattern, it is need to

try different things. I can send you my algorithm, it's something very stupid. I don't

know exactly it's working time, I think it's something about five hours.

1 - 00000000000000000000000000

2 - 00000000000000001111111111

3 - 00000000111111110000000011

4 - 00000000111111111111111100

5 - 00001111000011110000111100

6 - 00001111000011111111000011

7 - 00001111111100000000111111

8 - 00001111111100001111000000

9 - 00110011001100110011001100

10 - 00110011001100111100110011

11 - 00110011110011000011001111

12 - 00110011110011001100110000

13 - 00111100001111000011110000

14 - 00111100001111001100001111

15 - 00111100110000110011110011

2 - 00000000000000001111111111

3 - 00000000111111110000000011

4 - 00000000111111111111111100

5 - 00001111000011110000111100

6 - 00001111000011111111000011

7 - 00001111111100000000111111

8 - 00001111111100001111000000

9 - 00110011001100110011001100

10 - 00110011001100111100110011

11 - 00110011110011000011001111

12 - 00110011110011001100110000

13 - 00111100001111000011110000

14 - 00111100001111001100001111

15 - 00111100110000110011110011

16 - 00111100110000111100001100

17 - 01010101010101010101010101

18 - 01010101010101011010101010

19 - 01010101101010100101010110

20 - 01010101101010101010101001

21 - 01011010010110100101101001

22 - 01011010010110101010010110

23 - 01011010101001010101101010

24 - 01011010101001011010010101

25 - 01100110011001100110011001

26 - 01100110011001101001100110

27 - 01100110100110010110011010

28 - 01100110100110011001100101

29 - 01101001011010010110100101

30 - 01101001011010011001011010

31 - 01101001100101100110100110

32 - 0110100110010110100101100

What does the second condition means - that in every pattern must be 16 zeroes and

16 1's?

What's a PN sequence?

I shouldn't say too much if this is an assignment. but there are several optimizations that could make on a search.

It shouldn't take too many of them to cut the search down to a few hours, which seems reasonably practical for a brute force search.

(you might also try testing your algorithm on a smaller problem.

how fast can you find 16 orthogonal 16 bit patterns?)

say, to require 15 or more bits different between any two patterns

rather than requireing exactly 16 different.

(although some of those sequences may still fail condition 3)

Are the requirements for distingishing patterns between the 11 channels the same as for distinguishing among the 4 states in each channel?

It looks like there are sets of at least 48 patterns which satisfy 3, 2, and between any two patterns, either 16 bits are different, or all 32 bits are different.

I try to find something more suitable.

You should be able to get at least 2 more to satisfy condition 3 by shifting the bits around a little, giving you 27 good sequences.

But I still don't think you can get more than 32 patterns to satisfy condition 1,

unless you also allow patterns to differ in all 32 bits.

(which seems a reasonable condition at least within each group of 4 signals,

while retaining 16 bit orthogonality between the 11 (or 13) channels)

I've started a brute force search to find a 28th run limited pattern,

If such a set exists, it, along with the complements of those patterns, should give you 14 two bit channels.

than your patterns generation does not seem to be the problem.

than your patterns generation does not seem to be the problem.

but they are, only more than 4 are not allowed. So the example has 24 good sequences:

5 and 10-32.

random numbers and checks them for the criteria. Note that it

also has an additional constraint - it guarantees that the

numbers are unique. However, a problem I've noticed is that it

sometimes will not respond. It should start printing out numbers

immediately, but if it hasn't, you can kill it and restart it.

I've had to do this a few times (sometimes 3 times in a row) to

get it to work. Can someone else debug this?

------

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#define COUNT 44

void bprint(unsigned int i, unsigned int l) {

int j, cnt = 0, ones = 0, xor = i ^ l;

for (j = 31; j >= 0; j--) {

if (i & (1 << j))

printf ("1"),ones++;

else

printf ("0");

if (xor & (1 << j))

cnt++;

}

printf (" %d diff, %d ones\n", cnt, ones);

}

int main() {

unsigned int i, j, last = 0, xor;

int cnt, cons[2], bit, xcnt, num = 0;

unsigned int alr[COUNT];

srand(time(NULL));

while(1) {

start:

i = (rand() & 0xFFFF) | ((rand() & 0xFFFF) << 16);

if (!last)

last = i;

for (j = 0; j < num; j++)

if (alr[j] == i)

goto done;

xor = i ^ last;

xcnt = cnt = cons[0] = cons[1] = 0;

for (j = 0; j < 32; j++) {

if ((bit = (i & (1 << j)) != 0))

cnt++;

cons[1 - bit] = 0;

if (++cons[bit] > 4)

goto start;

if (xor & (1 << j))

if (++xcnt > 16)

goto start;

}

if (cnt == 16 && xcnt == 16) {

bprint (i, last);

alr[num++] = last = i;

if (num == COUNT)

exit(0);

}

}

done:

return 0;

}

And the requirement is that any signal is orthogonal to any signal on the next 6 channels?

If so, then you should only need orthogonality between signals on different channels,

and you should be able to go through a sequence of 27 channels without generating a mirror.

(But I'm now also wondering if there may be a furthur requirement that a signal not look to similar to another signal shifted by a few bits?

And whether you'd also need to avoid 4 consecutive bits the same when one sequence follows another, as with tulin's #10 followed by #5?)

to check of two patterns are orthogonal:

d=p^PN[j];

d-=(d>>1)&0x55555555;

d=(d&0x33333333) + ((d>>2)&0x33333333);

d=(d&0x0f0f0f0f) + ((d>>4)&0x0f0f0f0f);

d=(d&0x00ff00ff) + ((d>>8)&0x00ff00ff);

d=(d&0xffff) + ((d>>16)&0xffff);

if( d != 16 ){ break; }

To check that a pattern has no more than 4 consecutive the same:

d = p&(p1=p>>1);

d &= (d>>2)&(p4=p>>4);

if( (d&0x0fffffff) != 0 ){ continue; }

d = p|p1;

d |= (d>>2)|p4;

if( (d&0x0fffffff) != 0x0fffffff ){ continue; }

to increment to the next larger number with the same number of bits set:

p1=p&~(p>>1);

p1&=-p1;

d=p&(p1-1);

p+=p1-d+d/(p&-p);

But much bigger opimizations should be possible if you observe that

the xor of any two orthogonal patterns is another orthogonal pattern.

This means that any set of 28 orthogonal patterns must be part of a set of 32 orthogonal patterns,

which will in fact be the same set as tulin's set, modulo permutations of the bit order.

So, to serch for a set of 28 orthogonal patterns with no more than 4 consecutive bits the same, it suffices to search through the 32! permutations of the numbers 0-31

(for this, it may be faster to pull another trick, and treat each int as a column in the table, rather than a row)

the requirment that every pattern must be ortogonal to ANYONE

other. I dont know, where an error in your logic becouse it

was hard to understand how your algorithm exactly works.

I took output of your algorithm and just have sorted it. This

is a ten first patterns:

00001101001111010010010011

00001101101100010101011010

00011011011101110001001000

00100100101111000101101010

00101001001011000101010111

00101010011011010101111001

00101101111011100100001001

00111001111001110100100101

01010000111011110010101010

01011101101100110110001010

It is simple to see that difference between first and second,

second and third are already not 16.

orthagonal. Let me see if I can fix that...

although you are correct that the worst case is very bad.

Can you quantify what "too regular" means?

Do you require that any two shifted patterns remain orthogonal?

With a more reasonable criterion, say, that the difference between any 32 bit subsequences must be between 8 and 24, then we may be able to help you.

We may even be able to search for a sequence that makes all the differences as close to 16 as possible, but we'll never get them all to be exactly 16.

01101001100101100110100110

01100110100110011001100101

01100110011001101001100110

01100110011001100110011001

01011010010110100101101001

01010101101010101010101001

01010101101010100101010110

01010101010101011010101010

01010101010101010101010101

00111100001111000011110000

00110011110011001100110000

00110011110011000011001111

00110011001100111100110011

00110011001100110011001100

00001111000011110000111100

00001111010110101111000010

00011000111001110001100011

00011110001011011110000111

00100100110110110010010011

00101101111000011101001000

00111100100101101100001101

01000010101111010100001010

01001011100001111011010001

01011010111100001010010100

01101001001111001001011011

01111000010010111000011110

20- pattern: 1825361100 01101100 11001100 11001100 11001100

21- pattern: 1894838513 01110000 11110000 11110000 11110001

22- pattern: 1825379123 01101100 11001101 00010011 00110011

23- pattern: 1894854414 01110000 11110001 00101111 00001110

24- pattern: 1829956883 01101101 00010010 11101101 00010011

25- pattern: 1898893614 01110001 00101110 11010001 00101110

26- pattern: 1829974764 01101101 00010011 00110010 11101100

27- pattern: 1898909393 01110001 00101111 00001110 11010001

28- pattern: 473709629 00011100 00111100 00111100 00111101

19 another 28-sequences, but I did not succeed to find even one 29-sequence, so it looks like the 28 is the maximum rank of solution to your problem.

Good luck,

Tulin

And given your requirements of 4 signals per channel, and orthogonalith with the next n channels in sequence,

it still seems like you should be able to use the complments within a channel.

it will still be orthogonal with all other channels. shis seems to satisfy the spec you describe on Sunday, July 19 1998 - 06:47PM PDT

(the same signal on the same channel will not be orthogonal to itself, so it seems you lose orthogonality once you repeat a channel anyway)

Are you just sensing transitions? How does that explain the requirement of exactly 16 differences between sequences rather than allowing 14 or 18?

(or if you're looking at transitions, maybe you really preferred no two sequences with more than 4 consecutive bits the same between them?)

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.