Материал из MachineLearning.
| Внимание! Текст задания находится в стадии разработки. Просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.
|
-
 Демонстрация процесса кодирования/декодирования с использованием низкоплотностного кода. Кодируемое сообщение (изображение цифры) содержит значительную избыточность для возможности визуальной оценки процесса декодирования. Алгоритм декодирования не использует свойство избыточности входного сигнала. |
Начало выполнения задания: 4 марта 2014 г.
Срок сдачи: 18 марта 2014 г., 23:59.
Среда для выполнения задания — MATLAB.
Задача помехоустойчивого кодирования
Рассмотрим решение задачи безошибочной передачи потока битовой информации по каналу с шумом с помощью кодов, исправляющих ошибки. При блоковом кодировании входящий поток информации разбивается на блоки фиксированной длины 
, и каждый блок кодируется/декодируется независимо. Обозначим один такой блок через 
. Предположим, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок 
в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через 
, 
. Для кодирования всевозможных блоков необходимо использовать 
кодовых слов длины 
. Назовём множество кодовых слов длины (n,k)-блоковым кодом, а величину 
— скоростью кода. При передаче по каналу с шумом кодовое слово 
превращается в принятое слово 
, которое, вообще говоря, отличается от . Предположим, что при передаче по каналу длина сообщения не изменяется, т.е. 
, а происходит лишь инверсия некоторых бит. Задача алгоритма декодирования состоит в восстановлении по переданного слова (например, путем поиска среди всевозможных кодовых слов ближайшего к ). Обозначим результат работы алгоритма декодирования через 
. На последнем этапе декодированное слово переводится в декодированное слово исходного сообщения 
.
Кодирование с помощью (n,k)-линейного блокового кода
Множество 
с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов 
. (n,k)-блоковый код называется линейным, если множество его кодовых слов образует линейное подпространство размерности общего линейного пространства . Одним из способов задания -мерного линейного подпространства является рассмотрение множества решений следующей системы линейных уравнений:
,
где {\times}n})
— матрица ранга 
(эта матрица задаёт базис линейного подпространства, ортогонального к рассматриваемому (n,k)-коду). Матрица 
называется проверочной матрицей кода, т.к. с её помощью можно проверить, является ли слово кодовым словом путём проверки соотношения (здесь и далее все операции проводятся по модулю 2).
Рассмотрим задачу кодирования слов исходного сообщения в кодовые слова (n,k)-линейного блокового кода, заданного своей проверочной матрицей . Для этого можно найти базис -мерного линейного подпространства 
. Тогда, рассматривая базисные вектора как столбцы общей матрицы 
, операция кодирования может быть представлена как 
. Матрица 
называется порождающей матрицей кода. Кодирование называется систематическим, если все биты слова копируются в некоторые биты кодового слова , т.е. в матрице некоторое подмножество строк образует единичную матрицу размера 
. При систематическом кодировании обратный процесс преобразования из декодированного кодового слова в декодированное сообщение становится тривиальным.
Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование всегда может быть сделано с помощью гауссовских исключений. С точностью до перестановки столбцов канонический ступенчатый вид матрицы эквивалентен её представлению в виде 
, где 
— единичная матрица размера 
. Тогда в качестве порождающей матрицы, обеспечивающей систематическое кодирование, можно выбрать матрицу
.
Действительно, в этом случае u = 0)
.
Декодирование низкоплотностного кода
Фактор-граф для (16,4)-низкоплотностного кода, в проверочной матрице которого в каждом столбце по 3 единицы, а в каждой строке - по 4 единицы.
Низкоплотностным кодом (или кодом с малой плотностью проверок на чётность) называется бинарный (n,k)-линейный блоковый код, в котором проверочная матрица 
является сильно разреженной.
Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью 
. В результате бинарный симметричный канал задает распределение )
для передаваемого кодового слова и полученного на выходе слова как
 = \prod_{i=1}^np(w_i|v_i) = \prod_{i=1}^nq^{w_i+v_i}(1-q)^{w_i+v_i+1})
