Практикум на ЭВМ (317)/2013/Коды БЧХ

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

(Различия между версиями)

Версия 12:32, 8 мая 2013

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

Основная статья: Практикум на ЭВМ (317)

Начало выполнения задания: 8 мая 2013 г.
Срок сдачи: 20 мая 2013 г. (понедельник), 23:59.

Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.

Необходимая теория

Кодирование с помощью (n,k,d)-блоковых линейных циклических кодов

Коды БЧХ: кодирование и декодирование

Укороченные коды

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

В задании выдается список всех примитивных многочленов степени $l$ для поля $GF(2^l)$ для всех $l=1,2,\dots,16$ .

Реализовать основные операции в поле $GF(2^l)$ : сложение, умножение, деление, решение СЛАУ, поиск примитивных элементов, вычисление значения многочлена из $GF(2^l)[x]$ для заданного элемента поля. Реализовать поиск минимального многочлена из $GF(2)[x]$ для заданного набора корней из поля $GF(2^l)$ двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных $n$ и $d$ с одновременным выбором нулей кода таким образом, чтобы значение $k$ было максимальным. С помощью экспериментов определить, как сильно может меняться $k$ в зависимости от выбора примитивного элемента - первого нуля кода для различных значений $l,n,d$ ;
Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ;
[Бонус] Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
Провести экспериментальное исследование БЧХ-кода на модельных данных;
Составить отчет в формате PDF обо всех проведенных исследованиях.

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

Выполненное задание с отчетом и всеми исходными кодами необходимо прислать преподавателю. Большая просьба строго следовать указанным ниже прототипам реализуемых функций.

Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля $GF(2^l)$
pm = gf_gen_pow_matrix(pp)
ВХОД
pp — примитивный многочлен в поле $GF(2^l)$ степени $l$ , десятичное число;
ВЫХОД
pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу $x$ , матрица размера $2^l-1{\times}2$ , в которой в первой колонке в позиции $i$ стоит степень $j:\alpha^j=i$ , а во второй колонке в позиции $i$ стоит значение $\alpha^i$ .

Суммирование в $GF(2^l)$
res = gf_sum(X, Y) — поэлементное суммирование двух матриц
res = gf_sum(X, [], dim) — суммирование по заданной размерности
ВХОД
X, Y — матрица из элементов поля $GF(2^l)$ , каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем $GF(2)$ , первый разряд соответствует старшей степени полинома;
dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1;
ВЫХОД
res — результат суммирования.

Умножение/деление в поле $GF(2^l)$
res = gf_prod(X, Y, pm) — поэлементное умножение двух матриц
res = gf_divide(X, Y, pm) — поэлементное деление двух матриц
ВХОД
X, Y — матрица из элементов поля $GF(2^l)$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ ;
ВЫХОД
res — результат операции, при делении на ноль соответствующий элемент равен NaN.

Решение СЛАУ $A\vec{x}=\vec{b}$ в поле $GF(2^l)$ методом Гаусса
x = gf_linsolve(A, b, pm)
ВХОД
A — квадратная матрица из элементов поля $GF(2^l)$ ;
b — вектор-столбец из элементов поля $GF(2^l)$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ ;
ВЫХОД
x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности $A$ равен NaN.

Поиск всех примитивных элементов поля $GF(2^l)$
alpha = gf_primel(pm)
ВХОД
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ ;
ВЫХОД
alpha — найденные примитивные элементы, вектор-столбец десятичных чисел.

Поиск минимального полинома в $GF(2)[x]$ с заданным набором корней из $GF(2^l)$
p = gf_minpoly(x, pm, method)
ВХОД
x — вектор-столбец из элементов поля $GF(2^l)$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ ;
method — (необязательный параметр) метод поиска, строка, возможные значения 'ls' (с помощью решения СЛАУ) и 'cosets' (с помощью построения циклотомических классов смежности), по умолчанию = 'cosets';
ВЫХОД
p — найденный полином, десятичное число.

Значение полинома из $GF(2^l)[x]$ на элементе из $GF(2^l)$
res = gf_polyval(p, X, pm)
ВХОД
p — полином из $GF(2^l)[x]$ , вектор-столбец коэффициентов, начиная со старшей степени;
X — матрица из элементов поля $GF(2^l)$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ ;
ВЫХОД
res — значение полинома для всех элементов X.

Систематическое кодирование циклическим кодом с заданным порождающим многочленом
V = cyclic_coding(U, g, n)
ВХОД
U — исходные сообщения для кодирования, вектор-столбец десятичных чисел;
g — порождающий полином кода, десятичное число;
n — длина кода, десятичное число;
ВЫХОД
V — закодированные сообщения, вектор-столбец десятичных чисел.

Поиск порождающего многочлена для БЧХ-кода с максимизацией $k$
[g, R, pm] = bch_genpoly(n, d)
ВХОД
n — длина кода, число вида $2^l-1$ ;
d — минимальное расстояние кода, число;
ВЫХОД
g — порождающий полином кода, число;
R — нули кода, вектор-столбец чисел;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ .

Декодирование БЧХ-кода
V = bch_decoding(W, R, pm, method)
ВХОД
W — набор принятых сообщений, вектор-столбец элементов из $GF(2^l)$ ;
R — нули кода, вектор-столбец элементов из $GF(2^l)$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ ;
method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'pgz';
ВЫХОД
V — декодированные сообщения, вектор-столбец чисел, в случае отказа от декодирования соответствующий элемент равен NaN.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%BA%D1%82%D0%B8%D0%BA%D1%83%D0%BC_%D0%BD%D0%B0_%D0%AD%D0%92%D0%9C_%28317%29/2013/%D0%9A%D0%BE%D0%B4%D1%8B_%D0%91%D0%A7%D0%A5»

@@ Строка 5: / Строка 5: @@
 '''Начало выполнения задания''': 8 мая 2013 г.<br>
-'''Срок сдачи''': {{важно|19 мая 2013 г. (воскресенье), 23:59.}}
+'''Срок сдачи''': {{важно|20 мая 2013 г. (понедельник), 23:59.}}
 Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
@@ Строка 19: / Строка 19: @@
 == Формулировка задания ==
-В задании выдается список всех примитивных многочленов степени <tex>l</tex> для поля <tex>GF(2^l)</tex> для всех <tex>l=1,2,\dots,16</tex>.
+В задании выдается [[Media:Gf_primpoly.zip|список]] всех примитивных многочленов степени <tex>l</tex> для поля <tex>GF(2^l)</tex> для всех <tex>l=1,2,\dots,16</tex>.
 # Реализовать основные операции в поле <tex>GF(2^l)</tex>: сложение, умножение, деление, решение СЛАУ, поиск примитивных элементов, вычисление значения многочлена из <tex>GF(2^l)[x]</tex> для заданного элемента поля. Реализовать поиск минимального многочлена из <tex>GF(2)[x]</tex> для заданного набора корней из поля <tex>GF(2^l)</tex> двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
@@ Строка 225: / Строка 225: @@
  |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
  |-
- |method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'bma';
+ |method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'pgz';
  |-
  |ВЫХОД

Практикум на ЭВМ (317)/2013/Коды БЧХ

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

Версия 12:32, 8 мая 2013

Необходимая теория

Кодирование с помощью (n,k,d)-блоковых линейных циклических кодов

Коды БЧХ: кодирование и декодирование

Укороченные коды

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

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

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

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты