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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{Main|Практикум на ЭВМ (317)}} {{stop|Внимание! Задание находится в стадии разработки. Просьба не приступать ...)
(релиз)
 
(8 промежуточных версий не показаны.)
Строка 1: Строка 1:
{{Main|Практикум на ЭВМ (317)}}
{{Main|Практикум на ЭВМ (317)}}
-
 
-
{{stop|Внимание! Задание находится в стадии разработки. Просьба не приступать к выполнению задания до тех пор, пока это предупреждение не будет удалено.}}
 
__TOC__
__TOC__
'''Начало выполнения задания''': 26 апреля 2014 г.<br>
'''Начало выполнения задания''': 26 апреля 2014 г.<br>
-
'''Срок сдачи''': {{важно|11 мая 2013 г. (воскресенье), 23:59.}}
+
'''Срок сдачи''': {{важно|11 мая 2014 г. (воскресенье), 23:59.}}
Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Строка 13: Строка 11:
=== Задача помехоустойчивого кодирования ===
=== Задача помехоустойчивого кодирования ===
-
Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины <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> ошибок.
+
Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При ''блоковом'' кодировании входящий поток информации разбивается на блоки фиксированной длины <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\in\{0,1\}^n</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)-линейного циклического блокового кода ===
=== Кодирование с помощью (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>\{0,1\}^n</tex> с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем <tex>\mathbb{F}_2</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>v(x)</tex> могут быть представлены как <tex>g(x)q(x)</tex>, где <tex>q(x)</tex> — некоторый полином степени, не превышающей <tex>k-1</tex>;
# Полином <tex>g(x)</tex> является делителем полинома <tex>x^n-1</tex>.
# Полином <tex>g(x)</tex> является делителем полинома <tex>x^n-1</tex>.
Такой полином <tex>g(x)</tex> называется ''порождающим полиномом циклического кода''. Любой полином, являющийся делителем <tex>x^n-1</tex>, является порождающим для некоторого циклического кода.
Такой полином <tex>g(x)</tex> называется ''порождающим полиномом циклического кода''. Любой полином, являющийся делителем <tex>x^n-1</tex>, является порождающим для некоторого циклического кода.
Строка 28: Строка 26:
=== Коды БЧХ: кодирование ===
=== Коды БЧХ: кодирование ===
-
Полином <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>m_{\alpha}(x)\in \mathbb{F}_2[x]</tex> называется ''минимальным полиномом'' для элемента <tex>\alpha\in \mathbb{F}_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>\{\alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}\}</tex>.
-
Данный набор элементов из поля <tex>GF(2^l)</tex> называется ''циклотомическим классом'' смежности для элемента <tex>\alpha</tex>. Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином
+
Данный набор элементов из поля <tex>\mathbb{F}_2^l</tex> называется ''циклотомическим классом'' смежности для элемента <tex>\alpha</tex>. Количество элементов в смежном классе либо равно <tex>l</tex>, либо является делителем <tex>l</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>\prod_{i=0}^q(x+\alpha^{2^i}) = x^{q+1}+\lambda_qx^q+\dots+\lambda_1x + \lambda_0</tex>
-
имеет коэффициенты из <tex>GF(2)</tex> и является минимальным полиномом для <tex>\alpha</tex>, а также для всех элементов поля, входящих вместе с <tex>\alpha</tex> в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля <tex>\alpha</tex>:
+
имеет коэффициенты из <tex>\mathbb{F}_2</tex> и является минимальным полиномом для <tex>\alpha</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>m_{\alpha}(x)</tex> путем перемножения многочленов <tex>x+\alpha^{2^i}</tex> для всех <tex>i=0,\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>n=2^l-1</tex>, <tex>t\le [(n-1)/2]</tex>. Тогда ''кодом БЧХ'' называется (n,k)-линейный циклический код, в котором порождающий многочлен <tex>g(x)</tex> определяется как минимальный многочлен для элементов <tex>\alpha,\alpha^2,\dots,\alpha^{2t}</tex> из поля <tex>\mathbb{F}_2^l</tex>, где <tex>\alpha</tex> — произвольный примитивный элемент поля <tex>\mathbb{F}_2^l</tex>. Набор элементов <tex>\alpha,\alpha^2,\dots,\alpha^{2t}</tex> называется ''нулями БЧХ-кода''. Можно показать, что минимальное кодовое расстояние кода БЧХ <tex>d</tex> не меньше, чем величина <tex>2t+1</tex>. В результате БЧХ-коды по построению способны исправлять не менее <tex>t</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>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_{\nu}}</tex> — полином ошибок, а <tex>j_1,\dots,j_{\nu}</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>\Lambda(z) = \prod_{i=1}^{\nu}(1+\alpha^{j_i}x) = \Lambda_{\nu}x^{\nu}+\dots+\Lambda_1x+1</tex>.
-
Данный полином имеет корни <tex>\alpha^{-j_i}</tex>. Можно показать, что коэффициенты полинома <tex>\Lambda(x)</tex> удовлетворяют следующей СЛАУ:
+
Данный полином имеет корни <tex>\alpha^{-j_i}</tex>. Можно показать, что коэффициенты полинома <tex>\Lambda(z)</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>\begin{bmatrix}s_1 & s_2 & \dots & s_{\nu}\\ s_2 & s_3 & \dots & s_{\nu+1}\\ \rule{0pt}{15pt}\dots & \dots & \dots & \dots \\ \rule{0pt}{15pt}s_{\nu} & s_{\nu+1} & \dots & s_{2\nu-1}\end{bmatrix}\begin{bmatrix}\Lambda_{\nu}\\ \Lambda_{\nu-1}\\ \rule{0pt}{15pt}\dots\\ \Lambda_1\end{bmatrix} = \begin{bmatrix}s_{\nu+1}\\ s_{\nu+2}\\ \rule{0pt}{15pt}\dots \\ s_{2\nu}\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>w(x)</tex> вычислить синдромы <tex>s_i=w(\alpha^i),\ i=1,\dots,2t</tex>. Если все <tex>s_i=0</tex>, то вернуть <tex>w(x)</tex> в качестве ответа;
-
# Найти количество допущенных ошибок <tex>t</tex> и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
+
# Найти количество допущенных ошибок <tex>\nu</tex> и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
-
# Найти все корни полинома <tex>\Lambda(x)</tex> путем полного перебора, по найденным корням вычислить номера позиций <tex>j_1,\dots,j_t</tex>, в которых произошли ошибки;
+
# Найти все корни полинома <tex>\Lambda(z)</tex> путем полного перебора, по найденным корням вычислить номера позиций <tex>j_1,\dots,j_{\nu}</tex>, в которых произошли ошибки;
-
# Исправить ошибки в позициях <tex>j_1,\dots,j_t</tex> путем инвертирования соответствующих битов в <tex>w(x)</tex>. Если после произведенного исправления <tex>w(x)</tex> не является кодовым словом (его синдромы не равны нулю), то вернуть отказ от декодирования.
+
# Исправить ошибки в позициях <tex>j_1,\dots,j_{\nu}</tex> путем инвертирования соответствующих битов в <tex>w(x)</tex>.
Различные алгоритмы декодирования БЧХ-кодов по-разному решают задачу на шаге 2 общего алгоритма декодирования. Рассмотрим две схемы декодирования.
Различные алгоритмы декодирования БЧХ-кодов по-разному решают задачу на шаге 2 общего алгоритма декодирования. Рассмотрим две схемы декодирования.
Строка 57: Строка 52:
==== Декодер PGZ (Peterson–Gorenstein–Zierler) ====
==== Декодер 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> уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования.
+
Данный декодер предполагает непосредственное решение СЛАУ (*). Основная трудность здесь — это определить количество фактически допущенных при передаче ошибок <tex>\nu</tex>. В декодере PGZ происходит перебор по всем значениям <tex>\nu</tex>, начиная с <tex>t</tex>. При текущем <tex>\nu</tex> делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее <tex>\nu</tex> признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то <tex>\Lambda_{\nu}=0</tex>, величина <tex>\nu</tex> уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования. Также отказ от декодирования выдаётся в случае, если после исправления синдромы <tex>\hat{v}(x)</tex> не равны нулю (кодовое слово не найдено).
-
==== Декодер BMA (Berlekamp–Massey Algorithm) ====
+
==== Декодер Euclid ====
-
Шаг 2 общего алгоритма декодирования может быть представлен как поиск для заданного набора синдромов <tex>s_1,\dots,s_{d-1}</tex> минимального <tex>t</tex> и набора <tex>\lambda_1,\dots,\lambda_t</tex>, удовлетворяющих следующей СЛАУ:
+
Рассмотрим ''синдромный полином'' вида <tex>S(z) = s_{2t}z^{2t}+s_{2t-1}z^{2t-1}+\dots+s_1z+1</tex>, где <tex>s_i</tex> — вычисленные ранее синдромы. Тогда можно показать, что <tex>S(z)</tex> и <tex>\Lambda(z)</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>.
+
:<tex>z^{2t+1}A(z) + S(z)\Lambda(z) = r(z)</tex>.
-
Матрица данной СЛАУ обладает структурой матрицы Тёплица. Поэтому для этой СЛАУ существует более эффективный [http://trsys.faculty.jacobs-university.de/files/IEE_bma.pdf алгоритм решения], чем общий алгоритм гауссовских исключений:
+
Здесь <tex>r(z)</tex> — некоторый многочлен из <tex>\mathbb{F}_2^l[x]</tex>, степень которого не превышает <tex>t</tex>. Решение данного уравнения <tex>A(z), \Lambda(z), r(z)</tex> для заданных многочленов <tex>z^{2t+1}</tex> и <tex>S(z)</tex> может быть найдено с помощью расширенного алгоритма Евклида. Здесь итерации алгоритма Евклида проводятся до тех пор, пока степень текущего остатка <tex>r(z)</tex> не станет меньше или равна <tex>t</tex>. Степень найденного <tex>\Lambda(z)</tex> равна количеству фактически допущенных при передаче ошибок <tex>\nu</tex>. Если количество корней у <tex>\Lambda(z)</tex> не совпадает с <tex>\nu</tex>, то выдаётся отказ от декодирования.
-
 
+
-
:<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>;
+
== Формулировка задания ==
== Формулировка задания ==
-
В задании выдается [[Media:Gf_primpoly.zip|список]] всех примитивных многочленов степени <tex>l</tex> для поля <tex>GF(2^l)</tex> для всех <tex>l=1,2,\dots,16</tex>.
+
В задании выдается [[Media:Gf_primpoly.zip|список]] всех примитивных многочленов степени <tex>l</tex> над полем <tex>\mathbb{F}_2</tex> для всех <tex>l=1,2,\dots,16</tex>.
-
# Реализовать основные операции в поле <tex>GF(2^l)</tex>: сложение, умножение, деление, решение СЛАУ, поиск примитивных элементов, вычисление значения многочлена из <tex>GF(2^l)[x]</tex> для заданного элемента поля. Реализовать поиск минимального многочлена из <tex>GF(2)[x]</tex> для заданного набора корней из поля <tex>GF(2^l)</tex> двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
+
# Реализовать основные операции в поле <tex>\mathbb{F}_2^l</tex>: сложение, умножение, деление, решение СЛАУ, поиск минимального многочлена из <tex>\mathbb{F}_2[x]</tex> для заданного набора корней из поля <tex>\mathbb{F}_2^l</tex>;
 +
# Реализовать основные операции для работы с многочленами из <tex>\mathbb{F}_2^l[x]</tex>: произведение многочленов, деление многочленов с остатком, расширенный алгоритм Евклида для пары многочленов, вычисление значения многочлена для набора элементов из <tex>\mathbb{F}_2^l</tex>;
# Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
# Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
-
# Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных <tex>n</tex> и <tex>d</tex>;
+
# Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных <tex>n</tex> и <tex>t</tex>;
-
# Построить графики зависимости скорости БЧХ-кода <tex>r=k/n</tex> от минимального кодового расстояния <tex>d</tex> для различных значений <tex>n</tex>. Какие значения <tex>d</tex> следует выбирать на практике для заданного <tex>n</tex>?
+
# Построить графики зависимости скорости БЧХ-кода <tex>r=k/n</tex> от количества исправляемых кодом ошибок <tex>t</tex> для различных значений <tex>n</tex>. Какие значения <tex>t</tex> следует выбирать на практике для заданного <tex>n</tex>?
-
# Реализовать процедуру вычисления истинного минимального расстояния циклического кода, заданного своим порождающим многочленом, путем полного перебора по всем <tex>2^k-1</tex> кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина <tex>d</tex>, задаваемая при построении порождающего многочлена;
+
# Реализовать процедуру вычисления истинного минимального расстояния циклического кода <tex>d</tex>, заданного своим порождающим многочленом, путем полного перебора по всем <tex>2^k-1</tex> кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина <tex>2t+1</tex>;
-
# Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ. Провести замеры времени работы реализованного алгоритма декодирования;
+
# Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ и на основе расширенного алгоритма Евклида. Провести сравнение двух методов декодирования по времени работы;
-
# '''[Бонус]''' Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
+
# С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до <tex>t</tex> ошибок. Может ли БЧХ-код исправить больше, чем <tex>t</tex> ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем <tex>t</tex>?
-
# С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до <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>\mathbb{F}_2^l</tex> удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента <tex>\alpha</tex>: <tex>\mathbb{F}_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>x^n-1</tex> (иначе код не будет циклическим);
#* произвольное кодовое слово БЧХ-кода <tex>v(x)</tex> должно делиться без остатка на порождающий многочлен кода <tex>g(x)</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>m_{\alpha}(x)</tex> для элемента <tex>\alpha\in \mathbb{F}_2^l</tex>, вычисляемый как многочлен с корнями <tex>\alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}</tex>, должен иметь коэффициенты из <tex>\mathbb{F}_2</tex>;
-
#* минимальное кодовое расстояние БЧХ-кода <tex>d_{min}</tex>, найденное полным перебором, должно быть не меньше, чем параметр <tex>d</tex> на этапе построения порождающего многочлена БЧХ-кода <tex>g(x)</tex>;
+
#* минимальное кодовое расстояние БЧХ-кода <tex>d</tex>, найденное полным перебором, должно быть не меньше, чем величина <tex>2t+1</tex>.
-
#* в декодере BMA для бинарных БЧХ-кодов на всех чётных итерациях значение <tex>d</tex> должно быть равно нулю.
+
== Оформление задания ==
== Оформление задания ==
Строка 110: Строка 90:
{|class="standard"
{|class="standard"
-
!''Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля <tex>GF(2^l)</tex>''
+
!''Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля <tex>\mathbb{F}_2^l</tex>''
|-
|-
|pm = '''gf_gen_pow_matrix'''(pp)
|pm = '''gf_gen_pow_matrix'''(pp)
Строка 116: Строка 96:
|ВХОД
|ВХОД
|-
|-
-
|pp — примитивный многочлен в поле <tex>GF(2^l)</tex> степени <tex>l</tex>, десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома;
+
|pp — примитивный многочлен над полем <tex>\mathbb{F}_2</tex> степени <tex>l</tex>, десятичное число, двоичная запись которого соответствует коэффициентам полинома, первый разряд соответствует старшей степени полинома;
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу <tex>x</tex>, матрица размера <tex>2^l-1{\times}2</tex>, в которой в первой колонке в позиции <tex>i</tex> стоит степень <tex>j:\alpha^j=i</tex>, а во второй колонке в позиции <tex>i</tex> стоит значение <tex>\alpha^i</tex>.
+
|pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу <tex>\alpha</tex>, матрица размера <tex>2^l-1{\times}2</tex>, в которой в первой колонке в позиции <tex>i</tex> стоит степень <tex>j:\alpha^j=i</tex>, а во второй колонке в позиции <tex>i</tex> стоит значение <tex>\alpha^i</tex>.
|}
|}
Строка 126: Строка 106:
{|class="standard"
{|class="standard"
-
!''Суммирование в <tex>GF(2^l)</tex>''
+
!''Суммирование в <tex>\mathbb{F}_2^l</tex>''
|-
|-
|res = '''gf_sum'''(X, Y) — поэлементное суммирование двух матриц
|res = '''gf_sum'''(X, Y) — поэлементное суммирование двух матриц
Строка 134: Строка 114:
|ВХОД
|ВХОД
|-
|-
-
|X, Y — матрица из элементов поля <tex>GF(2^l)</tex>, каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома;
+
|X, Y — матрица из элементов поля <tex>\mathbb{F}_2^l</tex>, каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>\mathbb{F}_2</tex>, первый разряд соответствует старшей степени полинома;
|-
|-
|dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1;
|dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1;
Строка 146: Строка 126:
{|class="standard"
{|class="standard"
-
!''Умножение/деление в поле <tex>GF(2^l)</tex>''
+
!''Умножение/деление в поле <tex>\mathbb{F}_2^l</tex>''
|-
|-
|res = '''gf_prod'''(X, Y, pm) — поэлементное умножение двух матриц
|res = '''gf_prod'''(X, Y, pm) — поэлементное умножение двух матриц
Строка 154: Строка 134:
|ВХОД
|ВХОД
|-
|-
-
|X, Y — матрица из элементов поля <tex>GF(2^l)</tex>;
+
|X, Y — матрица из элементов поля <tex>\mathbb{F}_2^l</tex>;
|-
|-
-
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
|-
|-
|ВЫХОД
|ВЫХОД
Строка 166: Строка 146:
{|class="standard"
{|class="standard"
-
!''Решение СЛАУ <tex>A\vec{x}=\vec{b}</tex> в поле <tex>GF(2^l)</tex> методом Гаусса''
+
!''Решение СЛАУ <tex>A\vec{x}=\vec{b}</tex> в поле <tex>\mathbb{F}_2^l</tex> методом Гаусса''
|-
|-
|x = '''gf_linsolve'''(A, b, pm)
|x = '''gf_linsolve'''(A, b, pm)
Строка 172: Строка 152:
|ВХОД
|ВХОД
|-
|-
-
|A — квадратная матрица из элементов поля <tex>GF(2^l)</tex>;
+
|A — квадратная матрица из элементов поля <tex>\mathbb{F}_2^l</tex>;
|-
|-
-
|b — вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
+
|b — вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>;
|-
|-
-
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
|-
|-
|ВЫХОД
|ВЫХОД
Строка 186: Строка 166:
{|class="standard"
{|class="standard"
-
!''Поиск всех примитивных элементов поля <tex>GF(2^l)</tex>''
+
!''Поиск минимального полинома в <tex>\mathbb{F}_2[x]</tex> с заданным набором корней из <tex>\mathbb{F}_2^l</tex>''
|-
|-
-
|alpha = '''gf_primel'''(pm)
+
|[p, x_coset] = '''gf_minpoly'''(x, pm)
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+
|x — вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>;
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|alpha найденные примитивные элементы, вектор-столбец десятичных чисел.
+
|p найденный полином, бинарный вектор-строка;
 +
|-
 +
|x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>.
 +
|-
|}
|}
Строка 202: Строка 187:
{|class="standard"
{|class="standard"
-
!''Поиск минимального полинома в <tex>GF(2)[x]</tex> с заданным набором корней из <tex>GF(2^l)</tex>''
+
!''Значение полинома из <tex>\mathbb{F}_2^l[x]</tex> на наборе элементов из <tex>\mathbb{F}_2^l</tex>''
|-
|-
-
|[p, x_coset] = '''gf_minpoly'''(x, pm, method)
+
|res = '''gf_polyval'''(p, X, pm)
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|x вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
+
|p полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
|-
|-
-
|pm матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+
|X вектор-столбец из элементов поля <tex>\mathbb{F}_2^l</tex>;
|-
|-
-
|method (необязательный параметр) метод поиска, строка, возможные значения 'ls' (с помощью решения СЛАУ) и 'cosets' (с помощью построения циклотомических классов смежности), по умолчанию = 'cosets';
+
|pm матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|p найденный полином, бинарный вектор-столбец;
+
|res значение полинома для всех элементов X, вектор-столбец.
 +
|}
 +
 
 +
&nbsp;
 +
 
 +
{|class="standard"
 +
!''Умножение двух полиномов из <tex>\mathbb{F}_2^l[x]</tex>''
|-
|-
-
|x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля <tex>GF(2^l)</tex>.
+
|res = '''gf_polyprod'''(p1, p2, pm)
|-
|-
 +
|ВХОД
 +
|-
 +
|p1 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
 +
|-
 +
|p2 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
 +
|-
 +
|ВЫХОД
 +
|-
 +
|res — значение полинома p1(x)*p2(x), вектор-строка коэффициентов, начиная со старшей степени.
|}
|}
Строка 225: Строка 227:
{|class="standard"
{|class="standard"
-
!''Значение полинома из <tex>GF(2^l)[x]</tex> на элементе из <tex>GF(2^l)</tex>''
+
!''Деление двух полиномов из <tex>\mathbb{F}_2^l[x]</tex> с остатком''
|-
|-
-
|res = '''gf_polyval'''(p, X, pm)
+
|[q, r] = '''gf_polydiv'''(p1, p2, pm)
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|p — полином из <tex>GF(2^l)[x]</tex>, вектор-столбец коэффициентов, начиная со старшей степени;
+
|p1 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
|-
|-
-
|X вектор-столбец из элементов поля <tex>GF(2^l)</tex>;
+
|p2 полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
|-
|-
-
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|res значение полинома для всех элементов X.
+
|q результат деления, вектор-строка коэффициентов, начиная со старшей степени;
 +
|-
 +
|r — остаток от деления, вектор-строка коэффициентов, начиная со старшей степени.
 +
|}
 +
 
 +
&nbsp;
 +
 
 +
{|class="standard"
 +
!''Расширенный алгоритм Евклида для решения уравнения a(x)p1(x)+b(x)p2(x)= r(x) для двух полиномов p1, p2 из <tex>\mathbb{F}_2^l[x]</tex>''
 +
|-
 +
|[r, a, b] = '''gf_euclid'''(p1, p2, max_deg, pm)
 +
|-
 +
|ВХОД
 +
|-
 +
|p1 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
 +
|-
 +
|p2 — полином из <tex>\mathbb{F}_2^l[x]</tex>, вектор-строка коэффициентов, начиная со старшей степени;
 +
|-
 +
|max_deg — максимально допустимая степень остатка r(x), число;
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
 +
|-
 +
|ВЫХОД
 +
|-
 +
|r — остаток, вектор-строка коэффициентов, начиная со старшей степени;
 +
|-
 +
|a — коэффициент при p1(x), вектор-строка коэффициентов, начиная со старшей степени;
 +
|-
 +
|b — коэффициент при p2(x), вектор-строка коэффициентов, начиная со старшей степени.
|}
|}
Строка 253: Строка 283:
|U — исходные сообщения для кодирования, бинарная матрица размера <число_сообщений> x k;
|U — исходные сообщения для кодирования, бинарная матрица размера <число_сообщений> x k;
|-
|-
-
|g — порождающий полином кода, бинарный вектор-столбец длины m+1;
+
|g — порождающий полином кода, бинарный вектор-строка длины m+1;
|-
|-
|ВЫХОД
|ВЫХОД
Строка 263: Строка 293:
{|class="standard"
{|class="standard"
-
!''Поиск порождающего многочлена для БЧХ-кода''
+
!''Вычисление минимального расстояния циклического кода путем полного перебора''
|-
|-
-
|[g, R, pm] = '''bch_genpoly'''(n, d)
+
|d = '''cyclic_dist'''(g, n)
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|n длина кода, число вида <tex>2^l-1</tex>;
+
|g порождающий многочлен кода, бинарный вектор-строка;
|-
|-
-
|d минимальное расстояние кода, число;
+
|n длина кода;
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|g порождающий полином кода, бинарный вектор-столбец;
+
|d минимальное расстояние кода, число.
-
|-
+
-
|R — нули кода, вектор-столбец чисел;
+
-
|-
+
-
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>.
+
|}
|}
Строка 285: Строка 311:
{|class="standard"
{|class="standard"
-
!''Декодирование БЧХ-кода''
+
!''Поиск порождающего многочлена для БЧХ-кода''
|-
|-
-
|V = '''bch_decoding'''(W, R, pm, method)
+
|[g, R, pm] = '''bch_genpoly'''(n, t)
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|W набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
+
|n длина кода, число вида <tex>2^l-1</tex>;
|-
|-
-
|R нули кода, вектор-столбец элементов из <tex>GF(2^l)</tex>;
+
|t исправляемое число ошибок, число;
|-
|-
-
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>;
+
|ВЫХОД
|-
|-
-
|method (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'pgz';
+
|g порождающий полином кода, бинарный вектор-строка;
|-
|-
-
|ВЫХОД
+
|R — нули кода, вектор-столбец десятичных чисел;
|-
|-
-
|V декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN.
+
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>.
|}
|}
Строка 307: Строка 333:
{|class="standard"
{|class="standard"
-
!''Вычисление минимального расстояния циклического кода путем полного перебора''
+
!''Декодирование БЧХ-кода''
|-
|-
-
|d = '''cyclic_dist'''(g, n)
+
|V = '''bch_decoding'''(W, R, pm, method)
|-
|-
|ВХОД
|ВХОД
|-
|-
-
|g порождающий многочлен кода, бинарный вектор-столбец;
+
|W набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
|-
|-
-
|n длина кода, число вида <tex>2^l-1</tex>;
+
|R нули кода, вектор-столбец элементов из <tex>\mathbb{F}_2^l</tex>;
 +
|-
 +
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>\mathbb{F}_2^l</tex>;
 +
|-
 +
|method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'euclid', по умолчанию = 'euclid';
|-
|-
|ВЫХОД
|ВЫХОД
|-
|-
-
|d минимальное расстояние кода, число.
+
|V декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN.
|}
|}

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

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

Содержание

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

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

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

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

Данный набор элементов из поля \mathbb{F}_2^l называется циклотомическим классом смежности для элемента \alpha. Количество элементов в смежном классе либо равно l, либо является делителем l. Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином

\prod_{i=0}^q(x+\alpha^{2^i}) = x^{q+1}+\lambda_qx^q+\dots+\lambda_1x + \lambda_0

имеет коэффициенты из \mathbb{F}_2 и является минимальным полиномом для \alpha, а также для всех элементов поля, входящих вместе с \alpha в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля \alpha:

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

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

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

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

\Lambda(z) = \prod_{i=1}^{\nu}(1+\alpha^{j_i}x) = \Lambda_{\nu}x^{\nu}+\dots+\Lambda_1x+1.

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

\begin{bmatrix}s_1 & s_2 & \dots & s_{\nu}\\ s_2 & s_3 & \dots & s_{\nu+1}\\ \rule{0pt}{15pt}\dots & \dots & \dots & \dots \\ \rule{0pt}{15pt}s_{\nu} & s_{\nu+1} & \dots & s_{2\nu-1}\end{bmatrix}\begin{bmatrix}\Lambda_{\nu}\\ \Lambda_{\nu-1}\\ \rule{0pt}{15pt}\dots\\ \Lambda_1\end{bmatrix} = \begin{bmatrix}s_{\nu+1}\\ s_{\nu+2}\\ \rule{0pt}{15pt}\dots \\ s_{2\nu}\end{bmatrix}. (*)

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

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

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

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

Данный декодер предполагает непосредственное решение СЛАУ (*). Основная трудность здесь — это определить количество фактически допущенных при передаче ошибок \nu. В декодере PGZ происходит перебор по всем значениям \nu, начиная с t. При текущем \nu делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее \nu признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то \Lambda_{\nu}=0, величина \nu уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования. Также отказ от декодирования выдаётся в случае, если после исправления синдромы \hat{v}(x) не равны нулю (кодовое слово не найдено).

Декодер Euclid

Рассмотрим синдромный полином вида S(z) = s_{2t}z^{2t}+s_{2t-1}z^{2t-1}+\dots+s_1z+1, где s_i — вычисленные ранее синдромы. Тогда можно показать, что S(z) и \Lambda(z) удовлетворяют следующему уравнению:

z^{2t+1}A(z) + S(z)\Lambda(z) = r(z).

Здесь r(z) — некоторый многочлен из \mathbb{F}_2^l[x], степень которого не превышает t. Решение данного уравнения A(z), \Lambda(z), r(z) для заданных многочленов z^{2t+1} и S(z) может быть найдено с помощью расширенного алгоритма Евклида. Здесь итерации алгоритма Евклида проводятся до тех пор, пока степень текущего остатка r(z) не станет меньше или равна t. Степень найденного \Lambda(z) равна количеству фактически допущенных при передаче ошибок \nu. Если количество корней у \Lambda(z) не совпадает с \nu, то выдаётся отказ от декодирования.

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

В задании выдается список всех примитивных многочленов степени l над полем \mathbb{F}_2 для всех l=1,2,\dots,16.

  1. Реализовать основные операции в поле \mathbb{F}_2^l: сложение, умножение, деление, решение СЛАУ, поиск минимального многочлена из \mathbb{F}_2[x] для заданного набора корней из поля \mathbb{F}_2^l;
  2. Реализовать основные операции для работы с многочленами из \mathbb{F}_2^l[x]: произведение многочленов, деление многочленов с остатком, расширенный алгоритм Евклида для пары многочленов, вычисление значения многочлена для набора элементов из \mathbb{F}_2^l;
  3. Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
  4. Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных n и t;
  5. Построить графики зависимости скорости БЧХ-кода r=k/n от количества исправляемых кодом ошибок t для различных значений n. Какие значения t следует выбирать на практике для заданного n?
  6. Реализовать процедуру вычисления истинного минимального расстояния циклического кода d, заданного своим порождающим многочленом, путем полного перебора по всем 2^k-1 кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина 2t+1;
  7. Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ и на основе расширенного алгоритма Евклида. Провести сравнение двух методов декодирования по времени работы;
  8. С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до t ошибок. Может ли БЧХ-код исправить больше, чем t ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем t?
  9. Составить отчет в формате PDF обо всех проведенных исследованиях.

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

  1. Для реализации операций умножения и деления ненулевых элементов в поле \mathbb{F}_2^l удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента \alpha: \mathbb{F}_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. При реализации алгоритмов задания рекомендуется, помимо прочего, использовать следующие проверки на корректность:
    • порождающий полином БЧХ-кода должен быть делителем многочлена x^n-1 (иначе код не будет циклическим);
    • произвольное кодовое слово БЧХ-кода v(x) должно делиться без остатка на порождающий многочлен кода g(x), а также обращаться в ноль на нулях кода (все синдромы кодового слова равны нулю);
    • минимальный многочлен m_{\alpha}(x) для элемента \alpha\in \mathbb{F}_2^l, вычисляемый как многочлен с корнями \alpha,\alpha^2,\alpha^4,\dots,\alpha^{2^q}, должен иметь коэффициенты из \mathbb{F}_2;
    • минимальное кодовое расстояние БЧХ-кода d, найденное полным перебором, должно быть не меньше, чем величина 2t+1.

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

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

 

Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля \mathbb{F}_2^l
pm = gf_gen_pow_matrix(pp)
ВХОД
pp — примитивный многочлен над полем \mathbb{F}_2 степени l, десятичное число, двоичная запись которого соответствует коэффициентам полинома, первый разряд соответствует старшей степени полинома;
ВЫХОД
pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу \alpha, матрица размера 2^l-1{\times}2, в которой в первой колонке в позиции i стоит степень j:\alpha^j=i, а во второй колонке в позиции i стоит значение \alpha^i.

 

Суммирование в \mathbb{F}_2^l
res = gf_sum(X, Y) — поэлементное суммирование двух матриц
res = gf_sum(X, [], dim) — суммирование по заданной размерности
ВХОД
X, Y — матрица из элементов поля \mathbb{F}_2^l, каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем \mathbb{F}_2, первый разряд соответствует старшей степени полинома;
dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1;
ВЫХОД
res — результат суммирования.

 

Умножение/деление в поле \mathbb{F}_2^l
res = gf_prod(X, Y, pm) — поэлементное умножение двух матриц
res = gf_divide(X, Y, pm) — поэлементное деление двух матриц
ВХОД
X, Y — матрица из элементов поля \mathbb{F}_2^l;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
ВЫХОД
res — результат операции, при делении на ноль соответствующий элемент равен NaN.

 

Решение СЛАУ A\vec{x}=\vec{b} в поле \mathbb{F}_2^l методом Гаусса
x = gf_linsolve(A, b, pm)
ВХОД
A — квадратная матрица из элементов поля \mathbb{F}_2^l;
b — вектор-столбец из элементов поля \mathbb{F}_2^l;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
ВЫХОД
x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности A равен NaN.

 

Поиск минимального полинома в \mathbb{F}_2[x] с заданным набором корней из \mathbb{F}_2^l
[p, x_coset] = gf_minpoly(x, pm)
ВХОД
x — вектор-столбец из элементов поля \mathbb{F}_2^l;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
ВЫХОД
p — найденный полином, бинарный вектор-строка;
x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля \mathbb{F}_2^l.

 

Значение полинома из \mathbb{F}_2^l[x] на наборе элементов из \mathbb{F}_2^l
res = gf_polyval(p, X, pm)
ВХОД
p — полином из \mathbb{F}_2^l[x], вектор-строка коэффициентов, начиная со старшей степени;
X — вектор-столбец из элементов поля \mathbb{F}_2^l;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
ВЫХОД
res — значение полинома для всех элементов X, вектор-столбец.

 

Умножение двух полиномов из \mathbb{F}_2^l[x]
res = gf_polyprod(p1, p2, pm)
ВХОД
p1 — полином из \mathbb{F}_2^l[x], вектор-строка коэффициентов, начиная со старшей степени;
p2 — полином из \mathbb{F}_2^l[x], вектор-строка коэффициентов, начиная со старшей степени;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
ВЫХОД
res — значение полинома p1(x)*p2(x), вектор-строка коэффициентов, начиная со старшей степени.

 

Деление двух полиномов из \mathbb{F}_2^l[x] с остатком
[q, r] = gf_polydiv(p1, p2, pm)
ВХОД
p1 — полином из \mathbb{F}_2^l[x], вектор-строка коэффициентов, начиная со старшей степени;
p2 — полином из \mathbb{F}_2^l[x], вектор-строка коэффициентов, начиная со старшей степени;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
ВЫХОД
q — результат деления, вектор-строка коэффициентов, начиная со старшей степени;
r — остаток от деления, вектор-строка коэффициентов, начиная со старшей степени.

 

Расширенный алгоритм Евклида для решения уравнения a(x)p1(x)+b(x)p2(x)= r(x) для двух полиномов p1, p2 из \mathbb{F}_2^l[x]
[r, a, b] = gf_euclid(p1, p2, max_deg, pm)
ВХОД
p1 — полином из \mathbb{F}_2^l[x], вектор-строка коэффициентов, начиная со старшей степени;
p2 — полином из \mathbb{F}_2^l[x], вектор-строка коэффициентов, начиная со старшей степени;
max_deg — максимально допустимая степень остатка r(x), число;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
ВЫХОД
r — остаток, вектор-строка коэффициентов, начиная со старшей степени;
a — коэффициент при p1(x), вектор-строка коэффициентов, начиная со старшей степени;
b — коэффициент при p2(x), вектор-строка коэффициентов, начиная со старшей степени.

 

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

 

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

 

Поиск порождающего многочлена для БЧХ-кода
[g, R, pm] = bch_genpoly(n, t)
ВХОД
n — длина кода, число вида 2^l-1;
t — исправляемое число ошибок, число;
ВЫХОД
g — порождающий полином кода, бинарный вектор-строка;
R — нули кода, вектор-столбец десятичных чисел;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l.

 

Декодирование БЧХ-кода
V = bch_decoding(W, R, pm, method)
ВХОД
W — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n;
R — нули кода, вектор-столбец элементов из \mathbb{F}_2^l;
pm — матрица соответствия между десятичным и степенным представлением в поле \mathbb{F}_2^l;
method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'euclid', по умолчанию = 'euclid';
ВЫХОД
V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN.
Личные инструменты