Операция ассоциативного поиска максимума.

Ячейка считается кандидатом на максимум, если в текущем разрядном срезе данных Q_ij = 1.

Рис.16

Мы не можем выделить значение F₃, так как данный срез нулевой. Поэтому F₃, будет взято от предыдущей функциии.

При организации поиска по 3-му разрядному срезу обнаруживается особая ситуация 1-го рода. Ее суть: нулевой срез данных не позволяет определить кандидатов на максимум. В этом случае F₃ принимается равным F₂. Если при поиске максимума для некоторой функции F_ij^max значение равно 0, то для всех бит, расположенных правее, в i-й ячейке также формируется значение ноль. Это так называемый “бегущий ноль”.

Первый бит маски равен 0 => F₁ не вычисляется, а берется от предыдущего, т. е. F₀.

Если старший бит маски М₁ равен 0, то для операции поиска максимума F₁ = F₀ =

В данном случае как максимум найдены 2-я и 6-я ячейки, содержащие в своих трех младших разрядах максимальные значения 111. При поиске максимума возникают две особые ситуации:

1. особая ситуация при нулевом разрядном срезе данных;

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

Рассмотрим пример поиска максимума при особой ситуации второго рода.

Рис.15

F₃ нельзя вычислить => берем ее как предыдущую, т. е. F₂.

При организации поиска по 3-му срезу данных возникает особая ситуация 2-го рода. Она заключается в том, что формально 1-я и последняя ячейки не могут быть кандидатами на максимум. Это приводит к возможности формирования F₃ как нулевого вектора. Для исключения подобной ситуации F₃ не вычисляется, а берется от предыдущей функции.

Выпишем функции F₂ и 3-й разрядный срез.

Анализ 2-х векторов показывает, что особая ситуация 2-го рода возникает при побитовой инверсии текущего среза данных и предыдущей поисковой функции.

Особая ситуация маска равна нулю

2-го рода

При организации поиска максимума для каждой F_i функции необходимо дополнительно вычислять переменную S. Эта переменная определяет отсутствие или наличие особой ситуации 1-го или 2-го рода.

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

Рис.18

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