Из журнала Info Guide #10, Рязань, 05.2007



     Код Грея и оптимизация программ

Lord Vader

             I. Что это такое

   Код Грея  обычно применяется в тех слу-
чаях, когда измеряемый параметр изменяется
с шагом 1 последовательно во времени, нап-
ример, в механических валкодерах,некоторых
АЦП и т.д. Классический пример использова-
ния  кода Грея - сигналы с оптопар механи-
ческой мышки, имеющие вид

X:  _/~~~\___/~~~\_
Xq: ___/~~~\___/~~~

и являющиеся 2-битным кодом Грея.

   Основное свойство кода Грея - при пере-
ходе  к соседнему состоянию в N-битной ве-
личине  в коде Грея меняется только 1 бит.
Например, для 4-битной величины последова-
тельность кодов Грея будет следующей:

 0000
 0001
 0011
 0010
 0110
 0111
 0101
 0100
 1100
 1101
 1111
 1110
 1010
 1011
 1001
 1000

   Отсюда видно правило формирования кодов
Грея: на  каждом  шаге надо поменять самый
младший бит,который не приведёт к повторе-
нию кода.

   Возможно  также и непосредственно пере-
водить  обычный  двоичный код в код Грея и
назад. Перевод из обычного кода в код Грея
(примеры  на  ассемблере Z80) для 8-битной
величины:

Bin2Gray
        ;IN:  A - in binary code
        ;OUT: A - in Gray code
        LD    C,A
        SRL   C
        XOR   C
        RET

   Перевод обратно:

Gray2Bin
        ;IN:  A - in Gray code
        ;OUT: A - in binary code
        LD    C,A
        XOR   A
G2B_L
        XOR   C
        SRL   C
        JR    NZ,G2B_L
        RET

   Более подробно о коде Грея можно прочи-
тать в [1] и [2].


         II. Примеры оптимизации

   Представьте себе, что требуется напеча-
тать  символ  8х8  в линейный буфер экрана
(где строчки идут друг за другом и для пе-
рехода на соседнюю надо прибавить к адресу
32 ).
   Код получится такой:

       DUP   8
        LD    A,(DE)
        INC   E
        LD    (HL),A
        ADD   HL,BC ;BC=32
       EDUP

   Для прибавления 32 потребовалась аж це-
лая регистровая пара. Можно делать так:

        LD    A,L
        ADD   A,32
        LD    L,A

   Но  либо это совсем медленно, либо тре-
бует дополнительного регистра для хранения
числа 32.

   А  теперь попробуем перебирать адреса в
коде Грея:

        LD    A,(DE)
        INC   E ; SET 0,E
        LD    (HL),A
        SET   5,L    ; 000>001

        LD    A,(DE)
        SET   1,E
        LD    (HL),A
        SET   6,L    ; 001>011

        LD    A,(DE)
        DEC   E ; RES 0,E
        LD    (HL),A
        RES   5,L    ; 011>010

        LD    A,(DE)
        SET   2,E
        LD    (HL),A
        SET   7,L    ; 010>110

        LD    A,(DE)
        INC   E
        LD    (HL),A
        SET   5,L    ; 110>111

        LD    A,(DE)
        RES   1,E
        LD    (HL),A
        RES   6,L    ; 111>101

        LD    A,(DE)
        DEC   E
        LD    (HL),A
        RES   5,L    ; 101>100

        LD    A,(DE)
        LD    (HL),A ; 100

   Таким образом,мы как минимум избавились
от использования дополнительных регистров,
прибавив  почти такт к каждому копированию
(вместо INC E : ADD HL,BC - 2 SET/RES'а ).
Если же переставить байтики шрифта соотве-
тствующим  образом, то  можно везде писать
INC E - выигрыш очевиден.

   Аналогичную  технику можно использовать
и в других случаях (каких - сам думайте:).
Для удобства написания можно ввести 2 мак-
роса (пример для арабского ассемблера  aka
Аль-асма ;).

       MACRO GRAY
        \0
        INC   E
        SET   5,L
        \0
        SET   1,E
        SET   6,L
        \0
        DEC   E
        RES   5,L
        \0
        SET   2,E
        SET   7,L
        \0
        INC   E
        SET   5,L
        \0
        RES   1,E
        RES   6,L
        \0
        DEC   E
        RES   5,L
        \0
       ENDM


       MACRO DOIT
        LD    A,(DE)
        LD    (HL),A
       ENDM

 И далее:
 
        GRAY  DOIT

lvd^mHm  lvd#dgap.mipt.ru

               Литература:

1. П. Хоровиц, У. Хилл.
"Искусство схемотехники", гл.8.
2. http://en.wikipedia.org/wiki/Gray_code