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

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

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

Перейти к: навигация, поиск

Текущая версия

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

Содержание

1 Необходимая теория
2 Формулировка задания
3 Рекомендации по выполнению задания
4 Оформление задания

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

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

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

Задача помехоустойчивого кодирования

Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При блоковом кодировании входящий поток информации разбивается на блоки фиксированной длины $k$ . Обозначим один такой блок через $u\in\{0,1\}^k$ . Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок $u$ в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через $v\in\{0,1\}^n$ , $n>k$ . Для кодирования всевозможных блоков $u$ необходимо использовать $2^k$ кодовых слов длины $n$ . Определим минимальное расстояние кода $d$ как минимальное хэммингово расстояние для всех различных пар кодовых слов. Назовём множество $2^k$ кодовых слов длины $n$ с минимальным расстоянием $d$ (n,k,d)-блоковым кодом, а величину $r=k/n$ — скоростью кода. При передаче по каналу с шумом кодовое слово $v$ превращается в принятое слово $w\in\{0,1\}^n$ , которое, вообще говоря, отличается от $v$ . Далее алгоритм декодирования пытается восстановить переданное слово $v$ путем поиска среди всевозможных кодовых слов ближайшего к $w$ . Обозначим результат работы алгоритма декодирования через $\hat{v}$ . На последнем этапе декодированное слово $\hat{v}$ переводится в декодированное слово исходного сообщения $\hat{u}$ . Очевидно, что (n,k,d)-блоковый код способен обнаруживать до $d-1$ ошибки и исправлять до $[(d-1)/2]$ ошибок.

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

Множество $\{0,1\}^n$ с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем $\mathbb{F}_2$ . (n,k,d)-блоковый код называется линейным, если множество его кодовых слов образует линейное подпространство размерности $k$ общего линейного пространства $\{0,1\}^n$ . Таким образом, для линейного кода произвольная линейная комбинация кодовых слов является кодовым словом. Минимальное кодовое расстояние $d$ для линейного кода определяется как минимальный хэммингов вес (количество ненулевых бит) среди ненулевых кодовых слов. (n,k,d)-линейный блоковый код называется циклическим, если любой циклический сдвиг кодового слова является кодовым словом. Поставим в соответствие произвольному вектору $v=[v_{n-1},v_{n-2},\dots,v_1,v_0]\in\{0,1\}^n$ полином вида $v(x)=v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+\dots+v_1x+v_0$ . Тогда можно показать, что для (n,k,d)-линейного циклического блокового кода найдется полином $g(x)$ степени $m=n-k$ такой, что

Все кодовые слова $v(x)$ могут быть представлены как $g(x)q(x)$ , где $q(x)$ — некоторый полином степени, не превышающей $k-1$ ;
Полином $g(x)$ является делителем полинома $x^n-1$ .

Такой полином $g(x)$ называется порождающим полиномом циклического кода. Любой полином, являющийся делителем $x^n-1$ , является порождающим для некоторого циклического кода.

Кодирование называется систематическим, если все биты исходного сообщения $u$ копируются в некоторые биты кодового слова $v$ . При систематическом кодировании обратный процесс преобразования из декодированного кодового слова $\hat{v}$ в декодированное слово сообщения $\hat{u}$ становится тривиальным. Для циклического кода, задаваемого порождающим полиномом $g(x)$ , процесс систематического кодирования может быть реализован как

$v(x) = x^mu(x) + \mathrm{mod}(x^mu(x), g(x))$ .

Здесь через $\mathrm{mod}(f(x), g(x))$ обозначена операция взятия остатка от деления многочлена $f(x)$ на многочлен $g(x)$ .

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

Полином $m_{\alpha}(x)\in \mathbb{F}_2[x]$ называется минимальным полиномом для элемента $\alpha\in \mathbb{F}_2^l$ , если он является неприводимым полиномом минимальной степени, для которого $\alpha$ является корнем. В частности, минимальный полином для примитивного элемента $\alpha$ называется примитивным полиномом. Можно показать, что корнями минимального полинома $m_{\alpha}(x)$ являются

$\{\alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}\}$ .

Данный набор элементов из поля $\mathbb{F}_2^l$ называется циклотомическим классом смежности для элемента $\alpha$ . Количество элементов в смежном классе либо равно $l$ , либо является делителем $l$ . Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином

$\prod_{i=0}^q(x+\alpha^{2^i}) = x^{q+1}+\lambda_qx^q+\dots+\lambda_1x + \lambda_0$

имеет коэффициенты из $\mathbb{F}_2$ и является минимальным полиномом для $\alpha$ , а также для всех элементов поля, входящих вместе с $\alpha$ в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля $\alpha$ :

Построить циклотомический класс, порожденный элементом $\alpha$ ;
Найти коэффициенты полинома $m_{\alpha}(x)$ путем перемножения многочленов $x+\alpha^{2^i}$ для всех $i=0,\dots,q$ .

Пусть $n=2^l-1$ , $t\le [(n-1)/2]$ . Тогда кодом БЧХ называется (n,k)-линейный циклический код, в котором порождающий многочлен $g(x)$ определяется как минимальный многочлен для элементов $\alpha,\alpha^2,\dots,\alpha^{2t}$ из поля $\mathbb{F}_2^l$ , где $\alpha$ — произвольный примитивный элемент поля $\mathbb{F}_2^l$ . Набор элементов $\alpha,\alpha^2,\dots,\alpha^{2t}$ называется нулями БЧХ-кода. Можно показать, что минимальное кодовое расстояние кода БЧХ $d$ не меньше, чем величина $2t+1$ . В результате БЧХ-коды по построению способны исправлять не менее $t$ ошибок.

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

Поставим в соответствие позициям принятого слова $w = [w_{n-1},\dots,w_0]$ элементы $\alpha^{n-1},\dots,\alpha^0$ . При передаче по шумовому каналу кодовое слово $v(x)$ переходит в слово $w(x)=v(x)+e(x)$ , где $e(x)=x^{j_1}+\dots+x^{j_{\nu}}$ — полином ошибок, а $j_1,\dots,j_{\nu}$ — позиции, в которых произошли ошибки. Назовем синдромами принятого сообщения $w(x)$ значения полинома $w(x)$ в нулях БЧХ-кода, т.е. $s_i=w(\alpha^i),\ i=1,\dots,2t$ . Если $w(x)$ является кодовым словом, то все синдромы $s_i=0$ . Рассмотрим полином локаторов ошибок

$\Lambda(z) = \prod_{i=1}^{\nu}(1+\alpha^{j_i}x) = \Lambda_{\nu}x^{\nu}+\dots+\Lambda_1x+1$ .

Данный полином имеет корни $\alpha^{-j_i}$ . Можно показать, что коэффициенты полинома $\Lambda(z)$ удовлетворяют следующей СЛАУ:

