Java code for generating m-sequences

I am working with Java and Eclipse to generate Gold Codes. 

I found about three different codes written in C++ on the internet for
generating the m-sequences. the problem is that I'm new to Java and even
though I am translating these codes into Java environment, which is a very
irritating process and time-consuming too (four weeks since I started).
Unfortunately, non of them is seems to be working until now ..

I am now looking for Java code for generating the m-sequence, would you
please help me, thanks 

On Tue, 05 Feb 2013 13:04:48 -0600, SudanBoy wrote:

> I am working with Java and Eclipse to generate Gold Codes.
> 
> I found about three different codes written in C++ on the internet for
> generating the m-sequences. the problem is that I'm new to Java and even
> though I am translating these codes into Java environment, which is a
> very irritating process and time-consuming too (four weeks since I
> started). Unfortunately, non of them is seems to be working until now ..
> 
> I am now looking for Java code for generating the m-sequence, would you
> please help me, thanks

I don't think you're going to get any takers.

I'm pretty sure that the "m-sequence" in your title means the output of 
an LFSR.  If this is the case, then actually generating the sequence 
should be pretty straight forward.  My inclination is to think that if 
you cannot generate the sequence, then you cannot use it -- so it's a 
very good exercise to keep working at this until you can generate the 
sequence.

And, of course, no one is going to write you the code for free.

So, here's a suggested sequence of steps to go through:

