Графические модели (курс лекций)/2013/Задание 2

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Содержание

1 Низкоплотностные коды
2 Формулировка задания
3 Рекомендации по выполнению задания
4 Оформление задания

Основная статья: Графические модели (курс лекций)

Демонстрация процесса кодирования/декодирования с исправлением ошибок. Кодируемое сообщение (изображение цифры) содержит значительную избыточность для возможности визуальной оценки процесса декодирования. Алгоритм декодирования не использует свойство избыточности входного сигнала.

Начало выполнения задания: 4 марта 2013 г.
Срок сдачи: 17 марта 2013 г., 23:59.

Среда для выполнения задания — MATLAB.

Низкоплотностные коды

Задача помехоустойчивого кодирования

Рассмотрим задачу безошибочной передачи потока битовой информации по каналу с шумом. Для этого необходимо воспользоваться кодом, способным исправлять ошибки в принятом сигнале. При блоковом кодировании входящий поток информации разбивается на блоки фиксированной длины K. Обозначим один такой блок через $t\in\{0,1\}^K$ . Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок $t$ в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через $x\in\{0,1\}^N$ , $N>K$ . Для кодирования всевозможных блоков $t$ необходимо использовать $2^K$ кодовых слов длины $N$ . Назовём множество $2^K$ кодовых слов длины $N$ (N,K)-блоковым кодом, а величину $R=K/N$ — скоростью кода. При передаче по каналу с шумом кодовое слово $x$ превращается в принятое слово $y$ , которое, вообще говоря, отличается от $x$ . Далее алгоритм декодирования пытается восстановить переданное слово $x$ путем поиска среди всевозможных кодовых слов ближайшего к $y$ . Обозначим результат работы алгоритма декодирования через $\hat{x}$ . На последнем этапе декодированное слово $\hat{x}$ переводится в декодированное слово исходного сообщения $\hat{t}$ .

Кодирование с помощью (N,K)-линейного блокового кода

Множество $\{0,1\}^N$ с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов $\{0,1\}$ . (N,K)-блоковый код называется линейным, если множество его кодовых слов образует линейное подпространство размерности $K$ общего линейного пространства $\{0,1\}^N$ . Одним из способов задания $K$ -мерного линейного подпространства является рассмотрение множества решений следующей системы линейных уравнений:

$Hx=0$ ,

где $H\in\{0,1\}^{(N-K){\times}N}$ — матрица ранга $N-K$ . Такая матрица называется проверочной матрицей кода, т.к. с её помощью можно проверить, является ли слово $x$ кодовым словом путём проверки соотношения $Hx=0$ (здесь и далее все операции проводятся по модулю 2).

Рассмотрим задачу кодирования слов исходного сообщения $t$ в кодовые слова $x$ (N,K)-линейного блокового кода, задаваемого проверочной матрицей $H$ . Для этого необходимо найти базис $K$ -мерного линейного подпространства $g_1,\dots,g_K\in\{0,1\}^N$ . Тогда, рассматривая базисные вектора как столбцы общей матрицы $G\in\{0,1\}^{N{\times}K}$ , операция кодирования может быть представлена как $x=Gt$ . Матрица $G$ называется порождающей матрицей кода. Кодирование называется систематическим, если все биты слова $t$ копируются в некоторые биты кодового слова $x$ , т.е. в матрице G некоторое подмножество строк образует единичную матрицу размера $K{\times}K$ . При систематическом кодировании обратный процесс преобразования из декодированного кодового слова $\hat{x}$ в декодированное слово сообщения $\hat{t}$ становится тривиальным.

Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование всегда может быть сделано с помощью гауссовских исключений. С точностью до перестановки столбцов канонический ступенчатый вид матрицы $H$ эквивалентен её представлению в виде $\begin{bmatrix} I_{N-K} & P\end{bmatrix}$ , где $I_{N-K}$ — единичная матрица размера $(N-K)\times(N-K)$ . Тогда в качестве порождающей матрицы, обеспечивающей систематическое кодирование, можно выбрать матрицу

$G = \begin{bmatrix}P\\ I_K\end{bmatrix}$ .

Действительно, в этом случае $HGt = (P+P)t = 0$ .

Декодирование низкоплотностного кода

Фактор-граф для (16,4)-низкоплотностного кода, в проверочной матрице которого в каждом столбце по 3 единицы, а в каждой строке - по 4 единицы.

Низкоплотностным кодом (или кодом с малой плотностью проверок на чётность) называется бинарный (N,K)-линейный блоковый код, в котором проверочная матрица $H\in\{0,1\}^{(N-K)\times N}$ является сильно разреженной.

Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью q. В результате бинарный симметричный канал задает распределение $p(y|x)$ для передаваемого кодового слова $x\in\{0,1\}^N$ и полученного на выходе слова $y\in\{0,1\}^N$ как

$p(y|x) = \prod_{n=1}^Np(y_n|x_n) = \prod_{n=1}^Nq^{y_n+x_n}(1-q)^{y_n+x_n+1}$ .

Пропускная способность данного канала определяется величиной $1+q\log_2q+(1-q)\log_2(1-q)$ .

Объединяя низкоплотностный код с бинарным симметричным каналом, получаем следующую вероятностную модель для пары $x,y$ :

$p(y,x)\propto p(y|x)I[Hx=0] = \prod_{n=1}^Np(y_n|x_n)\prod_{m=1}^MI[h_m^Tx = 0]$ .

Здесь M=N-K — количество проверок на чётность, $h_m^T$ — m-ая строка матрицы H, а $I[\cdot]$ — индикаторная функция. Фактор-граф введённой модели показан на рис. справа.

Процесс декодирования, т.е. восстановление кодового слова $x$ по полученному слову $y$ , предлагается осуществлять как $x_n^* = \arg\max p(x_n|y)$ , а маргинальные распределения $p(x_n|y)$ оценивать в помощью циклического алгоритма передачи сообщений (sum-product loopy BP) на фактор-графе. При этом для упрощения алгоритма декодирования предлагается избавиться от факторов-унарных потенциалов (путем их включения в сообщения от переменных $x_n$ к факторам $f_m$ ), а в качестве расписания пересчёта сообщений выбрать параллельное расписание, при котором сначала все переменные одновременно посылают сообщения во все факторы, а затем все факторы одновременно посылают сообщения во все вершины.

Введём обозначения $N(n)=\{m:H_{mn}=1\}$ — множество факторов, в которых участвует переменная $x_n$ , и $N(m)=\{n:H_{mn}=1\}$ — множество переменных, которые входят в фактор $f_m$ . Тогда общая схема алгоритма декодирования выглядит следующим образом:

1. Инициализация:

$\mu_{x_n\rightarrow f_m}(x_n) = p(y_n|x_n)$ ;

2. Пересчет сообщений от факторов:

