ЛОКАЛЬНОГО КОДИРОВАНИЯ ПРИНЦИП

— общий подход к построению методов синтеза схем, реализующих булевы функции (или вектор-функции) из специальных классов функций, основанный на обладающем особыми свойствами кодировании функций наборами из нулей и единиц. Для построения асимптотически оптим. метода синтеза кодирование должно быть асимптотически оптимальным: длина кода должна быть асимптотически равна (двоичному) логарифму числа рассматриваемых ф-ций (от аргументов). Кодирование должно быть локальным в том смысле, что для вычисления ф-ции на каждом конкретном наборе а значений аргументов (для «декодирования») достаточно знать сравнительно небольшой отрезок кода- Декодирование также должно осуществляться сравнительно просто. Во-первых, сравнительно просто (в смысле сложности схемной реализации) должны вычисляться «координаты» отрезка кода; напр., номер отрезка кода, если код разбит на отрезки одинаковой длины; номер первого разряда и длина отрезка, если имеют различную длину. Во-вторых, по набору а, отрезку кода быть может, «координатам» отрезка кода) сравнительно просто должно вычисляться значение

Схема вычисления по принципу локального копирования.

В общем виде схема, построенная для в соответствии с Л- к. п., состоит из нескольких подсхем (рис.). Подсхема А по набору а вычисляет координаты отрезка кода. Подсхема В по координатам отрезка кода выдает часть кода (фиксированной длины), содержащую требуемый отрезок его. Подсхема С выделяет из части кода требуемый отрезок кода, подсхема D вычисляет f (а). Обычно подсхема С является универсальной (не зависящей ни от класса F реализуемых ф-ций, ни от конкретной ф-ции ); подсхемы А и D не зависят от но зависят от F; подсхема В зависит от эта подсхема содержит осн. часть элементов всей схемы. Кодирование не обязательно должно быть взаимно однозначным. В небольшом количестве дополнительная информация может содержаться в подсхеме декодирования D. Л. к. п. фактически сводит задачу синтеза схем к задаче кодирования ф-ций, трудность задачи в этом случае сосредоточена здесь. Особенно удобен Л. к. п. в том случае, если схемы имеют достаточно большие возможности (схемы из функциональных элементов, логические сети и алгоритмы)

Примеры асимптотически оптим. локального кодирования.

1. Пусть симметрических ф-ций Кодом ф-ции является набор , где значение функции на (любом) наборе с i единицами.

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

3. Пусть набор из нулей и единиц, и ЗЛП — класс вектор-функций удовлетворяющих условию: если то Нелокальный (но асимптотически оптимальный) код вектор-функции F — это набор длины имеющий нулей и единиц, в котором число единиц, стоящих перед нулем, равно где . Пусть набор я разбит на частей: имеет длину кроме набор длины n такой, что есть число единиц в наборе . Асимптотически оптим. локальный код для F (при ) - это набор

Б. Лупанов.