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

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

(Различия между версиями)
Перейти к: навигация, поиск
м
Текущая версия (12:32, 29 августа 2013) (править) (отменить)
 
(25 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
{{stop|Формулировка задания находится в стадии разработки. Убедительная просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.}}
+
{{Main|Практикум на ЭВМ (317)/2012-2013}}
-
 
+
-
{{Main|Практикум на ЭВМ (317)}}
+
__TOC__
__TOC__
-
'''Начало выполнения задания''': 8 мая 2013 г.<br>
+
'''Начало выполнения задания''': 9 мая 2013 г.<br>
'''Срок сдачи''': {{важно|20 мая 2013 г. (понедельник), 23:59.}}
'''Срок сдачи''': {{важно|20 мая 2013 г. (понедельник), 23:59.}}
Строка 11: Строка 9:
== Необходимая теория ==
== Необходимая теория ==
-
=== Кодирование с помощью (n,k,d)-блоковых линейных циклических кодов ===
+
=== Задача помехоустойчивого кодирования ===
 +
 
 +
Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины <tex>k</tex>. Обозначим один такой блок через <tex>u\in\{0,1\}^k</tex>. Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок <tex>u</tex> в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через <tex>v\in\{0,1\}^n</tex>, <tex>n>k</tex>. Для кодирования всевозможных блоков <tex>u</tex> необходимо использовать <tex>2^k</tex> кодовых слов длины <tex>n</tex>. Определим минимальное расстояние кода <tex>d</tex> как минимальное хэммингово расстояние для всех различных пар кодовых слов. Назовём множество <tex>2^k</tex> кодовых слов длины <tex>n</tex> с минимальным расстоянием <tex>d</tex> ''(n,k,d)-блоковым кодом'', а величину <tex>r=k/n</tex> — ''скоростью кода''. При передаче по каналу с шумом кодовое слово <tex>v</tex> превращается в принятое слово <tex>w</tex>, которое, вообще говоря, отличается от <tex>v</tex>. Далее алгоритм декодирования пытается восстановить переданное слово <tex>v</tex> путем поиска среди всевозможных кодовых слов ближайшего к <tex>w</tex>. Обозначим результат работы алгоритма декодирования через <tex>\hat{v}</tex>. На последнем этапе декодированное слово <tex>\hat{v}</tex> переводится в декодированное слово исходного сообщения <tex>\hat{u}</tex>. Очевидно, что (n,k,d)-блоковый код способен обнаруживать до <tex>d-1</tex> ошибки и исправлять до <tex>[(d-1)/2]</tex> ошибок.
 +
 
 +
=== Кодирование с помощью (n,k,d)-линейного циклического блокового кода ===
 +
 
 +
Множество <tex>\{0,1\}^n</tex> с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов <tex>\{0,1\}</tex>. (n,k,d)-блоковый код называется ''линейным'', если множество его кодовых слов образует линейное подпространство размерности <tex>k</tex> общего линейного пространства <tex>\{0,1\}^n</tex>. Таким образом, для линейного кода произвольная линейная комбинация кодовых слов является кодовым словом. Минимальное кодовое расстояние <tex>d</tex> для линейного кода определяется как минимальный хэммингов вес (количество ненулевых бит) среди ненулевых кодовых слов. (n,k,d)-линейный блоковый код называется ''циклическим'', если любой циклический сдвиг кодового слова является кодовым словом. Поставим в соответствие произвольному вектору <tex>v=\{v_{n-1},v_{n-2},\dots,v_1,v_0\}\in\{0,1\}^n</tex> полином вида <tex>v(x)=v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+\dots+v_1x+v_0</tex>. Тогда можно показать, что для (n,k,d)-линейного циклического блокового кода найдется полином <tex>g(x)</tex> степени <tex>m=n-k</tex> такой, что
 +
# Все кодовые слова <tex>v(x)</tex> могут быть представлены как <tex>g(x)q(x)</tex>, где <tex>q(x)</tex> — некоторый полином степени <tex>k</tex>;
 +
# Полином <tex>g(x)</tex> является делителем полинома <tex>x^n-1</tex>.
 +
Такой полином <tex>g(x)</tex> называется ''порождающим полиномом циклического кода''. Любой полином, являющийся делителем <tex>x^n-1</tex>, является порождающим для некоторого циклического кода.
 +
 
 +
Кодирование называется ''систематическим'', если все биты исходного сообщения <tex>u</tex> копируются в некоторые биты кодового слова <tex>v</tex>. При систематическом кодировании обратный процесс преобразования из декодированного кодового слова <tex>\hat{v}</tex> в декодированное слово сообщения <tex>\hat{u}</tex> становится тривиальным. Для циклического кода, задаваемого порождающим полиномом <tex>g(x)</tex>, процесс систематического кодирования может быть реализован как
 +
:<tex>v(x) = x^mu(x) + \mathrm{mod}(x^mu(x), g(x))</tex>.
 +
Здесь через <tex>\mathrm{mod}(f(x), g(x))</tex> обозначена операция взятия остатка от деления многочлена <tex>f(x)</tex> на многочлен <tex>g(x)</tex>.
 +
 
 +
=== Коды БЧХ: кодирование ===
 +
 
 +
Полином <tex>m_{\alpha}(x)\in GF(2)[x]</tex> называется ''минимальным полиномом'' для элемента <tex>\alpha\in GF(2^l)</tex>, если он является неприводимым полиномом минимальной степени, для которого <tex>\alpha</tex> является корнем. В частности, минимальный полином для примитивного элемента <tex>\alpha</tex> называется ''примитивным полиномом''. Можно показать, что корнями минимального полинома <tex>m_{\alpha}(x)</tex> являются
 +
:<tex>\{\alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}\}</tex>.
 +
Данный набор элементов из поля <tex>GF(2^l)</tex> называется ''циклотомическим классом'' смежности для элемента <tex>\alpha</tex>. Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином
 +
:<tex>\prod_{i=1}^q(x+\alpha^{2^i}) = x^q+\lambda_{q-1}x^{q-1}+\dots+\lambda_1x + \lambda_0</tex>
 +
имеет коэффициенты из <tex>GF(2)</tex> и является минимальным полиномом для <tex>\alpha</tex>, а также для всех элементов поля, входящих вместе с <tex>\alpha</tex> в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля <tex>\alpha</tex>:
 +
# Построить циклотомический класс, порожденный элементом <tex>\alpha</tex>;
 +
# Найти коэффициенты полинома <tex>m_{\alpha}(x)</tex> путем перемножения многочленов <tex>x+\alpha^{2^i}</tex> для всех <tex>i=1,\dots,q</tex>, либо решить СЛАУ
 +
:<tex>\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}</tex>.
 +
 
 +
&nbsp;
 +
 
 +
Пусть <tex>n=2^l-1</tex>, <tex>d = 2t+1\le n</tex>. Тогда ''кодом БЧХ'' называется (n,k,d)-линейный циклический код, в котором порождающий многочлен <tex>g(x)</tex> определяется как минимальный многочлен для элементов <tex>\alpha,\alpha^2,\dots,\alpha^{d-1}</tex> из поля <tex>GF(2^l)</tex>, где <tex>\alpha</tex> — произвольный примитивный элемент поля <tex>GF(2^l)</tex>. Набор элементов <tex>\alpha,\alpha^2,\dots,\alpha^{d-1}</tex> называется ''нулями БЧХ-кода''. Можно показать, что минимальное кодовое расстояние кода БЧХ не меньше, чем величина <tex>d</tex>. В результате БЧХ-коды по построению способны исправлять не менее <tex>t</tex> ошибок, где <tex>t=[(d-1)/2]</tex>.
 +
 
 +
=== Коды БЧХ: декодирование ===
 +
 
 +
Поставим в соответствие позициям принятого слова <tex>w = (w_{n-1},\dots,w_0)</tex> элементы <tex>\alpha^{n-1},\dots,\alpha^0</tex>. При передаче по шумовому каналу кодовое слово <tex>v(x)</tex> переходит в слово <tex>w(x)=v(x)+e(x)</tex>, где <tex>e(x)=x^{j_1}+\dots+x^{j_t}</tex> — полином ошибок, а <tex>j_1,\dots,j_t</tex> — позиции, в которых произошли ошибки. Назовем ''синдромами'' принятого сообщения <tex>w(x)</tex> значения полинома <tex>w(x)</tex> в нулях БЧХ-кода, т.е. <tex>s_i=w(\alpha^i),\ i=1,\dots,2t</tex>. Если <tex>w(x)</tex> является кодовым словом, то все синдромы <tex>s_i=0</tex>. Рассмотрим ''полином локаторов ошибок''
 +