$\begin{bmatrix}s_1 & s_2 & \dots & s_{\nu}\\ s_2 & s_3 & \dots & s_{\nu+1}\\ \rule{0pt}{15pt}\dots & \dots & \dots & \dots \\ \rule{0pt}{15pt}s_{\nu} & s_{\nu+1} & \dots & s_{2\nu-1}\end{bmatrix}\begin{bmatrix}\Lambda_{\nu}\\ \Lambda_{\nu-1}\\ \rule{0pt}{15pt}\dots\\ \Lambda_1\end{bmatrix} = \begin{bmatrix}s_{\nu+1}\\ s_{\nu+2}\\ \rule{0pt}{15pt}\dots \\ s_{2\nu}\end{bmatrix}$ . (*)

Отсюда получаем следующую общую схему декодирования БЧХ-кода:

Для принятого слова $w(x)$ вычислить синдромы $s_i=w(\alpha^i),\ i=1,\dots,2t$ . Если все $s_i=0$ , то вернуть $w(x)$ в качестве ответа;
Найти количество допущенных ошибок $\nu$ и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
Найти все корни полинома $\Lambda(z)$ путем полного перебора, по найденным корням вычислить номера позиций $j_1,\dots,j_{\nu}$ , в которых произошли ошибки;
Исправить ошибки в позициях $j_1,\dots,j_{\nu}$ путем инвертирования соответствующих битов в $w(x)$ .

Различные алгоритмы декодирования БЧХ-кодов по-разному решают задачу на шаге 2 общего алгоритма декодирования. Рассмотрим две схемы декодирования.

Декодер PGZ (Peterson–Gorenstein–Zierler)

Данный декодер предполагает непосредственное решение СЛАУ (*). Основная трудность здесь — это определить количество фактически допущенных при передаче ошибок $\nu$ . В декодере PGZ происходит перебор по всем значениям $\nu$ , начиная с $t$ . При текущем $\nu$ делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее $\nu$ признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то $\Lambda_{\nu}=0$ , величина $\nu$ уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования. Также отказ от декодирования выдаётся в случае, если после исправления синдромы $\hat{v}(x)$ не равны нулю (кодовое слово не найдено).

Декодер Euclid

Рассмотрим синдромный полином вида $S(z) = s_{2t}z^{2t}+s_{2t-1}z^{2t-1}+\dots+s_1z+1$ , где $s_i$ — вычисленные ранее синдромы. Тогда можно показать, что $S(z)$ и $\Lambda(z)$ удовлетворяют следующему уравнению:

$z^{2t+1}A(z) + S(z)\Lambda(z) = r(z)$ .

Здесь $r(z)$ — некоторый многочлен из $\mathbb{F}_2^l[x]$ , степень которого не превышает $t$ . Решение данного уравнения $A(z), \Lambda(z), r(z)$ для заданных многочленов $z^{2t+1}$ и $S(z)$ может быть найдено с помощью расширенного алгоритма Евклида. Здесь итерации алгоритма Евклида проводятся до тех пор, пока степень текущего остатка $r(z)$ не станет меньше или равна $t$ . Степень найденного $\Lambda(z)$ равна количеству фактически допущенных при передаче ошибок $\nu$ . Если количество корней у $\Lambda(z)$ не совпадает с $\nu$ , то выдаётся отказ от декодирования.

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

В задании выдается список всех примитивных многочленов степени $l$ над полем $\mathbb{F}_2$ для всех $l=1,2,\dots,16$ .

Реализовать основные операции в поле $\mathbb{F}_2^l$ : сложение, умножение, деление, решение СЛАУ, поиск минимального многочлена из $\mathbb{F}_2[x]$ для заданного набора корней из поля $\mathbb{F}_2^l$ ;
Реализовать основные операции для работы с многочленами из $\mathbb{F}_2^l[x]$ : произведение многочленов, деление многочленов с остатком, расширенный алгоритм Евклида для пары многочленов, вычисление значения многочлена для набора элементов из $\mathbb{F}_2^l$ ;
Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных $n$ и $t$ ;
Построить графики зависимости скорости БЧХ-кода $r=k/n$ от количества исправляемых кодом ошибок $t$ для различных значений $n$ . Какие значения $t$ следует выбирать на практике для заданного $n$ ?
Реализовать процедуру вычисления истинного минимального расстояния циклического кода $d$ , заданного своим порождающим многочленом, путем полного перебора по всем $2^k-1$ кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина $2t+1$ ;
Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ и на основе расширенного алгоритма Евклида. Провести сравнение двух методов декодирования по времени работы;
С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до $t$ ошибок. Может ли БЧХ-код исправить больше, чем $t$ ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем $t$ ?
Составить отчет в формате PDF обо всех проведенных исследованиях.

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

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

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

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

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

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

Поиск минимального полинома в $\mathbb{F}_2[x]$ с заданным набором корней из $\mathbb{F}_2^l$
[p, x_coset] = gf_minpoly(x, pm)
ВХОД
x — вектор-столбец из элементов поля $\mathbb{F}_2^l$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $\mathbb{F}_2^l$ ;
ВЫХОД
p — найденный полином, бинарный вектор-строка;
x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля $\mathbb{F}_2^l$ .

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

Умножение двух полиномов из $\mathbb{F}_2^l[x]$
res = gf_polyprod(p1, p2, pm)
ВХОД
p1 — полином из $\mathbb{F}_2^l[x]$ , вектор-строка коэффициентов, начиная со старшей степени;
p2 — полином из $\mathbb{F}_2^l[x]$ , вектор-строка коэффициентов, начиная со старшей степени;
pm — матрица соответствия между десятичным и степенным представлением в поле $\mathbb{F}_2^l$ ;
ВЫХОД
res — значение полинома p1(x)*p2(x), вектор-строка коэффициентов, начиная со старшей степени.

Деление двух полиномов из $\mathbb{F}_2^l[x]$ с остатком
[q, r] = gf_polydiv(p1, p2, pm)
ВХОД
p1 — полином из $\mathbb{F}_2^l[x]$ , вектор-строка коэффициентов, начиная со старшей степени;
p2 — полином из $\mathbb{F}_2^l[x]$ , вектор-строка коэффициентов, начиная со старшей степени;
pm — матрица соответствия между десятичным и степенным представлением в поле $\mathbb{F}_2^l$ ;
ВЫХОД
q — результат деления, вектор-строка коэффициентов, начиная со старшей степени;
r — остаток от деления, вектор-строка коэффициентов, начиная со старшей степени.

Расширенный алгоритм Евклида для решения уравнения a(x)p1(x)+b(x)p2(x)= r(x) для двух полиномов p1, p2 из $\mathbb{F}_2^l[x]$
[r, a, b] = gf_euclid(p1, p2, max_deg, pm)
ВХОД
p1 — полином из $\mathbb{F}_2^l[x]$ , вектор-строка коэффициентов, начиная со старшей степени;
p2 — полином из $\mathbb{F}_2^l[x]$ , вектор-строка коэффициентов, начиная со старшей степени;
max_deg — максимально допустимая степень остатка r(x), число;
pm — матрица соответствия между десятичным и степенным представлением в поле $\mathbb{F}_2^l$ ;
ВЫХОД
r — остаток, вектор-строка коэффициентов, начиная со старшей степени;
a — коэффициент при p1(x), вектор-строка коэффициентов, начиная со старшей степени;
b — коэффициент при p2(x), вектор-строка коэффициентов, начиная со старшей степени.

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

