Графические модели (курс лекций)/2013/Задание 2
Материал из MachineLearning.
(Различия между версиями)
| Строка 12: | Строка 12: | ||
Среда для выполнения задания — MATLAB. | Среда для выполнения задания — MATLAB. | ||
| - | == Низкоплотностные коды == | + | == [http://en.wikipedia.org/wiki/LDPC Низкоплотностные коды] == |
| + | |||
| + | Низкоплотностный код (или код с малой плотностью проверок на чётность) представляет собой (N,K)-бинарный линейный блоковый код, в котором проверочная матрица <tex>H\in\{0,1\}^{(N-K)\times N}</tex> является сильно разреженной. Таким образом, вектор <tex>x\in\{0,1\}^N</tex> является кодовым словом, если <tex>Hx = 0 (mod\ 2)</tex>. | ||
| + | |||
| + | Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью q. Таким образом, бинарный симметричный канал задает распределение <tex>p(y|x)</tex> для передаваемого кодового слова <tex>x\in\{0,1\}^N</tex> и полученного на выходе слова <tex>y\in\{0,1\}^N</tex> как | ||
| + | |||
| + | <tex>p(y|x) = \prod_{n=1}^Np(y_n|x_n) = \prod_{n=1}^Nq^{y_n+x_n}(1-q)^{y_n+x_n+1}</tex>. | ||
| + | |||
| + | Объединяя низкоплотностный код с бинарным симметричным каналом, получаем следующую вероятностную модель для пары <tex>x,y</tex>: | ||
| + | |||
| + | <tex>p(y,x)\propto p(y|x)I[Hx=0] = \prod_{n=1}^Np(y_n|x_n)\prod_{m=1}^MI[h_m^Tx = 0]</tex>. | ||
| + | |||
| + | Здесь M=N-K — количество проверок на чётность, а <tex>h_m^T</tex> является m-ой строкой матрицы H. | ||
== Формулировка задания == | == Формулировка задания == | ||
| Строка 28: | Строка 40: | ||
# Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться [[Media:make_ldpc_mex.zip|данным кодом]], который генерирует проверочную матрицу с заданным количеством единиц в каждом столбце. При этом данный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP. | # Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться [[Media:make_ldpc_mex.zip|данным кодом]], который генерирует проверочную матрицу с заданным количеством единиц в каждом столбце. При этом данный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP. | ||
# Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование может быть сделано с помощью [http://en.wikipedia.org/wiki/Gaussian_elimination гауссовских исключений]. При выполнении задания разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 2 самостоятельно, т.к. такая реализация может быть сделана значительно эффективнее по сравнению с общим случаем логики по модулю произвольного простого числа, т.к. в логике по модулю два нет необходимости использовать операцию деления и, например, искать ведущий элемент при очередном вычитании (т.к. все ненулевые элементы равны единице). | # Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование может быть сделано с помощью [http://en.wikipedia.org/wiki/Gaussian_elimination гауссовских исключений]. При выполнении задания разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 2 самостоятельно, т.к. такая реализация может быть сделана значительно эффективнее по сравнению с общим случаем логики по модулю произвольного простого числа, т.к. в логике по модулю два нет необходимости использовать операцию деления и, например, искать ведущий элемент при очередном вычитании (т.к. все ненулевые элементы равны единице). | ||
| + | # В эффективной реализации алгоритма декодирования все вычисления на очередной итерации не должны использовать вложенных циклов. | ||
== Оформление задания == | == Оформление задания == | ||
Версия 14:57, 2 марта 2013
| Формулировка задания находится в стадии разработки. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено. |
Начало выполнения задания: 3 марта 2013 г.
Срок сдачи: 17 марта 2013 г., 23:59.
Среда для выполнения задания — MATLAB.
Низкоплотностные коды
Низкоплотностный код (или код с малой плотностью проверок на чётность) представляет собой (N,K)-бинарный линейный блоковый код, в котором проверочная матрица является сильно разреженной. Таким образом, вектор
является кодовым словом, если
.
Рассмотрим бинарный симметричный канал для передачи данных. Здесь при передаче каждый бит независимо инвертируется с некоторой вероятностью q. Таким образом, бинарный симметричный канал задает распределение для передаваемого кодового слова
и полученного на выходе слова
как
.
Объединяя низкоплотностный код с бинарным симметричным каналом, получаем следующую вероятностную модель для пары :
.
Здесь M=N-K — количество проверок на чётность, а является m-ой строкой матрицы H.
Формулировка задания
- Реализовать алгоритм построения по заданной проверочной матрице чётности H порождающей матрицы кода G для систематического кодирования;
- Реализовать алгоритм декодирования низкоплотностного кода на основе loopy BP, провести временные замеры реализованного алгоритма для различных значений входных параметров, время работы алгоритма не должно превышать XX секунд для ...
- Реализовать алгоритм оценки вероятности битовой и блоковой ошибки кода с помощью метода стат. испытаний;
- Провести эксперименты по оцениванию битовой и блоковой ошибки низкоплотностного кода для различных значений длины кодового слова N, скорости кода R, вероятности инвертирования бита при передаче по каналу связи q и среднего количества единиц в столбце проверочной матрицы j. В частности, необходимо проанализировать следующие ситуации:
- Теорема Шеннона определяет пропускную способность канала как максимально допустимую скорость кода, при которой возможно осуществление надежной коммуникации. Требуется проверить, как меняются характеристики кода при изменении скорости R от минимального значения до пропускной способности канала.
- Теорема Шеннона предполагает, что качество кода растет при увеличении длины кодового слова N. Требуется проверить это предположение.
- Одно из следствий теоремы Шеннона утверждает, что хорошими кодами являются коды со случайной проверочной матрицей H. В частности, здесь предполагается, что качество кода должно расти при увеличении среднего количества единиц в столбце проверочной матрицы j. Требуется проверить это утверждение для низкоплотностных кодов.
Рекомендации по выполнению задания
- Разреженную проверочную матрицу кода заданных размеров можно строить с помощью случайной генерации (с соблюдением условия полноранговости). Однако, здесь рекомендуется воспользоваться данным кодом, который генерирует проверочную матрицу с заданным количеством единиц в каждом столбце. При этом данный алгоритм старается сократить количество циклов длины 4 в генерируемой матрице, т.к. наличие коротких циклов в графе, как правило, значительно усложняет работу алгоритма loopy BP.
- Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование может быть сделано с помощью гауссовских исключений. При выполнении задания разрешается пользоваться сторонними кодами по реализации стандартных алгоритмов линейной алгебры (с соответствующими указаниями в отчёте). Однако, рекомендуется реализовывать алгоритм гауссовских исключений в логике по модулю 2 самостоятельно, т.к. такая реализация может быть сделана значительно эффективнее по сравнению с общим случаем логики по модулю произвольного простого числа, т.к. в логике по модулю два нет необходимости использовать операцию деления и, например, искать ведущий элемент при очередном вычитании (т.к. все ненулевые элементы равны единице).
- В эффективной реализации алгоритма декодирования все вычисления на очередной итерации не должны использовать вложенных циклов.
Оформление задания
Выполненное задание следует отправить письмом по адресу bayesml@gmail.com с заголовком письма «[ГМ13] Задание 2 <ФИО>». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.
Присланный вариант задания должен содержать в себе:
- Текстовый файл в формате PDF с указанием ФИО, содержащий описание всех проведенных исследований. Данный файл должен, в частности, содержать необходимые графики зависимости битовой и блоковой ошибки кода в зависимости от различных значений параметров.
- Все исходные коды с необходимыми комментариями.
| Построение порождающей матрицы для систематического кодирования | ||
|---|---|---|
| [G, ind] = ldpc_gen_matrix(H) | ||
| ВХОД | ||
| ||
| ВЫХОД | ||
|
| Алгоритм декодирования LDPC-кода в синдромном представлении | ||||||||
|---|---|---|---|---|---|---|---|---|
| [n, status] = ldpc_decoding(z, H, q, param_name1, param_value1, ...) | ||||||||
| ВХОД | ||||||||
| ||||||||
| ВЫХОД | ||||||||
|
| Оценка характеристик LDPC-кода с помощью метода Монте Карло | ||||
|---|---|---|---|---|
| [err_bit, err_block, diver] = ldpc_mc(H, G, g, num_points) | ||||
| ВХОД | ||||
| ||||
| ВЫХОД | ||||
|
