Прикладное программирование и основы микропроцессорной техники

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Методические указания

к выполнению лабораторных работ

"Прикладное программирование и основы микропроцессорной техники"

1. Введение в системы счисления

1.1 Общие положения. Классификация систем счисления

Системой счисления называется совокупность приемов и правил для обозначения и наименования чисел.

Система счисления задает правила кодированной записи количественных эквивалентов, позволяющие для каждого числа однозначно получать его кодовую запись и по каждой кодовой записи - соответствующий ей количественный эквивалент.

Множество символов, используемых для такого представления, называют цифрами и служебными символами. Цифры это - 0,1,2,… и т.п. К служебным относятся необходимые для записи числа символы - запятая, плюс, минус и т.п.

В вычислительной технике применяются в основном системы счисления, которые получили название позиционных систем счисления.

Их «место» во множестве известных систем счисления иллюстрируется следующей классификацией СС

Коротко, не углубляясь в тонкости непозиционных систем, целесообразно отметить следующее.

Цифрам в непозиционных системах соответствует некоторый числовой эквивалент, который не изменяется при изменении позиции (места) цифры в числе. Характерны в этом смысле римская и единичная (унитарная) системы. В таких системах, например десятичному числу 6, соответствуют числа VI (в римской) и 111111 (в унитарной) СС. В унитарной СС используется всего одна цифра, например - 1. Этой цифре сопоставлен количественный эквивалент, равный единице, а функцией при вычислении количественного эквивалента кода числа здесь является операция сложения.

Непозиционные системы характеризуются сложными и громоздкими алгоритмами выполнения арифметических операций, поэтому они не получили значительного распространения в вычислительной технике, в которой более широко используются позиционные системы.

Систему счисления называют позиционной, если одна и та же цифра может принимать различные численные значения в зависимости от местоположения (разряда) этой цифры в совокупности цифр, представляющей заданное число.

Например, вес старшей цифры 3 в десятичном числе 33 в десять раз больше веса 3 в младшем разряде, а вес старшей цифры в двоичном числе 111 - в четыре раза больше веса младшей цифры.

Позиционные системы разделяют на однородные и смешанные. Во всех разрядах числа, представленного в однородной системе, используются цифры из одного и того же множества. Например, в обычной десятичной системе во всех разрядах любого числа используются цифры из множества {0,1, …, 9}, в двоичной системе - цифры из множества {0, 1} и т.п.

В смешанных системах множества цифр различны по характеру и мощности для разных разрядов числа. Примерами смешанных систем являются, например: система для измерения углов и дуг (в разряде градусов могут быть использованы - 360 различных цифр, обозначающих градусы как координату положения, в разрядах минут и секунд -60 различных цифр),

система измерения времени, например, в секундах, минутах, часах, сутках, неделях, система английских денежных единиц и т.п.

Если в позиционной системе для каждой цифры имеется отдельный символ, то ее называют системой с непосредственным представлением цифр. В позиционных системах с кодированным представлением цифр каждая цифра исходной СС кодируется определённой комбинацией из нескольких символов другой СС. Причём должно быть установлено взаимно-однозначное соответствие между количественным эквивалентом кодируемой цифры и количественным эквивалентом кодовой комбинации.

Примером кодированной системы, используемой в ЭВМ является двоично-десятичная система - BCD (Binary Coded Decimal). В такой системе каждая десятичная цифра представляется кодом, в качестве которого используется комбинация из четырёх цифр двоичной системы счисления - тетрада.

Преимущественное распространение получили позиционные однородные системы счисления. Находят практическое применение как системы с непосредственным представлением чисел, так и кодированные СС. Далее, целесообразно ввести следующие понятия.

Всякая позиционная система задаётся тремя компонентами (А, , F). При этом, А - множество цифр системы; - функция, определяющая для цифр в каждом разряде, их количественный эквивалент; F - функция, определяющая по количественным эквивалентам цифр в записи числа количественный эквивалент самого числа.

Если в системе множество цифр состоит из элементов 0, 1,……, q - 1, то система имеет естественное множество цифр (естественная система счисления).

Если q = m + k +1, а множество цифр делится на два подмножества - {-m, - m+ 1, - m+2,…, -1} и {0, 1, 2,…, k}, то если m= k то система имеет симметрическое множество цифр, если k > m или m > k, то имеет место асимметрическое, соответственно, в положительную или отрицательную сторону, множество цифр.

Системы с такими свойствами называются - симметрической (m= k) и асимметрической (k > m или m > k).

По виду функции системы классифицируются следующим образом.

Если значение функции и не совпадает при различных , то система называется весомозначной, где вес разряда. Если для любых цифр из множества A имеет место соотношение , то система имеет основание

Наконец, по характеру функции системы разделяются на аддитивные и мультипликативные.

Если в качестве этой функции используется функция сложения, то систему называют аддитивной (как в римской и в унитарной), если же используется функция умножения, систему называют мультипликативной.

В вычислительной технике используются позиционные, однородные системы счисления, с естественным кодированием. Кроме того, получили распространение и кодированные системы. Такие системы рассматриваются ниже более подробно.

1.2 Позиционные системы счисления. Полиномиальное представление чисел

В дальнейшем используются следующие понятия и термины.

Во-первых, число содержащее целую и дробную части наз. смешанным. Во-вторых, число, состоящее только из целой части наз. целым, а число, состоящее только из дробной части наз. дробным числом.

В позиционной однородной системе с естественным множеством цифр основанием системы (q) является количество цифр, используемых для представления чисел.

Это мощность множества A, т.е. .

Так как одно и то же число может быть представлено в нескольких системах счисления, то применительно к его представлению в q-ичной системе целесообразно употреблять термин q-ичное число и обозначать как . Важнейшим свойством позиционных систем с естественным множеством цифр является следующее.

