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

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

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

Версия 16:53, 8 мая 2013

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

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

Начало выполнения задания: 8 мая 2013 г.
Срок сдачи: 20 мая 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)-блоковый код называется линейным, если множество его кодовых слов образует линейное подпространство размерности $K$ общего линейного пространства $\{0,1\}^N$ . Одним из способов задания $K$ -мерного линейного подпространства является рассмотрение множества решений следующей системы линейных уравнений:

$Hx=0$ ,

где $H\in\{0,1\}^{(N-K){\times}N}$ — матрица ранга $N-K$ . Такая матрица называется проверочной матрицей кода, т.к. с её помощью можно проверить, является ли слово $x$ кодовым словом путём проверки соотношения $Hx=0$ (здесь и далее все операции проводятся по модулю 2).

Рассмотрим задачу кодирования слов исходного сообщения $t$ в кодовые слова $x$ (N,K)-линейного блокового кода, задаваемого проверочной матрицей $H$ . Для этого необходимо найти базис $K$ -мерного линейного подпространства $g_1,\dots,g_K\in\{0,1\}^N$ . Тогда, рассматривая базисные вектора как столбцы общей матрицы $G\in\{0,1\}^{N{\times}K}$ , операция кодирования может быть представлена как $x=Gt$ . Матрица $G$ называется порождающей матрицей кода. Кодирование называется систематическим, если все биты слова $t$ копируются в некоторые биты кодового слова $x$ , т.е. в матрице G некоторое подмножество строк образует единичную матрицу размера $K{\times}K$ . При систематическом кодировании обратный процесс преобразования из декодированного кодового слова $\hat{x}$ в декодированное слово сообщения $\hat{t}$ становится тривиальным.

Одним из способов построения порождающей матрицы кода по заданной проверочной матрице является преобразование проверочной матрицы к каноническому ступенчатому виду. Такое преобразование всегда может быть сделано с помощью гауссовских исключений. С точностью до перестановки столбцов канонический ступенчатый вид матрицы $H$ эквивалентен её представлению в виде $\begin{bmatrix} I_{N-K} & P\end{bmatrix}$ , где $I_{N-K}$ — единичная матрица размера $(N-K)\times(N-K)$ . Тогда в качестве порождающей матрицы, обеспечивающей систематическое кодирование, можно выбрать матрицу

$G = \begin{bmatrix}P\\ I_K\end{bmatrix}$ .

Действительно, в этом случае $HGt = (P+P)t = 0$ .

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

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

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

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

Поиск порождающего многочлена для БЧХ-кода с максимизацией $k$
[g, R, pm] = bch_genpoly(n, d)
ВХОД
n — длина кода, число вида $2^l-1$ ;
d — минимальное расстояние кода, число;
ВЫХОД
g — порождающий полином кода, число;
R — нули кода, вектор-столбец чисел;
pm — матрица соответствия между десятичным и степенным представлением в поле $GF(2^l)$ .

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

@@ Строка 47: / Строка 47: @@
 == Рекомендации по выполнению задания ==
+# Для реализации операций умножения и деления ненулевых элементов в поле <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>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>d</tex>, найденное полным перебором, должно быть не меньше, чем параметр <tex>d</tex> на этапе построения порождающего многочлена БЧХ-кода <tex>g(x)</tex>.
 == Оформление задания ==

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

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

Версия 16:53, 8 мая 2013

Содержание

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

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

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

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

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

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты