Системы счисления - презентация

1 Системы Счисления Выполнил студент группы 04-РРТШамринКонстантин

2 Содержание 1. Представление о системах счисления. Однородные позиционные системы счисления. Многочленное представление числа. Веса разрядов 2. Преобразование целых чисел из одной системы счисления в другую 3. Перевод правильных дробей и одной системы счисления в другую 4. Сложение-вычитание целых беззнаковых чисел 5. Представление знакопеременных чисел и сложение-вычитание чисел со знаком 6. Двоичное умножение 1. Представление о системах счисления. Однородные позиционные системы счисления. Многочленное представление числа. Веса разрядов 2. Преобразование целых чисел из одной системы счисления в другую 3. Перевод правильных дробей и одной системы счисления в другую 4. Сложение-вычитание целых беззнаковых чисел 5. Представление знакопеременных чисел и сложение-вычитание чисел со знаком 6. Двоичное умножениеПредставление о системах счисления. Однородные позиционные системы счисления. Многочленное представление числа. Веса разрядовПреобразование целых чисел из одной системы счисления в другуюПеревод правильных дробей и одной системы счисления в другуюСложение-вычитание целых беззнаковых чиселПредставление знакопеременных чисел и сложение-вычитание чисел со знакомДвоичное умножениеПредставление о системах счисления. Однородные позиционные системы счисления. Многочленное представление числа. Веса разрядовПреобразование целых чисел из одной системы счисления в другуюПеревод правильных дробей и одной системы счисления в другуюСложение-вычитание целых беззнаковых чиселПредставление знакопеременных чисел и сложение-вычитание чисел со знакомДвоичное умножение 7. Двоичное деление целых чисел 8. Коды Хемминга 7. Двоичное деление целых чисел 8. Коды ХеммингаДвоичное деление целых чиселКоды ХеммингаДвоичное деление целых чиселКоды Хемминга

3 Представление о система счисления. Однородные позиционные системы счисления. Многочленное представление числа. Веса разрядов. Система счисления (далее СС) - совокупность приемов и правил для записи чисел цифровыми знаками. Система счисления (далее СС) - совокупность приемов и правил для записи чисел цифровыми знаками. Наиболее известна десятичная СС, в которой для записи чисел используются цифры 0,1,:,9. Способов записи чисел цифровыми знаками существует бесчисленное множество. Любая предназначенная для практического применения СС должна обеспечивать: Наиболее известна десятичная СС, в которой для записи чисел используются цифры 0,1,:,9. Способов записи чисел цифровыми знаками существует бесчисленное множество. Любая предназначенная для практического применения СС должна обеспечивать: возможность представления любого числа в рассматриваемом диапазоне величин; возможность представления любого числа в рассматриваемом диапазоне величин; единственность представления (каждой комбинации символов должна соответствовать одна и только одна величина); единственность представления (каждой комбинации символов должна соответствовать одна и только одна величина); простоту оперирования числами; простоту оперирования числами; Все системы представления чисел делятся на позиционные и непозиционные. Все системы представления чисел делятся на позиционные и непозиционные. Запись чисел может быть представлена в виде, k Запись чисел может быть представлена в виде, k А (Д) = Д 1 + Д 2 + …+ Д K = Д i А (Д) = Д 1 + Д 2 + …+ Д K = Д i i=1 i=1 где A (D) - запись числа A в СС D; D i - символ системы, образующие базу. Поэтому принципу построены непозиционные СС. где A (D) - запись числа A в СС D; D i - символ системы, образующие базу. Поэтому принципу построены непозиционные СС. Непозиционная СС - система, для которой значение символа не зависит от его положения в числе. Непозиционная СС - система, для которой значение символа не зависит от его положения в числе.

