graycode to binary code
nick bernard
Posts: 329
continuing from
http://forums.parallax.com/forums/default.aspx?f=15&m=146166
how does this look? could it be more concise? i always have trouble juggling bits with asm and i could use some help testing the script.
i've implemented:
Let B[noparse][[/noparse]n:0] the array of bits in the usual binary representation
Let G[noparse][[/noparse]n:0] the array of bits in Gray code
G[noparse][[/noparse]n]=B[noparse][[/noparse]n]
for i=n-1 down to i=0 {G[noparse][[/noparse] i]=B[noparse][[/noparse]i+1] XOR B[noparse][[/noparse] i]}
or if you prefer it graphically
AS
DEVICE SX48, OSCXT2
FREQ 50_000_000
reset main
ORG $0A
binary DS 1
gray DS 1
mask DS 1
ax DS 1
bx DS 1
cx DS 1
watch ax,8,UBIN
watch bx,8,UBIN
watch gray,8,UBIN110111
watch binary,8,UDEC
watch mask,8,UBIN
main:
mov gray, #%0010_0111 ;G 53
break
mov binary, gray
mov mask, #%0100_0000
clr cx
movb gray.7, cx.0
top:
mov w, binary
mov ax, w
mov bx, w
clc
rr ax
and ax, mask
and bx, mask
xor ax, bx
jz set_0
or binary, mask
jmp next
set_0:
not mask
and binary, mask
not mask
next
clc
rr mask
sc
jmp top
stick:
jmp stick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
engineer, fireman, bowler, father, WoW addict [noparse];)[/noparse]
Post Edited (nick bernard) : 9/25/2006 7:15:06 PM GMT
http://forums.parallax.com/forums/default.aspx?f=15&m=146166
how does this look? could it be more concise? i always have trouble juggling bits with asm and i could use some help testing the script.
i've implemented:
Let B[noparse][[/noparse]n:0] the array of bits in the usual binary representation
Let G[noparse][[/noparse]n:0] the array of bits in Gray code
G[noparse][[/noparse]n]=B[noparse][[/noparse]n]
for i=n-1 down to i=0 {G[noparse][[/noparse] i]=B[noparse][[/noparse]i+1] XOR B[noparse][[/noparse] i]}
or if you prefer it graphically
AS
DEVICE SX48, OSCXT2
FREQ 50_000_000
reset main
ORG $0A
binary DS 1
gray DS 1
mask DS 1
ax DS 1
bx DS 1
cx DS 1
watch ax,8,UBIN
watch bx,8,UBIN
watch gray,8,UBIN110111
watch binary,8,UDEC
watch mask,8,UBIN
main:
mov gray, #%0010_0111 ;G 53
break
mov binary, gray
mov mask, #%0100_0000
clr cx
movb gray.7, cx.0
top:
mov w, binary
mov ax, w
mov bx, w
clc
rr ax
and ax, mask
and bx, mask
xor ax, bx
jz set_0
or binary, mask
jmp next
set_0:
not mask
and binary, mask
not mask
next
clc
rr mask
sc
jmp top
stick:
jmp stick
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
engineer, fireman, bowler, father, WoW addict [noparse];)[/noparse]
Post Edited (nick bernard) : 9/25/2006 7:15:06 PM GMT
Comments
If you need it to run faster, you can use an O(log(n)) algorithm.
For 8 bits, you basically have the following steps (in pseudocode):
Load Gray code value into REG
REG = (REG) XOR (REG >> 4) (>> means right shift, shifting zeros into the left side)
REG = (REG) XOR (REG >> 2)
REG = (REG) XOR (REG >> 1)
The value in REG is now the binary value.
If you are working with 16 bits, you only need to add a line that shifts it 8 places.
NOTE: I'm assuming you are using a reflected Gray code - but I figure that's a pretty safe bet since your approach is only valid for that same type of Gray code.
HTH
this is my revised procedure.
Gray_To_Binary_Log:
cx = __PARAM1
'REG = (REG) XOR (REG >> 4) (>> means right shift, shifting zeros into the left side)
'REG = (REG) XOR (REG >> 2)
'REG = (REG) XOR (REG >> 1)
ASM
mov ax, cx
clc
rr cx
clc
rr cx
clc
rr cx
clc
rr cx
xor ax, cx
mov cx, ax
clc
rr cx
clc
rr cx
xor ax, cx
mov cx, ax
clc
rr cx
xor ax, cx
ENDASM
RETURN ax
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
engineer, fireman, bowler, father, WoW addict [noparse];)[/noparse]
BTW, the HTH are not my initials (but I can sure see why it looked that way). It's net shorthand for "hope that helps".
The O(something) is called "Big-O" notation. It relates to fields such as Analysis and Design of Algorithms, Computational Complexity, and others.·The·'O' is for "order". Saying that something·is·O(n) means that·it scales linearly with the size of the problem. In your case, if you double then number of bits in the gray code word, then you double the amount of effort/time to convert it to binary. For most meaningful problems, O(n) solutions are considered quite nice - it's actually pretty seldom we can do that good.
Technically,·O() describes the behavior·as the size of the problem grows to very large values and doesn't always apply too well to small versions of the·problem.
If something is O(log(n)) it means that (for large n) when you square the size of the problem, the amount of effort only doubles. That is, indeed, powerful juju - when you can find a way to pull it off.
Cheers!
Bill
·
Just so I understand "Big-O" notation. Would a binary search (on a sorted array) be considered O(log(n)) ? If not what would it be ?
Bean.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Cheap used 4-digit LED display with driver IC·www.hc4led.com
Low power SD Data Logger www.sddatalogger.com
SX-Video Display Modules www.sxvm.com
There are only two guaranteed ways to become weathy.
Spend less than you make.
Make more than you spend.
·
Hey! neat algorithm. What is a reflected Gray code, vs. its opposite? Here is the standard progresssion, I thought, is it "reflected"?
Gray Bin
0000 0000
0001 0001
0011 0010
0010 0011
0110 0100
0111 0101
0101 0110
0100 0111
1100 1000
1101 1001
1111 1010
1110 1011
1010 1100
1011 1101
1001 1110
1000 1111
0000 again
Terry, the binary search is O(log2 N). Double the number of samples adds only one iteration to the search.
The notion of "O" is important in convolutions, where the goal of things like the FFT and number theoretic transforms is to reduce the number of multiplications required. In a large array, a standard transform requires O(n^2) multiplicatons. The FFT reduces it to O(n log n), which is a great improvement when n is large. It is not as good as O(n), but it is very good for a convolution. For arithmentic computations, CORDIC algorithms are very efficient, because they are basically a binary search algorithm that involves shifts and compares, no general multplications. So CORDIC can compute functions like SIN and COS in O(log n).
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
A reflected Gray code can be constructed by taking the (reflected) Gray code pattern for n bits and constructing a pattern for n+1 bits by appending a reversed copy of the current pattern to the end of the current pattern and then adding a new bit that is one state for the original part and the other state for the new part.
For instance, the simplist Gray code is a 1-bit Gray code:
0
1
To construct a 2-bit reflected Gray code, we (1) append a reflected copy of the current code to the end:
0
1
1
0
and then (2) add a new bit that changes state at the midpoint:
00
01
11
10
Notice how the upper two bits are both square waves at twice the frequency of the overall code but are in quadrature to each other.
Repeating this process to get a 3-bit code:
000
001
011
010
110
111
101
100
And 4-bits:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Now, I need to correct something I said originally. When I said that both algorithms (the original cascaded XORs and the O(log(n)) one that I offered) were for reflected Gray codes, I was being sloppy to the point of being flat wrong. There is a specific Gray code that both techniques work for and, it just happens, that Gray code is one example of a reflected Gray code. There are tons of Gray codes (in fact, any code other than this particular one) that are reflected but which can not be converted to binary using either algorithm.
Both algorithms really stem not from the reflected nature of the code, but from another property that could be used to construct this particular code. Consider binary addition - whenever a binary value in incremented, the new value can be generated from the old by toggling the b least significant bits. For instance:
10010110111
Can be incremented by toggling the 4 least significant bits to get:
10010111000
Since a Gray code merely requires that, in going from one code to the next, only a single bit be changed, we can construct a Gray code from binary addition by simply toggling the bit corresponding to the boundary between bits that get flipped and bits that don't. So the Gray codes for the two values above would be identical except for the 4th bit from the right.
This construction leads to an O(1) algorithm (also known as a "constant time" algorithm) for converting from Binary to Gray. Bit n in the Gray code value is simply the XOR of bits n and n+1 of the Binary code value. It doesn't matter how wide the Binary value is, we can convert it to Gray in the same amount of time. For an N-bit code, bit N+1 of the binary value is considered to be LO - which only makes sense since that would be the case if we think of working with the first half of a N+1 bit Binary sequence.
So how do we convert from Gray to Binary using this code?
Our algorithm for going from Binary to Gray is simple:
Gray[noparse][[/noparse]n] = Binary[noparse][[/noparse]n] XOR Binary[noparse][[/noparse]n+1]
It is always true that:
If C = A XOR B, then A = C XOR B.
Hence:
Binary[noparse][[/noparse]n] = Gray[noparse][[/noparse]n] XOR Binary[noparse][[/noparse]n+1]
This means that, given the Binary value for bit n+1 and the Gray value for bit n, we can determine the Binary value for bit n.
To get the ball rolling, we just need one bit of the Binary value obtained through some means other than this relationship. But we have that. A consequence of assuming that bit N+1 of the binary value is LO is that the MSB of the Gray code and the Binary code are identical. This, then, gives the hook for progressively converting from Gray to Binary and leads directly to the cascaded XOR algorithm in the original post.
Wow, some heavy and great analysis !
Cheers,
Peter (pjv)
Numerical Recipes Books Online - library.lanl.gov/numerical/
Here is another nice resource:
http://www.comp.nus.edu.sg/~stevenha/programming/prog_mathematics.html
regards peter
today, I had to interface a multi-turn absolute encoder with a resolution of 13 bits/turn, allowing for a total of 4096 turns. Thus, this beast is returning a 25 bit Gray code that I needed to convert into binary for later serial transmission.
I remembered this thread about Gray code conversion, so I thought I might share my conversion routine with you:
; Gray to Binary ; ; Expects 32 bit Gray Code in GData+3 (HOB) ... GData+0 (LOB) ; stores conversion result in the same registers. ; mov Counter, #33 ; Prepare for 33 shifts (32 bits plus carry) clr BitCount ; Counter for subsequent 1 bits to handle the XOR clc ; Prepare carry for a "clean start" snb GData+3.7 ; When highest bit is set, increment the bit counter inc BitCount :Loop6 snb GData+3.6 ; When the next lower bit is set, increment the bit counter once again inc BitCount mov w, --Counter ; Check if we are about to do the last shift to get back what's in the Carry flag snz jmp :LastBit ; Don't XOR bits in this case movb GData+3.6, BitCount.0 ; This XORs the GData+3.7, and GData+3.6 bits, i.e. when the two bits are equal, ; BitCount is even (i.e. BitCount.0 = clear) - when the two bits are not equal, ; BitCount is odd (i.e. BitCount.0 = set). So, BitCount.0 is the XOR of the two ; source bits, and the result goes into GData+3.6 :LastBit rl GData+3 ; Shift the next bits into GData+3.7 and GData+3.6 for XORing, and shift the rl GData+0 ; Carry flag with the second-last result into GData+0.0 rl GData+1 rl GData+2 decsz Counter ; More bits to go? jmp :Loop6 ; yes ; Continue with instructions to handle the converted Gray code here...You may increase or decrease the number of code bytes to be handled. The Counter variable must always be initialized to the total number of bits plus one. Bit-checking and manipulation must always take place with bits 7 and 6 of the highest order byte, and following the :LastBit label, the highest order byte must be rotated left first, followed by the remaining bytes from lowest to higher order. So, for a 16 bit Gray code value, the routine would look like this:
; Gray to Binary ; ; Expects 16 bit Gray Code in GData+1 (HOB) ... GData+0 (LOB) ; stores conversion result in the same registers. ; mov Counter, #17 ; Prepare for 17 shifts (16 bits plus carry) clr BitCount ; Counter for subsequent 1 bits to handle the XOR clc ; Prepare carry for a "clean start" snb GData+1.7 ; When highest bit is set, increment the bit counter inc BitCount :Loop6 snb GData+1.6 ; When the next lower bit is set, increment the bit counter once again inc BitCount mov w, --Counter ; Check if we are about to do the last shift to get back what's in the Carry flag snz jmp :LastBit ; Don't XOR bits in this case movb GData+1.6, BitCount.0 ; This XORs the GData+1.7, and GData+1.6 bits, i.e. when the two bits are equal, ; BitCount is even (i.e. BitCount.0 = clear) - when the two bits are not equal, ; BitCount is odd (i.e. BitCount.0 = set). So, BitCount.0 is the XOR of the two ; source bits, and the result goes into GData+1.6 :LastBit rl GData+! ; Shift the next bits into GData+!.7 and GData+!.6 for XORing, and shift the rl GData+0 ; Carry flag with the second-last result into GData+0.0 decsz Counter ; More bits to go? jmp :Loop6 ; yes ; Continue with instructions to handle the converted Gray code here...▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Greetings from Germany,
G
1)could you tell me what cx is ? is it a register?
2) this part " rr cx" , i couldn't understand it, plz explain it , if it's possible for u
RR stands for "rotate right" -- essentially dividing the byte (register) by 2, presuming the carry has been cleared first (CLC instruction)