8.6.2. Итерационные методы

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

8.6.2.1Метод простых итераций

Итерационные формулы метода

Тогда

И т.д. Здесь k-номер итерации

8.6.2.2. Метод Гаусса-Зейделя (метод последовательных замещений)

Итерационные формулы метода Гаусса-Зейделя:

Недостатком метода простых итераций и метода Гаусса-Зейделя является низкая скорость сходимости.

Лекция 9

Классификация цифровых схем

–Ты что, не знаешь, что такое «это»?

–Я прекрасно знаю, что такое «это»,

когда я его нахожу.

Льюис Кэрролл, «Алиса в Стране чудес»

Цифровые схемы (ЦС) делят на комбинационные и последовательностные.

ПустьX–множество двоичных переменных на входах (x₁, …, x_n),аY– множество двоичных переменных на выходах (y₁, …, y_k).

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

Структура последовательностного и комбинационного устройства приведена на рис.9.1.

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

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

К устройствам последовательностного типа относятся триггеры, регистры, счётчики и т.д.

Рис.9.1. Структура комбинационного и последовательностного цифровых устройств

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

Алгебраическая форма этих связей представляет систему уравнений:

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

Таблицы истинности соответствуют только статическим или установившимся режимам работы цифровых устройств. При изменении входных сигналов в комбинационной схеме из-за инерционности логических элементов в ней начинает протекать переходный процесс. Максимальная длительность переходного процесса определяется максимальным числом последовательно включенных ЛЭ. Входные сигналы x_mизменяются не мгновенно, а в течение некоторого времениt_ф, т. е. сигналы имеют фронты конечной длительности. В течение этого времени входные сигналы имеют неопределенное значение. По этой причине, а также из-за задержек сигналов в ЛЭ выходные сигналы комбинационной схемы в течение переходного процесса могут принимать значения, не соответствующие описывающим их функциям. Это явление называют переходными состояниями или “гонками”. Появление кратковременных ложных значений выходных сигналов комбинационной схемы может привести к неправильному срабатыванию других схем, подключенных к ее выходам.

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

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

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

Логическую схему можно представлять на поведенческом, структурном, физическом уровне (см. рис.9.2).

Рис.9.2. Модели ЦС

При построении моделей ЦС рассматриваются три подхода: функциональный, структурный ипредставление языками описания аппаратуры (HDL).