В позиционной однородной системе с естественным множеством цифр и основанием q любое (n+m) - разрядное смешанное q-ичное число является полиномом.

Целая часть числа представляется полином вида



Дробная часть имеет вид

где ? основание системы счисления

? номер позиции цифры в числе {n-1, …0, - 1, - 2,…, - m}

{0,1,2,…, q-1} - цифра, соответствующая - ой позиции

? длина соответственно целой и дробной части числа.

Степень называется весом r-ой цифры (разряда) числа .

Смешанное число представляется суммой полиномов соответственно вида (1.1) и (1.2).

Если значение известно заранее, то числа обычно записывают в «привычной» символической форме

Представление числа в символической форме (1.4) наз. кодовой записью или кодом - ичного числа.

В выражении (1.4) запятая отделяет целую часть числа от дробной части, а для кодирования знака числа перед старшим разрядом используются служебные символы «+»,» - «. Знак «+» в положительном числе может не проставляться и подразумеваться «по умолчанию». Полиномиальное представления смешанного десятичного числа 873,56 имеет вид

Кодовые записи разных чисел в различных системах могут совпадать. Например, число 100 (сто) в десятичной системе и число 100 (четыре) в двоичной системе имеют одинаковые кодовые записи, но это разные числа, существенно отличающиеся по числовому эквиваленту. Поэтому, в кодовой записи числа необходимо указывать используемую систему счисления. Для известных систем достаточно указать основание системы. Для этого могут быть использованы следующие способы.

Во-первых, основание системы может быть указано в виде нижнего индекса после кодовой записи числа.

Во-вторых, в конце кода числа может использоваться идентификатор (суффикс), определяющий используемую систему счисления.

Таблица 1.1 - Способы указания системы счисления в коде числа

Обозначение системы в числе	Система счисления
	Десятичная	Двоичная	Восьмеричная	Шестнадцатеричная	Двоично-десятичная
Используемый индекс	10	2	8	16	2-10
Буквенный идентификатор	D или d	B или b	Q или q	H или h	BCD

Например, записи 1011011,10101₂ или 1011011,10101 означают, что для представления числа используется система счисления с основанием q=2.

Приведенные в табл. 1.1 аббревиатуры буквенных идентификаторов означают:

§ D (decimal) для десятичной системы счисления,

§ B(binary) для двоичной системы счисления,

§ Q (octal) для восьмеричной системы счисления,

§ H(hex) для шестнадцатеричной системы счисления,

§ BCD - Binary Coded Decimal для двоично-десятичной системы.

Так как, q-ичного числа, представленные в соответствующих позиционных системах - полиномы, то элементарные арифметические операции сложение / вычитание, умножение / деление могут интерпретироваться как операции над полиномами. Это прослеживается на примере формализованных правил типа сложение «в столбик», умножение «в столбик» и т.д.

1.3 Системы счисления, применяемые в микропроцессорной технике

В практике находят широкое применение следующие системы счисления.

Десятичная. Привычная система с основанием в которой используется десять цифр . В этой системе могут представляться исходные данные, решаются контрольные примеры и выводятся на различные носители и средства визуального отображения результаты, полученные при вычислении.

Двоичная. Основание двоичной системы. Используется только две цифры . Такая система естественно описывает состояния дискретных элементов (ключевых схем), являющихся базой микропроцессорной схемотехники. На этой системе основываются аналитические бинарные модели дискретных устройств.

В двоичной системе счисления целой и дробной частям смешанного число соответствуют следующие полиномиальные представления.

Например, целой части двоичного числа соответствует двоичный полином вида

Дробная часть этого числа запишется в виде

Очевидно, что для получения двоичного полинома при представлении весовых коэффициентов и цифр должны использоваться правила двоичной системы счисления. Более того, все операции в полиноме (умножение, возведение в степень, сложение) должны выполняться по правилам двоичной арифметики.

В этом случае имеет место полиномиальное представление двоичного числа в виде двоичного полинома.

Система не лишена недостатков: для представления целых чисел в системе с основанием 2 необходимо больше разрядов, чем, в других систем с непосредственным представлением чисел (см. Рис. 1).

Шестнадцатеричная. Система с основанием , в которой используется шестнадцать цифр . Цифрами, превышающими по значению 9, служат прописные буквы латинского алфавита. В этой системе счисления полиномиальное представление смешанного числа, например, имеет следующий вид.



Дробная часть

Шестнадцатеричная система в силу компактности записи числа обеспечивает компактный вывод данных и результатов на средства визуального отображения - электролюминесцентные и жидкокристаллические индикаторы, в поля ввода-вывода экранных форм и т.п. Это преимущество шестнадцатеричных систем счисления очевидно из Рис. 1, на котором приведены символические экраны для вывода десятичного числа в виде шестнадцатеричного числа и в виде двоичного .

Восьмеричная СС. Это система с основанием , в которой используется восемь цифр {0,1,2,…, 7}.

В восьмеричной системе счисления смешанное число, например выражается в следующем виде.

Целая часть числа представляется как полином вида

Дробная часть имеет вид



Обобщая вышесказанное, необходимо сделать следующие выводы.

Для получения - ичного полинома -ичного числа необходимо все элементы полинома представлять в -ичной системе счисления.

Более того, все операции в полиноме (умножение, возведение в степень сложение) должны выполняться по правилам - ичной арифметики.

Обращает на себя внимание, что кодовые записи оснований во всех системах счисления выглядят одинаково -10. Однако, это разные по количественному эквиваленту числа, а именно .

Двоично-десятичная система счисления (BCD (Binary Coded Decimal)). Относится к двоично-кодируемым позиционным системам.

