Re: Digest Number 5174

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

Re: Digest Number 5174

MSP430 - Discuss mailing list
Hi,

 Before most of you were born I used a LAN product, called Planet, by RACAL
to connect 2 mainframes and a few minicomputers to a Cambridge Ring fibre
optic network of a couple of hundred terminals.  The problem you face is
similar to the one that Planet had to overcome in that it was possible for
"packets" from two stations could collide on the network. The planet system
implemented a system called "exponential back off" . Now I am pretty rusty
now however I seem to recall it worked a bit like this. The system
monitored the time it took from a packet to be transmitted to the receipt
of an acknowledgement that the packet was received. If the system did not
receive the acknowledgement within the expected time it assumed that the
packet was corrupted. So it knew it needed to re transmit it. But it did
not do this immediately, it waited a little before sending it again. If the
system did not receive an acknowledgement, it waited a longer time before
retransmitting it. And so on. There would come a point at which the system
would decide that the "receiver" was not there, record some sort of error
message and give up.

Given that this technology was used in the mid 1980s, when micro
controllers were not really around and microprocessors were mostly 8 bit
with limited capabilities compared with what we have now I am pretty sure
this would be quite easy to implement on an MSP430 system.

Hope this helps,

Steve G0XAR

On 10 June 2015 at 10:00, <[hidden email]> wrote:

>    [image: Yahoo! Groups]
> <https://groups.yahoo.com/neo;_ylc=X3oDMTJkc2k3aGFjBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxNDMzOTI2ODM3>
>   TI MSP430 microcontroller users group  Group
> <https://groups.yahoo.com/neo/groups/msp430/info;_ylc=X3oDMTJkbmdxcDU4BF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwNoZHIEc2xrA2hwaARzdGltZQMxNDMzOTI2ODM3>
>    1 Message
> Digest #5174
>      1a
>  Re: Random number generator in assembler <#14ddcb332202c9e7_1a> by
> "Peter Grey" petertgrey
>
>   Message
>  1a   Re: Random number generator in assembler
> <https://groups.yahoo.com/neo/groups/msp430/conversations/topics/52414;_ylc=X3oDMTJyNTM3ZzhpBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BG1zZ0lkAzUyNDE0BHNlYwNkbXNnBHNsawN2bXNnBHN0aW1lAzE0MzM5MjY4Mzc->
>   Tue Jun 9, 2015 6:38 pm (PDT) . Posted by:   "Peter Grey" petertgrey
> <[hidden email]?subject=Re%3A%20Random%20number%20generator%20in%20assembler>
>   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
>
>       Reply to sender
> <[hidden email]?subject=Re%3A%20Random%20number%20generator%20in%20assembler>
> .   Reply to group
> <[hidden email]?subject=Re%3A%20Random%20number%20generator%20in%20assembler>
> .   Reply via Web Post
> <https://groups.yahoo.com/neo/groups/msp430/conversations/messages/52414;_ylc=X3oDMTJyb2xjZ21qBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BG1zZ0lkAzUyNDE0BHNlYwNkbXNnBHNsawNycGx5BHN0aW1lAzE0MzM5MjY4Mzc-?act=reply&messageNum=52414>
> .   All Messages (9)
> <https://groups.yahoo.com/neo/groups/msp430/conversations/topics/52406;_ylc=X3oDMTM3MXAwcGtqBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BG1zZ0lkAzUyNDE0BHNlYwNkbXNnBHNsawN2dHBjBHN0aW1lAzE0MzM5MjY4MzcEdHBjSWQDNTI0MDY->
> .  Top ^ <#14ddcb332202c9e7_toc>
>        To unsubscribe from the msp430 group, send an email to:
> [hidden email]
>
>   Visit Your Group
> <https://groups.yahoo.com/neo/groups/msp430/info;_ylc=X3oDMTJlcTJkNWNyBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTQzMzkyNjgzNw-->
>
>
>  [image: Yahoo! Groups]
> <https://groups.yahoo.com/neo;_ylc=X3oDMTJkc2k3aGFjBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxNDMzOTI2ODM3>
> • Privacy <https://info.yahoo.com/privacy/us/yahoo/groups/details.html> •
> Unsubscribe <[hidden email]?subject=Unsubscribe> • Terms
> of Use <https://info.yahoo.com/legal/us/yahoo/utos/terms/>
>
Reply | Threaded
Open this post in threaded view
|

Re: Digest Number 5174

MSP430 - Discuss mailing list
well lots of us here are quite ancient! Single Chip Microprocessors have
been around since 1971, multi-chip even longer, and microcontrollers
since 1974 (TMS 1000), although they were probably popularised by the
8048 becoming commercially available in 1977, and by the mid 80's there
were probably billions of them hiding in keyboards. I think the micros
were not as limited as you might think. Simple first generation PICs,
for example ran one of the most sophisticated robotic semiconductor
furnace robotic transfer systems in the world, you could build an engine
management computer on an 8 pin PIC, etc. I think one huge limiting
factor compared to today was the cost of memory, the lack of reliable
non-volatile memory that was in system programmable, and the lack of
advanced sensor and RF technologies that were suitably small.

Al


On 10/06/2015 8:01 PM, Stephen Farthing [hidden email] [msp430] wrote:

>
>
> Hi,
>
>  Before most of you were born I used a LAN product, called Planet, by
> RACAL to connect 2 mainframes and a few minicomputers to a Cambridge
> Ring fibre optic network of a couple of hundred terminals.  The
> problem you face is similar to the one that Planet had to overcome in
> that it was possible for "packets" from two stations could collide on
> the network. The planet system implemented a system called
> "exponential back off" . Now I am pretty rusty now however I seem to
> recall it worked a bit like this. The system monitored the time it
> took from a packet to be transmitted to the receipt of an
> acknowledgement that the packet was received. If the system did not
> receive the acknowledgement within the expected time it assumed that
> the packet was corrupted. So it knew it needed to re transmit it. But
> it did not do this immediately, it waited a little before sending it
> again. If the system did not receive an acknowledgement, it waited a
> longer time before retransmitting it. And so on. There would come a
> point at which the system would decide that the "receiver" was not
> there, record some sort of error message and give up.
>
> Given that this technology was used in the mid 1980s, when micro
> controllers were not really around and microprocessors were mostly 8
> bit with limited capabilities compared with what we have now I am
> pretty sure this would be quite easy to implement on an MSP430 system.
>
> Hope this helps,
>
> Steve G0XAR
>
> On 10 June 2015 at 10:00, <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Yahoo! Groups
>     <https://groups.yahoo.com/neo;_ylc=X3oDMTJkc2k3aGFjBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxNDMzOTI2ODM3>
>
>     TI MSP430 microcontroller users group Group
>     <https://groups.yahoo.com/neo/groups/msp430/info;_ylc=X3oDMTJkbmdxcDU4BF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwNoZHIEc2xrA2hwaARzdGltZQMxNDMzOTI2ODM3>
>
>
>
>       1 Message
>
>     Digest #5174
>     1a
>     Re: Random number generator in assembler by "Peter Grey" petertgrey
>
>
>       Message
>
>
>         1a
>
>
>         Re: Random number generator in assembler
>         <https://groups.yahoo.com/neo/groups/msp430/conversations/topics/52414;_ylc=X3oDMTJyNTM3ZzhpBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BG1zZ0lkAzUyNDE0BHNlYwNkbXNnBHNsawN2bXNnBHN0aW1lAzE0MzM5MjY4Mzc->
>
>
>
>             Tue Jun 9, 2015 6:38 pm (PDT) . Posted by:
>
>
>           "Peter Grey" petertgrey
>           <mailto:[hidden email]?subject=Re%3A%20Random%20number%20generator%20in%20assembler>
>
>
>     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]>
>     [mailto:[hidden email] <mailto:[hidden email]>]
>     Sent: Tuesday, 9 June 2015 4:15 PM
>     To: [hidden email] <mailto:[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]
>     <mailto:[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]>
>     [mailto:[hidden email] <mailto:[hidden email]>]
>     > *Sent:* Tuesday, 9 June 2015 1:42 AM
>     > *To:* [hidden email] <mailto:[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]> <mailto:[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]
>     <mailto:[hidden email]>>
>     ------------------------------------
>
>     To unsubscribe from the msp430 group, send an email to:
>     [hidden email] <mailto:[hidden email]>
>
>     ------------------------------------
>
>     Yahoo Groups Links
>
>     Reply to sender
>     <mailto:[hidden email]?subject=Re%3A%20Random%20number%20generator%20in%20assembler>
>     . Reply to group
>     <mailto:[hidden email]?subject=Re%3A%20Random%20number%20generator%20in%20assembler>
>     . Reply via Web Post
>     <https://groups.yahoo.com/neo/groups/msp430/conversations/messages/52414;_ylc=X3oDMTJyb2xjZ21qBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BG1zZ0lkAzUyNDE0BHNlYwNkbXNnBHNsawNycGx5BHN0aW1lAzE0MzM5MjY4Mzc-?act=reply&messageNum=52414>
>     . All Messages (9)
>     <https://groups.yahoo.com/neo/groups/msp430/conversations/topics/52406;_ylc=X3oDMTM3MXAwcGtqBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BG1zZ0lkAzUyNDE0BHNlYwNkbXNnBHNsawN2dHBjBHN0aW1lAzE0MzM5MjY4MzcEdHBjSWQDNTI0MDY->
>     . Top ^
>     To unsubscribe from the msp430 group, send an email to:
>     [hidden email] <mailto:[hidden email]>
>
>     Visit Your Group
>     <https://groups.yahoo.com/neo/groups/msp430/info;_ylc=X3oDMTJlcTJkNWNyBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTQzMzkyNjgzNw-->
>
>
>     Yahoo! Groups
>     <https://groups.yahoo.com/neo;_ylc=X3oDMTJkc2k3aGFjBF9TAzk3MzU5NzE1BGdycElkAzIzNDI2MjkEZ3Jwc3BJZAMxNzA1MDA1Mzc4BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxNDMzOTI2ODM3>
>
>     • Privacy
>     <https://info.yahoo.com/privacy/us/yahoo/groups/details.html> •
>     Unsubscribe
>     <mailto:[hidden email]?subject=Unsubscribe> •
>     Terms of Use <https://info.yahoo.com/legal/us/yahoo/utos/terms/>
>
>
>
>
>

