БІЛЕТ № 28

№1

Нехай А - ділене, В - дільник і С - частка. Найпростіше ділення виконується в прямому коді. У разі представлення чисел , і у формі з фіксованою комою, воно реалізується у два етапи. На першому етапі визначається знак частки шляхом додавання за модулем два цифр знакових розрядів діленого і дільника (див. табл. 3.1). На другому етапі здійснюється ділення модулів початкових чисел і , округлення модуля частки, після чого до нього дописується знак, що визначений на першому етапі.

На відміну від множення чисел з фіксованою комою, в процесі якого принципово неможливе переповнення розрядної сітки, ділення дробових чисел може призвести до переповнення розрядної сітки і, отже, до неправильного результату. Тому для уникнення такої ситуації має виконуватись умова: .

Відомо два основних метода ділення чисел, а саме: ділення з відновленням та без відновлення остач.

Алгоритм ділення модулів чисел з відновленням остач полягає у виконанні таких дій.

П. 1. Подвоїти модуль діленого .

П. 2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця є першою остачею.

П. 3. Проаналізувати знак остачі R. Якщо , то черговому розряду частки присвоїти цифру 1 і перейти до п. 5; якщо ж R < 0, то черговому розряду частки присвоїти цифру 0.

П. 4. Відновити остачу, додавши модуль дільника .

П. 5. Подвоїти остачу.

П. 6. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника. Перейти до п. 3.

П. 3 - п. 6 виконувати до одержання всіх необхідних цифр частки.

За своїм характером операція ділення відноситься до операцій, що дають не завжди точний результат, тому ознакою закінчення операції ділення може бути досягнення заданої точності. Якщо в процесі ділення одержується остача R = 0, то операція зупиняється й у решту розрядів частки записується нуль. Звичайно формальною ознакою кінця операції ділення є одержання такої самої кількості розрядів у частці, яку мають операнди.

Подвоєння діленого та остачі практично виконується шляхом зсуву коду вліво на один розряд.

Приклад 3.16. Поділити число А = - 0, 10100 на число В = 0, 11011, використовуючи метод ділення з відновленням остач.

Розв'язання. Для даних чисел маємо: =1; = 0, 10100; =0; = 0, 11011. Визначаємо знак частки: =1 0=1. Віднімання будемо виконувати як додавання доповняльних кодів, тому = 1, 00101.

Усі дії, що виконуються в процесі ділення, наведені в табл. 3.18.

Відповідь: С = - 0, 10111.

З наведеного прикладу випливає, що цифри частки є інверсними значеннями знакових розрядів чергових остач. Треба також відзначити, що результат подвоєння іноді може бути > 1. Однак таке переповнення розрядної сітки усувається на наступному кроці алгоритму, оскільки після подвоєння завжди виконується віднімання.

Основні недоліки розглянутого методу ділення такі:

- аритмічність процесу ділення, яка обумовлена нерегулярністю виконання відновлення остачі, що призводить до ускладнення блоку керування діленням;

- відносно мала швидкість ділення, оскільки в середньому для половини кроків потрібно виконувати додаткове додавання, що забезпечує відновлення остач.

Для ритмізації процесу ділення можна виконувати фіктивну дію у тих випадках, коли відновлення остачі не потрібне, що призведе до збільшення часу виконання операції. Разом з тим, операцію можна спростити, якщо відмовитись від відновлення остач.

Таблиця 3.18 - Приклад ділення з відновленням остач

Алгоритм ділення модулів чисел без відновлення остач зводиться до виконання таких дій.

П. 1. Подвоїти модуль діленого .

П. 2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця є першою остачею.

П. 3. Проаналізувати знак остачі R. Якщо , то черговому розряду частки присвоїти цифру 1; якщо ж R < 0, то черговому розряду частки присвоїти цифру 0.

П. 4. Подвоїти остачу.

П. 5. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника якщо і додавши до попередньої остачі модуль дільника якщо R < 0. Перейти до п. 3.

П. 3 - п. 5 виконувати до одержання всіх необхідних цифр частки.

Приклад 3.17. Поділити число А = - 0, 10100 на число В = 0, 11011, використовуючи метод ділення без відновлення остач.

Розв'язання. Для даних чисел маємо: =1; = 0, 10100; =0; = 0, 11011. Визначаємо знак частки: =1 0=1. Віднімання будемо виконувати як додавання доповняльних кодів, тому = 1, 00101.

Усі дії, що виконуються в процесі ділення, наведені в табл. 3.19.

Відповідь: С = - 0, 10111.

В наведених алгоритмах пункт " Подвоєння остачі" можна замінити пунктом " Зменшити в два рази модуль дільника". В машині це буде відповідати зсуву дільника, а не остачі. Наявність двох варіантів зсуву для двох алгоритмів ділення приводить до чотирьох основних алгоритмів машинного ділення:

- ділення з відновленням остач і зі зсувом дільника;

- ділення з відновленням остач та з їх зсувом;

- ділення без відновлення остач і зсувом дільника;

- ділення без відновлення остач та з їх зсувом.

Алгоритми ділення з відновленням остач не знаходять практичного застосування в машинах у силу наведених вище причин, тому на рис. 3.8, а і б приведені тільки структурні схеми пристроїв для ділення без відновлення остач.

Для реалізації варіанта а необхідні 2n- розряднийрегістр дільника (РгВ) з колами зсуву вправо, 2 n- розрядний нагромаджувальний суматор (НСМ), (п +1)-розрядний регістр частки (РгС) з колами зсуву вліво, суматор за модулем два (М2), блок інвертування цифр (БІЦ) і блок керування (БК).

Таблиця 3.19 - Приклад ділення без відновлення остач

 

Перед початком ділення в нагромаджувальний суматор НСМ записується ділене. За допомогою М2 визначається цифра знакового розряду частки, що записується в знаковий розряд регістра РгС. Передавання модуля дільника в НСМ для додавання або віднімання забезпечується блоком керування, що аналізує цифру знакового розряду НСМ. Ця знакова цифра остачі, проходячи через блок БІЦ, інвертується і подається в молодший розряд регістра частки, де вона зсувається вже як цифра частки.

Для реалізації варіанта б необхідні: (п + 1)-розрядний регістр дільника; (п + 1)-розрядний регістр частки з колами зсуву вліво і (n + 1)-розрядний суматор з колами зсуву вліво. Решта блоків така сама, як для варіанта а.

а)

б)

Рис. 3.8. Варіанти пристроїв для ділення без відновлення остач:

а - зі зсувом дільника; б - зі зсувом остач

 

Аналіз обох схем показує, що апаратні витрати на реалізацію варіанта б менше, ніж варіанта а. Проте у варіанті б неможливо сумістити додавання і зсув, оскільки додавання в НСМ можна тільки після закінчення зсуву коду остачі в нагромаджувальному суматорі. В варіанті а кожну цифру дільника з відповідного розряду регістра РгВ можна одночасно передавати за двома адресами: в сусідній правий розряд цього регістра (зсув) і у відповідний розряд НСМ, тобто починати виконувати додавання модуля дільника (або його доповнення) до остачі. Виходячи з цього, час ділення за алгоритмом без відновлення остач і зі зсувом дільника дорівнює , тоді як зі зсувом остач - .

№2

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

Аналого-цифровой преобразователь (АЦП) производит обратную операцию.

Звуковой ЦАП обычно получает на вход цифровой сигнал в импульсно-кодовой модуляции (англ. PCM, pulse-code modulation). Задача преобразования различных сжатых форматов в PCM выполняется соответствующими кодеками.

Применение

ЦАП применяется всегда, когда надо преобразовать сигнал из цифрового представления в аналоговое, например, в проигрывателях компакт-дисков (Audio CD).

