Міністерство освіти та науки України Національний університет “Львівська політехніка” Звіт до лабораторної роботи № 1 На тему: Бітова арифметика. Алгоритмічна реалізація коду Грея. Створення консольних Windows-програм на основі Microsoft Visual Studio .NET Варіант №4 Мета роботи: отримати навики по розробленню консольних Windows-програм CLR за допомогою інструментарію Visual C++ 2005, алгоритмічно реалізувати кодер/декодер Грея, дослідити основні бітові операції алгоритмічної мови С++ та на їх основі навчитися виконувати різноманітні маніпуляції над бітовими послідовностями. Завдання Для заданого числа А вибрати необхідний цілочисельний тип даних C++, що відповідає кількості розрядам n. Написати консольну CLR програму, яка реалізує такий алгоритм (після кожного пункту вивести отриманий результат в десятковій та двійковій формах; наступні обчислення проводяться для модифікованого значення попереднього пункту): Вивести число А у консолі. Порахувати кількість розрядів, що займає число А. Перетворити число А у код Грея. 4. Підрахувати к-сть одиничних бітів тривіальним способом. 5. Виконати реверс бітів у кожному байті біт. послідовності методом перемішування. 6. Визначити парність біт. послідовності за формулою (5.2). 7. Здійснити інверсію 5, 8, 14 бітів 8. Виконати зворотні перетворення, щоб в кінцевому результаті отримати вхідне число А. n = 16 A=11267 Теоретичні відомості Реверс бітів. Під операцією реверса бітів мається на увазі відображення вмісту слова відносно його середини, тобто розміщення бітів у слові у зворотному порядку: rev(0x01234567)=0xE6A2C480 rev(00000001001000110100010101100111) = 11100110101000101100010010000000 h 1. Тривіальний спосіб. У циклі побітово зчитується усе слово та записується у нове слово. Зчитування починається з наймолодшого біту до найстаршого заданого слова. Зчитаний біт записується у наймолодший біт нового слова, яке після цього зсувається на 1 біт вліво. unsigned int word = 3093512288, revers, mask; mask = 1; revers = 0; for (int i=0;i<32;i++) { revers = revers << 1; if (word & mask) revers = revers ^ 1; mask = mask << 1; } //word: 10111000011000110100000001100000 //revers 00000110000000101100011000011101 h 2. Метод перемішування. Спершу міняються місцями сусідні біти, потім – сусідні 2-бітові поля, далі – сусідні 4-бітові поля і т.д. Перемішування можна виконувати і у зворотному порядку. Алгоритмічно це реалізовується шляхом накладання відповідних числових масок операцією AND та зсувом на сусідню позицію, аналогічно з сусідньої позиції профільтровані значення суміжною маскою зсуваються в протилежний бік. Для слова з
виглядає так: unsigned int word = 3093512288; word = (word & 0x55555555) << 1 | (word & 0xAAAAAAAA) >> 1; word = (word & 0x33333333) << 2 | (word & 0xCCCCCCCC) >> 2; word = (word & 0x0F0F0F0F) << 4 | (word & 0xF0F0F0F0) >> 4; word = (word & 0x00FF00FF) << 8 | (word & 0xFF00FF00) >> 8; word = (word & 0x0000FFFF) << 16 | (word & 0xFFFF0000) >> 16; Код Грея Код Грея отримав свою назву по імені фізика Франка Грея (Frank Gray). Цей код, який ще називають рефлексним (відбитим), застосовують у пристроях, що перетворюють вимірювану величину в двійковий код. Якщо при такому перетворенні використовується звичайний двійковий код, то деякі розташовані поряд кодові комбінації відрізняються в декількох розрядах. Наприклад, комбінація 0111 (цифра 7) та 1000 (цифра 8) відрізняються у всіх розрядах, і тому при зчитуванні може виникнути велика похибка. Натомість, код Грея при переході від однієї кодової комбінації до сусідньої відрізняється лише одним розрядом (табл. 6.1). Кодування. Звичайний двійковий код перетворюється в код Грея шляхом сумування по модулю 2 даної комбінації з такою ж, але зсунутою вправо на один розряд.
(6.1) Мовою С++ це виглядає так: unsigned int Bin = 123456789, Gray; Gray = Bin ^ (Bin >> 1); Декодування. Перетворення коду Грея в двійковий починається з молодшого розряду шляхом сумування за модулем 2 цифр у коді Грея, починаючи зі старшого розряду та закінчуючи розрядом. що перетворюється. Наприклад, при перетворенні коду Грея 1011 (рис. 6.1) в молодшому розряді комбінації двійкового коду запишеться 1, так як
. У другому розряді буде 0, так як
. У третьому розряді запишеться 1, так як у третьому розряді коду Грея стоїть 0, а в четвертому 1. Запишеться 1 також і в останньому розряді, так як в останньому розряді коду Грея стоїть 1. Таким чином, комбінація Коду Грея 1011 у двійковому коді прийме вигляд 1101. Алгоритмічно це перетворення реалізується за такою формулою:
(6.1) Мовою С++ це виглядає так: unsigned int Gray = 83241887, Bin = 0; for (int i=0; i<32; i++) Bin = Bin ^ (Gray>>i); Як бачимо, реалізація декодера Грея ідентична алгоритму визначення парності слова згідно формули (5.2). Також для декодера можна використати і метод сканування (5.3), який виконує декодування значно швидше. unsigned int Gray = 83241887, Bin; Bin = Gray; for (int i=1; i<32; i*=2) Bin = Bin ^ (Bin >> i); Для виведення числа у двійковому вигляді у вікно консолі ми можемо перетворити це число з десяткового у двійкове класичним способом ділення на 2. Список використаних змінних Mask – маска яка накладається на число Worker – допомагає обрахувати кількість розрядів Word – допоміжна змінна зберігає задане число Counti – обрахунок кількості одиничних бітів Count - обрахунок кількості розрядів A - задане число цілочисельного типу Bin – використовується для декодування коду Грея Gray - використовується для перетворення заданого числа в код Грея Parity – присвоює значення парності чи непарності числа Остаточна версія програми // lab1.cpp : main project file. #include "stdafx.h" using namespace System; void main (void) { short byte =11267 , mask,worker,word,counti,count = 1, A,bin, Gray,parity; // 1 A=byte; Console::WriteLine(L"10-forma - {0}",byte); String ^line = ""; do { if (byte % 2) line = "1" + line; else line = "0" + line; byte = byte / 2; } while (byte >= 2); if (byte > 0) line = "1" + line; Console::WriteLine(L"2-forma - {0}",line); //2 worker=A;count = 1; while (worker>1) { worker = worker/2; count++; } Console::WriteLine(L"Kikistj Rozrjadiv - {0}",count); // 3 Gray Code A = A ^ (A >> 1); Gray=A; Console::WriteLine(L"Gray10-forma - {0}",A); line = ""; do { if (Gray % 2) line = "1" + line; else line = "0" + line; Gray = Gray / 2; } while (Gray >= 2); if (Gray > 0) line = "1" + line; Console::WriteLine(L"Gray2-forma - {0}",line); //4 1bity word=A; mask = 1; count = 0; for (int i=0; i<16; i++) { if (word & mask) count ++; mask = mask << 1; } Console::WriteLine(L"Kikistj 1 - bitiv {0}",count); // 5 revers A = (A & 0x5555) << 1 | (A & 0xAAAA) >> 1; A = (A & 0x3333) << 2 | (A & 0xCCCC) >> 2; A = (A & 0x0F0F) << 4 | (A & 0xFF00) >> 4; word=A; Console::WriteLine(L"Revers10-forma - {0}",A); line = ""; do { if (word % 2) line = "1" + line; else line = "0" + line; word = word / 2; } while (word >= 2); if (word > 0) line = "1" + line; Console::WriteLine(L"Revers2-forma - {0}",line); //6 parnistj word=A;parity=0; for (int i=0; i<32; i++) parity = parity ^ (word >> i); parity = parity &1; Console::WriteLine(L"Parnistj {0}",parity); //7 invers mask = 0x4120; A = A ^ mask; word=A; Console::WriteLine(L"Invers10-forma - {0}",A); line = ""; do { if (word % 2) line = "1" + line; else line = "0" + line; word = word / 2; } while (word >= 2); if (word > 0) line = "1" + line; Console::WriteLine(L"Invers2-forma - {0}",line); Console::ReadKey(true); } Результат виконання програми: Висновок: Я отримав навики по розробленню консольних Windows-програм CLR за допомогою інструментарію Visual C++ 2005, алгоритмічно реалізував кодер/декодер Грея, дослідив основні бітові операції алгоритмічної мови С++ та на їх основі навчився виконувати різноманітні маніпуляції над бітовими послідовностями.