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

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

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

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

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

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

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

Низкоплотностный код (или код с малой плотностью проверок на чётность) представляет собой (N,K)-бинарный линейный блоковый код, в котором проверочная матрица является сильно разреженной. Таким образом, вектор является кодовым словом, если .

Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью q. Таким образом, бинарный симметричный канал задает распределение для передаваемого кодового слова и полученного на выходе слова как

.

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

.

Здесь M=N-K — количество проверок на чётность, а является m-ой строкой матрицы H.

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

1. Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
2. Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP, провести временные замеры реализованного алгоритма для различных значений входных параметров, время работы алгоритма не должно превышать XX секунд для ...
3. Реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний;
4. Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова N, скорости кода R, вероятности инвертирования бита при передаче по каналу связи q и среднего количества единиц в столбце проверочной матрицы j. В частности, необходимо проанализировать следующие ситуации:
   • Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
   • Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
   • Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов.

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

1. Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться данным кодом, который генерирует проверочную матрицу с заданным количеством единиц в каждом столбце. При этом данный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP.
2. Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование может быть сделано с помощью гауссовских исключений. При выполнении задания разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 2 самостоятельно, т.к. такая реализация может быть сделана значительно эффективнее по сравнению с общим случаем логики по модулю произвольного простого числа, т.к. в логике по модулю два нет необходимости использовать операцию деления и, например, искать ведущий элемент при очередном вычитании (т.к. все ненулевые элементы равны единице).
3. В эффективной реализации алгоритма декодирования все вычисления на очередной итерации не должны использовать вложенных циклов.

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

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

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

• Текстовый файл в формате PDF с указанием ФИО, содержащий описание всех проведенных исследований. Данный файл должен, в частности, содержать необходимые графики зависимости битовой и блоковой ошибки кода в зависимости от различных значений параметров.
• Все исходные коды с необходимыми комментариями.

 

Построение порождающей матрицы для систематического кодирования
[G, ind] = ldpc_gen_matrix(H)
ВХОД
H — проверочная матрица чётности, бинарная матрица размера MxN;
ВЫХОД
G — порождающая матрица кода, бинарная матрица размера Nx(N-M); ind — номера позиций кодового слова, в которые копируются биты исходного сообщения, т.е. G(ind, :) является единичной матрицей.

 

Алгоритм декодирования LDPC-кода в синдромном представлении
[n, 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, то отображается промежуточная информация на итерациях, например, номер итерации, текущее число ошибок декодирования, невязка для сообщений и т.д.
ВЫХОД
n — восстановленный вектор ошибок, бинарный вектор-столбец длины N; status — результат декодирования, равен 0, если вектор n восстановлен без ошибок, равен -1, если произошел выход по максимальному числу итераций или стабилизации значений сообщений.

 

Оценка характеристик LDPC-кода с помощью метода Монте Карло
[err_bit, err_block, diver] = ldpc_mc(H, G, g, 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.