Вычисление минимального расстояния циклического кода путем полного перебора
d = cyclic_dist(g, n)
ВХОД
g — порождающий многочлен кода, бинарный вектор-строка;
n — длина кода;
ВЫХОД
d — минимальное расстояние кода, число.

Поиск порождающего многочлена для БЧХ-кода
[g, R, pm] = bch_genpoly(n, t)
ВХОД
n — длина кода, число вида $2^l-1$ ;
t — исправляемое число ошибок, число;
ВЫХОД
g — порождающий полином кода, бинарный вектор-строка;
R — нули кода, вектор-столбец десятичных чисел;
pm — матрица соответствия между десятичным и степенным представлением в поле $\mathbb{F}_2^l$ .

Декодирование БЧХ-кода
V = bch_decoding(W, R, pm, method)
ВХОД
W — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
R — нули кода, вектор-столбец элементов из $\mathbb{F}_2^l$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $\mathbb{F}_2^l$ ;
method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'euclid', по умолчанию = 'euclid';
ВЫХОД
V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов 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/2014/%D0%9A%D0%BE%D0%B4%D1%8B_%D0%91%D0%A7%D0%A5»

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

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

Текущая версия

Содержание

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

Задача помехоустойчивого кодирования

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

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

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

Декодер PGZ (Peterson–Gorenstein–Zierler)

Декодер Euclid

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
 {{Main|Практикум на ЭВМ (317)}}
-{{stop|Внимание! Задание находится в стадии разработки. Просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.}}
 __TOC__
 '''Начало выполнения задания''': 26 апреля 2014 г.<br>
-'''Срок сдачи''': {{важно|11 мая 2013 г. (воскресенье), 23:59.}}
+'''Срок сдачи''': {{важно|11 мая 2014 г. (воскресенье), 23:59.}}
 Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
@@ Строка 13: / Строка 11: @@
 === Задача помехоустойчивого кодирования ===
-Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины <tex>k</tex>. Обозначим один такой блок через <tex>u\in\{0,1\}^k</tex>. Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок <tex>u</tex> в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через <tex>v\in\{0,1\}^n</tex>, <tex>n>k</tex>. Для кодирования всевозможных блоков <tex>u</tex> необходимо использовать <tex>2^k</tex> кодовых слов длины <tex>n</tex>. Определим минимальное расстояние кода <tex>d</tex> как минимальное хэммингово расстояние для всех различных пар кодовых слов. Назовём множество <tex>2^k</tex> кодовых слов длины <tex>n</tex> с минимальным расстоянием <tex>d</tex> ''(n,k,d)-блоковым кодом'', а величину <tex>r=k/n</tex> — ''скоростью кода''. При передаче по каналу с шумом кодовое слово <tex>v</tex> превращается в принятое слово <tex>w</tex>, которое, вообще говоря, отличается от <tex>v</tex>. Далее алгоритм декодирования пытается восстановить переданное слово <tex>v</tex> путем поиска среди всевозможных кодовых слов ближайшего к <tex>w</tex>. Обозначим результат работы алгоритма декодирования через <tex>\hat{v}</tex>. На последнем этапе декодированное слово <tex>\hat{v}</tex> переводится в декодированное слово исходного сообщения <tex>\hat{u}</tex>. Очевидно, что (n,k,d)-блоковый код способен обнаруживать до <tex>d-1</tex> ошибки и исправлять до <tex>[(d-1)/2]</tex> ошибок.
+Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины <tex>k</tex>. Обозначим один такой блок через <tex>u\in\{0,1\}^k</tex>. Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок <tex>u</tex> в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через <tex>v\in\{0,1\}^n</tex>, <tex>n>k</tex>. Для кодирования всевозможных блоков <tex>u</tex> необходимо использовать <tex>2^k</tex> кодовых слов длины <tex>n</tex>. Определим минимальное расстояние кода <tex>d</tex> как минимальное хэммингово расстояние для всех различных пар кодовых слов. Назовём множество <tex>2^k</tex> кодовых слов длины <tex>n</tex> с минимальным расстоянием <tex>d</tex> ''(n,k,d)-блоковым кодом'', а величину <tex>r=k/n</tex> — ''скоростью кода''. При передаче по каналу с шумом кодовое слово <tex>v</tex> превращается в принятое слово <tex>w\in\{0,1\}^n</tex>, которое, вообще говоря, отличается от <tex>v</tex>. Далее алгоритм декодирования пытается восстановить переданное слово <tex>v</tex> путем поиска среди всевозможных кодовых слов ближайшего к <tex>w</tex>. Обозначим результат работы алгоритма декодирования через <tex>\hat{v}</tex>. На последнем этапе декодированное слово <tex>\hat{v}</tex> переводится в декодированное слово исходного сообщения <tex>\hat{u}</tex>. Очевидно, что (n,k,d)-блоковый код способен обнаруживать до <tex>d-1</tex> ошибки и исправлять до <tex>[(d-1)/2]</tex> ошибок.
 === Кодирование с помощью (n,k,d)-линейного циклического блокового кода ===
-Множество <tex>\{0,1\}^n</tex> с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов <tex>\{0,1\}</tex>. (n,k,d)-блоковый код называется ''линейным'', если множество его кодовых слов образует линейное подпространство размерности <tex>k</tex> общего линейного пространства <tex>\{0,1\}^n</tex>. Таким образом, для линейного кода произвольная линейная комбинация кодовых слов является кодовым словом. Минимальное кодовое расстояние <tex>d</tex> для линейного кода определяется как минимальный хэммингов вес (количество ненулевых бит) среди ненулевых кодовых слов. (n,k,d)-линейный блоковый код называется ''циклическим'', если любой циклический сдвиг кодового слова является кодовым словом. Поставим в соответствие произвольному вектору <tex>v=\{v_{n-1},v_{n-2},\dots,v_1,v_0\}\in\{0,1\}^n</tex> полином вида <tex>v(x)=v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+\dots+v_1x+v_0</tex>. Тогда можно показать, что для (n,k,d)-линейного циклического блокового кода найдется полином <tex>g(x)</tex> степени <tex>m=n-k</tex> такой, что
+Множество <tex>\{0,1\}^n</tex> с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем <tex>\mathbb{F}_2</tex>. (n,k,d)-блоковый код называется ''линейным'', если множество его кодовых слов образует линейное подпространство размерности <tex>k</tex> общего линейного пространства <tex>\{0,1\}^n</tex>. Таким образом, для линейного кода произвольная линейная комбинация кодовых слов является кодовым словом. Минимальное кодовое расстояние <tex>d</tex> для линейного кода определяется как минимальный хэммингов вес (количество ненулевых бит) среди ненулевых кодовых слов. (n,k,d)-линейный блоковый код называется ''циклическим'', если любой циклический сдвиг кодового слова является кодовым словом. Поставим в соответствие произвольному вектору <tex>v=[v_{n-1},v_{n-2},\dots,v_1,v_0]\in\{0,1\}^n</tex> полином вида <tex>v(x)=v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+\dots+v_1x+v_0</tex>. Тогда можно показать, что для (n,k,d)-линейного циклического блокового кода найдется полином <tex>g(x)</tex> степени <tex>m=n-k</tex> такой, что
-# Все кодовые слова <tex>v(x)</tex> могут быть представлены как <tex>g(x)q(x)</tex>, где <tex>q(x)</tex> — некоторый полином степени <tex>k</tex>;
+# Все кодовые слова <tex>v(x)</tex> могут быть представлены как <tex>g(x)q(x)</tex>, где <tex>q(x)</tex> — некоторый полином степени, не превышающей <tex>k-1</tex>;
 # Полином <tex>g(x)</tex> является делителем полинома <tex>x^n-1</tex>.
 Такой полином <tex>g(x)</tex> называется ''порождающим полиномом циклического кода''. Любой полином, являющийся делителем <tex>x^n-1</tex>, является порождающим для некоторого циклического кода.
