Материал из MachineLearning.
| Формулировка задания находится в стадии разработки. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.
|
-
Начало выполнения задания: 3 марта 2013 г.
Срок сдачи: 17 марта 2013 г., 23:59.
Среда для выполнения задания — MATLAB.
Низкоплотностные коды
Формулировка задания
- Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
- Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP, провести временные замеры реализованного алгоритма для различных значений входных параметров, время работы алгоритма не должно превышать XX секунд для ...
- Реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний;
- Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова N, скорости кода R, вероятности инвертирования бита при передаче по каналу связи q и среднего количества единиц в столбце проверочной матрицы j. В частности, необходимо проанализировать следующие ситуации:
- Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
- Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
- Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов.
Рекомендации по выполнению задания
Оформление задания
Выполненное задание следует отправить письмом по адресу 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.
|
|
