Графические модели (курс лекций)/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://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»

@@ Строка 1: / Строка 1: @@
-{{stop|Формулировка задания находится в стадии разработки. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.}}
+{{TOCright|300px}}
 {{Main|Графические модели (курс лекций)}}
-__NOTOC__
+{|
+ |[[Изображение:GM13_task2_intro.jpg|мини|600px|Демонстрация процесса кодирования/декодирования с исправлением ошибок. Кодируемое сообщение (изображение цифры) содержит значительную избыточность для возможности визуальной оценки процесса декодирования. Алгоритм декодирования не использует свойство избыточности входного сигнала.]]
-[[Изображение:GM13_task2_intro.jpg|600px]]
+ |}
-'''Начало выполнения задания''': 3 марта 2013 г.<br>
+'''Начало выполнения задания''': 4 марта 2013 г.<br>
 '''Срок сдачи''': {{важно|17 марта 2013 г., 23:59.}}
@@ Строка 14: / Строка 14: @@
 == [http://ru.wikipedia.org/wiki/LDPC Низкоплотностные коды] ==
-[[Image:GM13_task2_fg.png|thumb|Фактор-граф для (16,4)-низкоплотностного кода, в проверочной матрице которого в каждом столбце по 3 единицы, а в каждой строке - по 4 единицы.]]
+=== Задача помехоустойчивого кодирования ===
-Низкоплотностный код (или код с малой плотностью проверок на чётность) представляет собой (N,K)-бинарный линейный блоковый код, в котором проверочная матрица <tex>H\in\{0,1\}^{(N-K)\times N}</tex> является сильно разреженной. Таким образом, вектор <tex>x\in\{0,1\}^N</tex> является кодовым словом, если <tex>Hx = 0</tex> (здесь и далее все вычисления проводятся по модулю 2).
+Рассмотрим задачу безошибочной передачи потока битовой информации по каналу с шумом. Для этого необходимо воспользоваться кодом, способным исправлять ошибки в принятом сигнале. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины 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>.
+=== Кодирование с помощью (N,K)-линейного блокового кода ===
+Множество <tex>\{0,1\}^N</tex> с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов <tex>\{0,1\}</tex>. (N,K)-блоковый код называется ''линейным'', если множество его кодовых слов образует линейное подпространство размерности <tex>K</tex> общего линейного пространства <tex>\{0,1\}^N</tex>. Одним из способов задания <tex>K</tex>-мерного линейного подпространства является рассмотрение множества решений следующей системы линейных уравнений:
+:<tex>Hx=0</tex>,
+где <tex>H\in\{0,1\}^{(N-K){\times}N}</tex> — матрица ранга <tex>N-K</tex>. Такая матрица называется ''проверочной матрицей'' кода, т.к. с её помощью можно проверить, является ли слово <tex>x</tex> кодовым словом путём проверки соотношения <tex>Hx=0</tex> (здесь и далее все операции проводятся по модулю 2).
+Рассмотрим задачу кодирования слов исходного сообщения <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> становится тривиальным.
+Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к [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>. Тогда в качестве порождающей матрицы, обеспечивающей систематическое кодирование, можно выбрать матрицу
+:<tex>G = \begin{bmatrix}P\\ I_K\end{bmatrix}</tex>.
+Действительно, в этом случае <tex>HGt = (P+P)t = 0</tex>.
+=== Декодирование низкоплотностного кода ===
+[[Image:GM13_task2_fg.png|thumb|Фактор-граф для (16,4)-низкоплотностного кода, в проверочной матрице которого в каждом столбце по 3 единицы, а в каждой строке - по 4 единицы.]]
-Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью q. Таким образом, бинарный симметричный канал задает распределение <tex>p(y|x)</tex> для передаваемого кодового слова <tex>x\in\{0,1\}^N</tex> и полученного на выходе слова <tex>y\in\{0,1\}^N</tex> как
+''Низкоплотностным кодом'' (или кодом с малой плотностью проверок на чётность) называется бинарный (N,K)-линейный блоковый код, в котором проверочная матрица <tex>H\in\{0,1\}^{(N-K)\times 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>.
+Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью 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>.
 Объединяя низкоплотностный код с бинарным симметричным каналом, получаем следующую вероятностную модель для пары <tex>x,y</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>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>.
 Здесь M=N-K — количество проверок на чётность, <tex>h_m^T</tex> — m-ая строка матрицы H, а <tex>I[\cdot]</tex> — индикаторная функция. Фактор-граф введённой модели показан на рис. справа.
-Восстановление кодового слова <tex>x</tex> по полученному слову <tex>y</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>), а в качестве расписания пересчёта сообщений выбрать параллельное расписание, при котором сначала все переменные одновременно посылают сообщения во все факторы, а затем все факторы одновременно посылают сообщения во все вершины.
@@ Строка 42: / Строка 58: @@
 : <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>\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>;
@@ Строка 50: / Строка 66: @@
 : Переход к шагу 2.
- Детали алгоритма передачи сообщений, в том числе, эффективные формулы для пересчета сообщений от факторов к вершинам можно найти [http://ru.wikipedia.org/wiki/Код_с_малой_плотностью_проверок_на_чётность#Декодирование здесь], а также в [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html книге МакКая] (стр. 560-561).
+При прямой реализации данного алгоритма на шаге 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, провести временные замеры реализованного алгоритма для различных значений входных параметров, время работы алгоритма не должно превышать XX секунд для ...
+# Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP; при реализации шага 2 пересчета сообщений от факторов  к переменным необходимо использовать эффективные схемы, обозначенные выше; при реализации на MATLAB одной итерации схемы передачи сообщений использование вложенных циклов является нежелательным; провести временные замеры реализованного алгоритма для различных значений входных параметров;
-# Реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний (многократная случайная генерация слова <tex>t</tex>, его преобразование к кодовому слову <tex>x</tex>, передача по каналу с независимым инвертированием каждого бита с заданной вероятностью <tex>q</tex>, восстановление кодового слова <tex>\hat{x}</tex> с помощью алгоритма декодирования и подсчет необходимых характеристик);
+# Рассмотрим две характеристики качества кода — вероятность совершить ошибку хотя бы в одном бите при декодировании блока (<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. В частности, необходимо проанализировать следующие ситуации:
-#* Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
+#* [http://ru.wikipedia.org/wiki/Теоремы_Шеннона_для_канала_с_шумами Теорема Шеннона] определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
 #* Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
-#* Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов.
+#* Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов (путём рассмотрения нескольких значений j, начиная от 3).
+# Составить отчёт в формате PDF с описанием всех проведённых исследований. Данный отчёт обязательно должен содержать описание отладочных тестов, которые проводились для проверки корректности реализованных алгоритмов. Также в этом отчёте должны быть графики поведения характеристик кода в зависимости от значений различных параметров.
 == Рекомендации по выполнению задания ==
-. Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться [[Media:make_ldpc_mex.zip|готовой реализацией]], которая генерирует проверочную матрицу с заданным количеством единиц в каждом столбце. При этом реализованный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP.
+. Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться [[Media:make_ldpc_mex.zip|готовой реализацией]], которая генерирует проверочную матрицу заданного размера с заданным количеством единиц в каждом столбце. При этом реализованный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP.
-. Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование может быть сделано с помощью [http://en.wikipedia.org/wiki/Gaussian_elimination гауссовских исключений]. При выполнении задания разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 2 самостоятельно, т.к. такая реализация может быть сделана значительно эффективнее по сравнению с общим случаем логики по модулю произвольного простого числа, т.к. в логике по модулю два нет необходимости использовать операцию деления и, например, искать ведущий элемент при очередном вычитании (т.к. все ненулевые элементы равны единице).
+. При построении порождающей матрицы кода по заданной проверочной матрице с помощью алгоритма гауссовских исключений разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, здесь рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 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>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>e</tex>, искомое кодовое слово можно найти как <tex>x=y+e</tex>. Заметим, что реализация алгоритма декодирования в синдромном представлении избавляет от необходимости предварительной реализации алгоритма кодирования.
+Для бинарного симметричного канала <tex>p(e_n) = q^{e_n}(1-q)^{e_n+1}</tex>. Зная <tex>e</tex>, искомое кодовое слово можно найти как <tex>x=y+e</tex>. Заметим, что реализация алгоритма декодирования в синдромном представлении избавляет от необходимости предварительной реализации алгоритма кодирования.
 . При тестировании алгоритма декодирования рекомендуется пробовать запускать итерационный процесс из различных начальных приближений для сообщений (не только из значений унарных потенциалов). При корректной реализации метода должна наблюдаться сходимость к одним и тем же финальным сообщениям независимо от начальных приближений.
-. В эффективной реализации алгоритма декодирования все вычисления на очередной итерации не должны использовать вложенных циклов.
 == Оформление задания ==
@@ Строка 81: / Строка 118: @@
 Присланный вариант задания должен содержать в себе:
-* Текстовый файл в формате PDF с указанием ФИО, содержащий описание всех проведенных исследований. Данный файл должен, в частности, содержать необходимые графики зависимости битовой и блоковой ошибки кода в зависимости от различных значений параметров.
+* Файл отчёта в формате PDF с указанием ФИО.
 * Все исходные коды с необходимыми комментариями.
@@ Строка 144: / Строка 181: @@
   |e — восстановленный вектор ошибок, бинарный вектор-столбец длины N;
   |-
-  |status — результат декодирования, равен 0, если вектор n восстановлен без ошибок, равен -1, если произошел выход по максимальному числу итераций или стабилизации значений сообщений.
+  |status — результат декодирования, равен 0, если вектор e восстановлен без ошибок, равен -1, если произошел выход по максимальному числу итераций или стабилизации значений сообщений.
   |}
  |}

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

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

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

Содержание

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

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

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

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

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты