Графические модели (курс лекций)/2014/Задание 2
Материал из MachineLearning.
Внимание! Текст задания находится в стадии разработки. Просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено. |
|
Начало выполнения задания: 4 марта 2014 г.
Срок сдачи: 18 марта 2014 г., 23:59.
Среда для выполнения задания — MATLAB.
Низкоплотностные коды
Задача помехоустойчивого кодирования
Рассмотрим решение задачи безошибочной передачи потока битовой информации по каналу с шумом с помощью кодов, исправляющих ошибки. При блоковом кодировании входящий поток информации разбивается на блоки фиксированной длины , и каждый блок кодируется/декодируется независимо. Обозначим один такой блок через . Предположим, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через , . Для кодирования всевозможных блоков необходимо использовать кодовых слов длины . Назовём множество кодовых слов длины (n,k)-блоковым кодом, а величину — скоростью кода. При передаче по каналу с шумом кодовое слово превращается в принятое слово , которое, вообще говоря, отличается от . Предположим, что при передаче по каналу длина сообщения не изменяется, т.е. , а происходит лишь инверсия некоторых бит. Задача алгоритма декодирования состоит в восстановлении по переданного слова (например, путем поиска среди всевозможных кодовых слов ближайшего к ). Обозначим результат работы алгоритма декодирования через . На последнем этапе декодированное слово переводится в декодированное слово исходного сообщения .
Кодирование с помощью (n,k)-линейного блокового кода
Множество с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов . (n,k)-блоковый код называется линейным, если множество его кодовых слов образует линейное подпространство размерности общего линейного пространства . Одним из способов задания -мерного линейного подпространства является рассмотрение множества решений следующей системы линейных уравнений:
- ,
где — матрица ранга (эта матрица задаёт базис линейного подпространства, ортогонального к рассматриваемому (n,k)-коду). Матрица называется проверочной матрицей кода, т.к. с её помощью можно проверить, является ли слово кодовым словом путём проверки соотношения (здесь и далее все операции проводятся по модулю 2).
Рассмотрим задачу кодирования слов исходного сообщения в кодовые слова (n,k)-линейного блокового кода, заданного своей проверочной матрицей . Для этого можно найти базис -мерного линейного подпространства . Тогда, рассматривая базисные вектора как столбцы общей матрицы , операция кодирования может быть представлена как . Матрица называется порождающей матрицей кода. Кодирование называется систематическим, если все биты слова копируются в некоторые биты кодового слова , т.е. в матрице некоторое подмножество строк образует единичную матрицу размера . При систематическом кодировании обратный процесс преобразования из декодированного кодового слова в декодированное сообщение становится тривиальным.
Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование всегда может быть сделано с помощью гауссовских исключений. С точностью до перестановки столбцов канонический ступенчатый вид матрицы эквивалентен её представлению в виде , где — единичная матрица размера . Тогда в качестве порождающей матрицы, обеспечивающей систематическое кодирование, можно выбрать матрицу
- .
Действительно, в этом случае .
Декодирование низкоплотностного кода
Низкоплотностным кодом (или кодом с малой плотностью проверок на чётность) называется бинарный (n,k)-линейный блоковый код, в котором проверочная матрица является сильно разреженной.
Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью . В результате бинарный симметричный канал задает распределение для передаваемого кодового слова и полученного на выходе слова как
- .
Пропускная способность данного канала определяется величиной .
Объединяя низкоплотностный код с бинарным симметричным каналом, получаем следующую вероятностную модель для пары :
- .
Здесь — количество проверок на чётность, — j-ая строка матрицы H, а — индикаторная функция. Фактор-граф введённой модели показан на рис. справа.
Назовём синдромом принятого слова вектор , определяемый как . Процесс передачи кодового слова по бинарному симметричному каналу можно представить как , где — вектор ошибок (, если в позиции произошла ошибка). Тогда . Далее можно перейти от вероятностной модели для переменных к аналогичной для переменных :
- .
Здесь . Зная значение вектора ошибок , результат декодирования вычисляется как . При использовании вероятностной модели для тестирование алгоритма декодирования можно проводить без предварительной реализации процедуры кодирования.
При использовании побитовой функции потерь оптимальная процедура декодирования связана с максимизацией маргиналов отдельных переменных, т.е. . Для поиска маргинальных распределений воспользуемся циклическим алгоритмом передачи сообщений (sum-product loopy BP) на фактор-графе. Введём обозначения — множество факторов, в которых участвует переменная , и — множество переменных, которые входят в фактор . Тогда общая схема алгоритма декодирования выглядит следующим образом:
1. Инициализация:
- ;
2. Пересчет сообщений от факторов:
- ;
3. Пересчет сообщений от переменных и вычисление beliefs (оценок на маргинальные распределения):
- ;
- ;
4. Оценка вектора ошибок:
- ;
5. Критерий остановки:
- Если , то выход алгоритма со статусом 0;
- Если достигнуто максимальное число итераций или произошла стабилизация по всем , то выход алгоритма со статусом -1;
- Переход к шагу 2.
При прямой реализации данного алгоритма на шаге 2 требуется рассмотрение для каждого фактора различных конфигураций переменных. Это может приводить как к низкой скорости пересчета сообщений, так и к большим требованиям по памяти.
Рассмотрим более эффективную схему реализации шага 2 путем его сведения к задаче вывода в графической модели с графом-цепочкой. Пусть нам необходимо вычислить сообщение . Перенумеруем все переменные, входящие в m-ый фактор (кроме переменной ), как . Рассмотрим графическую модель с бинарными переменными и графом
Положим, что . Определим априорное распределение и вероятность перехода как
- ;
Тогда требуемое сообщение поэлементно равно маргинальному распределению , которое может быть эффективно вычислено путем однократной пересылки сообщений вдоль цепи от до .
Дальнейшее повышение эффективности реализации шага 2 связано с рассмотрением разностей значений сообщений и . В терминах разностей можно показать, что новое значение может быть вычислено как
- . (*)
Зная значение и учитывая условие нормировки на сообщения, сами сообщения от факторов могут быть вычислены как
- ; .
Основное преимущество условия (*) по сравнению с пересчетом сообщений для связано с тем, что формула (*) может быть реализована с помощью векторных операций в 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. Алгоритм декодирования удобно реализовывать в т.н. синдромном представлении. Полученное на выходе канала слово можно представить как , где — посылаемое кодовое слово, а — вектор ошибок, которые вносит канал. Назовём величину синдромом полученного сообщения. Тогда , и на этапе декодирования можно вместо оценивать вектор ошибок путем оценки аргмаксимумов маргинальных распределений в вероятностной модели
- .
Для бинарного симметричного канала . Зная , искомое кодовое слово можно найти как . Заметим, что реализация алгоритма декодирования в синдромном представлении избавляет от необходимости предварительной реализации алгоритма кодирования.
4. При тестировании алгоритма декодирования рекомендуется пробовать запускать итерационный процесс из различных начальных приближений для сообщений (не только из значений унарных потенциалов). При корректной реализации метода должна наблюдаться сходимость к одним и тем же финальным сообщениям независимо от начальных приближений.
Оформление задания
Выполненное задание следует отправить письмом по адресу bayesml@gmail.com с заголовком письма «[ГМ13] Задание 2 <ФИО>». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.
Присланный вариант задания должен содержать в себе:
- Файл отчёта в формате PDF с указанием ФИО.
- Все исходные коды с необходимыми комментариями.
Построение порождающей матрицы для систематического кодирования | ||
---|---|---|
[G, ind] = ldpc_gen_matrix(H) | ||
ВХОД | ||
| ||
ВЫХОД | ||
|
Алгоритм декодирования LDPC-кода в синдромном представлении | ||||||||
---|---|---|---|---|---|---|---|---|
[e, status] = ldpc_decoding(z, H, q, param_name1, param_value1, ...) | ||||||||
ВХОД | ||||||||
| ||||||||
ВЫХОД | ||||||||
|
Оценка характеристик LDPC-кода с помощью метода Монте Карло | ||||
---|---|---|---|---|
[err_bit, err_block, diver] = ldpc_mc(H, G, q, num_points) | ||||
ВХОД | ||||
| ||||
ВЫХОД | ||||
|