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

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

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


Основная статья: Практикум на ЭВМ (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.

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