Практикум на ЭВМ (317)/2013/Коды БЧХ
Материал из MachineLearning.
Содержание |
Начало выполнения задания: 9 мая 2013 г.
Срок сдачи: 20 мая 2013 г. (понедельник), 23:59.
Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Необходимая теория
Задача помехоустойчивого кодирования
Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При блоковом кодировании входящий поток информации разбивается на блоки фиксированной длины . Обозначим один такой блок через . Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через , . Для кодирования всевозможных блоков необходимо использовать кодовых слов длины . Определим минимальное расстояние кода как минимальное хэммингово расстояние для всех различных пар кодовых слов. Назовём множество кодовых слов длины с минимальным расстоянием (n,k,d)-блоковым кодом, а величину — скоростью кода. При передаче по каналу с шумом кодовое слово превращается в принятое слово , которое, вообще говоря, отличается от . Далее алгоритм декодирования пытается восстановить переданное слово путем поиска среди всевозможных кодовых слов ближайшего к . Обозначим результат работы алгоритма декодирования через . На последнем этапе декодированное слово переводится в декодированное слово исходного сообщения . Очевидно, что (n,k,d)-блоковый код способен обнаруживать до ошибки и исправлять до ошибок.
Кодирование с помощью (n,k,d)-линейного циклического блокового кода
Множество с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов . (n,k,d)-блоковый код называется линейным, если множество его кодовых слов образует линейное подпространство размерности общего линейного пространства . Таким образом, для линейного кода произвольная линейная комбинация кодовых слов является кодовым словом. (n,k,d)-линейный блоковый код называется циклическим, если любой циклический сдвиг кодового слова является кодовым словом. Поставим в соответствие произвольному вектору полином вида . Тогда можно показать, что для (n,k,d)-линейного циклического блокового кода найдется полином степени такой, что
- Все кодовые слова могут быть представлены как , где — некоторый полином степени ;
- Полином является делителем полинома .
Такой полином называется порождающим полиномом циклического кода. Любой полином, являющийся делителем , является порождающим для некоторого циклического кода.
Кодирование называется систематическим, если все биты исходного сообщения копируются в некоторые биты кодового слова . При систематическом кодировании обратный процесс преобразования из декодированного кодового слова в декодированное слово сообщения становится тривиальным. Для циклического кода, задаваемого порождающим полиномом , процесс систематического кодирования может быть реализован как
- .
Здесь через обозначена операция взятия остатка от деления многочлена на многочлен .
Коды БЧХ: кодирование
Полином называется минимальным полиномом для элемента , если он является неприводимым полиномом минимальной степени, для которого является корнем. В частности, минимальный полином для примитивного элемента называется примитивным полиномом. Можно показать, что корнями минимального полинома являются
- .
Данный набор элементов из поля называется циклотомическим классом смежности для элемента . Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином
имеет коэффициенты из и является минимальным полиномом для , а также для всех элементов поля, входящих вместе с в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля :
- Построить циклотомический класс, порожденный элементом ;
- Найти коэффициенты полинома путем перемножения многочленов для всех , либо решить СЛАУ
- .
Пусть , . Тогда кодом БЧХ называется (n,k,d)-линейный циклический код, в котором порождающий многочлен определяется как минимальный многочлен для элементов из поля , где — произвольный примитивный элемент поля . Набор элементов называется нулями БЧХ-кода. Можно показать, что минимальное кодовое расстояние кода БЧХ не меньше, чем величина . В результате БЧХ-коды по построению способны исправлять не менее ошибок, где .
Коды БЧХ: декодирование
Поставим в соответствие позициям принятого слова элементы . При передаче по шумовому каналу кодовое слово переходит в слово , где — полином ошибок, а — позиции, в которых произошли ошибки. Назовем синдромами принятого сообщения значения полинома в нулях БЧХ-кода, т.е. . Если является кодовым словом, то все синдромы . Рассмотрим полином локаторов ошибок
- .
Данный полином имеет корни . Можно показать, что коэффициенты полинома удовлетворяют следующей СЛАУ:
- . (*)
Отсюда получаем следующую общую схему декодирования БЧХ-кода:
- Для принятого слова вычислить синдромы . Если все , то вернуть в качестве ответа;
- Найти количество допущенных ошибок и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
- Найти все корни полинома путем полного перебора, по найденным корням вычислить номера позиций , в которых произошли ошибки;
- Исправить ошибки в позициях путем инвертирования соответствующих битов в . Если после произведенного исправления не является кодовым словом (его синдромы не равны нулю), то вернуть отказ от декодирования.
Различные алгоритмы декодирования БЧХ-кодов по-разному решают задачу на шаге 2 общего алгоритма декодирования. Рассмотрим две схемы декодирования.
Декодер PGZ (Peterson–Gorenstein–Zierler)
Данный декодер предлагает непосредственно решать СЛАУ (*). Основная трудность здесь — это определить количество допущенных при передаче ошибок . В декодере PGZ происходит перебор по всем значениям , начиная с максимального . При текущем делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то величина уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования.
Декодер BMA (Berlekamp–Massey)
to appear
Формулировка задания
В задании выдается список всех примитивных многочленов степени для поля для всех .
- Реализовать основные операции в поле : сложение, умножение, деление, решение СЛАУ, поиск примитивных элементов, вычисление значения многочлена из для заданного элемента поля. Реализовать поиск минимального многочлена из для заданного набора корней из поля двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
- Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
- Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных и ;
- Построить графики зависимости скорости БЧХ-кода от минимального кодового расстояния для различных значений . Какие значения следует выбирать на практике для заданного ?
- Реализовать процедуру вычисления истинного минимального расстояния циклического кода, заданного своим порождающим многочленом, путем полного перебора по всем кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина , задаваемая при построении порождающего многочлена;
- Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ. Провести замеры времени работы реализованного алгоритма декодирования;
- [Бонус] Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
- С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до ошибок. Может ли БЧХ-код исправить больше, чем ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем ?
- Составить отчет в формате PDF обо всех проведенных исследованиях.
Рекомендации по выполнению задания
- Для реализации операций умножения и деления ненулевых элементов в поле удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента : . Тогда произведение двух элементов поля и равно . Аналогично частное этих двух элементов равно . Для быстрого перехода от десятичного представления элементов поля к степенному и обратно удобно завести таблицу размера . В первой колонке этой таблицы в позиции будет находится число , а во второй колонке в позиции — значение .
- Для построения таблицы соответствий между десятичным и степенным представлением элементов в поле , а также на этапе выбора нулей БЧХ-кода необходимо иметь некоторый примитивный элемент поля . Найти все примитивные элементы поля можно полным перебором. Однако, в случае построения поля как фактор-кольца , где в качестве выступает примитивный полином поля степени , элемент (в десятичном представлении равен 2) гарантированно является примитивным элементом поля. Это свойство теряется при использовании в качестве произвольного неприводимого многочлена степени .
- При реализации алгоритмов задания рекомендуется, помимо прочего, использовать следующие проверки на корректность:
- порождающий полином БЧХ-кода должен быть делителем многочлена (иначе код не будет циклическим);
- произвольное кодовое слово БЧХ-кода должно делиться без остатка на порождающий многочлен кода , а также обращаться в ноль на нулях кода (все синдромы кодового слова равны нулю);
- минимальный многочлен для элемента , вычисляемый как многочлен с корнями , должен иметь коэффициенты из ;
- минимальное кодовое расстояние БЧХ-кода , найденное полным перебором, должно быть не меньше, чем параметр на этапе построения порождающего многочлена БЧХ-кода .
Оформление задания
Выполненное задание с отчетом и всеми исходными кодами необходимо прислать преподавателю. Большая просьба строго следовать указанным ниже прототипам реализуемых функций.
Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля |
---|
pm = gf_gen_pow_matrix(pp) |
ВХОД |
pp — примитивный многочлен в поле степени , десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем , первый разряд соответствует старшей степени полинома; |
ВЫХОД |
pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу , матрица размера , в которой в первой колонке в позиции стоит степень , а во второй колонке в позиции стоит значение . |
Суммирование в |
---|
res = gf_sum(X, Y) — поэлементное суммирование двух матриц |
res = gf_sum(X, [], dim) — суммирование по заданной размерности |
ВХОД |
X, Y — матрица из элементов поля , каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем , первый разряд соответствует старшей степени полинома; |
dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1; |
ВЫХОД |
res — результат суммирования. |
Умножение/деление в поле |
---|
res = gf_prod(X, Y, pm) — поэлементное умножение двух матриц |
res = gf_divide(X, Y, pm) — поэлементное деление двух матриц |
ВХОД |
X, Y — матрица из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
res — результат операции, при делении на ноль соответствующий элемент равен NaN. |
Решение СЛАУ в поле методом Гаусса |
---|
x = gf_linsolve(A, b, pm) |
ВХОД |
A — квадратная матрица из элементов поля ; |
b — вектор-столбец из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности равен NaN. |
Поиск всех примитивных элементов поля |
---|
alpha = gf_primel(pm) |
ВХОД |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
alpha — найденные примитивные элементы, вектор-столбец десятичных чисел. |
Поиск минимального полинома в с заданным набором корней из |
---|
[p, x_coset] = gf_minpoly(x, pm, method) |
ВХОД |
x — вектор-столбец из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
method — (необязательный параметр) метод поиска, строка, возможные значения 'ls' (с помощью решения СЛАУ) и 'cosets' (с помощью построения циклотомических классов смежности), по умолчанию = 'cosets'; |
ВЫХОД |
p — найденный полином, десятичное число; |
x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля . |
Значение полинома из на элементе из |
---|
res = gf_polyval(p, X, pm) |
ВХОД |
p — полином из , вектор-столбец коэффициентов, начиная со старшей степени; |
X — вектор-столбец из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
res — значение полинома для всех элементов X. |
Систематическое кодирование циклическим кодом с заданным порождающим многочленом |
---|
V = cyclic_coding(U, g, n) |
ВХОД |
U — исходные сообщения для кодирования, вектор-столбец десятичных чисел; |
g — порождающий полином кода, десятичное число; |
n — длина кода, десятичное число; |
ВЫХОД |
V — закодированные сообщения, вектор-столбец десятичных чисел. |
Поиск порождающего многочлена для БЧХ-кода |
---|
[g, R, pm] = bch_genpoly(n, d) |
ВХОД |
n — длина кода, число вида ; |
d — минимальное расстояние кода, число; |
ВЫХОД |
g — порождающий полином кода, число; |
R — нули кода, вектор-столбец чисел; |
pm — матрица соответствия между десятичным и степенным представлением в поле . |
Декодирование БЧХ-кода |
---|
V = bch_decoding(W, R, pm, method) |
ВХОД |
W — набор принятых сообщений, вектор-столбец элементов из ; |
R — нули кода, вектор-столбец элементов из ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'pgz'; |
ВЫХОД |
V — декодированные сообщения, вектор-столбец чисел, в случае отказа от декодирования соответствующий элемент равен NaN. |
Вычисление минимального расстояния циклического кода путем полного перебора |
---|
d = cyclic_dist(g, n) |
ВХОД |
g — порождающий многочлен кода, десятичное число; |
n — длина кода, число вида ; |
ВЫХОД |
d — минимальное расстояние кода, число. |