Ячейка считается кандидатом на максимум, если в текущем разрядном срезе данных Qij = 1.
М1 | Fmax | ||||||||
бегущий ноль | |||||||||
F1 | F2 | F3 | F4 |
Рис.16
Мы не можем выделить значение F3, так как данный срез нулевой. Поэтому F3,будет взято от предыдущей функциии.
При организации поиска по 3-му разрядному срезу обнаруживается особая ситуация 1-го рода. Ее суть: нулевой срез данных не позволяет определить кандидатов на максимум. В этом случае F3 принимается равным F2. Если при поиске максимума для некоторой функции Fijmax значение равно 0, то для всех бит, расположенных правее, в i-й ячейке также формируется значение ноль. Это так называемый “бегущий ноль”.
М1 | Fmax | |||||||
F0 | F1 | F2 | F3 | F4 |
Первый бит маски равен 0 => F1 не вычисляется, а берется от предыдущего, т. е. F0.
|
|
Если старший бит маски М1 равен 0, то для операции поиска максимума F1 = F0 =
В данном случае как максимум найдены 2-я и 6-я ячейки, содержащие в своих трех младших разрядах максимальные значения 111. При поиске максимума возникают две особые ситуации:
1. особая ситуация при нулевом разрядном срезе данных;
2. особая ситуация при нулевых битах поисковой функции и единичного бита предыдущего среза данных.
Рассмотрим пример поиска максимума при особой ситуации второго рода.
М1 | Fmax | |||||||
F1 | F2 | F3 | F4 |
Рис.15
F3 нельзя вычислить => берем ее как предыдущую, т. е. F2.
При организации поиска по 3-му срезу данных возникает особая ситуация 2-го рода. Она заключается в том, что формально 1-я и последняя ячейки не могут быть кандидатами на максимум. Это приводит к возможности формирования F3 как нулевого вектора. Для исключения подобной ситуации F3 не вычисляется, а берется от предыдущей функции.
Выпишем функции F2 и 3-й разрядный срез.
F2 | Р3 |
Анализ 2-х векторов показывает, что особая ситуация 2-го рода возникает при побитовой инверсии текущего среза данных и предыдущей поисковой функции.
|
|
М1 | Fmax | |||||||
F1 | F2 | F3 | F4 | |||||
S 0 | 1 |
Особая ситуация маска равна нулю
2-го рода
При организации поиска максимума для каждой Fi функции необходимо дополнительно вычислять переменную S. Эта переменная определяет отсутствие или наличие особой ситуации 1-го или 2-го рода.
Рассмотрим ячейку накопителя для операции поиска максимума и выполним ее формальный синтез.
Рис.18
Ячейка, как черный ящик, определяется с помощью таблицы, зависящей от 4-х входов.
M1j | Fmaxij-1 | Si | Qij | Fmaxij | |
т. к. М1i = 0 (берем предыдущее значение) | |||||
не было особой ситуации | |||||
была особая ситуация => берем предыдущее значение | |||||