|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Формы представления чисел в ЭВМСтр 1 из 16Следующая ⇒
Тверь 2004
Курс «Теория автоматов» является одной из важнейших компонент федерального государственного образовательного стандарта по направлению «Информатика и вычислительная техника» и входит в естественнонаучный цикл дисциплин российской высшей школы. Курс служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для корректной постановки и решения проблем в области проектирования элементов вычислительных устройств на нижнем логическом уровне на примере арифметики ЦВМ. Освоение методов теории автоматов необходимо для дальнейшего изучения специальных дисциплин, связанных со схемотехническим проектированием устройств вычислительной техники. Методические указания предназначены для студентов специальности ЭВМ, изучающих курс " Теория автоматов". Методические указания рассмотрены на заседании кафедры № от и рекомендованы к изданию.
Автор АСЕЕВА Т.В
Введение. 4 Арифметика ЦВМ... 6 Формы представления чисел в ЭВМ... 6 Представление чисел со знаком в ЭВМ... 6 Переполнение разрядной сетки. 7 Модифицированные коды. 7 Алгоритмы перевода чисел из системы счисления с основанием p в систему счисления с основанием q. 8 Перевод правильной дроби из кода Д1 в двоичную систему счисления. 8 Перевод правильной дроби из двоичной системы счисления в код Д1. 10 Перевод целого числа из кода Д1 в двоичную систему счисления. 11 Перевод целого двоичного числа в код Д1. 12 Сложение двоичных чисел с плавающей запятой. 13 Умножение двоичных чисел в форме с плавающей запятой. 17 Умножение чисел с фиксированной запятой на ДСДК, схема 1. 17 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 1. 18 Умножение двоичных чисел с фиксированной запятой на ДСДК, схема 2. 19 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 2. 20 Умножение двоичных чисел с фиксированной запятой на ДСДК, схема 3. 21 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 3. 22 Умножение двоичных чисел с фиксированной запятой на ДСДК, схема 4. 23 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 4. 23 Деление двоичных чисел с плавающей запятой. 24 Деление двоичных чисел с фиксированной запятой с восстановлением остатка. 24 Пример деления двоичных чисел с фиксированной запятой на ДСДК со сдвигом текущего остатка с восстановлением остатка. 26 Деление двоичных чисел с фиксированной запятой без восстановления остатка. 27 Основные сведения о конечных цифровых автоматах. 31 Абстрактная теория цифровых автоматов. 31 Совмещенная модель автомата (С-автомат) 33 Функционирование цифрового автомата во времени. 33 Канонический метод структурного синтеза цифровых автоматов. 34 Элементы памяти в цифровых автоматах. 36 Проектирование автомата Мили. 36 Проектирование автомата Мура. 39 Принцип микропрограммного управления в цифровых автоматах. 40 Алгоритм отметки ГСА и построение автомата Мура. 42 Алгоритм отметки ГСА и построение автомата Мили. 43 Тривиальная реализация цифрового автомата. 44 Кодирование состояний. Гонки в автомате. 44 Замена входных переменных и кодирование состояний. 45 Кодирование микрокоманд. 48 Матричная реализация комбинационных схем и автоматов. 49 Матричная реализация комбинационных схем.. 49
. Введение Конечные автоматы и такие связанные с ними конструкции как линейные грамматики и регулярные выражения относятся к важнейшим понятиям информатики. Различные варианты конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств, различных систем и процессов, программ и алгоритмов. Теория автоматов является одним из старейших разделов теоретической информатики. В читаемом курсе рассматриваются цифровые автоматы как теоретическая основа проектирования аппаратных средств ЭВМ последовательного типа. В этом случае принято рассматривать цифровой автомат как совокупность операционного автомата (исполнительного устройства) и управляющего автомата (собственно конечного автомата), образующих операционное устройство. Устройство, исполняющее алгоритм процедурного типа, называется операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат со сложно структурированной памятью - состоянием: часть памяти используется для идентификации шага алгоритма, остальная память используется для запоминания промежуточных данных, вычисляемых в процессе последовательного (по шагам) выполнения алгоритма. Такая модель вычислителя особенно удобна для расчета продолжительности одного такта работы устройства. УА инициирует действия отдельных шагов алгоритма и участвует в их выполнении. ОА выполняет все вычисления на отдельных шагах алгоритма под управлением УА. Кроме того, к ОА удобно отнести все вычисления предикатов, оставив УА только анализ вычисленных значений предикатов. Конспект лекций включает разделы, относящиеся к арифметическим основам ЭВМ, основные концепции которых можно найти в учебниках[1], [2] Каноническое описание синхронного конечного автомата можно интерпретировать как одношаговый алгоритм процедурного типа. Исполнитель этого алгоритма состоит только из ОА. На каждом шаге этого алгоритма изменяется вся память устройства, поэтому управление памятью не требуется, нет необходимости идентифицировать шаги этого алгоритма. Проектирование ОУ включает следующие этапы:
В ОА выполняются микрооперации над данными, которые поступают из памяти и хранятся в регистрах. Множество регистров образуют сверхбыструю память. Обработка данных в ОУ происходит с минимальным числом обращений к внешней памяти, а именно, обращение к внешней памяти происходит дважды за время работы автомата: первое обращение – получение данных, второе обращение – передача в память результатов обработки. Автомат такого типа называется автоматом с жесткой логикой. В отличие от микропрограммных автоматов, которые выполняют те же функции с обращением к памяти на каждом такте. Так как обращение к внешней памяти требует больших затрат времени по сравнению с обращением к регистровой памяти, автоматы с жесткой логикой имеют повышенное быстродействие. Такие автоматы являются основой RISK – процессоров. Автомат с жесткой логикой работает в дискретном времени. Поэтому на вход УА поступает синхронизирующий сигнал, который определяет это дискретное время. В каждом такте автоматного времени УА активизирует набор микроопераций (образующих микрокоманду), которые выполняются в ОА. Промежуточные результаты обработки данных, а также значения предикатов, отображающих состояния отдельных элементов ОА, также хранятся в регистровой памяти ОА. Микрооперация - базисное (элементарное) действие, необходимое для получения (вычисления) значения одной или более переменных. Микрооперация присваивания: при любых условиях разрядность левой и правой частей равны. Неиспользуемые разряды в правой части микрооперации обозначаются " *". Микрооперации входят в состав микрооператоров. Микрооператор - набор взаимосвязанных микроопераций (или одна микрооперация), выполняемых одновременно и необходимых для получения одного или более значений. Микрокоманда - набор сигналов, поступающих из УА в ОА и интерпретируемый как управляющий, т.е. необходимый для выполнения всех микроопераций данного микрооператора. При проектировании вычислительного устройства основными являются ограничения на следующие параметры: время вычисления, объем аппаратуры, тип применяемых базовых функций. Алгоритм функционального типа обладает максимальным потенциальным параллелизмом, и его реализация в виде логической схемы обеспечивает максимальное быстродействие по сравнению с любыми другими вычислителями.
Блок схема ОУ приведена на рисунке 1. Здесь Х – множество осведомительных сигналов о состоянии контролируемых элементов ОА. У – множество микрокоманд, вырабатываемых в УА в соответствии с ГСА. G – команда, инициализирующая процесс выполнения задачи. СС – синхронизирующий сигнал. КР – сигнал окончания работы ОУ. Операционный автомат выполняет все операции над числами на основании последовательных алгоритмов. Арифметика ЦВМ Модифицированные коды. В модифицированных кодах вслед за знаковым разрядом вводится разряд переполнения, имеющий формат цифр используемой системы счисления. Т.е. в двоичной системе счисления разряд переполнения занимает один бит. В десятичной и шестнадцатеричной – четыре бита. В восьмеричной – три бита. При выполнении алгебраического сложения первый знаковый разряд, он обозначается Sg1, всегда сохраняет правильное значение знака результата. Разряд переполнения служит для контроля переполнения разрядной сетки. В двоичной системе счисления запись числа в модифицированном коде имеет вид: Sg1 Sg2.c1, c2, …, cn, где c1, c2, …, cn – числовые разряды, Sg1 Sg2 – два знаковых разряда, каждый из которых занимает один бит, точка между знаковой и числовой частью служит исключительно для удобства чтения чисел, так как в разрядной сетке регистра отсутствует какой-либо разделитель этих двух частей в записи числа. Положение запятой при такой записи обозначается только в пояснениях, которые содержатся в сопровождающей документации. Критерий переполнения d разрядной сетки формулируется следующим образом: d=0 Û Sg1=Sg2. Если Sg1 ¹ Sg2, и Sg1=0, говорят о положительном переполнении разрядной сетки. Если Sg1 ¹ Sg2, и Sg1=1, говорят об отрицательном переполнении разрядной сетки. В случае чисел с фиксированной запятой положительное переполнение разрядной сетки является фатальным и сопровождается выработкой требования прерывания. Отрицательное переполнение разрядной сетки не требует прерывания. В этом случае результату присваивается значение 0. При представлении чисел в форме с плавающей запятой данные представляются в нормализованном виде. Нарушение нормализации означает, что мантисса результата вычислений не удовлетворяет заданному диапазону значений. Как было отмечено выше, допустимые значения нормализованной мантиссы находятся в диапазоне p-1£ |m| < 1. Поэтому переполнение разрядной сетки мантиссы называется нарушением нормализации справа, критерием нарушения нормализации справа является d=1 (d=1Û Sg1 ¹ Sg2). Переполнение разрядной сетки требует выполнения определенных действий: если Sg1 ¹ Sg2, необходимо выполнить арифметический сдвиг мантиссы на один разряд вправо и прибавить единицу к значению порядка. Поскольку при сложении двух чисел может произойти переполнение разрядной сетки не более, чем на один разряд, процедура нормализации при этом занимает один такт автоматного времени. Если нарушена левая часть приведенного неравенства, говорят о нарушении нормализации слева. Критерием нарушения нормализации слева является величина l. l=1 Û Sg2=c1. Т.е. в случае равенства значений знакового разряда и старшего числового разряда при отсутствии переполнения разрядной сетки. Очевидно, l=1 означает, что значение мантиссы меньше, чем р-1. Для нормализации числа требуется выполнить сдвиг мантиссы на один разряд влево и вычесть 1 из значения порядка. Положительное переполнение разрядной сетки порядка сопровождается выработкой требования прерывания. При отрицательном переполнении разрядной сетки вырабатывается машинный нуль, т.е. порядок и мантисса обнуляются. Кодирование микрокоманд О кодировании микрокоманд имеет смысл говорить только для случая построения автомата Мили. В принципе выходные сигналы автомата Мили формируются из тех же конъюнкций, из которых строились функции возбуждения элементов памяти автомата. Так что можно использовать имеющиеся термы, полученные при тривиальной реализации, и сформировать из них микрокоманды. Так как некоторые микрооперации выполняются более чем в одной микрокоманде, для последующего формирования сигналов, инициирующих выполнение микроопераций, используются дизъюнкции микрокоманд. Например, для выходных сигналов в Табл.1 микрокоманды имеют следующий состав:
Закодируем каждую микрокоманду таким образом, чтобы выражения для микроопераций сводились к одному терму. Тогда выходные сигналы МПА будут сформированы слоем конъюнкторов, следующих за кодами микрокоманд.
Тверь 2004
Курс «Теория автоматов» является одной из важнейших компонент федерального государственного образовательного стандарта по направлению «Информатика и вычислительная техника» и входит в естественнонаучный цикл дисциплин российской высшей школы. Курс служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для корректной постановки и решения проблем в области проектирования элементов вычислительных устройств на нижнем логическом уровне на примере арифметики ЦВМ. Освоение методов теории автоматов необходимо для дальнейшего изучения специальных дисциплин, связанных со схемотехническим проектированием устройств вычислительной техники. Методические указания предназначены для студентов специальности ЭВМ, изучающих курс " Теория автоматов". Методические указания рассмотрены на заседании кафедры № от и рекомендованы к изданию.
Автор АСЕЕВА Т.В
Введение. 4 Арифметика ЦВМ... 6 Формы представления чисел в ЭВМ... 6 Представление чисел со знаком в ЭВМ... 6 Переполнение разрядной сетки. 7 Модифицированные коды. 7 Алгоритмы перевода чисел из системы счисления с основанием p в систему счисления с основанием q. 8 Перевод правильной дроби из кода Д1 в двоичную систему счисления. 8 Перевод правильной дроби из двоичной системы счисления в код Д1. 10 Перевод целого числа из кода Д1 в двоичную систему счисления. 11 Перевод целого двоичного числа в код Д1. 12 Сложение двоичных чисел с плавающей запятой. 13 Умножение двоичных чисел в форме с плавающей запятой. 17 Умножение чисел с фиксированной запятой на ДСДК, схема 1. 17 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 1. 18 Умножение двоичных чисел с фиксированной запятой на ДСДК, схема 2. 19 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 2. 20 Умножение двоичных чисел с фиксированной запятой на ДСДК, схема 3. 21 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 3. 22 Умножение двоичных чисел с фиксированной запятой на ДСДК, схема 4. 23 Умножение двоичных чисел с фиксированной запятой на ДСОК, схема 4. 23 Деление двоичных чисел с плавающей запятой. 24 Деление двоичных чисел с фиксированной запятой с восстановлением остатка. 24 Пример деления двоичных чисел с фиксированной запятой на ДСДК со сдвигом текущего остатка с восстановлением остатка. 26 Деление двоичных чисел с фиксированной запятой без восстановления остатка. 27 Основные сведения о конечных цифровых автоматах. 31 Абстрактная теория цифровых автоматов. 31 Совмещенная модель автомата (С-автомат) 33 Функционирование цифрового автомата во времени. 33 Канонический метод структурного синтеза цифровых автоматов. 34 Элементы памяти в цифровых автоматах. 36 Проектирование автомата Мили. 36 Проектирование автомата Мура. 39 Принцип микропрограммного управления в цифровых автоматах. 40 Алгоритм отметки ГСА и построение автомата Мура. 42 Алгоритм отметки ГСА и построение автомата Мили. 43 Тривиальная реализация цифрового автомата. 44 Кодирование состояний. Гонки в автомате. 44 Замена входных переменных и кодирование состояний. 45 Кодирование микрокоманд. 48 Матричная реализация комбинационных схем и автоматов. 49 Матричная реализация комбинационных схем.. 49
. Введение Конечные автоматы и такие связанные с ними конструкции как линейные грамматики и регулярные выражения относятся к важнейшим понятиям информатики. Различные варианты конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств, различных систем и процессов, программ и алгоритмов. Теория автоматов является одним из старейших разделов теоретической информатики. В читаемом курсе рассматриваются цифровые автоматы как теоретическая основа проектирования аппаратных средств ЭВМ последовательного типа. В этом случае принято рассматривать цифровой автомат как совокупность операционного автомата (исполнительного устройства) и управляющего автомата (собственно конечного автомата), образующих операционное устройство. Устройство, исполняющее алгоритм процедурного типа, называется операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат со сложно структурированной памятью - состоянием: часть памяти используется для идентификации шага алгоритма, остальная память используется для запоминания промежуточных данных, вычисляемых в процессе последовательного (по шагам) выполнения алгоритма. Такая модель вычислителя особенно удобна для расчета продолжительности одного такта работы устройства. УА инициирует действия отдельных шагов алгоритма и участвует в их выполнении. ОА выполняет все вычисления на отдельных шагах алгоритма под управлением УА. Кроме того, к ОА удобно отнести все вычисления предикатов, оставив УА только анализ вычисленных значений предикатов. Конспект лекций включает разделы, относящиеся к арифметическим основам ЭВМ, основные концепции которых можно найти в учебниках[1], [2] Каноническое описание синхронного конечного автомата можно интерпретировать как одношаговый алгоритм процедурного типа. Исполнитель этого алгоритма состоит только из ОА. На каждом шаге этого алгоритма изменяется вся память устройства, поэтому управление памятью не требуется, нет необходимости идентифицировать шаги этого алгоритма. Проектирование ОУ включает следующие этапы:
В ОА выполняются микрооперации над данными, которые поступают из памяти и хранятся в регистрах. Множество регистров образуют сверхбыструю память. Обработка данных в ОУ происходит с минимальным числом обращений к внешней памяти, а именно, обращение к внешней памяти происходит дважды за время работы автомата: первое обращение – получение данных, второе обращение – передача в память результатов обработки. Автомат такого типа называется автоматом с жесткой логикой. В отличие от микропрограммных автоматов, которые выполняют те же функции с обращением к памяти на каждом такте. Так как обращение к внешней памяти требует больших затрат времени по сравнению с обращением к регистровой памяти, автоматы с жесткой логикой имеют повышенное быстродействие. Такие автоматы являются основой RISK – процессоров. Автомат с жесткой логикой работает в дискретном времени. Поэтому на вход УА поступает синхронизирующий сигнал, который определяет это дискретное время. В каждом такте автоматного времени УА активизирует набор микроопераций (образующих микрокоманду), которые выполняются в ОА. Промежуточные результаты обработки данных, а также значения предикатов, отображающих состояния отдельных элементов ОА, также хранятся в регистровой памяти ОА. Микрооперация - базисное (элементарное) действие, необходимое для получения (вычисления) значения одной или более переменных. Микрооперация присваивания: при любых условиях разрядность левой и правой частей равны. Неиспользуемые разряды в правой части микрооперации обозначаются " *". Микрооперации входят в состав микрооператоров. Микрооператор - набор взаимосвязанных микроопераций (или одна микрооперация), выполняемых одновременно и необходимых для получения одного или более значений. Микрокоманда - набор сигналов, поступающих из УА в ОА и интерпретируемый как управляющий, т.е. необходимый для выполнения всех микроопераций данного микрооператора. При проектировании вычислительного устройства основными являются ограничения на следующие параметры: время вычисления, объем аппаратуры, тип применяемых базовых функций. Алгоритм функционального типа обладает максимальным потенциальным параллелизмом, и его реализация в виде логической схемы обеспечивает максимальное быстродействие по сравнению с любыми другими вычислителями.
Блок схема ОУ приведена на рисунке 1. Здесь Х – множество осведомительных сигналов о состоянии контролируемых элементов ОА. У – множество микрокоманд, вырабатываемых в УА в соответствии с ГСА. G – команда, инициализирующая процесс выполнения задачи. СС – синхронизирующий сигнал. КР – сигнал окончания работы ОУ. Операционный автомат выполняет все операции над числами на основании последовательных алгоритмов. Арифметика ЦВМ Формы представления чисел в ЭВМ Числа в ЭВМ представляют в формах с фиксированной и с плавающей запятой. Представление чисел в форме с фиксированной запятой Представление целых чисел: запятая фиксирована слева от младшего разряда. В случае правильных дробей запятая фиксирована справа от старшего разряда. В обоих случаях диапазон представимых чисел, определяемый как отношения максимального числа в заданной разрядной сетке к модулю минимального представимого в этой разрядной сетке числа, равен DФТ= 2n-1. Представление чисел в форме с плавающей запятой Эта форма представления называется также логарифмической. Число представляют в виде произведения мантиссы, которая удовлетворяет в случае нормализованного представления неравенству p-1£ |m| < 1, и pП, где П – двоичное число, формат которого определяет диапазон представимых чисел, p – основание системы счисления. В случае k-разрядной сетки порядка (k числовых разрядов) порядок принимает значения –(2k-1) £ П £ 2k-1. Поэтому диапазон представимых чисел в форме с плавающей запятой в случае нормализованного представления равен Последнее выражение показывает, что диапазон представимых чисел в этом случае определяется разрядностью порядка. Мантисса же определяет точность представления чисел. Вычисления в форме с плавающей запятой являются принципиально не точными. Ошибка вычислений связана, с одной стороны, с погрешностью исходного представления числа, обусловленная ограниченностью разрядной сетки мантиссы, и с другой стороны, с алгоритмическими особенностями выполнения операций с плавающей запятой. |
Последнее изменение этой страницы: 2019-03-29; Просмотров: 372; Нарушение авторского права страницы
