Код Грея и оптимизация программ
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
