Breaking News
Programmable Logic DesignLine Blog

"n-ary" (non-Boolean) Gray codes (Part Deux)

NO RATINGS
View Comments: Newest First | Oldest First | Threaded View
Page 1 / 2   >   >>
Hillbilly Jimmy
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
Hillbilly Jimmy   10/22/2008 7:58:59 PM
NO RATINGS
(er, n'er mind.) Missed the cyclic req. from 20 -> 00 (with the twinned binary).

Hillbilly Jimmy
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
Hillbilly Jimmy   10/22/2008 7:52:02 PM
NO RATINGS
Try this (note the bit symmetry: 0 = 100 or 011 1 = 110 or 001 2 = 010 or 101 It seems a little wasteful, but if you need all 3 digits to have twins (and you do) that's 6 values. Not counting 000 and 111, (not sure whether that's important) 6 values is all you get with 3 bits. 00.....100..100.....100100 01.....100..110.....100110 02.....100..010.....100010 12.....110..010.....110010 10.....110..011.....110011 11.....110..001.....110001 21.....010..001.....010001 22.....010..101.....010101 20.....010..100.....010100 Q: what comes next in the series? A: 20 is obvious, but after that, it's not 22... Twin values is an odd "allow"ance...

Max The Magnificent
User Rank
Blogger
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
Max The Magnificent   10/16/2008 4:58:24 PM
NO RATINGS
OK -- now I understand why you were using dots as spacers -- let's try that formatting again.... ------------------- Wow -- I didn't realize this would generate so much interest. One trick I'm dorking around with in my head at the moment is that a 2-bit binary field supports four values 00, 01, 10, 11, but we need only three of these to represent the ternary digits 0, 1, and 2. Soooo ... I?ve been wondering about using two codes to represent one ternary value. For example Ternary . . . Binary .....0........00 and 10 .....1.............01 .....2.............11 I haven't yet gotten this to work, but .... maybe ...

Max The Magnificent
User Rank
Blogger
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
Max The Magnificent   10/16/2008 4:56:55 PM
NO RATINGS
Wow -- I didn't realize this would generate so much interest. One trick I'm dorking around with in my head at the moment is that a 2-bit binary field supports four values 00, 01, 10, 11, but we need only three of these to represent the ternary digits 0, 1, and 2. Soooo ... I?ve been wondering about using two codes to represent one ternary value. For example Ternary Binary 0 00 and 10 1 01 2 11 I haven't yet gotten this to work, but .... maybe ...

probinson
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
probinson   10/16/2008 2:10:44 PM
NO RATINGS
Well, that came out all screwed up. Let's try this. The fact that odd bases roll over after an odd number of possible combinations makes it impossible for any such Gray code to be mapped directly to binary. You will always have a transition from an even number of bits being 1 or 0 back to the same, requiring a change of two bits. In order to map your ternary code to binary you need to make the total combinations an even number. One obvious method is to simply double the base. For a ternary Gray code we could simply add one more bit and map each of our ternary codes to a pair of senary codes. One way to implement this is to add one more bit which changes in place of the normal rollover. A simple XOR of the added bit with all other bits could also be used to decode the duplicate sequence bringing it pretty close to the ternary Gray we were after. ..Decimal..Ternary...Gray Code...XOR Decode ....0........00.......0.0000..->..0000 ....1........01.......0.0001..->..0001 ....2........02.......0.0011..->..0011 ....3........10.......0.0111..->..0111 ....4........11.......0.0110..->..0110 ....5........12.......0.0100..->..0100 ....6........20.......0.1100..->..1100 ....7........21.......0.1110..->..1110 ....8........22.......0.1111..->..1111 ....0........00.......1.1111..->..0000 ....1........01.......1.1110..->..0001 ....2........02.......1.1100..->..0011 ....3........10.......1.1000..->..0111 ....4........11.......1.1001..->..0110 ....5........12.......1.1011..->..0100 ....6........20.......1.0011..->..1100 ....7........21.......1.0001..->..1110 ....8........22.......1.0000..->..1111 ....0........00.......0.0000..->..0000 ....:.........:..........:........:

probinson
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
probinson   10/16/2008 2:02:50 PM
NO RATINGS
The fact that odd bases roll over after an odd number of possible combinations makes it impossible for any such Gray code to be mapped directly to binary. You will always have a transition for on even of bits being 1 of 0 back to the same, requiring a change of two bits. In order to map your ternary code to binary you need to make the total combinations an even number. One obvious method is to simply double the base. For a ternary Gray code we could simply add one more bit and assign map each of our ternary codes to a pair of senary codes. One way to implement this is to add one more bit which changes in place of the normal rollover. A simple XOR of the added bit with all other bits could also be used to decode the duplicate the sequence bringing it pretty close to the ternary Gray we were after. Decimal Ternary Gray Code XOR Decode 0 00 0 0000 -> 0000 1 01 0 0001 -> 0001 2 02 0 0011 -> 0011 3 10 0 0111 -> 0111 4 11 0 0110 -> 0110 5 12 0 0100 -> 0100 6 20 0 1100 -> 1100 7 21 0 1110 -> 1110 8 22 0 1111 -> 1111 0 00 1 1111 -> 0000 1 01 1 1110 -> 0001 2 02 1 1100 -> 0011 3 10 1 1000 -> 0111 4 11 1 1001 -> 0110 5 12 1 1011 -> 0100 6 20 1 0011 -> 1100 7 21 1 0001 -> 1110 8 22 1 0000 -> 1111 0 00 0 0000 -> 0000 : : : :

probinson
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
probinson   10/13/2008 4:31:09 PM
NO RATINGS
Well, further reading on this worm Max has put in my head has lead me to conclude that as long as only one digit changes per incremental count it is considered Gray code but only even based Gray codes translate to electronic implementation.

probinson
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
probinson   10/13/2008 2:45:49 PM
NO RATINGS
While the code you proposed, limiting the error to 2, is certainly a drastic reduction in error, I think a Gray code needs to limit the error from missed transitions to 1 rather than one digit. With that being said, if I needed a code for Ternary numbering, for some reason, an error of 2 would quite probably be acceptable. As for mapping odd bases to binary, that is obviously not possible if you use restrict adjacent counts to one bit transition. If you relax the constraint to allow adjacent count errors 2 then any base can be used.

jadwin79
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
jadwin79   10/13/2008 1:27:13 AM
NO RATINGS
Just to summarize more clearly: I answered the first question in the blog: "Now, this isn't to say that it isn't possible to come up with some sequence that passes through all nine combinations and returns to 00 with only a single digit change each time. But I'm a bit busy at the moment, so I'll hand this over to you... can you come up with such a sequence?" The harder question that followed is still unanswered, although the answer is probably "no": "And, if so, can you map binary values onto the ternary digits such that we have Gray codes in both bases?"

jadwin79
User Rank
Rookie
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
jadwin79   10/13/2008 1:12:09 AM
NO RATINGS
You are making an assumption about what the meaning of "Gray code" is. The whole point of ternary (and higher) codes is that we don't expand each digit in a lower-base representation, we are concerned only with that base -- there is NO need to look at the digits in binary (or decimal, re your last comment) from a theoretical point of view. If you define a Gray code as being one where only one digit (in that base) changes (which is the standard definition), then there are many ternary gray codes. If you add the additional restriction that the jumps must be +/- 1, then of course there are none. You are making a perfectly valid connection to practical things like voltages and such in your comments, whereas I (and I think the original blogger) were concerned more with the abstract concept of Gray codes extended to higher bases than 2.

Page 1 / 2   >   >>
August Cartoon Caption Winner!
August Cartoon Caption Winner!
"All the King's horses and all the KIng's men gave up on Humpty, so they handed the problem off to Engineering."
5 comments
Top Comments of the Week
Like Us on Facebook

Datasheets.com Parts Search

185 million searchable parts
(please enter a part number or hit search to begin)
EE Times on Twitter
EE Times Twitter Feed
Flash Poll
Radio
LATEST ARCHIVED BROADCAST
David Patterson, known for his pioneering research that led to RAID, clusters and more, is part of a team at UC Berkeley that recently made its RISC-V processor architecture an open source hardware offering. We talk with Patterson and one of his colleagues behind the effort about the opportunities they see, what new kinds of designs they hope to enable and what it means for today’s commercial processor giants such as Intel, ARM and Imagination Technologies.