4 В общем же случае системы счисления: A (B) =a 1 B 1 +a 2 B a n B n. Если положить, что B i =q i *B i-1, а B 1 =1, то получим позиционную СС. Если при этом q i =q, то, очевидно, B i =q i, и система называется однородной позиционной. При этом натуральное число q называют базисом системы, а цифры a i принимают целые значения от 0 до q-1. Число A записывается так: a n a n-1...a 1. После последовательности цифр иногда указывают основание той СС, в которой число записано, например число 9 в двоичной форме записывается так: 1001 (2). При q=10 мы имеем дело с привычной нам десятичной СС. На практике также используют другие СС: В общем же случае системы счисления: A (B) =a 1 B 1 +a 2 B a n B n. Если положить, что B i =q i *B i-1, а B 1 =1, то получим позиционную СС. Если при этом q i =q, то, очевидно, B i =q i, и система называется однородной позиционной. При этом натуральное число q называют базисом системы, а цифры a i принимают целые значения от 0 до q-1. Число A записывается так: a n a n-1...a 1. После последовательности цифр иногда указывают основание той СС, в которой число записано, например число 9 в двоичной форме записывается так: 1001 (2). При q=10 мы имеем дело с привычной нам десятичной СС. На практике также используют другие СС: Каждая СС имеет свои правила арифметики (таблица умножения, сложения). Поэтому, производя какие-либо операции над числами, надо помнить о СС, в которой они представлены. Каждая СС имеет свои правила арифметики (таблица умножения, сложения). Поэтому, производя какие-либо операции над числами, надо помнить о СС, в которой они представлены. qНазваниеЦифры 2двоичная 0, 1 3троичная 0, 1, 2 8восьмеричная 0, …., 7 16 шестнадцатирична я 0,...,9,A,..., F

5 Если основание системы q превышает 10, то цифры, начиная с 10, при записи обозначают прописными буквами латинского: A,B,...,Z. При этом цифре 10 соответствует знак 'A', цифре 11 - знак 'B' и т.д. В таблице ниже приводятся десятичные числа от 0 до 15 и их эквивалент в различных СС: q=10q=2q=16q=10q=2q= А В С D E F

6 В однородной позиционной СС число можно представить через его цифры с помощью следующего многочлена относительно q: В однородной позиционной СС число можно представить через его цифры с помощью следующего многочлена относительно q: A=a 1 *q 0 +a 2 *q a n *q n (1) Выражение (1) формулирует правило для вычисления числа по его цифрам в Выражение (1) формулирует правило для вычисления числа по его цифрам в q-ичной СС. Для уменьшения количества вычислений пользуются т.н. схемой Горнера. Она получается поочередным выносом q за скобки: q-ичной СС. Для уменьшения количества вычислений пользуются т.н. схемой Горнера. Она получается поочередным выносом q за скобки: A=(...((a n *q+a n-1 )*q+a n-2 )*q+...)*q+a 1 A=(...((a n *q+a n-1 )*q+a n-2 )*q+...)*q+a 1 результат вычисления многочлена будет всегда получен в той системе счисления, в которой будут представлены цифры и основание и по правилам которой будут выполнены операции. результат вычисления многочлена будет всегда получен в той системе счисления, в которой будут представлены цифры и основание и по правилам которой будут выполнены операции.

7 Преобразование целых чисел из одной системы счисления в другую. Задача преобразования из СС с основанием q в CC с основанием r сводится к нахождению цифр b i - коэффициентов многочлена b 0 +qb 1 +q 2 b q n b n из уравнения b 0 +qb 1 +q 2 b q n b n = c 0 +rc 1 +r 2 c r n c k, где c 0, c 1, c 2, c k - цифры записи числа в исходной СС. Предположим, что мы можем производить арифметические действия в исходной СС. Представим число A, которое надо перевести, в виде схемы Горнера: A=b 0 +q(b 1 +q(b qb n )...). Видно, что при делении A на q в качестве результата получаем b 1 +q(b qb n )..., а в качестве остатка - младшую цифру b0 числа A в q-ичной СС. Разделив результат на основание q, получаем в остатке b1 - вторую цифру и так далее, пока в результате не получится ноль. См. примеры перевода из десятичной СС в двоичную, восьмеричную и шестнадцатеричную СС (далее). Задача преобразования из СС с основанием q в CC с основанием r сводится к нахождению цифр b i - коэффициентов многочлена b 0 +qb 1 +q 2 b q n b n из уравнения b 0 +qb 1 +q 2 b q n b n = c 0 +rc 1 +r 2 c r n c k, где c 0, c 1, c 2, c k - цифры записи числа в исходной СС. Предположим, что мы можем производить арифметические действия в исходной СС. Представим число A, которое надо перевести, в виде схемы Горнера: A=b 0 +q(b 1 +q(b qb n )...). Видно, что при делении A на q в качестве результата получаем b 1 +q(b qb n )..., а в качестве остатка - младшую цифру b0 числа A в q-ичной СС. Разделив результат на основание q, получаем в остатке b1 - вторую цифру и так далее, пока в результате не получится ноль. См. примеры перевода из десятичной СС в двоичную, восьмеричную и шестнадцатеричную СС (далее). Предположим теперь, что требуется перевести число A=c0+qc1+q2c2+...+qncn из q-ичной СС в СС с основанием q m. Преобразуем многочлен: A=(c 0 +qc 1 +q 2 c q m-1 c m-1 ) + q m (c m +qc 1+m +q 2 c 2+m +...+q m-1 c 2m-1 ) + q 2m (c 2m +qc 1+2m +q 2 c 2+2m +...+q m-1 c 3m-1 ) q pm (c pm +qc 1+pm +q 2 c 2+pm +...+q n-pm c n ), где p - наибольшее целое число, при котором pm

8 Примеры перевода из десятичной СС в двоичную, восьмеричную и шестнадцатеричную СС Двоичная СС (q=2). Переведем число в двоичное представление. Используя вышеизложенное правило, разделим число 23 на основание целевой СС - 2: 23/2 = 11 и 1 в остатке. Младшая цифра двоичного числа - 1. Делим 11 на 2, получаем 5 и 1 в остатке. Следующая цифра числа - тоже 1. Записываем ее слева от предыдущей цифры Далее получаем 2 и 1 в остатке, а само число Далее, 2/2 = 1 и 0 в остатке. Получилось число Последнюю единицу делим опять на 2, получаем в результате 0 (это значит, что процесс перевода закончен) и в остатке - 1. Получили число Таким образом, = Двоичная СС (q=2). Переведем число в двоичное представление. Используя вышеизложенное правило, разделим число 23 на основание целевой СС - 2: 23/2 = 11 и 1 в остатке. Младшая цифра двоичного числа - 1. Делим 11 на 2, получаем 5 и 1 в остатке. Следующая цифра числа - тоже 1. Записываем ее слева от предыдущей цифры Далее получаем 2 и 1 в остатке, а само число Далее, 2/2 = 1 и 0 в остатке. Получилось число Последнюю единицу делим опять на 2, получаем в результате 0 (это значит, что процесс перевода закончен) и в остатке - 1. Получили число Таким образом, = Восьмеричная СС (q=8). Переведем десятичное число 100 в восьмеричный вид: 100/8=12 и 4 в остатке 12/8=1 и 4 в остатке 1/8=0 и 1 в остатке Получили = Восьмеричная СС (q=8). Переведем десятичное число 100 в восьмеричный вид: 100/8=12 и 4 в остатке 12/8=1 и 4 в остатке 1/8=0 и 1 в остатке Получили = Шестнадцатеричная СС (q=16). Переведем десятичное число 1000 в шестнадцатеричную СС: 1000/16=62 и 8 в остатке 62/16=3 и 14 в остатке 3/16=0 и 3 в остатке Вспомним, что цифры, большие девяти, обозначаются буквами. Шестнадцатеричная СС (q=16). Переведем десятичное число 1000 в шестнадцатеричную СС: 1000/16=62 и 8 в остатке 62/16=3 и 14 в остатке 3/16=0 и 3 в остатке Вспомним, что цифры, большие девяти, обозначаются буквами. Цифре 14 соответствует буква E. Получили =3E8 16. Цифре 14 соответствует буква E. Получили =3E8 16.

9 Так, чтобы перевести число из двоичной записи в восьмеричную, нужно сгруппировать его цифры по три (2 3 =8). Из каждой триады получается одна восьмеричная цифра. Например, дано число = Младшая цифра восьмеричной записи будет равна 1+2*1+4*0=3. Средняя 1+1*2+1*4=7, и старшая 0+1*2=2. Получаем Так, чтобы перевести число из двоичной записи в восьмеричную, нужно сгруппировать его цифры по три (2 3 =8). Из каждой триады получается одна восьмеричная цифра. Например, дано число = Младшая цифра восьмеричной записи будет равна 1+2*1+4*0=3. Средняя 1+1*2+1*4=7, и старшая 0+1*2=2. Получаем Для перевода из СС с основанием q m в q-ичную СС каждая цифра переводится в q-ичную систему, затем эти цифры записываются по порядку, причем каждая цифра, кроме старшей, дополняется слева нулями до m разрядов. Например, переведем число 2F5 16 в двоичную СС. В данном случае m=4. Так как 2 16 =10 2, F 16 =1111 2, 5 16 =0101 2, то 2F5 16 = Для перевода из СС с основанием q m в q-ичную СС каждая цифра переводится в q-ичную систему, затем эти цифры записываются по порядку, причем каждая цифра, кроме старшей, дополняется слева нулями до m разрядов. Например, переведем число 2F5 16 в двоичную СС. В данном случае m=4. Так как 2 16 =10 2, F 16 =1111 2, 5 16 =0101 2, то 2F5 16 =

10 Перевод правильных дробей из одной системы счисления в другую Правильной дробью называется число, равное m/n, где m и n - натуральные числа, причем m

11 Пример перевода правильной дроби из десятичной в двоичную, восьмеричную и шестнадцатеричную СС Двоичная СС (q=2). Переведем число в двоичное представление с абсолютной точностью. Используем вышеизложенное правило: умножим число 0.23 на основание целевой СС - 2: 0.23*2 = Видим, что целая часть получившегося числа равна нулю. Значит и первая цифра двоичной дроби - 0. Записываем ее после запятой Умножаем 0.46 еще раз на 2, получаем Следующая цифра двоичной дроби - тоже 0. Записываем ее справа от предыдущей цифры Далее получаем 0.92*2=1.84, а само число Далее, обнуляем целую часть и снова умножаем: 0.84*2=1.68. Продолжаем этот процесс: Двоичная СС (q=2). Переведем число в двоичное представление с абсолютной точностью. Используем вышеизложенное правило: умножим число 0.23 на основание целевой СС - 2: 0.23*2 = Видим, что целая часть получившегося числа равна нулю. Значит и первая цифра двоичной дроби - 0. Записываем ее после запятой Умножаем 0.46 еще раз на 2, получаем Следующая цифра двоичной дроби - тоже 0. Записываем ее справа от предыдущей цифры Далее получаем 0.92*2=1.84, а само число Далее, обнуляем целую часть и снова умножаем: 0.84*2=1.68. Продолжаем этот процесс:

12 ЧислоДвоичная дробь ( )

