Конспект лекций по дискретной математике

единицы(нуля).

Существенные вершины

| |макс. |0000 |0001 |0101 |0111 |1000 |1010 |1100 |1110 |1111 |

|A|000X | * | * | | || || || || | |

|B|X000 | * | | | || *|| || || | |

|C|0X01 | | * | * | || || || || | |

|D|01X1 | | | * | * || || || || | |

|E|X111 | | | | * || || || || | * |

|F|111X | | | | || || || || | * |

| |1XX0 | | | | || * || *|| * || * | |

| | | a | b | c | d || || || || | e|

Для полностью определенной булевой функции количество меток в каждой

строке равно числу ноль - кубов покрываемых кубом данной строки .Для не

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

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

кубов ,принадлежащих ядру покрытия в таблице ищутся столбцы с единственной

меткой .Строка ,которой принадлежит эта метка определяет куб ядра .

Т(f)=(1XX0(

3) Определение множества минимальных покрытий .

На этом этапе из множества максимальных кубов не принадлежащих ядру

покрытия ,выделяются такие минимальные подмножества ,с помощью каждого из

которых покрываются оставшиеся вершины (не покрытые ядром) .

Реализацию этого этапа целесообразно производить с использованием

упрощенной таблицы.

В упрощенной таблице вычеркнуты все кубы принадлежащие ядру и вершины

покрываемые ядром.

Для решения задачи 3-го этапа можно использовать один из 3-х методов

или их комбинацию:

1) Метод простого перебора

2) Метод Петрика

3) Дальнейшее упрощение.

1)На данном этапе целесообразно ввести обозначение максимальных кубов

и существенных вершин.

Максимальные кубы обозначены в таблице А...F

1-ый метод целесообразно применять для упрощенной таблицы небольшого

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

Для нашего примера все кубы входящие в упрощенную таблицу покрытий

обладают одной размерностью(то есть необходимо выбрать минимальное

количество этих кубов для покрытия всех оставшихся существенных вершин).

Из таблицы видно ,что минимальное число кубов равно трем.К возможным

вариантам покрытий относятся:

( T( ( T(

C min1(f)= (A( C min 1(f)= (B( ,...

(C( (C(

(E ( (E (

2)Достоинство этого метода-получение всех минимальных покрытий.

Метод базируется на составлении логического выражения ,

представляющего собой условие покрытия всех вершин из упрощенной таблицы

покрытий и преобразования этого выражения .

Y=(AvB)(AvC)(CvD)(DvE)(EvF)=(AvBC)(DvCE)(EvF)=

=(AvBC)(DEvCEvDFvCEF)=

=(ADEvACEvADFvBCDEvBCEvBCDF)

Каждый из пяти конъюнктивных термов соответствует покрытию булевой

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

соответствие тупиковую ДНФ.

Последний терм не соответствует минимальному покрытию ,то есть данная

функция имеет четыре минимальных покрытия.

3) Дальнейшее упрощение состоит в применение двух операций :

а)Вычеркивание лишних строк.

б)Вычеркивание лишних столбцов.

Если множество меток i-й строки является подмножеством меток j-й

строки и куб i имеет небольшую размерность, чем куб j, то из таблицы можно

вычеркнуть i-ю строку так как существенные вершины покрываемые i-м кубом

будут с гарантией покрыты j-м кубом.

В дальнейшем рекомендуется построить новую упрошенную таблицу.

В отношении новой таблицы можно использовать один из трех методов:

1) Метод простого перебора.

2)Метод Петрика.

3)Дальнейшее упрощение.

Функциональная полнота системы булевых функций.

Система булевых функций S=(y1,y2,...,ym(называется функционально

полной ,если с помощью функций этой системы можно выразить любую сколь

угодно сложную булеву функцию с использованием метода суперпозиции,

возможно многократно.

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

одних функций в другие вместо их аргумента.

Примерами полных систем являются :

1)S1 =((,&,(((булев базис)

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

базируется на возможности представления любой булевой функции в нормальной

форме ,которая является комбинацией операций отрицания ,конъюнкции и

дизъюнкции, применительно к аргументу этой функции.

Система S1 =((,&,(( является избыточной так как из нее можно удалить

одну из функций (& или () без нарушения функциональной полноты.

Получаемые при этом системы S2 ={(,&}(и S3((,&,((обычно называют

сокращенным булевым базисом .

Недостающие операции( ( в системе S2 и & в системе S3 ) могут быть

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

____

Де Моргана : x1V x2= [pic]1[pic]2

_____

x1 x2= [pic]1 v[pic]2

Функциональная полнота системы булевых функций называется минимальной

,если удаление из нее какой-либо функции приводит к нарушению свойства

функциональной полноты.

Системы из одной функции S4=((стрелка Пирса)

S5=|(штрих Шеффера)

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

2)Базис Жегалкина S6= {&, (, 1}

Понятие функциональной полноты системы булевых функций связано с

аналогичным понятием для системы логических элементов.

Эта связь заключается в следующем :

Если каждой функции из некоторой функционально полной системы

сопоставить логический элемент, реализующий эту функцию ,то система

логических элементов соответствующая некоторой функционально полной системе

булевых функций естественным образом оказывается тоже функционально полной

Задача синтеза комбинационных схем с использованием функционально

полной системы логических элементов можно построить комбинационную схему

реализующую любую наперед заданную ,сколь угодно сложную булеву функцию.

Доказательство функциональной полноты некоторой системы

булевых функций можно осуществлять одним из двух способов:

1) С использованием теоремы о функциональной полноте .

2) С использованием конструктивного подхода .

Теорема о функциональной полноте (Пост - Яблонского).

Для того, чтобы система булевых функций была функционально полной

необходимо и достаточно чтобы она содержала хотя бы одну функцию не:

1) cохраняющую константу ноль

2) cохраняющую константу единица

3) линейную функцию

4) монотонную функцию

5) самодвойственную функцию.

Замечательные классы булевых функций.

1. Булева функция называется сохраняющей константу ноль , если на нулевом

наборе аргументов она принимает значение равное нулю, то есть

f(0,0,0,...,0) = 0;

В противном случае функция относится к классу не cохраняющих

константу ноль.

К функциям ,сохраняющим константу ноль относятся

f(x1,x2)= x1 v x2

f(x1,x2)= x1 * x2

К функциям не cохраняющим константу ноль относятся

f(x)=[pic] и f(x1,x2)=x1(x2

2.Булева функция называется сохраняющей константу единица , если на

единичном наборе аргументов она принимает значение равное единице, то есть

f(1,1,1,...,1)= 1;

В противном случае функция относится к классу не cохраняющих

константу единица.

К функциям ,сохраняющим константу единица относятся

f(x1,x2)= x1 v x2

f(x1,x2)= x1 * x2

К функциям не cохраняющим константу единица относятся

f(x)=[pic] и f(x1,x2)=x1(x2

3. Булева функция называется линейной если она представима полиномом

Жегалкина первой степени.

В булевой алгебре доказывается теорема о возможности представления

любой булевой функции от n переменных с помощью полинома Жегалкина n-ой

степени.

В общем случае полином имеет вид :

fn (x) = K0 (K1x1 (...(Kn xn (...

...(Kn+1x1x2 (Kn+2x1x3 (...(Kn+lxn-1xn (...

...

...(Kn+mx1x2...xn

K0 ,K1 ,Kn+m -являются коэффициентами и представляют собой логические

константы нуля или единицы.

В алгебре Жегалкина одноименной полином можно считать канонической

нормальной формой для булевой алгебры.

Полином Жегалкина является линейным (1-ой степени) если все

коэффициенты общего полинома ,начиная с Kn+1=Kn+2 =...=Kn+m =0

В отношении функции от 2-х переменных полином Жегалкина имеет вид

(линейный): f2(x)=K0(K1x1(K2x2

Примерами линейных функций являются:

y= x1(x2 (K0=0,K1=K2=1)

_____

y= x1(x2=x1(x2=1(x1(x2 (K0=K1=K2)

y= [pic]=1(x1 (K0=K1=1 ,K2=0)

Примеры нелинейных функций:

y= x1(x2

____

y= x1(x2 =x1(x2=1(x1(x2

4.Булева функция называется монотонной если при возрастании наборов

аргументов она принимает неубывающие значения.

A=(a1,a2,...,an)>B=(b1,b2,...,bn)

f(A)(f(B)

Между наборами аргументов А и В имеет место отношение возрастания в

том и только том случае , если имеет место отношение не убывания для всех

компонент этого набора:

___

ai(bi (i=1, n )

и по крайней мере для одной компоненты имеет место отношение возрастания.

Примеры наборов ,для которых имеет место отношение возрастания:

(1011)>(0011)

(1011)>(0001)

(0001)>(0000)

Пример несопоставимых наборов (1011) и (0111)

В отношении функции от 2-х переменных несопоставимыми являются наборы

(01) и (10)

Пример немонотонных функций: y=[pic]

y= x1(x2

5.Две булевы функции fn(x) и gn(x) называются двойственными если для

любых наборов аргументов выполняется равенство

____

fn(x) =gn(x) то есть функции f и g на противоположных наборах аргументов х

и [pic] принимает противоположные значения .

Два набора аргументов называются противоположными если любая из их

компонент принимает противоположные значения.

x=(0101) [pic]=(1010)

Булева функция называется самодвойственной если она является

двойственной по отношению к самой себе то есть принимает противоположные

значения на противоположных наборах аргументов.

Примером самодвойственной функции является : у= [pic]

Примеры не самодвойственных функций: у=х1(х2

у=х1vх2

у=х1(х2

Принадлежность базовых булевых функций и логических констант к

замечательным классам представлена таблицей.

К0 + сохраняет константу ноль ,- не сохраняет константу ноль

К1 + сохраняет константу единица ,- не сохраняет константу

Кл + линейная ,- нелинейная

Км + монотонная , - не монотонная

Кс + самодвойственная ,- не самодвойственная

|Функция |К0 |К1 |Кл |Км |Кс |

|0 | + | - | + | + | - |

|1 | - | + | + | + | - |

|[pic] | - | | | | |

|х1(х2 | + | + | - | + | - |

|х1vх2 | + | + | | + | - |

|х1(х2 | + | - | + | - | - |

|х1(х2 | - | | + | | - |

|х1(х2 | + | | | - | |

|х1(х2 | - | | | | |

|х1(х2 | - | | - | | |

|х1(х2 | - | | | | |

Конструктивный подход к доказательству функциональной полноты некоторой

системы булевых функций.

Подход основан на доказательстве реализуемости функций булева базиса

с помощью функций этой системы.

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

базис образует функционально полную систему.

Пример :S5=(((

_ ____

x =x ( x= x(x

((((

x1(x2 = x1(x2 =( x1(x2)(( x1(x2)

______

x1vx2=[pic]1 ([pic]2 =( x1(x1)(( x2(x2)

Синтез комбинационных схем.

Понятие логического элемента.

Типовые логические элементы и их обозначения на функциональных схемах.

Определение: как правило ,под логическим элементом понимается

комбинационная схема ,реализующая некоторую элементарную булеву функцию.

Любой логический элемент характеризуется :

1) Наличием одного или нескольких входов на которые подаются входные

сигналы( входные переменные).

2) Наличием выхода ,на котором формируется выходной сигнал

(выходная переменная).

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

от входных.

К основным типам логических элементов относятся:

1) Инвертор( НЕ)

[pic]

2) Дизъюнктор (ИЛИ)

[pic]

3) Конъюнктор (И)

[pic]

4) Дизъюнктор с отрицанием (ИЛИ - НЕ)

[pic]

5) Конъюнктор с отрицанием (И - НЕ)

[pic]

6) Исключительное ИЛИ

(единичный сигнал на выходе имеет место в том и только том случае если на

одном и только одном входе присутствует единичный сигнал)

[pic]

7) Сумматор по модулю 2

[pic]

1)Элементы 1,2,3 образуют булев базис.

2)Элементы 1 и 2 или 1 и 3 образует сокращенный(неполный)

булев базис.

3)Элементы 4 или 5 образуют универсальный базис.

4)Элементы 3 и 7 образуют базис Жегалкина.

Функции элементов 6 и 7 совпадают при наличии только двух входов.

Понятие двоичного сигнала.

Способы его кодирования.

В связи с использованием двух значений логики в логических схемах как

входные ,так и выходные сигналы в этих схемах представляются с помощью так

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

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

В зависимости от того ,какой уровень сигнала сопоставляется с

логическим нулем а какой с логической единицей различают два способа

кодирования двоичных сигналов:

1)Позитивное кодирование (положительное)

высший уровень сигнала - 1 ,низший - 0

2)Негативное кодирование (отрицательное)

высший уровень сигнала - 0 ,низший - 1

При изменении способа кодирования двоичного сигнала функция одной и

той же электронной схемы ,реализующей некоторый логический элемент меняется

на противоположную.

Понятие логической системы.

Типы логических систем.

Логическая схема представляет собой совокупность логических элементов

и связей между ними.

Соединения логических элементов в рамках единой логической системы

должны удовлетворять следующим правилам:

1)К любому входу логического элемента могут быть подключены:

a) выход любого другого логического элемента( в частном случае ,того же

самого)

б) входной сигнал (входная переменная)

в) логическая константа(0 или 1)

В реальных электронных схемах подача логической константы на вход элемента

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

через резистор к шине питания.

2)Выход любого логического элемента схемы может быть подключен к входу

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

.В частном случае возможна комбинация того и другого.

Логические схемы разделяются на два типа :

1)Комбинационные

2)Последовательносные

В комбинационных схемах значение выходного сигнала в любой момент

времени зависит только от комбинации входных сигналов (в этот же момент

времени с учетом задержки распространения сигнала по элементам схемы)

С учетом этой задержки значение выходного сигнала по времени

запаздывает на время задержки по сравнению с моментом изменения входных

сигналов.

Функционирование комбинационной схемы может быть описано булевой

функцией, отражающей зависимость выходного сигнала схемы, как функции от

входных сигналов , как аргумент этой функции.

Для комбинационных схем с несколькими выходами эта зависимость

отражается системой булевых функций.

Пример комбинационной схемы на элементах булева базиса :

[pic]

В последовательносных схемах выходные сигналы в любой момент времени

зависят не только от комбинации входных сигналов в данный момент времени

,но и от предыстории их изменения ,то есть от последовательности входных

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

некоторым внутренним строением ,от которого зависит значение выходного

сигнала(ов).

Внутреннее состояние такой схемы сохраняется на запоминающих элементах

(триггерах) ,в связи с чем ,схемы этого типа называются схемами с памятью.

В общем случае поседовательносная схема представляет собой некоторый

цифровой автомат.

Пример последовательносной схемы: (универсальный базис И-НЕ)

[pic]

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

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

самого элемента (через другие элементы схемы).

Основные параметры комбинационной схемы.

Основными параметрами комбинационных схем (КС) является стоимость и

быстродействие ,как правило при построении абстрактных КС не привязанных к

конкретной системе элементов цена схемы определяется в смысле Квайна.

Быстродействие схемы ,как правило оценивается задержкой распространения

сигналов от входов схемы к ее выходу. Для абстрактных КС эту задержку

принято считать в виде : Т=к( ,(-задержка на одном логическом элементе,к-

максимальное количество логических элементов ,через которые проходит сигнал

от входов к выходу.

[pic]

Как правило задержка схемы сопоставляется с числом уровней этой схемы.

Для этой цели все элементы схемы распределяются по уровням. Уровень

элемента ,на выходе которого формируется выходной сигнал схемы совпадает с

количеством уровней схема и следовательно с ее задержкой.

Для приведенной схемы элементы 1,2,3 относятся к первому уровню.

Элементы 4,5 ко второму уровню.

Элемент 6 к третьему уровню.

Элемент 7 к четвертому уровню.

Задачи анализа и синтеза комбинационных схем.

В общем виде задача анализа ,комбинационных схем сводится к

определению функции ,реализуемой заданной схемой ,в частном случае задача

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

комбинацию входных сигналов.

Для определения функции схемы целесообразно использовать метод

подстановки ,его идея состоит в следующем: Выходы логических элементов

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

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

аргумент, до тех пор ,пока в выражении функции все промежуточные переменные

не будут заменены на входные переменные:

y=y1v y2=[pic]4v y3y6=x1x2v(y4v y5)x4x5=

___

=x1x2v(x1x2v[pic]3)x4x5

Определим реакцию схемы на входной набор.

Например (00000) у=1

Задача синтеза состоит в построении комбинационной схемы по заданному

закону функционирования.

При решении этой задачи необходимо учитывать следующие моменты:

1) Синтезируемая схема должна по возможности содержать минимум

оборудования. В связи с этим актуальной задачей является минимизация

заданной булевой функции. При решении этой задачи целесообразно получить

как МДНФ так и МКНФ.

2) Как правило ,синтезируемая схема строится на логических элементах

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

элементов должна обладать свойством функциональной полноты ,то есть быть

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

любую наперед заданную булеву функцию. Такими функционально полными

системами логических элементов являются: 1.(И,ИЛИ,НЕ( 2.(И,НЕ(

3.(ИЛИ,НЕ( 4.(И-НЕ(

5.(ИЛИ-НЕ( 6.(И,М2(

3) Как правило при решении задачи синтеза стараются добиться экстремального

значения одного из параметров схемы :минимум цены или максимум

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

эффективности схемы является минимум цены по Квайну над минимальными

формами проводят дополнительные преобразования ,путем решения задач

факторизации и возможно декомпозиции булевой функции. Как правило

минимальная форма не дает абсолютного минимума стоимости ,чего можно

добиться решением задач факторизации и декомпозиции. Если критерием

эффективности схемы является минимальная задержка ,то следует иметь в

виду ,что факторное преобразование и декомпозиция булевой функции в общем

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

случае схема оптимизируется по одному из показателей при наличии

ограничения на второй. Примером подобной постановки задачи синтеза

является: Синтезировать схему с минимальной ценой по Квайну ,чтобы ее

задержка не превышала 4(.

4) Необходимо учитывать ,в каком виде представлены входные сигналы схемы:

только в прямом или и в прямом и в обратном. В первом

случае строится комбинационная схема с однофазными входами. Во втором

случае с парафазными. В реальных комбинационных схемах входные

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

Например при построении комбинационного сумматора входные сигналы

снимаются с регистров слагаемого. При интегральной реализации

регистров в виде СИС в целях минимизации числа выходов выходные сигналы

регистров как правило представляются только в прямом виде ,что делает

актуальными схемы с однофазными входами.

5) При построении схем в реальной системе элементов необходимо учитывать

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

а) Коэффициент объединения по входу, который представляет собой ограничение

на число входов в элемент. Может принимать значения 2,3,4,8,16.

б) Коэффициент разветвления по выходам который определяет максимальное

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

условиях его нормального функционирования. Этот коэффициент определяет

нагрузочную способность. Варьируется от 10 до 30.

6) В реальных системах элементов однотипные элементы объединяются в модули

,реализуемые одной интегральной схемой с малым уровнем интеграции(МИС). В

связи с этим при построении схем в реальной системе элементов необходимо

минимизировать не столько число элементов и входов в них сколько число

модулей ,из которых компонуется схема.

7) Как правило в большинстве реальных систем элементов наряду с простыми

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

составную булеву функцию. Типичным примером может служить элемент И-ИЛИ-

НЕ.

8) В реальных системах элементов как правило используется значительное

разнообразие логических элементов, относящихся к разным базисам. Тем не

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

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

элементов.

Построение комбинационных схем (КС) по минимальным нормальным формам в

различных базисах.

1) Булев Базис (И, ИЛИ, НЕ)

_ _ _ _ _ _ _

y=x1x2x3vx1x2x4vx1x5vx6 (МДНФ)

-------- ------- -----

и (3) и (3) и (2)

Схема с парафазными входами

[pic]

SQ=3+3+2=12 Sa= 0 цифра частного равна единице ,для

остатка < 0 цифра равна нулю.

Особенности реализации деления в ЭВМ.

(по отношению к целым числам)

1) Делимое по сравнению с делителем представляется в удвоенном

формате.

2) В качестве результата деления формируется как частное так и остаток

.При этом как правило остаток замещает старшие разряды ,а частное

младшие.

3) В целях экономии оборудования на каждом шаге осуществляется не сдвиг

делителя вправо относительно остатка ,а сдвиг остатка влево относительно

неподвижного делителя. При этом делитель совмещается со старшими разрядами

делимого ,а далее остатка.

4) При получении отрицательного остатка на каком либо шаге для перехода

к следующему шагу требуется восстановление остатка путем сложения с

делителем. Подобный метод называется делением с восстановлением

остатка .В целях экономии времени деление как правило реализуется в ЭВМ

с применением метода без восстановления .В соответствии с этим

методом при получении отрицательного остатка он не восстанавливаясь

сдвигается влево так же как и положительный однако при этом на

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

делителем.

Доказательство:Допустим на i-м шаге получен отрицательный остаток

тогда по методу с восстановлением :Ri+1=2(Ri+B)-B

Ri+1 =2Ri +2B-B=2Ri+B

5) При некоторых соотношениях между делимым и делителем может оказаться что

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

при делении на 0. Этот особый случай распознается на начальном шаге деления

и приводит к прерыванию выполняемой программы по причине ошибки деления.

Деление беззнаковых.

А/В0, B>0 => A/B A/B0

A0 => A/B(-2n-1 A/B>-2n-1 A+B*2n-1+B>0

A>0, B>0 => A/B>-2n-1-1 A+B*2n-1+B<0

При одинаковых знаках операндов для проверки корректности деления

необходимо сдвинуть делимое на 1 разряд влево а затем вычесть делитель из

его старших разрядов.

Проверка корректности осуществляется сравнением знака первого

остатка со знаком делимого. Если они НЕ совпадают деление корректно, в

противном случае - не корректно.

При разных знаках пробное вычитание фактически заменяется сложением.

В этом нет ничего необычного, так как для первого шага в качестве

остатка для первого шага фигурирует само делимое и его знак не совпадает со

знаком делителя в соответствии с действиями для основного цикла над текущим

остатком в этом случае необходимо выполнять сложение с остатком.

В связи с тем, что при разных знаках операндов получается

отрицательное, имеющее диапазон, больший на единицу, чем положительное,

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

последовательность действий :

Сложение делимого с делителем, совмещенным с его младшими разрядами. При

этом выполняется знаковое расширение делимого на старшие разряды делителя.

Сдвиг полученного остатка на один разряд влево.

Сложение с делителем, совмещенным со старшими разрядами остатка.

Сравнение знака остатка со знаком делимого выполняется также как и для

операндов с одинаковыми знаками.

В связи с тем, что при проверке корректности деления используется

знак делимого необходимо при схемной реализации предусмотреть его

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

старшая цифра частного, интерпретируемая как знак.

Действительно, при корректном делении получается верный знак

частного.

Пример : A=-168 B=-14 n=5

A=1101011000 ; B=10010

Выполняемые действия

| |я | |(младшие) |

|0 |A | 11010 |11000 |

| |( | | |

| |A |-10101 |10000 |

| |B |10010 | |

| |R0 |((( | |

| | |00011 |1000|0 |

| | |( |( |

| | |sign R0(sign |(( |

| | |B( | |

|1 |( | | |

| |R0 |+00111 |000|00 |

| |B |10010 | |

| | |((( | |

| |R1 |11001 |000|01 |

|2 |( | | |

| |R1 |+10010 |00|010 |

| |B |10010 | |

| | |((( | |

| |R2 |00000 |00|010 |

| | |( |( |

| | |sign R2(sign |(( |

| | |B( | |

|3 |( | | |

| |R2 |+00000 |0|0100 |

| |B |10010 | |

| | |((( | |

| |R3 |10010 |0|0101 |

|4 |( | | |

| |R3 |-00100 |01010 |

| |B |10010 | |

| | |((( | |

| |R4 |10010 |01011 |

|псевдо- |R4 | -10010 | |

|коррекция|B |10010 | |

| |R |((( | |

| | |00000 | |

|коррекция| | |+01011 |

|частного | | |1 |

| | | |((( |

| | | |01100 |

Приведенный пример иллюстрирует ряд дополнительных нюансов деления в

дополнительных кодах :

На четвертом шаге при сдвиге остатка произошло искажение его знака.

Выполняемое действие над остатком должно определяться его знаком для

предыдущего шага (до сдвига). В схемной реализации этот факт необходимо

учитывать путем применения модифицированного кода с удвоенным знаковым

разрядом. В связи с этим разрядность регистра для хранения остатка и

частного должна быть 2n+1, а разрядность сумматора (сумматора вычитателя)

n+1. При получении нулевого остатка на коком либо шаге деления для

следующего шага остаток будет равен делителю. При его сдвиге влево он

станет равен удвоенному делителю. И после вычитания делителя на следующем

шаге он снова станет равен делителю. Таким образом в конце операции после

выработки всех цифр частного остаток будет не нулевым, а равным делителю.

Если при этом его знак совпадает со знаком делимого, то в соответствии с

основным алгоритмом деления он не подлежит коррекции.

Для устранения этого недостатка алгоритма во всех случаях совпадения

знака остатка и делимого выполняется попытка так называемой

псевдокоррекции. Если после этой коррекции остаток равен нулю, то он

является истинным, если же остаток не равен нулю, то требуется его

восстановление обратным по сравнению с псевдокоррекцией действием с

делителем.

Страницы: 1, 2, 3

МЕНЮ

Конспект лекций по дискретной математике

ИНТЕРЕСНОЕ