Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
59.(СиФо).Организация компьютерной памяти. Постоянные запоминающие устройства (ПЗУ). Флэш-память.
Постоянные запоминающие устройства (ПЗУ или ROM), которые также часто называют энергонезависимыми, обеспечивают сохранение записанной в них информации и при отсутствии напряжения питания. К началу 2000-х годов наибольшее распространение получили полупроводниковые ПЗУ. В полупроводниковых ПЗУ в качестве элементов памяти обычно используются транзисторы. Они объединены в матрицу. Различают две большие группы ПЗУ: программируемые изготовителем и программируемые пользователем. ЗУ первой группы, называемые иначе масочными, обычно выпускаются большими партиями. Информация в них заносится в процессе изготовления этих ЗУ на заводах: с помощью специальной маски в конце технологического цикла на кристалле формируется соответствующая конфигурация соединений. Их обычно используют для хранения различных постоянных программ и подпрограмм, кодов, физических констант, постоянных коэффициентов и пр. В ПЗУ, программируемые пользователем, информация записывается после их изготовления самими пользователями. При этом существуют два основных типа таких ЗУ: однократно программируемые и перепрограммируемые. Наиболее простыми являются однократно программируемые ПЗУ. В этих ЗУ запись как раз и производится посредством разрушения соединительных перемычек между выводами транзисторов и шинами матрицы. Перепрограммируемые ПЗУ позволяют производить в них запись информации многократно.
Рис – элементы памяти а – диодное ПЗУ,б – ПЗУ на стабилитронах,в – ПЗУ с плавкими перемычками,г – ПЗУ на транзисторах с изолированным затвором
Рис. - структурная схема ПЗУ с однократным программированием
Флэш-память -представитель класса перепрограммируемых постоянных ЗУ с электрическим стиранием. Однако стирание в ней осущ-ется сразу целой области ячеек: блока или всей микросхемы. Флэш-память строится на однотранзисторных элементах памяти (с “плавающим” затвором), что обеспечивает плотность хранения инфы даже несколько выше, чем в динамической оперативной памяти. Сущ-ют различные технологии построения базовых эл-тов флэш-памяти. Эти технологии отличаются кол-вом слоев, методами стирания и записи данных.
Дос-ва: способность сохранять инфу при выключенном питании, малые размеры, высокая надежность и приемлемая цена. К минусам : относ-но невысокую скорость передачи данных.
Принцип функционирования. Перед записью данных в ЗУ ячейки, в к-ые будет производиться запись, должны быть стерты. Стирание заключается в переводе эл-тов памяти в состояние 1 и возможно только сразу для целого блока ячеек. Выборочное стирание невозможно. В процессе записи инфы соответствующие элементы памяти переключаются в нулевое состояние.
59. Лист 2. (СиФо).
В самой ЭВМ эту память применяют для хранения BIOS. Другим применением флэш-памяти являются так называемые “твердотельные диски” (solidstate disks), эмулирующие работу внешних винчестеров. Более общее применение флэш-память находит в различных модификациях карт памяти, которые используются не только в компьютерах разных классов, но и в цифровых видео- и фотокамерах, плеерах, телефонах, музыкальных центрах и другой медиатехнике. Причем такая карта может также быть и сменной картой в твердотельном диске.
60.(СиФо).Проектирование процессоров. Особенности организации современных процессоров. Концепция открытых систем.
Процесс выполнения программы сводится к циклу выполнения команд:
1. Выборка команды из памяти. 2. Выборка операндов.
3. Выполнение операции. 4. Запись результата.
5. Переход к п. 1.
CISC-процессоры отличаются сложностью форматов и переменной длиной команд, сложным устр-вом управления, что препятствует повышению тактовой частоты. RISC-команды позволяет увеличивать тактовую частоту: блоки конвейеров проще, время их работы меньше, такт работы конвейера меньше, частота процессора выше.Недостаток RISC-процессоров - большой объем (длина) машинных программ.
Пример простейшего естественного параллелизма –целочисленная обработка и обработка с плавающей запятой. Испол-ние этого параллелизма привело к появлению процессоров с разнесенной структурой. Процессор с разнесенной архитектурой состоит из двух субпроцессоров, каждый из к-рых управляется собственным потоком команд. А-процессор выполняет все целочисленные вычисления и формирует обращения к памяти по чтению и записи. Е-процессор реализует вычисления с плавающей запятой.
А-процессор выполняет все целочисленные (прежде всего адресные) вычисления и формирует обращения к памяти по чтению и записи. Е-процессор реализует вычисления с плавающей запятой.
Данные, извлекаемые из памяти, разделяются по типам и помещаются в соответствующую очередь (FIFO-очередь) адресов АА (целочисленные данные) или АЕ - очередь данных с плавающей запятой. Если очередь АЕ пуста, то Е-процессор ждет поступления данных в очередь АЕ от А-процессора. Результаты обработки из Е-процессора помещаются в очередь результатов ЕА для записи в память по адресу из очереди адресов записи AW. Адрес для записи результата вычисляется А-процессором и отправляется в очередь адресов для записи AW, не дожидаясь, пока результат обработки поступит в очередь ЕА. А-процессор, выбирая первые элементы из очередей AW, ЕА, организует их в пары А,D и отправляет в память (на запись). Если одна из очередей пуста (или обе вместе), то запись в память приостанавливается.
При чтении из памяти А-процессор отправляет данные либо в очередь АА (целочисленные данные), либо в очередь ЕА (плавающая запятая). Расщепление последовательной программы на потоки команд для А- и Е-процессоров осуществляется либо на уровне компилятора, либо в процессоре специальным блоком–расщепителем.
Открытая система –система, разработанная с испол-нием стандартных средств: интерфейсов, протоколов и форматов данных, переносимых по принципам построения.
Переносимость –возможности исполнения программы в исх кодах на различных аппаратных ср-вах под управлением различных ОС. Взаимодействие – обеспечивающее способность обмена инфо-ей с автоматическим восприятием форматов и семантики данных. Масштабируемость - обеспечивает возможность исполнения программ на различных ресурсах с пропорциональным изменению ресурсов значением показателей эффективности.
61.(СиФо).Устр-тва управления ЭВМ. Организация управляющего автомата с программируемой логикой управления.
ОУ работает во времени тактами. В каждом такте ОА может выполнить одну или несколько совместимых МО. Для этого УА должен вырабатывать в каждом такте один или несколько управляющих сигналов.
Очевидный способ формирования управляющих сигналов состоит в следующем: набору сигналов y1 ,y2, ..., yМ (одна из функций ОА) ставится в соответствие слово Y= y1 ,y2, ..., yМ, в котором каждой МО, которая должна выполнятся в данном такте, ставится в соответствие единица, если нет - то ноль, т.е. производится унитарное кодирование МО.
Чтобы в следующем такте можно было вырабатывать другие сигналы, достаточно сменить слово Y на входе этой схемы.
Двоичный код Y, на основе которого вырабатываются управляющие сигналы, естественно называют управляющим словом или микрокомандой (МК). Алгоритм операции fgєF, описанный в терминах МК, называют микропрограммой. Для хранения микропрограммы естественно использовать ПЗУ. Из ПЗУ МК извлекаются поочерёдно и используются для выработки управляющих сигналов ym.
УА, построенный в соответствии с идеей формирования управляющих сигналов на основе МК, извлекаемых из ПЗУ, и наз УА с программируемой логикой (ПЛ) управления. Усовершенствование идеи Уилкса: при большом числе управляющих сигналов испол-ие идеи Уилкса, т.е. унитарного кодирования МО, ведёт к большой длине МК и, =>, к большой ёмкости ПЗУ для хранения МП.
Простой способ сокращения длины МК - использование позиционного кода вместо унитарного: т.н. позиционное кодирование МО. Длина позиционного кода m= log2M (M=2m). Недостаток: в каждом такте можно вырабатывать только один сигнал. Это нежелательно, т.к. вносит ограничения на совместимость МО и снижает производительность ОА.
Поэтому обычно применяется способ кодирования МО – т.н. смешанное кодирование. Суть: всё множество МО Y= y1, y2, ..., yМ разделяется на группы несовместимых МО.
Можно ещё уменьшить длину МК, если использовать способ код-я – т.н. косвенное кодирование МО. Суть: кодир-ю подвергаются не отдельные МО, а наборы совместимых МО.
принудительной адресацией МК
62.(СиФо).Устройства ввода/вывода. Организация и основные принципы построения систем ввода/вывода.
Интерфейс представляет собой совокупность линий и шин, сигналов,электронных схем и алгоритмов (протоколов), предназначенную дляосуществления обмена информацией между устройствами ЭВМ. Физически интерфейс представляет собой совокупность линий и схемформирования сигналов. Все линии интерфейса разбиты на группы линий –шины.
Шины интерфейса в зависимости от их назначения можно разделить на: 1.информационные, предназначенные для передачи команд, данных иадресов;2.идентификации типа информации, передаваемой по информационнымшинам;3.управляющие, предназначенные для синхронизации, инициирования изавершения передачи информации.
В зависимости от способа реализации интерфейса различают: ЭВМ с одним общим интерфейсом и ЭВМ с множеством интерфейсов и процессорами (каналами) ввода - вывода.
ЭВМ с одним общим интерфейсом
Внешние устройства подключаются к единому интерфейсу через контроллер – устройство управления ВУ. Контроллер ВУ выполняет следующие функции: 1.согласуют форматы данных, используемые в ВУ, с форматом, принятым для передачи по единому интерфейсу; 2. обеспечивают синхронизацию работы ВУ с другими устр.; 3.обеспечивают буферизацию информации.
ЭВМ с множеством интерфейсов и каналамивв-вывода.
В данной структуре используются интерфейсы четырех типов: - оперативной памяти. Через интерфейс основной памяти производится обмен информацией между ОП, с одной стороны, и процессором (процессорами) и каналами ввода-вывода - с другой; - процессор - каналы. Интерфейс "процессор - каналы" предназначается для передачи управляющей информации между процессорами и каналами ввода-вывода;- ввода-вывода. Через интерфейс ввода-вывода производится обмен информацией между каналами и контроллерами ВУ;-малые интерфейсы внешних у-в. Через малые интерфейсы осуществляется передача информации между контроллерами ВУ и ВУ.
63.(СиФо).Элементы архитектуры компьютерных систем. Способы адресации информации в памяти ЭВМ.
Адресация инфа – это способ исп-ния адресной части команды для адресации инфы в памяти ЭВМ. Память ЭВМ имеет трехуровневую иерархич. стр-ру.
В адресном пр-ве проца инфа адресуется обычно с точностью до байта. В адресном пр-ве ввода-вывода адресуется не инфа, а периф. устр-ва ПУ1, ПУ2, …ПУN, обращение к к-ым осущ-ется ч/з р-ры, входящие в состав контроллеров ПУ. Каждому ПУ выделяется не мене 3 р-ров различного назначения – регистры данных, состояния и управления. Эти регистры нумеруются и образуют адресное пр-во ввода-вывода. Инфа же располагается на носителях инфы (съемных или нет) ПУ. На них инфа организуется в виде массивов, к-ым присваиваются различные имена, - имена файлов. Имя файла исп-ся при обращении к массиву на носителе инфы. Местоположение файлов на носителе инфы хранится в каталоге. Каталог –таблица, в к-ой указывается соответствие имен файлов и их физич. адресов. Сам каталог располагается также на носителе инфы, т. е. каталог – это тоже файл, только специфический, адресный.
Прямая адресация – в адресной части команды указывают ячейки ОП (адрес типа А). Если это байт – то номер байта, если это слово – то номер слова. Недостатки прямой адресации: 1) длина адреса А m – переменная величина, т. к. зависит от емкости ОП 2) m принимает большие значения, т.к. емкость ОП современных ЭВМ измеряется мегабайтами. Прямая адресация обычно исп-ется только для фиксированной части ОП т.е. с помощью прямого адреса фиксированной длины n можно адресовать часть ОП - т.н. страницу ОП. Чтобы узнать, в какой странице (сегменте) находятся адресуемые прямым адресом данные, процу нужно указать № страницы. Страничная адресация. ОП разделяется на страницы фиксированной емкости ЕСТР=2n. Адрес А ячейки памяти формируется из 2 полей: А=Р.D, Р – № страницы (старшие разряды адреса), D – № ячейки в странице (младшие разряды). № страницы Р заносится и хранится в спец. р-ре №а страницы РС ЦП, адрес ячейки D указывается в адресном поле команды. Недостатки:1)сложности с орг-цией переходов в пр-ме за пределы страницы. При таком переходе требуется выполнение доп. операций с р-ром Р, что снижает быстродействие проца;2)увеличивается длина пр-мы – за счет модификации р-ра Р, что также ведет к увеличению времени выполнения пр-мы и снижению производительности проца. Р-р Р обычно загружается и модифицируется ОС.Косвенная адресация – в адресной части команды указывается не прямой, а косвенный адрес оп-да Ак, т.е. адрес адреса оп-да: АкАО. По адресу Ак производится первое обращение к памяти и извлекается адрес оп-да А, а затем уже по адресу А производится 2ое обращение и извлекается оп-д О. Недостаток– доп. обращение к памяти и уменьшение быстродействия ЦП. Этот недостаток можно сгладить, если адрес А хранить не в ОП, а в ЛП, т.е. использовать косв. адрес типа Rк, к-ый и указывается в адресной части команды. Дос-ва: 1)возможность обработки адреса оп-нда – А=А А, 2)уменьшение длины адресной части команды при косв. рег. адресации, т. к. адрес типа R короче адреса типа А.
относительная (базовая), Индексная, индексно-относительная, непосредственная, неявная адресация
64.(СПО1).Архитектура ОС. Ядро и вспомогательные модули ОС. Концепция микроядерной архитектуры.
Наиболее общим подходом к структуризации операционной системы является разделение всех ее модулей на две группы:
Модули ядра выполняют такие базовые функции ОС, как управление процессами, памятью, устройствами ввода-вывода и т. п. Функции ядра, которые могут вызываться приложениями, образуют интерфейс прикладного программирования — API.
Вспомогательные модули ОС обычно подразделяются на следующие группы:
Многослойная структура ОС
Вычислительную систему, работающую под управлением ОС на основе ядра, можно рассматривать как систему, состоящую из трех иерархически расположенных слоев: нижний – аппаратура, промежуточный — ядро, а утилиты, обрабатывающие программы и приложения, составляют верхний слой системы.
Ядро может состоять из следующих слоев:
Выбор количества слоев ядра является ответственным и сложным делом: увеличение числа слоев ведет к некоторому замедлению работы ядра за счет дополнительных накладных расходов на межслойное взаимодействие, а уменьшение числа слоев ухудшает расширяемость и логичность системы.
Суть микроядерной архитектуры. В привилегированном режиме остается работать только очень небольшая часть ОС, называемая микроядром. В состав микроядра обычно входят машинно-зависимые модули, а также модули, выполняющие базовые функции ядра по управлению процессами, обработке прерываний, управлению виртуальной памятью, пересылке сообщений и управлению устройствами I/O. Набор функций микроядра обычно соответствует функциям слоя базовых механизмов обычного ядра Все остальные более высокоуровневые функции ядра оформляются в виде приложений, работающих в пользовательском режиме.
65.(СПО1).Процессы и потоки. Планирование и диспетчеризация потоков. Вытесняющие и невытесняющие алгоритмы планирования.
Более крупная единица работы, обычно носящая название процесса, или задачи, требует для своего выполнения нескольких более мелких работ, для обозначения которых используют термины «поток», или «нить».
В операционных системах, где существуют и процессы, и потоки, процесс рассматривается операционной системой как заявка на потребление всех видов ресурсов, кроме одного — процессорного времени. Оно распределяется операционной системой между другими единицами работы — потоками, которые и получили свое название благодаря тому, что они представляют собой последовательности (потоки выполнения) команд.
Создание потоков требует от ОС меньших накладных расходов, чем процессов. В отличие от процессов, которые принадлежат разным, вообще говоря, конкурирующим приложениям, все потоки одного процесса всегда принадлежат одному приложению, поэтому ОС изолирует потоки в гораздо меньшей степени, нежели процессы в традиционной мультипрограммной системе. Все потоки одного процесса используют общие файлы, таймеры, устройства, одну и ту же область оперативной памяти, одно и то же адресное пространство. Чтобы организовать взаимодействие и обмен данными, потокам вовсе не требуется обращаться к ОС, им достаточно использовать общую память — один поток записывает данные, а др. читает их.
Наибольший эффект от введения многопоточной обработки достигается в мультипроцессорных системах, в которых потоки, в том числе и принадлежащие одному процессу, могут выполняться на разных процессорах действительно параллельно (а не псевдопараллельно).
Планирование и диспетчеризация потоков
На протяжении существования процесса выполнение его потоков может быть многократно прервано и продолжено. Работа по определению того, в какой момент необходимо прервать выполнение текущего активного потока и какому потоку предоставить возможность выполняться, называется планированием.
Сущ-ет мно-во различных алг-тмов планирования потоков, по-своему решающих каждую из приведенных выше задач.
В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), то есть решения принимаются во время работы системы на основе анализа текущей ситуации.
Динамические планировщики могут гибко приспосабливаться к изменяющейся ситуации и не используют никаких предположений о мультипрограммной смеси.
Планировщик наз-ся статическим (или предварительным планировщиком), если он принимает решения о планировании не во время работы системы, а заранее (off-line).
Диспетчеризация заключается в реализации найденного в результате планирования решения, то есть в переключении процессора с одного потока на другой. Прежде чем прервать выполнение потока, ОС запоминает его контекст. Контекст отражает, во-первых, состояние аппаратуры компьютера в момент прерывания потока: значение счетчика команд, содержимое РОН, режим работы процессора. Во-вторых, контекст включает параметры операционной среды, а именно ссылки на открытые файлы, данные о незавершенных операциях ввода-вывода и т. д.
Вытесняющие и невытесняющие алг-мы планирован.
Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того.
Вытесняющие (preemptive) алгоритмы — это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается операционной системой, а не активной задачей.
66.(СПО1).Управление памятью. Алгоритмы распределения памяти. Свопинг и виртуальная память.
Память является ресурсом, требующим управления со стороны мультипрограммной ОС. Особая роль памяти объясняется тем, что процессор может выполнять инструкции только в том случае, если они находятся в памяти. Память распределяется как между модулями прикладных программ, так и между модулями самой ОС.
Ф-циями ОС по управлению памятью в мультипрограммной системе являются: отслеживание свободной и занятой памяти; выделение памяти процессам и освобождение памяти по завершении процессов; вытеснение кодов и данных процессов из оперативной памяти на диск, когда размеры основной памяти не достаточны для размещения в ней всех процессов, и возвращение их в оперативную память, когда в ней освобождается место; Защита памяти —задача ОС, к-ая состоит в том, чтобы не позволить выполняемому процессу записывать или читать данные из памяти, назначенной другому процессу.
Алгоритмы распределения памяти разделены на два класса: алгоритмы, в которых используется перемещение сегментов процессов между оперативной памятью и диском, и алгоритмы, в которых внешняя память не привлекается (страничное, сегментное, сегментно-страничное распределение).
Распределение памяти фиксированными разделами - Простейший способ управления оперативной памятью состоит в том, что память разбивается на несколько областей фиксированной величины, называемых разделами. Такое разбиение может быть выполнено вручную оператором во время старта системы или во время ее установки. После этого границы разделов не изменяются.
Распределение памяти динамическими разделами - Каждому вновь поступающему на выполнение приложению на этапе создания процесса выделяется вся необходимая ему память (если достаточный объем памяти отсутствует, то приложение не принимается на выполнение и процесс для него не создается). После завершения процесса память освобождается, и на это место может быть загружен другой процесс.
Перемещаемые разделы - В дополнение к функциям, которые выполняет ОС при распределении памяти динамическими разделами, в данном случае она должна еще время от времени копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется сжатием. Сжатие может выполняться либо при каждом завершении процесса, либо только тогда, когда для вновь создаваемого процесса нет свободного раздела достаточного размера. В первом случае требуется меньше вычислительной работы при корректировке таблиц свободных и занятых областей, а во втором — реже выполняется процедура сжатия.
Свопинг и виртуальная память
Виртуализация памяти может быть осуществлена на основе двух различных подходов:
Подкачке свойственна избыточность: когда ОС решает активизировать процесс, для его выполнения, как правило, не требуется загружать в оперативную память все его сегменты полностью — достаточно загрузить небольшую часть кодового сегмента с подлежащей выполнению инструкцией и частью сегментов Данных, с которыми работает эта инструкция, а также отвести место под сегмент стека.
Системы, поддерживающие свопинг, имеют очень существенный недостаток: они не способны загрузить для выполнения процесс, виртуальное адресное пространство которого превышает имеющуюся в наличии свободную память.
В настоящее время все множество реализаций виртуальной памяти может быть представлено тремя классами:
1)Страничная виртуальная память, 2)Сегментная виртуальная память, 3)Сегментно-страничная.
67.(СПО1).Физич. организация NTFS.Стр-ра файлов NTFS.
Файловая система NTFS была разработана в качестве основной файловой системы для ОС Windows NT. Основными отличительными свой ствами NTFS являются:поддержка больших файлов и больших дисков объемом до 264 байт;восстанавливаемость после сбоев и отказов программ и аппаратуры управле ния дисками;высокая скорость операций, в том числе и для больших дисков;низкий уровень фрагментации, в том числе и для больших дисков;гибкая структура, допускающая развитие за счет добавления новых типов за писей и атрибутов файлов с сохранением совместимости с предыдущими вер сиями ФС;устойчивость к отказам дисковых накопителей;поддержка длинных символьных имен;контроль доступа к каталогам и отдельным файлам.
Структура файлов NTFS
Каждый файл и каталог на томе NTFS состоит из набора атрибутов. Важно отме тить, что имя файла и его данные также рассматриваются как атрибуты файла, то есть в трактовке NTFS кроме атрибутов у файла нет никаких других компо нентов.
Каждый атрибут файла NTFS состоит из полей: тип атрибута, длина атрибута, значение и, возможно, имя атрибута. Тип атрибута, длина и имя обра зуют заголовок атрибута.
Имеется системный набор атрибутов, определяемых структурой тома NTFS. Сис темные атрибуты имеют фиксированные имена и коды их типа, а также опреде ленный формат.
Системный набор включает следующие атрибуты:
Файлы NTFS в зависимости от способа размещения делятся на небольшие, боль шие, очень большие и сверхбольшие.
68.(СПО1).СтандартыPOSIXS, POSIXS 1b, 1с. Файловый API.
Цель подхода POSIX состоит в том, чтобы обеспечить возможность решения проблемы переносимости прикладных программ между различными компьютерными платформами на основе стандартизации прикладных программных интерфейсов (API) операционных систем (ОС).
В более полной трактовке целью разработки системы стандартов POSIX OSE являлось обеспечение следующих возможностей (называемых также свойствами открытости) для разрабатываемых информационных систем:
Следование этим методическим рекомендациям позволяет решить следующие главные задачи:
В POSIX имеется несколько подгрупп, в частности, POSIX.1, POSIX .1b и POSIX.1c. POSIX.1 предлагает стандарт на базовый интерфейс прикладного программирования ОС, в котором определяются API для манипулирования файлами и процессами. Комитет POSIX.1b предлагает набор стандартных API для интерфейса ОС реального времени, включающий APIмежпроцессного взаимодействия. Наконец, стандарт POSIX.1c определяет интерфейс многопоточного программирования.
Хотя в основе работа комитетов POSIX строится на использовании ОС UNIX, предлагаемые ими стандарты предназначены для некой обобщенной ОС, которая вовсе не обязательно д.б. UNIX. Так ОС VMS (DEC), OS/2 (IBM), WindowsNT (Microsoft) совместимы с POSIX. Большинство ОС, в т.ч. и UNIX, имеют кроме стандартных и свои собственные API.
API:
1) int open(char* path_name,intaccess_mode, mode_t permission). Открытие файла.
2) int create(char* path_name, mode_t mode). Создание файла
3) sssize_t write(intfdesc, void* buf, size_t size). Запись в файл.
4) int close (intfdesc). Закрытие файла.
5) int rename (const char* , const char*). Переименование.
6)int mkdir(const char* name, mode_t mode). Созданиедиректории.
7) DIR* opendir(…) – открытиекаталога.
8) intclosedir(…) – закрытие.
9) voidrewinddir(…) – указатель чтения в начало файла каталога и др.
69.(СПО1).Объекты синхронизации и межпроцессного взаимодействия.
Традиционно считается, что основными способами межпроцессного обмена являются каналы и разделяемая память (рис. 1), которые базируются на соответствующих объектах ядра.
В случае разделяемой памяти два или более процессов совместно используют сегмент памяти. Каналы предполагают созданные средствами операционной системы линии связи. Двумя основными моделями передачи данных по каналу являются поток ввода-вывода и сообщения. Работа с объектами синхронизации
Wait-функции позволяют потоку в любой момент приостановиться и ждать освобож дения какого-либо объекта ядра.
События - самая примитивная разновидность объектов ядра. Они содержат счетчик числа пользователей (как и все объекты ядра) и две булевы переменные: одна сооб щает тип данного объекта-события, другая — его состояние (свободен или занят).
События просто уведомляют об окончании какой-либо операции. Объекты-собы тия бывают двух типов: со сбросом вручную (manual-reset events) и с автосбросом (auto-reset events). Первые позволяют возобновлять выполнение сразу нескольких ждущих потоков, вторые — только одного.
Объекты-события обычно используют в том случае, когда какой-то поток выпол няет инициализацию, а затем сигнализирует другому потоку, что тот может продол жить работу. Инициализирующий поток переводит объект "событие» в занятое состо яние и приступает к своим операциям. Закончив, он сбрасывает событие в свободное состояние. Тогда другой поток, который ждал перехода события в свободное состоя ние, пробуждается и вновь становится планируемым.
Ожидаемые таймеры (waitahle timers) ~ это объекты ядра, которые самостоятельно переходят в свободное состояние в определенное время или через регулярные про межутки времени. Объекты ядра «семафор» используются для учета ресурсов Как и все объекты ядра, они содержат счетчик числа пользователей, но, кроме того, поддерживают два 32 битных значения со знаком: одно определяет максимальное число ресурсов (контро лируемое семафором), другое используется как счетчик текущего числа ресурсов
Для семафоров определены следующие правила:
Не путайте счетчик текущего числа ресурсов со счетчиком числа пользователей объекта-семафора
мьютекс-семaфoр или прoстo мьютекс (mutex). Мьютекс синхрoнизирует дoступ к ресурсу тaким oбрaзoм, чтo oдин и тoлькo oдин пoтoк или прoцесс мoжет oбрaщaться к ресурсу в кaждый мoмент времени. Пoсуществу, мьютекс — этo специaльнaя версия стaндaртнoгo семaфoрa.Для мьютексов определены следующие правила:
70.(СПО2).Классификация языков и грамматик. Четыре типа грамматик по Хомскому. Классификация языков.
Формальные грамматики классифицируются по структуре их правил.
Тип О: грамматики с фразовой структурой
На структуру их правил не накладывается никаких ограничений: для граммати ки вида G(VT,VN,P,S), V = VNVT правила имеют вид: α→β, где αV+, βV*.
Это самый общий тип грамматик. В него подпадают все без исключения фор мальные грамматики, но часть из них, может быть также отне сена и к другим классификационным типам. Грамматики, которые относятся только к типу 0 и не могут быть отнесены к другим типам, являются самыми сложными по структуре.
Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики
В этот тип входят два основных класса грамматик.
Контекстно-зависимые грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: α1Aα2→α1βα2, где α1,α2V*, AVN, βV+.
Неукорачивающие грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: α→β, где αβV+, |β|≥|α|.
Структура правил КЗ-грамматик такова, что при построении предложений за данного ими языка один и тот же нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от того контекста, в котором он встречается. Цепочки α1 и α2 в правилах грамматики обозначают контекст (α1 — левый контекст, а α2 — правый контекст).
Неукорачивающие грамматики имеют такую структуру правил, что при построе нии предложений языка, заданного грамматикой, любая цепочка символов мо жет быть заменена на цепочку символов не меньшей длины.
Тип 2: контекстно-свободные (КС) грамматики
Контекстно-свободные (КС) грамматики G(VT,VN,P,S), V = VNVT имеют правила вида: А→β, где AVN, βV+. Такие грамматики также иногда называют неукорачивающими контекстно-свободными (ИКС) грамматиками. Существует также почти эквивалентный им класс грамматик — укорачивающие контекстно-свободные (УКС) грамматики.Разница между этими двумя классами грамматик лишь в том, что в УКС-грамматиках в правой части правил может присутствовать пустая це почка (), а в НКС-грамматиках — нет.
Тип 3: регулярные грамматики
К типу регулярных относятся два эквивалентных класса грамматик: леволинейные и праволинейные.
Регулярные грамматики используются при описании простейших конструкций языков программирования: идентификаторов, констант, строк, комментариев и т. д.
Тип О: языки с фразовой структурой
Это самые сложные языки. Для распознавания цепочек таких языков требуются вычис лители, равномощные машине Тьюринга. Поэтому можно сказать, что если язык относится к типу 0, то для него невозможно построить компилятор, который гарантированно выполнял бы разбор предложений языка за ограниченное время на основе ограниченных вычислительных ресурсов.
Тип 1: контекстно-зависимые (КЗ) языки
Языки и грамматики, относящиеся к типу 1, применяются в анализе и переводе текстов на естественных языках. Распознаватели, построенные на их основе, по зволяют анализировать тексты с учетом контекстной зависимости в предложе ниях входного языка.
Тип 2: контекстно-свободные (КС) языки
КС-языки лежат в основе синтаксических конструкций большинства современ ных языков программирования, на их основе функционируют некоторые сложные командные процессоры, допускающие управляющие команды цикла и условия. Эти обстоятельства определяют распространенность данного класса языков.
В общем случае время на распознавание предложений языка, относящегося к типу 1, полиноминально зависит от длины исходной цепочки символов.
Тип 3: регулярные языки
Регулярные языки — самый простой тип языков. Наверное, поэтому они явля ются самым распространенным и широко используемым типом языков в облас ти вычислительных систем. Время на распознавание предложений регулярного языка линейно зависит от длины исходной цепочки символов.
71.(СПО2).Цепочки вывода. Сентенциальная форма. Левосторонний и правосторонний выводы. Однозначные и неоднозначные грамматики. Эквивалентность и преобразование грамматик.
Суть рекурсивной выводимости заключается в том, что цепочка β выводима из цепочки α, если αβ или же если можно построить последовательность непосредственно выводимых цепочек от α к β следующего вида: α1…i…nβ, n≥1 этой последовательности каждая последую щая цепочка , непосредственно выводима из предыдущей цепочки i-1.
Такая последовательность непосредственно выводимых цепочек называется вы водом или цепочкой вывода. Каждый переход от одной непосредственно выводи мой цепочки к следующей в цепочке вывода называется шагом вывода.
Вывод называется законченным, если цепочка р, полученная в результате вывода, пус тая или содержит только терминальные символы грамматики G(VT,VN,P,S): βVT*. Цепочка β, полученная в результате законченного вывода, называется конечной цепочкой вывода.
Алфавитом языка L(G) будет множество терминальных символов грамматики VT, поскольку все конечные сентенциаль ные формы грамматики — это цепочки над алфавитом VT.
Вывод называется левосторонним, если в нем на каждом шаге вывода правило грамматики применяется всегда к крайнему левому нетерминальному символу в цепочке.
Ввывод называется правосторонним, если в нем на каждом шаге вы вода правило грамматики применяется всегда к крайнему правому нетерминаль ному символу в цепочке.
Для грамматик типов 2 и 3 (КС-грамматик и регулярных грамматик) для любой сентенциальной формы всегда можно построить левосторонний или правосто ронний выводы. Для грамматик других типов это не всегда возможно, так как по структуре их правил не всегда можно выполнить замену крайнего левого или крайнего правого нетерминального символа в цепочке.
Рассмотрим некоторую грамматику G({+,-,*,/,(,),a,b},{S},P,S):
Р: S → S+S | S-S | S*S | S/S | (S) | а | b
Представленная грамматика определяет язык арифметических выра жений с четырьмя основными операциями (сложение, вычитание, умножение и деление) и скобками над операндами а и b. Пример: служить: a*b+a, a*(a+b).
Возьмем цепочку а*b+а и построим для нее левосторонний вывод. Получитсядваварианта:
S S+S S*S+S a*S+S a*b+S a*b+a
S S*S a*S a*S+S a*b+S a*b+a
Такая ситуация называется неоднозначностью в грамматике.
Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить единственный левосторонний (и единственный правосторонний) вывод. В противном случае грамматика называется неоднозначной.
Чтобы убедиться в том, что некоторая грамматика не является однозначной, согласно определению достаточно найти в заданном ею языке хотя бы одну цепочку, которая бы допускала более чем один левосторон ний или правосторонний вывод. Но если такая цепочка не найдена, мы не можем утверждать, что данная грамматика является однозначной.
Если грамматика все же является неоднозначной, то необходимо преобразовать ее в однозначный вид. Например, для рассмотрен ной выше неоднозначной грамматики арифметических выражений над операн дами а и b существует эквивалентная ей однозначная грамматика следующего вида
G1 ({+,-,*,/,(,),а,b},{5,Т,E},P',S):
Р':
S → S+T | S-T | Т
Т → Т*Е | Т/Е | Е
Е → (S) | а | b
В этой грамматике для рассмотренной выше цепочки символов языка a*b+a воз можен только один левосторонний вывод:
S S+T Т+Т Т*Е+Т Е*Е+Т а*Е+Т а*b+Т а*b+Е а*
72.(СПО2).Распознаватели. Задача разбора. Общая схема распознавателя. Виды распознавателей. Классификация распознавателей по типам языков.
Распознаватель — это специальный алгоритм, который позво ляет определить принадлежность цепочки символов некоторому языку. Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ, принадлежит ли она заданному языку или нет.
В общем виде распознаватель приведен на рисунке.
Распознаватель состоит из следующих основных компо нентов:
-ленты, содержащей исходную цепочку входных символов, и считывающей го ловки, обозревающей очередной символ в этой цепочке;
-устройства управления (УУ), которое координирует работу распознавателя, имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации);
-внешней (рабочей) памяти, которая может хранить некоторую информацию в процессе работы распознавателя и в отличие от памяти УУ может иметь не ограниченный объем.
В процессе своей работы распознаватель может выполнять некоторые элемен тарные операции, такие как чтение очередного символа из входной цепочки, сдвиг входной цепочки на заданное кол-во символов, доступ к рабочей памяти для чтения или записи информации, преобразование информации в памяти, изменение состояния УУ. Какие конкретно операции должны выполняться в процессе работы распознавателя, определяется в УУ.
Распознаватель работает по тактам. В начале такта, как правило, счи тывается очередной символ из входной цепочки, и в зависимости от этого симво ла УУ определяет, какие действия необходимо выполнить. В начале каждого такта состояние распознавателя определяется его конфигурацией. В процессе работы конфигура ция распознавателя меняется.
По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.
- Односторонние распознаватели допускают перемещение считывающей головки по ленте входных символов только в одном направлении.
- Двусторонние распознаватели допускают, что считывающая головка может пе ремещаться относительно ленты входных символов в обоих направлениях.
По видам устройства управления распознаватели бывают детерминированные и недетерминированные.
Распознаватель называется детерминированным в том случае, если для каждой допустимой конфигурации распознавателя, которая возникла на некотором шаге его работы, существует единственно возможная конфигурация, в которую распо знаватель перейдет на следующем шаге работы.
В противном случае распознаватель называется недетерминированным.
По видам внешней памяти распознаватели бывают следующих типов:
Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга — недетерминированный двусторонний автомат, имею щий неограниченную внешнюю память.
Для контекстно-зависимых языков (тип 1) распознавателями являются двусто ронние недетерминированные автоматы с линейно ограниченной внешней памя тью.
Для контекстно-свободных языков (тип 2) распознавателями являются односто ронние недетерминированные автоматы с магазинной (стековой) внешней па мятью — МП-автоматы.
Для регулярных языков (тип 3) распознавателями являются односторонние неде терминированные автоматы без внешней памяти — конечные автоматы (КА). Это очень простой тип распознавателя, который всегда предполагает линейную зависимость времени на разбор входной цепочки от ее длины.
73.(СПО2).Регулярные языки и грамматики. Леволинейные и праволинейные грамматики. Автоматные грамматики. Алгоритм преобразования регулярной грамматики к автоматному виду.
К регулярным относятся два типа грамматик: леволинейные и праволинейные.
Леволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: А→В или А→, где A,BVN, VT* .
В свою очередь, праволинейные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила также двух видов: А→В или А→, где A,BVN, VT*.
Для любого регулярного языка, заданного праволинейной грамматикой, может быть построена леволинейная грамматика, определяющая эквивалентный язык; и наоборот.
Разница между леволинейными и праволинейными грамматиками заключается в основном в том, в каком порядке строятся предложения языка: слева направо для леволинейных, либо справа налево для праволинейных.
Среди всех регулярных грамматик можно выделить отдельный класс — автомат ные грамматики. Они также могут быть леволинейными и праволинейными.
Леволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: A→Bt или A→t, где A.BVN, tVT.
Праволинейные автоматные грамматики G(VT,VN,P,S), V = VNVT могут иметь правила двух видов: A→tB или A→t, где A,BVN, tVT.
Разница между автоматными грамматиками и обычными регулярными грам матиками заключается в следующем: там, где в правилах обычных регулярных грамматик может присутствовать цепочка терминальных символов, в автомат ных грамматиках может присутствовать только один терминальный символ. Лю бая автоматная грамматика является регулярной, но не наоборот.
Имеется регулярная грамматика G(VT,VN,P,S), необходимо преобразовать ее в почти эквивалентную автоматную грамматику G'(VT,VN',P',S'). Для опреде ленности будем рассматривать леволинейные грамматики.
Шаг 1. Все нетерминальные символы из множества VN грамматики G перено сятся во множество VN' грамматики G'.
Шаг 2. Необходимо просматривать все множество правил Р грамматики G. Если встречаются правила вида А→Ва1, A,BVN, a1VT или вида А→a1, AVN, , то они переносятся во множество Р' правил грамматики G' без изменений.
Если встречаются правила вида А→Вa1a2…an, n>1, A.BVN, n>i>0: aiVT, то во множество нетерминальных символов VN' грамматики G' добавляются символы A1,A2,...,An-i, а во множество правил Р' грамматики G' добавляются правила:
A→An-1An; An-1→ An-2 an-1; …; A2→A1a2; A1→Ba1
Если встречаются правила вида А→a1a2…an, n >1, AVN, n > i > 0: aiVT, то во множество нетерминальных символов VN' грамматики G' добавляются символы A1,A2,...,An-1, а во множество правил Р' грамматики G' добавляются правила:
A→An-1an ; An-1→ An-2 an-1; …; A2→A1a2; A1→a1
Если встречаются правила вида А→В или вида А→ то они переносятся во мно жество правил Р' грамматики G' без изменений.
Шаг 3. Просматривается множество правил Р' грамматики G'. В нем ищутся пра вила вида А→В или вида А→.
Если находится правило вида А→В, то просматривается множество правил Р' грамматики G'. Если в нем присутствует правила вида В→С, В→Са, В→ или В→, то в него добавляются правила вида А→С, А→Са, А→a и А→, соответст венно, VA,B,CVN', aVT (при этом следует учитывать, что в грамматике не должно быть совпадающих правил, и если какое-то правило уже присутствует в грамматике G', то повторно его туда добавлять не следует). Правило А→В уда ляется из множества правил Р'.
Правило А→. удаляется из множества правил Р'.
Шаг 4. Если на шаге 3 было найдено хотя бы одно правило вида А→В или А→. во множестве правил Р' грамматики G', то надо повторить шаг 3, иначе перейти к шагу 5.
Шаг 5. Целевым символом S' грамматики G' становится символ S. Шаги 3 и 4 алгоритма в принципе можно не выполнять, если грамматика не со держит правил вида А→В (такие правила называются цепными) или вида А→ (такие правила называются -правилами).
74.(СПО2).Конечные автоматы. Определение конечного автомата. Детерминированные и недетерминированные конечные автоматы. Преобразование конечного автомата к детерминированному виду.
Конечным автоматом (КА) называют пятерку следующего вида: M(Q,V,,q0,F),где: Q — конечное множество состояний автомата; V — конечное множество допустимых входных символов (алфавит автомата); — функция переходов, отображающая V*Q. (декартово произведение мно жеств) в множество подмножеств : R(Q), то есть (a,q) = R, aV, qQ, RQ; q0 — начальное состояние автомата Q, q0Q; F — непустое множество конечных состояний автомата, FQ, F≠.
КА называют полностью определенным, если в каждом его состоянии сущест вует функция перехода для всех возможных входных символов, то есть aV, qQ(a,q) = R, RQ.
Работа конечного автомата представляет собой последовательность шагов. На каждом шаге работы автомат находится в одном из своих состояний Q, на следующем шаге он может перейти в другое состоя ние или остаться в текущем состоянии. То, в какое состояние автомат перейдет на следующем шаге работы, определяет функция переходов . Она зависит не только от текущего состояния, но и от символа из алфавита V, поданного на вход автомата. Когда функция перехода допускает несколько следующих состояний автомата, то КА может перейти в любое из этих состояний. В начале работы ав томат всегда находится в начальном состоянии q0. Работа КА продолжается до тех пор, пока на его вход поступают символы из входной цепочки V+.
Граф переходов КА — это направленный помеченный граф, с символами состоя ний КА в вершинах, в котором есть дуга (p,q) p.qQ, помеченная символом aV, если в КА определена (а, р) и q(a, p).
Рассмотрим конечный автомат: M({H,A,B,S},{a,b},,H,{S}); : (H,b) = В, (В, а) = А, (A,b) = {B,S}. Ниже на рис. 5.1 приведен пример графа состояний для этого КА.
Конечный автомат M(Q,V,,q0,F) называют детерминированным конечным авто матом (ДКА), если в каждом из его состояний для любого входного символа функ ция перехода содержит не более одного состояния: aV, VqQ: либо (a,q) = {r}, rQ либо (a,q) = .
В противном случае конечный автомат называют недетерминированным.
ДКА может быть задан в виде пятерки: M(QV,β,q0,F),где: Q — конечное множество состояний автомата; V — конечное множество до пустимых входных символов; 8 — функция переходов, отображающая V*Q в множество Q: (a,q) = г, aV, q,rQ; q0 — начальное состояние автомата Q, q0Q; F — непустое множество конечных состояний автомата, FQ, F≠.
Если функция переходов ДКА определена для каждого состояния автомата, то автомат называется полностью определенным ДКА: aV, qQ: либо (a,q) = r, rQ.
Доказано, что для любого КА можно построить эквивалентный ему ДКА. По этому используемый произвольный КА стремятся преобразовать в ДКА.
Алгоритм преобразования произвольного КА M(Q,V,,q0,F) в эквивалентный ему ДКА M'(Q',V,',q'0,F') заключается в следующем: 1. Множество состояний Q' автомата М' строится из комбинаций всех состоя ний множества Q. автомата М. Если q1,q2,...,qn, n > 0 — состояния автомата М, 0 < i < n q1Q, то всего будет 2n-1 состояний автомата М'. Обозначим их так: [q1,q2,...,qm]. 0<mn. 2. Функция переходов ' автомата М' строится так: '(a,[q1,q2,...,qm]) = [r1,r2,...,rk], где 0<im0<jk так, что (a,qi) = rj; 3. Обозначим q'0 = [q0]; 4. Пусть f1,f2,...,fl, l > 0 — конечные состояния автомата М, O < i < l flF, тогда множество конечных состояний F' автомата М' строится из всех состояний, имеющих вид [...,fl...], flF.
После построения из нового ДКА необходимо удалить все недостижимые со стояния.
Для работы алгоритма удаления недостижимых состояний используются два множества: множество достижимых состояний R и множество текущих актив ных состояний на каждом шаге алгоритма Р. Рассмотрим работу алго ритма по шагам:
1. R:={q0}; i:=0; P0:={q0};
2. Рi+1:=0;
3. aV, qP,: Pi+1:=Pi+1(a,q);
4. Если Рi+1-R = , то выполнение алгоритма закончено, иначе R:=RPi+1, i:=i+1 и перейти к шагу 3.
75.(СПО2).Контекстно-свободные языки. Распознаватели КС-языков. Автоматы с магазинной памятью. Определение МП-автомата. Классы КС-языков и грамматик.
Контекстно-свободными (КС) называются языки, определяемые грамматиками типа G(VT,VN,P,S), в которых правила Р имеют вид: А→β, где AVN и βV*, V-VTVN.
Распознавателями КС-языков служат автоматы с магазинной памятью (МП-ав томаты). В общем виде МП-автомат можно определить следующим образом: R(Q,V,Z,,q0,z0,F), где: Q — множество состояний автомата; V — алфавит входных символов автома та; Z — специальный конечный алфавит магазинных символов автомата (обычно он включает в себя алфавиты терминальных и нетерминальных символов грам матики), VZ; — функция переходов автомата, которая отображает множество Qx(V{})xZ на конечное множество подмножеств P(QxZ*); q0Q — начальное состояние автомата; z0Z — начальный символ магазина; FQ, — множество ко нечных состояний.
МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные «магазинные» символы. Переход из одного состояния в дру гое зависит не только от входного символа, но и от одного или нескольких верх них символов стека. Таким образом, конфигурация автомата определяется тремя параметрами состояния текущим символом входной цепочки и содержимым стека. МП-автомат на рисунке:
Конфигурация МП-автомата описывается в виде тройки (q,α,)QxV*xZ*, кото рая определяет текущее состояние автомата q, цепочку еще непрочитанных символов α на входе автомата и содержимое магазина (стека) . Вместо α в конфигурации можно указать пару (β,n), где βV* — вся цепочка входных символов, nN{0}, n 0 — положение считывающего указателя в цепочке. Тогда один такт работы автомата можно описать в виде (q,aα,z) + (q',α,), если (q’,)(q,a,z), где q,q'Q, aV{}, V*, zZ{}, ,Z*. При выполнении акта (перехода) из стека удаляется верхний символ, соответствующий условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при кото рых входной символ игнорируется. Эти переходы (такты) называются -переходами (-тактами).
Существует класс грамматик, основанный на выборе одной альтернативы из множества возможных на основе нескольких очередных симво лов в цепочке. Это так называемые LL(k)-грамматики. Грамматика обладает свойством LL(k), k > 0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего поло жения считывающей головки во входной цепочке символов.
Грамматика называется LL(k)-грамматикой, если она обладает свойством LL(k) для некоторого k > О.
Первая литера «L» означает, что входная цепочка символов читается в направлении слева направо. Вторая литера «L» означает, что при работе распознавателя используется левосторонний вывод. Вместо «k» в названии класса грамматики стоит некоторое число, которое показывает, сколь ко символов надо рассмотреть, чтобы однозначно выбрать одну из множества аль тернатив.
Для LL(k)- грамматики при k>l совсем не обязательно, чтобы псе правые части правил грамматики для каждого нетерминального символа начинались с k различ ных терминальных символов.
Для LL(k)-грамматики, очевидно, для каждого нетерминального символа не мо жет быть двух правил, начинающихся с одного и того же терминального симво ла.
76.(СПО2).Класс LL(k)-грамматик. Принципы построения распознавателей для LL(k)-грамматик. Алгоритм разбора для LL(1)-грамматик.
Для построения распознавателей LL(к)-грамматик используются два важных множества, определяемые следующим образом: FIRST(k,) — множество терминальных цепочек, выводимых из (VTVN)*, укороченных до k символов; FOLLOW(k.A) — множество укороченных до k символов терминальных це почек, которые могут следовать непосредственно за АVN в цепочках вывода.
Формально эти два множества могут быть определены следующим образом:
FIRST(k,) - { VT* | либо ||_k и =>*, либо ||>k и =>*х, x (VTVN)'}, (VTVN)'. k>0.
FOLLOW(k,A) - (VT* | S=>*AиFIRST(,k), VT*), AVN, k>0.
Доказано, что грамматика G(VT,VN,P,S) является LL(k)-грамматикой тогда и только тогда, когда выполняется следующее условие: АР и Аg Р (): FIRST(k, ) FIRST(k, ) - для всех цепочек и таких, что S =>* A.
Иначе говоря, если существуют две цепочки вывода:
S =>* A =>z =>*
S =>* A =>t =>*
то из условия FIRST(k, ) - FIRST(k, ) следует, что z = t.
На основе этих двух множеств строится алгоритм работы распознавателя для LL(к)-грамматик, который представляет собой k-предсказывающий алгоритм для МП-автомата, заданного так: R({q},VT,Z,,q,S,{q}), где Z = VTVN, а S - целевой символ грамматики G. Функция переходов автомата строится на основе управ ляющей таблицы М, которая отображает множество (Z{.}) x VT*k на множест во.
Конфигурацию распознавателя можно отобразить в виде конфигурации МП-автомата с дополнением цепочки, в которую помещаются номера применен ных правил. Поскольку автомат имеет только одно состояние, его в конфигура ции можно не указывать. Если считать, что X — это символ на верхушке стека автомата, — непрочитанная автоматом часть входной цепочки символов, а = FIRST(k, ), то работу алгоритма распознавателя можно представить сле дующим образом:
(, X, ) +(, , i), Z*, если М(Х, ) = (,i);
(, X, ) + (1, , ), если X = аVT и = а', М(а, ) = «выброс»; (,.,) — завершение работы, при этом М(,) = «допуск»; иначе — «ошибка».
Цепочка = FIRST(k,) носит в работе автомата название «аванцепочка».
Для LL(1)- грамматик алгоритм работы распознавателя предельно прост. Он за ключается всего в двух условиях, проверяемых на шаге выбора альтернати вы. Исходными данными для этих условий являются символ aVT, обозреваемый считывающей головкой МП-автомата (текущий символ входной цепочки), и символ AVN, находящийся на верхушке стека автомата.
Эти условия можно сформулировать так:
Если ни одно из этих условий не выполняется, то цепочка не принадлежит заданному языку и МП-автомат не принимает ее.
Работа автомата на шаге «выброса» остается без изменений.
Кроме того, чтобы убедиться, является ли заданная грамматика G(VT,VN,P,S) LL(1)-грамматикой, необходимо и достаточно проверить следующее условие: для каждого символа AVN, для которого в грамматике существует более одного правила вида А1||2|...|n, должно выполняться требование
FIRST(l, i,FOLLOW(l,A)) FIRST(l, jFOLLOW(l,A)) =
ij, n i 0 n j 0.
Очевидно, что если для символа AVN отсутствует правило вида А, то соглас но этому требованию все множества FIRST(1,1), FIRST(l, 2), ..., FIRST(l, n) должны попарно не пересекаться, если же присутствует правило А, то они не должны также пересекаться со множеством FOLLOW(l,A). Для того чтобы запрограммировать работу МП-автомата, выполняющего разбор входных цепочек символов языка, заданного LL(1)-грамматикой, надо научить ся строить множества символов FIRST(l,x) и FOLLOW(1,A). Для множества FIRST(l,x) все очевидно, если цепочка х начинается с терминального симво ла, если же она начинается с нетерминального символа В (х = By, x (VTVN)*, y (VTVN)'), то FIRST(l.x) = FIRST(1,B). Следовательно, для LL(1)-грамматик остается только найти алгоритм построения множеств FIRST(1,B) и FOLLOW(l,A) для всех нетерминальных символов A,BVN.
Исходными данными для этих алгоритмов служат правила грамматики.
77.(СПО2).Инструментальные средства для построения компиляторов. Лексический анализ. Регулярные выражения в Lex-правилах. Операторы регулярных выражений. Оператор выделения классов символов. Повторители. Операторы выбора.
Рассмотрим два инструментальных средства: Lex - предназначен для реализации сканера, Yacc - для построения парсера. Они компилируют описания сканера и парсера соответственно, записанные на специальных языках, в C-программы, реализующие эти компоненты компилятора.
Важная часть механизма разбора - лексический анализатор. Эта процедура, задаваемая пользователем, читает входной поток, выделяет низкоуровневые конструкции и передает их в качестве лексем процедуре разбора. Процедура лексического анализа распознает во входном потоке конструкции, являющиеся терминальными символами, процедура синтаксического разбора - конструкции, являющиеся нетерминальными символами. Терминальные символы называются лексемами.
Лексический анализ
Пользователь должен определить лексический анализатор, который читает входной поток и передает лексемы процедуре разбора. Лексический анализатор - это целочисленная функция с именем yylex. Функция возвращает номер_лексемы.
Спецификации лексических анализаторов используют не грамматические правила, а регулярные выражения.
Регулярные выражения в Lex-правилах
Регулярные выражения определяют лексему. Регулярное выражение может содержать символы латинского и русского алфавитов в верхнем и нижнем регистрах, другие символы (цифры, знаки препинания и т.д.) и символы-операторы.
Операторы регулярных выражений
Операторы обозначаются символами-операторами, к ним относятся:
\ ^ ? * + | $ / % [ ] { } ( ) <>
Каждый из этих символов или пар скобок в регулярном выражении играет роль оператора. Если необходимо отменить специальное значение символа, обозначающего оператор, перед ним нужно поставить символ \ или указать его в двойных кавычках.
Например: abc+ - символ "+" - оператор; abc\+ - символ "+";
abc"+" - символ "+".
Оператор выделения классов символов
Регулярное выражение, состоящее из одного символа, принадлежащего определенному классу, описывается в квадратных скобках. [abc] означает либо символ "a", либо "b", либо символ "c";
Знак - используется для указания любого символа из лексикографически упорядоченной последовательности:
[A-z] означает любой латинский символ; [А-Я] любая прописная русская буква; [+-0-9]все цифры и знаки "+" и "-";
[^0-9A-Fa-f] что угодно кроме шестнадцатеричных цифр.
Повторители
Когда необходимо указать повторяемость вхождения символа в регулярном выражении, используют операторы-повторители * и +.
Оператор * означает любое (в том числе и 0) число вхождений символа или класса символов. Например:
abc* любое число вхождений цепочки "abc";
[A-z]* любое число вхождений любой латинской буквы;
[A-ZА-Яa-zа-я_0-9]* любое вхождение русских и латинских букв, знака подчеркивания и цифр.
Оператор + означает одно и более вхождений. Например:
[0-9]+ одно или более вхождений цифр;
abc+ одно или более вхождений цепочки abc;
[A-z]+ одно или более вхождений любой латинской буквы.
Нетерминал r следует произносить как "описатель регулярного выражения".
r: r? необязательное вхождение r
[A-Za-z][A-Za-z0-9]* последовательность букв или цифр, начинающаяся с буквы.
Операторы выбора
Оп-ры / | ? $ ^ управляют процессом выбора символов.
ab/cd "ab" учитывается только тогда, когда за ним следует "cd".
ab|cd или "ab", или "cd".
x? означает необязательный символ "x".
-?[0-9]+ выделит любое целое число с необязательным минусом впереди.
^x означает выбрать символ "x", если он является первым символом строки;
78.(СПО2).Инструментальные средства для построения компиляторов. Синтаксический анализ. Основные спецификации. Действия. Использование значений произвольных типов, алгоритм разбора. Алгоритм синтаксического разбора.
Yaccпредназначен для построения парсера (синтаксического анализатора). Он воспринимает описание контекстно-свободной грамматики языка в виде, близком форме Бэкуса-Наура (НФБН) и строит восходящий LALR(1) распознаватель для данного языка.
Yacc как средство синтаксического анализа
yacc предоставляет универсальные средства для структуризации исходных данных программ. Пользователь yacc'а готовит спецификацию, которая включает:
Множество правил, описывающих составные части исходных данных.
Действия, выполняемые при применении правила.
Определение или описание процедуры нижнего уровня, анализирующей исходные данные.
Затем yacc отображает спецификацию в функцию на языке C, обрабатывающую входной поток данных. Эта функция, которая называется процедурой разбора, выполняется, обращаясь к низкоуровневому сканеру исходных данных, который извлекает из входного потока лексемы. Лексемы сопоставляются с правилами, описывающими структуру входного текста (с грамматическими правилами).
Если правило оказывается подходящим, то выполняется ассоциированное с ним действие. Действие - это фрагмент программы на языке C. Действия могут возвращать значения, а также использовать значения, возвращаемые другими действиями.
Имена обозначают лексемы или нетерминальные символы. YACC требует, чтобы имена лексем были указаны явно. Хотя лексический анализатор можно включить в файл спецификаций, определение его в отдельном файле, вероятно, более соответствует принципам модульного проектирования. Подобно лексическому анализатору, в файл спецификаций могут быть также включены и другие подпрограммы. Таким образом, каждый файл спецификаций теоретически состоит из трех секций:
Секции отделяются двумя знаками процента %% (знак% используется в yacc-спецификациях как универсальный управляющий).
Действия
Действие - это произвольный оператор на языке C. Следовательно, в действии можно выполнять операции ввода/вывода, вызывать подпрограммы, изменять значения массивов и переменных. Действие задается одним или несколькими операторами в фигурных скобках, { и }.
Для организации взаимосвязи между действиями и процедурой разбора используется знак $ (доллар). Псевдопеременная $$ представляет значение, возвращаемое завершенным действием.
Внутреннее действие – это действие, запускаемое при применении дополнительного правила.
Пользователь может определить дополнительные переменные, чтобы использовать их в действиях. Описания и определения могут быть указаны в секции определений между последовательностями %{ и%}. Эти описания и определения являются глобальными, поэтому они доступны в действиях и могут быть сделаны доступными для лексического анализатора..
Yacc поддерживает значения типов, отличных от целочисленных, в том числе структуры. Кроме того, yaccотслеживает типы и вставляет соответствующие имена элементов объединений, в результате чего получается строго типизированная
yacc порождает алгоритм разбора, использующий конечный автомат со стеком. Кроме того, алгоритм разбора может прочесть и запомнить следующую входную лексему (которая называется предварительно просмотренной). Текущее состояние автомата всегда сохраняется на вершине стека. В алгоритме имеется всего четыре типа действий –
перенос(shift), свертка (reduce), успех (accept), ошибка.
Шаг работы алгоритма состоит в следующем:
Используя текущее состояние и, если нужно, предварительно просмотренную лексему, алгоритм выбирает очередное действие и выполняет его. В результате состояния могут быть помещены в стек или извлечены из него, предварительно просмотренная лексема может быть обработана, а может и нет.
79.(Сх-ка).Автоколебательный мультивибратор на логических элементах.
Принцип. схема автоколебат. муль т-ра, на ЛЭ И-НЕ.
Предположим, при включении питания в момент t1 ЛЭ DD1 оказался в состоянии лог. 1, т.е. Uвых1 (t1) = U1вых, а ЛЭ DD2 - в состоянии лог. нуля, т.е. Uвых2 (t1) = U0вых. Это вызовет зарядку С1 током, протекающим по цепи: выход ЛЭ DD1 --> Cl --> R2 --> корпус, и напр-ние на нем будет возрастать по з-ну (2.6)
где Uост - остаточное напр-ние на C1; τ1 - постоянная време ни цепи зарядки С1, определяемая τ1 = С1( R1 вых + R2), (2.7)
в к-ой R1 вых - вых. сопр-ние ЛЭ DD1, находящимся в лог. 1.
В момент t1 (начало зарядки) C1 представляет собой коротко-замкнутую цепь, поэтому напр-ние Uвых1 передается на вход ЛЭ DD2 прак тически без изменения, т.е. Uвх2 (t1) = U1вых, и на выходе DD2 поддержи вается лог. нуль. Низкий уровень напр-ния действует и на входах DD1.
По мере зарядки C1 напр-ние на нем увеличивается, что приводит к уменьшению напр-ния Uвх2 на входах DD2. При достижении напр-нием Uвх2 зн-ния Uвх2 = U1пор ЛЭ DD2 переключится в состояние лог. 1 (момент времени t1).
Уровень лог. 1 с выхода DD2 ч/з С2 передается на входы ЛЭ DD1 и переводит его в состояние лог. 0. Начнется разрядка С1 по цепи : левая обкладка С1 --> вых. сопр-ние DD1 (R вых) --> корпус --> диод VD2 --> правая обкладка С1. Постоян ная времени цепи разрядки определяется τразр С1 = С1( R0 вых + R д.пр), (2.9)
где R д.пр - сопр-ние диода VD2, смещенного в прямом направлении. Разрядка С1 будет происходить значительно быстрее, чем его зарядка.
Одновременно с разрядкой С1 начнется зарядка С2 током, протекающим по цепи: выход ЛЭ DD2 --> С2 -->R1 --> корпус
По мере зарядки С2 напр-ние на нем возрастает, а напр-ние на входах DD1 Uвх1 = U2вых - Uc2 уменьшается. При Uвх1 = U1пор (момент t3) напр-ние на С2 достигнет значения
Uc2(t3)= U2вых - U1пор (2.12)
и произойдет переключение ЛЭ DD1 в состояние логической 1.
Уровень логической 1, появившейся на выходе DD1, через разряженный конденсатор С1 передается на выходы ЛЭ DD2 и переводит его в состояние ло гического нуля. Начинается повторение вышеописанных процессов. При этом конденсатор С2 быстро разряжается по цепи: правая обкладка конденсатора С2 --> выходное сопротивление R0 вых открытого элемента DD1 --> кор пус --> VD1 --> левая обкладка С2 . Постоянная времени цепи разрядки
Tразр С2 = С2( R0 вых + R д.пр), значительно меньше, чем постоянная времени τ1 цепи зарядки С1, поэтому разрядка С2 (как и С1) никакого влияния на работу схемы не оказывает.
Недостатком схемы: невозможность генерации, если в момент подачи на нее напряжения питания оба ЛЭ DD1и DD2 примут одинаковые состояния. Такую ситуацию можно предотвратить, добавив к рассмотренной схеме еще два ЛЭ И-НЕ
80.(Сх-ка).Базовый логический элемент ЭСЛ.
Цифровые микросхемы ЭСЛ имеют сейчас наилучшее быстродействие. Это достигается благодаря исключению насыщенного режима работы тр-ров и уменьшением лог. перепада. Влияние лог. перепада напр-ний Uл на быстродействие поясняется так
где С -- паразитные емкости нагрузки;I зар -- ток заряда , t зар -- время перезаряда вышеуказанных емкостей при переключении ЛЭ.
Основа ЛЭ ЭСЛ - токовый переключатель (ТП), выполненный на основе дифференциального усилителя (рис. 21.1).
Управление ТП осущ-ется сигналами отриц. полярности, под воздействием к-ых проводящим оказывается либо плечо с VT1, либо плечо с VT2. Протекание тока ч/з то или иное плечо определяется уровнем Uвх, подаваемого на базу VT1, по отношению к уровню Uоп, подаваемого на базу VT2.
В базовых схемах ЛЭ ЭСЛ: Uоп=-1,3 В, U0= -1,7 В, U1= -0,9 В. Тогда Uл=0,8 В. Благодаря небольшому Uл можно использовать в качестве RК1 RК2 резисторы с малыми сопротивлениями, благодаря чему уменьшается время перезарядки нагрузочных емкостей.
В схеме базового эл-та ЭСЛ левое плечо ТП образовано несколькими параллельно включенными тр-рами, число к-ых определяет число входов (VT1 - VT3).
На базу VT4 подается Uоп, вырабатываемое источником опорного напр-ния (VT5, R7, R8, R9, VD1, VD2), представляющим собой эмиттерный повторитель ЭП с температурной стабилизацией напр-ния. Этот каскад обеспечивает на базе VT4 напр-ния:
Uоп=(U1+U0)/2= -1.3В
Если хотя бы на один из входов Х1...Х3 подан уровень логической 1 (напр., Х1=U1= -0,9 В), то соответствующий тр-р (VT1) будет открыт, а транзистор VT4 закрыт, поскольку на его базу поступает напряжение Uоп=1,3 В. Ток ТП будет протекать через левое плечо ТП, и на выходеY1 формируется низкий потенциал, а на выходе Y2 – высокий.
Если на все входы подать напряжение логического 0 (Х1=Х2=Х3=U0= -1,7 В), то транзисторы VT1..VT3 будут закрыты, а VT4 -- открыт и ток переключится в правое плечо. Тогда на выходе Y1 станет высокий потенциал, а на выходе Y2 -- низкий.
Из сказанного следует, что по выходу Y1 в положительной логике реализуется функция ИЛИ-НЕ, а по выходу Y2 -- ИЛИ.
Пар-ры схемы рассчитаны т. о., что высокий потенциал по выходам Y1 и Y2 составляет-0,1В, а низкий -- -0,9В. Эти уровни отличаются от стандартных уровней логических 0 и 1 элементов ЭСЛ. Для приведения указанных уровней к стандартным служит вторая ступень, образованная эмиттерными повторителями на тр-рах VT6, VT7 и R10, R11. Напр-ния на выходах Z1 и Z2 повторяют вых. напр-ния Y1 и Y2 первой ступени, но смещены относ-но их на уровень UБЭ открытых транзисторов VT6 и VT7 -0,8 В. В элементах ЭСЛ с общей точкой (корпусом) соединены положительные полюса источников питания. Это обеспечивает меньшую зависимость вых. напр-ний от помех, наводимых в общей шине.
81.(Сх-ка).Запоминающие элементы на транзисторах МНОП и ЛИЗМОП.
Запоминающие элементы современных РПЗУ – тр-ры типов МНОП и ЛИЗМОП (Лавинная Инжекция Заряда).
МНОП-транзистор отличается от обычного МОП-транзистора двухслойным подзатворным диэлектриком. На поверхности кристалла расположен тонкий слой двуокиси кремния SiO2, далее более толстый слой нитрида кремния Si3N4 и затем уже затвор (рис. 9.1, а).
Благодаря туннельному эффекту, носители заряда могут проходить ч/з тонкую пленку окисла толщиной не более 5 нм и скапливаться на границе раздела слоев. Этот заряд - носитель инфы, хранимой МНОП-тр-ром. Заряд записывают созданием под затвором напряженности электрич. поля, достаточной для возник новения туннельного перехода носителей заряда ч/з тонкий слой SiO2. На границе раздела диэлектрических слоев можно создавать заряд любого знака в зависимости от направленности электрич. поля в подзатворной области. Наличие заряда влияет на пороговое напр-ние тр-ра.
Для МНОП-транзистора с n-каналом отрицательный заряд на границе раз дела слоев повышает пороговое напряжение. При этом пороговое напряжение возрастает настолько, что рабочие напряжения на затворе тр-ра не в состоянии его открыть (создать в нем проводящий канал). Транзистор, в котором заряд отсутствует или имеет другой знак, легко открывается рабочим значением напряжения. Так осуществляется хранение бита в МНОП: одно из состояний трактуется как отображение лог. единицы, другое — нуля.
При программировании ЗУ используются относительно высокие напр-ния, около 20 В. После снятия высоких напр-ний туннельное прохождение носителей заряда через диэлектрик прекращается и заданное транзистору пороговое напряжение остается неизменным.
После 104... 106 перезаписей МНОП-транзистор перестает устойчиво хранить заряд. РПЗУ на МНОП-транзисторах энергонезависимы и могут хранить инфу месяцами и т.п. Перед новой записью старая инфа стирается записью нулей во все запоминающие эл-ты. Тип ЗУ — РПЗУ-ЭС.
Тр-ры типа ЛИЗМОП всегда имеют плавающий затвор, к-ый м.б. единственным или вторым, доп-ным к обычному (управляющему) затвору. Тр-ры с одним плавающим затвором исп-ся в ЗУ типа РПЗУ-УФ, а тр-ры с двойным затвором пригодны для применения как в РПЗУ-УФ, так и в РПЗУ-ЭС. Рассмотрим более современный тип — ЛИЗМОП-транзистор с двойным затвором (рис. 9.1, б).
Принцип работы ЛИЗМОП с двойным затвором близок к принципу работы МНОП-тр-ра — здесь также между управляющим затвором и каналом помещается область, в к-ую при программировании можно вводить заряд, влияющий на величину порогового напр-ния тр-ра. Только область введения заряда - не граница раздела сло ев диэлектрика, а окруженная со всех сторон диэлектриком проводящая область (обычно из поликристаллического кремния), в к-ую, как в ло вушку, можно ввести заряд, способный сохраняться в ней в течение очень длительного времени. Эта область и наз-ся плавающим затвором.
При подаче на управляющий затвор, исток и сток импульса положит. напр-ния относительно большой амплитуды 20...25 В в обратно смещен ных р-n переходах возникает лавинный пробой, область к-ого насыщает ся электронами. Часть электронов, имеющих энергию, достаточную для преодоления потенциального барьера диэлектрической области, проникает в плавающий затвор. Снятие высокого программирующего напр-ния вос станавливает обычное состояние областей тр-ра и запирает электроны в плавающем затворе, где они могут находиться длительное время (в вы сококачественных приборах многие годы).
Заряженный электронами плавающий затвор увеличивает пороговое напря жение транзистора настолько, что в диапазоне рабочих напряжений проводящий канал в транзисторе не создается. При отсутствии заряда в плавающем затворе транзистор работает в обычном ключевом режиме.
82.(ЦОС).Дискретное преобразование Фурье. Алгоритм БПФ с прореживанием по времени.
Выражение (2.1) называется прямым преобразованием, а выражение (2.2) - обратным. Как уже было сказано, ДПФ устанавливает связь между временными и частотным представлениями сигнала при разложении в базисе гармонических функций.
В матричной форме ДПФ имеет вид:
Основная идея алгоритма БПФ с прореживанием по времени заключается в поэтапном вычислении N-точечного ДПФ (N =2v ) на v этапах, на каждом из которых текущее ДПФ определяется как комбинация ДПФ вдвое меньшей размерности.
Общая ф-ла расчета ДПФ на произвольной i-м этапе:
число шагов (итераций) этого процесса равно log2 N .
1. Граф вычислительного процесса (рис.2.1) содержит N log2 N узлов, в каждом из которых происходит суммирование или вычитание данных, поэтому общее количество операций сложения (вычитания) равно log2 N .
2. Процедура многократного прореживания приводит к тому, что исходные данные располагаются не в естественном, а в двоично-инверсном порядке.
3. Граф алг-ма имеет регулярную стр-ру и строится из пары базовых операций - "бабочки". "Крылья" такой бабочки увеличиваются вдвое на каждой последующей итерации.
83.(ЦОС).Преобразование Уолша-Адамара. Алгоритм быстрого преобразования.
Пусть {s(n)}={s(0),s(1),…,s(N-1)} – совокупность равноотстоящих отсчетов сигнала. Пара дискретного преобразования Уолша-Адамара в показательной форме представляется в виде:
Равенство (2.15) называется прямым преобразованием и дает спектр сигнала в базисе Уолша. Равенство (2.16) называют обратным преобразованием.
Используя матрицу Адамара порядка N, можно записать преобразование в матричной форме:
Вычисление преобразования прямым способом требует выполнения N(N – 1) операций сложения. Существуют быстрые алгоритмы, которые требуют только Nlog2N операций. вычисление N-точечного преобразования сводится к предварительному суммированию (вычитанию) входных данных и
последующему вычислению двух N/2-точечных преобразований
84.(ЦОС).Преобразование Хаара.
Функции Хаара (har(r,k,t)) были построены в 1910 г. Они образуют полную систему ортонормированных функций, определенных на интервале [0,N), N=2l, l = 1,2, …, и описываются следующими рекуррентными соотношениями:
Для N=8 матрица этих функций имеет вид
.
Пара дискретного преобразования Хаара вектора S=[s(0), s(1),…, s(N-1)]T определяется следующими соотношениями:
Y=НS – прямое преобразоание Хаара
S=Н-1Y=N-1НTY – обратное преобразование Хаара.(трансп.матрица!!!)
Для вычиения этих преобразований существуют быстрые алгоритмы с числом операций сложения, равным 2(N-1), т.е. преобразование Хаара является самым быстрым среди всех рассмотренных ортогональных преобразований.
85.(ЦОС). Типы и основные структуры цифровых фильтров.
Функционирование ЦФ описывается разностным уравнением :
Нерекурсивный цифровой фильтр (НРЦФ).
ЦФ называется нерекурсивным , если хотя бы один из коэффициентов a(k),k=1,2,...M−1, разностного уравнения равен нулю.
Импульсная характеристика НЦФ имеет конечную длительность; значения отсчетов импульсной характеристики равны коэффициентам разностного уравнения.
Рекурсивный цифровой фильтр (РЦФ).
ЦФ называется рекурсивным , если хотя бы один из коэффициентов a(k),k=1,2,...M−1, разностного уравнения не равен нулю.
Импульсная характеристика РЦФ имеет бесконечную длительность. Поэтому РЦФ называют системами с бесконечной импульсной характеристикой (БИХ-системами). Однако РЦФ могут иметь и конечную импульсную характеристику.
Передаточной функцией H(z) ЦФ называется отношение Z –преобразования выходной последовательности к Z -преобразованию входной последовательности при нулевых начальных условиях .
Выделяют следующие структуры ЦФ: каскадная, прямая, каноническая и параллельная.
Прямая структура РЦФ 2-го порядка
Прямая каноническая структура 1 РЦФ 2-го порядка
Параллельная структура из трех РЦФ 2-го порядка
86.(ЦОС).Спектральный анализ сигналов на основе ДПФ.
Спектральный анализ заключается в разложении сигнала на его частотные или спектральные составляющие и оценке или измерении их спектральных характеристик − амплитуды, фазы, мощности, спектральной плотности мощности и др.
Особенности классического спектрального анализа на основе ДПФ связаны с оценкой спектра сигнала по его реализациям конечной длины, т. е. на конечном интервале наблюдения. При этом полагается, что за пределами этого интервала сигнал равен нулю или является периодическим продолжением считанной реализации. Широкое применение анализаторов спектра на основе ДПФ обусловлено наличием высокоэффективных вычислительных алгоритмов БПФ.
В основе анализаторов спектра, использующих ДПФ, лежит базовая структура:
Она реализует базовые операции анализатора спектра – взвешивание и вычисление ДПФ. Ее выходом является вектор ДПФ входной в общем случае не ограниченной по длине последовательности s(n), усеченной весовой функцией w(n) конечной длины N:
При реализации конкретных алгоритмов спектрального анализа различных сигналов важное значение имеет правильное масштабирование результатов анализа и учета их размерности. Так, по вычисленному ДПФ
вещественного периодического сигнала sp(n)N с периодом NTд и частотами гармоник ifд/N, совпадающими с бинами ДПФ, амплитуды гармоник Am(ωi) определяются как:
По ДПФ X(jωk) детерминированного сигнала конечной длительности NTд аналогичным образом находятся амплитуды, фазы и мощности k -й частотной выборки спектра сигнала.
87.(ЦОС).Представление полутоновых и цветных изображений. Виды градационных преобразований и их математическое описание.
Пусть F = {fij | i = 0, …, M-1, j = 0, …, N-1} – растровое изображение, представляющее собой прямоугольную матрицу, fij элемент изображения (пиксель). Если fij ∈{0, 1, …, L-1}, то изображение называется полутоновым, и каждый пиксель может принимать L оттенков серого (градаций яркости).
В общем виде процессы пространственной обработки изображений описываются выражением:
где fij – элементы входного изображения F;
gij – элементы обработанного изображения G;
T – оператор преобразования входного изображения в окрестности точки с координатами (ij).
Преобразование цветного изображения в полутоновое заключается в получении яркости каждой точки по формуле:
и последующем копировании на все три канала полученной величины (R=B=G=Y).где R, G, B – значение красного, зеленого и синего цветов в обрабатываемой точке.
Пусть fij – полутоновое изображение, t – порог и b0, b1 – два бинарных значения (для бинарного черно-белого b0 = 0, b1 = 255). Результат порогового разделения – бинарное изображение gij, полученное следующим образом:
Преобразование изображения в негатив - для изображения с диапазоном яркостей [0, ..., 1] L − выполняется согласно выражению:
Преобразование используется для усиления белых или серых деталей на фоне темных областей изображения, особенно когда темные области имеют преобладающие размеры и широко применяется при обработке цифровых медицинских снимков Логарифмическое преобразование определяется как:
где c – константа, f ∈0, 1, …, L . Использование логарифма позволяет узкий диапазон малых значений яркости преобразовать в более широкий диапазон выходных значений.
Степенные преобразования описываются выражением:
где c,γ – положительные константы. В результате применения логарифмического или степенного преобразования изменяется лишь яркость изображения.
Соляризация изображения имеет вид:
где fmax - максимальное значение входного изображения, а k - константа, позволяющая управлять динамическим диапазоном преобразованного изображения. участки исходного
изображения, имеющие уровень белого или близкий к нему уровень яркости, после обработки имеют уровень черного. При этом сохраняют уровень черного и участки, имеющие его на исходном изображении. Уровень же белого на выходе приобретают участки, имеющие на входе средний уровень яркости (уровень серого).
88.(ЦОС).Фильтрация изображений во временной и частотной областях.
В практике цифровой обработки изображений широко используется масочная фильтрация. В качестве маски используется множество весовых коэффициентов, заданных во всех точках окрестности, обычно симметрично окружающих рабочую точку кадра. Распространенным видом окрестности, часто применяемым на практике, является квадрат 3×3 с рабочим элементом в центре.
Сущность процедуры фильтрации заключается в смещении маски фильтра по изображению с шагом один пиксель слева направо, сверху вниз. При этом отклик задается суммой произведений коэффициентов фильтра на соответствующие значения пикселей в области, покрытой маской фильтра.
В общем случае фильтрация изображения fij размером M×N с использованием маски размером m×n описывается выражением:
где a=(m-1)/2, b=(n-1)/2
Если центр маски находится на границе изображения, то ее края выходят за пределы изображения. Для обработки краев изображений используются следующие приемы:
– Дополнение средним значением.
– Доопределение повторением крайних отсчетов последовательности.
– Экстраполяция более высокого порядка.
Низкочастотная фильтрация
Для устранения эффекта размывания контуров при подавлении шума следует переходить к нелинейной обработке. Примером нелинейного фильтра для подавления шума служит медианный фильтр.
Если упорядочить последовательность {, k1,} k wn = по возрастанию, то ее медианой будет тот элемент выборки, который занимает центральное положение в этой упорядоченной последовательности. Полученное таким образом число и является продуктом фильтрации для текущей точки кадра. Формальное обозначение описанной процедуры представляется в виде:
Медианная фильтрация в меньшей степени сглаживает границы изображения, чем любая линейная фильтрация.
Подчеркивание границ
Высокочастотная фильтрация не только улучшает детальность объектов на изображении, но и подчеркивает высокочастотные шумы.
89.(ЦОС).Методы улучшения контраста изображений.
Слабый контраст – один из наиболее распространенных дефектов фотографических, сканированных и телевизионных изображений, обусловленный ограниченностью диапазона воспроизводимых яркостей. Путем цифровой обработки контраст можно повысить, изменяя яркость каждого элемента изображения и увеличивая диапазон яркостей.
Одним из методов улучшения таких изображений является видоизменение гистограммы. Этот метод предусматривает преобразование яркостей исходного изображения с тем, чтобы гистограмма распределения яркостей обработанного изображения приняла желаемую форму.
Одним из методов улучшения контраста является линейная растяжка гистограммы, когда уровням исходного изображения, лежащим в интервале , присваиваются новые значения с тем, чтобы охватить весь возможный интервал изменения яркости, в данном случае [0, 255]. При линейном контрастировании используется линейное поэлементное преобразование вида: ,
параметры которого и определяются желаемыми значениями минимальной и максимальной выходной яркости. Решив систему уравнений:
относительно параметров преобразования и , можно привести выражение к виду:
.
Нормализация гистограммы. При этом на весь максимальный интервал уровней яркости [0, 255] растягивается не вся гистограмма, лежащая в пределах , а её наиболее интенсивный участок , из рассмотрения исключаются малоинформативные начальный и конечный участки.
Целью выравнивания гистограммы (линеаризации, эквализации) является такое преобразование, чтобы, в идеале, все уровни яркости приобрели бы одинаковую частоту, а гистограмма яркостей отвечала бы равномерному закону распределения. Кроме этого существует метод видоизменения гистограмм, который обеспечивает экспоненциальную или
гиперболическую ,
Рэлея форму распределения яркостей улучшенного изображения.
90.(ЦОС).Обработка бинарных и полутоновых изображений на основе методов математической морфологии.
Математическая морфология – относительно новый подход, исходное изображение рассматривается как множество и к нему применяются теоретико-множественные операции.
Фундаментальными морфологическими операторами для множеств являются наращение (dilation) и эрозия (erosion) – X с помощью , которые определяются как
Расширение: ,
Эрозия:.
Применение только операции расширения или эрозии обычно не дает эффекта в обработке изображений. Следует отметить, что в результате выполнения эрозии на изображениях могут исчезнуть объекты, диаметр которых меньше диаметра структурирующего элемента. В результате же выполнения расширения могут закраситься впадины в объектах и пустоты в изображениях, чей диаметр меньше структурирующего элемента.
Кроме того, следует отметить одно очень важное свойство морфологических операций. В результате их выполнения в изображении остаются лишь те симметрии, которые присутствуют в структурирующем элементе. Поэтому, для того чтобы в результате обработки изображения не внести в него новых искажений, структурирующий элемент должен быть близок к кругу (симметричен по всем направлениям). В этом случае в изображении останутся все его симметрии.
Для того чтобы исп-ть аппарат морфологии в обработки изобр-ний, применяют комбинации расширения и эрозии
Отмыканием множества А множеством В (А°В) - последовательное применение операций эрозии и расширений .
Замыкание множества А мн-вом В (А•В) – посл-ное применение операций расширения и эрозии .
Для полутоновых расширение: центральному элементу маски присваивают MAX значение из маски.
Для полутоновых эрозия : центральному элементу маски присваивают MIN значение из маски.
По аналогии с бинарными изображениями открывание есть последовательное применение операций эрозии и расширения, а закрывание – последовательное применение операций расширения и эрозии.
Открывание:
Закрывание:
С помощью математической морфологии можно проводить сглаживание изображения. Определяя строго математически, эта операция есть последовательное применение открывания и закрывания к исходному изображению, т.е.
БАЗЫ ДАННЫХ, ЗНАНИЙ И ЭКСПЕРТНЫЕ СИСТЕМЫ
ВЫЧИСЛИТЕЛЬНЫЕ КОМПЛЕКСЫ, СИСТЕМЫ И СЕТИ
ГЛОБАЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ
ИНТЕРФЕЙСЫ ПЭВМ
МОДЕЛИРОВАНИЕ
МИКРОПРОЦЕССОРНЫЕ СРЕДСТВА И СИСТЕМЫ
ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ
ПЕРИФЕРИЙНЫЕ УСТРОЙСТВА ЭВМ
СТРУКТУРНАЯ И ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ ЭВМ
СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ_I ЧАСТЬ
СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ_II ЧАСТЬ
СХЕМОТЕХНИКА
ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ И ИЗОБРАЖЕНИЙ
1-ая сторона
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71
2-ая сторона
8, 6, 4, 2, 16, 14, 12, 10, 24, 22, 20, 18, 32, 30, 28, 26, 40, 38, 36, 34, 48, 46, 44, 42, 56, 54, 52, 50, 64, 62, 60, 58, 72, 70, 68, 66