Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Бітова арифметика. Алгоритмічна реалізація коду Грея. Створення консольних Windows-програм
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт
Предмет:
Інші
Група:
КС-33
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт до лабораторної роботи № 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, алгоритмічно реалізував кодер/декодер Грея, дослідив основні бітові операції алгоритмічної мови С++ та на їх основі навчився викону вати різноманітні маніпуляції над бітовими послідовностями.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора