Kombinatorične Grayeve kode

diplomsko delo

Maja Vidner (Author), Matjaž Kovše (Mentor)

Abstract

Veliko naprav v elektromehaniki uporablja sistem prikazovanja pozicij z odpiranjem in zapiranjem stikal. Če ta naprava uporablja binarno kodo, so možnosti za napačno branje pozicije bitov in posledično napačen izhod podatka, velike. Ker se binarne besede med seboj razlikujejo za več kot en bit in ker se stikala v napravah ne premikajo sinhrono, bi morale biti spremembe bitov med besedami čim manjše. Tukaj nastopi uporaba Grayeve kode, katere značilnost je sprememba samo enega bita med bitnimi besedami. V prvem delu diplomskega dela je predstavljen binarni številčni sistem, ki je osnova za razvoj in gradnjo Grayevih kod. Nadalje je opisana povezava in pretvarjanje med binarno in Grayevo kodo. V drugem delu je predstavljena definicija Grayevih kod in generiranje le-teh z rekurzivnim algoritmom, znanim pod imenom binarna reflektirana Grayeva koda. Opisani sta tudi uravnotežena in monotona Grayeva koda, ki predstavljata posebni različici Grayevih kod. Nadalje so predstavljene kombinatorične Grayeve kode za permutacije, kombinacije in particije celih števil. Opisana je tudi bijekcija med nizom particij in funkcijo omejene rasti. V zadnjem delu so predstavljeni praktični primeri, ki so lahko rešeni s pomočjo uporabe različnih Grayevih kod.

Keywords

matematika;kombinatorika;Grayeve kode;binarne kode;bitna beseda;diplomska dela;

Data

Language:	Slovenian
Year of publishing:	2011
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[M. Vidner]
UDC:	51(043.2)
COBISS:	18845960
Views:	2736
Downloads:	143
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	COMBINATORIAL GRAY CODES
Secondary abstract:	Many devices in electromechanics use a system of indicating position by closing and opening switches. If those devices use binary codes, the chance for reading spurious positions is increased. Because binary strings differ in more than one bit and switches do not change states exactly in synchrony, the bit changes should be reduced in order for device to give us the right result. At this point Gray code is a perfect solution, considering that Gray code is a binary numeral system, where two successive values differ in only one bit. In this thesis the first part is dedicated to describe binary numeral system which is the base for generating Gray codes. Further on in this work is the description of relation between binary and Gray codes. In the second part is presented the definition of Gray code and generating of the code with recursive algorithm, known as binary reflected Gray code. Further in this part of work there are presented combinatorial Gray codes for permutations, combinations and integer partitions. Also in this part are described balanced Gray codes and their construction. In the last part are presented practical problems, that can be solved using Gray codes.
Secondary keywords:	Binary code;bit string;Gray code;balanced Gray code;monotone Gray code;combinatorial Gray code.;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	51 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19701