вторник, 17 января 2012 г.

Код Грея

Рассмотрим все возможные комбинации из трёх цифр: нулей или единиц. Обычно из записывают в таком порядке:
000
001
010
011
100
101
110
111

То есть в виде двоичных представлений числе от 0 до 7. Однако эти 8 строки можно записать и так, чтобы каждая пара соседних элементов отличалась только одним символом:
000
001
011
010
110
111
101
100

Такое упорядочивание называется кодом Грея. Заметим, что первая срока от последней также отличается ровно одним символом.

Можно ли подобное сделать для шестнадцати строк от 0000 до 1111? Да, и вот какой способ формирования 4-битного кода Грея показал мне Кузнецов Сергей Тихонович.

Обозначим 4 двоичных цифры буквами A, B, C, D. А каждое из 16 чисел будет представлено ячейкой вот в такой таблице:

Если ячейка находится в колонке (строке), отмеченной буквой, в соответствующем разряде числа будет стоять единица. Иначе - ноль.

При такой разметке таблицы числа, стоящие в соседних ячейках, будут отличаться только одним разрядом. Поэтому код Грея можно сформировать, обойдя все ячейки, например, так:
Этот путь даст нам последовательность:
1100
1110
0110
0100
0101
0001
0000
0010
0011
0111
1111
1011
1010
1000
1001
1101

Её тоже можно зациклить и начинать с любого элемента.

2 комментария:

  1. Проще получать новый код при помощи «переворачивания».

    Например, записываем 3-битный код Грея сначала в прямом порядке, а потом в обратном. И дописываем перед первой половиной 0, а перед второй — 1. Получаем 4-битный год Грея.

    0000
    0001
    0011
    0010
    0110
    0111
    0101
    0100
    1100 -- начало второй половины в обратном порядке
    1101
    1111
    1110
    1010
    1011
    1001
    1000

    ОтветитьУдалить
  2. Да, точно, так проще, написал в следующем посте. Мне в таблице сама структура понравилась

    ОтветитьУдалить

Популярные сообщения

Темы

число цифра простые геометрия юмор язык дроби степень делимость пи методы история самоописывающее квадрат система счисления время узор задача корень структура тригонометрия е конструкция сайты формулы игра факториал функции приближение программа фрактал последовательность график комбинаторика память вероятность пределы конкурс логарифм треугольник неизвестное интеграл уравнение видео комплексные магический квадрат палиндром правильно-неправильное действие софизм заблуждения процесс ряды цитаты книги окружность прогрессия среднее стереометрия число фи выражения графы проценты логика парабола разрезания символ 2014 Фибоначчи клеточный автомат матрица производная статистика фокус головоломка кривая куб шахматы действия иллюзия новости оказывается оригами построение сложение термин тетраэдр