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

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

Версия от 05:09, 4 марта 2014; Kropotov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

Начало выполнения задания: 5 марта 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$ -мерного линейного подпространства является рассмотрение множества решений следующей системы линейных уравнений:

$Hv=0$ ,

где $H\in\{0,1\}^{(n-k){\times}n}$ — матрица ранга $m=n-k$ (эта матрица задаёт базис линейного подпространства, ортогонального к рассматриваемому (n,k)-коду). Матрица $H$ называется проверочной матрицей кода, т.к. с её помощью можно проверить, является ли слово $v$ кодовым словом путём проверки соотношения $Hv=0$ (здесь и далее все операции проводятся по модулю 2).

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

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

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

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

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

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

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

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

$p(w|v) = \prod_{i=1}^np(w_i|v_i) = \prod_{i=1}^nq^{w_i+v_i}(1-q)^{w_i+v_i+1}$ .

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

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

$p(v|w)\propto p(w|v)I[Hv=0] \propto \prod_{i=1}^np(w_i|v_i)\prod_{j=1}^mI[h_j^Tv = 0]$ .

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

Назовём синдромом принятого слова $w$ вектор $s\in\{0,1\}^m$ , определяемый как $s=Hw$ . Процесс передачи кодового слова по бинарному симметричному каналу можно представить как $w=v+e$ , где $e\in\{0,1\}^n$ — вектор ошибок ( $e_i=1$ , если в позиции $i$ произошла ошибка). Тогда $s = Hw = H(v+e) = Hv+He = He$ . Далее можно перейти от вероятностной модели для переменных $v,w$ к аналогичной для переменных $e,s$ :

$p(e|s)\propto p(e)p(s|e) \propto\prod_{i=1}^np(e_i)\prod_{j=1}^mI[h_j^Te=s_j]$ .

Здесь $p(e_i)=q^{e_i}(1-q)^{1-e_i}$ . Зная значение вектора ошибок $\hat{e}$ , результат декодирования вычисляется как $\hat{v}=w+\hat{e}$ . При использовании вероятностной модели для $e,s$ тестирование алгоритма декодирования можно проводить без предварительной реализации процедуры кодирования.

При использовании побитовой функции потерь $\lambda(e,\tilde{e}) = \sum_{i=1}^nI[e_i\neq \tilde{e}_i]$ оптимальная процедура декодирования связана с максимизацией маргиналов отдельных переменных, т.е. $\hat{e}_n = \arg\max p(e_n|s)$ . Для поиска маргинальных распределений $p(e_n|s)$ воспользуемся циклическим алгоритмом передачи сообщений (sum-product loopy BP) на фактор-графе. Введём обозначения $N(i)=\{j:H_{ji}=1\}$ — множество факторов, в которых участвует переменная $e_i$ , и $N(j)=\{i:H_{ji}=1\}$ — множество переменных, которые входят в фактор $h_j$ . Тогда общая схема алгоритма декодирования выглядит следующим образом:

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

$\mu_{e_i\rightarrow h_j}(e_i) = p(e_i)$ ;

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

$\mu_{h_j\rightarrow e_i}(e_i) = \sum_{e_k:k\in N(j)\backslash i}I[e_i+\sum_{k}e_{k}=s_j]\prod_{k\in N(j)\backslash i}\mu_{e_{k}\rightarrow h_j}(e_{k})$ ;

3. Пересчет сообщений от переменных и вычисление beliefs (оценок на маргинальные распределения):

$\mu_{e_i\rightarrow h_j}(e_i) \propto p(e_i)\prod_{k\in N(i)\backslash j}\mu_{h_{k}\rightarrow e_i}(e_i)$ ;

$b_i(e_i)\propto p(e_i)\prod_{k\in N(i)}\mu_{h_{k}\rightarrow e_i}(e_i)$ ;

4. Оценка вектора ошибок:

$\hat{e}_i=\arg\max b_i(e_i)$ ;

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

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

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

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

Оптимизации в процедуре декодирования

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

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

Рассмотрим более эффективную схему реализации шага 2. Пусть нам необходимо вычислить сообщение $\mu_{h_j\rightarrow e_i}(e_i)$ . Перенумеруем все переменные, входящие в j-ый фактор (кроме переменной $e_i$ ), как $e_{(1)},e_{(2)},\dots,e_{(l)}$ , где $l=|N(j)|-1$ . Тогда вычисление сообщения $\mu_{h_j\rightarrow e_i}(e_i)$ можно записать как

$\mu_{h_j\rightarrow e_i}(e_i)\propto\sum_{e_{(k)}}I[\sum_{k=1}^le_{(k)} = s_j+e_i]\prod_{k=1}^l\mu_{e_{(k)}\rightarrow h_j}(e_{(k)})$ .

Данный результат можно интерпретировать как вычисление вероятности $p(\sum_{k=1}^le_{(k)}=s_j+e_i)$ для набора независимых бинарных переменных $e_{(k)}$ с распределением $p_{(k)}(e_{(k)}) = \mu_{e_{(k)}\rightarrow h_j}(e_{(k)}).$ Обозначим через $e^k$ сумму первых $k$ переменных $e_{(k)}$ , т.е. $e^k=e_{(1)}+e_{(2)}+\dots+e_{(k)}$ . Тогда распределение на $e^k$ можно итерационно пересчитывать по формуле

