Breaking News
Programmable Logic DesignLine Blog

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

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

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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...

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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 ...

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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 ...

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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 ....:.........:..........:........:

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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 : : : :

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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.

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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.

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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?"

User Rank
Author
re: "n-ary" (non-Boolean) Gray codes (Part Deux)
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   >   >>