Основанием системы является десятичное число 10, а для кодирования десятичных цифр используется десять двоичных четырехразрядных комбинаций (тетрад). Каждая комбинация однозначно соответствует десятичной цифре в десятичном числе.

Известно, что число двоичных четырехразрядных комбинаций превышает число цифр десятичной системы счисления - 10.

Вследствие этого возникает дополнительная проблема выбора оптимального соответствия между десятичными цифрами и двоичными тетрадами (кодирование).

Актуальность решения задачи выбора кода усугубляются тем, что каждый тип отображения цифра > тетрада порождает код с уникальными свойствами.

Число различных вариантов кодирования определяется как число размещений с перестановками из шестнадцати элементов (число возможных тетрад -) на десяти местах. Оно может быт подсчитано как



Подсчёты показывают, что число кодов около 6 млн. (!). Пригодность и эффективность конкретного кода для машинных расчётов - различна.

Поэтому при выборе кода желательно, чтобы были учтены некоторые ограничения и требования.

Известны пять основных требований (критериев), которые сформулированы Рутисхаузером.

1. Единственность. Необходимо однозначное соответствие цифр и тетрад. Если это требование не выполнено, то невозможно кодирование и декодирование чисел.

2. Упорядоченность. Большим десятичным цифрам должны соответствовать большие (по количественному эквиваленту) тетрады. Выполнение этого требования необходимо при сравнении кодированных чисел.

3. Четность. Четным десятичным цифрам должны соответствовать четные тетрады (тетрады, у которых в крайнем правой разряде стоит нуль), а нечетным цифрам - нечетные тетрады.

4. Дополнительность. Если цифры десятичной системы таковы, что сумма их равна девяти, то им должны сопоставляться тетрады, которые взаимно инвертированы, т.е. получаются друг из друга заменой единиц на нули, а нулей на единицы. Выполнение этого требования необходимо для того, чтобы ввести в двоично-десятичной системе дополнительный или обратный код.

5. Весомозначность. Должны существовать четыре веса таких, что если десятичной цифре сопоставлена тетрада (), то имеет место равенство

.

К весомозначности приводит, например, следующий способ кодирования: каждая десятичная цифра кодируется ее записью в двоичной системе с использованием полинома вида (1.1).

В этом случае цифра 5 будет закодирована тетрадой 0101, цифра 6 - тетрадой 0110 и т.д. Такой способ кодирования называется кодом прямого замещения с весами (8, 4, 2, 1). В этом случае количественный эквивалент цифры равен количественному эквиваленту соответствующей тетрады.

Кодирование, удовлетворяющее всем пяти требованиям, называется совершенным.

Код прямого замещения не является совершенным. Действительно, он удовлетворяет всем требованиям Рутисхаузера, кроме четвертого. Нарушение этого требования не позволяет вводить дополнительный или обратный код, что в свою очередь не позволяет заменить вычитание операцией сложения.

Для выполнения свойства дополнительности можно кодировать десятичную цифру тетрадой Т(х), равной . Полученный код называется кодом с избытком 3, или кодом Штибитца.

Для выполнения свойства дополнительности можно кодировать десятичную цифру тетрадой Т(х), равной . Полученный код называется кодом с избытком 6.

Однако, кодирование с избытком 3 и 6 как и код прямого замещения, не является совершенным т. к. не обладает свойством весомозначности.

Коротко останавливаясь на свойствах возможных вариантов кодирования, целесообразно выполнить следующий анализ.

Для кодирования единицы необходимо, чтобы один из весов был равен 1. Если считать, что р₀ = 1, то необходимо чтобы р₃ + р₂+ р₁ = 8. Возможны следующие комбинации весов (р_3, р₂, р₁) с точностью до их перестановки: (6,1,1), (5,2,1), (4,2,2), (3,2,3), (4,1,3).

Соответствующие варианты кодирования (комбинации весов) сведены в таблицу.

Таблица 1.2 - Варианты двоично-десятичного кодирования

Кодируемая десятичная цифра x	Значение тетрады Т(х) в системе счисления
	(8,4,2,1)	(6,1,1,1)	(5,2,1,1)	(3,3,2,1)	(4,3,1,1)	(2,4,2,1)	х + 3
0	0000	0000	0000	0000	0000	0000	0011
1	0001	0001	0001	0001	0001	0001	0100
2	0010	0011	0100	0010	0010	0010	0101
3	0011	0111	0101	0011	0100	0011	0110
4	0100	-	0111	0101	0110	0100	0111
5	0101	-	1000	1010	1001	1011	1000
6	0110	1000	1010	1100	1011	1100	1001
7	0111	1001	1011	1101	1100	1101	1010
8	1000	1011	1110	1110	1110	1110	1011
9	1001	1111	1111	1111	1111	1111	1100

Данные таблицы позволяют сделать следующие выводы.

В системе с весами (8,4,2,1) отсутствует свойство дополнительности.

Для случая (6,1,1,1) нарушается первое требование Рутисхаузера: для цифр 4 и 5, т.е. отсутствуют соответствующие тетрады.

В системе с весами (5, 2, 1, 1) не выполняется требование четности для цифр 4 и 5. В системе с весами (3, 3, 2, 1) не выполняется требование четности для цифр 4 и 5.

Число в десятичной СС	Число в двоичной СС	Число в шестнадцатеричной СС	Число в восьмеричной СС	Число в двоично-десятичной СС
				Код прямого замещения	Код Айкена-Эмери
