Info Guide
#10
30 апреля 2007 |
|
For Coderz - Код Грея и оптимизация программ.
Код Грея и оптимизация программ 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
Другие статьи номера:
Похожие статьи:
В этот день... 10 октября