For Coderz - Код Грея и оптимизация программ.

<b>For Coderz</b> - Код Грея и оптимизация программ.

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

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
         
         INC   E
         SET   5,L
         
         SET   1,E
         SET   6,L
         
         DEC   E
         RES   5,L
         
         SET   2,E
         SET   7,L
         
         INC   E
         SET   5,L
         
         RES   1,E
         RES   6,L
         
         DEC   E
         RES   5,L
         
       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