@@ Строка 28: / Строка 26: @@
 === Коды БЧХ: кодирование ===
-Полином <tex>m_{\alpha}(x)\in GF(2)[x]</tex> называется ''минимальным полиномом'' для элемента <tex>\alpha\in GF(2^l)</tex>, если он является неприводимым полиномом минимальной степени, для которого <tex>\alpha</tex> является корнем. В частности, минимальный полином для примитивного элемента <tex>\alpha</tex> называется ''примитивным полиномом''. Можно показать, что корнями минимального полинома <tex>m_{\alpha}(x)</tex> являются
+Полином <tex>m_{\alpha}(x)\in \mathbb{F}_2[x]</tex> называется ''минимальным полиномом'' для элемента <tex>\alpha\in \mathbb{F}_2^l</tex>, если он является неприводимым полиномом минимальной степени, для которого <tex>\alpha</tex> является корнем. В частности, минимальный полином для примитивного элемента <tex>\alpha</tex> называется ''примитивным полиномом''. Можно показать, что корнями минимального полинома <tex>m_{\alpha}(x)</tex> являются
 :<tex>\{\alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}\}</tex>.
-Данный набор элементов из поля <tex>GF(2^l)</tex> называется ''циклотомическим классом'' смежности для элемента <tex>\alpha</tex>. Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином
+Данный набор элементов из поля <tex>\mathbb{F}_2^l</tex> называется ''циклотомическим классом'' смежности для элемента <tex>\alpha</tex>. Количество элементов в смежном классе либо равно <tex>l</tex>, либо является делителем <tex>l</tex>. Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином
-:<tex>\prod_{i=1}^q(x+\alpha^{2^i}) = x^q+\lambda_{q-1}x^{q-1}+\dots+\lambda_1x + \lambda_0</tex>
+:<tex>\prod_{i=0}^q(x+\alpha^{2^i}) = x^{q+1}+\lambda_qx^q+\dots+\lambda_1x + \lambda_0</tex>
-имеет коэффициенты из <tex>GF(2)</tex> и является минимальным полиномом для <tex>\alpha</tex>, а также для всех элементов поля, входящих вместе с <tex>\alpha</tex> в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля <tex>\alpha</tex>:
+имеет коэффициенты из <tex>\mathbb{F}_2</tex> и является минимальным полиномом для <tex>\alpha</tex>, а также для всех элементов поля, входящих вместе с <tex>\alpha</tex> в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля <tex>\alpha</tex>:
 # Построить циклотомический класс, порожденный элементом <tex>\alpha</tex>;
-# Найти коэффициенты полинома <tex>m_{\alpha}(x)</tex> путем перемножения многочленов <tex>x+\alpha^{2^i}</tex> для всех <tex>i=1,\dots,q</tex>, либо решить СЛАУ
+# Найти коэффициенты полинома <tex>m_{\alpha}(x)</tex> путем перемножения многочленов <tex>x+\alpha^{2^i}</tex> для всех <tex>i=0,\dots,q</tex>.
-:<tex>\begin{bmatrix}\alpha^{q-1} & \alpha^{q-2} & \dots & \alpha & 1\\ \alpha^{2(q-1)} & \alpha^{2(q-2)} & \dots & \alpha^2 & 1\\ \rule{0pt}{15pt}\dots & \dots & \dots & \dots \\ \alpha^{2^q(q-1)} & \alpha^{2^q(q-2)} & \dots & \alpha^{2^q} & 1\end{bmatrix}\begin{bmatrix}\lambda_{q-1}\\ \lambda_{q-2}\\ \rule{0pt}{15pt}\dots \\ \lambda_0\end{bmatrix} = \begin{bmatrix}\alpha^q\\ \alpha^{2q}\\ \rule{0pt}{15pt}\dots \\ \alpha^{2^qq}\end{bmatrix}</tex>.
-&nbsp;
-Пусть <tex>n=2^l-1</tex>, <tex>d = 2t+1\le n</tex>. Тогда ''кодом БЧХ'' называется (n,k,d)-линейный циклический код, в котором порождающий многочлен <tex>g(x)</tex> определяется как минимальный многочлен для элементов <tex>\alpha,\alpha^2,\dots,\alpha^{d-1}</tex> из поля <tex>GF(2^l)</tex>, где <tex>\alpha</tex> — произвольный примитивный элемент поля <tex>GF(2^l)</tex>. Набор элементов <tex>\alpha,\alpha^2,\dots,\alpha^{d-1}</tex> называется ''нулями БЧХ-кода''. Можно показать, что минимальное кодовое расстояние кода БЧХ не меньше, чем величина <tex>d</tex>. В результате БЧХ-коды по построению способны исправлять не менее <tex>t</tex> ошибок, где <tex>t=[(d-1)/2]</tex>.
+Пусть <tex>n=2^l-1</tex>, <tex>t\le [(n-1)/2]</tex>. Тогда ''кодом БЧХ'' называется (n,k)-линейный циклический код, в котором порождающий многочлен <tex>g(x)</tex> определяется как минимальный многочлен для элементов <tex>\alpha,\alpha^2,\dots,\alpha^{2t}</tex> из поля <tex>\mathbb{F}_2^l</tex>, где <tex>\alpha</tex> — произвольный примитивный элемент поля <tex>\mathbb{F}_2^l</tex>. Набор элементов <tex>\alpha,\alpha^2,\dots,\alpha^{2t}</tex> называется ''нулями БЧХ-кода''. Можно показать, что минимальное кодовое расстояние кода БЧХ <tex>d</tex> не меньше, чем величина <tex>2t+1</tex>. В результате БЧХ-коды по построению способны исправлять не менее <tex>t</tex> ошибок.
 === Коды БЧХ: декодирование ===
