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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Оформление задания)
Строка 4: Строка 4:
__NOTOC__
__NOTOC__
-
'''Начало выполнения задания''': 6 мая 2013 г.<br>
+
'''Начало выполнения задания''': 8 мая 2013 г.<br>
'''Срок сдачи''': {{важно|19 мая 2013 г. (воскресенье), 23:59.}}
'''Срок сдачи''': {{важно|19 мая 2013 г. (воскресенье), 23:59.}}
Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
-
== Коды БЧХ ==
+
== Необходимая теория ==
 +
=== Кодирование с помощью (n,k,d)-блоковых линейных циклических кодов ===
 +
 +
=== Коды БЧХ: кодирование и декодирование ===
 +
 +
=== Укороченные коды ===
== Формулировка задания ==
== Формулировка задания ==
-
# Реализовать основные операции в поле <tex>GF(2^l)</tex>: сложение, умножение, деление, решение СЛАУ, вычисление значения многочлена для заданного элемента поля, поиск примитивного элемента;
+
В задании выдается список всех примитивных многочленов степени <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> двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
# Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
# Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
-
# Реализовать процедуру построения порождающего многочлена для БЧХ-кода двумя способами: с помощью решения СЛАУ для коэффициентов многочлена и с помощью построения минимальных многочленов для каждого корня кода;
+
# Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных <tex>n</tex> и <tex>d</tex> с одновременным выбором нулей кода таким образом, чтобы значение <tex>k</tex> было максимальным. С помощью экспериментов определить, как сильно может меняться <tex>k</tex> в зависимости от выбора примитивного элемента - первого нуля кода для различных значений <tex>l,n,d</tex>;
-
# Реализовать процедуру декодирования БЧХ-кода двумя способами: с помощью алгоритма Берлекемпа-Мэсси и с помощью прямого решения СЛАУ (декодер PGZ);
+
# Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ;
 +
# '''[Бонус]''' Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
# Провести экспериментальное исследование БЧХ-кода на модельных данных;
# Провести экспериментальное исследование БЧХ-кода на модельных данных;
# Составить отчет в формате PDF обо всех проведенных исследованиях.
# Составить отчет в формате PDF обо всех проведенных исследованиях.
Строка 102: Строка 110:
|-
|-
|x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности <tex>A</tex> равен NaN.
|x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности <tex>A</tex> равен NaN.
 +
|}
 +
 +
&nbsp;
 +
 +
{|class="standard"
 +
!''Поиск всех примитивных элементов поля <tex>GF(2^l)</tex>''
 +
|-
 +
|alpha = '''gf_primel'''(pm)
 +
|-
 +
|ВХОД
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
 +
|-
 +
|ВЫХОД
 +
|-
 +
|alpha — найденные примитивные элементы, вектор-столбец десятичных чисел.
|}
|}
Строка 167: Строка 191:
{|class="standard"
{|class="standard"
-
!''Поиск порождающего многочлена для БЧХ-кода''
+
!''Поиск порождающего многочлена для БЧХ-кода с максимизацией <tex>k</tex>''
|-
|-
-
|g = '''bch_genpoly'''(n, d)
+
|[g, R, pm] = '''bch_genpoly'''(n, d)
|-
|-
|ВХОД
|ВХОД
Строка 179: Строка 203:
|ВЫХОД
|ВЫХОД
|-
|-
-
|g — порождающий полином кода, число.
+
|g — порождающий полином кода, число;
 +
|-
 +
|R — нули кода, вектор-столбец чисел;
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>.
 +
|}
 +
 
 +
&nbsp;
 +
 
 +
{|class="standard"
 +
!''Декодирование БЧХ-кода''
 +
|-
 +
|V = '''bch_decoding'''(W, R, pm, method)
 +
|-
 +
|ВХОД
 +
|-
 +
|W — набор принятых сообщений, вектор-столбец элементов из <tex>GF(2^l)</tex>;
 +
|-
 +
|R — нули кода, вектор-столбец элементов из <tex>GF(2^l)</tex>;
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
 +
|-
 +
|method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'bma';
 +
|-
 +
|ВЫХОД
 +
|-
 +
|V — декодированные сообщения, вектор-столбец чисел, в случае отказа от декодирования соответствующий элемент равен NaN.
|}
|}

Версия 23:25, 7 мая 2013

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


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


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

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

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

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

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

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

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

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

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