Random number generator in assembler

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Random number generator in assembler

MSP430 - Discuss mailing list
Does anyone know of a simple way of randomising some data in assembler. I
want to send a RF signal between noon and 1300 hours. There are quite a few
transmitters and I do not want them to all send off at once. Each has a
unique ID numbered from 1-65000.

 

TIA

 

Peter

 

Peter Grey

Reply | Threaded
Open this post in threaded view
|

Re: Random number generator in assembler

MSP430 - Discuss mailing list
why not use the ID to determine the RF signal delay time? That way, the receiver will also know when a device doesn’t send its signal too...

From: mailto:[hidden email]
Sent: Sunday, June 07, 2015 11:25 PM
To: [hidden email]
Subject: [msp430] Random number generator in assembler

 

Does anyone know of a simple way of randomising some data in assembler. I want to send a RF signal between noon and 1300 hours. There are quite a few transmitters and I do not want them to all send off at once. Each has a unique ID numbered from 1-65000.


TIA


Peter


Peter Grey

Reply | Threaded
Open this post in threaded view
|

Re: Random number generator in assembler

MSP430 - Discuss mailing list
In reply to this post by MSP430 - Discuss mailing list
"'Peter Grey' [hidden email] [msp430]" <[hidden email]>:

> Does anyone know of a simple way of randomising some data in assembler.
> I want to send a RF signal between noon and 1300 hours. There are quite
> a few transmitters and I do not want them to all send off at once. Each
> has a unique ID numbered from 1-65000.

TI has at least 2 examples for random number generation, one uses the
asynchonous behaviour between two counters; the other one is using the noise
from the internal temperature diode. Search for "random" in the application
notes.

Matthias

Reply | Threaded
Open this post in threaded view
|

Re: Random number generator in assembler

MSP430 - Discuss mailing list
"Matthias Weingart [hidden email] [msp430]"
<[hidden email]>:

> "'Peter Grey' [hidden email] [msp430]"
> <[hidden email]>:
>
>> Does anyone know of a simple way of randomising some data in assembler.
>> I want to send a RF signal between noon and 1300 hours. There are quite
>> a few transmitters and I do not want them to all send off at once. Each
>> has a unique ID numbered from 1-65000.
>
> TI has at least 2 examples for random number generation, one uses the
> asynchonous behaviour between two counters

SLAA388

M.

Reply | Threaded
Open this post in threaded view
|

Re: Random number generator in assembler

MSP430 - Discuss mailing list
In reply to this post by MSP430 - Discuss mailing list
XOR-SHIFT is one technique, wikipedia describes it .

Brian


'Peter Grey' [hidden email] [msp430] wrote:

>
> Does anyone know of a simple way of randomising some data in
> assembler. I want to send a RF signal between noon and 1300 hours.
> There are quite a few transmitters and I do not want them to all send
> off at once. Each has a unique ID numbered from 1-65000.
>
> TIA
>
> Peter
>
> Peter Grey
>
>

--
PelagicAutopilot.com

Reply | Threaded
Open this post in threaded view
|

Re: Random number generator in assembler

MSP430 - Discuss mailing list
SLAA338 is the one you want. It comes complete with assembler source code.

 PDF and source code are available here: App Note Abstract: Random Number Generation Using the MSP430 http://www.ti.com/sc/docs/psheets/abstract/apps/slaa338.htm
 
 --rick
 

Reply | Threaded
Open this post in threaded view
|

RE: Random number generator in assembler

MSP430 - Discuss mailing list
In reply to this post by MSP430 - Discuss mailing list
Thank you to all who replied. It is appreciated. I am going to have a look
at SLAA338 and I found I have a few books by Donald Knuth with references to
random number generation. It will keep me busy over a few evenings!

 

Peter

 

From: [hidden email] [mailto:[hidden email]]
Sent: Tuesday, 9 June 2015 1:42 AM
To: [hidden email]
Subject: Re: [msp430] Random number generator in assembler

 



XOR-SHIFT is one technique, wikipedia describes it .

Brian



'Peter Grey' [hidden email] [msp430] wrote:

 

Does anyone know of a simple way of randomising some data in assembler. I
want to send a RF signal between noon and 1300 hours. There are quite a few
transmitters and I do not want them to all send off at once. Each has a
unique ID numbered from 1-65000.

 

TIA

 

Peter

 

Peter Grey





--
PelagicAutopilot.com








Reply | Threaded
Open this post in threaded view
|

Re: Random number generator in assembler

MSP430 - Discuss mailing list
Hi,

Knuth is the ultimate reference for many algorithms, but The Art of
Computer Programming is not light reading.  If you are not heavily into
theoretical computing, don't bother trying to use them as sources for
something like this.

What you have to do is think about the /real/ problem, not jump to a
solution and try to implement it.  You don't need a random number
generator - so trying to make something that will generate good quality
high entropy pseudo-random numbers will mean extra effort and extra risk
of getting things wrong.

You have a bunch of nodes that are going to send sometime between 1200
and 1300.  That's a period of 3600 seconds.  Each has a unique node
number between 1 and 65000.  If the radio transmission takes less than
50 ms, then your solution is easy - wait (id * 50 ms) before sending.
That will also guarantee that there won't be collisions, which would
otherwise always be a risk with random delays.  Case closed.


If send times are longer than 50 ms, there will always be a risk of
collisions.  You will need some way to spread out the nodes amongst
appropriately timed slots - but it does not need to be random.  In fact,
it is better if it is /not/ random.  Use a hash function on the ID with
an initial fixed salt value.  If two nodes collide, they should each
pick a different salt value - they will not collide again.  (In theory,
they could now collide with other nodes - there is no limit to the
maximum length of such collision chains, but in practice the likelihood
of collision decreases at each step unless you have too many nodes.)
Once the nodes have settled on their slot numbers, stick to them.

An easy hash function is something like crc16(idLo ++ idHi ++ saltLo ++
saltHi), since there's a fair chance you already have code for a crc
calculation for adding checksums to your telegrams.

mvh.,

David





On 09/06/15 03:28, 'Peter Grey' [hidden email] [msp430] wrote:

>  
>
> Thank you to all who replied. It is appreciated. I am going to have a
> look at SLAA338 and I found I have a few books by Donald Knuth with
> references to random number generation. It will keep me busy over a few
> evenings!
>
>  
>
> Peter
>
>  
>
> *From:*[hidden email] [mailto:[hidden email]]
> *Sent:* Tuesday, 9 June 2015 1:42 AM
> *To:* [hidden email]
> *S ubject:* Re: [msp430] Random number generator in assembler
>
>  
>
>
>
> XOR-SHIFT is one technique, wikipedia describes it .
>
> Brian
>
> 'Peter Grey' [hidden email] <mailto:[hidden email]>
> [msp430] wrote:
>
>      
>
>     Does anyone know of a simple way of randomising some data in
>     assembler. I want to send a RF signal between noon and 1300 hours.
>     There are quite a few transmitters and I do not want them to all
>     send off at once. Each has a unique ID numbered from 1-65000.
>
>      
>
>     TIA
>
>      
>
>     Peter< o>
>
>      
>
>     Peter Grey
>
>
>
Reply | Threaded
Open this post in threaded view
|

RE: Random number generator in assembler

MSP430 - Discuss mailing list
Hi David

Thanks for the very informed reply. I had decided to use the ID to encode a
send time. Lucky for me I do not have a busy network. I am also looking at
the RSSI prior to a send to avoid possible collisions. In another project I
may get the RF traffic will increase so I need to do a little more in
relation to collisions. I will take a better look at the hash function you
mentioned.
I have volume I & II of Knuth. I agree it is not light reading but very
interesting to see how he does things.


Thanks

Peter

-----Original Message-----
From: [hidden email] [mailto:[hidden email]]
Sent: Tuesday, 9 June 2015 4:15 PM
To: [hidden email]
Subject: Re: [msp430] Random number generator in assembler

Hi,

Knuth is the ultimate reference for many algorithms, but The Art of Computer
Programming is not light reading.  If you are not heavily into theoretical
computing, don't bother trying to use them as sources for something like
this.

What you have to do is think about the /real/ problem, not jump to a
solution and try to implement it.  You don't need a random number generator
- so trying to make something that will generate good quality high entropy
pseudo-random numbers will mean extra effort and extra risk of getting
things wrong.

You have a bunch of nodes that are going to send sometime between 1200 and
1300.  That's a period of 3600 seconds.  Each has a unique node number
between 1 and 65000.  If the radio transmission takes less than
50 ms, then your solution is easy - wait (id * 50 ms) before sending.
That will also guarantee that there won't be collisions, which would
otherwise always be a risk with random delays.  Case closed.


If send times are longer than 50 ms, there will always be a risk of
collisions.  You will need some way to spread out the nodes amongst
appropriately timed slots - but it does not need to be random.  In fact, it
is better if it is /not/ random.  Use a hash function on the ID with an
initial fixed salt value.  If two nodes collide, they should each pick a
different salt value - they will not collide again.  (In theory, they could
now collide with other nodes - there is no limit to the maximum length of
such collision chains, but in practice the likelihood of collision decreases
at each step unless you have too many nodes.) Once the nodes have settled on
their slot numbers, stick to them.

An easy hash function is something like crc16(idLo ++ idHi ++ saltLo ++
saltHi), since there's a fair chance you already have code for a crc
calculation for adding checksums to your telegrams.

mvh.,

David





On 09/06/15 03:28, 'Peter Grey' [hidden email] [msp430] wrote:

>  
>
> Thank you to all who replied. It is appreciated. I am going to have a
> look at SLAA338 and I found I have a few books by Donald Knuth with
> references to random number generation. It will keep me busy over a
> few evenings!
>
>  
>
> Peter
>
>  
>
> *From:*[hidden email] [mailto:[hidden email]]
> *Sent:* Tuesday, 9 June 2015 1:42 AM
> *To:* [hidden email]
> *S ubject:* Re: [msp430] Random number generator in assembler
>
>  
>
>
>
> XOR-SHIFT is one technique, wikipedia describes it .
>
> Brian
>
> 'Peter Grey' [hidden email] <mailto:[hidden email]>
> [msp430] wrote:
>
>      
>
>     Does anyone know of a simple way of randomising some data in
>     assembler. I want to send a RF signal between noon and 1300 hours.
>     There are quite a few transmitters and I do not want them to all
>     send off at once. Each has a unique ID numbered from 1-65000.
>
>      
>
>     TIA
>
>      
>
>     Peter< o>
>
>      
>
>     Peter Grey
>
>
>


------------------------------------
Posted by: David Brown <[hidden email]>
------------------------------------

To unsubscribe from the msp430 group, send an email to:
[hidden email]


------------------------------------

Yahoo Groups Links