Древовидная диаграмма

Cтраница 2

Более формальный, но все же эвристический подход к задаче состоит в том, чтобы графически изобразить число получаемых из иерархического дерева кластеров как функцию коэффициента слияния или смешения, равного числу способов объединения различных объектов в кластер. Значения коэффициентов слияния показаны вдоль оси У древовидной диаграммы. [16]

Добавленное измерение времени в древовидной диаграмме ( по сравнению с диаграммой состояния) допускает динамическое описание кодера как функции конкретной входной последовательности. Однако заметили ли вы, что при попытке описания с помощью древовидной диаграммы последовательности произвольной длины возникает проблема. Число ответвлений растет как 2L, где L - это количество кодовых слов ветвей в последовательности. При большом L вы бы очень быстро исписали бумагу и исчерпали терпение. [17]

Если мы проделаем это для древовидной структуры, показанной на рис. 7.6, получим иную диаграмму, называемую решетчатой. Решетчатая диаграмма, которая использует повторяющуюся структуру, дает более удобное описание кодера, по сравнению с древовидной диаграммой. [18]

Иерархия грамматик, языков и канонических систем. [19]

Меры сложности будут использоваться для сравнения формул или языков. Возможными мерами являются длина доказательства, длина строки или высота ( длина самого длинного пути, состоящего из ветвей) древовидной диаграммы вывода. [20]

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

Первое - все эти методы просматривают матрицу сходства размерностью NXN ( где N - число объектов) и последовательно объединяют наиболее схожие объекты. Второй важный момент, на который стоит обратить внимание, состоит в том, что последовательность объединений кластеров можно представить визуально в виде древовидной диаграммы, часто называемой дендрограммой. Каждый шаг, на котором объединялась пара объектов, представляется ветвью этого дерева. Заметьте, что дерево изображает иерархическую организацию связей между шестью точками данных. На самом нижнем уровне все шесть точек независимы; иа следующем уровне они объединяются в одну группу и три независимых объекта; наконец, на самом верхнем уровне они все объединяются в одну большую группу. [22]

Теперь задача декодирования заключается в выборе пути вдоль дерева на рис. 1.6 или решетки на рис. 7.7 таким образом, чтобы Уи ( т) было максимальным. При древовидном представлении кода игнорируется то, что пути снова объединяются. Поэтому декодирование полученных последовательностей, основанное на принципе максимального правдоподобия с использованием древовидной диаграммы, требует метода грубой силы или исчерпывающего сопоставления 2L накопленных логарифмических метрик правдоподобия, описывающих все варианты возможных последовательностей кодовых слов. Поэтому рассматривать декодирование на основе принципа максимального правдоподобия с помощью древовидной структуры практически невозможно. В предыдущем разделе было показано, что при решетчатом представлении кода декодер можно построить так, чтобы можно было отказываться от путей, которые не могут быть кандидатами на роль максимально правдоподобной последовательности. Путь декодирования выбирается из некоего сокращенного набора выживших путей. [23]

Страницы: 1 2