Арифметические и логические основы ПК
план-конспект по информатике и икт по теме

Тема №2. Арифметические и логические основы персонального компьютера

План

1. Количество информации как мера уменьшения неопределенности знания

2. Единицы измерения информации

3. Арифметические основы персонального компьютера

3.1. Системы счисления

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

3.3. Двоичная арифметика

4. Кодирование информации

4.1. Кодирование числовой информации

4.2. Кодирование текстовой информации

4.3. Кодирование графической информации

4.4. Кодирование звуковой информации

5. Логические основы персонального компьютера

5.1. Основные логические операции

5.2. Логические законы и правила преобразования

1. Количество информации как мера уменьшения неопределенности знания

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

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

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

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

Единица количества информации – бит, такое количество информации, которое уменьшает неопределенность знаний в два раза.

В описанном опыте с бросанием монеты полученное количество информации равно 1 биту.

Существует формула, которая связывает между собой количество возможных событий N  и количество информации I.

N=2I

Из математики известно, что решение такого уравнения имеет вид:

I = log2N

Пример: В барабане для розыгрыша лотереи находится 32 шара. Сколько информации содержит сообщение о первом выпавшем номере?

2I=32

I = 5

Пример: Вы подошли к светофору, когда горел желтый свет. После этого загорелся зеленый. Какое количество информации вы при этом получили?

N=2I

N=2 (может загореться как красный, так и зеленый цвет), отсюда I=1 бит.

Пример: Вы подошли к светофору, когда горел красный свет. После этого загорелся желтый. Какое количество информации вы при этом получили?

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

Существует множество ситуаций, когда возможные события имеют различные вероятности реализации. Формулу для вычисления количества информации для событий с различными вероятностями предложил К. Шеннон в 1948 г.

,

где I – количество информации;

N – количество возможных событий;

pi – вероятности отдельных событий.

2. Единицы измерения информации

Бит – минимальная единица измерения информации, может принимать значения 0 или 1.

Комбинация из восьми бит называется байтом.

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

Для измерения больших объемов информации используют производные единицы измерения:

1 Кб = 1024 байт

1Мб = 1024 Кб

1 Гб = 1024 Мб.

3. Арифметические основы персонального компьютера

3.1. Системы счисления

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

Различают два типа систем счисления:

- позиционные – значение каждой цифры определяется ее местом (позицией) в записи числа.

- непозиционные – значение цифры в числе не зависит от ее места в записи числа.

Количество цифр, используемых в системе счисления, называется основанием системы счисления. В десятичной с.с. используется 10 цифр от 0 до  9, двоичная с.с. имеет 2, т.к. использует две цифры 0 и 1.

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

534110 = 5*103+3*102+4*101+1*100

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

1. Перевод чисел из системы счисления с любым основанием в десятичную.

Для перевода числа из с.с. с любым основанием в десятичную нужно представить число в развернутом виде и вычислить сумму.

101001012=1*27+0*26+1*25+0*24+0+23+1*22+0*21+1*20=16510

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

101,1012=1*22+0*21+1*20+1*2-1+0*2-2+1*2-3=4+0+1+0,5+0,+0,125 =5,62510

2. Для перевода целого числа из десятичной в с.с. с любым основанием, необходимо это число делить на основание с.с, запоминая остатки. Когда частное станет меньше делителя (основание с.с.), деление прекращается, и это частное становится старшей цифрой искомого числа. Затем все остатки записываются в обратном порядке.

Пример: перевести число 25 в двоичную систему счисления.

25:2=12(ост. 1)

12:2=6(ост.0)

6:2=3(ост.0)

3:2=1(ост.1)

2510=110012

3. Чтобы перевести дробное число из десятичной с.с. в другую, нужно:

1. Умножить дробное число на основание новой с.с.

2. Отдельно выписать целую часть полученного числа.

3. Если дробная часть полученного числа не равна нулю, или не достигнута требуемая точность вычислений, то с дробной частью повторить операции 1 и 2.

4. Полученные целые части произведений составляют искомую дробь в той последовательности, в которой они были получены.

Пример: Перевести десятичную дробь 0,625 в двоичную систему.

0,625*2=1,25 (целая часть – 1, дробная часть – 0,25)

0,25*2=0,5 (целая часть – 0, дробная часть – 0,5)

0,5*2=1 (целая часть – 1, дробная часть – 0)

Составляем двоичную дробь из целых чисел сверху вниз, предварительно записав 0 в целую часть: 0,101.

Если в исходной десятичной дроби есть и целая, и дробная части, то отдельно надо перевести его в целую часть путем деления на основание системы счисления и дробную часть – путем умножения на основание новой системы счисления. Затем записать их через запятую.

25,62510=11001,1012

4. Перевод чисел из двоичной в восьмеричную и шестнадцатеричную с.с.

Для перевода используют таблицы соответствия.

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

Затем сопоставить эти группы по таблицам.

Соответствие двоичных и восьмеричных чисел

Соответствие двоичных и шестнадцатеричных чисел

Пример: Перевести двоичное число 1010111112 в восьмеричную и шестнадцатеричную системы:

1010111112 =         101         011 1112 = 5378 

                        5        3        7

1010111112 =         0001         0101 1112 = 15F16 

                        1        5        F

5. Перевод чисел из восьмеричной и шестнадцатеричной в двоичную с.с.

Перевод осуществляется по таблицам соответствия в обратную сторону. Полученное число записывается без пробелов и незначащих нулей.

2468 =         2        4        6 = 11001102 

                001        100        110

37D16 =         3        7        D=11011111012 

                0011        0111        1101

3.3. Двоичная арифметика

1. Сложение производится в соответствии со следующими правилами:

0+0=0

0+1=1

1+0=1

1+1=10 (0 и единица в старший разряд)

Пример:

2. Вычитание производится по следующим правилам:

1 способ.

0-0=0

10-0=1

1-0=1

1-1=0

Пример:

2. способ.

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

112-1112 =

Заменяем 111 на 000, прибавляем единицу, получаем 001.

Складываем 11+001=1100, старший разряд – это знак числа, получаем 100.

4. Кодирование информации

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

Код – система условных символов для представления информации.

Кодирование – операция преобразования символов или группы символов одного кода в символы или группы символов другого кода.

В вычислительной технике используют двоичное кодирование. Это объясняется легкостью реализации такого способа кодирования с технической точки зрения: 1 – есть сигнал, 0 – нет сигнала.

4.1. Кодирование числовой информации.

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

Число А в любой системе счисления в экспоненциальной форме записывается следующим образом:

A = mq n

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

q - основание системы счисления;

n - порядок числа

Например, 1,3*1016=13000000000000000=1.3Е16

1,3* 10-16=0.00000000000000013=1.3Е-16

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

1. Представление целых чисел

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

Пример: Определить диапазон хранимых чисел при 16-разрядной ячейке памяти.

216=65536

Если числа только положительные, то диапазон составляет от 0 до 65535.

Если хранятся и положительные и отрицательные числа, то диапазон равен от -3276 до 32767.

Чтобы поучить внутреннее представление целого положительного числа N, хранящегося в k-разрядном машинном слове, нужно:

1.        Перевести число N в двоичную систему счисления.

2.        Полученный результат дополнить слева незначащими нулями до
k разрядов.

Пример: Получить внутреннее представление целого числа 1607 в 2-х байтовой ячейке.

N=160710 =110 0100 01112

Дополним слева незначащими нулями:

N=0000 0110 0100 0111

Для записи внутреннего представления целого отрицательного числа (-N) нужно:

1.        Получив внутреннее представление целого положительного числа (N)

2. Получить обратный код этого числа заменой 0 на 1 и 1 на 0
3. К полученному результату добавить 1

Пример: Получить внутреннее представление целого положительного числа -1607

1.  N=0000 0110 0100 0111
2.  Обратный код: 1111 1001 1011 1000
3. Результат прибавления 1: 1111 1001 1011 1001

2. Представление чисел в экспоненциальной форме.

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

Таблица

Внутреннее представление вещественного числа

4.2. Кодирование текстовой информации

Для кодирования текстовой информации используют кодовые таблицы символов, где каждому символу (букве, цифре и т.д.) присвоен определенный код - десятичное число в диапазоне от 0 до 255. Традиционно для кодирования одного символа требуется 1 байт. Во всем мире в качестве стандарта принят американский стандарт - таблица ASCII (American Standard Code for Information Interchange). Эта таблица кодирует только первые 128 символов (т.е. символы с номерами от 0 до 127). Остальные 128 кодов используются для кодировки символов национального алфавита, псевдографики и научных символов.

Ограниченный набор из 256 символов сегодня уже не вполне удовлетворяет возросшие требования международного общения. В последнее время появился новый международный стандарт UNICODE, который отводит на каждый символ не один, а два байта, и поэтому с его помощью можно закодировать не 256, a N=216=65536 различных символов.

Пример: Каков информационный объем текста ПРОГРАММИРОВАНИЕ в 16-битной кодировке (UNICODE) и 8-битной кодировке?

Количество символов в данном тексте равно 16, таким образом, при кодировании в UNICODE объем информации будет равен 16*2=32 байта, а при 8-битной кодировке - 16 байт.

4.3. Кодирование графической информации.

В процессе кодирования изображения производится его пространственная дискретизация. Изображение разбивается на отдельные маленькие фрагменты (точки), причем каждой точке присваивается значение его цвета, т.е. код цвета.

Качество кодирования изображения зависит от размера точек и количества цветов.

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

Разрешающая способность экрана - размер сетки растра, представляемый в виде произведения М (число точек по горизонтали) на N (число точек по вертикали).

Число цветов, воспроизводимых на экране дисплея (N) и число бит, отводимых в видеопамяти под каждый пиксель (I), связаны формулой:

N=2I

В простейшем случае каждая точка экрана (черно-белое изображение без градаций серого) может иметь одно из двух состояний (черная или белая), соответственно для хранения ее состояния требуется 1 бит. (N=2I)

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

Глубина цвета (битовая глубина) - количество бит, необходимое для кодирования цвета точки.

Страница - раздел видеопамяти, вмещающий информацию об одном образе экрана. В видеопамяти одновременно могут размещаться несколько страниц.

Таблица

Глубина цвета и количество отображаемых цветов

Пример: На экране с разрешающей способностью 640X200 отображаются только черно-белые изображения. Какой объем памяти необходим для хранения изображения?

Битовая глубина черно-белого изображения равна 1 ,а видеопамять, как минимум, должна вмещать одну страницу, то объем видеопамяти равен

640х200х1=28000бит=16000 байт

Пример: Какой объем видеопамяти необходим для хранения четырех страниц изображения при условии, что разрешающая способность экрана равна 640x480, используемых цветов - 32.

N=2I=32=25, глубина цвета 5 бит

640*480*5*4 = 6144000 бит = 750 Кбайт

4.4. Кодирование звуковой информации

Физическая природа звука - колебания в определенном диапазоне частот, передаваемые звуковой волной с непрерывно меняющейся амплитудой и частотой. Чем больше амплитуда сигнала, тем он громче для человека, чем выше частота сигнала, тем выше тон. Чтобы компьютер мог обработать звук, непрерывный звуковой сигнал должен быть превращен в последовательность электрических импульсов (двоичных 0 и 1).

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

Оцифровку звука выполняет специальное устройство на звуковой карте, АЦП (аналого-цифровой преобразователь), обратный процесс - воспроизведение закодированного звука производится с помощью цифро-аналогового преобразователя (ЦАП).

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

Качество звука зависит от двух характеристик:

Глубина кодирования звука (I) - количество бит, используемое для кодирования различных уровней сигнала или состояний.

Современные звуковые карты обеспечивают 16-битную глубину кодирования звука, и общее количество различных уровней будет тогда: N=26=65536

Частота дискретизации (М) - количество измерений уровня звукового сигнала в единицу времени. Измеряется в герцах. Одно измерение за 1 секунду соответствует частоте в 1 Гц, 1000 измерений в секунду=1 кГц. М может принимать значение от 8 (радиотрансляция) до 48 кГц (аудио-CD).

Чтобы найти объем звуковой информации, нужно воспользоваться формулой:

V=M*I*t

где М - частота дискретизации

I - глубина кодирования

t - время звучания

Пример: Звук воспроизводится в течение 10 секунд при частоте дискретизации 22,05 кГц и глубине звука 8 бит. Определить размер звукового файла.

М = 22,05*1000 = 22050 Гц

1=8/8=1 байт

t= 10 секунд

V = 22050* 10* 1=220500 байт

2.5. Логические основы персонального компьютера

Отсутствие ошибок в рассуждениях возможно только тогда, когда строго соблюдаются законы логики. Логика - это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений.

Формальная логика содержит в себе некоторые основные понятия, такие как: высказывание, истинность высказывания и вывод.

Высказывание - грамматически правильное повествовательное предложение, о котором можно сказать, истинно оно или нет. Высказывания обозначают буквами латинского алфавита. Обычно считают, что высказывание может принимать два значения: ИСТИНА или ЛОЖЬ, их английские эквиваленты TRUE или FALSE, часто используют двоичные цифры 1 (ИСТИНА) или 0 (ЛОЖЬ).

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

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

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

5.1. Основные логические операции

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

1. Операция отрицания (инверсия).

Логическое отрицание меняет значение высказывания на противоположное. Обозначается «», «¬А», NOT, читается « не A».

Таблица

Таблица истинности для операции инверсии.

Схемные реализации логических операций называются логическими элементами или вентилями. Вентиль НЕ (инвертор) имеет один вход и один выход, единица на входе дает ноль на выходе и наоборот.

Рис. Схема логического вентиля НЕ.

2. Операция логического умножения (конъюнкция).

Высказывание, полученное в результате конъюнкции, истинно тогда и только тогда, когда истинны все исходные высказывания. Обозначается И, «х», «∧», «&», AND.

Таблица 2.6. Таблица истинности для операции конъюнкции.

На выходе логического элемента И получается единица, только если на оба входа поступили единицы.

Схема логического вентиля И.

3. Операция логического сложения (дизъюнкция).

Высказывание, полученное в результате дизъюнкции, истинно тогда и только тогда, когда истинно хотя бы одно из исходных высказываний. Обозначается ИЛИ, «+», « V », OR.

Таблица истинности для операции дизъюнкции.

На выходе логического элемента ИЛИ получается ноль, только тогда, когда на все его входы поданы сигналы логического ноля, во всех других случаях на выходе появляется логическая единица.

Схема логического вентиля ИЛИ.

Этот вентиль также называется «включающим ИЛИ», поскольку при наличии на обоих его входах значения ИСТИНА, на выходе тоже появляется значение ИСТИНА.

4. Операция импликации.

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

Такое сложное высказывание называют условным высказыванием. Часть импликации, идущая после слова «если», называется основанием, посылкой или антецедентом. Часть импликации, идущая после «то», называется следствием, заключением или консеквентом.

Импликация ложна тогда и только тогда, когда посылка истинна, а заключение ложно, в остальные случаях импликация истинна. Обозначается знаками «→», «⊃».

Таблица истинности для операции дизъюнкции.

5. Операция эквивалентности.

С помощью операции эквивалентности можно получить сложное высказывание из двух импликаций. Такое высказывание содержит слова «если и только если», «тогда и только тогда, когда». Эквивалентность истинна, если оба высказывания имеют одинаковые значения (оба истины или оба ложны).

Обозначается знаками «↔», «≡».

Таблица истинности для операции эквивалентности.

6. Операция исключающее ИЛИ.

Результат оказывается истинным только, если А или В (но не А и В) истинны. Иначе эта операция называется отрицанием эквивалентности. Обозначается XOR.

На выходе логического элемента исключающее ИЛИ получается логическая единица, только тогда, когда один из входных сигналов равен логической единице, а остальные - логическому нолю.

Таблица истинности для операции эквивалентности.

Схема логического вентиля исключающее ИЛИ.

7. Операция И -НЕ.

Результат этой операции является истиной только тогда, когда оба высказывания одновременно ложны. Обозначается ИЛИ - НЕ, NOR, «↓».

Таблица истинности для операции ИЛИ - НЕ.

На выходе логического элемента ИЛИ – НЕ получается логическая единица, только тогда, когда на все его входы поданы сигналы логического ноля, в любых других случаях на выходе получается логический ноль.

Схема логического вентиля ИЛИ - НЕ.

8. Операция И-НЕ.

Результатом этой операции будет значение ИСТИНА, только тогда, когда одно или оба высказывания принимают значение ЛОЖЬ. Обозначается ИЛИ - НЕ, «⏐», NAND.

На выходе логического элемента ИЛИ – НЕ получается логический ноль только тогда, когда на все его входы поданы сигналы логической единицы в любых других случаях на выходе получается логическая единица.

Результат этой операции является истиной только тогда, когда оба высказывания одновременно ложны. Обозначается ИЛИ - НЕ, NOR, « I».

Таблица 2.11. Таблица истинности для операции ИЛИ -НЕ.

Схема логического вентиля И – НЕ.

5.2. Логические законы и повила преобразования.

5.2.1. Законы алгебры логики

Закон тождества: любое высказывание тождественно само себе.

А≡А

Предмет обсуждения должен быть строго определён и не должен меняться до конца обсуждения. Примером нарушения этого закона может быть подмена понятий, когда, например программирование толкуется как единственное содержание информатики.

Закон непротиворечия: не могут быть одновременно истинны утверждение и его отрицание.

А∧=0

Примером противоречивого утверждения может служить утверждение «Идет дождь, и на улице сухо».

Закон исключенного третьего: высказывание может быть или истинным, или ложным, третьего не дано.

А∨=1

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

А =А

1. Правила преобразований.

Законы де Моргана.

2. Правша коммутативности.

От перемены мест слагаемых сумма не меняется.

От перемены мест сомножителей произведение не меняется.

Правила ассоциативности.

 (АУВ)УС=АУ(ВУС) (А&В)&С=А&(В&С)

3. Правша дистрибутивности. (А&В) V (А&С) =A&(BVC) (AvB)&(AV С) =А V (В&С)
4. Правша идемпотентности. AVA=A

А&А=А

6.        Теоремы поглощения.
АУА&В^В

Aw А 8с В = Aw В

А&(АУВ)=А

A8c(Aw В) = А&В

7.

AVl=l А&1=А AvO=A А&0=0

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

i [in пер:

\ простить следующую логическую формулу

/. )&(BvC)&(CwA) = A&Ј&Cv A&B&Aw А&С &Cv А&С & Aw i: Л H&CvB&B&A vB&C&CwB & С & Z = Л & С v 0 v 0 v 0 v 0 v 0 v 0 v I Л: В & C = A&B&CwA&B&C

Контрольные вопросы.

1. Что такое энтропия? Когда энтропия максимальна?
2. Что принято за единицу измерения информации?

>.        Как количество информации зависит от количества возможных событий?

4. Что такое система счисления?
5. Чем отличаются позиционные и непозиционные системы счисления?
6. Что такое основание системы счисления?
7. Как записать дополнительный код отрицательного числа?
8. Какие стандарты кодирования текстовой информации вы знаете?
9. Как определить глубину цвета, если известно количество отображаемых цветов?

10. Что такое частота дискретизации?
11. Что содержит таблица истинности?
12. Перечислите основные логические операции.

Какие существуют основные логические законы и правила преобразования?