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

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

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

Версия 15:12, 3 марта 2014

Внимание! Текст задания находится в стадии разработки. Просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.

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

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

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

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

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

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

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

Кодирование с помощью (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/2014/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_2»

@@ Строка 17: / Строка 17: @@
 === Задача помехоустойчивого кодирования ===
-Рассмотрим решение задачи безошибочной передачи потока битовой информации по каналу с шумом с помощью кодов, исправляющих ошибки. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины <tex>k</tex>, и каждый блок кодируется/декодируется независимо. Обозначим один такой блок через <tex>u\in\{0,1\}^k</tex>. Предположим, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок <tex>u</tex> в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через <tex>v\in\{0,1\}^n</tex>, <tex>n>k</tex>. Для кодирования всевозможных блоков <tex>u</tex> необходимо использовать <tex>2^k</tex> кодовых слов длины <tex>n</tex>. Назовём множество <tex>2^k</tex> кодовых слов длины <tex>n</tex> ''(n,k)-блоковым кодом'', а величину <tex>r=k/n</tex> — ''скоростью кода''. При передаче по каналу с шумом кодовое слово <tex>v</tex> превращается в принятое слово <tex>w</tex>, которое, вообще говоря, отличается от <tex>v</tex>. Предположим, что при передаче по каналу длина сообщения не изменяется, т.е. <tex>w\in\{0,1\}^n</tex>, а происходит лишь инверсия некоторых бит. Алгоритм декодирования пытается восстановить переданное слово <tex>v</tex> (например, путем поиска среди всевозможных кодовых слов ближайшего к <tex>w</tex>). Обозначим результат работы алгоритма декодирования через <tex>\hat{v}</tex>. На последнем этапе декодированное слово <tex>\hat{v}</tex> переводится в декодированное слово исходного сообщения <tex>\hat{u}</tex>.
+Рассмотрим решение задачи безошибочной передачи потока битовой информации по каналу с шумом с помощью кодов, исправляющих ошибки. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины <tex>k</tex>, и каждый блок кодируется/декодируется независимо. Обозначим один такой блок через <tex>u\in\{0,1\}^k</tex>. Предположим, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок <tex>u</tex> в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через <tex>v\in\{0,1\}^n</tex>, <tex>n>k</tex>. Для кодирования всевозможных блоков <tex>u</tex> необходимо использовать <tex>2^k</tex> кодовых слов длины <tex>n</tex>. Назовём множество <tex>2^k</tex> кодовых слов длины <tex>n</tex> ''(n,k)-блоковым кодом'', а величину <tex>r=k/n</tex> — ''скоростью кода''. При передаче по каналу с шумом кодовое слово <tex>v</tex> превращается в принятое слово <tex>w</tex>, которое, вообще говоря, отличается от <tex>v</tex>. Предположим, что при передаче по каналу длина сообщения не изменяется, т.е. <tex>w\in\{0,1\}^n</tex>, а происходит лишь инверсия некоторых бит. Задача алгоритма декодирования состоит в восстановлении по <tex>w</tex> переданного слова <tex>v</tex> (например, путем поиска среди всевозможных кодовых слов ближайшего к <tex>w</tex>). Обозначим результат работы алгоритма декодирования через <tex>\hat{v}</tex>. На последнем этапе декодированное слово <tex>\hat{v}</tex> переводится в декодированное слово исходного сообщения <tex>\hat{u}</tex>.
 === Кодирование с помощью (N,K)-линейного блокового кода ===

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

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

Версия 15:12, 3 марта 2014

Содержание

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

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

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

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

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты