Elektrotehniški vestnik 74(4): 213-216, 2007 Electrotechnical Review, Ljubljana, Slovenija
Tabelarična pretvorba Grayeve kode v dvojiško število
Rajko Mahkovic, Roman Hribar
Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, Tržaška 25, 1000 Ljubljana, Slovenija E-pošta: rajko.mahkovic@fri. uni-lj.si
Povzetek. V članku predstavljamo tabelarično pretvorbo Grayeve kodne besede v dvojiško število, kije zasnovana na strategiji deli in vladaj. Algoritem vhodno besedo razdeli na particije, ki jih z uporabo sorazmerno majhne tabele pretvori v dvojiške ekvivalente, nato pa pretvorjene dvojiške particije združi v ustrezno dvojiško število. Časovna kompleksnost se z 0(n) (n je dolžina Grayeve kodne besede -1), kakršna je zahtevnost navadne pretvorbe z verigo XOR, zmanjša na O(l + 1), kjer je / + 1 število particij vhodne kodne besede. Implementacija predlaganega algoritma v zbirnem jeziku za Motorolin mikrokrmilnik 68HC11 je v primerjavi z navadno pretvorbo skrajšala čas pretvorbe na polovico.
Ključne besede: Grayeva koda, pretvorba Grayeve kode, absolutni optični enkoder
Tabular conversion of the Gray code into a binary number
Extended abstract. A new Gray-to-binary number conversion algorithm which employes divide-and-conquer approach is presented. The algorithm splits the Gray codeword G into I + 1 partitions Gi,Go, by using a small table it obtains their binary number equivalents, E>i,..., Bo, and concatenates these binary partitions into complete corresponding binary number B. The conversion table holds all the binary equivalents of the Gray partition Gi. The concatenation of binary partitions depends on the values read from the table. The value of the current binary partition depends solely on the value of the least significant bit of the previous binary partition; if this bit is 0, the value of the corresponding binary equivalent of the Gray partition could be simply read from the table, if the bit is 1, the one's complement of the value from the table should be taken. Time complexity with respect to the conventional XOR conversion scheme is reduced from 0(n), where n is the length of the Gray codeword-1, to 0(1 + 1), I + 1 being the number of partitions. The proposed algorithm is especially convenient to be applied in small microprocessor-based systems with enough memory space to put the conversion table into. There is a trade-off between the conversion table size and conversion time. If we consider the whole Gray codeword in a trivial case as one partition, we get the shortest conversion time; on the other hand, considering each bit as one partition, leads us to the conventional conversion scheme. In between we have the opportunity to optimize the relationship between the required memory space and the conversion time for a specific system. In our implementation of the algorithm with an 8-bit conversion table in Motorola 68HC11 assembly language the conversion time was reduced approximately by a half, compared to the conventional conversion scheme.
Key words: Gray code, Gray code conversion, absolute optical encoder
1	Uvod
Grayeva koda [1] je tako urejeno zaporedje 2n+1 nizov, kodnih besed, da se sosednji kodni besedi razlikujeta le v enem bitu. Kadar govorimo o Grayevi kodi, ponavadi mislimo reflektirano binarno Gray evo kodo [2], kije dobila ime po lastnosti, da je druga polovica besed v nizu enaka prvi polovici v obrnjenem vrstnem redu, z izjemo najpomembnejšega bita; ta je invertirán. Obstajajo pa še druge Grayeve kode [2]. Grayeva koda se uporablja v absolutnih optičnih enkoderjih, A/D pretvornikih in v prenosih podatkov kot koda za odkrivanje in popravljanje napak [3]. Vlogo ima tudi na nekaterih matematičnih področjih [4].
Ker ni primerna za nadaljnjo rabo, se navadno najprej pretvori v (za računanje) ustreznejši zapis. V nadaljevanju predstavljamo novo pretvorbo iz Grayeve kode v dvojiško število, kije izvedena s pomočjo tabele.
2	Pretvorba
Naj bo B v dvojiškem številskem sistemu zapisano celo število v mejah 0 < B < 2n+1 — 1. B in njegovo predstavitev v Grayevi kodi G lahko zapišemo kot
B = Mn-i • • -Mo G = gngn-i---gigo-
Navadna pretvorba iz G v B je izvedena po naslednji rekurzivni shemi [2]
Prejet 26. februar, 2007 Odobren 16. marec, 2007
K = gn
bi =	© gi za z = n-l,...,l,0,

Gn
9k+1
9k
g i