Типы ЦАП

Наиболее общие типы электронных ЦАП:

Широтно-импульсный модулятор — простейший тип ЦАП. Стабильный источник тока или напряжения периодически включается на время, пропорциональное преобразуемому цифровому коду, далее полученная импульсная последовательность фильтруется аналоговым фильтром нижних частот. Такой способ часто используется для управления скоростью электромоторов, а также становится популярным в Hi-Fi-аудиотехнике;

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

Большинство ЦАП большой разрядности (более 16 бит) построены на этом принципе вследствие его высокой линейности и низкой стоимости. Быстродействие дельта-сигма ЦАП достигает сотни тысяч отсчетов в секунду, разрядность — до 24 бит. Для генерации сигнала с модулированной плотностью импульсов может быть использован простой дельта-сигма модулятор первого порядка или более высокого порядка как MASH (англ. Multi stage noise SHaping). С увеличением частоты передискретизации смягчаются требования, предъявляемые к выходному фильтру низких частот и улучшается подавление шума квантования;

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

ЦАП лестничного типа (цепная R-2R-схема). В R-2R-ЦАП значения создаются в специальной схеме, состоящей из резисторов с сопротивлениями R и 2R, называемой матрицей постоянного импеданса, которая имеет два вида включения: прямое — матрица токов и инверсное — матрица напряжений. Применение одинаковых резисторов позволяет существенно улучшить точность по сравнению с обычным взвешивающим ЦАП, так как сравнительно просто изготовить набор прецизионных элементов с одинаковыми параметрами. ЦАП типа R-2R позволяют отодвинуть ограничения по разрядности. С лазерной подгонкой резисторов на одной подложке достигается точность 20-22 бита. Основное время на преобразование тратится в операционном усилителе, поэтому он должен иметь максимальное быстродействие. Быстродействие ЦАП единицы микросекунд и ниже (то есть наносекунды);

Характеристики

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

Разрядность — количество различных уровней выходного сигнала, которые ЦАП может воспроизвести. Обычно задается в битах; количество бит есть логарифм по основанию 2 от количества уровней. Например, однобитный ЦАП способен воспроизвести два () уровня, а восьмибитный — 256 () уровней. Разрядность тесно связана с эффективной разрядностью (англ. ENOB, Effective Number of Bits), которая показывает реальное разрешение, достижимое на данном ЦАП.

Максимальная частота дискретизации — максимальная частота, на которой ЦАП может работать, выдавая на выходе корректный результат. В соответствии с теоремой Найквиста — Шеннона (известной также как теорема Котельникова), для корректного воспроизведения аналогового сигнала из цифровой формы необходимо, чтобы частота дискретизации была не менее, чем удвоенная максимальная частота в спектре сигнала. Например, для воспроизведения всего слышимого человеком звукового диапазона частот, спектр которого простирается до 20 кГц, необходимо, чтобы звуковой сигнал был дискретизован с частотой не менее 40 кГц. Стандарт Audio CD устанавливает частоту дискретизации звукового сигнала 44, 1 кГц; для воспроизведения данного сигнала понадобится ЦАП, способный работать на этой частоте. В дешевых компьютерных звуковых картах частота дискретизации составляет 48 кГц. Сигналы, дискретизованные на других частотах, подвергаются передискретизации до 48 кГц, что частично ухудшает качество сигнала.

Монотонность — свойство ЦАП увеличивать аналоговый выходной сигнал при увеличении входного кода.

THD+N (суммарные гармонические искажения + шум) — мера искажений и шума вносимых в сигнал ЦАПом. Выражается в процентах мощности гармоник и шума в выходном сигнале. Важный параметр при малосигнальных применениях ЦАП.

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

Статические характеристики:

DNL (дифференциальная нелинейность) — характеризует, насколько приращение аналогового сигнала, полученное при увеличении кода на 1 младший значащий разряд (МЗР), отличается от правильного значения;

INL (интегральная нелинейность) — характеризует, насколько передаточная характеристика ЦАП отличается от идеальной. Идеальная характеристика строго линейна; INL показывает, насколько напряжение на выходе ЦАП при заданном коде отстоит от линейной характеристики; выражается в МЗР;

усиление;

смещение.

Частотные характеристики:

SNDR (отношение сигнал/шум+искажения) — характеризует в децибелах отношение мощности выходного сигнала к суммарной мощности шума и гармонических искажений;

HDi (коэффициент i-й гармоники) — характеризует отношение i-й гармоники к основной гармонике;

THD (коэффициент гармонических искажений) — отношение суммарной мощности всех гармоник (кроме первой) к мощности первой гармоники.

№3

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

Характерные особенности Linux

Одновременное выполнение нескольких программ

Работа нескольких пользователей на одной машине

Документированность Linux

Отличие Linux от других ОС со свободной лицензией

Характерные особенности Linux

 

Характерными особенностями Linux как операционной системы являются:

многозадачность: одновременно выполняется множество программ;

многопользовательский режим: большое число пользователей одновременно работают на одной и той же машине;

защищенный режим процессора (386 protected mode);

защита памяти процесса; сбой программы не может вызвать зависания системы;

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

разделение страниц по записи между экземплярами выполняемой программы. Это значит, что процессы-экземпляры программы могут использовать при выполнении одну и ту же память. Когда такой процесс пытается произвести запись в память, то 4-x килобайтная страница, в которую идет запись, копируется на свободное место. Это свойство увеличивает быстродействие и экономит память;

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

общая память программ и дискового кэша: вся свободная память используется для буферизации обмена с диском;

динамические загружаемые разделяемые библиотеки;

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

совместимость со стандартами System V и BSD на уровне исходных текстов;

наличие исходного текста всех программ, включая тексты ядра, драйверов, средств разработки и приложений. Эти тексты свободно распространяются. В настоящее время некоторыми фирмами для Linux поставляется ряд коммерческих программ без исходных текстов, но все, что было свободным так и остается свободным;

управление заданиями в стандарте POSIX;

эмуляция сопроцессора в ядре, поэтому приложение может не заботиться об эмуляции сопроцессора. Конечно, если сопроцессор в наличии, то он и используется;

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

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

поддержка ряда распространенных файловых систем (MINIX, Xenix, файловые системы System V); наличие собственной передовой файловой системы объемом до 4 Терабайт и с именами файлов до 255 знаков;

прозрачный доступ к разделам DOS (или OS/2 FAT): раздел DOS выглядит как часть файловой системы Linux; поддержка VFAT;

специальная файловая система UMSDOS, которая позволяет устанавливать Linux в файловую систему DOS;

поддержка всех стандартных форматов CD ROM;

поддержка сети TCP/IP, включая ftp, telnet, NFS и т.д.

Одновременное выполнение нескольких программ

 

Так называемая виртуальная мультиконсоль дает возможность на одном дисплее организовать работу нескольких консолей. На первой консоли запускается процесс трансляции. Комбинацией клавиш Alt-F2 следует переход на вторую консоль. Трансляция продолжается, но при этом первая консоль на экране дисплея заменяется новой картинкой второй консоли, в которой запускается, например, редактор текста. Комбинацией Alt-F3 следует переход на третью консоль, в которой запускается отладчик и т.д. Обычно в системе 6 консолей, но можно установить до 64-х. В любой момент времени можно переключиться на любую консоль.

 

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

 

На одной из свободных консолей можно запустить оконную графическую систему X Window System. Открываете окно на экране и играете в DOOM (можно через сеть с партнером). В других окнах: база данных, почта, редактор, трансляция и т.д.

 

Таким образом, одновременно работает много консолей, а на одной из консолей еще и много окон X Window System.

 

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

 

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