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

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





Раздел 1 Основные понятия и методы теории информатики

Информатика - это комплексная, техническая наука, которая систематизирует приемы создания, сохранения, воспроизведения, обработки и передачи данных средствами вычислительной техники, а также принципы функционирования этих средств и методы управления ними. Термин "информатика" происходит от французского слова Informatique и образован из двух слов: информация и автоматика. Этот термин введен во Франции в середине 60-х лет XX ст., когда началось широкое использование вычислительной техники. Тогда в англоязычных странах вошел в употребление термин "Computer Science" для обозначения науки о преобразовании информации, которая базируется на использовании вычислительной техники. Теперь эти термины являются синонимами.

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

Предмет информатики как науки составляют:

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

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

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



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

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

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

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


Тема 1.1 Понятие информации

Термин «информация» происходит от лат. informatio – «сведения, разъяснения, изложение». Понятие И. имеет настолько широкий смысл, что невозможно составить его обобщающего определения.

 

Существующие определения отражают отдельные из всевозможных аспектов И.:

1) в обиходе И. называют любые данные или сведения, которые кого-либо интересуют. Например, сообщение о каких-либо событиях, о чьей-либо деятельности и т.п. «Информировать» в этом смысле означает «сообщить нечто, неизвестное раньше»;

2) в технике под И. понимают сообщения, передаваемые в форме знаков или сигналов;

3) Норберт Винер определял И. как обозначение содержания, полученного из внешнего мира в процессе нашего приспособления к нему и приспособления к нему наших чувств;

4) Клод Шеннон, американский учёный, заложивший основы теории информации, рассматривает И. как снятую неопределенность наших знаний о чем-то, то есть И. является средством, сокращающим энтропию. (Энтропия – мера неопределенности. Измеряется вероятностью наступления одного из N возможных событий. Если вероятность одного из них становится равной 1, то неопределенность отсутствует (вероятность остальных равна 0). Максимальная неопределенность имеет место, если все события равновероятны).

Федеральный закон «Об информации, информационных технологиях и защите информации» (от 27 июля 2006 г. № 149-ФЗ) определяет И. как «сведения (сообщения, данные) независимо от формы их представления».

 

И. не следует отождествлять с данными. Данные – это И., представленная в форме, удобной для хранения, передачи и обработки. Связь между данными и И. определяется следующим образом:

· информация – это полезное содержание данных;

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

 

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

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

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

 

 

Передача информации – это распространение И. в пространстве. И. передается с помощью сообщений.

 

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

 

Средством же передачи И. является сигнал.

 

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

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

 

Канал связи – это естественный или искусственный материальный объект, обеспечивающий передачу данных от источника к приёмнику.

 

Хранение информации – это распространение И. во времени. Средством хранения И. является носитель информации.

 

Носитель информации – это материальный объект-регистратор данных (бумага, магнитный и оптический диски и т.д.).

Свойства информации

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

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

3) Достоверность информации.Данные возникают в момент регистрации сигналов, но не все сигналы являются «полезными» — всегда присутствует какой-то уровень посторонних сигналов, в результате чего полезные данные сопровождаются определенным уровнем «информационного шума». Если полезный сигнал зарегистрирован более четко, чем посторонние сигналы, достоверность информации может быть более высокой. При увеличении уровня шумов достоверность информации снижается. В этом случае для передачи того же количества информации требуется использовать либо больше данных, либо более сложные методы.

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

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

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

 

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

Операции с данными

В структуре возможных операций с данными можно выделить следующие основные:

· сбор данных – накопление информации с целью обеспечения достаточной полноты для принятия решений;

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

· фильтрация данных – отсеивание «лишних» данных, в которых нет необходимости для принятия решений; при этом должен уменьшаться уровень «шума», а достоверность и адекватность данных должны возрастать;

· сортировка данных – упорядочение данных по заданному признаку с целью удобства использования; повышает доступность информации;

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

· защита данных – комплекс мер, направленных на предотвращение утраты, воспроизведения и модификации данных;

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

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

 


Единицы измерения данных

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

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

