Лекции по дисциплине Информатика

Министерство образования и науки Российской Федерации

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. А.Н. ТУПОЛЕВА

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

 

 

Лекции по дисциплине

«Информатика»

 

Направление 230100 "Информатика и вычислительная техника"

Специальность 230101 – "Вычислительные машины, комплексы, системы и сети"

 

 

Учебно-методическое пособие

Казань 2007г.

Лекция 1.

Введение. История информатики. Измерение

И кодирование информации.

.

Интуитивно мы понимаем, что такое информация и, поэтому, при получении сообщения используем различные выражения, например:

“ это сообщение не дает мне никакой информации”,

что приводит к пониманию взаимоотношения между информацией и передаваемым сообщением.

В связи с этим и было введено первоначальное понятие: информация (от латинского informatio) - разъяснение, изложение, осведомленность. В дальнейшем, в связи развитием информатизации общества понятие существенно расширилось. Таким образом, широта применения информатики влечет за собой колоссально большую “емкость" понятия информации и, следовательно, большую степень неопределенности и избыточности.

В социальных, “ручных” системах основной носитель информации - документы и, соответственно, - знаки, символы, графики, рисунки, чертежи.

Функция, выдаваемая источником, x(t) может быть непрерывная, дискретная и смешанная (рис.1.1):

- непрерывные функции x(t) c непрерывным аргументом t, т.е. значение функции может иметь бесконечное число значений в интервале (x_min, x_max ) и бесконечное число значений в интервале (t_min , t_max );

- непрерывные функции x(t) с дискретным аргументом t , т.е. значения функции имеют существенные значения только в определенные выделенные моменты времени t_i , i = 1 ¸ n ;

- дискретные функции x_i(t), с непрерывным аргументом t, т.е. функция может принимать только конечное число значений, в заданном интервале, x₁ (t), x₂ (t),..., x_n (t), в то время как аргумент t - произвольное количество значений в заданном интервале;

- дискретные функции x_i(t), с дискретным аргументом t_i, т.е. и функция и аргумент принимают конечное число значений в заданных интервалах.

Отметим, что каковы бы не были источники информации, ИС могут обрабатывать, передавать и хранить только ограниченное количество значений функций и аргумента. Преобразование осуществляется следующим образом.

Съем информации по времени t осуществляется только в определенные моменты t_i,, i = 1 ¸ n, например, через равные промежутки Dt (в принципе интервалы могут быть любыми) (рис.1). Такое преобразование называют дискретизацией (рис.1.1а).

Аналогичные преобразования производят и по значениям функции. Для этого на интервале значений функции (x_min, x_max) выделяют несколько значений, уровней, например, через равные промежутки (случай, аналогичный предыдущему). Такое преобразование называют квантованием по уровню (рис.1.1б,в).

Каждой выделенной точке можно сопоставить символ, букву, число (как символ) и т. п., т.е. кодировать, представить в виде некоторых данных, для чего выбираются методы кодирования.

Кодирование- установление соответствия между элементом данных и совокупностью символов, называемой кодовой комбинацией (словом кода); отожествление данных с их кодовой комбинацией.

Несмотря на то, что исходная информация весьма разнообразна, после преобразования требуется представить ее так, чтобы можно было передавать, обрабатывать и хранить в виде данных с помощью универсальных средств (цифровых устройств).

Рис.1.1. Преобразование исходной информации

 

Информация преобразуется к двоичному представлению, при хранении – это биты, и каждый элемент данных формируется как знаки “1” и “0”. Преобразователи сопоставляют знакам электрические сигналы. На рис. 1.2а. “1”- соответствует высокий потенциал, “0” - низкий на рис.1.2б. - “1” - соответствует серия импульсов, 0” – их отсутствие (динамическая форма).

 

0 1 0 0 1

Рис.1.2. Представление сигналов в дискретном виде

 

Таким образом, здесь фактически выбран алфавит из знаков “1” и “0”.

 

 

Измерение информации

Бурное развитие средств и систем связи в 30-х годах нашего столетия привело к необходимости разработки методов оценки количества информации.… Одно из представлений направлений включает следующие системы показателей:… Прагматическое направление и показатели предназначено для систем передачи обработки и хранения информации, т.е. для…

Раздел 2

Логические основы информатики

Лекция 2. Основные понятия и определения

 

В ЭВМ обрабатывается числовая информация, представленная в двоичной системе счисления (0 и 1). Любую схему ЭВМ можно рассматривать как устройство, имеющее n входных сигналов и m выходных. Поступления на входы некоторой последовательности 0 и 1 вызывает появление на выходах вполне определенной последовательности 0 и 1.

В ЭВМ различают два больших класса схем: класс комбинационных (логических) схем и класс конечных автоматов. В комбинационных схемах значение выходных сигналов в момент времени t однозначно определяется входными сигналами в тот же момент времени. В конечных автоматах выходные сигналы определяются не только входными сигналами, но и состоянием схемы (конечные автоматы содержат элементы памяти).

Построение схем ЭВМ решается с помощью аппарата математической логики. При этом используется только самая простая ее часть – алгебра логики. Основным понятием в той части алгебры логики, на которой основывается ее применение к построению схем ЭВМ, является понятие переключательной функции.

Переключательной или булевой функцией называется функция f(x_1, ,x₂, … x_n), способная принимать как и ее аргументы x₁, … , x_n только два значения 0 или 1. Любая переключательная функция (ПФ) может быть задана таблицей ее значений в зависимости от значений ее аргументов. Такая таблица называется таблицей истинности.

Пример. Зададим ПФ трех аргументов f(x₁, x₂, x₃). Так как каждый из аргументов принимает лишь 2 значения, поэтому мы имеем 8 различных комбинаций 3 переменных. Эти комбинации называют набором. Наборы обычно пишут в так называемом естественном порядке, когда наборы принимают значения (000), (001), … Для получения следующего набора прибавляют 1 к правому разряду – применяется как бы сложение чисел. Наборам присваивается номер, равный двоичному числу, соответствующему данному набору. Сопоставляя каждому набору одно из двух значений ПФ, мы и получим таблицу истинности (например, представленную в табл.2.1).

 

 

Таблица 2.1

x1 x2 x3 f(x1,x2,x3)

Любая ПФ n аргументов определена на 2ⁿ наборах. Число различных ПФ n аргументов равно при n = 1, число различных ПФ равно 4, при n = 2 – 16, при n = 3 – 256, при n =4 – 65536, при n=5 – примерно 4,3´10⁹. Ясно, что прямое изучение ПФ с помощью таблиц истинности возможно для небольшого числа аргументов.

Возьмем какую либо комбинационную схему (КС) (рис.2.1).

 

Рис.2.1. Комбинационная схема

Если значения ПФ отождествить с выходным сигналом КС, а аргументов - с входными сигналами, то ПФ будет описывать процесс преобразования входных сигналов в выходные, т.е.

y₁ = f₁(x₁,x₂,…,x_n);

y₂ = f₂ (x₁,x₂,…,x_n);

.

y_m = f_m (x₁,x₂,…,x_n).

Любые сложные схемы ЭВМ строятся из простых схем, которые называют логическими элементами^Ì.

Логическим элементом называется электронная схема, реализующая элементарную ПФ, имеющая количество входов, равное числу аргументов ПФ и только один выход.

При составлении сложных схем используют два приема: последовательное соединение элементов и перестановку входов элементов. Последовательное соединение логических элементов показано на рис.2.2.

 

 

Рис.2.2. Последовательное соединение элементов

Последовательное соединение двух логических элементов позволяет получить функцию f₃ трех аргументов. Подстановка в функцию вместо ее аргументов других функций называется суперпозицией.

Перестановка входов элементов показана на рис.2.3.

В общем случае функция f₄(x₁,x₂,x₃) отличается от функции f₃(x₁,x₂,x₃). Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов.

 

 

Рис.2.3. Перестановка входов элементов

В алгебре логики доказывается, что из ПФ одного и двух аргументов с помощью операций суперпозиции и подстановки можно получить все ПФ от большого числа аргументов. Практически это означает, что из логических элементов с одним и двумя входами можно построить любую сколь угодно сложную комбинационную схему.

.

Переключательные функции одного и двух переменных

Таблица 2.2 x f0(x) f1(x) f2(x) f3(x) …   Функция f0 (x) равно нулю (константа нуля), f3(x) равна единице (константа единицы),…

Лекция 3. Преобразования логических выражений

Формулы для отрицания:   Формулы для дизъюнкции:

Логические элементы

Логический элемент НЕ (инвертор). Инвертор реализует ПФ НЕ. В схемах инвертор изображается следующим образом (рис.2.4).      

Аналитическая запись переключательной функции.

Построение схем на элементах заданного базиса

- в таблице истинности выбирают все наборы, на которых ПФ равна единице; - выписывают произведения аргументов, соответствующих этим наборам. При этом,… - все полученные произведения соединяются знаком дизъюнкции.

Раздел 3

Арифметические основы информатики

 

Лекция 4. Системы счисления

- возможность представления любого числа в рассматриваемом, заранее назначенном диапазоне величин; - единственность представления (любая комбинация символов соответствует одному… - простоту операций с числами.

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

 

Все арифметические операции в системе счисления с основанием р проводятся в соответствии с известными правилами выполнения арифметических действий в десятичной системе счисления, но при этом используются таблицы сложения и умножения, составленные для данной системы счисления.

Рассмотрим сложение.

 

 

Сложение производится поразрядно, начиная с младшего, используя соответствие таблицы сложения. Так, для двоичной, системы счисления имеем:

0+0 = 0

0+1 = 1

1+0 = 1

1+1 =10.

 

Примеры сложения чисел.

Пример 3.2. Пример 3.3.

101011, 1101 ₍₂₎ 245,0 ₍₈₎

10010, 1011 ₍₂₎ 734,7 ₍₈₎

111110, 1000 ₍₂₎ . 1201,7 ₍₈₎ .

 

Правило вычитания чисел в системе счисления основанием р представляется так:

a_k = a_i - a_j при a_i ³ a_j ,

a_k = p + a_i – a_j при a_i < a_j ,

т.е. при a_i < a_j занимается ”1“ старшего разряда, содержащая р единиц младшего разряда. Таблица вычитания для двоичной системы счисления:

0-0=0

1-0=1

1-1=0

10-1=1 .

Примеры вычитания чисел:

Пример 3.4. Пример 3.5.

1001,01 ₍₂₎ 1352,2 ₍₈₎

110,11 ₍₂₎ 743,5 ₍₈₎

0010,10 ₍₂₎ . 406,5 ₍₈₎ .

 

При умножении используется таблица умножения, которая может быть легко составлена из таблицы сложения. Так, скажем,

.

Таким же образом можно составить всю таблицу. Наиболее проста таблица для двоичной системы:

0´0=0

0´1=0

1´0=0

1´1=1.

Пример 3.6:

Как видим, процесс умножения сводится к операциям сдвига множимого и прибавления его к сумме частичных произведений.

Деление выполняется по правилам, аналогичным десятичной системе счисления, но с использованием соответствующих таблиц сложения и умножения. Рассмотрим деление целых чисел в двоичной системе счисления (при дробных числах освобождаются от дробей умножением на одно и то же число). При делении в делимом выделяют минимально возможную группу разрядов, образующих число, равное или большее, делителя. Если такая группа образуется, то в частном записывают 1, если нет – 0. Затем образуется новая группа разрядов путем вычитания из выделенной группы делителя и приписыванием к полученной разности следующей цифры делимого и т.д.

Пример 3.7. Разделить число 111111,01₍₂₎ на 101,1 ₍₂₎.

Умножим оба числа на 100 ₍₂₎ и будем делить два целых числа:

 

 

Перевод чисел из одной системы счисления в другую

Использование в ЭВМ двоичной системы счисления связано с преодолением дополнительных трудностей, вызванных необходимостью перевода вводимых в ЭВМ чисел в двоичную систему счисления и обратного перевода числовых данных при выводе информации из ЭВМ. Эти преобразования информации в ЭВМ осуществляются автоматически с использованием специально разработанных методов.

Пусть задано число А_(q) в q–ичной системе счисления. Требуется найти запись этого числа в р-ичной системе счисления, т.е. В_(р).

Метод непосредственного замещения

- заданное число А(q) представляется в виде (3.1): A(q)=an-1´qn-1+…+a0´q0+a –1´q-1+…+a-m´q-m ; - все цифры ai и основание q в правой части записываются (замещаются) в системе счисления с новым основанием p и…

Метод последовательного деления на основание

Пусть число A(q) требуется записать в р-ичной системе. Допустим, что такое представление получено и новое число В(р) имеет вид: A(q) = B(p) = bn-1 bn-2 … b1 b0 (p) = bn-1´pn-1 + bn-2´pn-2 + … +… Разделим число A(q) на р. Так как b0<p, то в результате деления получим целую часть:

Метод последовательного умножения на основание

Пусть правильную дробь A(q) требуется записать в системе счисления с основанием р. Предположим опять, что эта запись найдена A(q)=B(p)=0, b-1 b-2… b-m(p)=b-1´p-1+b-2´p-2+…+b-m ´p-m. Если умножить число А на основание новой системы счисления p, то целая часть произведения будет равна b-1, а дробная …

Перевод чисел из восьмеричной системы счисления

В двоичную и наоборот

Пусть задано число А в 8-ричной системе: A=an-1 an-2…a1 a0(8) =… Пусть число А записано в 2-ичной системе счисления:

Лекция 5. Способы представления в ЭВМ отрицательных чисел

В ЭВМ нашли широкое распространение три способа представления (кодирования) чисел в прямом, обратном и дополнительном кодах.

Как уже указывалось ранее, для запоминания одной двоичной цифры в ЭВМ используется элемент с двумя устойчивыми состояниями 0 и 1. Для хранения k-разрядного двоичного числа берут k таких элементов, совокупность которых называется регистром.

Пусть в ЭВМ для записи числа А отводится n разрядов под целую часть, m под дробную часть и один разряд под знак числа:

an

an-1

an-2

…

a1

a0

a-1

…

a-m

 

 

Прямой код

Числа в прямом коде представляются в форме: при А ³ 0 [A]пp = 0.an-1an-2 … a1a0,a-1 … a-m; ( 3.2 )

Обратный код

С = 2n-2-m. Двоичное число в обратном коде записывается в виде [A]обр = bn.bn-1 … b1b0,b-1 … b-m,

Сложение чисел в обратном коде

Рассмотрим возможные случаи при сложении чисел В и С : В+С=D. 1. B > C , C > 0. Так как положительные числа в прямом и обратном кодах… 2. Рассмотрим сложение чисел с разными знаками: В > 0, C < 0.

Дополнительный код

[A]доп = dn . dn-1 … d1 d0, d-1…d-m,   Правило. Положительные числа в прямом и дополнительном кодах имеют одинаковую форму записи. Для записи отрицательного…

Лекция 6. Переполнение разрядной сетки

В ЭВМ количество разрядов, используемых для представления чисел, ограничено. Поэтому при сложении двух чисел с одинаковыми знаками их сумма может… Пример 3.26. Сложить два числа А = + 1101,1 и В = + 1011,0 (n=4, m=1) в… + Решение. [A]обр = 0.1101,1

Формы представления в ЭВМ числовых данных

При естественной форме число записывается в естественном натуральном виде, например: 28759 – целое число, 0,01372 – правильная дробь, 25,0265 –… При нормальной форме запись одного и того же числа может быть различной в… 28759=2,8759 . 104=287590 . 10-1=0,28759 . 105 и т.д.

Раздел 4.

ЭВМ – средство обработки информации.

Лекция 7. Комбинационные схемы и конечные автоматы

Имеются два типа устройств обработки цифровой информации: на основе комбинационных схем и на основе конечных (цифровых) автоматов. В комбинационных схемах совокупность входных сигналов (входное слово)… Закон функционирования комбинационной схемы может быть задан несколькими способами. Можно определить таблицу…

Электронные цифровые элементы памяти – триггеры, используемые в ЭВМ в качестве ячеек быстрой (статической) памяти, последовательностных схем (регистры сдвига, счетчики) являются простейшими автоматами. Их выходные сигналы зависят не только от комбинаций входных сигналов , но и от значений самих выходных сигналов в предшествующий момент времени.

Триггером называют последовательностную схему с положительной обратной связью и двумя устойчивыми состояниями 0 и 1 (то есть триггер обладает свойством памяти). В общем случае триггер может иметь асинхронные входы предварительной установки, тактовый (синхронизирующий) и информационные входы. К основным типам триггеров относятся:

· триггер с раздельной установкой состояний (RS-триггер),

· триггер "защелка" (D - триггер),

· универсальный триггер (JK - триггер),

· триггер со счетным входом (T - триггер).

По способу записи информации триггеры подразделяются на асинхронные и синхронные или тактируемые, а по способу управления - на триггеры со статическим управлением (единичным или реже нулевым уровнем тактового сигнала) и триггеры с динамическим управлением (положительным - из 0 в 1, или отрицательным - из 1 в 0) фронтом тактового сигнала. В последнем случае говорят о триггерах с прямым или инверсным динамическим входом управления.

Основу триггера составляет кольцевая схема из двух инверторов (рис.4.10). Если левый инвертор на выходе имеет единичный сигнал, то он передается на вход правого инвертора. На выходе правого формируется нулевой сигнал, который передается (по цепи обратной связи) на вход левого инвертора. На выходе левого инвертора подтверждается единичный сигнал. Таким образом, это состояние является устойчивым состоянием, которое может сохраняться сколько угодно долго.

В силу симметрии схемы возможно второе устойчивое состояние, при котором на выходе левого инвертора сохраняется нулевой сигнал, а на правом – единичный. Следовательно, представленная схема является схемой элемента с двумя устойчивыми состояниями. Но это еще не триггер. Триггер должен содержать входы, сигналами на которых можно управлять состоянием триггера.

Асинхронный триггер RS-триггер

Асинхронный триггер с раздельной установкой состояний (RS-триггер) имеет два входа:

· S (set) – установить (в единичное состояние),

· R (reset) – сбросить (установить в исходное состояние).

В таблице 4.1 представлены переходы RS-триггера, а на рис.4.2 – схема и обозначение RS-триггера на функциональных схемах.

Таблица 4.1.
Переходы RS-триггера
t	t+1
R	S	Q(t)	Q(t+1)
			не определено
			не определено

 

Для RS-триггера существует комбинация входных сигналов (два единичных сигнала, поданных одновременно на входы R и S), которая переводит триггер в неопределенное (неустойчивое) состояние. Это запрещенная комбинация. При этих комбинациях входных сигналов триггер может случайным образом перейти в любое из двух состояний. Для правильного функционирования триггера появление запрещенной комбинации на его входах должно быть исключено.

 

Синхронный RS-триггер с дополнительным входом установки исходного состояния.

Асинхронные триггеры имеют недостаточную защищенность от помех на входных линиях. Для повышения помехозащищенности триггеров в их схему вводят синхронизацию (управление). Изменение состояния синхронного триггера допускается только во время подачи синхросигналов С.

Схема синхронного RS-триггера и его обозначение на функциональных схемах представлены на рис.4. 3.

 

Синхронный RS-триггер имеет два информационных входа R и S и вход синхронизации С. Кроме этого, триггер может иметь дополнительные несинхронизируемые входы R и S. В этом случае запись в триггер может производится с использованием синхронизируемых входов R и S при отсутствии активных сигналах на несинхронизируемых входах, или при использовании несинхронизируемых входов при C=0.

D-триггер

  Если С = 0, то состояние D-тригтера устойчиво и не зависит от сигнала на его информационном входе (режим хранения…

D-триггер с дополнительными RS входами

Если на вход подать активный сигнал 0, а на вход единицу, то D-триггер… Сигналы D и С не влияют на этот процесс. В силу этого, асинхронные входы и имеют наивысший приоритет.

Двухтактный D-триггер

На рис.4.6. представлена схема и обозначение двухтактного D-триггера на функциональных схемах. Двухтактный D-триггер содержит два однотактных триггера (на рисунке отмечены пунктирными линиями) и инвертор в цепи…

D-триггер с динамическим управлением

Двухтактные триггеры позволяют в значительной степени решать вопросы, связанные с особыми ситуациями при передаче и обработке информации с использованием триггерных схем. Но в некоторых ситуациях более эффективно использование схем с динамическим управлением.

В динамических схемах, в частности, в D-триггерах, запись входной информации, в зависимости от схемы, производится по одному из фронтов синхроимпульса (возрастающему или спадающему).

На схемах динамический вход управления обозначается или наклонной чертой (с наклоном соответствующим активному перепаду сигнала синхронизации) или стрелкой (рис. 4.7)

При постоянном значении синхроимпульса или противоположном перепаде триггер хранит предыдущую информацию. Промышленно выпускаемые триггеры дополняются асинхронными инверсными входами установки и сброса и .

Т-триггер

Это триггер со счетным входом. Он имеет вход Т (счетный вход), причем по каждому единичному входному сигналу триггер меняет свое состояние на обратное. Простейший Т-триггер можно получить на основе двухтактных триггеров: RS-триггера или D-триггера. Схема Т-триггера на основе двухтактного RS-триггера (не синхронного и синхронного) и обозначение Т-триггера на функциональных схемах представлены на рис. 4.7. На рис. 4.8. представлена схема Т-триггера на основе двухтактного D-триггера

 

Как и D-триггеры, Т-триггеры могут строиться со статическим управлением и с динамическим управлением.

Самым универсальными и сложными являются JK-триггеры. Они могут строиться как со статическим, так и с динамическим управлением.

Универсальный JK-триггер

JK-триггер имеет два информационных входа J и K, тактовый статический или динамический вход, чаще инверсный, и два асинхронных входа установки и сброса.

Обозначение JK-триггера с инверсным динамическим входом приведено на рис.4.9. Наклонная черта "смотрит слева - направо - сверху - вниз". JK-триггер функционирует аналогично RS-триггеру, но в отличие от последнего, не имеет запрещенных комбинаций сигналов на входах.

Вход J функционально подобен входу S, а вход K – входу R RS-триггера. Но одновременная подача активных сигналов на этих входах приводит к переходу триггера в состояние противоположное исходному, т.е. объединение J и K входов JK-триггера превращает JK-триггер в Т-триггер.

Лекция 8. Типовые устройства ЭВМ

Регистры

Параллельный регистр (рис. 4.10, 4.11) может быть построен на тактируемых (синхронных) D-триггерах. Число триггеров равно количеству разрядов…  

Счетчики

  Для правильной работы второго и последующих триггеров необходимо, чтобы на их входах формировался единичный сигнал в…

Одноразрядный двоичный сумматор

  При параллельном суммировании на входы каждого разряда сумматора поступают значения цифр а и b соответствующих…

Лекция 9. Типовые устройства ЭВМ

Дешифратор – это устройство, которое имеет n входов и 2 n выходов, причем каждой i-ой комбинации сигналов на входе соответствует сигнал на одном… Рассмотрим синтез дешифратора на 3 входа и 8. Таблица истинности дешифратора… Дешифратор на три входа содержит восемь конъюнкторов, каждый на три входа, и три инвертора. Таблица …

Мультиплексор

  Функционирование мультиплексора описывается следующей таблицей состояний:   . Состояния …

Демультиплексор

Демультиплексор – это устройство, имеющее один информационный вход D и несколько выходов, осуществляющее передачу сигнала с информационного входа на один из выходов в соответствиис управляющим (адресным) кодом, поступающим на управляющие входы. В простейшем случае, в качестве демультиплексора может использоваться дешифратор, у котороговместо сигнала OE подается информационный сигнал X. Например, если на входы подать код a1a0=10(₂)=2(₁₀), то сигнал X появится на выходе y2, а на остальных выходах yi=0. На рис. 4.21 представлено обозначение демультиплексора на функциональных схемах.