Размещено на http://www.allbest.ru

ЛЕКЦИИ ПО КУРСУ «ИНФОРМАТИКА»

Лекция 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, например, через равные промежутки t (в принципе интервалы могут быть любыми) (рис.1). Такое преобразование называют дискретизацией (рис.1.1а).

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

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

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

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



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

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

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

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

Бурное развитие средств и систем связи в 30-х годах нашего столетия привело к необходимости разработки методов оценки количества информации. Основные теоретические положения были сформулированы в 40-х годах в работах К. Шеннона в связи с необходимостью развития системы передачи военной информации. В качестве единицы количества информации было принято то количество информации, которое содержится в некотором стандартном сообщении.

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

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

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

Для однозначного описания каждого уровня функции (или точки аргумента t_i рис.1.6) выделим некоторое количество символов - q, например, знаков выбранного алфавита (в русском q будет равно 33, в английском - 26 и т.п.) и некоторое количество позиций, длину слова, - n . Тогда общее возможное количество описываемых уровней функции будет определяться количеством общим числом комбинаций (числом произвольных слов, смысловая составляющая здесь не учитывается) и определится как N = qⁿ . При слове длины n = 2 и русском алфавите, число комбинаций N = 33² = 1089, т.е. можно обозначить такое количество уровней.

В ИС, для простоты реализации, в цифровых системах, практически всегда выбирают двоичный алфавит, состоящий только из символов “1” и “0” Количество комбинаций двоичного слова длины n будет N = 2ⁿ. Двоичное слово длины n называют байтом, в настоящее время принято считать n=8.

Объем информации может измеряться длиной необходимого слова в выбранном алфавите, так если имеется N - “количество информации”, число уровней, и выбран алфавит размерности q, то требуется найти n. Так как N = qⁿ, то n = log_q N , это для технической информатики не выгодно (средства реализации!), поэтому все (количество информации - I(q)) сводят к определению количества необходимых бит

I(q) = n log₂ q

Один бит соотносят одному элементу информации, тогда общее количество информации от множества k источников с алфавитами длиной q_i, равно

I(q_1, q₂, q_k) = I(q₁) + I(q₂) + I(q₃) + ….+ I(q_k)

Рассмотренный метод оценки количества называется аддитивной (суммарной) мерой информации (по Хартли), где q - глубина числа, количество символов принятых для представления информации, n - число позиций, необходимых и достаточных для представления чисел заданной величины.

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

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

I = - p_i log₂ p_i,

где i - номер знака (символа), i - 1 n, p_i - вероятность (возможность) появления знака (символа) в сообщении, p_i принимает значение 0p_i I. I - называют энтропией , очевидно, что она определяет возможность появления различных знаков в условиях “неопределенности”, случайного появления знаков. Подобная оценка называется статистической мерой информации и широко используется в технических системах.

В систему показателей количества и качества информации включаются следующие показатели:

- важность - значимость информации с точки зрения тех задач, для решения которых используется оцениваемая информация, полнота информации для решаемых задач;

- адекватность - соответствие текущему состоянию соответствующих объектов или процессов;

- релевантность информации, поступающей для обеспечения решаемых задач;

- толерантность поступающей информации

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

Под адекватностью информации понимается “…степень ее соответствия действительному состоянию тех реалий, которые отображает оцениваемая информация”. Определение адекватности осуществляется по двум параметрам: объективностью получения информации о предмете, процессе или явлении и продолжительностью интервала времени между моментом получения информации и текущим моментом, т. е. до момента оценивания ее адекватности.

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

Релевантность - характеристика соответствия содержания потребностям решаемой задачи. Количественно релевантность определяется коэффициентом К^p = N_p / N_o, где - N_p - количество релевантной информации, N_o - общее количество информации. Проблема заключается в сложности, а порою и невозможности, определения количества информации.

Толерантность - показатель удобства восприятия и использования информации для решаемых задач. Определение является неопределенным, субъективным и значение показателя представляется качественно.

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

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

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).

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

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

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

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

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

.

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

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

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

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

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

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

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



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

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

Рассмотрим некоторые ПФ одного и двух аргументов. В табл. 2.2 представлены все 4 функции одного аргумента.

Таблица 2.2

x	f0(x)	f1(x)	f2(x)	f3(x)
0	0	0	1	1
1	0	1	0	1

Функция f₀ (x) равно нулю (константа нуля), f₃(x) равна единице (константа единицы), функция f₁(x) повторяет значение аргумента, т.е. f₁(x)=x. Наиболее интересной и имеющей важное значение является функция f₂(x), которая принимает значения, обратные значению аргумента- логическое отрицание или функция НЕ и обозначается как:

Все ПФ двух аргументов приведены в табл.2.3.

Таблица 2.3

х1	х2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Функции f₀(x₁,x₂) и f₁₅(x₁,x₂) не зависят от значений аргументов: f₀(x₁,x₂)=0 и f₁₅(x₁,x₂)=1. Функции f₃(x₁,x₂), f₅(x_1, x₂), f₁₀(x₁,x₂) и f₁₂(x₁,x₂) являются фактически функциями одного аргумента:

f₃(x₁,x₂)=x₁, f₅(x₁,x₂)=x₂, f₁₀(x₁,x₂)=x₂ и f₁₂(x₁,x₂)=x₁.

Рассмотрим часто встречающиеся ПФ. Функция f₁(x₁,x₂) реализует операцию конъюнкции или логического произведения. Как видим из табл.2.3 , функция f₁(x₁,x₂) равна 1, когда и x₁ и x₂ равны 1. Конъюнкция обозначается как

f₁(x₁,x₂)=x₁ x₂ = x₁ x₂ = x₁ x₂ (читается x₁ и x₂).

Функция f₇(x₁,x₂) реализует операцию дизъюнкцию или логического сложения. Функция равна 1, когда или x₁ или x₂ равны 1. Дизъюнкция обозначается как

f₇(x₁,x₂)=x₁ x₂.

Функция f₁₄(x₁,x₂) реализует операцию отрицания конъюнкции. Из табл.2.3 видно, что когда конъюнкция f₁(x₁,x₁) равна 0, то функция f₁₄(x₁,x₂) равна 1, а если f₁(x_1, x₂) равна1, то f₁₄(x₁,x₂) равна 0, т.е. f₁₄(x₁,x₂)=f₁(x₁,x₂). Эта операция получила название “штрих Шеффера” и обозначается различными способами:

Функция f₈(x₁, x₂) реализует операцию отрицания дизъюнкции. По аналогии с функцией отрицания конъюнкции, из табл.2.3 видно, что f₈(x₁, x₂)=f₇(x₁, x₂). Эта операция также получила отдельное название - “стрелка Пирса” и обозначается следующим образом:

Функция f₆(x₁, x₂) реализует операцию логической неравнозначности или еще ее называют суммой по модулю два. ПФ равна 1, если аргументы x₁ и x₂ не равны между собой.

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

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

- дизъюнкция, конъюнкция и отрицание;

- отрицание конъюнкции;

- отрицание дизъюнкции и другие.

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

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

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

Формулы для отрицания:

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

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

Правило действия со скобками:

Операция поглощения:

Операция склеивания:

Формулы де Моргана:

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

Пример 2.2. Выражение

можно упростить следующим образом:

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

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

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

На вход инвертора подается цифровой сигнал, величина напряжения которого соответствует значению аргумента ПФ. Например, если x=1, то это напряжение составляет +5 В, а если х=0 , то 0 В (рис.2.5). На выходе инвертора получается сигнал, представляющий значение функции отрицания НЕ, т.е. значение, обратное входному (рис.2.6) : y=1 (на выходе +5 В, если на входе 0 В) или y=0 (на выходе 0 В, если на входе +5 В). Нужно сказать, что на временной диаграмме инвертора допущена некоторая условность: судя по диаграмме, переключение цифрового сигнала происходит мгновенно, в действительности же любой физический процесс в логических элементах протекает за определенное время.

Логический элемент И. Этот элемент реализует ПФ конъюнкции или логического произведения. Иногда логический элемент И называют конъюнктором, а также схемой совпадения, что отражает существо работы этого элемента: цифровой сигнал, соответствующий значению логической единицы, появляется на выходе схемы только тогда, когда совпадут по времени единичные значения цифровых сигналов на входе. На рис.2.7 представлено схематическое изображение элемента, а на рис.2.8 - его временная диаграмма.

Логический элемент ИЛИ. Этот элемент реализует ПФ дизъюнкции или логического сложения. Иногда логический элемент ИЛИ называют дизъюнктором или схемой сборки: сигнал, соответствующий уровню логической единицы, возникает на выходе, если хотя бы на один из входов придет сигнал логической единицы. На рис.2.9 приведено схематическое представление элемента, а на рис.2.10 - временная диаграмма.



Логические элементы И-НЕ и ИЛИ-НЕ. Последовательное соединение элементов И и НЕ реализует функцию отрицания конъюнкции (рис.2.11). Логический элемент, реализующий эту функцию, называется И-НЕ. Обозначение этого элемента приведено на рис.2.12.

Особенностью этих элементов является то, что они реализуют функционально полную систему ПФ, а следовательно, используя элементы И-НЕ или ИЛИ-НЕ, можно построить любую сколь угодно сложную схему.

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

Для аналитического представления ПФ используют правило ее записи по единицам:

- в таблице истинности выбирают все наборы, на которых ПФ равна единице;

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

- все полученные произведения соединяются знаком дизъюнкции.

Пример 2.3. Построить схему сумматора по модулю два на элементах И, ИЛИ, НЕ. Таблица истинности для ПФ f₆(x₁,x₂) логической неравнозначности представлена в табл.2.3.

В соответствии с правилом записи ПФ по единицам получим:

Тогда схема сумматора по модулю два будет иметь вид (рис.2.15):



Рис. 2.15. Схема сумматора по модулю два на элементах И, ИЛИ, НЕ

Можно построить схему сумматора только на элементах И-НЕ. Для этого, используя формулы де Моргана, преобразуем выражение f₆(x₁,x₂) следующим образом:

По этому выражению построим схему сумматора по модулю два на элементах И-НЕ (рис.2.16):

Сумматор по модулю два можно построить и на элементах ИЛИ-НЕ:

Схема представлена на рис.2.17.

Рис.2.17. Схема сумматора по модулю два на элементах ИЛИ-НЕ

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

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

- возможность представления любого числа в рассматриваемом, заранее назначенном диапазоне величин;

- единственность представления (любая комбинация символов соответствует одному и только одному числу);

- простоту операций с числами.

Все системы счисления разделяются на два больших класса - непозиционные и позиционные.

В непозиционной системе счисления значения символов не зависят от положения в числе. Для образования таких систем используют, в основном, операции сложения и вычитания. Например, система с одним символом-палочкой встречалась у многих народов. Для изображения числа в этой системе нужно записать определенное множество палочек, равное данному числу. Эта система не эффективна, т.к. запись числа получается длинной. Другим примером непозиционной системы счисления является римская система, использующая набор следующих символов: I, V, X, L, C, D и т.д. В этой системе имеются отклонения от правила независимости значения цифры от положения в числе. В числах IV и VI символ I принимает соответственно значения -1 и +1.

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

903,87=9?10²+0?10¹+3?10⁰+8?10^-1+7?10^-2.

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

Количество различных цифр, применяемых в позиционной системе счисления, называется ее основанием (для десятичной системы - от 0 до 9- десять ).

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

A_(p) = a_n-1 a_n-2 … a₁ a₀, a_-1 … a_-m

в р-ичной системе означает число



где a_i - цифры системы счисления, n и m - число целых и дробных разрядов числа.

Обычно в качестве двух младших цифр во всех системах счисления используются знаки 0 и 1. При этом основание системы счисления р записывается в виде последовательности цифр 10 (это не десять, а один ноль!). В скобках указывают систему счисления, в которой записывается число, т.е 10_(р).

В вычислительной технике широко используются двоичная, восьмеричная и шестнадцатеричная системы счисления. При этом для представления чисел в двоичной системе используются две цифры 0 и 1, в восьмеричной - 0, 1,…,7 и в шестнадцатеричной - цифры 0, 1,…,9 и знаки A, B, C, D, E, F (часто вместо этих знаков записывают символы

).

Пример 3.1. В качестве примера возьмем двоичное число 1001,1101₍₂₎. В соответствии с равенством (3.1 ) двоичное число можно определить следующим образом:

1001,1101₍₂₎=1?2³+0?2²+0?2¹+1?2⁰+1?2^-1+1?2^-2 + 0?2^-3 + 1?2^-4.

Если по правилам десятичной арифметики выполнить действия в правой части приведенного равенства, то можно получить значение этого числа в десятичной системе счисления (десятичный эквивалент двоичного числа):

1001, 1001₍₂₎=9,8125₍₁₀₎ .

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

Таблица 3.1

Десятичная	Эквиваленты в системах счисления	Десятичная	Эквиваленты в системах счисления
цифра	p=2	p=8	p=16	цифра	p=2	p=8	p=16
0	0	0	0	8	1000	10	8
1	1	1	1	9	1001	11	9
2	10	2	2	10	1010	12	A
3	11	3	3	11	1011	13	B
4	100	4	4	12	1100	14	C
5	101	5	5	13	1101	15	D
6	110	6	6	14	1110	16	E
7	111	7	7	15	1111	17	F

Для записи одного и того же значения в различных системах счисления требуется разное число позиций или разрядов. Например, 96₍₁₀₎=140₍₈₎=1100000₍₂₎. Чем меньше основание системы счисления, тем больше длина числа (длина разрядной сетки). Если длина разрядной сетки задана, то это ограничивает максимальное по абсолютному значению число, которое можно записать.

Пусть длина разрядной сетки равна числу N. Тогда

A _{(p )max} = p^N - 1.

Если же задано максимальное абсолютное значение числа, то длина разрядной сетки N равна:

N=log_P (A_(P)max+1).

Интервал числовой оси, заключенный между максимальным и минимальными числами, называется диапазоном представления (ДП) чисел в данной системе счисления для заданной длины разрядной сетки:

-A _(P)max ДП A_(P)max .

В ЭВМ длина обрабатываемых чисел обычно ограничена следующими значениями: 1 байт (8 двоичных разрядов), 2 байта (16 разрядов), 4 байта (32 разряда) и 8 байт (64 разряда). Соответственно ограничены и значения чисел, записываемых с использованием этих разрядных сеток. Так, максимальное целое положительное число, которое можно записать с использованием 16 двоичных разрядов, равно 2¹⁶-1 = =65535.

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

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

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

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

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)=a_n-1?q^n-1+…+a₀?q⁰+a -₁?q^-1+…+a_-m?q^-m ;

- все цифры a_i и основание q в правой части записываются (замещаются) в системе счисления с новым основанием p и выполняются необходимые операции. При этом, если р>q, то изображение цифр в p-ичной системе совпадает с изображением чисел в q-ичной системе. Если же p<q, то необходимо знать представление чисел от p до q в системе счисления с основанием р.

Пример 3.8. Перевести число 357 ₍₈₎ в десятичную систему счисления.

Решение. 357₍₈₎=3?8²+5?8¹+7?8⁰=192+40+7=239₍₁₀₎.

Пример 3.9. Перевести число 13,5₍₁₀₎ в двоичную систему счисления.

Решение. 13,5₍₁₀₎=1?10¹+3?10⁰+5?10^-1=1?1010+11+101/1010=1101,1₍₂₎ .

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

Этот метод используется для перевода только целых чисел.

Пусть число A_(q) требуется записать в р-ичной системе. Допустим, что такое представление получено и новое число В_(р) имеет вид:

A_(q) = B_(p) = b_n-1 b_n-2 … b₁ b_{0 (p)} = b_n-1?p^n-1 + b_n-2?p^n-2 + … + b₁ p¹ + b₀.

Разделим число A_(q) на р. Так как b₀<p, то в результате деления получим целую часть:

A₁ = b_n-1?p^n-2 + b_n-2?p^n-3 + … + b₁

и остаток b₀. Отсюда следует, что остаток от деления заданного числа на основаниe р равен значению цифры младшего разряда р-ичного числа. При этом, если p<q, то остаток является цифрой р-ичной системы счисления, а при p>q остаток представляет собой число в q-ичной системе счисления, которое соответствует цифре р-ичной системы (заметим, что деление должно выполняться в q-ичной системе счисления, т.е. в системе, в которой задано исходное число).

Чтобы найти цифру b₁ следует отбросить остаток b₀, a А₁ вновь разделить на р. Получим целую часть

А₂ = b_n-1?p^n-3 + … b₃?p + b₂

и остаток b₁, который равен значению цифры очередного разряда. Последовательное деление продолжается до тех пор, пока не получится частное, меньшее р. Это частное является цифрой старшего разряда искомого р-ичного числа.

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

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

Решение:

Ответ: B₍₂₎=b₅ b₄ b₃ b₂ b₁ b₀₍₂₎=100110₍₂₎ .

Пример 3.11. Провести обратный перевод числа B₍₂₎=100110₍₂₎ в десятичную систему счисления.

Решение: Сначала новое основание системы счисления представим в двоичной системе: 10₍₁₀₎=1010₍₂₎. Далее делим число 100110₍₂₎ на основание 1010₍₂₎.

100110

1010

10010

1010

Ответ: 100110₍₂₎=b₁b_{0 (10)} = 38₍₁₀₎.

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

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

Пусть правильную дробь 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, а дробная

A₁=b_-2?p^-1+b_-3?p^-2 + … + b_-m?p^-m+1,

причем A₁-правильная дробь, т.к. все a_i < p.

Таким образом, в результате умножения числа А на основание р получается целая часть, равная значению цифры старшего разряда р-ичного числа. Продолжая умножать дробные части A_j на основание р (целые части при умножении отбрасываются), можно получить остальные цифры искомой дроби: ими являются целые части получаемых произведений. При этом, если p<q, то целые части произведения являются цифрами р-ичной системы счисления, а при p>q целые части представляют собой числа в q-ичной системе счисления, которые необходимо заменить цифрами р-ичной системы.

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

Пример 3.12. Перевести десятичную дробь A₍₁₀₎=0,6875₍₁₀₎ в двоичную систему счисления.

Решение. Выполним следующие действия:

Ответ: B₍₂₎=0, b_-1 b_-2 b_-3 b_-4=0,1011₍₂₎.

Пример 3.13. Провести обратный перевод двоичного числа 0,1011₍₂₎ в десятичную дробь.

Решение. В данном примере p>q, поэтому сначала переведем р₍₁₀₎ в двоичную систему счисления: р=10₍₁₀₎=1010₍₂₎. Выполним последовательные умножения:

Ответ: B₍₁₀₎=0, b_-1 b_-2 b_-3 b_-4 = 0,6875.

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

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

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

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

Пусть задано число А в 8-ричной системе:

A=a_n-1 a_n-2…a₁ a₀₍₈₎ = a_n-1?8^n-1+a_n-2?8^n-2+…+a₁?8¹+a₀?8⁰.

Пусть число А записано в 2-ичной системе счисления:

A=b_l-1 b_l-2…b₂ b₁ b_{0 (2)} = b_l-1?2^l-1+b_l-2?2^l-2+…+b₂?2²+b₁?2¹+b_0.

Так как числа одинаковые, мы можем приравнять их друг другу:

a_n-18^n-1+a_n-28^n-2+…+a₁8¹+a₀8⁰= b_l-1 2^l-1+2_l-2 2^l-2+…+b₂ 2²+b₁ 2¹+b₀ 2⁰ .

Если разделить обе части равенства на 8, то получим одинаковые частные

a_n-1 8^n-2 + a_n-2 8^n-3 +…+ a₁ = b_l-1 2^l-4 + b_l-2^l-5 +…+ b₄ 2¹ + b₃

и одинаковые остатки:

a₀₍₈₎=b₂ 2² + b₁ 2¹ + b₀ 2⁰ = b₂ b₁ b_{0 (2)}.

Следовательно, младшая восьмеричная цифра a₀₍₈₎ выражается трехразрядным двоичным числом b₂ b₁ b_{0 (2)}.

Если частное вновь разделить на 8, то получим

а₁₍₈₎=b₅ b₄ b_{3 (2)}.

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

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

Пример 3.14. Перевести восьмеричное число 571,034 ₍₈₎ в двоичное.

Решение.

.

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

Пример 3.15. Перевести двоичное число 11011111011001 , 1001₍₂₎ в восьмеричное.

Решение.

.

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

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

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

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

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

Прямой код

Прямой код соответствует обычной записи числа со своим знаком. Положительное число имеет в знаковом разряде символов 0, отрицательное - 1. Прямой код обозначают [A]_пр, а знаковый разряд отделяют от цифровых разрядов точкой.

Числа в прямом коде представляются в форме:

при А ? 0 [A]_пp = 0.a_n-1a_n-2 … a₁a₀,a_-1 … a_-m;

( 3.2 )

при А ? 0 [A]_пр = 1.a_n-1a_n-2 … a₁a₀,a_-1 … a_-m ;

Пример 3.16.

А =+11011,1001; [A]_пр=0.11011,1001 (n=5, m=4).

Пример 3.17.

В =-1010,101, [В]_пр=1.1010,101 (n=4, m=3).

Число нуль в прямом коде имеет два изображения:

+ 0 : [0]_пр = 0.00…0, - 0 : [0]_пр = 1.00…0.

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

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

( 3.3 )

Здесь a_n - не знаковый разряд , он будет участвовать во всех операциях. Как увидим, введение этого разряда позволит заменить операцию вычитания операцией алгебраического сложения чисел с разными знаками. Для удобства разряд a_n все равно называют знаковым. При записи чисел разряд с отрицательным весовым коэффициентом отделяют точкой.

Обратный код

Для образования обратного кода коэффициент С в выражении (3.3) выбирается равным максимальному числу, которое может быть записано в регистре с n целыми и m дробными разрядами:

С = 2ⁿ-2^-m.

Двоичное число в обратном коде записывается в виде

[A]_обр = b_n.b_n-1 … b₁b₀,b_-1 … b_-m,

при этом число А определяется как:

( 3.4 )

Пример 3.18. Найти значения двоичных чисел, записанных в обратном коде:

[A₁]_обр = 0.110,11, [A₂]_обр = 1.011,01 (n=3, m=2).

Решение. А₁=0^. (-2⁺³+2^-2)+110,11=+110,11.

А₂ = 1^. (-2⁺³+2^-2)+011,01=-1000+0,01+011,01=-100,10.

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

Чтобы найти правило перехода от прямого кода отрицательного числа к обратному, приравняем правые части соотношений (3.2) и (3.4). Учитывая, что в соотношении (3.4 ) для отрицательных чисел b_n=1, получим:

Так как то

Следовательно, b_i=1-a_i, т.е. если a_i=0, то b_i=1 и если a_i=1, то b_i=0.

Правило: Для получения обратного кода для отрицательного числа следует в разряд с отрицательным весовым коэффициентом записать 1, а в остальных разрядах прямого кода заменить 1 на 0, а 0 на 1. Аналогично образуется и прямой код отрицательного числа из обратного.

Пример 3.19. Получить обратный код для числа А = -10101,1011.

Решение. [A]_пр = 1.10101,1011, [A]_обр = 1.01010,0100.

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

Нуль в обратном коде имеет два представления:

+ 0 : [0]_обр = 0.00 … 0, - 0 : [0]_обр = 1.11 … 1.

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

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

Рассмотрим возможные случаи при сложении чисел В и С : В+С=D.

1. B > C , C > 0. Так как положительные числа в прямом и обратном кодах записываются одинаково, то и складываются они по известному правилу.

2. Рассмотрим сложение чисел с разными знаками: В > 0, C < 0.

[B]_обр = 0.b_n-1b_n-2 … b₁b₀,b_-1 … b_-m,

[C]_обр = 1.c_n-1c_n-2 … c₁c₀,c_-1 … c_-m, .

Тогда

[B]_обр + [C]_обр = [D]_обр = d_n.d_n-1 … d₁d₀,d_-1 … d_-m ,

D . (3.5)

Рассмотрим два случая в выражении (3.5):

1.

Тогда нет переноса в n-й разряд и [D]_обр имеет вид:

[D]_обр = 1.d_n-1 … d₁d₀,d_-1 … d_-m,

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

Пример 2.20. Сложить два числа в обратных кодах: В = + 3₍₁₀₎,

С = - 5₍₁₀₎, n=3, m=0.

Решение. В = + 011₍₂₎, С = - 101₍₂₎.

[B]_обр =0.011

[C]_обр =1.010

[D]_обр =1.101 .

[D]_пр = 1.010, D = - 010₍₂₎ = - 2₍₁₀₎ , т.е. + 3₍₁₀₎ + (-5)₍₁₀₎ = - 2₍₁₀₎.

2.

В данном случае имеется единица переноса в n-ный разряд и тогда можно записать:

Подставив это выражение, получим:

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

Заметим, что в этом случае при сложении чисел по обычным правилам появится 1 переноса из разряда с отрицательным весом, которая также участвует в операции сложения. Это и является формальным признаком того, что необходимо добавить 1 в младший разряд. Такая операция называется циклическим переносом.

Пример 3.21. Сложить два числа в обратных кодах: В = +5 ₍₁₀₎,

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

Пример 3.22. Сложить два числа в обратных кодах: В = - 2₍₁₀₎, С = - 5₍₁₀₎, n=3, m=0.

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

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

...