Более крупная единица измерения – килобайт (Кбайт). Условно можно считать, что 1 Кбайт примерно равен 1000 байт. Условность связана с тем, что для вычислитель­ной техники, работающей с двоичными числами, более удобно представление чисел в виде степени двойки и потому на самом деле 1 Кбайт равен 210 байт (1024 байт). Однако всюду, где это не принципиально, с инженерной погрешностью (до 3 %) «забывают» о «лишних» байтах.

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

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

· 1 Кбайт = 1024 байт = 210 байт ≈ 103 байт.

· 1 Мбайт = 1024 Кбайт = 210 Кбайт = 220 байт = 1.048.576 байт ≈ 106 байт.

· 1 Гбайт = 1024 Мбайт = 210 Мбайт = 230 байт = 1.073.741.824 байт ≈ 109 байт.

· 1 Тбайт = 1024 Гбайт = 210 Гбайт = 240 байт = 1.099.511.627.776 байт ≈ 1012 байт.

· 1 Пбайт = 1024 Тбайт = 210 Тбайт = 250 байт = 1.125.899.906.842.624 байт ≈ 1015 байт.

Таким образом, например, минимальный объем видеопамяти необходимый для LCD-монитора с разрешением 1280´1024 dpi в режиме цветопередачи True Color (32 бита) составит:

1280´1024´32 бит = 41.943.040 бит = 5.242.880 байт = 5.120 Кбайт = 5 Мбайт.

Единицы хранения данных

При хранении данных решаются две проблемы: как сохранить данные в наиболее компактном виде и как обеспечить к ним удобный и быстрый доступ (если доступ не обеспечен, то это не хранение). Для обеспечения доступа необходимо, чтобы данные имели упорядоченную структуру, а при этом, как мы уже знаем, образуется «паразитная нагрузка» в виде адресных данных. Без них нельзя получить доступ к нужным элементам данных, входящих в структуру.

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

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

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

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

Тема 1.3 Системы счисления

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

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

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

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

Любая позиционная СС с основанием q может быть представлена в виде полинома:

A(q) = rnqn + rn–1qn–1 + rn–2qn–2 + … + r1q1 + r0q0 + r–1q–1 + …,

где A – число в позиционной СС с основанием q; ri – коэффициент; n – степень и индекс.

Позиционные СС бывают различными в зависимости от основания:

1) Десятичная с основанием 10

[0 1 2 3 4 5 6 7 8 9]

23610 = 2∙102 + 3∙101 + 6∙100

2) Восьмеричные с основанием 8

[0 1 2 3 4 5 6 7]

2368 = 2∙82 + 3∙81 + 6∙80 = 15810

3) Шестнадцатеричная с основанием 16

[0 1 2 3 4 5 6 7 8 9 A B C D E F]

2АF16 = 2∙162 + A∙161 + F∙160 = 2∙162 + 10∙161 + 15∙160 = 68710

4) Двоичная с основанием 2

[0 1]

10112 = 1∙23 +0∙22 + 1∙21 + 1∙20 = 1110

Таблица 1.3.1 – Методы перевода целых и дробных чисел в десятичную СС

Тип преобразования Целые числа Дробные числа
Повторное умножение промежуточного результата на q и сложение со значением разряда данного числа. Первый промежуточный результат есть старший разряд Повторное деление промежуточного результата на q и сложение с разрядом данного числа. Первый промежуточный результат есть последний разряд, разделенный на q
Двоичное в десятичное 1∙2 + 1 = 3 3∙2 + 0 = 6 6∙2 + 1 = 13 13∙2 + 1 = 27 27∙2 + 0 = 54 54∙2 + 0 = 108   11011002 = 10810 1:2 = 0,5 (0,5 + 1):2 = 0,75 (0,75 + 0):2 = 0,375 (0,375 + 1):2 = 0,6875 (0,6875 + 0):2 = 0,34375 (0,34375 + 1):2 = 0,67187 (0,67187 + 0):2 = 0,33593   0,01010112 = 0,33593 ≈ 0,33610
Десятичное в восьмеричное 1∙8 + 5 = 13 13∙8 + 4 = 108   1548 = 10810 5:8 = 0,625 (0,625 + 0):8 = 0,078125 (0,078125 + 6):8 = 0,75976 (0,75976 + 5):8 = 0,71997 (0,71997 + 2):8 = 0,33999   0,256058 = 0,33999 ≈ 0,34010
Десятичное в шестнадцатеричное 6∙16 + 12 = 108   6С16 = 10810 A:16 = 0,625 (0,625 + 0):16 = 0,039062 (0,039062 + 6):16 = 0,75976 (0,75976 + 7):16 = 0,71997 (0,71997 + 5):16 = 0,33999   0,570A16 = 0,33999 ≈ 0,34010

 