$\mu_{f_m\rightarrow x_n}(x_n) = \sum_{x_{n^'}:n^'\in N(m)\backslash n}I[x_n+\sum_{n^'}x_{n^'}=0]\prod_{n^'\in N(m)\backslash n}\mu_{x_{n^'}\rightarrow f_m}(x_{n^'})$ ;

3. Пересчет сообщений от переменных:

$\mu_{x_n\rightarrow f_m}(x_n) \propto p(y_n|x_n)\prod_{m^'\in N(n)\backslash m}\mu_{f_{m^'}\rightarrow x_n}(x_n)$ ;

$\hat{p}_n(x_n|y)\propto p(y_n|x_n)\prod_{m^'\in N(n)}\mu_{f_{m^'}\rightarrow x_n}(x_n)$ ;

Символом $\propto$ обозначается пропорциональность. Таким образом, при пересчете все сообщения от переменных и оценки на маргинальные распределения должны нормироваться так, чтобы $\mu_{x_n\rightarrow f_m}(0)+\mu_{x_n\rightarrow f_m}(1)=1$ и $\hat{p}_n(0|y)+\hat{p}_n(1|y)=1$ ;

4. Оценка кодового слова:

$\hat{x}_n=\arg\max\hat{p}_n(x_n|y)$ ;

5. Критерий остановки:

Если $H\hat{x}=0$ , то выход алгоритма со статусом 0;

Если достигнуто максимальное число итераций или суммарная норма разности между сообщениями на текущей и предыдущей итерациях меньше определенного порога $\varepsilon$ , то выход алгоритма со статусом -1;

Переход к шагу 2.

При прямой реализации данного алгоритма на шаге 2 требуется рассмотрение для каждого фактора $2^{N(m)-1}$ различных конфигураций переменных. Это может приводить как к низкой скорости пересчета сообщений, так и к большим требованиям по памяти.

Рассмотрим более эффективную схему реализации шага 2 путем его сведения к задаче вывода в графической модели с графом-цепочкой. Пусть нам необходимо вычислить сообщение $\mu_{f_m\rightarrow x_n}(x_n)$ . Перенумеруем все переменные, входящие в m-ый фактор (кроме переменной $x_n$ ), как $x_1,x_2,\dots,x_{N(m)-1}$ . Рассмотрим графическую модель с $N(m)-1$ бинарными переменными $s_i$ и графом

Положим, что $s_i=\sum_{j=1}^ix_j$ . Определим априорное распределение и вероятность перехода как

$p(s_1) = \mu_{x_1\rightarrow f_m}(s_1)$ ; $p(s_i|s_{i-1}) = \begin{cases}\mu_{x_i\rightarrow f_m}(0),& s_i=s_{i-1},\\ \mu_{x_i\rightarrow f_m}(1),& s_i\neq s_{i-1}.\end{cases}$

Тогда требуемое сообщение $\mu_{f_m\rightarrow x_n}(x_n)$ поэлементно равно маргинальному распределению $p(s_{N(m)-1})$ , которое может быть эффективно вычислено путем однократной пересылки сообщений вдоль цепи от $s_1$ до $s_{N(m)-1}$ .

Дальнейшее повышение эффективности реализации шага 2 связано с рассмотрением разностей значений сообщений $\delta\mu_{x_n\rightarrow f_m} = \mu_{x_n\rightarrow f_m}(0) - \mu_{x_n\rightarrow f_m}(1)$ и $\delta\mu_{f_m\rightarrow x_n} = \mu_{f_m\rightarrow x_n}(0) - \mu_{f_m\rightarrow x_n}(1)$ . В терминах разностей можно показать, что новое значение $\delta\mu_{f_m\rightarrow x_n}$ может быть вычислено как

$\delta\mu_{f_m\rightarrow x_n} = \prod_{n^'\in N(m)\backslash n}\delta\mu_{x_{n^'}\rightarrow f_m}$ . (*)

Зная значение $\delta\mu_{f_m\rightarrow x_n}$ и учитывая условие нормировки на сообщения, сами сообщения от факторов могут быть вычислены как

$\mu_{f_m\rightarrow x_n}(0) = \frac{1}{2}(1+\delta\mu_{f_m\rightarrow x_n})$ ; $\mu_{f_m\rightarrow x_n}(1) = \frac{1}{2}(1-\delta\mu_{f_m\rightarrow x_n})$ .

Основное преимущество условия (*) по сравнению с пересчетом сообщений для $s_i$ связано с тем, что формула (*) может быть реализована с помощью векторных операций в MATLAB.

Покажем теперь справедливость условия (*). Для этого рассмотрим две произвольные бинарные независимые случайные величины $u_1$ и $u_2$ . Обозначим через $p_i^u$ величину $\mathbb{P}\{u_i=u\}$ . Тогда очевидно, что

$\mathbb{P}\{u_1+u_2=0\} = p_1^0p_2^0 + p_1^1p_2^1$ ; $\mathbb{P}\{u_1+u_2=1\} = p_1^0p_2^1 + p_1^1p_2^0$ ; $\mathbb{P}\{u_1+u_2=0\}-\mathbb{P}\{u_1+u_2=1\} = (p_1^0-p_1^1)(p_2^0-p_2^1) = \delta p_1\delta p_2$ .

Аналогичные рассуждения справедливы для произвольного количества случайных величин $u$ . В частности,

$\mathbb{P}\{u_1+u_2+u_3=0\} - \mathbb{P}\{u_1+u_2+u_3=1\} = \delta p_1\delta p_2\delta p_3$ .

Отсюда немедленно следует справедливость (*).

Формулировка задания

Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP; при реализации шага 2 пересчета сообщений от факторов к переменным необходимо использовать эффективные схемы, обозначенные выше; при реализации на MATLAB одной итерации схемы передачи сообщений использование вложенных циклов является нежелательным; провести временные замеры реализованного алгоритма для различных значений входных параметров;
Рассмотрим две характеристики качества кода — вероятность совершить ошибку хотя бы в одном бите при декодировании блока ( $p(\hat{x}\neq x)$ ) и среднюю вероятность совершить ошибку при декодировании в одном бите ( $\frac{1}{N}\sum_{n=1}^Np(\hat{x}_n\neq x_n)$ ). Требуется реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний (многократная случайная генерация слова $t$ , его преобразование к кодовому слову $x$ , передача по каналу с независимым инвертированием каждого бита с заданной вероятностью $q$ , восстановление кодового слова $\hat{x}$ с помощью алгоритма декодирования и подсчет необходимых характеристик);
Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова N, скорости кода R, вероятности инвертирования бита при передаче по каналу связи q и среднего количества единиц в столбце проверочной матрицы j. В частности, необходимо проанализировать следующие ситуации:
- Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
- Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
- Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов (путём рассмотрения нескольких значений j, начиная от 3).
Составить отчёт в формате PDF с описанием всех проведённых исследований. Данный отчёт обязательно должен содержать описание отладочных тестов, которые проводились для проверки корректности реализованных алгоритмов. Также в этом отчёте должны быть графики поведения характеристик кода в зависимости от значений различных параметров.

Оформление задания

Выполненное задание следует отправить письмом по адресу bayesml@gmail.com с заголовком письма «[ГМ13] Задание 2 <ФИО>». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.

Присланный вариант задания должен содержать в себе:

Файл отчёта в формате PDF с указанием ФИО.
Все исходные коды с необходимыми комментариями.

Построение порождающей матрицы для систематического кодирования

[G, ind] = ldpc_gen_matrix(H)

ВХОД

H — проверочная матрица чётности, бинарная матрица размера MxN;

ВЫХОД

G — порождающая матрица кода, бинарная матрица размера Nx(N-M);

ind — номера позиций кодового слова, в которые копируются биты исходного сообщения, т.е. G(ind, :) является единичной матрицей.

Алгоритм декодирования LDPC-кода в синдромном представлении

[e, status] = ldpc_decoding(z, H, q, param_name1, param_value1, ...)

ВХОД

z — наблюдаемый синдром, бинарный вектор-столбец длины M;

H — проверочная матрица чётности, бинарная матрица размера MxN;

q — вероятность инверсии бита при передаче по каналу связи, число от 0 до 0.5;

(param_name, param_value) — набор необязательных параметров алгоритма, следующие имена и значения возможны:

'max_iter' — максимальное число итераций алгоритма декодирования, число, по умолчанию = 200;

'eps' — порог стабилизации для сообщений, число, по умолчанию = 1e-4;

'display' — режим отображения, true или false, если true, то отображается промежуточная информация на итерациях, например, номер итерации, текущее число ошибок декодирования, невязка для сообщений и т.д.

ВЫХОД

e — восстановленный вектор ошибок, бинарный вектор-столбец длины N;

status — результат декодирования, равен 0, если вектор e восстановлен без ошибок, равен -1, если произошел выход по максимальному числу итераций или стабилизации значений сообщений.

Оценка характеристик LDPC-кода с помощью метода Монте Карло

[err_bit, err_block, diver] = ldpc_mc(H, G, q, num_points)

ВХОД

H — проверочная матрица чётности, бинарная матрица размера MxN;

G — порождающая матрица кода, бинарная матрица размера Nx(N-M);

q — вероятность инверсии бита при передаче по каналу связи, число от 0 до 0.5;

num_points — общее количество экспериментов, число;

ВЫХОД

err_bit — вероятность битовой ошибки декодирования (относительно N бит кодового слова), число от 0 до 1;

err_block — вероятность блоковой ошибки декодирования, число от 0 до 1;

diver — доля ситуаций расходимости алгоритма декодирования, число от 0 до 1.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29/2013/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_2»

Графические модели (курс лекций)/2013/Задание 2

Материал из MachineLearning.

Текущая версия

Содержание

Низкоплотностные коды

Задача помехоустойчивого кодирования

Кодирование с помощью (N,K)-линейного блокового кода

Декодирование низкоплотностного кода

Формулировка задания

Рекомендации по выполнению задания

Оформление задания

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-{{stop|Формулировка задания находится в стадии разработки. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.}}
+{{TOCright|300px}}
 {{Main|Графические модели (курс лекций)}}
-__TOC__
+{|
+ |[[Изображение:GM13_task2_intro.jpg|мини|600px|Демонстрация процесса кодирования/декодирования с исправлением ошибок. Кодируемое сообщение (изображение цифры) содержит значительную избыточность для возможности визуальной оценки процесса декодирования. Алгоритм декодирования не использует свойство избыточности входного сигнала.]]
+ |}
-'''Начало выполнения задания''': 1 марта 2013 г.<br>
+'''Начало выполнения задания''': 4 марта 2013 г.<br>
-'''Срок сдачи''': {{важно|15 марта 2013 г., 23:59.}}
+'''Срок сдачи''': {{важно|17 марта 2013 г., 23:59.}}
 Среда для выполнения задания — MATLAB.
-== Вероятностные модели посещаемости курса ==
+== [http://ru.wikipedia.org/wiki/LDPC Низкоплотностные коды] ==
-Рассмотрим модель посещаемости студентами одного курса лекции. Пусть аудитория данного курса состоит из студентов профильной кафедры, а также студентов других кафедр. Обозначим через <tex>a</tex> количество студентов, распределившихся на профильную кафедру, а через <tex>b</tex> — количество студентов других кафедр на курсе. Пусть студенты профильной кафедры посещают курс с некоторой вероятностью <tex>p_1</tex>, а студенты остальных кафедр — с вероятностью <tex>p_2</tex>. Обозначим через <tex>c</tex> количество студентов на данной лекции. Тогда случайная величина <tex>c|a,b</tex> есть сумма двух случайных величин, распределенных по биномиальному закону <tex>B(a,p_1)</tex> и <tex>B(b,p_2)</tex> соответственно. Пусть далее на лекции по курсу ведется запись студентов. При этом каждый студент записывается сам, а также, быть может, записывает своего товарища, которого на лекции на самом деле нет. Пусть студент записывает своего товарища с некоторой вероятностью <tex>p_3</tex>. Обозначим через <tex>d</tex> общее количество записавшихся на данной лекции. Тогда случайная величина <tex>d|c</tex> представляет собой сумму <tex>c</tex> и случайной величины, распределенной по биномиальному закону <tex>B(c,p_3)</tex>. Для завершения задания вероятностной модели осталось определить априорные вероятности для <tex>a</tex> и для <tex>b</tex>. Пусть обе эти величины распределены равномерно в своих интервалах <tex>[a_{min},a_{max}]</tex> и <tex>[b_{min},b_{max}]</tex>. Таким образом, мы определили следующую вероятностную модель:<br>
+=== Задача помехоустойчивого кодирования ===
-'''Модель 1'''<br>
-{| class = "standard"
-|-
-|<tex>p(a,b,c,d)=p(d|c)p(c|a,b)p(a)p(b)</tex>,<br>
-<tex>d|c \sim c + B(c,p_3)</tex>,<br>
-<tex>c|a,b \sim B(a,p_1) + B(b,p_2)</tex>,<br>
-<tex>a \sim R[a_{min},a_{max}]</tex>,<br>
-<tex>b \sim R[b_{min},b_{max}]</tex>.<br>
-| [[Изображение:BayesML2010_gm1.png|100px|thumb|Графическая модель для вероятностной модели 1]]
-|-
-|}
-<br>Рассмотрим несколько упрощенную версию модели 1. Известно, что биномиальное распределение <tex>B(n,p)</tex> при большом количестве испытаний и маленькой вероятности успеха может быть с высокой точностью приближено пуассоновским распределением <tex>Poiss(\lambda)</tex> с <tex>\lambda = np</tex>. Известно также, что сумма двух пуассоновских распределений с параметрами <tex>\lambda_1</tex> и <tex>\lambda_2</tex> есть пуассоновское распределение с параметром <tex>\lambda_1+\lambda_2</tex>. Таким образом, мы можем сформулировать вероятностную модель, которая является приближенной версией модели 1:<br>
+Рассмотрим задачу безошибочной передачи потока битовой информации по каналу с шумом. Для этого необходимо воспользоваться кодом, способным исправлять ошибки в принятом сигнале. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины K. Обозначим один такой блок через <tex>t\in\{0,1\}^K</tex>. Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок <tex>t</tex> в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через <tex>x\in\{0,1\}^N</tex>, <tex>N>K</tex>. Для кодирования всевозможных блоков <tex>t</tex> необходимо использовать <tex>2^K</tex> кодовых слов длины <tex>N</tex>. Назовём множество <tex>2^K</tex> кодовых слов длины <tex>N</tex> ''(N,K)-блоковым кодом'', а величину <tex>R=K/N</tex> — ''скоростью кода''. При передаче по каналу с шумом кодовое слово <tex>x</tex> превращается в принятое слово <tex>y</tex>, которое, вообще говоря, отличается от <tex>x</tex>. Далее алгоритм декодирования пытается восстановить переданное слово <tex>x</tex> путем поиска среди всевозможных кодовых слов ближайшего к <tex>y</tex>. Обозначим результат работы алгоритма декодирования через <tex>\hat{x}</tex>. На последнем этапе декодированное слово <tex>\hat{x}</tex> переводится в декодированное слово исходного сообщения <tex>\hat{t}</tex>.
-'''Модель 2'''<br>
-<tex>p(a,b,c,d)=p(d|c)p(c|a,b)p(a)p(b)</tex>,<br>
-<tex>d|c \sim c + B(c,p_3)</tex>,<br>
-<tex>c|a,b \sim Poiss(ap_1+bp_2)</tex>,<br>
-<tex>a \sim R[a_{min},a_{max}]</tex>,<br>
-<tex>b \sim R[b_{min},b_{max}]</tex>.<br>
-<br>Рассмотрим теперь модель посещаемости нескольких лекций курса. Будем считать, что посещаемости отдельных лекций являются независимыми. Тогда:<br>
+=== Кодирование с помощью (N,K)-линейного блокового кода ===
-'''Модель 3'''<br>
-{| class = "standard"
-|-
-|<tex>p(a,b,c_1,\dots,c_N,d_1,\dots,d_N)=\prod_{n=1}^Np(d_n|c_n)p(c_n|a,b)p(a)p(b)</tex>,<br>
-<tex>d_n|c_n \sim c_n + B(c_n,p_3)</tex>,<br>
-<tex>c_n|a,b \sim B(a,p_1) + B(b,p_2)</tex>,<br>
-<tex>a \sim R[a_{min},a_{max}]</tex>,<br>
-<tex>b \sim R[b_{min},b_{max}]</tex>.<br>
-| [[Изображение:BayesML2010_gm2.png|100px|thumb|Графическая модель для вероятностной модели 3]]
-|-
-|}
-<br>По аналогии с моделью 2 можно сформулировать упрощенную модель для модели 3:<br>
+Множество <tex>\{0,1\}^N</tex> с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов <tex>\{0,1\}</tex>. (N,K)-блоковый код называется ''линейным'', если множество его кодовых слов образует линейное подпространство размерности <tex>K</tex> общего линейного пространства <tex>\{0,1\}^N</tex>. Одним из способов задания <tex>K</tex>-мерного линейного подпространства является рассмотрение множества решений следующей системы линейных уравнений:
-'''Модель 4'''<br>
+:<tex>Hx=0</tex>,
-<tex>p(a,b,c_1,\dots,c_N,d_1,\dots,d_N)=\prod_{n=1}^Np(d_n|c_n)p(c_n|a,b)p(a)p(b)</tex>,<br>
+где <tex>H\in\{0,1\}^{(N-K){\times}N}</tex> — матрица ранга <tex>N-K</tex>. Такая матрица называется ''проверочной матрицей'' кода, т.к. с её помощью можно проверить, является ли слово <tex>x</tex> кодовым словом путём проверки соотношения <tex>Hx=0</tex> (здесь и далее все операции проводятся по модулю 2).
-<tex>d_n|c_n \sim c_n + B(c_n,p_3)</tex>,<br>
-<tex>c_n|a,b \sim Poiss(ap_1+bp_2)</tex>,<br>
-<tex>a \sim R[a_{min},a_{max}]</tex>,<br>
-<tex>b \sim R[b_{min},b_{max}]</tex>.<br>
-<br>Задание состоит из трех вариантов. Распределение студентов по вариантам см. [[Графические модели (курс лекций)/2013/Задание 1#Распределение студентов по вариантам|ниже]].
+Рассмотрим задачу кодирования слов исходного сообщения <tex>t</tex> в кодовые слова <tex>x</tex> (N,K)-линейного блокового кода, задаваемого проверочной матрицей <tex>H</tex>. Для этого необходимо найти базис <tex>K</tex>-мерного линейного подпространства <tex>g_1,\dots,g_K\in\{0,1\}^N</tex>. Тогда, рассматривая базисные вектора как столбцы общей матрицы <tex>G\in\{0,1\}^{N{\times}K}</tex>, операция кодирования может быть представлена как <tex>x=Gt</tex>. Матрица <tex>G</tex> называется ''порождающей матрицей'' кода. Кодирование называется ''систематическим'', если все биты слова <tex>t</tex> копируются в некоторые биты кодового слова <tex>x</tex>, т.е. в матрице G некоторое подмножество строк образует единичную матрицу размера <tex>K{\times}K</tex>. При систематическом кодировании обратный процесс преобразования из декодированного кодового слова <tex>\hat{x}</tex> в декодированное слово сообщения <tex>\hat{t}</tex> становится тривиальным.
-== Вариант 1 ==
+Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к [http://ru.wikipedia.org/wiki/Ступенчатый_вид_по_строкам каноническому ступенчатому виду]. Такое преобразование всегда может быть сделано с помощью [http://en.wikipedia.org/wiki/Gaussian_elimination гауссовских исключений]. С точностью до перестановки столбцов канонический ступенчатый вид матрицы <tex>H</tex> эквивалентен её представлению в виде <tex>\begin{bmatrix} I_{N-K} & P\end{bmatrix}</tex>, где <tex>I_{N-K}</tex> — единичная матрица размера <tex>(N-K)\times(N-K)</tex>. Тогда в качестве порождающей матрицы, обеспечивающей систематическое кодирование, можно выбрать матрицу
-Рассматривается модель 2 с параметрами <tex>a_{min}=15, a_{max}=30, b_{min}=250, b_{max}=350, p_1 = 0.5, p_2 = 0.05, p_3 = 0.5</tex>. Провести на компьютере следующие исследования:
+:<tex>G = \begin{bmatrix}P\\ I_K\end{bmatrix}</tex>.
-# Найти математические ожидания и дисперсии априорных распределений для всех параметров <tex>a, b, c, d</tex>.
+Действительно, в этом случае <tex>HGt = (P+P)t = 0</tex>.
-# Пронаблюдать, как происходит уточнение прогноза для величины <tex>c</tex> по мере прихода новой косвенной информации. Для этого построить графики и найти мат.ожидание и дисперсию для распределений <tex>p(c), p(c|b), p(c|a,b), p(c|a,b,d)</tex> при параметрах <tex>a,b,d</tex>, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого.
-# Определить, какая из величин <tex>a,b,d</tex> вносит больший вклад в уточнение прогноза для величины <tex>c</tex> (в смысле дисперсии распределения). Для этого убедиться в том, что <tex>\mathbb{D}[c|d]<\mathbb{D}[c|b]</tex> и <tex>\mathbb{D}[c|d]<\mathbb{D}[c|a]</tex> для любых допустимых значений <tex>a,b,d</tex>. Найти множество точек <tex>(a,b)</tex> таких, что <tex>\mathbb{D}[c|b]<\mathbb{D}[c|a]</tex>. Являются ли множества <tex>\{(a,b)|\mathbb{D}[c|b]<\mathbb{D}[c|a]\}</tex> и <tex>\{(a,b)|\mathbb{D}[c|b]\ge\mathbb{D}[c|a]\}</tex> линейно разделимыми?
-# Провести временные замеры по оценке всех необходимых распределений <tex>p(c),p(c|a),p(c|b),p(c|d),p(c|a,b),p(c|a,b,d),p(d)</tex>.
-# Провести исследования из пп. 1-4 для точной модели 1 и сравнить результаты с аналогичными для модели 2. Привести пример оценки параметра, в котором разница между моделью 1 и 2 проявляется в большой степени.
-Взять в качестве диапазона допустимых значений для величины <tex>c</tex> интервал <tex>[0,a_{max}+b_{max}]</tex>, а для величины <tex>d</tex> — интервал <tex>[0,2*(a_{max}+b_{max})]</tex>.
+=== Декодирование низкоплотностного кода ===
-При оценке выполнения задания будет учитываться эффективность программного кода. В частности, временные затраты на расчет отдельного распределения не должны превышать одной секунды.
+[[Image:GM13_task2_fg.png|thumb|Фактор-граф для (16,4)-низкоплотностного кода, в проверочной матрице которого в каждом столбце по 3 единицы, а в каждой строке - по 4 единицы.]]
-== Вариант 2 ==
+''Низкоплотностным кодом'' (или кодом с малой плотностью проверок на чётность) называется бинарный (N,K)-линейный блоковый код, в котором проверочная матрица <tex>H\in\{0,1\}^{(N-K)\times N}</tex> является сильно разреженной.
-Рассматривается модель 2 с параметрами <tex>a_{min}=15, a_{max}=30, b_{min}=250, b_{max}=350, p_1 = 0.5, p_2 = 0.05, p_3 = 0.5</tex>. Провести на компьютере следующие исследования:
-# Найти математические ожидания и дисперсии априорных распределений для всех параметров <tex>a, b, c, d</tex>.
-# Пронаблюдать, как происходит уточнение прогноза для величины <tex>b</tex> по мере прихода новой косвенной информации. Для этого построить графики и найти мат.ожидание и дисперсию для распределений <tex>p(b), p(b|a), p(b|a,d)</tex> при параметрах <tex>a,d</tex>, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого.
-# Определить, при каких соотношениях параметров <tex>p_1,p_2</tex> изменяется относительная важность параметров <tex>a,b</tex> для оценки величины <tex>c</tex>. Для этого найти множество точек <tex>\{(p_1,p_2)|\mathbb{D}[c|b]<\mathbb{D}[c|a]\}</tex> при <tex>a,b</tex>, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого. Являются ли множества <tex>\{(p_1,p_2)|\mathbb{D}[c|b]<\mathbb{D}[c|a]\}</tex> и <tex>\{(p_1,p_2)|\mathbb{D}[c|b]\ge\mathbb{D}[c|a]\}</tex> линейно разделимыми?
-# Провести временные замеры по оценке всех необходимых распределений <tex>p(c),p(c|a),p(c|b),p(b|a),p(b|a,d),p(d)</tex>.
-# Провести исследования из пп. 1-4 для точной модели 1 и сравнить результаты с аналогичными для модели 2. Привести пример оценки параметра, в котором разница между моделью 1 и 2 проявляется в большой степени.
-Взять в качестве диапазона допустимых значений для величины <tex>c</tex> интервал <tex>[0,a_{max}+b_{max}]</tex>, а для величины <tex>d</tex> — интервал <tex>[0,2*(a_{max}+b_{max})]</tex>.
+Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью q. В результате бинарный симметричный канал задает распределение <tex>p(y|x)</tex> для передаваемого кодового слова <tex>x\in\{0,1\}^N</tex> и полученного на выходе слова <tex>y\in\{0,1\}^N</tex> как
+:<tex>p(y|x) = \prod_{n=1}^Np(y_n|x_n) = \prod_{n=1}^Nq^{y_n+x_n}(1-q)^{y_n+x_n+1}</tex>.
-При оценке выполнения задания будет учитываться эффективность программного кода. В частности, временные затраты на расчет отдельного распределения не должны превышать одной секунды.
+[http://en.wikipedia.org/wiki/Channel_capacity Пропускная способность] данного канала определяется величиной <tex>1+q\log_2q+(1-q)\log_2(1-q)</tex>.
-== Вариант 3 ==
+Объединяя низкоплотностный код с бинарным симметричным каналом, получаем следующую вероятностную модель для пары <tex>x,y</tex>:
-Рассматривается модель 4 с параметрами <tex>a_{min}=15, a_{max}=30, b_{min}=250, b_{max}=350, p_1 = 0.5, p_2 = 0.05, p_3 = 0.5, N = 50</tex>. Провести на компьютере следующие исследования:
+:<tex>p(y,x)\propto p(y|x)I[Hx=0] = \prod_{n=1}^Np(y_n|x_n)\prod_{m=1}^MI[h_m^Tx = 0]</tex>.
-# Найти математические ожидания и дисперсии априорных распределений для всех параметров <tex>a, b, c_n, d_n</tex>.
-# Реализовать генератор выборки <tex>d_1,\dots,d_N</tex> из модели при заданных значениях параметров <tex>a,b</tex>.
-# Пронаблюдать, как происходит уточнение прогноза для величины <tex>b</tex> по мере прихода новой косвенной информации. Для этого построить графики и найти мат.ожидание и дисперсию для распределений <tex>p(b), p(b|d_1), \dots, p(b|d_1,\dots,d_N)</tex>, где выборка <tex>d_1,\dots,d_N</tex> 1) сгенерирована из модели при параметрах <tex>a,b</tex>, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого и 2) <tex>d_1=\dots=d_N</tex>, где <tex>d_n</tex> равно мат.ожиданию своего априорного распределения, округленного до ближайшего целого. Провести аналогичный эксперимент, если дополнительно известно значение <tex>a</tex>. Сравнить результаты двух экспериментов.
-# Провести временные замеры по оценке всех необходимых распределений <tex>p(c_n),p(d_n),p(b|d_1,\dots,d_n),p(b|a,d_1,\dots,d_n)</tex>.
-# Провести исследования из пп. 1-4 для точной модели 3 и сравнить результаты с аналогичными для модели 4.
-Взять в качестве диапазона допустимых значений для величины <tex>c</tex> интервал <tex>[0,a_{max}+b_{max}]</tex>, а для величины <tex>d</tex> — интервал <tex>[0,2*(a_{max}+b_{max})]</tex>.
+Здесь M=N-K — количество проверок на чётность, <tex>h_m^T</tex> — m-ая строка матрицы H, а <tex>I[\cdot]</tex> — индикаторная функция. Фактор-граф введённой модели показан на рис. справа.
-При оценке выполнения задания будет учитываться эффективность программного кода. В частности, временные затраты на расчет отдельного распределения не должны превышать одной секунды.
+Процесс декодирования, т.е. восстановление кодового слова <tex>x</tex> по полученному слову <tex>y</tex>, предлагается осуществлять как
+<tex>x_n^* = \arg\max p(x_n|y)</tex>, а маргинальные распределения <tex>p(x_n|y)</tex> оценивать в помощью циклического алгоритма передачи сообщений (sum-product loopy BP) на фактор-графе. При этом для упрощения алгоритма декодирования предлагается избавиться от факторов-унарных потенциалов (путем их включения в сообщения от переменных <tex>x_n</tex> к факторам <tex>f_m</tex>), а в качестве расписания пересчёта сообщений выбрать параллельное расписание, при котором сначала все переменные одновременно посылают сообщения во все факторы, а затем все факторы одновременно посылают сообщения во все вершины.
+Введём обозначения <tex>N(n)=\{m:H_{mn}=1\}</tex> — множество факторов, в которых участвует переменная <tex>x_n</tex>, и <tex>N(m)=\{n:H_{mn}=1\}</tex> — множество переменных, которые входят в фактор <tex>f_m</tex>. Тогда общая схема алгоритма декодирования выглядит следующим образом:
+. Инициализация:
+: <tex>\mu_{x_n\rightarrow f_m}(x_n) = p(y_n|x_n)</tex>;
+. Пересчет сообщений от факторов:
+: <tex>\mu_{f_m\rightarrow x_n}(x_n) = \sum_{x_{n^'}:n^'\in N(m)\backslash n}I[x_n+\sum_{n^'}x_{n^'}=0]\prod_{n^'\in N(m)\backslash n}\mu_{x_{n^'}\rightarrow f_m}(x_{n^'})</tex>;
+. Пересчет сообщений от переменных:
+: <tex>\mu_{x_n\rightarrow f_m}(x_n) \propto p(y_n|x_n)\prod_{m^'\in N(n)\backslash m}\mu_{f_{m^'}\rightarrow x_n}(x_n)</tex>;<br>
+: <tex>\hat{p}_n(x_n|y)\propto p(y_n|x_n)\prod_{m^'\in N(n)}\mu_{f_{m^'}\rightarrow x_n}(x_n)</tex>;
+: Символом <tex>\propto</tex> обозначается пропорциональность. Таким образом, при пересчете все сообщения от переменных и оценки на маргинальные распределения должны нормироваться так, чтобы <tex>\mu_{x_n\rightarrow f_m}(0)+\mu_{x_n\rightarrow f_m}(1)=1</tex> и <tex>\hat{p}_n(0|y)+\hat{p}_n(1|y)=1</tex>;
+. Оценка кодового слова:
+: <tex>\hat{x}_n=\arg\max\hat{p}_n(x_n|y)</tex>;
+. Критерий остановки:
+: Если <tex>H\hat{x}=0</tex>, то выход алгоритма со статусом 0;
+: Если достигнуто максимальное число итераций или суммарная норма разности между сообщениями на текущей и предыдущей итерациях меньше определенного порога <tex>\varepsilon</tex>, то выход алгоритма со статусом -1;
+: Переход к шагу 2.
+При прямой реализации данного алгоритма на шаге 2 требуется рассмотрение для каждого фактора <tex>2^{N(m)-1}</tex> различных конфигураций переменных. Это может приводить как к низкой скорости пересчета сообщений, так и к большим требованиям по памяти.
+Рассмотрим более эффективную схему реализации шага 2 путем его сведения к задаче вывода в графической модели с графом-цепочкой. Пусть нам необходимо вычислить сообщение <tex>\mu_{f_m\rightarrow x_n}(x_n)</tex>. Перенумеруем все переменные, входящие в m-ый фактор (кроме переменной <tex>x_n</tex>), как <tex>x_1,x_2,\dots,x_{N(m)-1}</tex>. Рассмотрим графическую модель с <tex>N(m)-1</tex> бинарными переменными <tex>s_i</tex> и графом
+[[Image:GM13_task2_chain.png|500px]].
+Положим, что <tex>s_i=\sum_{j=1}^ix_j</tex>. Определим априорное распределение и вероятность перехода как
+:<tex>p(s_1) = \mu_{x_1\rightarrow f_m}(s_1)</tex>; <tex>p(s_i|s_{i-1}) = \begin{cases}\mu_{x_i\rightarrow f_m}(0),& s_i=s_{i-1},\\ \mu_{x_i\rightarrow f_m}(1),& s_i\neq s_{i-1}.\end{cases}</tex>
+Тогда требуемое сообщение <tex>\mu_{f_m\rightarrow x_n}(x_n)</tex> поэлементно равно маргинальному распределению <tex>p(s_{N(m)-1})</tex>, которое может быть эффективно вычислено путем однократной пересылки сообщений вдоль цепи от <tex>s_1</tex> до <tex>s_{N(m)-1}</tex>.
+Дальнейшее повышение эффективности реализации шага 2 связано с рассмотрением разностей значений сообщений <tex>\delta\mu_{x_n\rightarrow f_m} = \mu_{x_n\rightarrow f_m}(0) - \mu_{x_n\rightarrow f_m}(1)</tex> и <tex>\delta\mu_{f_m\rightarrow x_n} = \mu_{f_m\rightarrow x_n}(0) - \mu_{f_m\rightarrow x_n}(1)</tex>. В терминах разностей можно показать, что новое значение <tex>\delta\mu_{f_m\rightarrow x_n}</tex> может быть вычислено как
+:<tex>\delta\mu_{f_m\rightarrow x_n} = \prod_{n^'\in N(m)\backslash n}\delta\mu_{x_{n^'}\rightarrow f_m}</tex>.&nbsp;&nbsp;&nbsp;(*)
+Зная значение <tex>\delta\mu_{f_m\rightarrow x_n}</tex> и учитывая условие нормировки на сообщения, сами сообщения от факторов могут быть вычислены как
+:<tex>\mu_{f_m\rightarrow x_n}(0) = \frac{1}{2}(1+\delta\mu_{f_m\rightarrow x_n})</tex>; <tex>\mu_{f_m\rightarrow x_n}(1) = \frac{1}{2}(1-\delta\mu_{f_m\rightarrow x_n})</tex>.
+Основное преимущество условия (*) по сравнению с пересчетом сообщений для <tex>s_i</tex> связано с тем, что формула (*) может быть реализована с помощью векторных операций в MATLAB.
+Покажем теперь справедливость условия (*). Для этого рассмотрим две произвольные бинарные независимые случайные величины <tex>u_1</tex> и <tex>u_2</tex>. Обозначим через <tex>p_i^u</tex> величину <tex>\mathbb{P}\{u_i=u\}</tex>. Тогда очевидно, что
+:<tex>\mathbb{P}\{u_1+u_2=0\} = p_1^0p_2^0 + p_1^1p_2^1</tex>; <tex>\mathbb{P}\{u_1+u_2=1\} = p_1^0p_2^1 + p_1^1p_2^0</tex>; <tex>\mathbb{P}\{u_1+u_2=0\}-\mathbb{P}\{u_1+u_2=1\} = (p_1^0-p_1^1)(p_2^0-p_2^1) = \delta p_1\delta p_2</tex>.
+Аналогичные рассуждения справедливы для произвольного количества случайных величин <tex>u</tex>. В частности,
+:<tex>\mathbb{P}\{u_1+u_2+u_3=0\} - \mathbb{P}\{u_1+u_2+u_3=1\} = \delta p_1\delta p_2\delta p_3</tex>.
+Отсюда немедленно следует справедливость (*).
+== Формулировка задания ==
+# Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
+# Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP; при реализации шага 2 пересчета сообщений от факторов  к переменным необходимо использовать эффективные схемы, обозначенные выше; при реализации на MATLAB одной итерации схемы передачи сообщений использование вложенных циклов является нежелательным; провести временные замеры реализованного алгоритма для различных значений входных параметров;
+# Рассмотрим две характеристики качества кода — вероятность совершить ошибку хотя бы в одном бите при декодировании блока (<tex>p(\hat{x}\neq x)</tex>) и среднюю вероятность совершить ошибку при декодировании в одном бите (<tex>\frac{1}{N}\sum_{n=1}^Np(\hat{x}_n\neq x_n)</tex>). Требуется реализовать алгоритм оценки вероятности битовой  и блоковой ошибки  кода с помощью метода стат. испытаний (многократная случайная генерация слова <tex>t</tex>, его преобразование к кодовому слову <tex>x</tex>, передача по каналу с независимым инвертированием каждого бита с заданной вероятностью <tex>q</tex>, восстановление кодового слова <tex>\hat{x}</tex> с помощью алгоритма декодирования и подсчет необходимых характеристик);
+# Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова N, скорости кода R, вероятности инвертирования бита при передаче по каналу связи q и среднего количества единиц в столбце проверочной матрицы j. В частности, необходимо проанализировать следующие ситуации:
+#* [http://ru.wikipedia.org/wiki/Теоремы_Шеннона_для_канала_с_шумами Теорема Шеннона] определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
+#* Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
+#* Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов (путём рассмотрения нескольких значений j, начиная от 3).
+# Составить отчёт в формате PDF с описанием всех проведённых исследований. Данный отчёт обязательно должен содержать описание отладочных тестов, которые проводились для проверки корректности реализованных алгоритмов. Также в этом отчёте должны быть графики поведения характеристик кода в зависимости от значений различных параметров.
+== Рекомендации по выполнению задания ==
+. Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться [[Media:make_ldpc_mex.zip|готовой реализацией]], которая генерирует проверочную матрицу заданного размера с заданным количеством единиц в каждом столбце. При этом реализованный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP.
+. При построении порождающей матрицы кода по заданной проверочной матрице с помощью алгоритма гауссовских исключений разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, здесь рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 2 самостоятельно, т.к. такая реализация может быть сделана значительно эффективнее по сравнению с общим случаем логики по модулю произвольного простого числа. Действительно, в логике по модулю два нет необходимости использовать операцию деления, а также искать ведущий элемент при очередном вычитании ввиду того, что все ненулевые элементы равны единице.
+. Алгоритм декодирования удобно реализовывать в т.н. синдромном представлении. Полученное на выходе канала слово <tex>y</tex> можно представить как <tex>x+e</tex>, где <tex>x</tex> — посылаемое кодовое слово, а <tex>e\in\{0,1\}^N</tex> — вектор ошибок, которые вносит канал. Назовём величину <tex>z = Hy</tex> ''синдромом'' полученного сообщения. Тогда <tex>z=Hy=H(x+e)=He</tex>, и на этапе декодирования можно вместо <tex>x</tex> оценивать вектор ошибок <tex>e</tex> путем оценки аргмаксимумов маргинальных распределений <tex>p(e_n|z)</tex> в вероятностной модели
+::<tex>p(e,z)\propto p(e)I[He=z]=\prod_{n=1}^Np(e_n)\prod_{m=1}^MI[h_m^Te=z_m]</tex>.
+Для бинарного симметричного канала <tex>p(e_n) = q^{e_n}(1-q)^{e_n+1}</tex>. Зная <tex>e</tex>, искомое кодовое слово можно найти как <tex>x=y+e</tex>. Заметим, что реализация алгоритма декодирования в синдромном представлении избавляет от необходимости предварительной реализации алгоритма кодирования.
+. При тестировании алгоритма декодирования рекомендуется пробовать запускать итерационный процесс из различных начальных приближений для сообщений (не только из значений унарных потенциалов). При корректной реализации метода должна наблюдаться сходимость к одним и тем же финальным сообщениям независимо от начальных приближений.
 == Оформление задания ==
-Выполненное задание следует отправить письмом по адресу ''bayesml@gmail.com'' с заголовком письма «[ГМ13] Задание 1 <ФИО>». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.
+Выполненное задание следует отправить письмом по адресу ''bayesml@gmail.com'' с заголовком письма «[ГМ13] Задание 2 <ФИО>». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.
 Присланный вариант задания должен содержать в себе:
-* Текстовый файл в формате PDF с указанием ФИО и номера варианта, содержащий описание всех проведенных исследований.
+* Файл отчёта в формате PDF с указанием ФИО.
 * Все исходные коды с необходимыми комментариями.
-Исходные коды должны включать в себя реализацию оценки распределений в виде отдельных функций. Прототип для функции оценки распределения <tex>p(c|a,d)</tex> для модели 2 имеет следующий вид:<br>
+&nbsp;
 {|class="standard"
- !''Оценка распределения <tex>p(c|a,d)</tex> для модели 2''
+ !''Построение порождающей матрицы для систематического кодирования''
  |-
- |[p, c, m, v] = '''p2c_ad'''(a, d, params)
+ |[G, ind] = '''ldpc_gen_matrix'''(H)
  |-
  |ВХОД
@@ Строка 110: / Строка 132: @@
  |
  {|border="0"
-  |a — значение параметра a;
+  |H — проверочная матрица чётности, бинарная матрица размера MxN;
-  |-
-  |d — значение параметра d;
-  |-
-  |params — набор параметров вероятностной модели, структура с полями 'amin', 'amax', 'bmin', 'bmax', 'p1', 'p2', 'p3';
-  |-
   |}
  |-
@@ Строка 122: / Строка 139: @@
  |
  {|
-  |p — распределение вероятности, вектор-столбец длины length(c);
+  |G — порождающая матрица кода, бинарная матрица размера Nx(N-M);
-  |-
-  |c — носитель распределения, вектор-столбец;
-  |-
-  |m — математическое ожидание распределения;
   |-
-  |v — дисперсия распределения.
+  |ind — номера позиций кодового слова, в которые копируются биты исходного сообщения, т.е. G(ind, :) является единичной матрицей.
   |}
  |}
-Прототипы функций для других распределений выглядят аналогично. Если в распределении переменных до или после | несколько, то в названии функции они идут в алфавитном порядке. Функция для оценки распределения <tex>p(b|a,d_1,\dots,d_N)</tex> для модели 3 имеет название p3b_ad, а входной параметр <tex>d</tex> является одномерным массивом длины <tex>N</tex>.
+&nbsp;
 {|class="standard"
- !''Генерация из распределения <tex>p(d_1,\dots,d_N|a,b)</tex> для модели 3''
+ !''Алгоритм декодирования LDPC-кода в синдромном представлении''
  |-
- |d = '''m3_generate'''(N, a, b, params)
+ |[e, status] = '''ldpc_decoding'''(z, H, q, param_name1, param_value1, ...)
  |-
  |ВХОД
@@ Строка 143: / Строка 156: @@
  |
  {|border="0"
-  |N — количество лекций;
+  |z — наблюдаемый синдром, бинарный вектор-столбец длины M;
   |-
-  |a — значение параметра a;
+  |H — проверочная матрица чётности, бинарная матрица размера MxN;
   |-
-  |b — значение параметра b;
+  |q — вероятность инверсии бита при передаче по каналу связи, число от 0 до 0.5;
   |-
-  |params — набор параметров вероятностной модели, структура с полями 'amin', 'amax', 'bmin', 'bmax', 'p1', 'p2', 'p3';
+  |(param_name, param_value) — набор необязательных параметров алгоритма, следующие имена и значения возможны:
+  |-
+  |
+   {|border="0"
+    |'max_iter' — максимальное число итераций алгоритма декодирования, число, по умолчанию = 200;
+    |-
+    |'eps' — порог стабилизации для сообщений, число, по умолчанию = 1e-4;
+    |-
+    |'display' — режим отображения, true или false, если true, то отображается промежуточная информация на итерациях, например, номер итерации, текущее число ошибок декодирования, невязка для сообщений и т.д.
+    |}
   |-
   |}
@@ Строка 157: / Строка 179: @@
  |
  {|
-  |d — значения <tex>d_1,\dots,d_N</tex>, вектор-столбец длины N.
+  |e — восстановленный вектор ошибок, бинарный вектор-столбец длины N;
+  |-
+  |status — результат декодирования, равен 0, если вектор e восстановлен без ошибок, равен -1, если произошел выход по максимальному числу итераций или стабилизации значений сообщений.
   |}
  |}
-== Распределение студентов по вариантам ==
+&nbsp;
-{|class = "standard sortable"
+{|class="standard"
- ! class="unsortable"|№ п/п !! Студент  !! Вариант
+ !''Оценка характеристик LDPC-кода с помощью метода Монте Карло''
  |-
- | align="center"|1 || Березин Алексей Андреевич || 1
+ |[err_bit, err_block, diver] = '''ldpc_mc'''(H, G, q, num_points)
  |-
- | align="center"|2 || [[Участник:Borman|Борисов Михаил Викторович]] || 3
+ |ВХОД
  |-
- | align="center"|3 || Гавриков Михаил Игоревич || 3
+ |
+ {|border="0"
+  |H — проверочная матрица чётности, бинарная матрица размера MxN;
+  |-
+  |G — порождающая матрица кода, бинарная матрица размера Nx(N-M);
+  |-
+  |q — вероятность инверсии бита при передаче по каналу связи, число от 0 до 0.5;
+  |-
+  |num_points — общее количество экспериментов, число;
+  |}
  |-
- | align="center"|4 || Зак Евгений Михайлович || 3
+ |ВЫХОД
- |-
- | align="center"|5 || Исмагилов Тимур Ниязович || 2
- |-
- | align="center"|6 || Кондрашкин Дмитрий Андреевич || 1
- |-
- | align="center"|7 || [[Участник:Kuraga|Куракин Александр Владимирович]] || 1
- |-
- | align="center"|8 || Лобачева Екатерина Максимовна  || 2
- |-
- | align="center"|9 || Любимцева Мария Михайловна || 2
- |-
- | align="center"|10 || Малышева Екатерина Константиновна || 1
- |-
- | align="center"|11 || Морозова Дарья Юрьевна || 2
- |-
- | align="center"|12 || [[Участник:Nizhibitsky|Нижибицкий Евгений Алексеевич]] || 2
- |-
- | align="center"|13 || [[Участник:Novikov|Новиков Максим Сергеевич]] || 3
- |-
- | align="center"|14 || Огнева Дарья Сергеевна || 2
- |-
- | align="center"|15 || [[Участник:MoRandi91|Остапец Андрей Александрович]] || 3
- |-
- | align="center"|16 || Потапенко Анна Александровна || 1
- |-
- | align="center"|17 || [[Участник:Peter Romov|Ромов Петр Алексеевич]] || 1
- |-
- | align="center"|18 || [[Участник:Newo|Фонарев Александр Юрьевич]] || 1
- |-
- | align="center"|19 || Шаймарданов Ильдар Рифарович || 3
  |-
+ |
+ {|
+  |err_bit — вероятность битовой ошибки декодирования (относительно N бит кодового слова), число от 0 до 1;
+  |-
+  |err_block — вероятность блоковой ошибки декодирования, число от 0 до 1;
+  |-
+  |diver — доля ситуаций расходимости алгоритма декодирования, число от 0 до 1.
+  |}
  |}