1: Make sure that you can generate a very short sequence by hand.  When 
I'm doing this kind of stuff and my software isn't working, I work out 
the 15 bit sequence for a 4-bit LFSR (I think 10011 generates a maximal-
length code, but you'll want to check that).

2: Choose a programming language that you _are_ familiar with, and try to 
generate that same n = 4 sequence.  Verify it against your hand-done one 
(in my case, I'll find out that I messed up the hand-done version half 
the time).

3: Extend that to the number of bits that you need.

4: Now that you thoroughly understand the issues, make it work in Java.

Alternately, if you can point to the specific area where you're having 
problems then let us know and we'll help with just those areas.  But keep 
in mind that it really helps if you already have a firm grasp of how to 
generate these sequences.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

Tim Wescott <tim@seemywebsite.please> wrote:

(snip)
> I don't think you're going to get any takers.
 
> I'm pretty sure that the "m-sequence" in your title means the output of 
> an LFSR.  If this is the case, then actually generating the sequence 
> should be pretty straight forward.  My inclination is to think that if 
> you cannot generate the sequence, then you cannot use it -- so it's a 
> very good exercise to keep working at this until you can generate the 
> sequence.
 
> And, of course, no one is going to write you the code for free.

Sometimes I will write code for posts up to about 10 lines.
I don't know if this could be done in 10, though.

If he posted a little C++ I might try it.
 
> So, here's a suggested sequence of steps to go through:
 
> 1: Make sure that you can generate a very short sequence by hand.  When 
> I'm doing this kind of stuff and my software isn't working, I work out 
> the 15 bit sequence for a 4-bit LFSR (I think 10011 generates a maximal-
> length code, but you'll want to check that).

There is a good discussion of primitive polynomicals in Numerical
Recipes in (appropriate language). 
 
> 2: Choose a programming language that you _are_ familiar with, and try to 
> generate that same n = 4 sequence.  Verify it against your hand-done one 
> (in my case, I'll find out that I messed up the hand-done version half 
> the time).

Considering the two different definitions for LFSR, and even with that,
remembering which polynomial bit goes on which end, half sounds
about right.

You can either input to the shift register the XOR (or sometimes
XNOR) of specified outputs, or, put XOR gates between the specified
FF's fed the shift register output. The former is more convenient
using hardware shift registers, the latter in software.
 
> 3: Extend that to the number of bits that you need.
> 
> 4: Now that you thoroughly understand the issues, make it work in Java.
> 
> Alternately, if you can point to the specific area where you're having 
> problems then let us know and we'll help with just those areas.  But keep 
> in mind that it really helps if you already have a firm grasp of how to 
> generate these sequences.

-- glen

On Tuesday, February 5, 2013 4:44:00 PM UTC-6, glen herrmannsfeldt wrote:
> ...........
>  

> 
> Considering the two different definitions for LFSR, and even with that,
> 
> remembering which polynomial bit goes on which end, half sounds
> 
> about right.
> 


Fortunately, if the feedback polynomial is a primitive
polynomial, so is its reverse (e.g. 11001 instead of
Tim's 10011), and so as long as one uses the same 
convention throughout, it does not matter which polynomial
bit goes on which end,


Dilip Sarwate

dvsarwate <dvsarwate@yahoo.com> wrote:

(snip, I wrote)
>> Considering the two different definitions for LFSR, and even with that,
>> remembering which polynomial bit goes on which end, half sounds
>> about right.
 
> Fortunately, if the feedback polynomial is a primitive
> polynomial, so is its reverse (e.g. 11001 instead of
> Tim's 10011), 

I didn't know that!

> and so as long as one uses the same convention throughout, 
> it does not matter which polynomial bit goes on which end,

But if you are trying to implement a standard, such as the
ethernet CRC generator, you have to do it the right way.

Also, initialize it right. I believe ethernet initializes
to all 1's. 

-- glen

On 2/6/13 10:43 PM, glen herrmannsfeldt wrote:
> dvsarwate<dvsarwate@yahoo.com>  wrote:
>
> (snip, I wrote)
>>> Considering the two different definitions for LFSR, and even with that,
>>> remembering which polynomial bit goes on which end, half sounds
>>> about right.
>
>> Fortunately, if the feedback polynomial is a primitive
>> polynomial, so is its reverse (e.g. 11001 instead of
>> Tim's 10011),
>
> I didn't know that!

i said here the other day (in the "Brain going numb" thread) that i 
learn something new every day.  (i think that might be true, but who 
knows? maybe there are days that i learn squat.)  but even so, it's nice 
to know that i'm not alone.  the Knuth (or was it Golomb?) 
Shift-Register Sequences book has a few of these useful little theorems. 
  there are other theorems that relate the two different ways of doing 
it (one where multiple taps are XORed to become a single bit to feed 
back to the input of the shift register, and the other where you XOR an 
entire word if a "1" falls off the edge of the shift).  and the most 
important little theorem is when you take two different "rotations" of 
the same maximum-length sequence and XOR them together, the result is 
the same sequence shifted by some other amount (unless the two XORed 
sequences are exactly the same, then the result are only zeros).

>
>> and so as long as one uses the same convention throughout,
>> it does not matter which polynomial bit goes on which end,
>
> But if you are trying to implement a standard, such as the
> ethernet CRC generator, you have to do it the right way.

you have to do it according to the promulgated convention.  whether 
that's the "right" way or not.

> Also, initialize it right. I believe ethernet initializes
> to all 1's.

and that's a convention too.  as long as it's not all 0's, anything is good.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Wednesday, February 6, 2013 9:43:53 PM UTC-6, glen herrmannsfeldt wrote:

> 
> But if you are trying to implement a standard, such as the
> 
> ethernet CRC generator, you have to do it the right way.
> 
> 
> 
> Also, initialize it right. I believe ethernet initializes
> 
> to all 1's. 
> 

True, though as r b-j points out, what one has
to do is follow the convention used in the standard
in order to maintain compatibility, regardless of
whether one thinks it is the right way or not.
I am sure all left-handed people feel that the
Latin word describing their condition is poorly
chosen, and that they are just as dextrous as the
right-handed folks and not at all sinister, that
is, right-handed is not necessarily the same as
right-minded....

Dilip Sarwate

On Thu, 07 Feb 2013 16:09:36 -0800, dvsarwate wrote:

> On Wednesday, February 6, 2013 9:43:53 PM UTC-6, glen herrmannsfeldt
> wrote:
> 
> 
>> But if you are trying to implement a standard, such as the
>> 
>> ethernet CRC generator, you have to do it the right way.
>> 
>> 
>> 
>> Also, initialize it right. I believe ethernet initializes
>> 
>> to all 1's.
>> 
>> 
> True, though as r b-j points out, what one has to do is follow the
> convention used in the standard in order to maintain compatibility,
> regardless of whether one thinks it is the right way or not.
> I am sure all left-handed people feel that the Latin word describing
> their condition is poorly chosen, and that they are just as dextrous as
> the right-handed folks and not at all sinister, that is, right-handed is
> not necessarily the same as right-minded....

I had an ardently left-handed friend who referred to people who were 
equally facile with both hands as "ambisinster".

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

>On Tue, 05 Feb 2013 13:04:48 -0600, SudanBoy wrote:
>
>don't think you're going to get any takers.
>
>I'm pretty sure that the "m-sequence" in your title means the output of 
>an LFSR. If this is the case, then actually generating the sequence 
>should be pretty straight forward.  My inclination is to think that if 
>you cannot generate the sequence, then you cannot use it -- so it's a 
>very good exercise to keep working at this until you can generate the 
>sequence.

thanks for your advice (and for the steps), now I am actually generating
the PN sequence (i.e: the m-sequence or the LFSR output). 

>And, of course, no one is going to write you the code for free.

I wasn't looking for the code for the sake of copying it, I was just
looking for the algorithm. BTW, I don't mind pasting my code if that will
help other engineers as well.

>Alternately, if you can point to the specific area where you're having 
>problems then let us know and we'll help with just those areas.  But keep

>in mind that it really helps if you already have a firm grasp of how to 
>generate these sequences.

as I mentioned in my main post, I want to generate the gold codes. My real
problem now is how to verify the gold sequences that I got from the two
LFSR. I mean calculating the cross-correlation between the sequences. 

anyhow, thank you for your help, I really appreciate the steps you
mentioned above which helped me generating the m-sequences.  

>.............

>Fortunately, if the feedback polynomial is a primitive
>polynomial, so is its reverse (e.g. 11001 instead of
>Tim's 10011), and so as long as one uses the same 
>convention throughout, it does not matter which polynomial
>bit goes on which end,
>

in fact it matters and I generated different sequences of gold codes. it is
preferred, from my experience, to reverse the seeds in the two LFSR
gnerators