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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Формулировка задания)
(→Оформление задания)
Строка 26: Строка 26:
== Оформление задания ==
== Оформление задания ==
-
Выполненное задание следует отправить письмом по адресу ''bayesml@gmail.com'' с заголовком письма «[ПРАК13] Задание 6, Фамилия». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также большая просьба строго следовать указанным ниже прототипам реализуемых функций.
+
Выполненное задание с отчетом и всеми исходными кодами необходимо прислать преподавателю. Большая просьба строго следовать указанным ниже прототипам реализуемых функций.
-
Присланный вариант задания должен содержать в себе:
+
 
-
* Текстовый файл в формате PDF, содержащий описание проведенных исследований;
+
 
-
* Все исходные коды с необходимыми комментариями.
+
{|class="standard"
 +
!''Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля <tex>GF(2^l)</tex>''
 +
|-
 +
|pm = '''gf_gen_pow_matrix'''(pp)
 +
|-
 +
|ВХОД
 +
|-
 +
|pp — примитивный многочлен в поле <tex>GF(2^l)</tex> степени <tex>l</tex>, десятичное число;
 +
|-
 +
|ВЫХОД
 +
|-
 +
|pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу <tex>x</tex>, матрица размера <tex>2^l-1{\times}2</tex>, в которой в первой колонке в позиции <tex>i</tex> стоит степень <tex>j:\alpha^j=i</tex>, а во второй колонке в позиции <tex>i</tex> стоит значение <tex>\alpha^i</tex>.
 +
|}
&nbsp;
&nbsp;
{|class="standard"
{|class="standard"
-
!''Основные операции в <tex>GF(2^l)</tex>''
+
!''Суммирование в <tex>GF(2^l)</tex>''
|-
|-
-
|res = '''gf_sum'''(X, Y, pp) — поэлементное суммирование двух матриц
+
|res = '''gf_sum'''(X, Y) — поэлементное суммирование двух матриц
|-
|-
-
|res = '''gf_prod'''(X, Y, pp) — поэлементное умножение двух матриц
+
|res = '''gf_sum'''(X, [], dim) — суммирование по заданной размерности
|-
|-
-
|res = '''gf_times'''(X, Y, pp) — умножение двух матриц
+
|ВХОД
|-
|-
-
|res = '''gf_rdivide'''(A, b, pp) — решение СЛАУ <tex>Ax=b</tex>
+
|X, Y — матрица из элементов поля <tex>GF(2^l)</tex>, каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома;
 +
|-
 +
|dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1;
 +
|-
 +
|ВЫХОД
 +
|-
 +
|res — результат суммирования.
 +
|}
 +
 
 +
&nbsp;
 +
 
 +
{|class="standard"
 +
!''Умножение/деление в поле <tex>GF(2^l)</tex>''
 +
|-
 +
|res = '''gf_prod'''(X, Y, pm) — поэлементное умножение двух матриц
 +
|-
 +
|res = '''gf_divide'''(X, Y, pm) — поэлементное деление двух матриц
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|
+
|X, Y — матрица из элементов поля <tex>GF(2^l)</tex>;
-
{|border="0"
+
|-
-
|-
+
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
-
|X, Y — матрица из элементов поля <tex>GF(2^l)</tex>, каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома;
+
|-
-
|-
+
|ВЫХОД
-
|pp — неприводимый многочлен степени <tex>l</tex> над <tex>GF(2)[x]</tex>, десятичное число;
+
|-
-
|-
+
|res — результат операции, при делении на ноль соответствующий элемент равен NaN.
-
|}
+
|}
 +
 
 +
&nbsp;
 +
 
 +
{|class="standard"
 +
!''Решение СЛАУ <tex>A\vec{x}=\vec{b}</tex> в поле <tex>GF(2^l)</tex> методом Гаусса''
 +
|-
 +
|x = '''gf_linsolve'''(A, b, pm)
 +
|-
 +
|ВХОД
 +
|-
 +
|A — квадратная матрица из элементов поля <tex>GF(2^l)</tex>;
 +
|-
 +
|b — вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
 +
|-
 +
|p — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
 +
|-
 +
|ВЫХОД
 +
|-
 +
|x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности <tex>A</tex> равен NaN.
 +
|}
 +
 
 +
&nbsp;
 +
 
 +
{|class="standard"
 +
!''Значение полинома из <tex>GF(2^l)[x]</tex> на элементе из <tex>GF(2^l)</tex>''
 +
|-
 +
|res = '''gf_polyval'''(p, X, pm)
 +
|-
 +
|ВХОД
 +
|-
 +
|p — полином из <tex>GF(2^l)[x]</tex>, вектор-столбец коэффициентов, начиная со старшей степени;
 +
|-
 +
|X — матрица из элементов поля <tex>GF(2^l)</tex>;
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|res — результат операции, набор элементов из поля <tex>GF(2^l)</tex>, каждый из которых представляется десятичным числом.
+
|res — значение полинома для всех элементов X.
|}
|}

Версия 16:08, 7 мая 2013

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


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


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

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

Коды БЧХ

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

  1. Реализовать основные операции в поле GF(2^l): сложение, умножение, деление, решение СЛАУ, вычисление значения многочлена для заданного элемента поля, поиск примитивного элемента;
  2. Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
  3. Реализовать процедуру построения порождающего многочлена для БЧХ-кода двумя способами: с помощью решения СЛАУ для коэффициентов многочлена и с помощью построения минимальных многочленов для каждого корня кода;
  4. Реализовать процедуру декодирования БЧХ-кода двумя способами: с помощью алгоритма Берлекемпа-Мэсси и с помощью прямого решения СЛАУ (декодер PGZ);
  5. Провести экспериментальное исследование БЧХ-кода на модельных данных;
  6. Составить отчет в формате 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);
p — матрица соответствия между десятичным и степенным представлением в поле GF(2^l);
ВЫХОД
x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности A равен NaN.

 

Значение полинома из 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.
Источник — «http://poligon.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»
Личные инструменты