Связь со свободной энергией - алгоритм суммы-произведения связан с вычислением свободной энергии в термодинамике. Пусть Z будет статистической суммой. Распределение вероятностей

P (X) = 1 Z ∏ fjfj (xj) {\ displaystyle P (\ mathbf {X}) = {\ frac {1} {Z}} \ prod _ {f_ {j}} f_ {j} (x_ {j})}

(согласно представлению факторного графа) можно рассматривать как меру внутренней энергии, присутствующей в системе, вычисляемой как

E (X) = журнал ⁡ ∏ fjfj (xj). {\ displaystyle E (\ mathbf {X}) = \ log \ prod _ {f_ {j}} f_ {j} (x_ {j}).}

Тогда свободная энергия системы равна

F = U - H = ∑ XP (X) E (X) + ∑ XP (X) журнал ⁡ P (X). {\ Displaystyle F = UH = \ сумма _ {\ mathbf {X}} P (\ mathbf {X}) E (\ mathbf {X}) + \ sum _ {\ mathbf {X}} P (\ mathbf {X }) \ log P (\ mathbf {X}).}

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

Распространение обобщенных убеждений (GBP) - распространение убеждений алгоритмы обычно представлены в виде уравнений обновления сообщений на факторном графе, включая сообщения между переменными узлами и их соседними факторными узлами, и наоборот. Рассмотрение сообщений между регионами в графе - это один из способов обобщения алгоритма распространения убеждений. Есть несколько способов определить набор регионов на графе, которые могут обмениваться сообщениями. Один метод использует идеи, представленные в физической литературе, и известен как Кикучи.

Улучшения в производительности алгоритмов распространения убеждений также достигаются путем нарушения симметрии реплик в распределениях полей (сообщений). Это обобщение приводит к новому виду алгоритма, называемому (SP), который оказался очень эффективным в NP-полных задачах, таких как выполнимость и раскраска графа.

. кластерный вариационный метод и алгоритмы распространения опроса - это два разных улучшения распространения убеждений. Имя (GSP) ожидает присвоения алгоритму, объединяющему оба обобщения.

Распространение убеждений по Гауссу (GaBP) - р

---

аспространение убеждений по Гауссу является вариантом алгоритма распространения убеждений, когда лежащие в основе распределения являются гауссовыми. Первой работой по анализу этой специальной модели была основополагающая работа Вейсса и Фримена.

Алгоритм GaBP решает следующую проблему маргинализации:

P (xi) = 1 Z ∫ j ≠ i exp ⁡ (- 1 / 2 x TA x + b T x) dxj {\ displaystyle P (x_ {i}) = {\ frac {1} {Z}} \ int _ {j \ neq i} \ exp (-1 / 2x ^ { T} Ax + b ^ {T} x) \, dx_ {j}}

где Z - константа нормализации, A - симметричная положительно определенная матрица (матрица обратной ковариации, также известная как матрица точности) и b - вектор сдвига.

Аналогично, можно показать, что с использованием модели Гаусса решение проблемы маргинализации эквивалентно задаче назначения MAP :

argmax x P (x) = 1 Z ехр ⁡ (- 1/2 x TA x + b T x). {\ displaystyle {\ underset {x} {\ operatorname {argmax}}} \ P (x) = {\ frac {1} {Z}} \ exp (-1 / 2x ^ {T} Ax + b ^ {T } x).}

Эта задача также эквивалентна следующей задаче минимизации квадратичной формы:

min x 1/2 x TA x - b T x. {\ displaystyle {\ underset {x} {\ operatorname {min}}} \ 1 / 2x ^ {T} Ax-b ^ {T} x.}

Что также эквивалентно линейной системе уравнений

А х = b. {\ displaystyle Ax = b.}

Сходимость алгоритма GaBP легче анализировать (по сравнению с общим случаем BP), и есть два известных достаточных условия сходимости. Первый был сформулирован Weiss et al. в 2000 году, когда информационная матрица A доминирует по диагонали. Второе условие сходимости сформулировано Johnson et al. в 2006 г., когда спектральный радиус матрицы

ρ (I - | D - 1/2 A D - 1/2 |) < 1 {\displaystyle \rho (I-|D^{-1/2}AD^{-1/2}|)<1\,},

