Cтраница 2
Для решения нелинейной целочисленной задачи оптимального размещения экземпляров логических записей по страницам памяти разработаны точный и приближенный алгоритмы ее решения. Точный алгоритм поставленной задачи основан на схеме ветвей и границ. Правило ветвления и выражения для вычисления оценок приведены ниже. Приближенный алгоритм основан на разделении общей задачи (5.3.7), (5.3.8) - (5.3.10) на ряд последовательно решаемых локальных задач оптимизации и композиции полученных локальных решений. [16]
Несмотря на то что диаграммы состояний полностью описывают кодер, по сути, их нельзя использовать для легкого отслеживания переходов кодера в зависимости от времени, поскольку диаграмма не представляет динамики изменений. Древовидная диаграмма ( tree diagram) прибавляет к диаграмме состояния временное измерение. Древовидная диаграмма сверточного кодера, показанного на рис. 7.3, изображена на рис. 7.6. В каждый последующий момент прохождения входного бита процедура кодирования может быть описана с помощью перемещения по диаграмме слева направо, причем каждая ветвь дерева описывает кодовое слово на выходе. Правило ветвления для нахождения последовательности кодовых слов следующее: если входным битом является нуль, то он связывается со словом, которое находится путем перемещения в следующую ( по направлению вверх) правую ветвь; если входной бит - это единица, то кодовое слово находится путем перемещения в следующую ( по направлению вниз) правую ветвь. Предполагается, что первоначально кодер содержал одни нули. [17]