Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 67
Текст из файла (страница 67)
Благодаря тому, что Т квантуется с шагом А, допусиэется небольшое убывание с(1) без пересечения порога. ')вэю р нз» замарая, аяэраз з Е за щюрэ а В алгоритме Фана требуется. чтобы я ребер, выходящих из каждой вершины, были перенумерованы согласно некоторому правилу упорядочивааия Это правило ставит в соответствие каждому ребру индекс с, ! = О, ..., д — !. Нет необходимости запоминать зги индексы в наждом ребре; достаточно знать правило, ао которому при возвращении алгоритма в вершину па ребру с известным индексом ! он мажет переупорялочить ребра, найти ребро ! н затем найти ребро с индексом ! 1. Наиболее общим правилам является правила минимального расстояния Ребра упорядочиваются в соответствии с их расстояниями до соответствующего кадр» заданного слова, а неопределенность разрешается по любому удобному подправилу.
Однако алгориты будет правилгшо работать при любом фиксированном порядке ребер Фиксированное правило упорядочввания может привести к более длительному поиску назад. вперед, но освобождает от необкоднмости вычистения и веревычисления при достижения каждой вершины Какое прапило упорядочивания более просто в реализации, зависит от деталей конструкция. Длв простоты понимания структуры алгоритма правило упорядочиванкя лучше оставить несколько неопределенным, предноложвм только, что в каждой вершине ребра, ближайшее к ребру данных, занумеровано первым Алгоритм будет отыскивать ребра из каждой вершины в соответствии с этим правилом. Основанная на регистрах сдвига реализация алгоритма Фано показана ва рис.
12.10. Основой реализации является копия ма|нины с конечным числалг состояний, которая на рисунке представлена регистрами сдвига, к ним добавлено несколько вспомогательных запоминающих регистров. Алгоритм пытается подать символы в копию машины с конечным числом состояний таким образом, чтобы на ее выходе сформировалась последовательность, достаточно близкая н заданной последовательности. На каждой итерапни алгоритм имеет доступ к самому последнему кадру, введенному в копию машины с конечным числом сашояний Он может изменить символ в этом кадре, вернуться к более раннему кадру или ввести новый кадр.
Что именно делать, алгоритм ре. знает на основе сравнения величины перекошенного расстояния с(!) и текущего значения порога Т. В упрощенной форме алгоритм Фана показан на рис 12.11. Практические детали, связанные с ионечностью размеров буфера, временно игнорируются Если последоватсдьность данных близка к генерируемой носледаватедьности, то алгоритм будет циркулировать па правой петле на рис. 12.11, и при каждом цикле все регистры на рис.
12 1О сдвигаются на адин кадр вправо. До тех пор пака с(!) остается выше порога, алгоритм продолжает сдвигаться вправо и повышать 12Л А р Ф 416 Га. 12 Б сюп* лгарю ю р ммке н х р щт Р 12.!а.реюмцвя р Фк юр р л порог так, чтобы тат оставался блнзкям к 1 )1) Волн 1 )1) спускается ниже порога, та адгорнтн Фана проверяет альтернативные ребра агата кадра. пытаясь найти то ребро, катеров делает 141) выше порога. Волн ему не удается сделать этого, то он возвращеется назад.
Как мы увидим в дальнейшем, если алгоритм начал возвращаться обратно, то логика заставят двигаться его назад до тех пор, пока не буде~ найлен альтернатнваый путь, который находятся над текущим значением порога, нлн вершина, в которой был установлен текущий порог. Затем алгорнтьг снова движется . ваеред с уже пониженным значением порога; но теперь, «ак мы убелимся позднее, порог не повышается до тех пор, пока атгоритм не придет а новую, ранее не рассматривавшуюся вершнну.
Каждый раз, когда алгорнтм, двигаясь ваеред, посещает ра~ее всследопзвшуюся вершину, он имеет меньший порог. Алгоритм некогда не посетят одну к ту же верп1нпу дважды с пдннаковым, значением порога. Влеровательно, ан мажет насещагь любую вер- ' шину только конечное число раз. Это поведение гарантирует нас от запиклнваггия алгоритма; он должен продолжать движение вперед 1ю последовательности данных. Рв . 12.11. Аа нрю ею Е емс ь ююр Ф а . з ° к. р Теперь необходимо доказать два сделанных ранее утвержденна: 1) если алгоритм Фана не может найтн зльтернативный путь, то он движется назад к вершине, в которой была установлена тенущее значение порога, я понижает его; 2) алгоритм не будет повмшать порог до тех пор, пана не достигнет ранее не исследовавшегося узла Чта касается первого утверждения, очевидна, что если алгоритм Фана не мажет найти ребра, ат которого оп должен двигаться вперед, то ан в коппс концов должен вернут ся в указанную вершину.
Но если в предшествующем некоторой вершине падре перекошенное расстояние 1)1 — 1) меныпе текущего зяачення порога Т, то порог бмл увелнчен в 1-м кадре. В блок-схему на ряс. !2.! ! включен этот тест для нахождення вершины, в которой был установлен текущей порог; теперь в этой вершине порог уменьшается. Ыв зг р. 4!З Г».12.»»мэ ее ер»н и р ш»псдвзт 4!Э Для доказательства второго утвержден»я заметим, что посл тога, как порог поннжен на Ь, алгоритм Фана ищет ребра в то же порядке, что н до.этого, до тех пор, пока не найдет место з котором перекошенное расстояние, ранее бывшее мепьше п рога, станов»той больше него. Да этого места порог Т нзменнтьс не может.
Это происходят нз-за того, что после поннженпя п рога на Ь перекошенное расстояние в тех вершинах, где он превышало первона'шльный порог, никогда не будет мень Т + Ь. Когда алгорнтм продвигается в новую часть дерева, он в конце концов достигает состояния, в котором !(! — 11 < < Т .1-Ь п 1(В )~ Т. В этой точке порог повышается. Это является тестом для определения того, что алгорнтм посети новую вершину » нет необходимости помнить точно все посещенные ранее вершнны.
Этот тест включен в схему на рнс. 12.1!. Алгоритм Фано завнснт от двух параметров р' н Ь, которые можно выбрать моделнраваннем на ЭВМ. Практически необходнма врем» от времен» уменыпать ! (1! п Т так, чтобы этп числ не станазнлнсь слвшном больш»мн. Вычитание нз обенх велнчн некоторого числа, кратного Ь, не впаяет на последующне вы числення.. В практической реализация существенен также выбор шн рины окна б. На ряс. 12.12 приведена более полна» блок-схем алгоритма Фано, о ображающая важную раль параметра й Каждый раз, когда саммй старый кадр достигает понца буфера что отмечается указателем кадра, ан выходит нз окна, а указа тель кадра изменяется тан, чтобы всегда указывать на самы старый нмеющяйся кадр.
Иногда алгар»тм может попытатьс вернуться назад тан далеко, что отыскиваемый им кадр о»азы настоя уже выведен»ым. Таксе явление называется переполн нием буфера н случаетс», когда указатель кадров прап»ма отрицательные значснпя. Перепоанен»е буфера является существеняым ограннченнем алгорнтмз Фано. Во м»агнх прялож пнях вероятносп переполнепня буфера так медленно убывает с ростом размера буфера, что вне эванс»мости от того, насколько большим выбран буфер, зта проблема полностью ке сннмаетсн' Существует два способа управления переполвеннем буфер Наиболее надежным является пернодическая подача на зха машины с конечным чнслом состояний известной паследавательй ности переходов, для»а которой равна длине кодового аграннз. ченвя.
Если буфер переполнятся, то алгорнтм декларирует отпав н ждет начала следующей известной ему последовательности прп нотором оп снова начинает работу. Все даннме, поступ»вш между моментом переполнения буфера » следующнм включеннем теряются. В случае, когда длина кодового ограничения »е слншпом в ля»а, альтернатнвный путь состоит в движении уназателя к Р !2,!2 й. 2» Пз»с ров вперед. Если алгоритму удастся найти правильную вершину, то он сможет пере»встроиться. Это возможно, еслн заданная последовательность содержнт достаточно длинный сегмент, в котором генерируемая последовательность с ней в точност» савпа- 2»ст.
Зваачв !2.!. Л рос го бор тэт мр » Пз з. зу », а рззз » мау д й»»от»й пехшта»ззд к гым»з м! 14 !ч '2 ,а: ' Й! -!) лб з, з з з о, с с и -с.-л г( о ('= ! -! -! е ° В г з — з, г, —. з. — з* ,=5, г,-г, з„ г, о -г, Ф о и - с О,. = и, — ю о =с Ф 420 Г» !2. Бысф е р и пгж а и рмлстю в д р у !2.2. П вг рн ь привед й р с 12.7 при ер дла д й пюмд нюги — гспп юаовв юоию.. 12.2.
Ллюр Вптерб ы бюь юпр гр мнроэю в д, кшо м д и ипу й -й ржжнзапо шммжн в юсиа,чю ра 2.4. 2 в жн ышнх в алюр В рби !прис= 2) пу й о юлию шраю ( пюьзул гик р л ю, как указзтюи б ы р зы) хе управлеа н намиг ю д аз оргпма Вн рбн, ка ор Мюш н О диыс гь чвгыва ю дой имран»и 2тз-бнюв к ок Звмечанп» румшим ю бкн.нла р юдачуд д р вани р ых н дов о рнршнро гь кэк мпж у а и рв «е (или и д р у) Бюьши й р, 'л й д а нькшобыг пиал р. ею р ы б л вели В э «рфгом П967) н падре аны В ейфр н м(196!).дню й р эвнгмсвнполу пуф ной963),3 га рою (1966) джелвю«а (!969) р зр б к джю «(1%6) н Фарии (197 юж р б ы Бывюл' Кштюло (!976) и Х ую и Ферио о э (Ю жс прод нули нс а ню аан ого аопрюа Й ию ж ние а е оно тс н ваши с д «ы Гюлаг р м (!966) юнем этого а гари пювх, м а «а рьюног оригма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