где D = diag (A). Позже Су и Ву установили необходимые и достаточные условия сходимости для синхронного GaBP и затухающего GaBP, а также другое достаточное условие сходимости для асинхронного GaBP. Для каждого случая условие сходимости включает проверку:

1) непустого набора (определяемого A);

2) спектрального радиуса определенной матрицы меньше единицы;

3) проблемы сингулярности (при преобразовании сообщения BP в убеждение) не встречается.

Алгоритм GaBP был связан с областью линейной алгебры, и было показано, что алгоритм GaBP можно рассматривать как итерационный алгоритм для решения линейной системы уравнений Ax = b, где A - информационная матрица, а b - вектор сдвига. Эмпирически показано, что алгоритм GaBP сходится быстрее, чем классические итерационные методы, такие как метод Якоби, метод Гаусса – Зейделя, последовательная избыточная релаксация и другие. Кроме того, показано, что алгоритм GaBP невосприимчив к числовым проблемам предварительно обусловленного метода сопряженного градиента

---

Синдромное декодирование АД -предыдущее описание алгоритма ВР называется декодированием на основе кодовых слов, который вычисляет приблизительную предельную вероятность P (x | X) {\ displaystyle P (x | X)} ​​ , учитывая полученное кодовое слово X {\ displaystyle X} . Существует эквивалентная форма, которая вычисляет P (e | s) {\ displaystyle P (e | s)} , где s {\ displaystyle s} - синдром полученного кодового слова X {\ displaystyle X} и e {\ displaystyle e} - декодированная ошибка. Декодированный входной вектор: x = X + e {\ displaystyle x = X + e} . Этот вариант изменяет только интерпретацию функции масс f a (X a) {\ displaystyle f_ {a} (X_ {a})} . Явно сообщения следующие:

∀ xv ∈ D om (v), μ v → a (xv) = P (X v) ∏ a ∗ ∈ N (v) ∖ {a} μ a ∗ → v (xv). {\ Displaystyle \ forall x_ {v} \ in Dom (v), \; \ mu _ {v \ to a} (x_ {v}) = P (X_ {v}) \ prod _ {a ^ {*} \ in N (v) \ setminus \ {a \}} \ mu _ {a ^ {*} \ to v} (x_ {v}).}