:<tex>\Lambda(x) = \prod_{i=1}^t(1+\alpha^{j_i}x) = \lambda_tx^t+\dots+\lambda_1x+1</tex>.
 +
Данный полином имеет корни <tex>\alpha^{-j_i}</tex>. Можно показать, что коэффициенты полинома <tex>\Lambda(x)</tex> удовлетворяют следующей СЛАУ:
 +
:<tex>\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}</tex>. (*)
 +
Отсюда получаем следующую общую схему декодирования БЧХ-кода:
 +
# Для принятого слова <tex>w(x)</tex> вычислить синдромы <tex>s_i=w(\alpha^i),\ i=1,\dots,d-1</tex>. Если все <tex>s_i=0</tex>, то вернуть <tex>w(x)</tex> в качестве ответа;
 +
# Найти количество допущенных ошибок <tex>t</tex> и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
 +
# Найти все корни полинома <tex>\Lambda(x)</tex> путем полного перебора, по найденным корням вычислить номера позиций <tex>j_1,\dots,j_t</tex>, в которых произошли ошибки;
 +
# Исправить ошибки в позициях <tex>j_1,\dots,j_t</tex> путем инвертирования соответствующих битов в <tex>w(x)</tex>. Если после произведенного исправления <tex>w(x)</tex> не является кодовым словом (его синдромы не равны нулю), то вернуть отказ от декодирования.
 +
 
 +
Различные алгоритмы декодирования БЧХ-кодов по-разному решают задачу на шаге 2 общего алгоритма декодирования. Рассмотрим две схемы декодирования.
 +
 
 +
==== Декодер PGZ (Peterson–Gorenstein–Zierler) ====
 +
 
 +
Данный декодер предлагает непосредственно решать СЛАУ (*). Основная трудность здесь — это определить количество допущенных при передаче ошибок <tex>t</tex>. В декодере PGZ происходит перебор по всем значениям <tex>t</tex>, начиная с максимального <tex>[(d-1)/2]</tex>. При текущем <tex>t</tex> делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее <tex>t</tex> признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то величина <tex>t</tex> уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования.
 +
 
 +
==== Декодер BMA (Berlekamp–Massey Algorithm) ====
-
=== Коды БЧХ: кодирование и декодирование ===
+
Шаг 2 общего алгоритма декодирования может быть представлен как поиск для заданного набора синдромов <tex>s_1,\dots,s_{d-1}</tex> минимального <tex>t</tex> и набора <tex>\lambda_1,\dots,\lambda_t</tex>, удовлетворяющих следующей СЛАУ:
 +
:<tex>\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}</tex>.
 +
Матрица данной СЛАУ обладает структурой матрицы Тёплица. Поэтому для этой СЛАУ существует более эффективный [http://trsys.faculty.jacobs-university.de/files/IEE_bma.pdf алгоритм решения], чем общий алгоритм гауссовских исключений:
-
=== Укороченные коды ===
+
:<tex>\Lambda(x):=1,\ B(x):=1,\ b:=1,\ m:=1,\ t:=0</tex>; ''//Инициализация''
 +
:'''для''' <tex>i=1,\dots,d-1</tex> ''//Цикл по синдромам''
 +
::<tex>d:=s_i+\sum_{j=1}^ts_{i-j}\lambda_{t+1-j}</tex>;
 +
::'''если''' <tex>d=0</tex>, '''то''' <tex>m:=m+1</tex>;
 +
::'''иначе'''
 +
:::'''если''' <tex>2t>i-1</tex>, '''то'''
 +
::::<tex>\Lambda(x):=\Lambda(x) - \frac{d}{b}x^mB(x)</tex>;
 +
::::<tex>m:=m+1</tex>;
 +
:::'''иначе'''
 +
::::<tex>B_1(x):=\Lambda(x)</tex>;
 +
::::<tex>\Lambda(x):=\Lambda(x)-\frac{d}{b}x^mB(x)</tex>;
 +
::::<tex>B(x):=B_1(x);\ b:=d;\ m:=1;\ t:=i-t</tex>;
== Формулировка задания ==
== Формулировка задания ==
Строка 23: Строка 82:
# Реализовать основные операции в поле <tex>GF(2^l)</tex>: сложение, умножение, деление, решение СЛАУ, поиск примитивных элементов, вычисление значения многочлена из <tex>GF(2^l)[x]</tex> для заданного элемента поля. Реализовать поиск минимального многочлена из <tex>GF(2)[x]</tex> для заданного набора корней из поля <tex>GF(2^l)</tex> двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
# Реализовать основные операции в поле <tex>GF(2^l)</tex>: сложение, умножение, деление, решение СЛАУ, поиск примитивных элементов, вычисление значения многочлена из <tex>GF(2^l)[x]</tex> для заданного элемента поля. Реализовать поиск минимального многочлена из <tex>GF(2)[x]</tex> для заданного набора корней из поля <tex>GF(2^l)</tex> двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
# Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
# Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
-
# Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных <tex>n</tex> и <tex>d</tex> с одновременным выбором нулей кода таким образом, чтобы значение <tex>k</tex> было максимальным. С помощью экспериментов определить, как сильно может меняться <tex>k</tex> в зависимости от выбора примитивного элемента - первого нуля кода для различных значений <tex>l,n,d</tex>;
+
# Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных <tex>n</tex> и <tex>d</tex>;
-
# Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ;
+
# Построить графики зависимости скорости БЧХ-кода <tex>r=k/n</tex> от минимального кодового расстояния <tex>d</tex> для различных значений <tex>n</tex>. Какие значения <tex>d</tex> следует выбирать на практике для заданного <tex>n</tex>?
 +
# Реализовать процедуру вычисления истинного минимального расстояния циклического кода, заданного своим порождающим многочленом, путем полного перебора по всем <tex>2^k-1</tex> кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина <tex>d</tex>, задаваемая при построении порождающего многочлена;
 +
# Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ. Провести замеры времени работы реализованного алгоритма декодирования;
# '''[Бонус]''' Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
# '''[Бонус]''' Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
-
# Провести экспериментальное исследование БЧХ-кода на модельных данных;
+
# С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до <tex>[(d-1)/2]</tex> ошибок. Может ли БЧХ-код исправить больше, чем <tex>[(d-1)/2]</tex> ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем <tex>[(d-1)/2]</tex>?
# Составить отчет в формате PDF обо всех проведенных исследованиях.
# Составить отчет в формате PDF обо всех проведенных исследованиях.
== Рекомендации по выполнению задания ==
== Рекомендации по выполнению задания ==
 +
# Для реализации операций умножения и деления ненулевых элементов в поле <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_{min}</tex>, найденное полным перебором, должно быть не меньше, чем параметр <tex>d</tex> на этапе построения порождающего многочлена БЧХ-кода <tex>g(x)</tex>;
 +
#* в декодере BMA для бинарных БЧХ-кодов на всех чётных итерациях значение <tex>d</tex> должно быть равно нулю.
== Оформление задания ==
== Оформление задания ==
Строка 45: Строка 114:
|ВХОД
|ВХОД
|-
|-
-
|pp — примитивный многочлен в поле <tex>GF(2^l)</tex> степени <tex>l</tex>, десятичное число;
+
|pp — примитивный многочлен в поле <tex>GF(2^l)</tex> степени <tex>l</tex>, десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома;
|-
|-
|ВЫХОД
|ВЫХОД
Строка 133: Строка 202:
!''Поиск минимального полинома в <tex>GF(2)[x]</tex> с заданным набором корней из <tex>GF(2^l)</tex>''
!''Поиск минимального полинома в <tex>GF(2)[x]</tex> с заданным набором корней из <tex>GF(2^l)</tex>''
|-
|-
-
|p = '''gf_minpoly'''(x, pm, method)
+
|[p, x_coset] = '''gf_minpoly'''(x, pm, method)
|-
|-
|ВХОД
|ВХОД
Строка 145: Строка 214:
|ВЫХОД
|ВЫХОД
|-
|-
-
|p — найденный полином, десятичное число.
+
|p — найденный полином, бинарный вектор-столбец;
 +
|-
 +
|x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля <tex>GF(2^l)</tex>.
 +
|-
|}
|}
Строка 159: Строка 231:
|p — полином из <tex>GF(2^l)[x]</tex>, вектор-столбец коэффициентов, начиная со старшей степени;
|p — полином из <tex>GF(2^l)[x]</tex>, вектор-столбец коэффициентов, начиная со старшей степени;
|-
|-
-
|X — матрица из элементов поля <tex>GF(2^l)</tex>;
+
|X — вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
|-
|-
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
Строка 173: Строка 245:
!''Систематическое кодирование циклическим кодом с заданным порождающим многочленом''
!''Систематическое кодирование циклическим кодом с заданным порождающим многочленом''
|-
|-
-
|V = '''cyclic_coding'''(U, g, n)
+
|V = '''cyclic_coding'''(U, g)
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|U — исходные сообщения для кодирования, вектор-столбец десятичных чисел;
+
|U — исходные сообщения для кодирования, бинарная матрица размера <число_сообщений> x k;
|-
|-
-
|g — порождающий полином кода, десятичное число;
+
|g — порождающий полином кода, бинарный вектор-столбец длины m+1;
-
|-
+
-
|n — длина кода, десятичное число;
+
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|V — закодированные сообщения, вектор-столбец десятичных чисел.
+
|V — закодированные сообщения, бинарная матрица размера <число_сообщений> x (k+m).
|}
|}
Строка 191: Строка 261:
{|class="standard"
{|class="standard"
-
!''Поиск порождающего многочлена для БЧХ-кода с максимизацией <tex>k</tex>''
+
!''Поиск порождающего многочлена для БЧХ-кода''
|-
|-
|[g, R, pm] = '''bch_genpoly'''(n, d)
|[g, R, pm] = '''bch_genpoly'''(n, d)
Строка 203: Строка 273:
|ВЫХОД
|ВЫХОД
|-
|-
-
|g — порождающий полином кода, число;
+
|g — порождающий полином кода, бинарный вектор-столбец;
|-
|-
|R — нули кода, вектор-столбец чисел;
|R — нули кода, вектор-столбец чисел;
Строка 219: Строка 289:
|ВХОД
|ВХОД
|-
|-
-
|W — набор принятых сообщений, вектор-столбец элементов из <tex>GF(2^l)</tex>;
+
|W — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
|-
|-
|R — нули кода, вектор-столбец элементов из <tex>GF(2^l)</tex>;
|R — нули кода, вектор-столбец элементов из <tex>GF(2^l)</tex>;
Строка 229: Строка 299:
|ВЫХОД
|ВЫХОД
|-
|-
-
|V — декодированные сообщения, вектор-столбец чисел, в случае отказа от декодирования соответствующий элемент равен NaN.
+
|V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN.
 +
|}
 +
 
 +
&nbsp;
 +
 
 +
{|class="standard"
 +
!''Вычисление минимального расстояния циклического кода путем полного перебора''
 +
|-
 +
|d = '''cyclic_dist'''(g, n)
 +
|-
 +
|ВХОД
 +
|-
 +
|g — порождающий многочлен кода, бинарный вектор-столбец;
 +
|-
 +
|n — длина кода, число вида <tex>2^l-1</tex>;
 +
|-
 +
|ВЫХОД
 +
|-
 +
|d — минимальное расстояние кода, число.
|}
|}

Текущая версия

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

Содержание

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

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

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

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

  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 обо всех проведенных исследованиях.

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

  1. Для реализации операций умножения и деления ненулевых элементов в поле GF(2^l) удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента \alpha: GF(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. Для построения таблицы соответствий между десятичным и степенным представлением элементов в поле GF(2^l), а также на этапе выбора нулей БЧХ-кода необходимо иметь некоторый примитивный элемент поля \alpha. Найти все примитивные элементы поля можно полным перебором. Однако, в случае построения поля GF(2^l) как фактор-кольца GF(2)[x]/f(x), где в качестве f(x) выступает примитивный полином поля GF(2^l) степени l, элемент x (в десятичном представлении равен 2) гарантированно является примитивным элементом поля. Это свойство теряется при использовании в качестве f(x) произвольного неприводимого многочлена степени l.
  3. При реализации алгоритмов задания рекомендуется, помимо прочего, использовать следующие проверки на корректность:
    • порождающий полином БЧХ-кода должен быть делителем многочлена x^n-1 (иначе код не будет циклическим);
    • произвольное кодовое слово БЧХ-кода v(x) должно делиться без остатка на порождающий многочлен кода g(x), а также обращаться в ноль на нулях кода (все синдромы кодового слова равны нулю);
    • минимальный многочлен m_{\alpha}(x) для элемента \alpha\in GF(2^l), вычисляемый как многочлен с корнями \alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}, должен иметь коэффициенты из GF(2);
    • минимальное кодовое расстояние БЧХ-кода d_{min}, найденное полным перебором, должно быть не меньше, чем параметр d на этапе построения порождающего многочлена БЧХ-кода g(x);
    • в декодере BMA для бинарных БЧХ-кодов на всех чётных итерациях значение d должно быть равно нулю.

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

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

 

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