Reply | Threaded
Open this post in threaded view
|

Re: Digest Number 5174

MSP430 - Discuss mailing list

Not only were the microprocessors quite powerful with respect to the demands
of the job described below, but amateur radio operators were communicating
via packet radio (AX25 protocol), with sophisticated collision arbitration,
in 1980.

Jim




Received from Onestone [hidden email] [msp430] at 06/10/2015
13:11  Wednesday UTC:

>well lots of us here are quite ancient! Single Chip Microprocessors have
>been around since 1971, multi-chip even longer, and microcontrollers since
>1974 (TMS 1000), although they were probably popularised by the 8048
>becoming commercially available in 1977, and by the mid 80's there were
>probably billions of them hiding in keyboards. I think the micros were not
>as limited as you might think. Simple first generation PICs, for example ran
>one of the most sophisticated robotic semiconductor furnace robotic transfer
>systems in the world, you could build an engine management computer on an 8
>pin PIC, etc. I think one huge limiting factor compared to today was the
>cost of memory, the lack of reliable non-volatile memory that was in system
>programmable, and the lack of advanced sensor and RF technologies that were
>suitably small.
>
>Al
>
>
>On 10/06/2015 8:01 PM, Stephen Farthing
><mailto:[hidden email]>[hidden email] [msp430] wrote:
>>
>>Hi,
>>
>>Before most of you were born I used a LAN product, called Planet, by RACAL
>>to connect 2 mainframes and a few minicomputers to a Cambridge Ring fibre
>>optic network of a couple of hundred terminals. The problem you face is
>>similar to the one that Planet had to overcome in that it was possible for
>>"packets" from two stations could collide on the network. The planet system
>>implemented a system called "exponential back off" . Now I am pretty rusty
>>now however I seem to recall it worked a bit like this. The system
>>monitored the time it took from a packet to be transmitted to the receipt
>>of an acknowledgement that the packet was received. If the system did not
>>receive the acknowledgement within the expected time it assumed that the
>>packet was corrupted. So it knew it needed to re transmit it. But it did
>>not do this immediately, it waited a little before sending it again. If the
>>system did not receive an acknowledgement, it waited a longer time before
>>retransmitting it. And so on. There would come a point at which the system
>>would decide that the "receiver" was not there, record some sort of error
>>message and give up.
>>
>>Given that this technology was used in the mid 1980s, when micro
>>controllers were not really around and microprocessors were mostly 8 bit
>>with limited capabilities compared with what we have now I am pretty sure
>>this would be quite easy to implement on an MSP430 system.
>>
>>Hope this helps,
>>
>>Steve G0XAR