$p_k(e^k) = \sum_{e^{k-1}}p_{k-1}(e^{k-1})p_{(k)}(e^k-e^{k-1})$ .

В результате вычисление $p_l(e^l)$ имеет линейную по $l$ сложность.

Дальнейшее повышение эффективности реализации шага 2 связано с рассмотрением разностей вероятностей $\delta p_{(k)} = p_{(k)}(0) - p_{(k)}(1)$ и $\delta p_k = p_k(0)-p_k(1)$ . Нетрудно показать, что

$\delta p_l = \prod_{k=1}^l\delta p_{(k)}$ . (*)

Зная значение $\delta p_l$ и учитывая условие нормировки $p_l(0)+p_l(1)=1$ , сами вероятности могут быть вычислены как $p_l(0)=\frac{1}{2}(1+\delta p_l)$ , $p_l(1)=\frac{1}{2}(1-\delta p_l)$ . Таким образом, $\mu_{h_j\rightarrow e_i}(e_i) = p_l(s_j+e_i)$ . Основное преимущество условия (*) по сравнению с последовательным пересчётом распределений $p_k(e^k)$ связано с тем, что формула (*) может быть реализована с помощью векторных операций в MATLAB.

Расписание пересчёта сообщений и дэмпфирование

Общая схема циклического алгоритма передачи сообщений оставляет определённый произвол в выборе расписания пересчёта сообщений. Обычно здесь рассматриваются следующие подходы:

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

При использовании дэмпфирования с параметром $\lambda\in(0,1]$ сообщения на итерации $t$ пересчитываются как

$\mu^t_{h_j\rightarrow e_i}(e_i) = \lambda\mu_{h_j\rightarrow e_i}(e_i) + (1-\lambda)\mu^{t-1}_{h_j\rightarrow e_i}(e_i)$ ;

$\mu^t_{e_i\rightarrow h_j}(e_i) = \lambda\mu_{e_i\rightarrow h_j}(e_i) + (1-\lambda)\mu^{t-1}_{e_i\rightarrow h_j}(e_i)$ .

Здесь $\mu_{h_j\rightarrow e_i}(e_i)$ и $\mu_{e_i\rightarrow h_j}(e_i)$ — сообщения, вычисляемые на шагах 2 и 3 общего алгоритма декодирования.

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

Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP; при реализации шага 2 пересчета сообщений от факторов к переменным необходимо использовать эффективные схемы, обозначенные выше; реализовать последовательное и параллельное расписание пересчёта сообщений, а также дэмпфирование сообщений; при реализации на MATLAB одной итерации схемы передачи сообщений использование вложенных циклов является нежелательным;
Провести эксперименты с различными расписаниями пересчёта сообщений и коэффициентами дэмпфирования; в частности, оценить долю стабилизировавшихся beliefs в зависимости от номера итерации алгоритма декодирования (усреднённую по различным запускам); оценить время работы алгоритма декодирования в зависимости от выбранного расписания и коэффициента дэмпфирования;
Рассмотрим две характеристики качества кода — вероятность совершить ошибку хотя бы в одном бите при декодировании блока ( $p(\hat{e}\neq e)$ ) и среднюю вероятность совершить ошибку при декодировании в одном бите ( $\frac{1}{n}\sum_{i=1}^np(\hat{e}_i\neq e_i)$ ). Требуется реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний (многократная случайная генерация вектора ошибок $e$ ( $e_i=1$ с вероятностью $q$ ), вычисление по нему синдрома $s=He$ , восстановление вектора ошибок $\hat{e}$ с помощью алгоритма декодирования и подсчет необходимых характеристик);
Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова , скорости кода , вероятности инвертирования бита при передаче по каналу связи и среднего количества единиц в столбце проверочной матрицы . В частности, необходимо проанализировать следующие ситуации:
- Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости $r$ от минимального значения до пропускной способности канала.
- Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова $n$ . Требуется проверить это предположение.
- Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы $j$ . Требуется проверить это утверждение для низкоплотностных кодов (путём рассмотрения нескольких значений $j$ , начиная от 3).
Провести эксперименты по сравнению низкоплотностного кода с кодами БЧХ;
Составить отчёт в формате PDF с описанием всех проведённых исследований. Данный отчёт обязательно должен содержать описание отладочных тестов, которые проводились для проверки корректности реализованных алгоритмов. Также в этом отчёте должны быть графики поведения характеристик кода в зависимости от значений различных параметров.

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

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

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

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

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

[G, ind] = ldpc_gen_matrix(H)

ВХОД

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

ВЫХОД

G — порождающая матрица кода, бинарная матрица размера n x k;

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

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

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

ВХОД

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

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

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

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

'schedule' — расписание пересчёта сообщений, возможные значения 'parallel' и 'sequential', по умолчанию = 'parallel';

'damping' — коэффициент дэмпфирования при пересчёте сообщений, число от 0 до 1, по умолчанию = 1;

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

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

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

ВЫХОД

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

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

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

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

ВХОД

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

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

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

ВЫХОД

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

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

diver — доля ситуаций расходимости алгоритма декодирования, число от 0 до 1, err_bit и err_block вычисляются только по тем ситуациям, когда алгоритм декодирования сошёлся.

Источник — «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»

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

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

Содержание

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

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

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

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

Оптимизации в процедуре декодирования

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

Расписание пересчёта сообщений и дэмпфирование

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты