ginaa
asked on
find PN sequence
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
ASKER
I have done like that
but it run half a day, just generate 10 patterns
so, do y have more efficent algorithm
but it run half a day, just generate 10 patterns
so, do y have more efficent algorithm
This doesn't seem to be possible. I can only find a set of 32 such patterns.
ginaa,
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
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
(sum from i=0 to i=16 of C(16, i)^2) is, of course, c(32, 16) = 32!/(16!(32-16)!)
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.
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.
ASKER
thanks for your time
but i hope some one can give me some surprise result
so i just reserve these point for 2~3 days
if there is no further answer, i will accept these comment
by the way, how do i grade the experts, i can't find option
but i hope some one can give me some surprise result
so i just reserve these point for 2~3 days
if there is no further answer, i will accept these comment
by the way, how do i grade the experts, i can't find option
You can only grade answers, not comments.
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.
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.
oxo,
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
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
ASKER
I ever wrote tow programs to do the job
1. recursive search legal pattern, each new pattern must orthogonal with fixed patterns. but, i got 15 patterns at most.
2. exhaustive search. until now, it take about two days(still running) i got 15 patterns too
1. recursive search legal pattern, each new pattern must orthogonal with fixed patterns. but, i got 15 patterns at most.
2. exhaustive search. until now, it take about two days(still running) i got 15 patterns too
aahhh... oxo, correct me if i'm wrong here, but intuitively, it seems that there should be a number of solutions to this problem.
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
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
The smallest legal pattern (which could be used as a seed pattern) is, of course:
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).
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).
assuming, of course, that we interpret the bit pattern as an unsigned... ;^)
Hi for everyone!
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
Hi for everyone!
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
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
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
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
Sorry, I have connection failure here. The last pattern is
32 - 01101001100101101001011001
32 - 01101001100101101001011001
ASKER
your mean i have 32 patterns orthogonal to each other at most?
if i consider all three conditions, then it'll be more less!
if i consider all three conditions, then it'll be more less!
Probably; but my be it is possible to find 32 ortogalal patterns satisfied to all criteria.
What does the second condition means - that in every pattern must be 16 zeroes and
16 1's?
What does the second condition means - that in every pattern must be 16 zeroes and
16 1's?
That would be the same as saying that there are 45 orthogonal patterns including 0 (or ~0)
What's a PN sequence?
What's a PN sequence?
Maybe the problem was supposed to be to find 24, not 44 patterns?
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?)
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?)
ASKER
yes, condition 2 means there are 16 zero and 16 one.
the problem is a key point for a project of my job
pn sequence is used in spread spectrum wireless communication
the sst chip i use, it encode two bits(00, 01, 10, 11) to 32 bits sequence
i use 11 channels in my project, if all sequence fit all criteria, it will have great feature for error correction
so i hope can find 4*11=44 sequence.
at least i need 28 sequence(7 set). in that situation, i can still promise the good feature
but now i can find 15 sequence at most
the problem is a key point for a project of my job
pn sequence is used in spread spectrum wireless communication
the sst chip i use, it encode two bits(00, 01, 10, 11) to 32 bits sequence
i use 11 channels in my project, if all sequence fit all criteria, it will have great feature for error correction
so i hope can find 4*11=44 sequence.
at least i need 28 sequence(7 set). in that situation, i can still promise the good feature
but now i can find 15 sequence at most
ASKER
yes, condition 2 means there are 16 zero and 16 one.
the problem is a key point for a project of my job
pn sequence is used in spread spectrum wireless communication
the sst chip i use, it encode two bits(00, 01, 10, 11) to 32 bits sequence
i use 11 channels in my project, if all sequence fit all criteria, it will have great feature for error correction
so i hope can find 4*11=44 sequence.
at least i need 28 sequence(7 set). in that situation, i can still promise the good feature
but now i can find 15 sequence at most
the problem is a key point for a project of my job
pn sequence is used in spread spectrum wireless communication
the sst chip i use, it encode two bits(00, 01, 10, 11) to 32 bits sequence
i use 11 channels in my project, if all sequence fit all criteria, it will have great feature for error correction
so i hope can find 4*11=44 sequence.
at least i need 28 sequence(7 set). in that situation, i can still promise the good feature
but now i can find 15 sequence at most
For error correction. you should be able to relax condition 1,
say, to require 15 or more bits different between any two patterns
rather than requireing exactly 16 different.
say, to require 15 or more bits different between any two patterns
rather than requireing exactly 16 different.
If you can accept 16 or more differences between patterns, then there do exist sets of 44 sequences which can correct any 7 bit errors, and detect any 8 bit errors.
(although some of those sequences may still fail condition 3)
(although some of those sequences may still fail condition 3)
so PN means pseudo-noise?
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.
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.
My patterns are given above gave you 17 good sequences: number 9 and numbers 17-32.
I try to find something more suitable.
I try to find something more suitable.
What's wrong with number 5 and numbers 10-16?
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.
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.
ginaa, if you really can relax condition 1 as ozo proposed ( and I think he is right )
than your patterns generation does not seem to be the problem.
than your patterns generation does not seem to be the problem.
ginaa, if you really can relax condition 1 as ozo proposed ( and I think he is right )
than your patterns generation does not seem to be the problem.
than your patterns generation does not seem to be the problem.
my mistake was that I thought that 4 consecutive identical bit are not already allowed,
but they are, only more than 4 are not allowed. So the example has 24 good sequences:
5 and 10-32.
but they are, only more than 4 are not allowed. So the example has 24 good sequences:
5 and 10-32.
ASKER
Thanks for everyone
If differences between patterns are not exactly 16, then they are not orthogonal. I not really know why, but these 3 conditions are required in the spec for the SST chip.
if can't find 11 set of PN, then 7 set is ok
fro 11 channel, i can arrange as follow
channel
0 1 2 3 4 5 6 7 8 9 a
7 pn set
0 1 2 3 4 5 6 0 1 2 3
but if less the 7 set, such as 6 set, then
6 pn set
0 1 2 3 4 5 0 1 2 3 4
my rf engineer say, channel 0 & 3 will generate a mirror signal at position 6, and the signal will be same as 0 but smaller.
the problem is channel use the same pn set as channel 6, it'll make 6 work not properlly
so i need 28 sequence
If differences between patterns are not exactly 16, then they are not orthogonal. I not really know why, but these 3 conditions are required in the spec for the SST chip.
if can't find 11 set of PN, then 7 set is ok
fro 11 channel, i can arrange as follow
channel
0 1 2 3 4 5 6 7 8 9 a
7 pn set
0 1 2 3 4 5 6 0 1 2 3
but if less the 7 set, such as 6 set, then
6 pn set
0 1 2 3 4 5 0 1 2 3 4
my rf engineer say, channel 0 & 3 will generate a mirror signal at position 6, and the signal will be same as 0 but smaller.
the problem is channel use the same pn set as channel 6, it'll make 6 work not properlly
so i need 28 sequence
This program does what you want. It generates a sequence of
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;
}
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;
}
So the channels go in sequence?
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?)
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?)
Some useful tricks in writing a brute force search:
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)
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)
rgmisra, your algorithm does not work right. It does not perform
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.
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.
Oops... I missed that every set of 2 numbers was supposed to be
orthagonal. Let me see if I can fix that...
orthagonal. Let me see if I can fix that...
rgmisa, trying to solve this problem via random number generation is (at best) no better than a brute force attack, and in general is very very much worse (and the worse case is really bad:)
At best, it can be *much* better than a brute force attack,
although you are correct that the worst case is very bad.
although you are correct that the worst case is very bad.
ASKER
Sorry, I think the problem is need another solution
ASKER
Hi,
one things more
if pattern is too regular, then it may not fit my project.
such as 0x33333333 and 0x99999999. they meet all conditions, but
if they shift one bit, then look the same, so....
one things more
if pattern is too regular, then it may not fit my project.
such as 0x33333333 and 0x99999999. they meet all conditions, but
if they shift one bit, then look the same, so....
I was afraid of that...
Can you quantify what "too regular" means?
Do you require that any two shifted patterns remain orthogonal?
Can you quantify what "too regular" means?
Do you require that any two shifted patterns remain orthogonal?
ASKER
i just find the problem, but not yet test in hardware. so i don't know is it will have an effect.
i mean in this case, all nibbles in the sequence is the same
if it shift or rotate 1 or 2 bit can generate another sequence that fit all condition, then the pattern is not good enough
such 0x333..., 0x666... or 0x666..., 0xccc... or 0xccc..., 0x999... or 0x999..., 0x333...
i feel something wrong, but can't prove
i mean in this case, all nibbles in the sequence is the same
if it shift or rotate 1 or 2 bit can generate another sequence that fit all condition, then the pattern is not good enough
such 0x333..., 0x666... or 0x666..., 0xccc... or 0xccc..., 0x999... or 0x999..., 0x333...
i feel something wrong, but can't prove
So, if what you really want is a sequence of 1408 bits, such that any 32 consecutive bits from that sequence differs in exactly 16 places from any other 32 consecutive bits, then I'm pretty sure you'll never find such a sequence.
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.
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.
ASKER
i think, that requirement is too mush.
if the pattern not looks like 0x33333333, 0x66666666,....
then it'll be acceptible
if the pattern not looks like 0x33333333, 0x66666666,....
then it'll be acceptible
I have found a sequence of 26 patterns satisfied to all criteria ( even not one, a lot ). I can publish it here, if you wish. May be I'll found a 28-sequence soon.
ASKER
that's great if you can show for us
if can find 28-sequence that will be better
if can find 28-sequence that will be better
01101001011010010110100101
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
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
19- pattern: 1464428726 01010111 01001001 01101000 10110110
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
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
If you wish an algorithm, give me your e-mail and I'll send you, becouse EE-way I can't send a big parts of text (?), I think the problem is in our proxy-server. I have also found
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
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
P.S. In my answer first comes decimal form of an pattern, and then binary form ( 4 group of 8 bits for every pattern )
ASKER
some of them look like a little regular. but that's ok
all of them meet 3 requirements. i think it's enough
i appreciate if you can give me the algorithm
my e-mail : william@ellcon.com.tw
the algorithm can generate not only one 28-sequences ?
all of them meet 3 requirements. i think it's enough
i appreciate if you can give me the algorithm
my e-mail : william@ellcon.com.tw
the algorithm can generate not only one 28-sequences ?
which would be 56 sequences if you include their complements.
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.
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.
ASKER
complement won't be orthogonal with the original sequence, are they?
That's right, but if the original sequence and the complement is used in the same 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)
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)
ASKER
Well, I guess the complement can be try.
In our system, we hope just with one link(a set of pn) in a channel.
These mirror signals are a side effect of RF.
We hope the mirror PN won't be recognized as a legal signal. If so, it will bother the normal signal to be recognized.
So, the same PN set in same channel is not allow.
With 7 set PN, the mirror won't be appear in the same channel with same PN(could be neighborhood, but not the same channel).
But 6 set PN will have the situation.
In our system, we hope just with one link(a set of pn) in a channel.
These mirror signals are a side effect of RF.
We hope the mirror PN won't be recognized as a legal signal. If so, it will bother the normal signal to be recognized.
So, the same PN set in same channel is not allow.
With 7 set PN, the mirror won't be appear in the same channel with same PN(could be neighborhood, but not the same channel).
But 6 set PN will have the situation.
Hmm, if the mirror signal is a side effect of RF, how is the sequence modulated onto the signal?
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?)
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?)
ASKER
I am not sure why 16.
But the 3 conditions are required by document of SST chip that I used.
And the 1st is orthogonal(exactly 16 different).
Spread spectrum expand 00, 01, 10, 11 into 32bits sequence.
if any noise confuse few bits, SST can recognize it as one of 4 sequences. So if all 4 sequences are orthogonal to each other.
I guess it will have good feature to identify.
But the 3 conditions are required by document of SST chip that I used.
And the 1st is orthogonal(exactly 16 different).
Spread spectrum expand 00, 01, 10, 11 into 32bits sequence.
if any noise confuse few bits, SST can recognize it as one of 4 sequences. So if all 4 sequences are orthogonal to each other.
I guess it will have good feature to identify.
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.