Solved

find PN sequence

Posted on 1998-07-13
58
411 Views
Last Modified: 2008-02-01
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
0
Comment
Question by:ginaa
  • 16
  • 16
  • 15
  • +4
58 Comments
 
LVL 11

Expert Comment

by:alexo
ID: 1251624
You can use the brute force approach.

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.

0
 

Author Comment

by:ginaa
ID: 1251625
I have done like that
but it run half a day, just generate 10 patterns
so, do y have more efficent algorithm
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251626
This doesn't seem to be possible. I can only find a set of 32 such patterns.
0
 
LVL 1

Expert Comment

by:Staplehead
ID: 1251627
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
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251628
(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.
0
 

Author Comment

by:ginaa
ID: 1251629
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
0
 
LVL 11

Expert Comment

by:alexo
ID: 1251630
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.
0
 
LVL 1

Expert Comment

by:Staplehead
ID: 1251631
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
0
 

Author Comment

by:ginaa
ID: 1251632
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

0
 
LVL 1

Expert Comment

by:Staplehead
ID: 1251633
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
0
 
LVL 1

Expert Comment

by:Musashi
ID: 1251634
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).
0
 
LVL 1

Expert Comment

by:Staplehead
ID: 1251635
assuming, of course, that we interpret the bit pattern as an unsigned... ;^)
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251636
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 - 00000000000000000000000000000000
2 - 00000000000000001111111111111111
3 - 00000000111111110000000011111111
4 - 00000000111111111111111100000000
5 - 00001111000011110000111100001111
6 - 00001111000011111111000011110000
7 - 00001111111100000000111111110000
8 - 00001111111100001111000000001111
9 - 00110011001100110011001100110011
10 - 00110011001100111100110011001100
11 - 00110011110011000011001111001100
12 - 00110011110011001100110000110011
13 - 00111100001111000011110000111100
14 - 00111100001111001100001111000011
15 - 00111100110000110011110011000011
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251637
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 - 00000000000000000000000000000000
2 - 00000000000000001111111111111111
3 - 00000000111111110000000011111111
4 - 00000000111111111111111100000000
5 - 00001111000011110000111100001111
6 - 00001111000011111111000011110000
7 - 00001111111100000000111111110000
8 - 00001111111100001111000000001111
9 - 00110011001100110011001100110011
10 - 00110011001100111100110011001100
11 - 00110011110011000011001111001100
12 - 00110011110011001100110000110011
13 - 00111100001111000011110000111100
14 - 00111100001111001100001111000011
15 - 00111100110000110011110011000011
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251638
1 - 00000000000000000000000000000000
2 - 00000000000000001111111111111111
3 - 00000000111111110000000011111111
4 - 00000000111111111111111100000000
5 - 00001111000011110000111100001111
6 - 00001111000011111111000011110000
7 - 00001111111100000000111111110000
8 - 00001111111100001111000000001111
9 - 00110011001100110011001100110011
10 - 00110011001100111100110011001100
11 - 00110011110011000011001111001100
12 - 00110011110011001100110000110011
13 - 00111100001111000011110000111100
14 - 00111100001111001100001111000011
15 - 00111100110000110011110011000011
16 - 00111100110000111100001100111100
17 - 01010101010101010101010101010101
18 - 01010101010101011010101010101010
19 - 01010101101010100101010110101010
20 - 01010101101010101010101001010101
21 - 01011010010110100101101001011010
22 - 01011010010110101010010110100101
23 - 01011010101001010101101010100101
24 - 01011010101001011010010101011010
25 - 01100110011001100110011001100110
26 - 01100110011001101001100110011001
27 - 01100110100110010110011010011001
28 - 01100110100110011001100101100110
29 - 01101001011010010110100101101001
30 - 01101001011010011001011010010110
31 - 01101001100101100110100110010110
32 - 0110100110010110100101100
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251639
Sorry, I have connection failure here. The last pattern is
32 - 01101001100101101001011001101001
0
 

Author Comment

by:ginaa
ID: 1251640
your mean i have 32 patterns orthogonal to each other at most?
if i consider all three conditions, then it'll be more less!
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251641
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?
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251642
That would be the same as saying that there are 45 orthogonal patterns including 0 (or ~0)
What's a PN sequence?
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251643
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?)
0
 

Author Comment

by:ginaa
ID: 1251644
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

0
 

Author Comment

by:ginaa
ID: 1251645
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

0
 
LVL 84

Expert Comment

by:ozo
ID: 1251646
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.
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251647
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)
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251648
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.
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251649
My patterns are given above gave you 17 good sequences: number 9 and numbers 17-32.
I try to find something more suitable.
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251650
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.
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251651
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.
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251652
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.
0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 1

Expert Comment

by:tulin
ID: 1251653
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.
0
 

Author Comment

by:ginaa
ID: 1251654
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
0
 
LVL 1

Expert Comment

by:rgmisra
ID: 1251655
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;
}

0
 
LVL 84

Expert Comment

by:ozo
ID: 1251656
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?)
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251657
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)
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251658
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:
00001101001111010010010011011101
00001101101100010101011010110101
00011011011101110001001000111001
00100100101111000101101010110110
00101001001011000101010111011011
00101010011011010101111001101000
00101101111011100100001001010110
00111001111001110100100101100100
01010000111011110010101010101100
01011101101100110110001010001001
It is simple to see that difference between first and second,
second and third are already not 16.
0
 
LVL 1

Expert Comment

by:rgmisra
ID: 1251659
Oops... I missed that every set of 2 numbers was supposed to be
orthagonal. Let me see if I can fix that...
0
 
LVL 1

Expert Comment

by:Musashi
ID: 1251660
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:)
0
 
LVL 1

Expert Comment

by:rgmisra
ID: 1251661
At best, it can be *much* better than a brute force attack,
although you are correct that the worst case is very bad.
0
 

Author Comment

by:ginaa
ID: 1251662
Sorry, I think the problem is need another solution

0
 

Author Comment

by:ginaa
ID: 1251663
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....

0
 
LVL 84

Expert Comment

by:ozo
ID: 1251664
I was afraid of that...
Can you quantify what "too regular" means?
Do you require that any two shifted patterns remain orthogonal?
0
 

Author Comment

by:ginaa
ID: 1251665
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

0
 
LVL 84

Expert Comment

by:ozo
ID: 1251666
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.
0
 

Author Comment

by:ginaa
ID: 1251667
i think, that requirement is too mush.
if the pattern not looks like 0x33333333,  0x66666666,....
then it'll be acceptible

0
 
LVL 1

Expert Comment

by:tulin
ID: 1251668
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.
0
 

Author Comment

by:ginaa
ID: 1251669
that's great if you can show for us
if can find 28-sequence that will be better

0
 
LVL 84

Expert Comment

by:ozo
ID: 1251670
01101001011010010110100101101001
01101001100101100110100110010110
01100110100110011001100101100110
01100110011001101001100110011001
01100110011001100110011001100110
01011010010110100101101001011010
01010101101010101010101001010101
01010101101010100101010110101010
01010101010101011010101010101010
01010101010101010101010101010101
00111100001111000011110000111100
00110011110011001100110000110011
00110011110011000011001111001100
00110011001100111100110011001100
00110011001100110011001100110011
00001111000011110000111100001111
00001111010110101111000010100101
00011000111001110001100011100111
00011110001011011110000111010010
00100100110110110010010011011011
00101101111000011101001000011110
00111100100101101100001101101001
01000010101111010100001010111101
01001011100001111011010001111000
01011010111100001010010100001111
01101001001111001001011011000011
01111000010010111000011110110100

0
 
LVL 1

Accepted Solution

by:
tulin earned 200 total points
ID: 1251671
Get 28-sequence!

1- pattern: 473818050            00011100 00111101 11100011 11000010
2- pattern: 501358050            00011101 11100010 00011101 11100010
3- pattern: 501465629            00011101 11100011 11000010 00011101
4- pattern: 644245095            00100110 01100110 01100110 01100111
5- pattern: 978999898            00111010 01011010 01011010 01011010
6- pattern: 644331928            00100110 01100111 10111001 10011000
7- pattern: 979076517            00111010 01011011 10000101 10100101
8- pattern: 666388408            00100111 10111000 01000111 10111000
9- pattern: 998538117            00111011 10000100 01111011 10000101
10- pattern: 666474567            00100111 10111001 10011000 01000111
11- pattern: 998614138            00111011 10000101 10100100 01111010
12- pattern: 1252698795            01001010 10101010 10101010 10101011
13- pattern: 1452709526            01010110 10010110 10010110 10010110
14- pattern: 1252750676            01001010 10101011 01110101 01010100
15- pattern: 1452755305            01010110 10010111 01001001 01101001
16- pattern: 1265929076            01001011 01110100 10001011 01110100
17- pattern: 1464383305            010101110 1001000 10110111 01001001
18- pattern: 1265980555            01001011 01110101 01010100 10001011
19- pattern: 1464428726            01010111 01001001
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251672
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
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251673
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
0
 
LVL 1

Expert Comment

by:tulin
ID: 1251674
P.S. In my answer first comes decimal form of an pattern, and then binary form ( 4 group of 8 bits for every pattern )
0
 

Author Comment

by:ginaa
ID: 1251675
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 ?

0
 
LVL 84

Expert Comment

by:ozo
ID: 1251676
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.
0
 

Author Comment

by:ginaa
ID: 1251677
complement won't be orthogonal with the original sequence, are they?
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251678
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)
0
 

Author Comment

by:ginaa
ID: 1251679
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.
0
 
LVL 84

Expert Comment

by:ozo
ID: 1251680
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?)
0
 

Author Comment

by:ginaa
ID: 1251681
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.
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now