Алгоритмы переводов из одной системы в другую

Работа ЭВМ заключается, в основном, в исполнении команд - так называются «приказы» программиста процессору на языке Ассемблер (Assembler). Программист должен при составлении программы понимать, как размещаются в памяти двоичные коды (b-коды) операндов и результатов команд, как программа может интерпретировать коды операндов, как представить код числового результата операции для вывода его изображения на экран и т.д. При отладке программ есть возможность «заглянуть» в память и проверить информацию. Для всех этих и других целей необходимо вспомнить информационные и арифметические, а точнее - алгебраические основы построения ЭВМ и освоить несколько новых понятий.

 

2.1. Понятия системы счисления

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

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

Каждое целое число в любой СС по сути есть свернутая форма следующего выражения:

 

A_(q)=a_n*qⁿ+a_n-1*q^n-1+..+a₁*q¹+a₀*q⁰, (2.1)

 

где: a –коэффициент в данном полиноме - цифра (символ) из алфавита CC; q - основание СС; n - номер старшего разряда числа; qi –вес коэффициента i-го разряда числа. Например, трехразрядное десятичное число 505 в соответствии с формулой 2.1 может быть представлено выражением:

 

5*102+ 0*101+ 5*100=505

 

Для указания вида СС в конце числа ставиться латинская буква: для двоичной – b десятичной – обычно не ставится или ставится d, для шестнадцатеричной – h (далее в тексте b-коды, d-коды, h-коды соответственно).

Для работы с Ассемблером необходимо знание 3-х СС: десятичной, двоичной и шестнадцетиричной. Применение b-кода обусловлено тем, что устройства ЭВМ построены на логических схемах, работа которых описывается законами дискретной математики. Ясно, что алфавит для b-кодов состоит из двух символов: 0 и 1; основание b-кода q равно 2. Для более компактного представления (на бумаге или на экране) информации вместо b-кодов используется h-коды: каждые 4 цифры двоичного кода заменяются ОДНОЙ цифрой шестнадцетиричной СС. h-коды имеет основание, равное 16, и следующий набор цифр: {0, 1, 2,..,9, A, B, C, D, E, F}. Как правило, карта памяти (dump) отлаживаемой программы и содержимое регистров текущей команды в программах-отладчиках выводится на экран в h-кодах. Но арифметические и логические операции в АЛУ выполняются поразрядно (говорят, побитово), поэтому для выявления ошибок программисту надо уметь выполнять операции и интерпретировать их результаты в b-кодах, а ввод с клавиатуры и вывод числовой информации программы на экран для пользователя, конечно, делают в d-кодах.

 

Список рекомендуемой литературы

1. Архитектура и программирование реального режима микропроцессоров фирмы Intel: учебное пособие /Сост. Т.К.Щемелева; Перм. техн. ун-т. Пермь, 2002. 96 c. – Тема 1.

2. Максимов Н.В. Партыка Т.Л. и др. Архитектура ЭВМ и вычислительных систем. М.: ФОРУМ:ИНФРА-М, 2005,-512 с.§ 1.3.

 

Контрольные задания:

Сосчитать число символов в своей фамилии, имени, отчестве раздельно и использовать полученные три числа в качестве основных исходных данных (сокращенно – Ф, И, О).

Преобразовать в b-коды значения Ф, И, О.

Выписать из таблицы кодов ASCII Н – коды ASCII первых двух символов своей фамилии на русском и на английском языках.

Работа ЭВМ заключается, в основном, в исполнении команд - так называются «приказы» программиста процессору на языке Ассемблер (Assembler). Программист должен при составлении программы понимать, как размещаются в памяти двоичные коды (b-коды) операндов и результатов команд, как программа может интерпретировать коды операндов, как представить код числового результата операции для вывода его изображения на экран и т.д. При отладке программ есть возможность «заглянуть» в память и проверить информацию. Для всех этих и других целей необходимо вспомнить информационные и арифметические, а точнее - алгебраические основы построения ЭВМ и освоить несколько новых понятий.

 

2.1. Понятия системы счисления

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

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

Каждое целое число в любой СС по сути есть свернутая форма следующего выражения:

 

A_(q)=a_n*qⁿ+a_n-1*q^n-1+..+a₁*q¹+a₀*q⁰, (2.1)

 

где: a –коэффициент в данном полиноме - цифра (символ) из алфавита CC; q - основание СС; n - номер старшего разряда числа; qi –вес коэффициента i-го разряда числа. Например, трехразрядное десятичное число 505 в соответствии с формулой 2.1 может быть представлено выражением:

 

5*102+ 0*101+ 5*100=505

 

Для указания вида СС в конце числа ставиться латинская буква: для двоичной – b десятичной – обычно не ставится или ставится d, для шестнадцатеричной – h (далее в тексте b-коды, d-коды, h-коды соответственно).

Для работы с Ассемблером необходимо знание 3-х СС: десятичной, двоичной и шестнадцетиричной. Применение b-кода обусловлено тем, что устройства ЭВМ построены на логических схемах, работа которых описывается законами дискретной математики. Ясно, что алфавит для b-кодов состоит из двух символов: 0 и 1; основание b-кода q равно 2. Для более компактного представления (на бумаге или на экране) информации вместо b-кодов используется h-коды: каждые 4 цифры двоичного кода заменяются ОДНОЙ цифрой шестнадцетиричной СС. h-коды имеет основание, равное 16, и следующий набор цифр: {0, 1, 2,..,9, A, B, C, D, E, F}. Как правило, карта памяти (dump) отлаживаемой программы и содержимое регистров текущей команды в программах-отладчиках выводится на экран в h-кодах. Но арифметические и логические операции в АЛУ выполняются поразрядно (говорят, побитово), поэтому для выявления ошибок программисту надо уметь выполнять операции и интерпретировать их результаты в b-кодах, а ввод с клавиатуры и вывод числовой информации программы на экран для пользователя, конечно, делают в d-кодах.

 

Алгоритмы переводов из одной системы в другую

Для перевода чисел из одной СС в другую используются точные алгоритмы, основанные на применении формул, например 2.1, и арифметических операций умножения, деления, сложения, изучаемые в курсах ИНФОРМАТИКИ. Рассмотрим переводы из одной СС в другую на примере только ЦЕЛЫХ чисел.

 

2.2.1. Перевод из b - коды в d-коды:

Пусть дано число А в b – коде: А = 011001b. Переведем его в d-код.

Чтобы получить число в d-коде, достаточно представить заданное число в развернутой форме (по формуле 2.1) и выполнить все указанные действия:

 

(011001)₂ = 0*25+1*24+1*23+0*22+0*21*1*20 =

 

0*32+1*16+1*8+0*4+0*2+1*1 = (25)₁₀

2.2.2. Перевод из b - кода в h -код

Рассмотрим перевод числа на примере. Пусть дано число 011001b. Для перевода b-кода целого числа в h-коды нужно

- разбить его b-код на тетрады (группы по 4 разряда), начиная с младшего целого разряда в сторону старших разрядов;

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

- заменить 4-х разрядные коды каждой тетрады символами h-кода.

Например, число 011001b разбивается на одну полную и одну неполную тетерады: 01|1001b. Дополним нулями старшие разряды неполной тетрады и получим: 0001|1001b. Переведем 0001b и 1001b раздельно в h-коды. Получим 19 h =011001b.

2.2.3. Перевод из d-кода в любую другую СС.

Алгоритм перевода следующий.

1) Разделить десятичное число A на основание той СС, в которой нужно представить число. Запомнить частное Ч и остаток О числа А.

2) Если в результата шага 1 частное Ч неравно 0, то принять его за новое делимое и отметить остаток О, который будет очередной значащей цифрой числа, вернуться к шагу 1, на котором в качестве делимого (десятичного числа) участвует полученное на шаге 2 частное.

3) Если в результате шага 1 частное Ч =0, алгоритм прекращается. Выписать остатки в порядке, обратном их получению. Получится двоичный эквивалент исходного числа.

 

Для примера переведите число 47 в b-код путем деления на 2 по правилам d-кода, так, как учили в курсе информатики. Должны получить 47=101111b.

 

2.2.4. Перевод из d-кода в b-код.

 

Однако перевод небольших чисел из d-кода в b-код и обратно просто выполнять и устно, используя метод подбора цифр в разрядах выражения (2.1). Для этого надо помнить, что все цифры b-кода могут принимать одно из двух значений - 0 или 1, то есть надо помнить многочлен типа: …32+16+8+4+2+1, или еще короче, ряд чисел…32,16,8,4,2,1, как последовательность весов нулей или единиц в составе двоичного числа. Тогда перевод будет состоять в том, чтобы правильно определить, будет ли участвовать определенный вес из этого ряда в формирования b-кода или нет. Если будет, то данному весу соответствует цифра «1», если нет – цифра «0».

Для правильного перевода сначала надо подобрать наибольший вес «единицы» для переводимого числа. Так, например, для числа 55 вес 32 будет наибольшим, т.к. следующий вес в этом ряду, равный 64, уже превышает число 55. Т.е. при весе 32 цифра b-коды есть 2. Затем надо «заполнить» нулями и единицами места для остальных цифр в указанном выше полинома. Для числа 55 следующий вес 16 также будет нужен, т.е. цифра двоичного числа при этом весе нужна 1, т.к. 32+16=48, что меньше 55. Вес 8 не нужен (цифра двоичного числа равна 0), т.к. 48+8=56, что больше 55.Вес 4, 2, 1 также будут нужны. Таким образом, мы получили двоичное число 110111b, равное 55 в d-коды.

 

Используя тот же метод, переведем число 111000b в d-коды:

1) Мысленно или письменно расставим веса для всех разрядов двоичного числа.
веса: 32 16 8 4 2 1
разряды числа: 1 1 1 0 0 0

2) Сложим веса разрядов, которым в числе соответствует «1». Получим 32+16+8=56, т.е. 111000b=56.