Gray code and its application
The console has four switches and a button, each switch can pull one of ON and OFF, written in bold ON the OPEN button.Only when the four switch ON/OFF state in a unique combination, right after the press of a button to open the door to the chamber of secrets (but you don't know what is the correct combination).You need to do is clear: open switch, try all kinds of ON/OFF, then press a button, open the door until success so far.In order to with the fastest speed to escape the chamber of secrets, what are you going to do?
A game of thinking
A few years ago, I played with a third person adventure game, already can't remember the name of the game, the only impressive is the scenario above.To avoid yourself forget what combination has tried, we only need one by one according to certain rule to try all the combinations.With the number 0, for example, to represent the OFF state, by the number 1 ON state, and then according to the law of the binary number, in turn, try 2 ? = 16 different
combinations: 0000, 0001, 0010, 0011, 0100,..., 1110, 1111.Among them, from 0000 to 0001 to throw a switch, from 0001 to 0010 to throw two switch...The most horrible is, from 0111 to 1000 to throw all four open shut.In the worst case, the final test to the combination is the right combination, the whole process, we want to pull (total of 26 times switch!More importantly, in the game, throw a switch is very difficult, you need to continue to hold down a button for a long time.
Then, an interesting question arises: in an attempt to order, can make us less throw several switch?At least need to throw several switch?
Easy to see, because we have to try to 16 different combinations, so that the whole process must be at least throw 15 times switch.Will throw 15 times switch is enough?This means that every combination between two adjacent only vary the position of a switch.So the ideal solution is really exists, that I don't know;But I immediately thought of at the time, if you tried all three switch after 2 = 8 kinds of combinations, only throw seven times switch is, indeed, can do it.This is equivalent to the edge of the cube is without repetition and without missing after each vertex.One of the project is shown in figure 1, it corresponds to the test sequence is as follows.
Figure 1 to 8 01 three series as the cube of eight vertices, between two 01 series have an edge if and only if they are only one
At that time my idea is simple: if we know that how to rapid traverse the three all the combination switch, then simply keep the first switch OFF state, the tangible such as 0???????The combination of all try again:
The next?My idea is that the first level 1, and then traverse again like just after the combination of the three.0100 into 0100 need to throw two switch, again after the combination of the three all try again and need to switch to seven, finally, a total of 16 flipped a switch, well, already very good.But, just pull out the first switch, turn 0100 to 1100, this would like to continue after the three back to 000, but had a subconscious to: 1100 is a new combination.Simply put the combination tried again.
Then, just as I was with a large stick to knock woke up, I suddenly realize: thenstarting from 1100, against the just after the order of traversal of all three combination, finally not to go back to 1000?
In this way, we can realize the throw 15 times switch without repetition and without omission to traverse the four switch all 16 kinds of combinations, each throw a switch just get is a kind of new composite!
Using a similar way, we can continue to expand, the 32 five 01 is arranged in a column, make each 01 on to the next 01 chain only need a change.Eight, of course, just the three 01 series order, itself can also be regarded as the more basic extension.We can, in fact, as in table 1, from a list of the most basic situation 01 departure, continuously through the "mirror image" and "tian's first" approach, and eventually get the 2 ⁿ n bit 01 solution string in a row, the adjacent two 01 string always only one.
Table 1 generated image binary encoding method
Let's give it a name, called "image binary code".
The story of the PCM signal converter
When people began to realize digital communication, once for how to convert analog signals into digital signals.In 1937, British scientists Alec Reeves has developed a method for digital to analog signals, which we now call the pulse code modulation (pulse code modulation, abbreviated as PCM maybe we will be more familiar with some).Suppose we have a voice, its waveform diagram is shown in figure 2.So, we have equal interval about some points on the timeline, look Look at this time the height of the waveform figure is in what position, and said to a binary number.If you use the five binary number, then every sampling results has 32 different values, can with the 0 to 31 in the decimal should be relatively.For ordinary human voice, in order to fully portray the shape of a wave, in theory only if need to sample at least 8000 times per second;The higher sampling frequency, restore the real sound effect is better.
Figure 2 pulse code modulation schemes
This encoding is good, the key is, how to design a signal converter, let it can automatically converts analog signals into digital signals by this way?Can't hire a few people to human flesh to complete sampling and conversion of thousands of times per second.
Figure 3 with a cathode ray tube to produce a signal converter
People with a cathode ray tube ably and X, Y, two groups of deflection plate to solve the problem.As shown in figure 3, gun shot first electron beam passes between two pieces of Y deflection plate, and by Y deflection plate produced by the electric field of the deflection, the deflection is determined by the input signal amplitude;After the deflection of the beam to continue passes between two pieces of X deflection plate, and subject to the influence of electric field and deflection.Potential difference of X deflection plate is determined by a sawtooth wave generator, its effect is to make the electron beam continuously from left to right scan.Before the arrival of the electron beam electron collection screen, also must go through a with perforated "coding dish".If we want to convert each samples values to five 01 string of words, then coding plate holes should be as shown in figure 4.Combine all the things, the height of the electron beam can be according to the input signal in different place from left to right scan, every scan will produce a five 01 series, one means that the electron beam through the hole on the code set, 0 means that the electron beam was blocked by coding mask.If the electron beam in r ? shown in the height of the scan time, get five 01 string is
01101, or a decimal 13.
The principle of the signal converter is clever, but still have a certain distance between theory and practice.In practical application, we will encounter some unexpected problems.Let us assume that a sample value is 23.5, so the electron beam in figure 4 r ? height from left to
right scan again.Note that the scan line through the border of the four holes, so it is entirely possible that appear such errors: electron beam through the second hole of should also through the third, fourth and fifth of the hole.So this value finally is coded to 11111.Or, electron beam completely missed the hole on the back four position, then this value is coded to 10000.In the worst case, we might even put 15.5 code is 11111 or 00000, it is can't tolerate mistakes.How to do?
In 1947, bell LABS Frank Gray submitted a patent, beautifully solved the
problem.Frank Gray method is very simple: changing the traditional binary encoding to image binary code!A new coding plate as shown in figure 5.We use the first item in five image binary coding, which is 00000, to represent the value of the minimum height, or decimal 0;With mirror under the binary code of a, i.e., 00001, to represent the height of the small value, or a decimal 1;Similarly, in 00011, 2 in 00010 3, 4, expressed in 00110 by analogy, until 31 in 10000.So that any two adjacent height corresponds to the digital coding is only one difference, in other words just Passing through them the scan lines will only meet a border.If the height of the scan line is 15.5, then the converted result or 01000 (15) it represents, or 11000 (16) it represents, just the error of the problem is solved.
Said Frank Gray in the patent document, this new way of coding is not a name, and for the first time put forward the "mirror image binary code" (reflected binary code) the name.Later, people gradually began to use "Gray code" to refer to this kind of coding way, the name "Gray code" is fixed down slowly.
Gray code of other applications
In industry, Gray code and many applications.If there is a temperature (or water level, pressure, the score, etc.), detection system, when it detects numerical from 7 to 8, the system will change the 0111 to 1000.One thousand appeared in the process of change is just read operations, the read data is wrong.Using numerical of Gray code, add and subtract 1 operation will become true atomic operation, also can avoid this problem.
It is interesting to note that n a Gray code first 01 string and finally there was only one difference between a string of 01.Therefore, if the n a Gray code as a cycle, and any two adjacent 01 series still meet the requirements.Some direction sensor will use Gray code to
indicate direction, is used to this property of Gray code.For example, might as well use 000, 000, 001, 010, 110, 111, 101, 100, in turn, said eight directions, so no matter from which direction to which the direction of the adjacent, the corresponding 01 bunch is only changed one, so that there would be no errors of "intermediate value".