.
Пропускная способность данного канала определяется величиной \log_2(1-q))
.
Объединяя низкоплотностный код с бинарным симметричным каналом, получаем следующую вероятностную модель для пары 
:
![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]](../mimetex/?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])
.
Здесь — количество проверок на чётность, 
— j-ая строка матрицы H, а ![I[\cdot]](../mimetex/?I[\cdot])
— индикаторная функция. Фактор-граф введённой модели показан на рис. справа.
Назовём синдромом принятого слова вектор 
, определяемый как 
. Процесс передачи кодового слова по бинарному симметричному каналу можно представить как 
, где 
— вектор ошибок (
, если в позиции 
произошла ошибка). Тогда  = Hv+He = He)
. Далее можно перейти от вероятностной модели для переменных 
к аналогичной для переменных 
:
![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]](../mimetex/?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])
.
Здесь =q^{e_i}(1-q)^{1-e_i})
. Зная значение вектора ошибок 
, результат декодирования вычисляется как 
. При использовании вероятностной модели для тестирование алгоритма декодирования можно проводить без предварительной реализации процедуры кодирования.
При использовании побитовой функции потерь ![\lambda(e,\tilde{e}) = \sum_{i=1}^nI[e_i\neq \tilde{e}_i]](../mimetex/?\lambda(e,\tilde{e}) = \sum_{i=1}^nI[e_i\neq \tilde{e}_i])
оптимальная процедура декодирования связана с максимизацией маргиналов отдельных переменных, т.е. )
. Для поиска маргинальных распределений )
воспользуемся циклическим алгоритмом передачи сообщений (sum-product loopy BP) на фактор-графе. Введём обозначения =\{j:H_{ji}=1\})
— множество факторов, в которых участвует переменная 
, и =\{i:H_{ji}=1\})
— множество переменных, которые входят в фактор 
. Тогда общая схема алгоритма декодирования выглядит следующим образом:
1. Инициализация:
-
 = 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})](../mimetex/?\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 (оценок на маргинальные распределения):
-
 \propto p(e_i)\prod_{k\in N(i)\backslash j}\mu_{h_{k}\rightarrow e_i}(e_i))
;
-
\propto p(e_i)\prod_{k\in N(i)}\mu_{h_{k}\rightarrow e_i}(e_i))
;
4. Оценка вектора ошибок:
-
)
;
5. Критерий остановки:
- Если
, то выход алгоритма со статусом 0;
- Если достигнуто максимальное число итераций или произошла стабилизация по всем
, то выход алгоритма со статусом -1;
- Переход к шагу 2.
Оптимизация в процедуре декодирования
При прямой реализации шага 2 общего алгоритма декодирования требуется рассмотрение для каждого фактора |-1})
различных конфигураций значений переменных 
. Это может приводить как к низкой скорости пересчета сообщений, так и к большим требованиям по памяти.
Рассмотрим более эффективную схему реализации шага 2. Пусть нам необходимо вычислить сообщение )
. Перенумеруем все переменные, входящие в j-ый фактор (кроме переменной ), как },e_{(2)},\dots,e_{(l)})
, где |-1)
. Тогда вычисление сообщения можно записать как
![\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)})](../mimetex/?\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)}))
.
Данный результат можно интерпретировать как вычисление вероятности }=s_j+e_i))
для набора независимых бинарных переменных })
с распределением }(e_{(k)}) = \mu_{e_{(k)}\rightarrow h_j}(e_{(k)}).)
Обозначим через 
сумму первых переменных , т.е. }+e_{(2)}+\dots+e_{(k)})
. Тогда распределение на можно итерационно пересчитывать по формуле
 = \sum_{e^{k-1}}p_{k-1}(e^{k-1})p_{(k)}(e^k-e^{k-1}))
.
В результате вычисление )
имеет линейную по 
сложность.
Дальнейшее повышение эффективности реализации шага 2 связано с рассмотрением разностей вероятностей } = p_{(k)}(0) - p_{(k)}(1))
и -p_k(1))
. Нетрудно показать, что
})
. (*)
Зная значение 
и учитывая условие нормировки +p_l(1)=1)
, сами вероятности могут быть вычислены как =\frac{1}{2}(1+\delta p_l))
, =\frac{1}{2}(1-\delta p_l))
. Таким образом,  = p_l(s_j+e_i))
. Основное преимущество условия (*) по сравнению с последовательным пересчётом распределений )
связано с тем, что формула (*) может быть реализована с помощью векторных операций в MATLAB.
Формулировка задания
- Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
- Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP; при реализации шага 2 пересчета сообщений от факторов к переменным необходимо использовать эффективные схемы, обозначенные выше; при реализации на MATLAB одной итерации схемы передачи сообщений использование вложенных циклов является нежелательным; провести временные замеры реализованного алгоритма для различных значений входных параметров;
- Рассмотрим две характеристики качества кода — вероятность совершить ошибку хотя бы в одном бите при декодировании блока (
)
) и среднюю вероятность совершить ошибку при декодировании в одном бите ()
). Требуется реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний (многократная случайная генерация слова 
, его преобразование к кодовому слову 
, передача по каналу с независимым инвертированием каждого бита с заданной вероятностью , восстановление кодового слова 
с помощью алгоритма декодирования и подсчет необходимых характеристик);
- Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова N, скорости кода R, вероятности инвертирования бита при передаче по каналу связи q и среднего количества единиц в столбце проверочной матрицы j. В частности, необходимо проанализировать следующие ситуации:
- Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
- Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
- Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов (путём рассмотрения нескольких значений j, начиная от 3).
- Составить отчёт в формате PDF с описанием всех проведённых исследований. Данный отчёт обязательно должен содержать описание отладочных тестов, которые проводились для проверки корректности реализованных алгоритмов. Также в этом отчёте должны быть графики поведения характеристик кода в зависимости от значений различных параметров.
Рекомендации по выполнению задания
1. Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться готовой реализацией, которая генерирует проверочную матрицу заданного размера с заданным количеством единиц в каждом столбце. При этом реализованный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP.
2. При построении порождающей матрицы кода по заданной проверочной матрице с помощью алгоритма гауссовских исключений разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, здесь рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 2 самостоятельно, т.к. такая реализация может быть сделана значительно эффективнее по сравнению с общим случаем логики по модулю произвольного простого числа. Действительно, в логике по модулю два нет необходимости использовать операцию деления, а также искать ведущий элемент при очередном вычитании ввиду того, что все ненулевые элементы равны единице.
3. Алгоритм декодирования удобно реализовывать в т.н. синдромном представлении. Полученное на выходе канала слово 
можно представить как 
, где — посылаемое кодовое слово, а 
— вектор ошибок, которые вносит канал. Назовём величину 
синдромом полученного сообщения. Тогда =He)
, и на этапе декодирования можно вместо оценивать вектор ошибок 
путем оценки аргмаксимумов маргинальных распределений )
в вероятностной модели
![p(e,z)\propto p(e)I[He=z]=\prod_{n=1}^Np(e_n)\prod_{m=1}^MI[h_m^Te=z_m]](../mimetex/?p(e,z)\propto p(e)I[He=z]=\prod_{n=1}^Np(e_n)\prod_{m=1}^MI[h_m^Te=z_m])
.
Для бинарного симметричного канала  = q^{e_n}(1-q)^{e_n+1})
. Зная , искомое кодовое слово можно найти как 
. Заметим, что реализация алгоритма декодирования в синдромном представлении избавляет от необходимости предварительной реализации алгоритма кодирования.
4. При тестировании алгоритма декодирования рекомендуется пробовать запускать итерационный процесс из различных начальных приближений для сообщений (не только из значений унарных потенциалов). При корректной реализации метода должна наблюдаться сходимость к одним и тем же финальным сообщениям независимо от начальных приближений.
Оформление задания
Выполненное задание следует отправить письмом по адресу 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.
|
|
