Телекоммуникации и Информатика и вычислительная техника Ульяновск 2007 2
 Скачать 1.77 Mb.
|
|
Непозиционная система счисления система, в которой символы, обозначающие то или иное количество, не меняют своего значения в зависимости от местоположения (позиции) в изображении числа. Запись числа А в непозиционной системе счисления D может быть представлена выражением A D = D 1 + D 2 + … D N = N 1 i i D , где A D — запись числа А в системе счисления D; D i — символы системы. Непозиционной системой счисления является самая простая система с одним символом (палочкой. Для изображения какого-либо числа в этой системе надо записать количество палочек, равное данному числу. Например, запись числа 12 в такой системе счисления будет иметь вид IIIIIIIIIIII. Эта система неэффективна, так как форма записи очень громоздка. К непозиционной системе счисления относится и римская, символы алфавита которой и обозначаемое ими количество представлены в табл. 1.1. Таблица 1.1 Римские цифры I V X L СМ Значение (обозначаемое количество) 1 5 10 50 100 500 Запись чисел в этой системе осуществляется последующим правилам 1) если цифра слева меньше, чем справа, толевая цифра вычитается из правой (IV: 1 < 5, следовательно, 5 – 1 = 4, XL: 10 < 50, следовательно, 50 – 10 = 40); 2) если цифра справа меньше или равна цифре слева, то эта цифры складываются. 10 Так, число 1964 в римской системе счисления имеет вид MCMLXIV (М – 1000, СМ – 900, LX – 60, IV – 4), здесь девятьсот получается посредством вычитания из тысячи числа сто, шестьдесят — посредством сложения пятидесяти и десяти, четыре — посредством вычитания из пяти единицы. В общем случае непозиционные системы счисления характеризуются сложными способами записи чисел и правилами выполнения арифметических операций. В настоящее время все наиболее распространенные системы счисления относятся к разряду позиционных. Позиционные системы счисления Систему счисления, в которой значение цифры определяется ее местоположением (позицией) в изображении числа, называют позиционной Упорядоченный набор символов (букв и цифра, а n }, используемый для представления любых чисел в заданной позиционной системе счисления, называют ее алфавитом, число символов (цифр) алфавита p = n + 1 — ее основанием, аса- му систему счисления называют р-ричной. Основаниепозиционной системы счисления — количество различных цифр, используемых для изображения чисел в данной системе счисления. Самой привычной для нас является десятичная система счисления. Ее алфавита основание рте. в этой системе для записи любых чисел используется только десять разных символов (цифр. Эти цифры введены для обозначения первых десяти последовательных чисел, а все последующие числа, начиная сит. д, обозначаются уже без использования новых цифр. Десятичная система счисления основана на том, что 10 единиц каждого разряда объединяются в одну единицу соседнего старшего разряда, поэтому каждый разряд имеет вес, равный степени 10. Следовательно, значение одной и той же цифры определяется ее местоположением в изображении числа, характеризуемым степенью числа 10. Например, в изображении числа 222,22 цифра 2 повторяется 5 раз, при этом первая слева цифра 2 означает количество сотен (ее вес равен 10 2 ); вторая — количество десятков (ее вес равен 10), третья — количество единиц (ее вес равен 10 0 ), четвертая — количество десятых долей единицы (ее вес равен 10 -1 ) и пятая цифра — количество сотых долей единицы (ее вес равен 10 -2 ), те. число 222,22 может быть разложено по степеням числа 10: 11 222,22 = 2 10 2 + 2 10 1 + 2 10 0 + 2 10 -1 + 2 Аналогично 725 = 7 10 2 + 2 10 1 + 5 10 0 ; 1304,5 = 1 10 3 + 3 10 2 + 0 10 1 + 4 10 0 + 5 10 -1 ; 50328,15 = 5 10 4 + 0 10 3 + 3 10 2 + 2 10 1 + 8 10 0 + 1 10 -1 + 5 Таким образом, любое число А можно представить в виде полинома путем разложения его по степеням числа 10: A 10 = а n 10 n + а n-1 10 n-1 + ... + а 10 1 + а 10 0 + a -1 10 -1 + ... + а +..., последовательность из коэффициентов которого представляет собой десятичную запись числа А A 10 = а n а n-1 ... а а , a –1 ... a –m … Запятая, отделяющая целую часть числа от дробной, служит для фиксации конкретных значений каждой позиции в этой последовательности цифр и является началом отсчета. 1.2. Двоичная, восьмеричная и шестнадцатеричная системы счисления Примеры изображения чисел в данных системах счисления представлены в табл. 1.2. В современной вычислительной технике, в устройствах автоматики и связи используется в основном двоичная система счисления, что обусловлено рядом преимуществ данной системы счисления перед другими системами. Так, для ее реализации нужны технические устройства лишь с двумя устойчивыми состояниями, например материал намагничен или размагничен (магнитные ленты, диски, отверстие есть или отсутствует (перфолента и перфокарта. Этот метод обеспечивает более надежное и помехоустойчивое представление информации, дает возможность применения аппарата булевой алгебры для выполнения логических преобразований информации. Кроме того, арифметические операции в двоичной системе счисления выполняются наиболее просто. 12 Таблица 1.2 Десятичная Двоичная Восьмеричная Шестнадцатеричная 0 00000 0 0 1 00001 1 1 2 00010 2 2 3 00011 3 3 4 00100 4 4 5 00101 5 5 6 00110 6 6 7 00111 7 7 8 01000 10 8 9 01001 11 9 10 01010 12 А 11 01011 13 ВСЕ 11 18 10010 22 12 19 10011 23 13 20 10100 24 14 Недостаток двоичной системы — быстрый рост числа разрядов, необходимых для записи больших чисел. Этот недостаток не имеет существенного значения для ЭВМ. Если же возникает необходимость кодировать информацию, вручную, например при составлении программы на машинном языке, то используют восьмеричную или шестнадцатеричную системы счисления. Числа в этих системах читаются почти также легко, как десятичные, требуют соответственно в 3 (восьмеричная) ив шестнадцатеричная) раза меньше разрядов, чем в двоичной системе (числа 8 и 16 — соответственно я и я степени числа 2), а перевод их в двоичную систему счисления и обратно осуществляется гораздо проще в сравнении с десятичной системой счисления. 13 Арифметические операции в двоичной системе счисления Правила выполнения арифметических действий над двоичными числами задаются таблицей сложения, вычитания и умножения (табл. 1.3). Таблица 1.3 Сложение Вычитание Умножение 0 + 0 = 0 0 – 0 = 0 0 0 = 0 0 + 1 = 1 1 – 0 = 1 0 1 = 0 1 + 0 = 1 1 – 1 = 0 1 0 = 0 1 + 1 = 10 10 – 1 = 1 1 1 = 1 Единица – перенос в старший разряд Правила арифметики во всех позиционных системах счисления аналогичны. В двоичной системе счисления арифметическое сложение происходит по правилу сложения по модулю два с учетом переноса единицы в старший разряд. Пример Выполнить операцию арифметического сложения в двоичной системе счисления чисел 13 и 7. 13 10 = 1101 2 7 10 = 0111 2 Решение 13 01101 7 00111 20 10 10100 При сложении двух единиц результат операции равен нулю и единица переносится в соседний разряд. 4 3 2 1 0 1 0 1 0 0 2 = 1 2 4 + 0 2 3 + 1 2 2 + 0 2 1 + 0 2 0 = 20 Пример Выполнить операцию арифметического вычитания в двоичной системе счисления чисел 12 и 7. 1 11 Решение 12 1 1 0 0 7 0 1 1 1 5 10 0 1 0 1 При вычитании из нулевого разряда в данном разряде образуются две единицы, а в соседних нулевых разрядах возникает единица. 3 2 1 0 0 1 0 1 2 = 0 2 3 + 1 2 2 + 0 2 1 + 1 2 0 = 5 10 + + – – 14 Таблицы сложения для восьмеричной и шестнадцатеричной систем счисления представлены на рис. 1.1 и 1.2. + 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 10 2 2 3 4 5 6 7 10 11 3 3 4 5 6 7 10 11 12 4 4 5 6 7 10 11 12 13 5 5 6 7 10 11 12 13 14 6 6 7 10 11 12 13 14 15 7 7 10 11 12 13 14 15 16 Рис. 1.1. Таблица сложения для восьмеричной систем счисления + 0 1 2 3 4 5 6 7 8 9 А ВСЕ А ВСЕ А ВСЕ А ВСЕ А ВСЕ А ВСЕ А ВСЕ А ВСЕ А ВСЕ А ВСЕ А ВСЕ А А ВСЕ ВВС Е F 10 11 12 13 14 15 16 17 18 19 С СЕ А 1B D D Е F 10 11 12 13 14 15 16 17 18 19 А ВСЕ Е F 10 11 12 13 14 15 16 17 18 19 А В С 1D F F 10 11 12 13 14 15 16 17 18 19 А В С 1D Рис. 1.2. Таблица сложения для шестнадцатеричной системы счисления При сложении цифры суммируются по разрядами если при этом возникает избыток, то он переносится влево. 15 1.3. Перевод числа из одной системы счисления в другую При переводе целого десятичного числа в систему с основанием q его необходимо последовательно делить надо тех пор, пока не останется остаток, меньший или равный q–1. Число в системе с основанием q записывается как последовательность остатков отделения, записанных в обратном порядке, начиная с последнего. Пример Перевести число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную в двоичную в восьмеричную в шестнадцатеричную Ответ 75 10 = 1 001 011 2 = 113 8 = Другой способ записи перевода числа из десятичной системы счисления в двоичную осуществляется следующим способом. Исходное число делят на 2, результат пишут под исходным числом, а справа от черты в строке с исходным числом ставят 0, если деление без остатка, и 1, если остаток есть. Деление повторяют до тех пор, пока делимое не станет меньше делителя. Считывание результата производится снизу вверх. Пример В десятичной системе число А = 37. Получить число А в двоичной системе счисления. 37 2 2 2 2 2 18 9 4 2 11 1 1 0 0 0 37 1 18 0 9 1 4 0 2 0 1 А = 37 А = 100101 16 Перевод восьмеричных и шестнадцатеричных чисел в двоичную систему осуществляется путем замены каждой цифры эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр) соответственно. Пример. 537,1 8 = 101 011 111, 001 2 ; А, F 16 = 1 1010 0011, 1111 2 . 5 3 7 1 1 А 3 F Чтобы перевести число из двоичной системы в восьмеричную или шестнадцатеричную, его нужно разбить влево и вправо от запятой на триады (для восьмеричной) или тетрады (для шестнадцатеричной) и каждую такую группу заменить соответствующей восьмеричной или шестнадцатеричной цифрой. Например 10101001,10111 2 = 10 101 001, 101 110 2 = 251, 56 8 ; 2 5 1 5 6 10101001,10111 2 = 1010 1001, 1011 1000 2 = А, В А 9 В 8 При переводе числа из двоичной (восьмеричной, шестнадцатеричной системы счисления в десятичную надо это число представить в виде суммы степеней основания его системы счисления. Приме. Разряды 3 2 1 0 -1 Число 1 0 1 1, 1 2 = 1 2 3 + 1 2 1 + 1 2 0 + 1 2 -1 = 11,5 Разряды 2 1 0 -1 Число 2 7 6, 5 8 = 2 8 2 + 7 8 1 + 6 8 0 + 5 8 -1 = 190,625 Разряды 2 1 0 Число 1 F 3 16 = 1 16 2 + 15 16 1 + 3 16 0 = 499 10 17 Контрольные вопросы 1. Что такое система счисления 2. Какие система счисления используются для представления информации в компьютерах 3. В чем отличие позиционной системы счисления от непозиционной? 4. Что называется основанием системы счисления 5. Назовите порядок перевода чисел из десятичной в двоичную, восьмеричную и шестнадцатеричную системы счисления. 18 2. ЛОГИЧЕСКИЕ ОСНОВЫ ЦИФРОВЫХ УСТРОЙСТВ 2.1. Основы алгебры логики Основой построения любого устройства, использующего цифровую информацию, являются элементы двух типов логические и запоминающие. Логические элементы выполняют простейшие логические операции над цифровой информацией, а запоминающие – ее хранят. Логическая операция состоит в преобразовании по определенным правилам входной информации в выходную. Сигналы на входах и выходах логических элементов обычно являются двоичными (бинарными, те. принимают лишь два значения, символически обозначаемые как 0 и 1. Поэтому их также называют двоичными переменными и обозначают буквами латинского алфавита (входные сигналы x l , x 2 , ..., x n , а результат операции, те. выходной сигналу. Переменная х может принимать два значения либо х = 1 (событие истинно, либо х = 0 (событие ложно. Эти переменные называются также булевыми по имени английского математика Дж. Булля, который в середине XIX века разработал основные положения алгебры логики. Различные логические переменные могут быть связаны функциональными зависимостями. Например, y = f(x 1 , x 2 ) указывает на функциональную зависимость логической переменной у от логических переменных хи х, называемых аргументами или входными переменными. 2.2. Основные законы алгебры логики В алгебре логики имеются четыре основных закона переместительный (свойство коммутативности сочетательный (свойство ассоциативности распределительный (свойство дистрибутивности инверсии (закон де Моргана. Переместительный и сочетательный законы имеют место в обычной алгебре. Распределительного закона и закона инверсии в обычной алгебре нет. Соотношения, отображающие основные законы алгебры логики, приведены в таблице 2.1. 19 Таблица 2.1 п/п Закон Логическое сложение Логическое умножение 1 Переместительный x 1 x 2 = x 2 x 1 x 1 x 2 = x 2 x 1 2 Сочетательный (x 1 x 2 ) x 3 = x 1 (x 2 x 3 ) (x 1 x 2 ) x 3 = x 1 (x 2 x 3 ) 3 Распределительный (x 1 x 2 ) x 3 = x 1 x 3 x 2 x 3 x 1 x 2 x 3 =(x 1 x 3 )(x 2 x 3 ) 4 Инверсии 2 1 2 х х х х 1 2 х х х х Используя основные законы алгебры логики, можно составить ряд правил, которые применяются при анализе сложных логических выражений, приведения их к более простому и удобному виду (таблица 2.2). Законами правилам булевой алгебры присуще свойство симметрии. Все правила (кроме последнего) представлены парой соотношений. В каждой паре одно соотношение вытекает из другого заменой логического сложения логическим умножением и наоборот. Кроме того, все значения «0» заменяются на «1» и наоборот. Это свойство симметрии отражает принцип двойственности булевой алгебры. Таблица 2.2 п/п Правило а б 1 Инверсии 1 0 0 1 2 Неизменности x 0 = x x 1 = x 3 Универсального и нулевого множества x 1 = 1 x 0 = 0 4 Повторения x x = x x x = x 5 Дополнительности x х = 1 x х = 0 6 Склеивания 1 2 1 х х х х х 1 2 1 2 1 х ) х х )( х х Двойного отрицаниях х Правило склеивания широко используется при минимизации логических функций с целью их упрощения. 20 2.3. Преобразование булевых выражений Рассмотренные законы и правила используются для тождественных преобразований булевых выражений, описывающих логические функции. Булевое выражение представляет собой формулу, состоящую из логических констант и логических переменных, соединенных знаками логических операций. Как ив обычной алгебре для задания порядка выполнения логических выражений используются скобки. Примером булевого выражения для трех переменных служит формулах х )( х х х х х ( 3 1 2 1 3 2 1 (2.1) Обычно считают, что операция логического умножения всегда предшествует операции логического сложения. Преобразуем выражение (2.1), применив законы и правила алгебры логики. х х ( х х х х х х х ) х х ( х х х х х х х х х х х х х х х х х х х х х х х х ) х х )( х х х х х ( 1 3 2 2 1 3 2 2 1 1 1 3 2 3 2 1 2 1 3 2 1 3 2 1 1 2 1 3 3 2 1 1 3 2 1 3 1 2 1 3 2 Полученное в результате тождественных преобразований выражение (2.2) значительно проще выражения (2.1). Процесс упрощения логического выражения, основанный на тождественных преобразованиях, называется минимизацией булевых выражений. Дизъюнктивные нормальные формы Для записи одной и той же функции алгебры логики можно использовать различные формы. Формы, которые представляют суммы элементарных произведений, называют дизъюнктивными нормальными формами (ДНФ). Под элементарным понимается такое произведение, в котором сомножителями являются только отдельные переменные или их отрицания. Например, формулах х х х содержит два элементарных произведения, каждое из которых состоит из двух сомножителей. Очевидно, одна и та же функция может быть представлена множеством различных ДНФ. Однако существуют такие виды ДНФ, (2.2) 21 в которых функция может быть записана единственным образом. Такие формы называют совершенными дизъюнктивными нормальными формами (СДНФ). СДНФ определяется как сумма элементарных произведений, в которых каждая переменная встречается ровно один раз либо с отрицанием, либо без него. Для преобразования функции (2.2) в СДНФ необходимо дополнить каждое элементарное произведение недостающими переменными так, чтобы тождественность преобразования не была нарушена f(x l, x 2 , x 3 ) = х х ( х х х х ) х х ( х х х х 3 2 1 3 2 1 1 2 1 3 После раскрытия скобок и приведения подобных членов, получим функцию, записанную в СДНФ: х х х х х х х х х ) х х х х х х х х х х х х ) x , x , f(x 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 l (2.3) Здесь каждая переменная (или ее отрицание) содержится по одному разув каждом элементарном произведении. Функция (2.3) обращается в логическую единицу при трех различных комбинациях значений входных переменных х = 1, х = 0, х = 1 – первая комбинациях, х = 0, х = 1 – вторая комбинациях, х = 0, х = 0 – третья комбинация. Для каждой комбинации соответствующее элементарное произведение равно единице, для всех остальных комбинаций входных переменных – нулю. Таблица истинности такой функции (таблица 2.3) содержит три строки, в которых функция равна 1. Таблицах 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 22 Каждой из этих строк соответствует по одной из рассмотренных выше комбинаций входных переменных, те. таблица истинности имеет столько строк, где функция обращается в 1, сколько элементарных произведений содержит ее СДНФ. Чтобы написать СДНФ по таблице истинности, необходимо для всех комбинаций входных переменных, обращающих функцию в 1, записать элементарные произведения, инвертируя переменные, принимающие на данной комбинации нулевые значения, а все полученные элементарные произведения соединить знаками логического сложения. Применив это правило, мы получим 3 2 1 3 2 1 3 2 1 3 2 l х х х х х х х х х ) x , x , f(x |