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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Оформление задания)
Строка 15: Строка 15:
== Формулировка задания ==
== Формулировка задания ==
 +
 +
# Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
 +
# Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP, провести временные замеры реализованного алгоритма для различных значений входных параметров, время работы алгоритма не должно превышать XX секунд для ...
 +
# Реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний;
 +
# Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова N, скорости кода R, вероятности инвертирования бита при передаче по каналу связи q и среднего количества единиц в столбце проверочной матрицы j. В частности, необходимо проанализировать следующие ситуации:
 +
#* Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
 +
#* Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
 +
#* Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов.
== Рекомендации по выполнению задания ==
== Рекомендации по выполнению задания ==
Строка 24: Строка 32:
Присланный вариант задания должен содержать в себе:
Присланный вариант задания должен содержать в себе:
-
* Текстовый файл в формате PDF с указанием ФИО, содержащий описание всех проведенных исследований.
+
* Текстовый файл в формате PDF с указанием ФИО, содержащий описание всех проведенных исследований. Данный файл должен, в частности, содержать необходимые графики зависимости битовой и блоковой ошибки кода в зависимости от различных значений параметров.
* Все исходные коды с необходимыми комментариями.
* Все исходные коды с необходимыми комментариями.
Строка 30: Строка 38:
!''Построение порождающей матрицы для систематического кодирования''
!''Построение порождающей матрицы для систематического кодирования''
|-
|-
-
|[G, ind] = '''LDPC_gen_matrix'''(H)
+
|[G, ind] = '''ldpc_gen_matrix'''(H)
|-
|-
|ВХОД
|ВХОД
Строка 54: Строка 62:
!''Алгоритм декодирования LDPC-кода в синдромном представлении''
!''Алгоритм декодирования LDPC-кода в синдромном представлении''
|-
|-
-
|[n, status] = '''LDPC_decoding'''(z, H, q, param_name1, param_value1, ...)
+
|[n, status] = '''ldpc_decoding'''(z, H, q, param_name1, param_value1, ...)
|-
|-
|ВХОД
|ВХОД
Строка 94: Строка 102:
!''Оценка характеристик LDPC-кода с помощью метода Монте Карло''
!''Оценка характеристик LDPC-кода с помощью метода Монте Карло''
|-
|-
-
|[err_bit, err_block, diver] = '''LDPC_MC'''(H, G, g, num_points)
+
|[err_bit, err_block, diver] = '''ldpc_mc'''(H, G, g, num_points)
|-
|-
|ВХОД
|ВХОД

Версия 14:01, 2 марта 2013

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


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


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

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

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

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

  1. Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
  2. Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP, провести временные замеры реализованного алгоритма для различных значений входных параметров, время работы алгоритма не должно превышать XX секунд для ...
  3. Реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний;
  4. Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова 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.
Источник — «http://www.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/2013/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_2»
Личные инструменты