WikiDer > Алгоритм Блахута – Аримото

В Алгоритм Блахута – Аримото, часто используется для обозначения класса алгоритмов для численных вычислений либо теоретическая информация емкость канала или скорость искажения функция источника. Они есть итерационные алгоритмы которые в конечном итоге сходятся к оптимальному решению выпуклая оптимизация проблема, которая связана с этими теоретико-информационными концепциями.

История и применение

В случае пропускная способность канала, алгоритм был независимо изобретен Сугуру Аримото^[1] и Ричард Блахут.^[2] В случае сжатия с потерями соответствующий алгоритм был изобретен Ричард Блахут. Алгоритм наиболее применим к случаю произвольных конечных алфавитных источников. Была проделана большая работа по распространению его на более общие примеры проблем.^[3][4]Недавно была предложена версия алгоритма, который учитывает непрерывные и многомерные выходы для приложений в сотовой сигнализации.^[5] Существует также версия алгоритма Блахута – Аримото для направленная информация.^[6]

Алгоритм

Допустим, у нас есть источник ${ displaystyle X}$ с вероятностью ${ displaystyle p (x)}$ любого данного символа. Мы хотим найти кодировку ${ displaystyle p ({ hat {x}} | x)}$ что порождает сжатый сигнал ${ displaystyle { hat {X}}}$ от исходного сигнала при минимизации ожидаемого искажение ${ Displaystyle langle d (х, { шляпа {х}}) rangle}$, где математическое ожидание берется из совместной вероятности ${ displaystyle X}$ и ${ displaystyle { hat {X}}}$. Мы можем найти кодирование, которое минимизирует функционал искажения скорости локально, повторяя следующую итерацию до сходимости:

${ displaystyle p_ {t + 1} ({ hat {x}}) = sum _ {x} p (x) p_ {t} ({ hat {x}} | x)}$

${ displaystyle p_ {t + 1} ({ hat {x}} | x) = { frac {p_ {t} ({ hat {x}}) exp (- beta d (x, { шляпа {x}}))} { sum _ { hat {x}} p_ {t} ({ hat {x}}) exp (- beta d (x, { hat {x}}) )}}}$

где ${ displaystyle beta}$ - это параметр, связанный с наклоном кривой скорость-искажение, на которую мы ориентируемся, и, таким образом, связан с тем, насколько мы отдаем предпочтение сжатию по сравнению с искажением (более высокое ${ displaystyle beta}$ означает меньшее сжатие).

Рекомендации