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

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

Перейти к: навигация, поиск
Основная статья: Практикум на ЭВМ (317)

Содержание

Начало выполнения задания: 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 такой, что

  1. Все кодовые слова v(x) могут быть представлены как g(x)q(x), где q(x) — некоторый полином степени, не превышающей k-1;
  2. Полином 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:

  1. Построить циклотомический класс, порожденный элементом \alpha;
  2. Найти коэффициенты полинома 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}. (*)

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

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

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

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

  1. Для реализации операций умножения и деления ненулевых элементов в поле \mathbb{F}_2^l удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента \alpha: \mathbb{F}_2^l=\{0,\alpha,\alpha^2,\dots,\alpha^{2^l-2},\alpha^{2^l-1}=1}. Тогда произведение двух элементов поля \alpha^{k_1} и \alpha^{k_2} равно \alpha^{k_1+k_2\ \mbox{mod}\ 2^l-1}. Аналогично частное этих двух элементов равно \alpha^{k_1-k_2\ \mbox{mod}\ 2^l-1}. Для быстрого перехода от десятичного представления элементов поля к степенному и обратно удобно завести таблицу размера (2^l-1){\times}2. В первой колонке этой таблицы в позиции i будет находится число j:\ \alpha^j=i, а во второй колонке в позиции i — значение \alpha^i.
  2. При реализации алгоритмов задания рекомендуется, помимо прочего, использовать следующие проверки на корректность:
    • порождающий полином БЧХ-кода должен быть делителем многочлена x^n-1 (иначе код не будет циклическим);
    • произвольное кодовое слово БЧХ-кода v(x) должно делиться без остатка на порождающий многочлен кода g(x), а также обращаться в ноль на нулях кода (все синдромы кодового слова равны нулю);
    • минимальный многочлен m_{\alpha}(x) для элемента \alpha\in \mathbb{F}_2^l, вычисляемый как многочлен с корнями \alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}, должен иметь коэффициенты из \mathbb{F}_2;
    • минимальное кодовое расстояние БЧХ-кода d, найденное полным перебором, должно быть не меньше, чем величина 2t+1.

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

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

 

Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля \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.
Личные инструменты