Таблица 1.3.2 – Методы перевода целых и дробных чисел из десятичной СС

Тип преобразования Целые числа Дробные числа
Деление данного десятичного числа на q. Остатки дают превращенное число, которое читается в обратном направлении Повторное умножение данного десятичного числа на q. Разряд перед запятой дает разряд превращенного числа. При дальнейшем умножении используется лишь дробная часть промежуточного результата
Десятичное в двоичное 108:2 = 54 остаток 0 54:2 = 27 остаток 0 27:2 = 13 остаток 1 13:2 = 6 остаток 1 6:2 = 3 остаток 0 3:2 = 1 остаток 1 1:2 = 0 остаток 1   10810 = 11011002 0,34∙2 = 0,68 переносится 0 0,68∙2 = 1,36 переносится 1 0,36∙2 = 0,72 переносится 0 0,72∙2 = 1,44 переносится 1 0,44∙2 = 0,88 переносится 0 0,88∙2 = 1,76 переносится 1 0,76∙2 = 1,52 переносится 1   Прерывание 0,3410 = 0,01010112
Десятичное в восьмеричное 108:8 = 13 остаток 4 13:8 = 1 остаток 5 1:8 = 0 остаток 1   10810 = 1548 0,34∙8 = 2,72 переносится 2 0,72∙8 = 5,76 переносится 5 0,76∙8 = 6,08 переносится 6 0,08∙8 = 0,64 переносится 0 0,64∙8 = 5,12 переносится 5   Прерывание 0,3410 = 0,256058
Десятичное в шестнадцатеричное 108:16 = 6 остаток 12 6:16 = 0 остаток 6   10810 = 6С16 0,34∙16 = 5,44 переносится 5 0,44∙16 = 7,04 переносится 7 0,04∙16 = 0,64 переносится 0 0,64∙16 = 10,24 переносится 10   Прерывание 0,3410 = 0,570A8

 

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

Таблица 1.3.3 – Методы перевода целых чисел из одной СС в другую СС

Десятичное число Двоичное число Восьмеричное число Десятичное число Двоичное число Шестнадцатеричное число
A
B
C
D
E
F

 

Перевод [восьмеричное число] ↔ [двоичное число]
24518 = 010.100.101.001 = 101001010012
Восьмеричные цифры
Двоичные триады
1010011110102 = 101.001.111.010 = 51728
Двоичные триады
Восьмеричные цифры

 

Перевод [шестнадцатеричное число] ↔ [двоичное число]
4C716 = 0100.1100.0111 = 100110001112
Шестнадцатеричные цифры С
Двоичные тетрады
1010001111102 = 1010.0011.1110 = A3E16
Двоичные тетрады
Шестнадцатеричные цифры A E

 

Перевод [восьмеричное число] → [двоичное число] → [шестнадцатеричное число]
24518 = 010.100.101.001 = 101001010012
Восьмеричные цифры
Двоичные триады
101001010012 = 0101.0010.1001 = 52916
Двоичные тетрады
Шестнадцатеричные цифры
24518 = 010.100.101.001 = 101001010012 = 0101.0010.1001 = 52916
Перевод [шестнадцатеричное число] → [двоичное число] → [восьмеричное число]
4C716 = 0100.1100.0111 = 100110001112
Шестнадцатеричные цифры С
Двоичные тетрады
100110001112 = 010.011.000.111 = 23078
Двоичные триады
Восьмеричные цифры
4C716 = 0100.1100.0111 = 100110001112 = 010.011.000.111 = 23078
               

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

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

Сложение Вычитание Умножение
0 + 0 = 0 0 – 0 = 0 0∙0 = 0
0 + 1 = 1 1 – 0 = 1 0∙1 = 0
1 + 0 = 1 1 – 1 = 0 1∙0 = 0
1 + 1 = 10 10 – 1 = 1 1∙1 = 1

 

Сложение двух многоразрядных двоичных чисел проводится поразрядно с учетом единиц переполнения от предшествующих разрядов:

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

Умножение представляет собой многоразовое сложение промежуточных сумм и сдвиги:

Процесс деления состоит из операций вычитания, которые повторяются:


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

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

 

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

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

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

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

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

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

 

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

A = m·qn,

где q – основание СС;

n – целое число, называемое порядком числа A;

m – мантисса числа A (|m| < 1).

Поскольку в ЭВМ применяется двоичная СС, то A = m·2n, причем порядок и мантисса представлены в двоичной форме.

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

· 3.1415926 = 0,31415926·101;

· 0,00125 = 0,125·10-2.

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

Для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). Шестнадцать бит позволяют закодировать целые числа от 0 до 65535, а 24 бита – уже более 16,5 миллионов разных значений.

Для кодирования действительных чисел используют 80-разрядное кодирование

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

Тема 1.5 Основные понятия алгебры логики

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

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

Соответственно рассмотренному перечню логических функций различают три основных логических элемента (ЛЭ): «И», «ИЛИ», «НЕ» (рисунок 1.5.1).

 
 

 


Рисунок 1.5.1 – Условные графические обозначения логических элементов

Число входов элементов «И», «ИЛИ» может быть произвольным, а элемент «НЕ» имеет только один вход.

 

На практике широкое применение нашли ЛЭ, которые совмещают функции указанных выше элементов. Это ЛЭ «И-НЕ» и «ИЛИ-НЕ» (рисунок 1.5.2).

 

 
 

 

 


Рисунок 1.5.2 – Условные графические обозначения ЛЭ «И-НЕ» и «ИЛИ-НЕ»

 

 

Минимизация булевых функций

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

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

Метод Карно-Вейча

Метод диаграмм Вейча, усовершенствованный Карно, применяется в случае, если число аргументов ФАЛ не больше 5–6. Карты Карно – это графическое представление таблиц истинности. Каждой комбинации переменных ставится в соответствие клетка карты Карно. В клетку записывается значение ФАЛ (0 или 1) для данной комбинации входных переменных. Входные переменный располагаются по внешним сторонам карты напротив ее строк и столбцов.

 

Пример:

Для вышерассмотренной таблицы истинности:

x2 x1 x0 y = f(x2,x1,x0)

 

Карта Карно для ФАЛ трех переменных по приведенной таблице истинности имеет вид:

 
 

 


Каждая из входных переменных делит по-своему любую карту Карно на две равные части, в одной из которых значение этой переменной равняется «1», а в другой – «0». Каждой клетке карты отвечает определенная комбинация значений всех входных переменных, а каждая сторона клетки представляет собой границу между значениями переменных. Число клеток карты Карно определяется величиной 2n, где n – число входных переменных ФАЛ.

 

Свойства карты Карно:

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

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

 

Для некоторой ФАЛ, представленной с помощью карты Карно, можно записать несколько алгебраических выражений в дизъюнктивной или конъюнктивной форме.

 

При этом необходимо руководствоваться следующими правилами:

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

2) Единичные контуры могут содержать несколько единиц, но не должны содержать нулей. Нулевые контуры могут содержать несколько нулей, но не должны содержать единиц.

3) Одноименные контуры могут накладываться один на другой, т.е. одна и та же единица (или ноль) может входить в несколько единичных (нулевых) контуров.

4) Число клеток в контуре должно быть равно 2i , где i = 0, 1, 2, …, n, т.е. число клеток в контуре выражается числами 0, 1, 2, 4, 8, 16, 32, …

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

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

7) Дизъюнктивная форма ФАЛ составляется в виде дизъюнкций конъюнкций, которые отвечают единичным контурам. Конъюнктивная форма ФАЛ составляется в виде конъюнкций дизъюнкций, которые отвечают нулевым контурам.

8) Если каждой клетке отвечает свой контур, то результирующее выражение представляет собой СДНФ или СКНФ данной ФАЛ. Минимальной ДНФ или КНФ отвечает минимальное количество единичных или нулевых контуров.

 

Пример для вышерассмотренной таблицы истинности:

x2 x1 x0 y = f(x2,x1,x0) x2 x1 x0 y = f(x2,x1,x0)
0

 

 

Минимальная ДНФ: Минимальная КНФ:

Построение логических схем

Пример для вышерассмотренной таблицы истинности:









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.