Савельвев А.Я. Основы информатики

Подождите немного. Документ загружается.

Информатика в техническом университете

Серия основана в 2000 году

РЕДАКЦИОННАЯ! КОЛЛЕГИЯ:

д-р техгг. наук И. Б. Федоров — главный редактор

д-р техн. наук И. П. Нореиков — зам. главного редактора

д-р техн. наук Ю. М. Смирнов — зам. главного редактора

д-р техн. науки, Ф. Горнее

д-р техн. наук В. В. Девятков

канд. техн. наук И. П. Иванов

д-р техн. наук А. А. Марков

д-р техн. наук В. А. Матвеев

д-р техн. науки. В. Сюзев

д-р техн. наук Б. Г, Трусов

д-р техн. наук В. М. Черненький

д-р техн. наук В. А. Шахнов

А.Я.Савельев

Основы

информатики

Допущено Министерством образования

Российской Федерации

в качестве учебника для студентов

высших учебных заведений,

обучающихся по направлению подготовки

дипломированных специалистов

«Информатика и вычислительная техника»

Москва

Издательство МГТУ имени Н.Э.Баумана

2001

УДК 002 (075.8)

ББК73

Ci2

Рецензенты:

Кафедра «Автоматизарованные системы и вычислительная техника»

Московского государственного университета (зав. кафедрой академик МАИ Bill,

д-р техн. наук, проф. В- //. Карпов):

д-р техн. наук. проф. В. В. Семенов (МАИ)

Савельев А. Я. Основы информатики: Учеб. для вузов. — М.: Изд-во

МГТУ им. Н. Э. Баумана, 2001. — 328 с,ил. (Сер. Информатика в техниче-

ском университете).

ISBN 5-7038-1515-0

Излагаютcя основные понятия информатики, методы измерения

представлеиня информации, спo-

собы представления числовой информации

информаиионных системах, методы

алгоритмы выпол-

нения арифметических

логических операций

различных системах счисления. Уделяется вниманиe

методам контроля правильности функционирования цифровых автоматов как основному элементу

ин-

форманцинных систем, а также способам защиты информации

вычислительных

информационных

системах. Рассматриваются методы логического описания

проектирования на основе использования

aппapaтa теории булевых функций, теории автоматов и автоматных языков.

Содержание учебника cooтветcтвyeт курсу лекций, который автор читает

МГТУ им

Н. Э.

Бaумaна.

Для студетов высших технических учебных заведений.

ББК

©А. Я.Савельев. 2001

® Московский юсуларсгвеиный (схинческнй

университет им

II Э

Баумана, 2001

ISBN 5 703R 1515-0

Издательство МГТУ им

И Э

Г>я\мзня, 20()|

Оглавление

Предисловие 9

i. baiuBMC иинигия информатики i i

1.1. Общие сведения об информации 11

1.2. Структурная мера информации 13

1.3. Статистическая мера информации 15

1.4. Семантическая мера информации 17

1.5. Преобразование информации 19

1.6. Формы представления информации 24

1.7. Передача информации 26

Задание для самоконтроля 29

Автомат как основной элемент информационных систем 30

2.1.

ЭВМ как автомат 30

2.2.

Лбстрактные автоматы и понятие алгоритма 34

2.3.

Основные понятия алгебры логики 3S

2.4. Свойства элементарных функций алгебры логики 45

2.5.

Аналитическое представление функций алгебры логики 51

2.6.

Совершенные нормальные формы 5А

2.7.

Системы функций алгебры логики 55

Задание для самоконтроля 6J

Представление чнсловой информации в информационных сис-

iCMax 6:

3.1.

Выбор системы счисления для представления числовой инфор-

мации 6:

3.2.11еревод числовой информации из одной позиционной системы в

другую Ы

3.3.

Разновидности двоичных систем счисления 7.'

3.4. Системы счисления с отрицательным основанием 7'

3.5.

Формы представления числовой информации 79

3.6. Представление отрицательных чисел 83

3.7. Погрешности представления числовой информации .86

Задание для самоконтроля 88

Алгоритмы выполнения операций сложении и вычшания чисел на

двоичных сумматорах 9{)

4.1.

Формальные правила двоичной арифметики 90

4.2.

Сложение чисел, представленных в форме с фиксированной заня-

той, на двоичных сумматорах 93

4.3.

Переполнение разрядной сетки 98

4.4.

Особенности сложения чисел, представленных в форме с плаваю-

щей запятой 100

4.5.

Методы ускорения операции сложения 105

4.6.

Оценка точности выполнения арифметических операций 107

Задание для самоконтроля I

1 I

5. Выполнение операций умножения чисел на двоичных сум-

маторах I 12

5.1.

Методы умножения двоичных чисел 112

5.2. Умножение чисел, представленных в форме с фиксированно!! запя-

той, на двоичном сумматоре прямого кода 115

5.3.

Особенности умножения чисел, представленных в форме с пла-

вающей запятой 117

5.4. Умножение чисел, представленных в форме с фнксирова1нюй запя-

той, на двоичном сумматоре дополнительного кода 119

5.5.

Умножение чисел на двоичном сумматоре обратного кода 121

5.6. Метод сокращенного умножения 124

5.7. Ускорение операции умножения 125

5.8. Матричные методы умножения 133

5.9. Методы параллельного умножения с использованием игераитных

структур. 136

5.10. Систолический метод вычислений

Задание для самоконтроля 139

6. Выполнение операций деления чисел на двоичных сумматорах 140

6-1-

Методы деления двоичных чисел 140

6-2. Деление чисел, представленных в форме с фиксированной запятой,

на сумматорах обратного и дополнительного кода 143

Оглавление

6.3.

Особенности деления чисел, представленных в форме с плавающей

запятой 148

6.4. Ускореине операции деления 149

6.5.

Параллельные методы деления с использованием итеративных

cipyKiyp 152

6.6. Операция извлечения квадратного корня 15'/

Задание для самоконтроля 159

Выполнение операций над десятичными числами в цифровых авто-

магах.. 16(

7.1.11редставлепие десятичных чисел в Д-кодах 16(

7.2. Формальные правила поразрядного сложения в Д-кодах 16^

7.3.

Представление отрицательных чисел в Д-кодах 16(

7.4. BbiHOjnieHHe операций сложения и вычитания чисел в Д-кодах.. 16i

7.5.

Умножение чисел в Д-кодах П(

7.6. Деление чисел в Д-кодах \Т.

7.7. Извлечение квадратного корня в Д-кодах 17:

7.8.

Перевод чисел в Д-код 171

Задание для самоконтроля 17!

8. Кон

роль работы цифровою автомата 181

8.1.

Кодирование информации как средство обеспечения контроля ра-

боты автомата 18'

8.2. Основные понятия теории кодирования 18!

8.3.

Методы эффективного кодирования информации 18

8.4. Кодирование по методу четности-нечетности 18

8.5. Коды Хэминга 18

8.6. Контроль по модулю 19

8.7. Выбор модуля для контроля 19

8.8. Контроль логических операций 19

8.9. Контроль арифметических операций 20

8.10. Арифметические коды 20

Задание для самоконтроля 21

9. Способы защиты информации 21

9.1.

Особенности систем защиты информации 21

9.2. Крипзографические методы защиты информации 21

9.3.

Л[п1аратные средства защиты 22

9.4.

Ipoi раммные средства защиты 22

9.5.

Палежность средств защиты информации 22

Оглавлети

10.

Методы логическою проектпрованпя 228

10.1.

Числовое и геометрическое представление функций алгебры ло-

гики : 228

10.2.

Минимизация логических функций. Метод неопределенных ко-

эффициентов для базиса И—ИЛИ—НЕ 230

10.3.

Метод Квайна 232

10.4.

Метод Квайна—Мак-Класки 236

10.5.

Метод минимизирующих карт 239

10.6.

Минимизация логических функций в базисе

Ф, л

, 1

241

10.7.

Минимизация функций в базисах Шеффера и Пирса 245

10.8.

Реализация частотно-минимального метода 248

11.

Логическое опнсзние и анализ электронных схем 260

11.1.

Логические операторы электронных схем 260

11.2.

Электронные схемы с одним выходом 265

11.3.

Электронные схемы с несколькими выходами 268

11.4.

Не полностью определенные функции ашебры логики 271

11.5.

Синтез электронных схем с использованием свойств не полно-

стью определенных функций 274

1 1.6. Времеинйе булевы функции 276

11.7.

Последовательностный автомат 279

11.8.

Анализ гтоследовательностиых автоматов с помощью реккуренг-

ных булевых функций 283

11.9.

Разновидности триггерных схем 285

Задание для самоконтроля 290

12.

Методы описания и синтеза цифровых автоматов 292

12.1.

Основные понятия теории автоматов 292

12.2.

Начальные языки описания цифровых автоматов 297

12.3.

Автоматные языки для задания автоматных отображений 301

12.4.

Соединение автоматов 305

12.5.

Синтез управляющего автомата 310

12.6.

Логическое проектирование управляющего автомата 3 13

Задание для самоконтроля 326

Список литературы 327

ПРЕДИСЛОВИЕ

i 1редс!анлеипая вниманию чи1ателей книга «Введение в информати-

ку» — первая книга из многотомной серии «Информатика в техническом

уиивсрси|е1е».

Н учебных планах подготовки дипломированного специалиста по на-

правлению «Информатика и вычислительная техника» дисциплина

«Ин-

форматика» входит в состав фундаментального цикла дисциплин. Она соз-

дает теоретическую базу для изложения и понимания таких дисциплин, как

«Организация ЭВМ и систем», «Алгоритмические языки и программирова-

mie»,

« 1еория автоматов» и других специальных курсов.

Основная uejib книги — познакомить студента с понятиями информа-

1ИКП,

изложи

1ь

методы и средства представления информации в компьюте-

рах и ин(|)ормационных системах, методы реализации арифметических и

лот ических операций в цифровых автоматах, а также основы анализа и

син-

теза логических схем ЭВМ и информационных систем.

Следуег натгомнить читателю, что термин «информатика» впервые был

исЕюльзован французскими специалистами для определения комплекса за-

дач,

связан1н>1х с применением ЭВМ для обработки, хранения и преобразо-

вания разнообразного вида информации. Однако этот термин не является

общепризнанным, так как ряд стран, а именно — США, Канада и некото-

рые лагиноамерикаиские государства — придерживаются термина «ком-

пьютерные пауки». Вместе с тем, на Международном Конгрессе «Образо-

вание и информатика» (1996 год, Москва) отмечалось, что «информатика

сегодня — это одна нз важных и перспективных «точек роста» мировой

пауки,

вокруг которой формируется новый комплекс наук об информации».

1'лавнь[М

понятием курса «Информатика» является понятие цифрового

автомата как средства для представления и обработки любых видов инфор-

мации.

Автор здесь придерживается классического определения, введенно-

го академиком В. М. Глушковым: «Электронные цифровые машины с про-

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

распространенных в настоящее время преобразователей дискретной ин-

формации, называемых дискретными или цифровыми автоматами».

llf4'(UiCJiORue

В главах I, 3. 8 и 9 изложены способы представления н кодирования

информации, методы конгроля и защиты информации. Эюч матернш! осно-

ван на результатах работ К. Шеннона, В. А. Котельникова. Р. Хэминга и др.

Главы 4, 5, 6 и 7 содержат описание методов и алгоритмов выполнения

арифметических операций на двоичных и десятичных суммаюрах. Их ос-

новой послужили работы С. А. Лебедева, Р. К. Ричардса, В. А. Ме;и,инкова

и др. Материал изложен таким образом, чтобы достичь максимальной общ-

ности содержания при возможности практического использования pe3yjrb-

татов теории. При этом используется некая гипотетическая ЭВМ. обла-

дающая определенной структурой, описанной в примерах.

Главы 2, 10 и ! I посвящены логическим основам анализа и сингеза

цифровых автоматов. Этот материал книги базируется на трудах Д. Буля,

В.

И. Шестакова, Э. Мак-Класки и др.

В главах 2, 11 и 12 изложены некоторые положения теории цифровых

автоматов, которые найдут дальнейшее развитие в специальном курсе

«Теория цифровых автоматов». Основой материала этих глав являются

труды В, М. Глушкова, Дж. фон-Иеймана, Э. Tlocia, А. Тыориига, С. В. Яб-

лонского и др. Читатель, интересующийся более глубоко вопросами анали-

за и синтеза цифровых автоматов, найдет эти сведения в специальной

литературе.' iUifl лучшего усвоения материала глава 12 допо;и|ена

конкрешыми примерами синтеза двух управляющих автоматов.

В основу книги положен курс лекций но данной дисциплине, читаемый

автором в течение нескольких лет в Московском государственном техниче-

ском университете имени Н. Э. Баумана.

Автор