h b0
Bi
Bn
Slika 1. Shema navadne pretvorbe razdeljene Gray eve kodne besede Figure 1. Scheme of conventional Gray-to-binary conversion
kjer 0 označuje operator XOR (ekskluzivni-OR).
Recimo, da Grayevo kodno besedo G pri nekem indeksu k (0 < k < n) razdelimo na dva dela, particiji: kodno besedo potem lahko zapišemo kot G = GiGo, njen dvojiški ekvivalent pa kot B = B\Bq. Shema navadne pretvorbe tako razdeljene Gray eve kodne besede je prikazana na sliki 1. Vidimo, daje v (kanonični) obliki navadne pretvorbe bit bk+i odvisen le od predhodnih g bitov, pretvorba Bo pa torej le od tega bita in seveda od
Zapišimo izraze za binarne bite desno od t°rej za spodnji del, Bo, pretvorjenega števila, za primer, ko je
h+i = 0.
b°k = 9k bl-i = 9k-\®9k
(1)
= 9o 0 gi 0 ... 0 gk
(Veljavnost le za ta primer označujejo nadpisani indeksi 0.) Kot smo lahko pričakovali, biti v Bo sploh niso odvisni od prednjega dela kodne besede; del Bo lahko dobimo le iz Go-
V drugem primeru, ko je bk+i = 1, veljajo izrazi
bi = 9k b\-i = 9k-i®9k
(2)
bo = £o0£i0...0£fc.
Iz primerjave izrazov 1 in 2 uvidimo lahko veljavnost naslednjh relacij: b\ = b® in Bq = Bq. Z uporabo te relacije in razdelitvijo poljubno dolge Gray eve kodne besede na l +1 particij pridemo do učinkovitega algoritma za pretvorbo:
(i)	razdeli G na G i particij e
(ii)	previousLSB = 0
(iii)	for i = I downto 0 do
Bi = G2BTab[Gi} if previousLSB = 1 then
Bl = Bl previousLSB = LSB[Bi\ enddo (iv) združi Bi v B.
G2BTab[•] je tabela, v kateri biti particij e G i pomenijo indeksa elementa tabele z ustreznim dvojiškim ekvivalentom Bi particije G i, LSB[-] pa označuje najmanj pomemben bit v prejšnji (v dvojiškem številskem sistemu zapisani) particiji. Uporaba tabelarične pretvorbe je upravičena v tem, da je pridobivanje določene Bi in s tem celega B hitrejše kot manipulacija z zaporednimi biti v XOR verigi navadne pretvorbe, vsaj za programske implementacije algoritma. Opaziti velja poseben odnos med prostorom in časom, pogosto najdenim v analizi algoritmov, med velikostjo tabele in časom pretvorbe. Najhitrejša pretvorba bi seveda bila, da vhodne kodne besede sploh ne bi razdeljevali na particije, da bi torej pretvarjali z eno samo veliko tabelo. Toda tako velika potrata pomnilniškega prostora v namenskih mikroračunalniških sistemih, kjer se pretvorba ponavadi uporablja, ni sprejemljiva. Na drugi strani pa imamo trivialen primer 1-bitne particije, ki je pravzaprav navadna pretvorba XOR.
3 Primer
Na primeru bomo pokazali pretvorbo 24-bitne kodne besede v Grayevi kodi FF34FCg z uporabo 8-bitnih particij in torej tudi 8-bitne tabele, podane v tabeli 1. Tabela je urejena v 16 vrstic s po 16 vrednostmi. Prva vrstica, označena z 0x, na primer, vsebuje vseh šestnajst dvojiških števil, katerih Gray eve kode se začenjajo z 0 (07 = 0,^6 = 0,05 = 0,04 = 0). Podobno velja za stolpce: sedmi stolpec (x6), na primer, vsebuje vseh šestnajst dvojiških števil, katerih Gray eve kode se končujejo na 6 (03 = 0, g2 = 1,01 = 1, go = 0). (Na dlani je sicer, da delitev kodne besede ni omejena ne po velikosti ne po številu particij. Niti ni nujno, da so vse enako dolge, toda v tem primeru potrebujemo za vsako dolžino svojo tabelo.) Zaradi krajšega zapisa bomo kodne besede zapisovali s šestnajstiškimi števkami. Po danem algoritmu pretvorimo najpomembnejšo
	xO	xl	x2	x3	x4	x5	x6	xl	x8	x9	xA	xB	xC	xD	xE	xF
Ox	00	01	03	02	07	06	04	05	OF	0E	OC	0D	08	09	0B	OA
lx	IF	IE	1C	ID	18	19	IB	1A	10	11	13	12	17	16	14	15
2x	3F	3E	3C	3D	38	39	3B	3A	30	31	33	32	37	36	34	35
3x	20	21	23	22	27	26	24	25	2F	2E	2C	2D	28	29	2B	2A
4x	7F	7E	7C	7D	78	79	7B	1A	70	71	73	72	77	76	74	75
5x	60	61	63	62	67	66	64	65	6F	6E	6C	6D	68	69	6B	6A
6x	40	41	43	42	47	46	44	45	4F	4E	4C	4D	48	49	4B	4A
7x	5F	5E	5C	5D	58	59	5B	5A	50	51	53	52	57	56	54	55
8x	FF	FE	FC	FD	F8	F9	FB	FA	F0	Fl	F3	F2	F7	F6	F4	F5
9x	E0	El	E3	E2	E7	E6	E4	E5	EF	EE	EC	ED	E8	E9	EB	EA
Ax	CO	CI	C3	C2	Cl	C6	C4	C5	CF	CE	CC	CD	C8	C9	CB	CA
Bx	DF	DE	DC	DD	D8	D9	DB	DA	DO	Dl	D3	D2	D7	D6	D4	D5
Cx	80	81	83	82	87	86	84	85	8F	8E	8C	8D	88	89	8B	8A
Dx	9F	9E	9C	9D	98	99	9B	9A	90	91	93	92	97	96	94	95
Ex	BF	BE	BC	BD	B8	B9	BB	BA	B0	BI	B3	B2	B7	B6	B4	B5
Fx	AO	Al	A3	A2	Al	A6	A4	A5	AF	AE	AC	AD	A8	A9	AB	AA
Tabela 1. Tabela pretvorbe 8-bitnih besed iz Grayeve v binarno kodoTable 1. Table for 8-bit Gray-to-binary conversion
Grayevo particijo G 2 = F F s pomočjo tabele v B2 = A A (šestnajsta vrstica, šestnajsti stolpec tabele). Ker je LSB[AA] = 0, lahko tudi pretvorbo naslednje Grayeve particije G\ = 34 preberemo kar neposredno iz tabele: B1 = 27. Toda LSB[27] = 1 določa, da je treba nad pretvorbo, iz tabele prebrane zadnje Grayeve particije, Go = F C, izvesti eniški komplement: Bo = A8 = 57. Združitev B2, Bi in Bo nam da celotno dvojiško število B = AA2151b-
Opisano pretvorbo smo implementirali v zbirnem jeziku v 16-bitnem absolutnem optičnem enkoderju firme RLS, Ljubljana, v katerem se uporablja maska z Grayevo kodo in je zasnovan na Motorolinem 68HC11 mikrokr-milniku (dvojiški zapis pozicije je samo eden njegovih izhodnih formatov). Čas pretvorbe se je v primerjavi s časom pretvorbe z verigo XOR zmanjšal na polovico. Uporabili smo 8-bitni particiji; tabela, dolga 256 bajtov, je bila najboljša izbira, saj ustreza širini podatkovnega vodila, kar je optimalno.
4 Sklep
Opisana tabelarična pretvorba kodnih besed iz Grayeve v dvojiško število temelji na metodi deli in vladaj: vhodno kodno besedo v Grayevi kodi razdeli na več particij, pretvori te manjše particije vsako posebej in rezultate združi. Združevanje dvojiških particij je odvisno od njihovih vrednosti: vrednost vsake naslednje dvojiške particije je odvisna od najmanj pomembnega bita prejšnje dvojiške particije. Če je ta bit enak nič, je
veljavna kar iz tabele prebrana vrednost, če je ena, je prava dvojiška particij a eniški komplement vrednosti iz tabele. Kompleksnost pretvorbe se z 0(n) (kjer je n dolžina Grayeve kodne besede -1), ki jo ima navadna pretvorba, zmanjša na 0(1 + 1), kjer je l + 1 število particij. Opisana pretvorba je posebno primerna za implementacije v mikroračunalniških sistemih, kjer imamo dovolj pomnilnika za tabelo. Velikost tabele sicer lahko prilagodimo razpoložljivemu pomnilniku, saj izberemo tako velikost particije, ki bo glede na porabo pomnilnika in hitrost pretvorbe optimalna.
V naši implementaciji algoritma v zbirnem jeziku za Motorolin mikrokrmilnik 68HC11 smo čas pretvorbe glede na čas klasične pretvorbe zmanjšali na polovico.
5 Literatura
[1]	F. Gray, Pulse Code Communication, U. S. Patent 2 632 058, March 17, 1953.
[2]	Gray code, Wikipedia, spletna enciklopedija,
http ://en.wikipedia.org/wiki/Gray_code
[3]	P. Mecklenburg, W.K. Pehlert, and D.D. Sullivan, "Correction of Errors in Multilevel Gray-Coded Data", IEEE Transactions on Information Theory, 1973, Vol.IT-19(3), pp.336-340.
[4]	E.M. Reingold, J. Nievergelt, N. Deo, Combinatorial Algorithms: Theory and Practice, Englewood Cliffs, NJ: Prentice-Hall, 1977.
Rajko Mahkovic je zaposlen na Fakulteti za računalništvo in informatiko v Ljubljani. Raziskovalno se ukvarja z mobilnimi roboti, pozicijskimi napravami in drugimi sistemi v realnem času. Izpeljal je več projektov v industriji, med drugim je zasnoval programsko opremo za numerični krmilnik Iskra CNC-2T.
Roman Hribarje zaposlen v Telekomu Slovenija, kjer dela kot sistemski administrator velikih računalnikov z operacijskim sistemom UNIX.