WEBVTT
1
00:00:00.000 --> 00:00:04.990
When we look at the binary numbers that are ordered from 1 and up
2
00:00:04.990 --> 00:00:06.720
we see an interesting phenomenon.
3
00:00:06.720 --> 00:00:11.720
Each time we reach a power of 2, all the bits (digits) change!
4
00:00:11.720 --> 00:00:15.000
Here is the binary table from 0 to 16.
5
00:00:15.000 --> 00:00:20.610
When advancing from 0 to 1... from 1 to 2,
6
00:00:20.610 --> 00:00:25.610
we go from 01 in binary code to 10,
7
00:00:25.610 --> 00:00:30.610
and when advancing from 3 to 4 we change 011 to 100, and so on.
8
00:00:30.610 --> 00:00:34.610
You can see that whenever we change from 0 to 1, from 1 to 2,
9
00:00:34.610 --> 00:00:42.610
from 3 to 4, from 7 to 8 or from 15 to 16, all the bits change.
10
00:00:42.780 --> 00:00:48.510
In digital devices that count things, like the speedometer in a car, this property may be a problem.
11
00:00:48.680 --> 00:00:52.920
In any electronic device, there is always a risk that something will malfunction,
12
00:00:52.920 --> 00:00:57.510
especially when changes are made, such as when one bit is changed into another.
13
00:00:57.510 --> 00:01:01.510
If all the bits are changed at once, the risk is much bigger.
14
00:01:01.510 --> 00:01:05.880
This problem exists even in meters that are based on the decimal system – like a row of cogwheels
15
00:01:05.880 --> 00:01:10.880
where each one has the digits 0 to 9 (in old-fashioned speedometers).
16
00:01:10.880 --> 00:01:16.510
When the number changes from 9999 to 10000, all the wheels rotate at once,
17
00:01:16.510 --> 00:01:19.510
and this raises the risk of a technical malfunction.
18
00:01:19.510 --> 00:01:25.040
This was exactly the motivation for Frank Gray, an American Physicist, to invent a symbology in which
19
00:01:25.040 --> 00:01:29.510
in every move between two consecutive numbers, only one digit is changed.
20
00:01:29.740 --> 00:01:34.240
Gray's method is appropriate for any counting system (decimal, binary, etc.),
21
00:01:34.240 --> 00:01:38.510
and when it is used in the binary system, it is called "Gray Code".
22
00:01:38.510 --> 00:01:42.860
Here is a table of the numbers 0 to 15 in Gray Code.
23
00:01:42.860 --> 00:01:48.930
Only one digit is changed when advancing from one number to the number after it.
24
00:01:49.120 --> 00:01:54.930
Note that one bit changes between every single consecutive line.
25
00:01:54.930 --> 00:01:59.930
From decimal zero to one - the furthest right hand bit changes.
26
00:01:59.930 --> 00:02:04.930
From 1 to 2, the second bit from the right changes and so on.
27
00:02:04.930 --> 00:02:11.930
A surprising fact is that there is more than one Gray Code that fulfils these demands!
28
00:02:11.930 --> 00:02:18.290
This means that this here is not the only table we can come up with.
29
00:02:18.290 --> 00:02:23.290
There are many other “Gray code” tables for the numbers between 0 to 15,
30
00:02:23.290 --> 00:02:39.290
for example, here are 2 different binary Gray codes for the numbers 0 to 7.
31
00:02:39.290 --> 00:02:45.580
In this example, all the numbers except zero are encoded differently.
32
00:02:45.580 --> 00:02:55.660
Take the number 7 for instance. Here it is encoded 0100 and here 0010.
33
00:02:55.660 --> 00:03:04.740
However in both tables these values, 0100 and 0010
34
00:03:04.740 --> 00:03:10.640
are both one bit different from the bit representation in the line above.
35
00:03:10.640 --> 00:03:25.880
So, How many different Gray encodings are there for a given range of numbers?
36
00:03:25.880 --> 00:03:31.210
The number of possible Gray Codes for different numbers is enormous - extremely large.
37
00:03:31.380 --> 00:03:38.520
There are 91,392 possible Gray Codes just for coding the numbers 0 to 15,
38
00:03:38.520 --> 00:03:45.740
and to find the number of possible Gray Codes for the numbers 0 to 255, you will probably need to wait for a very long time.
39
00:03:45.740 --> 00:03:49.720
This is an "open" problem in math – a problem that has not yet been solved!
40
00:03:49.720 --> 00:03:56.210
Even a very powerful computer can't calculate this number but maybe it will be possible in the future.
41
00:03:56.210 --> 00:04:10.210
The recreational mathematician Martin Gardner writes about Gray Codes in his book "Knotted Doughnuts and Other Mathematical Entertainments".
42
00:04:10.210 --> 00:04:17.210
He shows that all the possible Gray Codes for a given number of bits,
43
00:04:17.210 --> 00:04:21.210
can be generated from a drawing of the corresponding n-cube.
44
00:04:21.210 --> 00:04:26.210
This means that you can generate all the possible 2-bit Gray codes by drawing a square,
45
00:04:26.210 --> 00:04:29.680
all the possible 3-bit Gray codes by drawing a cube,
46
00:04:29.680 --> 00:04:36.210
all the possible 4-bit Gray codes by drawing a 4-dimensional hypercube and so on.
47
00:04:36.210 --> 00:04:39.210
Let’s see how this is done for the 2-bit case.
48
00:04:39.210 --> 00:04:47.210
We’ll generate two (for example) of the eight possible Gray codes for the numbers zero to three.
49
00:04:47.210 --> 00:04:52.700
So, draw a square, and label each vertex
50
00:04:52.700 --> 00:05:00.110
with binary numbers so that there is only one different bit between any two adjacent vertices.
51
00:05:00.110 --> 00:05:08.520
So we’ll draw our square and label it clockwise 00, 01,11 and 10.
52
00:05:08.520 --> 00:05:17.110
Every vertex is just one bit different from the two adjacent vertices.
53
00:05:17.110 --> 00:05:22.860
Now, we trace the square starting from one vertex and traveling along all its sides,
54
00:05:22.860 --> 00:05:26.350
passing through each vertex exactly once.
55
00:05:26.350 --> 00:05:35.120
A path like this, one that visits all the vertices in a graph exactly once, is known as a "Hamiltonian Path",
56
00:05:35.120 --> 00:05:40.780
after the famous, late, Irish mathematician, William Rowan Hamilton.
57
00:05:40.780 --> 00:05:46.170
If we start at the vertex labeled "00" and trace the square clockwise,
58
00:05:46.170 --> 00:05:52.640
we get the sequence 00, 01, 11 and 10.
59
00:05:52.640 --> 00:05:56.170
This is one possibility for a Gray Code for the numbers zero to three:
60
00:05:56.170 --> 00:06:02.540
with 00 = 0, 01 = 1, 11 = 2 and 10 = 3.
61
00:06:02.540 --> 00:06:07.720
There is another way to generate a Gray code - to start with the vertex "10", for example,
62
00:06:07.720 --> 00:06:10.600
and trace the square counter- clockwise.
63
00:06:10.600 --> 00:06:18.480
In this case, we get the sequence 10, 11, 01 and 00,
64
00:06:18.480 --> 00:06:25.960
and the Gray Code will be 10 = 0, 11 = 1, 01 = 2 and 00 = 3.
65
00:06:25.960 --> 00:06:30.960
Since we can start with any of the four vertices, there are 4 times 2 equals 8
66
00:06:30.960 --> 00:06:33.040
2-bit Gray codes.
67
00:06:33.040 --> 00:06:39.920
Doing the same thing on a cube will generate the 144 different 3-bit Gray codes for the numbers 0-7.
68
00:06:39.920 --> 00:06:48.240
One main disadvantage of Gray codes is that there is no straightforward way to convert them from binary code to Gray Code.
69
00:06:48.240 --> 00:06:56.530
In order to solve this problem, mathematicians found a way to convert a binary number into one specific kind of Gray Code.
70
00:06:56.760 --> 00:07:01.530
This Gray Code is called "reflected" Gray Code.
71
00:07:01.760 --> 00:07:06.140
Here is how to change a binary number to binary reflected Gray code.
72
00:07:06.140 --> 00:07:11.140
Let’s take an example the number twelve - in binary - 1100.
73
00:07:11.140 --> 00:07:17.750
Go over the digits of the binary number from right to left: 0, 0, 1, 1.
74
00:07:17.750 --> 00:07:23.280
If the digit to the left of the digit you are looking at is 0,
75
00:07:23.280 --> 00:07:28.750
as is the case in the example, leave the digit alone. Otherwise reverse the digit you are looking at.
76
00:07:28.920 --> 00:07:33.750
o, we leave this 0 alone because the digit to its left is 0,
77
00:07:33.920 --> 00:07:41.750
this 0 we reverse or flip, because the digit to its left is 1. So we change it to 1.
78
00:07:41.750 --> 00:07:47.750
This 1 has a 1 to the left of it so we reverse it and it becomes 0.
79
00:07:47.750 --> 00:07:55.540
This 1 has a 0 to it, the leading zero, so its left alone.
80
00:07:55.540 --> 00:08:02.500
The binary number 1100 is equal to 1010 in reflected Gray Code.
81
00:08:02.500 --> 00:08:07.750
Now let’s do the other direction and convert from reflected Gray Code to binary. Here’s how we do this.
82
00:08:07.960 --> 00:08:14.420
We’ll change the number 1010 which is in Gray back into binary.
83
00:08:14.420 --> 00:08:21.340
So, go over the digits of the number in reflected Gray Code from right to left.
84
00:08:21.340 --> 00:08:26.340
If the sum of the digits that are to the left of the digit you are looking at
85
00:08:26.340 --> 00:08:31.340
is an even number, leave the digit alone. Otherwise reverse it.
86
00:08:31.340 --> 00:08:37.400
The sum of the digits to the left of this zero is 2 which is even, so we leave this 0 alone.
87
00:08:37.400 --> 00:08:46.750
The sum of the digits to the left of this 1 is 1 which is odd, so we flip it and it becomes a 0.
88
00:08:46.750 --> 00:08:52.200
This 0 also has a sum of 1 to the left of it so we reverse it and it becomes 1.
89
00:08:52.200 --> 00:09:01.750
This 1 has a 0 to the left of it, the leading zero, this is odd so its left alone.
90
00:09:01.750 --> 00:09:09.460
The binary-reflected Gray code number 1010 is equal to 1100 in binary.
91
00:09:09.460 --> 00:09:14.460
And that’s a bit about Gray Codes - note the pun...