00	0000	0	0	0000 0000	0000 0000
01	0001	1	1	0000 0001	0000 0001
02	0010	2	2	0000 0010	0000 0010
03	0011	3	3	0000 0011	0000 0011
04	0100	4	4	0000 0100	0000 0100
05	0101	5	5	0000 0101	0000 0101
06	0110	6	6	0000 0110	0000 1100
07	0111	7	7	0000 0111	0000 1101
08	1000	8	10	0000 1000	0000 1110
09	1001	9	11	0000 1001	0000 1111
10	1010	A	12	0001 0000	0001 0001
11	1011	B	13	0001 0001	0001 0001
12	1100	C	14	0001 0010	0001 0010
13	1101	D	15	0001 0011	0001 0011
14	1110	E	16	0001 0100	0001 0100
15	1111	F	17	0001 0101	0001 0101
16	10000	10	20	0001 0110	0001 1100
17	10001	11	21	0001 0111	0001 1101
0,0625	0,0001	0,1	0,04	0,0000011000100101	0,0000110000100101
0,125	0,001	0,2	0,1	0,000100100101	0,000100100101
0,25	0,01	0,4	0,2	0,00100101	0,00100101
0,375	0,011	0,6	0,3	0,001101110101	0,001111010101
0,5	0,1	0,8	0,4	0,0101	0,0101
0,625	0,101	0, A	0,5	0,011000100101	0,110000100101
0,75	0,11	0, C	0,6	0,01110101	0,11010101

В системе с весами (4, 3, 1, 1) не выполняется требование четности для цифр 2, 3, 6, 7.

Кодирование с избытком 3, как и код прямого замещения, не является совершенным т. к. не обладает свойством весомозначности

В системе с весами (2, 4, 2, 1) все пять требований выполнены, соответствующая арифметика является совершенной и называется в честь авторов - арифметикой Айкена-Эмери.

Двоично-десятичные системы эффективны при решении задач обработки больших массивов десятичных чисел. Например, при обработке массивов десятичных параметров (экономические задачи). В этом случае, за счет упрощения процедур перевода десятичных чисел в BCD-систему и обратно, может быть достигнуто повышение производительности вычислительного средства.

1.4 Некоторые свойства позиционных однородных систем с естественным множеством цифр

Для чисел, представимых в виде полиномов (1.1), (1.2) характерны несколько основополагающих и существенных для практики свойств, которые рассматриваются ниже.

Свойство 1. Значение цифры разряда для целой части числа в раз больше значения такой же цифры в ( разряде Например, цифра 9 во втором разряде целого десятичного числа 99 в десять раз больше (с учетом веса) цифры 9 в первом разряде.

Свойство 2. Значение цифры разряда для дробной части числа в раз меньше значения такой же цифры в (( разряде . Например, цифра 1 во втором разряде десятичной дроби 0,11 в десять раз меньше (c учетом веса) цифры 1 в первом разряде.

Систему счисления порождающую числа со Свойствами 1,2 называют системой с естественным порядком весов. Существуют также системы с искусственным порядком весов (например, Айкена-Эмери), для которых указанное соотношение весов одинаковых цифр в соседних разрядах не является обязательным.

Свойство 3. Минимальный модуль смешанного числа отличающегося от нуля, а также дробного числа представимого согласно (1.2), равен

.

Свойство 4. Максимальное количество чисел одного диапазона, которые можно представить на разрядах, определяется как

.

Свойство 5. Для представления N различных чисел в системе с основанием необходимо не менее

разрядов. Здесь запись означает, что если число в скобках - дробное, то оно округляется в сторону ближайшего большего целого.

Следующее свойство имеет важное практическое значение.

Пусть смешанное - ичное число содержит непрерывную последовательность максимальных в этой системе счисления цифр. Пусть при этом, последовательность условно начинается со стороны младших разрядов числа с позиции b (begin), а заканчивается на позиции с номером e (end) (Рисунок 2).

Свойство 6. Количественный эквивалент непрерывной последовательности максимальных цифр, начинающейся с позиции b и заканчивающейся на позиции e, определяется как



При этом, и

Очевидно, что числовой эквивалент последовательности с указанными свойствами может быть определен также как сумма вида

Свойство может быть доказано следующим образом. Уменьшаемое и вычитаемое разности (1.5) в кодовом виде - это числа вида 0…100…0 и 0…, 0010…, т.е. числа, содержащие единицу в единственном разряде с позицией определяемой весами Единица вычитаемого формирует заем из единицы уменьшаемого, который распределяется в виде максимальных цифр по всем промежуточным позициям разности. Такое правило вычитания справедливо для всех систем рассматриваемого типа, что является доказательством Свойства 6.

Доказательство иллюстрируется рисунком 3. Рисунок 3а показывает, что результат вычитания равен количественному эквиваленту десятичного числа , которое представляет собой непрерывную последовательность из пяти максимальных десятичных цифр с началом в позиции и окончанием в позиции

Свойство 7. Максимальный модуль либо положительного, либо отрицательного смешанного (n+m) - разрядного числа, которое может быть представлено в форме (1.1) и (1.2). определяется как



Действительно, максимальное по модулю q-значное число должно содержать во всех значащих разрядах максимальные цифры, т.е. может рассматриваться как непрерывная последовательность максимальных цифр с параметрами и . Соответствующая подстановка параметров в выражение (1.5) доказывает Свойство 7.

Свойство 8. Из свойства 6 следует, что максимальные модули целого и дробного чисел равны, соответственно

для целого числа:

для дробного числа:

Действительно, максимальное целое число можно рассматривать как непрерывную последовательность максимальных цифр, начинающуюся с позиции и заканчивающуюся на позиции .

Максимальное дробное число - последовательность максимальных цифр с началом и концом .

Соответствующие подстановки параметров b, e в выражение (1.5) доказывает Свойство 8.

Свойство 9. В силу особого места, занимаемого двоичной системой счисления, целесообразно уточнить Свойства 6-8 применительно к этому случаю.

Свойство 9.1. Количественный эквивалент непрерывной двоичной последовательности, начинающейся с позиции b и заканчивающейся позицией e (Рисунок 2), определяется как

При этом, и

Свойство 9.2. Максимальный модуль либо положительного, либо отрицательного смешанного (n+m) - разрядного двоичного числа, которое может быть представлено в форме (1.1) и (1.2) определяется как

Свойство 9.3. Из свойства 3 следует, что максимальные модули целого и дробного двоичных чисел равны, соответственно

для целого двоичного числа:

для дробного двоичного числа:

Замечание. Свойство 6 и Свойство 9.1 позволяет упростить реализацию некоторых арифметических операций, а также операций по преобразованию чисел, например, из двоичной в десятичную систему счисления Существенно упрощается, например, перевод двоичных чисел типа в десятичную систему. Непосредственное и «громоздкое» решение, а именно, суммирование полиномиальных коэффициентов , может быть заменено вычислением разности . Для «ручных» вычислений упрощение существенно.

2. Преобразование чисел из одной системы счисления в другую

Для практической деятельности актуальна задача преобразования чисел из одной системы счисления в другую (конвертирование). Задача состоит в преобразовании числа, заданного в исходной системе счисления с основанием , в другую (требуемую) СС с основанием Задача может решаться как «вручную» (подготовка данных, решение контрольных примеров, контроль результатов и т.п.), так и путем машинного преобразования. Во втором случае, имеет место ряд особенностей, связанных со специфическим представлении данных в МПТ.

2.1 Методы конвертирования

счисление цифра система преобразование

Для преобразований могут использоваться следующие методы:

1. Метод подбора.

2. Метод замещения полиномиальных элементов (поэлементное замещение).

3. Преобразования по схеме Горнера.

4. Метод «цифра за цифрой».

5. Метод, основанный на специфическом соотношении оснований заданной и требуемой систем счисления.

6. Метод «через промежуточную систему счисления».

Далее коротко прослеживаются теоретические основы каждого метода, способы реализации, возможности и ограничения, области преимущественного использования.

2.2 Метод подбора

Метод используется для преобразований «в уме», хотя не не исключена и его машинная реализация. Служит в основном для преобразований из десятичной в двоичную систему счисления. В этом случае, метод описывается следующей процедурой.

Процедура 2.1

1. Подбирается ближайшая снизу к заданному числу (текущему остатку) степень двойки, не превосходящая числа (остатка). В соответствующей позиции двоичного числа записывается единица. Промежуточные (пропущенные) старшие позиции заполняются нулями.

2. Определяется разность между числом (текущим остатком) и значением подобранной степени. Разность наз. текущим остатком.

3. Если разность не равна 0 или не отрицательна, то переход на п. 1.

Иначе: конец.

Конец

Процедура интуитивно понятна, но требует знания степеней двойки. Выполняется в десятичной арифметике. Теоретически возможно использование метода для преобразования в другие системы счисления. Однако в системах отличных от двоичных, требуется в качестве вычитаемых из текущего остатка использовать не только значения степени недвоичных оснований, а их произведения на соответствующие цифры. В этом случае подбирается не только ближайшая степень основания требуемой системы счисления, но и соответствующая ему цифра.

Таблица 2.1 - Степени двойки для преобразования целого числа

Степень
Десятичный эквивалент	2	4	8	16	32	64	128	256	512	1024	2048	4096

Таблица 2.2 - Степени двойки для преобразования дробного числа

Степень
Десятичный эквивалент	0,5	0,25	0,125	0,0625	0,0 3125	0,015625	0,0078125

2.3 Метод замещения полиномиальных элементов (поэлементное замещение)

Процедура преобразования методом поэлементного замещения имеет следующий вид.

Процедура 2.2

1. Число заданное в исходной системе счисления с основанием , представляется в виде суммы полиномов (1.1) и (1.2) в системе с основанием .

2. Все цифры и числа, используемые в полученном полиноме заменяются их представлениями в системе .

3. Выполняются операции над измененными полиномиальными членами по правилам требуемой системы счисления. К таким операциям относятся - возведение в степень оснований, умножение полученных степеней на цифры.

4. Полученные произведения складываются

5. Полученная сумма - число в новой системе счисления.

Процедуру целесообразно пояснить на следующем примере.

Пример 2.1 Выполнить методом поэлементного замещения преобразование .

Этап 1. Представление заданного двоичного числа в виде

Этап 2. Замещение двоичных чисел их десятичными эквивалентами

На этом этапе корректность преобразований обеспечивается тем, что все элементы исходного полинома заменяются (замещаются) их числовыми эквивалентами в требуемой системе счисления. Следовательно, числовые значения полиномиальных коэффициентов, а, следовательно, и полиномов в целом, равны между собой. Полученный полином пока не является числом в системе . Его можно интерпретировать как десятично-двоичный полином, требующий для конверсии дальнейших преобразований.

Этап 3. Поэлементные преобразования в требуемой системе счисления имеют вид .

Слагаемые в правой части сохраняют количественные эквиваленты полиномиальных членов исходного двоичного полинома, т.е. например, ,

Этап 4. Перераспределение количественных эквивалентов в полиномиальном представлении десятичного числа иное, чем двоичном.

Правильно перераспределить количественные эквиваленты можно, используя операцию десятичного сложения

Таким образом,

Метод интуитивно понятен при преобразованиях из двоичной в десятичную системы счисления. В этом случае, преобразования обычно начинают со второго этапа.

Особенности метода поэлементного замещения состоят в следующем. Требуется различать особенности и возможности метода при преобразованиях целых и дробных чисел.

Целые числа. Метод универсален в том смысле, что обеспечивает преобразования из любой исходной системы в любую требуемую. В этом случае имеют место лишь различия в сложности процедур.

Дробные числа. Метод обеспечивает преобразования Однако, имеются ограничения при преобразованиях из десятичной системы в двоичную, восьмеричную и шестнадцатеричную системы.

Смешанные числа. Рассматривая смешанные числа как сумму целого и дробного числа, можно сделать вывод об ограниченных возможностях метода при преобразовании дробной части смешанного десятичного числа в другие системы.

Для целых чисел универсальность метода подтверждаются следующими примерами.

Пример 2.2 Выполнить методом поэлементного замещения преобразование .

Этап 1. Представление заданного двоичного числа в виде

Этап 2. Замещение двоичных чисел их шестнадцатеричными эквивалентами

В правой части получен шестнадцати-двоичный полином.

Этап 3. Поэлементные преобразования в шестнадцатеричной системе счисления имеют вид

Этап 4. Итоговая операция шестнадцатеричного сложения

Таким образом,

Пример 2.3 Выполнить методом поэлементного замещения преобразование .

Этап 1. Представление заданного восьмеричного числа в виде

Этап 2. Замещение восьмеричных чисел их шестнадцатеричными эквивалентами

В правой части получен шестнадцати-восьмеричный полином.

Этап 3. Поэлементные преобразования в шестнадцатеричной системе счисления имеют вид

Этап 4. Итоговая операция шестнадцатеричного сложения

Таким образом,

Пример 2.4 Выполнить методом поэлементного замещения преобразование .

Этап 1. Представление заданного шестнадцатеричного числа в виде

полинома

Этап 2. Замещение шестнадцатеричных чисел их восьмеричными эквивалентами

В правой части получен восьми-шестнадцатеричный полином.

Этап 3. Поэлементные преобразования в шестнадцатеричной системе счисления имеют вид

Этап 4. Итоговая операция восьмеричного сложения

Таким образом,

Для дробных чисел возможны точные преобразования Сделанные утверждения подтверждаются следующими примерами.

Пример 2.5 Выполнить методом поэлементного замещения преобразование .

Этап 1. Представление заданного двоичного дробного числа в виде

полинома

Этап 2. Замещение двоичных чисел их десятичными эквивалентами

В правой части получен десятично-двоичный полином.

Этап 3. Поэлементные преобразования в десятичной системе счисления имеют вид

Этап 4. Итоговая операция десятичного сложения приводит к результату

Таким образом,

Пример 2.6 Выполнить методом поэлементного замещения преобразование .

Этап 1. Представление заданного восьмеричного числа в виде

Этап 2. Замещение восьмеричных чисел их шестнадцатеричными эквивалентами .

В правой части получен шестнадцати-восьмеричный полином.

Этап 3. Поэлементные преобразования в шестнадцатеричной системе счисления имеют вид .

Этап 4. Итоговая операция шестнадцатеричного сложения

Таким образом,

Существенным ограничением метода является то, метод не обеспечивает точный перевод для большинства чисел из десятичной системы в системы с основаниями 2,8,16.

Пример 2.7 Выполнить методом поэлементного замещения преобразование .

Этап 1. Представление заданного десятичного дробного числа в виде

Этап 2. Замещение десятичных компонентов их двоичными эквивалентами

В правой части получен двоично-десятичный полином.

Этап 3. Поэлементные арифметические операции в двоичной системе счисления приводят к следующему результату.

.

Таким образом, при делении двоичное частное представляет бесконечную дробь, состоящую из повторяющихся последовательностей цифр 1100.

К аналогичному результату приводит преобразование второго члена двоично-десятичного полинома

.

Этап 4. Итоговая операция двоичного сложения приводит к сумме

Правая часть полученного приближенного равенства стремиться снизу к точному значению . Абсолютная погрешность преобразования для этого случая - единица младшего разряда полученного двоичного числа. Погрешность уменьшается с увеличением разрядности преобразованного числа.

Существенно, что, полученная погрешность преобразования - это ограничения со стороны возможностей метода. Этот вывод следует из того, что число в двоичной системе имеет точное представление и равно

Несмотря на недостатки, метод поэлементного замещения является базовым как при «ручных «переводов малоразрядных чисел, так и при машинном конвертировании чисел (данных). Его эффективность усиливает при использованием для вычислений т.н. «схемы Горнера», рассматриваемой ниже.

2.4 Метод, основанный на «схеме Горнера»

В основе метода преобразования, использующего т.н. «cхему Горнера», лежит представление полиномов 1.1 и 1.2 в виде

Для целой части числа

Для дробной части числа



Вычисления по разложениям вида 2.1 и 2.1 выполняются следующим образом.

Задача состоит в преобразовании числа, заданного в исходной системе счисления с основанием , в другую (требуемую) СС с основанием

Процедура 2.3 Преобразование целых чисел (целой части смешанного числа).

1. Число заданное в исходной системе счисления с основанием , представляется в виде полинома (2.1) в системе с основанием . В полиноме сохраняются члены с нулевыми цифрами

2. Все цифры и числа, используемые для представления полиномиальных членов, заменяются их представлениями в системе .

3. Выполняются (по правилам требуемой системы счисления!) следующие операции над конвертированными полиномиальными членами:

3.1 старшая цифра числа умножается на основание требуемой системы счисления. К полученному произведению прибавляется следующая (с ближайшим меньшим весом) цифра.

3.2 полученная сумма умножается на основание требуемой системы счисления.

3.3 к полученному произведению прибавляется очередная цифра. Если прибавленная цифра - младшая цифра числа, то п. 4, если нет, то п. 3.2;

4. Полученная сумма - число в новой системе счисления.

Процедура 2.4 Преобразование дробных чисел (дробной части смешанного числа).

1. Пункты. 1,2 по Процедуре 2.3.

2. Младшая цифра числа делиться на основание требуемой системы счисления.

3. К полученному частному прибавляется следующая (с ближайшим большим весом) цифра.

4. Полученная сумма делиться на основание требуемой системы счисления.

5. Если последняя прибавленная цифра - старшая цифра дробной части, то п. 6, иначе п. 3

6. Конец

Рассматриваемый метод является частным случаем метода поэлементного замещения, рассмотренного ранее. Действительно, конвертация, как и в методе непосредственного замещения, обеспечивается за счет замещения полиномиальных членов их эквивалентами в требуемой системе счисления (этапы 1-2 Процедур 2.3, 2.4). Применение же схемы Горнера для вычислений на последующих этапах обеспечивает:

§ ускорение процедур конвертации.

§ позволяет устранить ограничения метода поэлементного замещения при переводе некоторых дробных чисел.

Пример 2.8 Выполнить по схеме Горнера конвертацию целых чисел .

Этап 1. Представление заданного восьмеричного числа по схеме Горнера в виде

Этап 2. Замещение восьмеричных чисел их десятичными эквивалентами

В правой части получен десятично-восьмеричный полином, представленный по схеме Горнера.

Этап 3. Поэлементные рекурсивные преобразования в десятичной системе счисления по выполняются как

Таким образом,

Для конвертации потребовалось 2 операции умножения и 2 операции сложения. Если сложность операции возведения в степень оценить как -умножений, то по прямой Процедуре 2.4 необходимо уже 3 умножения и два сложения. Очевидно, что эффективность применения схемы Горнера возрастает с увеличением разрядности конвертируемых чисел. Очевидно, также, что для целых чисел метод не теряет универсальности.

Пример 2.9 Выполнить, используя схему Горнера конвертацию дробных чисел .

Этапы 1,2 Заданное восьмеричное число по схеме Горнера представляется в виде

Выполнено также замещение десятичных элементов их двоичными эквивалентами.

Этапы 3. Вычисления в двоичной системе счисления приводят к результатам

Таким образом, Для конвертации потребовалось 2 операции умножения и 2 операции сложения.

Из примера 2.9 следует важный вывод о том, что схема Горнера обеспечила точное преобразование числа в двоичную систему счисления, что не обеспечивалось ранее методом поэлементного замещения.

Метод является базовым при преобразованиях двоично - десятичных чисел в двоичные. При «ручных» преобразованиях удаётся избежать операций возведения в отрицательную или положительную степень оснований систем счисления, заменив эти операции последовательным (рекурсивным) умножением.

2.5 Метод «цифра за цифрой»

Метод «цифра за цифрой» предусматривает последовательное получение цифр кода конвертированного числа.

При этом для целого числа, а равно для целой части смешанного числа конвертирование выполняется с использованием операции деления, а для дробного числа (дробной части смешанного числа) с использованием операции умножения. Конверсия для каждой части имеет свои особенности, поэтому соответствующие алгоритмы целесообразно рассмотреть отдельно.

2.5.1 Конверсия целого числа методом «цифра за цифрой»

Преобразуемое (исходное) число, заданное в исходной системе счисления с основанием , необходимо представить в СС с другим основанием

Базовым предположением, на котором строятся дальнейшие процедуры, является предположение о том, что исходное целое число в требуемой системе счисления представляется в виде 2.1

Задача конвертирования заключается в определении неизвестных пока полиномиальных коэффициентов (цифр) - Это выполняется путем деления исходного числа на основание требуемой системы счисления. Очевидно, что при конвертировании разрядность числа может измениться по сравнению с исходной.

Деление на , выполненное по правилам исходной системы счисления приводит к результату

Если обозначить полученное частное как , то результат деления можно записать как

Таким образом, младшая цифра искомого представления в новой системе счисления ? есть остаток от деления исходного числа на. Если продолжить деление частного на , то получается результат

Результатом второго деления является частное и остаток.

Остаток от второго деления есть вторая цифра исходного числа в системе счисления.

Таким образом, последовательное деление обеспечивает последовательное получение цифр исходного числа в новой системе счисления («цифра за цифрой»).

Поэтому алгоритм преобразования целого числа методом «цифра за цифрой» может быть сформулирован в следующем виде.

Процедура 2.5 Конвертация целых чисел методом «цифра за цифрой»

1. Число делится на по правилам деления системы с основанием до получения остатка.

2. Если частное от деления - больше делителя, то частное становится делимым и процесс деления на продолжается.

3. Как только очередное частное станет меньше , процесс деления на прекращается. Остаток, полученный при первом делении на , представляет цифру разряда результата с весом в требуемой системе счисления. Остаток от второго деления представляет цифру разряда результата с весом и т.д.

4. Последний остаток является старшей цифрой результата, имеющей вес.

Особенности метода иллюстрируются следующими примерами.

Пример 2.10. Выполнить, используя метод «цифра за цифрой», конвертацию целых десятичных чисел , соответственно, в двоичную, восьмеричную и шестнадцатеричную системы счисления.

Преобразования приводят к результатам: Обозначение 8 (mod10) означает, что деление выполняется по правилам десятичной системы счисления.

2.5.2 Конверсия дробного числа методом «цифра за цифрой»

Перевод правильных дробей из системы счисления с основанием в систему с основанием осуществляется так.

Как и при конвертировании целого числа, исходное число ? правильная дробь, заданная в СС с основанием .. Необходимо представить ее в СС с основанием . Основополагающим, является предположение о том, что в исходная правильная дробь в требуемой системе счисления представляется в виде полинома 2.3

Задача конвертирования заключается в определении неизвестных пока полиномиальных коэффициентов (цифр) Это выполняется путем умножения исходного числа на основание требуемой системы счисления. Очевидно, что при конвертировании разрядность числа может измениться по сравнению с разрядностью исходного числа.

Умножение разложения (2.3) на позволяет получить произведение вида

Пусть

В полученном произведении содержится в виде целой части старшая цифра числа и дробная часть . Дробным число является потому, что имеет вес . Если дробь опять умножить на основание требуемой системы счисления , то целая часть произведения дает следующую цифру числа в новой системе счисления и т.д. Тогда правило перевода правильных дробей в новую систему счисления методом «цифра за цифрой» («последовательное умножение») формулируется следующим образом.

Процедура 2.6. Конвертация дробных чисел методом «цифра за цифрой»

1. Дробь, соответствующая числу умножается на по правилам умножения в системе с основанием .

2. В полученном произведении отделяется целая часть, которая может быть равной нулю, а дробная часть снова умножается на с последующим отделением целой части.

3. Эти операции повторяют

· либо до получения нулевой дробной части произведения,

· либо до заполнения разрядной сетки, выделенной для представление числа

· либо до достижения заданной точности преобразования.

4. Старшая цифра результата перевода (то есть первая после запятой) совпадает с первой отделенной целой частью, вторая цифра результата - со второй отделенной целой частью и т.д.

Для чисел переводимых точно должен существовать конечный полином вида 2.3 в требуемой системе счисления. Таких чисел - не много, для них характерно формирование нулевой дробной части при переводе.

2.6 Методы, учитывающие специфические соотношения оснований систем счисления

Практический интерес представляют взаимные преобразования в двоичной, восьмеричной и шестнадцатеричной системах счислениях. Основания таких систем являются степенями двойки и в этом смысле системы оказываются взаимосвязаны. Это свойство используется при преобразованиях.

2.6.1 Двоично-шестнадцатеричные и шестнадцатерично-двоичные преобразования

Двоично-шестнадцатеричные преобразования целых чисел (целой части смешанного числа)

Цель преобразований: представить целое число, заданное в двоичной системе счисления, в шестнадцитеричной системе счисления. При этом учитывается, что основания требуемой и исходной систем счисления связаны соотношением

Преобразования основаны на представлении двоичного полинома (1.1) в виде

Очевидно, что исходное число разбивается на группы по четыре разряда (тетрады). Каждая тетрада - целое число с весами разрядов 8-4-2-1. Вес тетрады зависит от ее позиции в исходном двоичном числе и определяется как

Преобразования по (2.4) описываются процедурой

Процедура 2.6 Преобразование целого двоичного числа в шестнадцатеричную систему счисления

1. Целая часть числа разбивается на группы из четырех разрядов (тетрады) Разбиение начинается с младшего разряда («справа налево от запятой»).

2. Если в старшей тетраде менее, чем четыре цифры, то вместо отсутствующих цифр записывают нули, которые дополняют тетраду до полной.

3. Комбинация цифр в каждой тетраде рассматривается как целое число, которое заменяется соответствующей по количественному эквиваленту шестнадцатеричной цифрой.

4. Полученное число - целое число в шестнадцатеричной системе счисления.

2.6.2 Двоично-восьмеричные и восьмерично-двоичные преобразования

Двоично-восьмеричные преобразования

Цель преобразований: представить целое число, заданное в двоичной системе счисления, в шестнадцитеричной системе счисления. При этом учитывается, что, основания требуемой и исходной систем счисления связаны соотношением

Процедуры конвертирования основаны на представлении разложение 1.1 и 1.2 в следующем виде.

Для целых чисел.



Для дробных чисел

Анализ (2.6) позволяет предложить следующую процедуру.

Процедура 2.9 Преобразование целого двоичного числа в числа в восьмеричную систему счисления

1. Целая часть двоичного числа разбивается на группы из трех разрядов (триады) начиная с младшего разряда («справа налево от запятой»).

2. Если в старшей триаде менее, чем три цифры, то вместо отсутствующих цифр записывают нули, которые дополняют триаду до полной

3. Комбинация цифр в каждой триаде рассматривается как целое число, которое заменяется соответствующей восьмеричной цифрой.

4. Полученное число - целое число в восьмеричной системе счисления.

Из (2.7) вытекает следующая процедура

Процедура 2.10 Преобразование дробного двоичного числа в числа в восьмеричную систему счисления

1. дробная часть исходного числа разбивается на группы из трех разрядов (триады). Разбиение начинается со старшего разряда значащей части числа («слева направо от запятой»).

2. Если в младшей триаде менее, чем три цифры, то она дополняется справа нулями до полной триады

3. Комбинация цифр в каждой триаде рассматривается как целое число и заменяется соответствующей восьмеричной цифрой.

4. Полученное число - целое число в восьмеричной системе счисления.

При конвертировании можно воспользоваться данными Табл. 2.3

Таблица 2.5 - Соответствие «триада-цифра»

000	001	010	011	100	101	110	111
0	1	2	3	4	5	6	7

Библиографический список

1. Каган Б.Н. Электронные вычислительные машины и системы: Учеб. пособие для вузов. - М.: Энергия, 1973. - 528 с., ил.

2. Карцев М.А. Арифметика цифровых машин. М., «Наука», 1969. - 575 стр.

3. Григорьев В.В. Кодирование чисел в микропроцессорных системах: Метод. указания. - ПГУПС, 2006.

4. Григорьев В.В. Дополнительные коды при выполнении вычислительных операций: Метод. указания. - ПГУПС, 2008.

Размещено на Allbest.ru