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

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

Версия от 13:14, 25 апреля 2014; Kropotov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

Начало выполнения задания: 26 апреля 2014 г.
Срок сдачи: 11 мая 2013 г. (воскресенье), 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$ , которое, вообще говоря, отличается от $v$ . Далее алгоритм декодирования пытается восстановить переданное слово $v$ путем поиска среди всевозможных кодовых слов ближайшего к $w$ . Обозначим результат работы алгоритма декодирования через $\hat{v}$ . На последнем этапе декодированное слово $\hat{v}$ переводится в декодированное слово исходного сообщения $\hat{u}$ . Очевидно, что (n,k,d)-блоковый код способен обнаруживать до $d-1$ ошибки и исправлять до $[(d-1)/2]$ ошибок.

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

Множество $\{0,1\}^n$ с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов $\{0,1\}$ . (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$ ;
Полином $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 GF(2)[x]$ называется минимальным полиномом для элемента $\alpha\in GF(2^l)$ , если он является неприводимым полиномом минимальной степени, для которого $\alpha$ является корнем. В частности, минимальный полином для примитивного элемента $\alpha$ называется примитивным полиномом. Можно показать, что корнями минимального полинома $m_{\alpha}(x)$ являются

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

Данный набор элементов из поля $GF(2^l)$ называется циклотомическим классом смежности для элемента $\alpha$ . Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином

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

имеет коэффициенты из $GF(2)$ и является минимальным полиномом для $\alpha$ , а также для всех элементов поля, входящих вместе с $\alpha$ в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля $\alpha$ :

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

$\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}$ .

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

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

Поставим в соответствие позициям принятого слова $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_t}$ — полином ошибок, а $j_1,\dots,j_t$ — позиции, в которых произошли ошибки. Назовем синдромами принятого сообщения $w(x)$ значения полинома $w(x)$ в нулях БЧХ-кода, т.е. $s_i=w(\alpha^i),\ i=1,\dots,2t$ . Если $w(x)$ является кодовым словом, то все синдромы $s_i=0$ . Рассмотрим полином локаторов ошибок

$\Lambda(x) = \prod_{i=1}^t(1+\alpha^{j_i}x) = \lambda_tx^t+\dots+\lambda_1x+1$ .

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

$\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}$ . (*)

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

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

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

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

Данный декодер предлагает непосредственно решать СЛАУ (*). Основная трудность здесь — это определить количество допущенных при передаче ошибок $t$ . В декодере PGZ происходит перебор по всем значениям $t$ , начиная с максимального $[(d-1)/2]$ . При текущем $t$ делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее $t$ признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то величина $t$ уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования.

Декодер BMA (Berlekamp–Massey Algorithm)

Шаг 2 общего алгоритма декодирования может быть представлен как поиск для заданного набора синдромов $s_1,\dots,s_{d-1}$ минимального $t$ и набора $\lambda_1,\dots,\lambda_t$ , удовлетворяющих следующей СЛАУ:

$\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}$ .

Матрица данной СЛАУ обладает структурой матрицы Тёплица. Поэтому для этой СЛАУ существует более эффективный алгоритм решения, чем общий алгоритм гауссовских исключений:

$\Lambda(x):=1,\ B(x):=1,\ b:=1,\ m:=1,\ t:=0$ ; //Инициализация

для $i=1,\dots,d-1$ //Цикл по синдромам

$d:=s_i+\sum_{j=1}^ts_{i-j}\lambda_{t+1-j}$ ;

если $d=0$ , то $m:=m+1$ ;

иначе

если $2t>i-1$ , то

$\Lambda(x):=\Lambda(x) - \frac{d}{b}x^mB(x)$ ;

$m:=m+1$ ;

иначе

$B_1(x):=\Lambda(x)$ ;

$\Lambda(x):=\Lambda(x)-\frac{d}{b}x^mB(x)$ ;

$B(x):=B_1(x);\ b:=d;\ m:=1;\ t:=i-t$ ;

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

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

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

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

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

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

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

Поиск порождающего многочлена для БЧХ-кода
[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 — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
R — нули кода, вектор-столбец элементов из $GF(2^l)$ ;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ ;
method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'pgz';
ВЫХОД
V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN.

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

Источник — «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)

Декодер BMA (Berlekamp–Massey Algorithm)

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты