В качестве кандидата на минимум при анализе текущего среза данных рассматриваются те ячейки памяти, у которых бит равен 0. При поиске минимума также возникают ситуации особые 1-го и 2-го рода:
1. особая ситуация при единичном срезе данных;
2. особая ситуация, при которой нулевые биты в срезе данных соответствуют единичным битам в предыдущей поисковой функции.
1 | Fmin | |||||||
F0 | F1 | F2 | F3 | F4 | ||||
S 0 | 1 |
При организации поиска по 3-му срезу данных возникает особая ситуация 1-го рода, поэтому F3 не вычисляется, а берется от предыдущего значения. Рассмотрим синтез ячейки накопителя для операции поиска минимума.
M1j | Fminij-1 | Si | Qij | Fminij | |
т. к. М1i = 0 | |||||
Т. к. Fi-1j = 0 | |||||
Рис. 21.
|
|
Операции ассоциативного поиска всех больших (F>), F<, F≥, F≤.
Особенность реализации данных операций связана с вычислением по каждому срезу данных двух поисковых функций.
M1i |
Vi,j |
Zi,j |
Яij Qij |
Ai |
M1j |
Zi-1,j |
Vi-1,j |
(A > Q первый раз)
(A ≤ Q во всех предыдущих разрядах)
В данные функции необходимо ввести бит маски. Окончательное решение об установлении отношений F>, F<, F≥, F≤ выносится на основе анализа поисковой функции для последнего среза данных.
Vm | Zm | Соотношение |
Q < A | ||
Q = A | ||
Q > A | ||
Операции поиска ближайшего большего и ближайшего меньшего.
Особенность данных операций определяется тем, что они реализуются в 2 этапа.
Fбб = min (>)
I этап – находятся все большие
II этап – среди них ищется минимум
Fбм = max (<)
I этап – ищутся минимумы
II этап – ищется среди них максимум
После выполнения первого этапа найденное значение поисковой функции записывается в маску Mz. Второй этап будет осуществляться только для тех ячеек накопителя, у которых M2i = 1.
Лекция №9