MC: Gray code
Eduardo M Kalinowski
Here's a nice challenge:
Those who study electrical engineering may have already heard of the
Gray code. It's a form to represent numbers using 0 and 1, but it's not
binary or BCD. There are several ways to build a table of it. I'll
describe one here (for 3 bits, can be repeated ad infinitum):
Start with the numbers 000 and 001, the first two. Then, imagine
there's a mirror below them. The numbers are reflected, starting at the
rightmost column, up to the first column consisting only of 0's. This
column is changed to be only of 1's. The columns left of that don't
change -- they still contain 0's. Example:
000 ---+
001 -+ |
--- | |
011 -+ |
010 ---+
||
|+-> This column is mirrored.
+--> This column is replaced by 1's
Now, repeat the same process for the four numbers we have:
000 ----+
001 ---+|
011 --+||
010 -+|||
--- ||||
110 -+|||
111 --+||
101 ---+|
100 ----+
|||
|++--> These columns are reflected
+----> This column is replaced by 1's
The objective of the challenge is to create a User RPL program
(usual rules apply) that converts a number in Gray code to binary. For
example:
#111 -> #100b
#1000 -> #1100b (not shown in table, but it's correct)
As you might have guessed, the numbers should be entered and
returned as hex strings.
The winner is the smallest solution, time doesn't matter. The
solution I have here is probably the shortest possible. Let's see if
someone can get one equal, or better.
A tip: first, think HOW the conversion can be done, then implement.
Yes, there is a way :-)
--
Eduardo M Kalinowski
mailto:eka...@iname.com
http://move.to/hp48g
ICQ 10944368
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Joachim Stump
<< DUP SR XOR >>
Greetings from Joachim Stump.
Eduardo M Kalinowski schrieb in Nachricht <7k056v$ush$1...@nnrp1.deja.com>...
Ben M.
Joachim Stump
here is what I know of the Gray code:
This code is mainly used to do absolute digital length or angular encoding.
The advantage over the binary encoding is that from each value to the next
or previous value only one digit changes. In binary code there are sometimes
many digits wich change. Example:
dec bin gray
0 0000 0000
1 0001 0001 \ 2 digits in binary change!
2 0010 0011 /
3 0011 0010 \ 3 digits in binary change!
4 0100 0110 /
5 0101 0111
....
You cant detect simultaniusly more than one changing digit. So you may read
some wrong values when using binary encoding in the moment, when you are
between two states.
Example in binary:
between 0011 and 0100 you may read:
0111
0101
0110
0001
0010
0000
or perhaps 0011 or 0100, which are the only two "correct" values.
Thats all no problem in Gray code!
Sorry for poor english language style. It is not my native language.
Greetings from Joachim Stump.
Joseph K. Horn
> ... So you may read some wrong values when using binary encoding in
> the moment, when you are between two states.
> Example in binary:
> between 0011 and 0100 you may read:
> 0111
> 0101
> 0110
> 0001
> 0010
> 0000
> or perhaps 0011 or 0100, which are the only two "correct" values.
> Thats all no problem in Gray code!
Hey, this sounds like a solution to the clock problem! Here's the
problem: when the operating system reads the time, it must read the
bits from the clock one by one (obviously), but what if the clock
advances halfway through the read? Then the reading would be wrong!
Simplified Example: Suppose the clock is at 5:59. The system begins
a clock read, and pulls in 5 as the hour. At that precise moment, the
clock happens to advance to 6:00, so the system reads 00 for the
minutes. The system therefore pulled 5:00 out of the clock and thus
thinks the time is 1 hour less than it really is! Very Bad Thing.
HP solves this problem by performing two clock reads and comparing
them. But if the timer ran in gray binary instead of regular binary,
a single read would be sufficient, thus speeding up all accesses to
the real-time clock. Also, advancing the clock would be faster,
since incrementing the clock would flip only a single bit instead of
adding 1 to a huge binary number. (Don't tell me, "It doesn't
matter how fast it is, because it's done in hardware." Hey, it's
ALL done in hardware. The less work done, the longer the batteries
last! And the clock advances 8192 times every second! Assuming one
saved flip-flop per addition, that's 707,788,800 saved state changes
per *day*!)
But HP doesn't do it this way. So... what am I missing?
-Joe-
Eduardo M Kalinowski
"Joachim Stump" <joachi...@berlin.de> wrote:
> << DUP SR XOR >>
Well, you got it.
--
Eduardo M Kalinowski
mailto:eka...@iname.com
http://move.to/hp48g
ICQ 10944368
Aaron Wallace
On Mon, 14 Jun 1999, Joachim Stump wrote:
> dec bin gray
> 0 0000 0000
> 1 0001 0001 \ 2 digits in binary change!
> 2 0010 0011 /
> 3 0011 0010 \ 3 digits in binary change!
as an interesting note, this is the manner in which Karnaugh (sp?) maps
are laid out (K-Maps are used to simplify boolean functions).
Here is a crude template for a 4 by 4 K-Map:
Y
|00|01|11|10|
--+-----------+
00| | | | |
--+--+--+--+--+
01| | | | |
X--+--+--+--+--+
11| | | | |
--+--+--+--+--+
10| | | | |
--+--+--+--+--+
if you were to make a larger K-map, you would continue as the gray code
numbering scheme increases.
--
Aaron.
John H Meyers
> Hey, this sounds like a solution to the clock problem! Here's the
> problem: when the operating system reads the time, it must read the
> bits from the clock one by one (obviously), but what if the clock
> advances halfway through the read? Then the reading would be wrong!
> Simplified Example: Suppose the clock is at 5:59. The system begins
> a clock read, and pulls in 5 as the hour. At that precise moment, the
> clock happens to advance to 6:00, so the system reads 00 for the
> minutes. The system therefore pulled 5:00 out of the clock and thus
> thinks the time is 1 hour less than it really is! Very Bad Thing.
I have an otherwise very good Seiko alarm-chronograph (module #A547)
which does exactly this Very Bad Thing, in its "count-down timer"
function -- if it is stopped while decrementing MM minutes 00 seconds
to what should be MM-1 minutes 59 seconds, it is possible to pause it
just before it propagates the "borrow" into the minutes field, which
can produce a paused timer of MM minutes 59 seconds, and then resume
counting from there when restarted, forgetting all about the "borrow"
from MM, and thus "losing one whole minute" of counting down; there
seems to be a little "window" of perhaps 1/100 second each minute,
during which this can actually happen.
Another way of looking at this is that the "stop" button might better
just set a *request*to*stop* bit, which would be tested and honored
only when suitable, which is how the HP48 acts with the CANCEL key,
disallowing any interruption to the completion of critical internal
system operations before more gracefully aborting a user program.
What are the chances of my convincing the parking meter maiden
that it was the fault of my wristwatch that I missed putting in
the next penny -- yes folks, Fairfield Iowa is one of the last places
on earth still using Duncan penny parking meters, a few of which
are actually not yet broken, and we are ordering a new lot from
nearby Lake Wobegon this summer, Garrison Keillor willing :)
A revived old mini-challenge:
Write a simple *UserRPL* program equivalent to \<< DATE TIME \>>
except that you must guarantee that the answers are not
approximately 24 hours wrong, which is possible if midnight
strikes between the above two *separate* user commands
(similar considerations apply to computer operating systems
which have separate function calls for date and for time).
-----------------------------------------------------------
With best wishes from: John H Meyers <jhme...@mum.edu>
dbac...@ionet.net
through Deja I was able to confirm my memories of an
earlier MC along this line.
I saw "Good artists create. Great artists steal" attributed
to Picasso the other day, and though I had already worked
out most of this, someone else did it first:
<< TICKS 8192 / B->R 86400 / DUP IP 1.01 SWAP DATE+ SWAP FP
24 * ->HMS >>
Donald
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
In article <3769E6...@miu.edu>,
dbac...@ionet.net
dbac...@ionet.net wrote:
> It nagged at me and nagged at me, and finally, digging
> through Deja I was able to confirm my memories of an
> earlier MC along this line.
>
> I saw "Good artists create. Great artists steal" attributed
> to Picasso the other day, and though I had already worked
> out most of this, someone else did it first:
>
> << TICKS 8192 / B->R 86400 / DUP IP 1.01 SWAP DATE+ SWAP FP
> 24 * ->HMS >>
>
Don't you hate noticing a problem right after you hit [Send]?
Seems as if there is a bit of a bug in the operation of
DATE+. Oh well, for cryptic reasons, change the above to:
<< TICKS B->R 707788800 / DUP IP 1.01 SWAP DATE+ .001999 - SWAP FP
24 * ->HMS >>
Donald
Sent via Deja.com http://www.deja.com/
John H Meyers
How to make sure, if you want *both* the date and time,
but have to invoke two separate commands, e.g. DATE TIME,
that you could not possibly be about 24 hours off, in case
midnight occurred right between performing DATE (say on Monday)
and then performing TIME (say just after the clock went
from 23:59 Monday to 00:00 Tuesday)
The simplest answer is:
Perform DATE, TIME, and then DATE again.
Compare the first date with the last date.
If equal, then all is well.
If not equal, then don't worry about trying to figure out
which date goes with the time value (this is where the posted
answers began getting complicated and making assumptions).
Instead, just go back and start all over again;
it will be quite impossible to get "stuck in a loop," because
only one "rollover" (or discontinuity) occurs in any whole day:
\<< WHILE DATE TIME OVER DATE \=/ REPEAT DROP2 END \>> [unequal symbol]
Gray code is often used in optical or electrical encoders, where
a rotating ring has concentric bands, each representing one binary
output bit. Because it is impossible to align and equalize the
independent bit state detectors perfectly, the rings are encoded
with Gray code (where only one detector changes state at a time),
and the result is converted externally into the more desirable
conventional binary output, proportional to absolute rotation.
It is therefore more common to need to convert *from* Gray code
*to* binary; only the encoder designer needs to do the reverse.
Conversion of a bit stream in *either* direction can be formulated as:
(next output bit) == (next input bit) XOR (previous binary bit)
It therefore seems to me that the program DUP SR XOR converts in
the direction Binary -> Gray; where's the answer to the reverse,
which I thought was what Eduardo Kalinowsky had originally asked?
-------------------------------------------------------
Establish world peace now: <http://www.kosovopeace.org>
<http://www.natural-law.org>
Consciousness-based education: <http://www.mum.edu>
john Latala
> It therefore seems to me that the program DUP SR XOR converts in
> the direction Binary -> Gray; where's the answer to the reverse,
> which I thought was what Eduardo Kalinowsky had originally asked?
Gray to Binary can be done in a number of ways but I've never been really
happy with any of the programs I've written to do it. That's not really
true but the best one I've used is a table lookup method which is pretty
easy on an embedded micro but probably not the best answer for the HP48.
One interesting way is to use the Binary->Gray program to do a
Gray->Binary conversion. If you put a binary number on the stack and then
execute your Binary->Gray routine (let's ball it B->G) you end up with the
resulting Gray value. Simple enough but have you ever then executed B->G
again ... and again ...
If you keep doing it you'll find you end up right back where you started
from! If you count the number of times you execute B->G before you end up
where you started you'll find it's the same as the number of bits in
your original binary value.
That's not really true because if you try doing it with oddball word sizes
(i.e. 12 or 13) you'll find that it only works when the word size is a
'nice' power of two (2, 4, 8, 16, ... ).
So with all that said a first crack at a G->B is:
\<<
1 RCWS 1 -
START
B\->G
NEXT
\>>
(provided you stay with the 'nice' power of two word sizes).
If you look at what a binary to gray actually does, especially if you've
ever seen a hardware implementation with it's cascade of XOR gates, you
should notice two things ... you still have the original MSBit and usually
an XOR operation is reversible.
I you run B->G on a gray scale number and compare it against the original
binary number you'll find that you have the MSBit right (it never changes)
and you also have the second MSBit too because you've XORed the MSBit out
of it!
That means you now have two or your original bits!
What happens if you shift this new value right TWO bits positions and XOR
it with itself again? You end up with your original for MSBits back.
This can be used to make a nice Gray to Binary but the drawback is that
the program is very dependant on the word size!
Let's assume you do all your binary calculations using 64 bit word sizes.
If that's true then you can use something like the following to do gray to
binary conversion:
\<<
@ recover the second MSBit
DUP SR XOR
@ recover the four MSBits
DUP SR SR XOR
@ recover the eight MSBits
DUP SR SR SR SR XOR
@ recover the sixteen MSBits
DUP SRB XOR
@ recover the thirty-two MSBITS
DUP SRB SRB XOR
@ recover all sixty-four bits
DUP SRB SRB SRB SRB XOR
\>>
You can make the above work for any word size by saving the word size,
forcing 64 bit words, doing a 64-bit gray to binary conversion then
restoring the original word size.
The only gotcha is that you have to make sure that after you widen the
word size to 64 bits the high order bits are all zero. This seems to be
quite easy to do because it seems that any logical operation clears them
out.
To see this try this sequence:
64 STWS #123456789ABCDEFh 8 STWS 64 STWS
which gives one answer while:
64 STWS #123456789ABCDEFh 8 STWS NOT NOT 64 STWS
gives you a different answer!
With all that in mind something like this should do it ...
\<<
@ clear the upper bits in case we're not using 64 bit words
NOT NOT
@ get the word size and save it
RCWS SWAP
@ do a 64-bit word gray to binary conversion
@ recover the second MSBit
DUP SR XOR
@ recover the four MSBits
DUP SR SR XOR
@ recover the eight MSBits
DUP SR SR SR SR XOR
@ recover the sixteen MSBits
DUP SRB XOR
@ recover the thirty-two MSBITS
DUP SRB SRB XOR
@ recover all sixty-four bits
DUP SRB SRB SRB SRB XOR
@
@ narrow the wordsize back to what it used to be
@
SWAP STWS
\>>
I haven't tried the above program so I'm not sure if I've got it exactly
right but it doesn't work it should give you the idea and it shouldn't be
too difficult to debug ...
--
john R. Latala
jrla...@golden.net
Donald Bachman
My only problem with the below solution is the lapse in
time between initiation of program execution, DATE, and TIME.
Not likely to be a major concern, of course.
Donald
John H Meyers (jhme...@miu.edu) wrote:
: The easy [midnight rollover] problem which I posed was:
:
: It therefore seems to me that the program DUP SR XOR converts in
: the direction Binary -> Gray; where's the answer to the reverse,
: which I thought was what Eduardo Kalinowsky had originally asked?
:
: -------------------------------------------------------
Aaron Wallace
On Sat, 19 Jun 1999, john Latala wrote:
> On Sat, 19 Jun 1999, John H Meyers wrote:
>
> > It therefore seems to me that the program DUP SR XOR converts in
> > the direction Binary -> Gray; where's the answer to the reverse,
> > which I thought was what Eduardo Kalinowsky had originally asked?
>
> Gray to Binary can be done in a number of ways but I've never been really
> happy with any of the programs I've written to do it. That's not really
> true but the best one I've used is a table lookup method which is pretty
> easy on an embedded micro but probably not the best answer for the HP48.
The easiest (best?) way to do it is with boolean instructions. Here are
the boolean functions for 4 bit Binary to Gray:
(assuming A->D are the bits of the binary number - A is MSB and E->H are
the bits of the Gray number - E is MSB)
E=A
F=!A*B+A*!B
G=B*!C+!B*C
H=!C*D+C*!D
This means that going from Gray to Binary will be the inverse (A->E,B->F,
C->G,D->H)
--
Aaron.