Close

Gray Codes

A project log for Ternary Computing Menagerie

A place for documenting the many algorithms, data types, logic diagrams, etc. that would be necessary for the design of a ternary processor.

mechanical-advantageMechanical Advantage 04/21/2019 at 07:560 Comments

Gray codes are any bit (or trit, qubit, etc.) sequence that changes in only one position between any digit-pattern and the next. This included the transition between the last pattern and the first in the sequence. Each code represents a specific value, but not necessarily the same value as if you simply counted the bit pattern normally as a number.

There are a number of uses gray codes such as error detection and correction, modulating digital sequences onto analog signals (i.e. radio) and the transmission of data between components with different clock rates.

There are a number of different binary gray codes. Here are some examples for various lengths:

As you can see, each pattern in the sequence only changes in one bit position at a time. This includes the switch from the last position back to the first position.

Let's see if you can do the same thing in a balanced ternary number system. I won't bore anyone with my path from "no clue" to "no problem". Instead I'll just jump straight ahead to the method I found to construct a balanced ternary gray code for any arbitrary number of digits.

First, we need to know which patterns of trits to throw out right away. Any pattern which does not include all three trit values (-,0,+) in equal numbers is obviously not going to work. So we can immediately toss out all patterns other than the following, given in sequence and with their heptavintimal name:

Any one of the above forms a 1-trit gray code by themselves. Thus there are 6 different 1-trit gray codes. To form a 2-trit gray code, simply take one of the above...

...follow it by another one that starts where the last one ends (two possible options)...

... and follow that by one more that starts where the last ended AND ends where the first one began...

...Now take the first of those three patterns, put it in the next most significant digit position, and stretch it out to three symbols for each symbol...

... and voila! You made a 2-trit gray code! How about 3-trits? Take your existing code and now copy the least significant digit position twice more, tripling it's length...

... now remember how we stretched out the first triplet in the 2nd digit position? Do that again with the second and third triplets.

... and finally take the first symbol, place it in the next most significant digit position, and strrreeeccchhh it out to 9 symbols per symbol...

... and you have a 3-trit gray code. Wash, rinse, repeat. Want an 847 billion value gray code? Just keep doing that until it is 25 trits wide. Or more, or whatever. The figures to the right show the pattern of changes as being regular and consistent.

As a side note, as long as you consider that swapping from - to + or from + to - is a shift of only one degree, then every ternary gray code is also only shifting one degree of value at any given time. If you consider that such a transition is shifting two values, then some transitions (like - to 0) are 1 degree while others (- to +) are two degrees.

Discussions