- •Московский государственный университет
- •Содержание
- •Введение
- •1.Средства вычислительной техники
- •1.1. История развития средств вычислительной техники
- •1.1.1.Предшественники электронных вычислительных машин
- •1.1.2.Математические идеи прошлого – в современных компьютерах
- •1.1.3.Поколения электронных вычислительных машин
- •1.2.Упрощенная структура компьютера и принцип его работы.
- •1.3. Программное обеспечение компьютера
- •1.4. История языков программирования
- •1.5. Основные характеристики компьютеров
- •1.6. Типы вычислительных систем
- •1.6.1. Упрощенная классификация вычислительных систем
- •1.6.2. Особенности некоторых типов эвм
- •1.6.2.1 МикроЭвм
- •1.6.2.2. Персональные компьютеры
- •1.6.2.3. Большие эвм и СуперЭвм
- •2. Представление информации в компьютере
- •2.1.Представление чисел в позиционной системе счисления
- •2.2. Способы перевода чисел из одной системы счисления в другую
- •2.2.1. Случай, когда система счисления является целой степенью числа 2
- •2.2.2. Общий случай перевода
- •2.3.Двоичная арифметика
- •2.4.Представление чисел в форме с фиксированной и плавающей точкой
- •2.5. Коды для представления чисел в компьютере
- •2.5.1.Прямой код
- •2.5.2.Обратный код
- •2.5.3.Дополнительный код
- •2.5.4.Смещенный код.
- •2.5.5. Пример кодирования чисел в форме с плавающей точкой
- •2.5.6. Сложение чисел в форме с плавающей точкой
- •2.6. Кодирование текстовой информации
- •2.7. Кодирование графической информации
- •2.8. Кодирование звуковой информации
- •2.9. Представление команд
- •3. Основы организации и обработки данных
- •3.1 Основные структуры данных
- •3.2 Основные понятия баз данных и систем управления базами данных
- •3.2.1. Общие сведения
- •3.2.2. Режимы и технологии работы с базами данных
- •4. Основные понятия компьютерной графики
- •5.Компьютерные сети
- •5.1.Основные понятия компьютерных сетей
- •Как уже отмечалось, система компьютерной связи согласно модели osi/iso рассматривается на семи уровнях.
- •5.2.Интернет и его основные службы Получение информации из Интернета
- •5.3. Создание Web-документов Основы языка html
- •5.3.1. Структура документа на языке html
- •5.3.2. Правила вложения элементов
- •5.3.3. Функциональные блочные элементы
- •6. Вопросы компьютерной безопасности
- •6.1. Понятие компьютерной безопасности
- •6.2. Компьютерные вирусы
- •6.2.1. Методы защиты от компьютерных вирусов
- •6.2.2. Средства антивирусной защиты
- •6.3. Защита от несанкционированного доступа (методы криптографии)
- •6.3.1. Понятие несимметричного шифрования информации
- •6.3.2. Принцип достаточности защиты
- •6.3.3. Понятие электронной подписи
- •6.3.4. Понятие электронных сертификатов
- •7. Математические основы синтеза схем
- •7.1. Основы булевой алгебры. Булевы функции
- •7.2. Основы автоматных преобразований
- •Литература.
- •Св. План 2007г., поз.
7.2. Основы автоматных преобразований
Цифровой (конечный) автомат – это образ элемента с конечной памятью, который реализуется через механизм «смены состояний», каждое из которых отражает некоторую предысторию поступления входных сигналов. В разных состояниях автомат может по-разному реагировать на одинаковые входные воздействия.
Под воздействием входного слова (последовательности символов, возникающей в моменты времени t = 0, 1, 2, ... i ... , которые называются тактами) автомат переходит из одного состояния в другое и выдает выходное слово. Слово на выходе автомата в такте определяется в общем случае входным словом, поступившим в этом такте на вход автомата, и внутренним состоянием автомата, которое явилось результатом воздействия на автомат входных слов в предыдущие такты. Таким образом восприняв сигнал Хt в ответ автомат формирует сигнал Yt с учетом предыстории.
При анализе автомата его заменяют автоматом с одним эквивалентным входом и одним эквивалентным выходом и считают, что эквивалентные входной сигнал Xt и выходной сигнал Yt принимают значения из соответствующих образом преобразованных алфавитов входных и выходных сигналов.
Рассмотрим примеры автоматов.
1.
Yt=1, если Xt=9, а непосредственно перед этим было Xt-1=2, Xt-2=1 и
Xt-3 = 1; в противном случае Yt = 0.
2.
Yt = 1, если Xt = 1 и до такта t число единичных значений Xi было нечетно; в противном случае Yt = 0.
Для автоматов существует формализованная система описания (автоматные преобразования).
Чтобы описать автомат нужно задать закон (функцию) переходов автомата из одного состояния в другое и функцию выходов (реакции на входные воздействия в каждом состоянии).
Опишем рассмотренный ранее автомат А2.
1) X=(0, 1) - входной алфавит.
2) Y=(0, 1) - выходной алфавит.
3) S=(S0, S1) - алфавит состояний. S0 - отражает факт прихода
ранее четного числа X=1. S1 - отражает факт прихода
ранее нечетного числа X=1.
4) S0 - начальное состояние автомата.
5)S(t)= Ф(X(t), S(t-1)) - функция переходов;
Y(t)= F(X(t), S(t-1)) - функция выходов.
Функция переходов и функция выходов однозначно определяют зависимость состояния автомата в такте t и зависимость выходного сигнала Y(t) от входного сигнала в такте t и состояния в такте (t-1).
Пример табличного описания автомата А2:
функции переходов. функции выходов.
Посмотрим, как по такому описанию можно проанализировать поведение автомата А2 в моменты времени t = 0, 1, 2, 3, 4. Пусть задано начальное состояние автомата S0 и значение входных сигналов в указанные моменты времени:
Найдем последовательность Y и S:
Y(t)=F(X(t), S(t-1));
S(t)=Ф(X(t), S(t-1)).
Алгоритм заполнения таблицы:
1. Зная S(t-1) и X(t), определяем Y(t) по функции выходов.
2. Зная S(t-1) и X(t), определяем S(t) по функции переходов.
3. Возвращаемся к пункту 1.
Получим следующую последовательность Y(t) и S(t).
Автомат может быть описан и в виде ориентированного графа. При этом состояния автомата представляются вершинами графа, входы и выходы автомата отмечаются соответственно как числители и знаменатели дробей, расположенных на дугах, направленно соединяющих вершины графа.
Ниже приведено графическое задание автомата А2.
Функциям вида:
Y(t)=F(X(t),S(t-1)),
S(t)=Ф(X(t),S(t-1)), t=1,2, ...
соответствует автомат, выходной сигнал которого зависит от состояния автомата и сигнала на его входе. Такой автомат называется автоматом МИЛИ.
Рассмотрим автомат МИЛИ как устройство, работающее в некоторой системе тактов (часов). Его поведение можно описать следующей блок-схемой:
Выход автомата МИЛИ в такте t зависит от воздействия в такте t:
Y(t)=F(X(t),S(t-1))
В устройствах ЭВМ также широко применяются и так называемые автоматы с задержанной реакцией. У таких автоматов выходной сигнал Y(t) в такте t зависит исключительно от состояния автомата S(t-1) в такте и не зависит от входного сигнала X(t). Наиболее изученные и употребляемые автоматы такого вида это - автоматы МУРА.
Функционирование автомата МУРА описывается выражениями:
S(t)=Ф(X(t), S(t-1)),
Y(t)=F(S(t-1)), t=1,2, ...
Пример графического описания некоторого автомата МУРА:
Выходы "Y" определяется только значением состояний S и соответственно задается не на дугах, а у вершин. Входы, как и в автомате Мили, задаются на дугах.
Функции переходов и выходов для автоматов МУРА также могут задаваться в форме таблиц.
Пусть задано графическое описание автомата Мура:
X =<0;1>
Y = <0;1>
Соответствующее табличное описание имеет вид:
Поведение описанного автомата Мура во времени отражает приведённая ниже таблица.