где P (X v) {\ displaystyle P (X_ {v})} - априорная вероятность ошибки для переменной v {\ displaystyle v} ∀ xv ∈ D om (v), μ a → v (xv) = ∑ xa ′: xv ′ = xv δ (синдром (xv ′) = s) ∏ v ∗ ∈ N (a) ∖ {v} μ v ∗ → a (xv ∗ ′). {\ displaystyle \ forall x_ {v} \ in Dom (v), \; \ mu _ {a \ to v} (x_ {v}) = \ sum _ {\ mathbf {x} '_ {a}: x '_ {v} = x_ {v}} \ delta ({\ text {синдром}} ({\ mathbf {x}}' _ {v}) = {\ mathbf {s}}) \ prod _ {v ^ {*} \ in N (a) \ setminus \ {v \}} \ mu _ {v ^ {*} \ to a} (x '_ {v ^ {*}}).}

Этот синдром - декодер на основе не требует информации о полученных битах, поэтому может быть адаптирован к квантовым кодам, где единственной информацией является синдром измерения. В двоичном случае, xi ∈ {0, 1} {\ displaystyle x_ {i} \ in \ {0,1 \}} , эти сообщения могут быть упрощены вызвать экспоненциальное уменьшение 2 | {v} | + | N (v) | {\ displaystyle 2 ^ {| \ {v \} | + | N (v) |}}в сложности

Определить логарифмическое отношение правдоподобия lv = log ⁡ uv → a (xv = 0) uv → a (xv = 1) {\ displaystyle l_ {v} = \ log {\ frac {u_ {v \ to a} (x_ {v} = 0)} {u_ {v \ к a} (x_ {v} = 1)}}} , L a = log ⁡ ua → v (xv = 0) ua → v (xv = 1) {\ displaystyle L_ {a} = \ log {\ frac {u_ {a \ to v} (x_ {v} = 0)} {u_ {a \ to v} (x_ {v} = 1)}}}, затем

---

v → a: lv = lv (0) + ∑ a ∗ ∈ N (v) ∖ {a} (L a ∗) {\ displaystyle v \ to a: l_ {v} = l_ {v} ^ {(0)} + \ sum _ {a ^ {*} \ in N (v) \ setminus \ {a \}} (L_ {a ^ {*}})} a → v: L a = (- 1) sa 2 tanh - 1 ⁡ ∏ v ∗ ∈ N (a) ∖ {v} tanh ⁡ (lv ∗ / 2) {\ displaystyle a \ to v: L_ {a} = (- 1) ^ {s_ {a}} 2 \ tanh ^ {- 1} \ prod _ {v ^ {*} \ in N (a) \ setminus \ {v \}} \ tanh (l_ {v ^ {*}} / 2)}

где lv (0) = журнал ⁡ (P (xv = 0) / P (xv = 1)) = const {\ displaystyle l_ {v} ^ {(0)} = \ log (P (x_ {v} = 0) / P (x_ {v} = 1)) = {\ text {const}}}

Апостериорное логарифмическое отношение правдоподобия можно оценить как lv = lv (0) + ∑ a ∈ N (v) (L a) {\ displayst yle l_ {v} = l_ {v} ^ {(0)} + \ sum _ {a \ in N (v)} (L_ {a})}

Заключение

Современные исследования в основном сосредоточены на создании LDPC-кодов с улучшенными характеристиками, а также методов их декодирования. Например, кодов на базе евклидовых геометрий. Для таких кодов также создаются и развиваются специальные методы декодирования и ускоренного декодирования с приемлемыми потерями в вероятности декодирования, и они показывают неплохие результаты. Дальнейшее развитие в рамках данной проблематики заключается в отработке современных алгоритмических решений в области кодирования и декодирования LDPC-кодов, а также в эмпирической проверке результатов современных теоретических исследований в этой области.

Таким образом, при проектировании декодера необходимо учитывать множество факторов, чтобы добиться компромисса между различными параметрами, такими как скорость работы, энергопотребление, задержка, приближение к пределу Шеннона, порог ошибки, площадь кристалла (в случае ASIC) . Также важным является время и стоимость разработки и производства. Перспективными направлениями в исследовании декодеров в ближайшее время можно считать построение кодов, разработку архитектур и алгоритмов декодирования, а также многоскоростные и реконфигурируемые декодеры.

Список используемой литературы

1. 
   D. MacKay and R. Neal, “Good codes based on very sparse matrices”, 1995 William E. Ryan, “An introduction to LDPC codes”, 2003 Sarah J. Johnson, “Iterative Error Correction”, 2010 Engling Yeo, BorivojeNikoli, and VenkatAnantharam, “Architectures and Implementations of Low-Density
   
2. 
   2. Parity Check Decoding Algorithms”, 2002 TinooshMohsenin and Bevan Baas, “Trends and Challenges in LDPC Hardware Decoders”, 2009
   
3. 
   S. Y. Chung, G. D. Forney, T. J. Richardson, R. Urbanke, “On the design of low-density parity-check codes within 0.0045dB of the Shannon limit”, 2001 T. J. Richardson, “Error Floors of LDPC Codes”, 2003
   
4. 
   http://ru.wikipedia.org/wiki/LDPC
   
5. 
   http://www.mtdbest.ru/articles/obzor_dvoichnie_kodi_2.pdf
   
6. 
   Овчинников А. К вопросу о построении LDCP-кодов на основе евклидовых геометрий // Вопросы передачи и защиты информации: Сборник статей под ред. А. Крука. СПбГУАП. СПб., 2006.
   

---

---

Смотрите также файлы

• Министерство связи и массовых коммуникаций российской федерации государственное образовательное учреждение.docx

• Контрольная работа по эргономике и дизайну графических интерфейсов на тему разработка интерфейса программного продукта.docx

• Отчет за 2016 2018 годы о работе лаборанта бактериологической лаборатории гбуз мо Луховицкая црб.docx

• Конспект лекций по дисциплине общий курс железных дорог.doc

• Контрольная работа Вопрос 2 Экологическая экспертиза и аудит как основа административного ограничения негативного воздействия на состояние окружающей среды.docx