-Поставим в соответствие позициям принятого слова <tex>w = (w_{n-1},\dots,w_0)</tex> элементы <tex>\alpha^{n-1},\dots,\alpha^0</tex>. При передаче по шумовому каналу кодовое слово <tex>v(x)</tex> переходит в слово <tex>w(x)=v(x)+e(x)</tex>, где <tex>e(x)=x^{j_1}+\dots+x^{j_t}</tex> — полином ошибок, а <tex>j_1,\dots,j_t</tex> — позиции, в которых произошли ошибки. Назовем ''синдромами'' принятого сообщения <tex>w(x)</tex> значения полинома <tex>w(x)</tex> в нулях БЧХ-кода, т.е. <tex>s_i=w(\alpha^i),\ i=1,\dots,2t</tex>. Если <tex>w(x)</tex> является кодовым словом, то все синдромы <tex>s_i=0</tex>. Рассмотрим ''полином локаторов ошибок''
+Поставим в соответствие позициям принятого слова <tex>w = [w_{n-1},\dots,w_0]</tex> элементы <tex>\alpha^{n-1},\dots,\alpha^0</tex>. При передаче по шумовому каналу кодовое слово <tex>v(x)</tex> переходит в слово <tex>w(x)=v(x)+e(x)</tex>, где <tex>e(x)=x^{j_1}+\dots+x^{j_{\nu}}</tex> — полином ошибок, а <tex>j_1,\dots,j_{\nu}</tex> — позиции, в которых произошли ошибки. Назовем ''синдромами'' принятого сообщения <tex>w(x)</tex> значения полинома <tex>w(x)</tex> в нулях БЧХ-кода, т.е. <tex>s_i=w(\alpha^i),\ i=1,\dots,2t</tex>. Если <tex>w(x)</tex> является кодовым словом, то все синдромы <tex>s_i=0</tex>. Рассмотрим ''полином локаторов ошибок''
-:<tex>\Lambda(x) = \prod_{i=1}^t(1+\alpha^{j_i}x) = \lambda_tx^t+\dots+\lambda_1x+1</tex>.
+:<tex>\Lambda(z) = \prod_{i=1}^{\nu}(1+\alpha^{j_i}x) = \Lambda_{\nu}x^{\nu}+\dots+\Lambda_1x+1</tex>.
-Данный полином имеет корни <tex>\alpha^{-j_i}</tex>. Можно показать, что коэффициенты полинома <tex>\Lambda(x)</tex> удовлетворяют следующей СЛАУ:
+Данный полином имеет корни <tex>\alpha^{-j_i}</tex>. Можно показать, что коэффициенты полинома <tex>\Lambda(z)</tex> удовлетворяют следующей СЛАУ:
-:<tex>\begin{bmatrix}s_1 & s_2 & \dots & s_t\\ s_2 & s_3 & \dots & s_{t+1}\\ \rule{0pt}{15pt}\dots & \dots & \dots & \dots \\ \rule{0pt}{15pt}s_t & s_{t+1} & \dots & s_{2t-1}\end{bmatrix}\begin{bmatrix}\lambda_t\\ \lambda{t-1}\\ \rule{0pt}{15pt}\dots\\ \lambda_1\end{bmatrix} = \begin{bmatrix}s_{t+1}\\ s_{t+2}\\ \rule{0pt}{15pt}\dots \\ s_{2t}\end{bmatrix}</tex>.      (*)
+:<tex>\begin{bmatrix}s_1 & s_2 & \dots & s_{\nu}\\ s_2 & s_3 & \dots & s_{\nu+1}\\ \rule{0pt}{15pt}\dots & \dots & \dots & \dots \\ \rule{0pt}{15pt}s_{\nu} & s_{\nu+1} & \dots & s_{2\nu-1}\end{bmatrix}\begin{bmatrix}\Lambda_{\nu}\\ \Lambda_{\nu-1}\\ \rule{0pt}{15pt}\dots\\ \Lambda_1\end{bmatrix} = \begin{bmatrix}s_{\nu+1}\\ s_{\nu+2}\\ \rule{0pt}{15pt}\dots \\ s_{2\nu}\end{bmatrix}</tex>.      (*)
 Отсюда получаем следующую общую схему декодирования БЧХ-кода:
-# Для принятого слова <tex>w(x)</tex> вычислить синдромы <tex>s_i=w(\alpha^i),\ i=1,\dots,d-1</tex>. Если все <tex>s_i=0</tex>, то вернуть <tex>w(x)</tex> в качестве ответа;
+# Для принятого слова <tex>w(x)</tex> вычислить синдромы <tex>s_i=w(\alpha^i),\ i=1,\dots,2t</tex>. Если все <tex>s_i=0</tex>, то вернуть <tex>w(x)</tex> в качестве ответа;
-# Найти количество допущенных ошибок <tex>t</tex> и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
+# Найти количество допущенных ошибок <tex>\nu</tex> и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
-# Найти все корни полинома <tex>\Lambda(x)</tex> путем полного перебора, по найденным корням вычислить номера позиций <tex>j_1,\dots,j_t</tex>, в которых произошли ошибки;
+# Найти все корни полинома <tex>\Lambda(z)</tex> путем полного перебора, по найденным корням вычислить номера позиций <tex>j_1,\dots,j_{\nu}</tex>, в которых произошли ошибки;
-# Исправить ошибки в позициях <tex>j_1,\dots,j_t</tex> путем инвертирования соответствующих битов в <tex>w(x)</tex>. Если после произведенного исправления <tex>w(x)</tex> не является кодовым словом (его синдромы не равны нулю), то вернуть отказ от декодирования.
+# Исправить ошибки в позициях <tex>j_1,\dots,j_{\nu}</tex> путем инвертирования соответствующих битов в <tex>w(x)</tex>.
 Различные алгоритмы декодирования БЧХ-кодов по-разному решают задачу на шаге 2 общего алгоритма декодирования. Рассмотрим две схемы декодирования.
@@ Строка 57: / Строка 52: @@
 ==== Декодер PGZ (Peterson–Gorenstein–Zierler) ====
-Данный декодер предлагает непосредственно решать СЛАУ (*). Основная трудность здесь — это определить количество допущенных при передаче ошибок <tex>t</tex>. В декодере PGZ происходит перебор по всем значениям <tex>t</tex>, начиная с максимального <tex>[(d-1)/2]</tex>. При текущем <tex>t</tex> делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее <tex>t</tex> признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то величина <tex>t</tex> уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования.
+Данный декодер предполагает непосредственное решение СЛАУ (*). Основная трудность здесь — это определить количество фактически допущенных при передаче ошибок <tex>\nu</tex>. В декодере PGZ происходит перебор по всем значениям <tex>\nu</tex>, начиная с <tex>t</tex>. При текущем <tex>\nu</tex> делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее <tex>\nu</tex> признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то <tex>\Lambda_{\nu}=0</tex>, величина <tex>\nu</tex> уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования. Также отказ от декодирования выдаётся в случае, если после исправления синдромы <tex>\hat{v}(x)</tex> не равны нулю (кодовое слово не найдено).
-==== Декодер BMA (Berlekamp–Massey Algorithm) ====
+==== Декодер Euclid ====
-Шаг 2 общего алгоритма декодирования может быть представлен как поиск для заданного набора синдромов <tex>s_1,\dots,s_{d-1}</tex> минимального <tex>t</tex> и набора <tex>\lambda_1,\dots,\lambda_t</tex>, удовлетворяющих следующей СЛАУ:
+Рассмотрим ''синдромный полином'' вида <tex>S(z) = s_{2t}z^{2t}+s_{2t-1}z^{2t-1}+\dots+s_1z+1</tex>, где <tex>s_i</tex> — вычисленные ранее синдромы. Тогда можно показать, что <tex>S(z)</tex> и <tex>\Lambda(z)</tex> удовлетворяют следующему уравнению:
-:<tex>\begin{bmatrix}1 & \lambda_1 & \dots & \lambda_t\end{bmatrix}\begin{bmatrix}s_{t+1} & s_{t+2} & \dots & s_{d-1}\\ s_t & s_{t+1} & \dots & s_{d-2}\\ \rule{0pt}{15pt}\dots & \dots & \dots & \dots\\ \rule{0pt}{15pt}s_1 & s_2 & \dots & s_{d-1-t}\end{bmatrix} = \begin{bmatrix}0 & 0 & \dots & 0\end{bmatrix}</tex>.
+:<tex>z^{2t+1}A(z) + S(z)\Lambda(z) = r(z)</tex>.
-Матрица данной СЛАУ обладает структурой матрицы Тёплица. Поэтому для этой СЛАУ существует более эффективный [http://trsys.faculty.jacobs-university.de/files/IEE_bma.pdf алгоритм решения], чем общий алгоритм гауссовских исключений:
+Здесь <tex>r(z)</tex> — некоторый многочлен из <tex>\mathbb{F}_2^l[x]</tex>, степень которого не превышает <tex>t</tex>. Решение данного уравнения <tex>A(z), \Lambda(z), r(z)</tex> для заданных многочленов <tex>z^{2t+1}</tex> и <tex>S(z)</tex> может быть найдено с помощью расширенного алгоритма Евклида. Здесь итерации алгоритма Евклида проводятся до тех пор, пока степень текущего остатка <tex>r(z)</tex> не станет меньше или равна <tex>t</tex>. Степень найденного <tex>\Lambda(z)</tex> равна количеству фактически допущенных при передаче ошибок <tex>\nu</tex>. Если количество корней у <tex>\Lambda(z)</tex> не совпадает с <tex>\nu</tex>, то выдаётся отказ от декодирования.
-:<tex>\Lambda(x):=1,\ B(x):=1,\ b:=1,\ m:=1,\ t:=0</tex>; ''//Инициализация''
-:'''для''' <tex>i=1,\dots,d-1</tex> ''//Цикл по синдромам''
-::<tex>d:=s_i+\sum_{j=1}^ts_{i-j}\lambda_{t+1-j}</tex>;
-::'''если''' <tex>d=0</tex>, '''то''' <tex>m:=m+1</tex>;
-::'''иначе'''
-:::'''если''' <tex>2t>i-1</tex>, '''то'''
-::::<tex>\Lambda(x):=\Lambda(x) - \frac{d}{b}x^mB(x)</tex>;
-::::<tex>m:=m+1</tex>;
-:::'''иначе'''
-::::<tex>B_1(x):=\Lambda(x)</tex>;
-::::<tex>\Lambda(x):=\Lambda(x)-\frac{d}{b}x^mB(x)</tex>;
-::::<tex>B(x):=B_1(x);\ b:=d;\ m:=1;\ t:=i-t</tex>;
 == Формулировка задания ==
-В задании выдается [[Media:Gf_primpoly.zip|список]] всех примитивных многочленов степени <tex>l</tex> для поля <tex>GF(2^l)</tex> для всех <tex>l=1,2,\dots,16</tex>.
+В задании выдается [[Media:Gf_primpoly.zip|список]] всех примитивных многочленов степени <tex>l</tex> над полем <tex>\mathbb{F}_2</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>\mathbb{F}_2^l</tex>: сложение, умножение, деление, решение СЛАУ, поиск минимального многочлена из <tex>\mathbb{F}_2[x]</tex> для заданного набора корней из поля <tex>\mathbb{F}_2^l</tex>;
+# Реализовать основные операции для работы с многочленами из <tex>\mathbb{F}_2^l[x]</tex>: произведение многочленов, деление многочленов с остатком, расширенный алгоритм Евклида для пары многочленов, вычисление значения многочлена для набора элементов из <tex>\mathbb{F}_2^l</tex>;
 # Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
-# Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных <tex>n</tex> и <tex>d</tex>;
+# Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных <tex>n</tex> и <tex>t</tex>;
-# Построить графики зависимости скорости БЧХ-кода <tex>r=k/n</tex> от минимального кодового расстояния <tex>d</tex> для различных значений <tex>n</tex>. Какие значения <tex>d</tex> следует выбирать на практике для заданного <tex>n</tex>?
+# Построить графики зависимости скорости БЧХ-кода <tex>r=k/n</tex> от количества исправляемых кодом ошибок <tex>t</tex> для различных значений <tex>n</tex>. Какие значения <tex>t</tex> следует выбирать на практике для заданного <tex>n</tex>?
-# Реализовать процедуру вычисления истинного минимального расстояния циклического кода, заданного своим порождающим многочленом, путем полного перебора по всем <tex>2^k-1</tex> кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина <tex>d</tex>, задаваемая при построении порождающего многочлена;
+# Реализовать процедуру вычисления истинного минимального расстояния циклического кода <tex>d</tex>, заданного своим порождающим многочленом, путем полного перебора по всем <tex>2^k-1</tex> кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина <tex>2t+1</tex>;
-# Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ. Провести замеры времени работы реализованного алгоритма декодирования;
+# Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ и на основе расширенного алгоритма Евклида. Провести сравнение двух методов декодирования по времени работы;
-# '''[Бонус]''' Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
+# С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до <tex>t</tex> ошибок. Может ли БЧХ-код исправить больше, чем <tex>t</tex> ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем <tex>t</tex>?
-# С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до <tex>[(d-1)/2]</tex> ошибок. Может ли БЧХ-код исправить больше, чем <tex>[(d-1)/2]</tex> ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем <tex>[(d-1)/2]</tex>?
 # Составить отчет в формате PDF обо всех проведенных исследованиях.
 == Рекомендации по выполнению задания ==
-# Для реализации операций умножения и деления ненулевых элементов в поле <tex>GF(2^l)</tex> удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента <tex>\alpha</tex>: <tex>GF(2^l)=\{0,\alpha,\alpha^2,\dots,\alpha^{2^l-2},\alpha^{2^l-1}=1}</tex>. Тогда произведение двух элементов поля <tex>\alpha^{k_1}</tex> и <tex>\alpha^{k_2}</tex> равно <tex>\alpha^{k_1+k_2\ \mbox{mod}\ 2^l-1}</tex>. Аналогично частное этих двух элементов равно <tex>\alpha^{k_1-k_2\ \mbox{mod}\ 2^l-1}</tex>. Для быстрого перехода от десятичного представления элементов поля к степенному и обратно удобно завести таблицу размера <tex>(2^l-1){\times}2</tex>. В первой колонке этой таблицы в позиции <tex>i</tex> будет находится число <tex>j:\ \alpha^j=i</tex>, а во второй колонке в позиции <tex>i</tex> — значение <tex>\alpha^i</tex>.
+# Для реализации операций умножения и деления ненулевых элементов в поле <tex>\mathbb{F}_2^l</tex> удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента <tex>\alpha</tex>: <tex>\mathbb{F}_2^l=\{0,\alpha,\alpha^2,\dots,\alpha^{2^l-2},\alpha^{2^l-1}=1}</tex>. Тогда произведение двух элементов поля <tex>\alpha^{k_1}</tex> и <tex>\alpha^{k_2}</tex> равно <tex>\alpha^{k_1+k_2\ \mbox{mod}\ 2^l-1}</tex>. Аналогично частное этих двух элементов равно <tex>\alpha^{k_1-k_2\ \mbox{mod}\ 2^l-1}</tex>. Для быстрого перехода от десятичного представления элементов поля к степенному и обратно удобно завести таблицу размера <tex>(2^l-1){\times}2</tex>. В первой колонке этой таблицы в позиции <tex>i</tex> будет находится число <tex>j:\ \alpha^j=i</tex>, а во второй колонке в позиции <tex>i</tex> — значение <tex>\alpha^i</tex>.
-# Для построения таблицы соответствий между десятичным и степенным представлением элементов в поле <tex>GF(2^l)</tex>, а также на этапе выбора нулей БЧХ-кода необходимо иметь некоторый примитивный элемент поля <tex>\alpha</tex>. Найти все примитивные элементы поля можно полным перебором. Однако, в случае построения поля <tex>GF(2^l)</tex> как фактор-кольца <tex>GF(2)[x]/f(x)</tex>, где в качестве <tex>f(x)</tex> выступает примитивный полином поля <tex>GF(2^l)</tex> степени <tex>l</tex>, элемент <tex>x</tex> (в десятичном представлении равен 2) гарантированно является примитивным элементом поля. Это свойство теряется при использовании в качестве <tex>f(x)</tex> произвольного неприводимого многочлена степени <tex>l</tex>.
 # При реализации алгоритмов задания рекомендуется, помимо прочего, использовать следующие проверки на корректность:
 #* порождающий полином БЧХ-кода должен быть делителем многочлена <tex>x^n-1</tex> (иначе код не будет циклическим);
 #* произвольное кодовое слово БЧХ-кода <tex>v(x)</tex> должно делиться без остатка на порождающий многочлен кода <tex>g(x)</tex>, а также обращаться в ноль на нулях кода (все синдромы кодового слова равны нулю);
-#* минимальный многочлен <tex>m_{\alpha}(x)</tex> для элемента <tex>\alpha\in GF(2^l)</tex>, вычисляемый как многочлен с корнями <tex>\alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}</tex>, должен иметь коэффициенты из <tex>GF(2)</tex>;
+#* минимальный многочлен <tex>m_{\alpha}(x)</tex> для элемента <tex>\alpha\in \mathbb{F}_2^l</tex>, вычисляемый как многочлен с корнями <tex>\alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}</tex>, должен иметь коэффициенты из <tex>\mathbb{F}_2</tex>;
-#* минимальное кодовое расстояние БЧХ-кода <tex>d_{min}</tex>, найденное полным перебором, должно быть не меньше, чем параметр <tex>d</tex> на этапе построения порождающего многочлена БЧХ-кода <tex>g(x)</tex>;
+#* минимальное кодовое расстояние БЧХ-кода <tex>d</tex>, найденное полным перебором, должно быть не меньше, чем величина <tex>2t+1</tex>.
-#* в декодере BMA для бинарных БЧХ-кодов на всех чётных итерациях значение <tex>d</tex> должно быть равно нулю.
 == Оформление задания ==
@@ Строка 110: / Строка 90: @@
 {|class="standard"
- !''Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля <tex>GF(2^l)</tex>''
+ !''Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля <tex>\mathbb{F}_2^l</tex>''
  |-
  |pm = '''gf_gen_pow_matrix'''(pp)
@@ Строка 116: / Строка 96: @@
  |ВХОД
  |-
- |pp — примитивный многочлен в поле <tex>GF(2^l)</tex> степени <tex>l</tex>, десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома;
+ |pp — примитивный многочлен над полем <tex>\mathbb{F}_2</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>.
+ |pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу <tex>\alpha</tex>, матрица размера <tex>2^l-1{\times}2</tex>, в которой в первой колонке в позиции <tex>i</tex> стоит степень <tex>j:\alpha^j=i</tex>, а во второй колонке в позиции <tex>i</tex> стоит значение <tex>\alpha^i</tex>.
  |}
@@ Строка 126: / Строка 106: @@
 {|class="standard"
- !''Суммирование в <tex>GF(2^l)</tex>''
+ !''Суммирование в <tex>\mathbb{F}_2^l</tex>''
  |-
  |res = '''gf_sum'''(X, Y) — поэлементное суммирование двух матриц
@@ Строка 134: / Строка 114: @@
  |ВХОД
  |-
- |X, Y — матрица из элементов поля <tex>GF(2^l)</tex>, каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома;
+ |X, Y — матрица из элементов поля <tex>\mathbb{F}_2^l</tex>, каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>\mathbb{F}_2</tex>, первый разряд соответствует старшей степени полинома;
  |-
  |dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1;
@@ Строка 146: / Строка 126: @@
 {|class="standard"
- !''Умножение/деление в поле <tex>GF(2^l)</tex>''
+ !''Умножение/деление в поле <tex>\mathbb{F}_2^l</tex>''
  |-
  |res = '''gf_prod'''(X, Y, pm) — поэлементное умножение двух матриц
@@ Строка 154: / Строка 134: @@
  |ВХОД
  |-
- |X, Y — матрица из элементов поля <tex>GF(2^l)</tex>;
+ |X, Y — матрица из элементов поля <tex>\mathbb{F}_2^l</tex>;
  |-
- |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
  |-
  |ВЫХОД
@@ Строка 166: / Строка 146: @@
 {|class="standard"
- !''Решение СЛАУ <tex>A\vec{x}=\vec{b}</tex> в поле <tex>GF(2^l)</tex> методом Гаусса''
+ !''Решение СЛАУ <tex>A\vec{x}=\vec{b}</tex> в поле <tex>\mathbb{F}_2^l</tex> методом Гаусса''
  |-
  |x = '''gf_linsolve'''(A, b, pm)
@@ Строка 172: / Строка 152: @@
  |ВХОД
  |-
- |A — квадратная матрица из элементов поля <tex>GF(2^l)</tex>;
+ |A — квадратная матрица из элементов поля <tex>\mathbb{F}_2^l</tex>;
  |-
- |b — вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
+ |b — вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>;
  |-
- |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
  |-
  |ВЫХОД
@@ Строка 186: / Строка 166: @@
 {|class="standard"
- !''Поиск всех примитивных элементов поля <tex>GF(2^l)</tex>''
+ !''Поиск минимального полинома в <tex>\mathbb{F}_2[x]</tex> с заданным набором корней из <tex>\mathbb{F}_2^l</tex>''
  |-
- |alpha = '''gf_primel'''(pm)
+ |[p, x_coset] = '''gf_minpoly'''(x, pm)
  |-
  |ВХОД
  |-
- |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+ |x — вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>;
+ |-
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
  |-
  |ВЫХОД
  |-
- |alpha — найденные примитивные элементы, вектор-столбец десятичных чисел.
+ |p — найденный полином, бинарный вектор-строка;
+ |-
+ |x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>.
+ |-
  |}
@@ Строка 202: / Строка 187: @@
 {|class="standard"
- !''Поиск минимального полинома в <tex>GF(2)[x]</tex> с заданным набором корней из <tex>GF(2^l)</tex>''
+ !''Значение полинома из <tex>\mathbb{F}_2^l[x]</tex> на наборе элементов из <tex>\mathbb{F}_2^l</tex>''
  |-
- |[p, x_coset] = '''gf_minpoly'''(x, pm, method)
+ |res = '''gf_polyval'''(p, X, pm)
  |-
  |ВХОД
  |-
- |x — вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
+ |p — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
  |-
- |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+ |X — вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>;
  |-
- |method — (необязательный параметр) метод поиска, строка, возможные значения 'ls' (с помощью решения СЛАУ) и 'cosets' (с помощью построения циклотомических классов смежности), по умолчанию = 'cosets';
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
  |-
  |ВЫХОД
  |-
- |p — найденный полином, бинарный вектор-столбец;
+ |res — значение полинома для всех элементов X, вектор-столбец.
+ |}
+&nbsp;
+{|class="standard"
+ !''Умножение двух полиномов из <tex>\mathbb{F}_2^l[x]</tex>''
  |-
- |x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля <tex>GF(2^l)</tex>.
+ |res = '''gf_polyprod'''(p1, p2, pm)
  |-
+ |ВХОД
+ |-
+ |p1 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
+ |-
+ |p2 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
+ |-
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
+ |-
+ |ВЫХОД
+ |-
+ |res — значение полинома p1(x)*p2(x), вектор-строка коэффициентов, начиная со старшей степени.
  |}
@@ Строка 225: / Строка 227: @@
 {|class="standard"
- !''Значение полинома из <tex>GF(2^l)[x]</tex> на элементе из <tex>GF(2^l)</tex>''
+ !''Деление двух полиномов из <tex>\mathbb{F}_2^l[x]</tex> с остатком''
  |-
- |res = '''gf_polyval'''(p, X, pm)
+ |[q, r] = '''gf_polydiv'''(p1, p2, pm)
  |-
  |ВХОД
  |-
- |p — полином из <tex>GF(2^l)[x]</tex>, вектор-столбец коэффициентов, начиная со старшей степени;
+ |p1 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
  |-
- |X — вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
+ |p2 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
  |-
- |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
  |-
  |ВЫХОД
  |-
- |res — значение полинома для всех элементов X.
+ |q — результат деления, вектор-строка коэффициентов, начиная со старшей степени;
+ |-
+ |r — остаток от деления, вектор-строка коэффициентов, начиная со старшей степени.
+ |}
+&nbsp;
+{|class="standard"
+ !''Расширенный алгоритм Евклида для решения уравнения a(x)p1(x)+b(x)p2(x)= r(x) для двух полиномов p1, p2 из <tex>\mathbb{F}_2^l[x]</tex>''
+ |-
+ |[r, a, b] = '''gf_euclid'''(p1, p2, max_deg, pm)
+ |-
+ |ВХОД
+ |-
+ |p1 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
+ |-
+ |p2 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
+ |-
+ |max_deg — максимально допустимая степень остатка r(x), число;
+ |-
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
+ |-
+ |ВЫХОД
+ |-
+ |r — остаток, вектор-строка коэффициентов, начиная со старшей степени;
+ |-
+ |a — коэффициент при p1(x), вектор-строка коэффициентов, начиная со старшей степени;
+ |-
+ |b — коэффициент при p2(x), вектор-строка коэффициентов, начиная со старшей степени.
  |}
@@ Строка 253: / Строка 283: @@
  |U — исходные сообщения для кодирования, бинарная матрица размера <число_сообщений> x k;
  |-
- |g — порождающий полином кода, бинарный вектор-столбец длины m+1;
+ |g — порождающий полином кода, бинарный вектор-строка длины m+1;
  |-
  |ВЫХОД
@@ Строка 263: / Строка 293: @@
 {|class="standard"
- !''Поиск порождающего многочлена для БЧХ-кода''
+ !''Вычисление минимального расстояния циклического кода путем полного перебора''
  |-
- |[g, R, pm] = '''bch_genpoly'''(n, d)
+ |d = '''cyclic_dist'''(g, n)
  |-
  |ВХОД
  |-
- |n — длина кода, число вида <tex>2^l-1</tex>;
+ |g — порождающий многочлен кода, бинарный вектор-строка;
  |-
- |d — минимальное расстояние кода, число;
+ |n — длина кода;
  |-
  |ВЫХОД
  |-
- |g — порождающий полином кода, бинарный вектор-столбец;
+ |d — минимальное расстояние кода, число.
- |-
- |R — нули кода, вектор-столбец чисел;
- |-
- |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>.
  |}
@@ Строка 285: / Строка 311: @@
 {|class="standard"
- !''Декодирование БЧХ-кода''
+ !''Поиск порождающего многочлена для БЧХ-кода''
  |-
- |V = '''bch_decoding'''(W, R, pm, method)
+ |[g, R, pm] = '''bch_genpoly'''(n, t)
  |-
  |ВХОД
  |-
- |W — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
+ |n — длина кода, число вида <tex>2^l-1</tex>;
  |-
- |R — нули кода, вектор-столбец элементов из <tex>GF(2^l)</tex>;
+ |t — исправляемое число ошибок, число;
  |-
- |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+ |ВЫХОД
  |-
- |method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'pgz';
+ |g — порождающий полином кода, бинарный вектор-строка;
  |-
- |ВЫХОД
+ |R — нули кода, вектор-столбец десятичных чисел;
  |-
- |V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN.
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>.
  |}
@@ Строка 307: / Строка 333: @@
 {|class="standard"
- !''Вычисление минимального расстояния циклического кода путем полного перебора''
+ !''Декодирование БЧХ-кода''
  |-
- |d = '''cyclic_dist'''(g, n)
+ |V = '''bch_decoding'''(W, R, pm, method)
  |-
  |ВХОД
  |-
- |g — порождающий многочлен кода, бинарный вектор-столбец;
+ |W — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
  |-
- |n — длина кода, число вида <tex>2^l-1</tex>;
+ |R — нули кода, вектор-столбец элементов из <tex>\mathbb{F}_2^l</tex>;
+ |-
+ |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
+ |-
+ |method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'euclid', по умолчанию = 'euclid';
  |-
  |ВЫХОД
  |-
- |d — минимальное расстояние кода, число.
+ |V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN.
  |}