13 В конце концов получим число 0.92, которое уже встречалось. Следующие вычисления с этого момента будут периодически повторяться. Повторяющаяся часть дроби (период) выделен скобками в таблице. Таким образом, =0.00( ) 2. Восьмеричная СС (q=8). Правила перевода дроби в восьмеричное представление аналогичны правилам перевода в двоичную СС. Только умножать надо на 8, а не на 2. Перевдем десятичное число 0.1 в восьмеричный вид с точность до трех цифр после запятой: 0.1*8=0.8 - цифра 0 в результате 0.8*8=6.4 - следующая цифра результата *8=3.2 - цифра 3 Получили » Шестнадцатиричная СС (q=16). Перевдем десятичное число 0.9 в шестадцатиричную СС с точностью до двух символов после запятой: 0.9*16= цифра 14 (E) в результате 0.4*16=6.4 - следующая цифра результата - 6 Получили » 0.E6 16.

14 Двоичное умножение Наиболее просто операция умножения производится при применении прямого кода. В машинах она реализуется в два этапа. Наиболее просто операция умножения производится при применении прямого кода. В машинах она реализуется в два этапа. 1-й этап - определяется знак произведения при помощи сложения знаковых цифр по модулю 2. 1-й этап - определяется знак произведения при помощи сложения знаковых цифр по модулю 2. 2-й этап - производится перемножение модулей сомножителей, затем в случае необходимости округление полученного модуля произведения, после чего к модулю результата приписывается его знак, определенный на первом этапе. 2-й этап - производится перемножение модулей сомножителей, затем в случае необходимости округление полученного модуля произведения, после чего к модулю результата приписывается его знак, определенный на первом этапе. В машинах может быть реализовано как умножение, начинающееся с младшей цифры (наиболее привычный способ), так и умножение, начинающееся со старшей цифры. При умножении вручную в первом случае частичные произведения сдвигаются влево, во втором - вправо. Оба способа покажем на примере. В машинах может быть реализовано как умножение, начинающееся с младшей цифры (наиболее привычный способ), так и умножение, начинающееся со старшей цифры. При умножении вручную в первом случае частичные произведения сдвигаются влево, во втором - вправо. Оба способа покажем на примере. Пример. Перемножить числа X 1пр. = 0,1010 и X 2пр. = 1, й этап - знак произведения 1+1 = 1. 2-й этап - перемножаем модули: Пример. Перемножить числа X 1пр. = 0,1010 и X 2пр. = 1, й этап - знак произведения 1+1 = 1. 2-й этап - перемножаем модули: 1-й способ 2-й способ

15 В машинах нельзя просуммировать сразу n частичных произведений, как это обычно делает человек. Любой сумматор, как правило, рассчитан на одновременное сложение только двух операндов. Поэтому частичные произведения складываются не сразу, а накапливаются в регистре. При этом полную сумму (произведение) можно получить двумя путями: В машинах нельзя просуммировать сразу n частичных произведений, как это обычно делает человек. Любой сумматор, как правило, рассчитан на одновременное сложение только двух операндов. Поэтому частичные произведения складываются не сразу, а накапливаются в регистре. При этом полную сумму (произведение) можно получить двумя путями: 1. сдвигом множимого влево при первом способе и вправо при втором; 2. сдвигом суммы частичных произведений на каждом шаге на один разряд вправо при первом способе и влево - при втором. Таким образом, в машинах могут быть реализованы 4 схемы умножения: Таким образом, в машинах могут быть реализованы 4 схемы умножения: 1-й вариант - умножение младшими разрядами вперед со сдвигом множимого влево (обычный школьный метод); 1-й вариант - умножение младшими разрядами вперед со сдвигом множимого влево (обычный школьный метод); 2-й вариант - умножение младшими разрядами вперед со сдвигом накапливаемой суммы частичных произведений вправо; 2-й вариант - умножение младшими разрядами вперед со сдвигом накапливаемой суммы частичных произведений вправо; 3-й вариант - умножение старшими разрядами вперед со сдвигом множимого вправо; 3-й вариант - умножение старшими разрядами вперед со сдвигом множимого вправо; 4-й вариант - умножение старшими разрядами вперед со сдвигом накапливаемой суммы частичных произведений влево. 4-й вариант - умножение старшими разрядами вперед со сдвигом накапливаемой суммы частичных произведений влево.