Практикум на ЭВМ (317)/2013/Коды БЧХ
Материал из MachineLearning.
(→Формулировка задания) |
|||
(21 промежуточная версия не показана) | |||
Строка 1: | Строка 1: | ||
- | + | {{Main|Практикум на ЭВМ (317)/2012-2013}} | |
- | + | ||
- | {{Main|Практикум на ЭВМ (317)}} | + | |
__TOC__ | __TOC__ | ||
- | '''Начало выполнения задания''': | + | '''Начало выполнения задания''': 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>. | ||
+ | |||
+ | | ||
+ | |||
+ | Пусть <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>; | ||
== Формулировка задания == | == Формулировка задания == | ||
Строка 33: | Строка 92: | ||
== Рекомендации по выполнению задания == | == Рекомендации по выполнению задания == | ||
+ | # Для реализации операций умножения и деления ненулевых элементов в поле <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> должно быть равно нулю. | ||
== Оформление задания == | == Оформление задания == | ||
Строка 47: | Строка 114: | ||
|ВХОД | |ВХОД | ||
|- | |- | ||
- | |pp — примитивный многочлен в поле <tex>GF(2^l)</tex> степени <tex>l</tex>, десятичное число; | + | |pp — примитивный многочлен в поле <tex>GF(2^l)</tex> степени <tex>l</tex>, десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем <tex>GF(2)</tex>, первый разряд соответствует старшей степени полинома; |
|- | |- | ||
|ВЫХОД | |ВЫХОД | ||
Строка 147: | Строка 214: | ||
|ВЫХОД | |ВЫХОД | ||
|- | |- | ||
- | |p — найденный полином, | + | |p — найденный полином, бинарный вектор-столбец; |
|- | |- | ||
|x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля <tex>GF(2^l)</tex>. | |x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля <tex>GF(2^l)</tex>. | ||
Строка 164: | Строка 231: | ||
|p — полином из <tex>GF(2^l)[x]</tex>, вектор-столбец коэффициентов, начиная со старшей степени; | |p — полином из <tex>GF(2^l)[x]</tex>, вектор-столбец коэффициентов, начиная со старшей степени; | ||
|- | |- | ||
- | |X — | + | |X — вектор-столбец из элементов поля <tex>GF(2^l)</tex>; |
|- | |- | ||
|pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>; | |pm — матрица соответствия между десятичным и степенным представлением в поле <tex>GF(2^l)</tex>; | ||
Строка 178: | Строка 245: | ||
!''Систематическое кодирование циклическим кодом с заданным порождающим многочленом'' | !''Систематическое кодирование циклическим кодом с заданным порождающим многочленом'' | ||
|- | |- | ||
- | |V = '''cyclic_coding'''(U, g | + | |V = '''cyclic_coding'''(U, g) |
|- | |- | ||
|ВХОД | |ВХОД | ||
|- | |- | ||
- | |U — исходные сообщения для кодирования, | + | |U — исходные сообщения для кодирования, бинарная матрица размера <число_сообщений> x k; |
- | + | ||
- | + | ||
|- | |- | ||
- | | | + | |g — порождающий полином кода, бинарный вектор-столбец длины m+1; |
|- | |- | ||
|ВЫХОД | |ВЫХОД | ||
|- | |- | ||
- | |V — закодированные сообщения, | + | |V — закодированные сообщения, бинарная матрица размера <число_сообщений> x (k+m). |
|} | |} | ||
Строка 196: | Строка 261: | ||
{|class="standard" | {|class="standard" | ||
- | !''Поиск порождающего многочлена для БЧХ-кода | + | !''Поиск порождающего многочлена для БЧХ-кода'' |
|- | |- | ||
|[g, R, pm] = '''bch_genpoly'''(n, d) | |[g, R, pm] = '''bch_genpoly'''(n, d) | ||
Строка 208: | Строка 273: | ||
|ВЫХОД | |ВЫХОД | ||
|- | |- | ||
- | |g — порождающий полином кода, | + | |g — порождающий полином кода, бинарный вектор-столбец; |
|- | |- | ||
|R — нули кода, вектор-столбец чисел; | |R — нули кода, вектор-столбец чисел; | ||
Строка 224: | Строка 289: | ||
|ВХОД | |ВХОД | ||
|- | |- | ||
- | |W — набор принятых сообщений, | + | |W — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n; |
|- | |- | ||
|R — нули кода, вектор-столбец элементов из <tex>GF(2^l)</tex>; | |R — нули кода, вектор-столбец элементов из <tex>GF(2^l)</tex>; | ||
Строка 234: | Строка 299: | ||
|ВЫХОД | |ВЫХОД | ||
|- | |- | ||
- | |V — декодированные сообщения, | + | |V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN. |
|} | |} | ||
Строка 246: | Строка 311: | ||
|ВХОД | |ВХОД | ||
|- | |- | ||
- | |g — порождающий многочлен кода, | + | |g — порождающий многочлен кода, бинарный вектор-столбец; |
|- | |- | ||
|n — длина кода, число вида <tex>2^l-1</tex>; | |n — длина кода, число вида <tex>2^l-1</tex>; |
Текущая версия
Содержание |
Начало выполнения задания: 9 мая 2013 г.
Срок сдачи: 20 мая 2013 г. (понедельник), 23:59.
Программная среда для выполнения задания — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Необходимая теория
Задача помехоустойчивого кодирования
Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматического исправления ошибок, допущенных при передаче. При блоковом кодировании входящий поток информации разбивается на блоки фиксированной длины . Обозначим один такой блок через . Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодировать блок в некоторое кодовое слово большей длины путем добавления избыточности в передаваемые данные. Обозначим кодовое слово через , . Для кодирования всевозможных блоков необходимо использовать кодовых слов длины . Определим минимальное расстояние кода как минимальное хэммингово расстояние для всех различных пар кодовых слов. Назовём множество кодовых слов длины с минимальным расстоянием (n,k,d)-блоковым кодом, а величину — скоростью кода. При передаче по каналу с шумом кодовое слово превращается в принятое слово , которое, вообще говоря, отличается от . Далее алгоритм декодирования пытается восстановить переданное слово путем поиска среди всевозможных кодовых слов ближайшего к . Обозначим результат работы алгоритма декодирования через . На последнем этапе декодированное слово переводится в декодированное слово исходного сообщения . Очевидно, что (n,k,d)-блоковый код способен обнаруживать до ошибки и исправлять до ошибок.
Кодирование с помощью (n,k,d)-линейного циклического блокового кода
Множество с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов . (n,k,d)-блоковый код называется линейным, если множество его кодовых слов образует линейное подпространство размерности общего линейного пространства . Таким образом, для линейного кода произвольная линейная комбинация кодовых слов является кодовым словом. Минимальное кодовое расстояние для линейного кода определяется как минимальный хэммингов вес (количество ненулевых бит) среди ненулевых кодовых слов. (n,k,d)-линейный блоковый код называется циклическим, если любой циклический сдвиг кодового слова является кодовым словом. Поставим в соответствие произвольному вектору полином вида . Тогда можно показать, что для (n,k,d)-линейного циклического блокового кода найдется полином степени такой, что
- Все кодовые слова могут быть представлены как , где — некоторый полином степени ;
- Полином является делителем полинома .
Такой полином называется порождающим полиномом циклического кода. Любой полином, являющийся делителем , является порождающим для некоторого циклического кода.
Кодирование называется систематическим, если все биты исходного сообщения копируются в некоторые биты кодового слова . При систематическом кодировании обратный процесс преобразования из декодированного кодового слова в декодированное слово сообщения становится тривиальным. Для циклического кода, задаваемого порождающим полиномом , процесс систематического кодирования может быть реализован как
- .
Здесь через обозначена операция взятия остатка от деления многочлена на многочлен .
Коды БЧХ: кодирование
Полином называется минимальным полиномом для элемента , если он является неприводимым полиномом минимальной степени, для которого является корнем. В частности, минимальный полином для примитивного элемента называется примитивным полиномом. Можно показать, что корнями минимального полинома являются
- .
Данный набор элементов из поля называется циклотомическим классом смежности для элемента . Циклотомические классы, порожденные различными элементами поля, либо совпадают, либо не пересекаются. Можно показать, что полином
имеет коэффициенты из и является минимальным полиномом для , а также для всех элементов поля, входящих вместе с в один циклотомический класс. Отсюда выводится метод построения минимального полинома для заданного элемента поля :
- Построить циклотомический класс, порожденный элементом ;
- Найти коэффициенты полинома путем перемножения многочленов для всех , либо решить СЛАУ
- .
Пусть , . Тогда кодом БЧХ называется (n,k,d)-линейный циклический код, в котором порождающий многочлен определяется как минимальный многочлен для элементов из поля , где — произвольный примитивный элемент поля . Набор элементов называется нулями БЧХ-кода. Можно показать, что минимальное кодовое расстояние кода БЧХ не меньше, чем величина . В результате БЧХ-коды по построению способны исправлять не менее ошибок, где .
Коды БЧХ: декодирование
Поставим в соответствие позициям принятого слова элементы . При передаче по шумовому каналу кодовое слово переходит в слово , где — полином ошибок, а — позиции, в которых произошли ошибки. Назовем синдромами принятого сообщения значения полинома в нулях БЧХ-кода, т.е. . Если является кодовым словом, то все синдромы . Рассмотрим полином локаторов ошибок
- .
Данный полином имеет корни . Можно показать, что коэффициенты полинома удовлетворяют следующей СЛАУ:
- . (*)
Отсюда получаем следующую общую схему декодирования БЧХ-кода:
- Для принятого слова вычислить синдромы . Если все , то вернуть в качестве ответа;
- Найти количество допущенных ошибок и коэффициенты полинома локаторов ошибок путем решения СЛАУ (*);
- Найти все корни полинома путем полного перебора, по найденным корням вычислить номера позиций , в которых произошли ошибки;
- Исправить ошибки в позициях путем инвертирования соответствующих битов в . Если после произведенного исправления не является кодовым словом (его синдромы не равны нулю), то вернуть отказ от декодирования.
Различные алгоритмы декодирования БЧХ-кодов по-разному решают задачу на шаге 2 общего алгоритма декодирования. Рассмотрим две схемы декодирования.
Декодер PGZ (Peterson–Gorenstein–Zierler)
Данный декодер предлагает непосредственно решать СЛАУ (*). Основная трудность здесь — это определить количество допущенных при передаче ошибок . В декодере PGZ происходит перебор по всем значениям , начиная с максимального . При текущем делается попытка решить СЛАУ (*). Если матрица СЛАУ является невырожденной, то текущее признается количеством допущенных ошибок, а коэффициенты полинома локаторов ошибок находятся из решения СЛАУ. Если матрица СЛАУ является вырожденной, то величина уменьшается на единицу, и процесс повторяется. Если СЛАУ решить не удается ни на одной итерации, то выдается отказ от декодирования.
Декодер BMA (Berlekamp–Massey Algorithm)
Шаг 2 общего алгоритма декодирования может быть представлен как поиск для заданного набора синдромов минимального и набора , удовлетворяющих следующей СЛАУ:
- .
Матрица данной СЛАУ обладает структурой матрицы Тёплица. Поэтому для этой СЛАУ существует более эффективный алгоритм решения, чем общий алгоритм гауссовских исключений:
- ; //Инициализация
- для //Цикл по синдромам
- ;
- если , то ;
- иначе
- если , то
- ;
- ;
- иначе
- ;
- ;
- ;
- если , то
Формулировка задания
В задании выдается список всех примитивных многочленов степени для поля для всех .
- Реализовать основные операции в поле : сложение, умножение, деление, решение СЛАУ, поиск примитивных элементов, вычисление значения многочлена из для заданного элемента поля. Реализовать поиск минимального многочлена из для заданного набора корней из поля двумя способами: с помощью решения СЛАУ и с помощью построения циклотомических классов смежности. Провести временные замеры скорости работы для этих двух способов.
- Реализовать процедуру систематического кодирования для циклического кода, заданного своим порождающим многочленом;
- Реализовать процедуру построения порождающего многочлена для БЧХ-кода при заданных и ;
- Построить графики зависимости скорости БЧХ-кода от минимального кодового расстояния для различных значений . Какие значения следует выбирать на практике для заданного ?
- Реализовать процедуру вычисления истинного минимального расстояния циклического кода, заданного своим порождающим многочленом, путем полного перебора по всем кодовым словам. Привести пример БЧХ-кода, для которого истинное минимальное расстояние больше, чем величина , задаваемая при построении порождающего многочлена;
- Реализовать процедуру декодирования БЧХ-кода с помощью метода PGZ. Провести замеры времени работы реализованного алгоритма декодирования;
- [Бонус] Реализовать процедуру декодирования БЧХ-кода с помощью алгоритма Берлекемпа-Мэсси (BMA). Провести сравнение методов BMA и PGZ по времени работы;
- С помощью метода стат. испытаний реализовать процедуру оценки доли правильно раскодированных сообщений, доли ошибочно раскодированных сообщений и доли отказов от декодирования для БЧХ-кода. С помощью этой процедуры убедиться в том, что БЧХ-код действительно позволяет гарантированно исправить до ошибок. Может ли БЧХ-код исправить больше, чем ошибок? Как ведут себя характеристики кода при числе ошибок, превышающем ?
- Составить отчет в формате PDF обо всех проведенных исследованиях.
Рекомендации по выполнению задания
- Для реализации операций умножения и деления ненулевых элементов в поле удобно пользоваться представлением элементов поля как степеней некоторого примитивного элемента : . Тогда произведение двух элементов поля и равно . Аналогично частное этих двух элементов равно . Для быстрого перехода от десятичного представления элементов поля к степенному и обратно удобно завести таблицу размера . В первой колонке этой таблицы в позиции будет находится число , а во второй колонке в позиции — значение .
- Для построения таблицы соответствий между десятичным и степенным представлением элементов в поле , а также на этапе выбора нулей БЧХ-кода необходимо иметь некоторый примитивный элемент поля . Найти все примитивные элементы поля можно полным перебором. Однако, в случае построения поля как фактор-кольца , где в качестве выступает примитивный полином поля степени , элемент (в десятичном представлении равен 2) гарантированно является примитивным элементом поля. Это свойство теряется при использовании в качестве произвольного неприводимого многочлена степени .
- При реализации алгоритмов задания рекомендуется, помимо прочего, использовать следующие проверки на корректность:
- порождающий полином БЧХ-кода должен быть делителем многочлена (иначе код не будет циклическим);
- произвольное кодовое слово БЧХ-кода должно делиться без остатка на порождающий многочлен кода , а также обращаться в ноль на нулях кода (все синдромы кодового слова равны нулю);
- минимальный многочлен для элемента , вычисляемый как многочлен с корнями , должен иметь коэффициенты из ;
- минимальное кодовое расстояние БЧХ-кода , найденное полным перебором, должно быть не меньше, чем параметр на этапе построения порождающего многочлена БЧХ-кода ;
- в декодере BMA для бинарных БЧХ-кодов на всех чётных итерациях значение должно быть равно нулю.
Оформление задания
Выполненное задание с отчетом и всеми исходными кодами необходимо прислать преподавателю. Большая просьба строго следовать указанным ниже прототипам реализуемых функций.
Построение матрицы соответствия между десятичным и степенным представлением для всех элементов поля |
---|
pm = gf_gen_pow_matrix(pp) |
ВХОД |
pp — примитивный многочлен в поле степени , десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем , первый разряд соответствует старшей степени полинома; |
ВЫХОД |
pm — матрица соответствия между десятичным представлением и степенным представлением по стандартному примитивному элементу , матрица размера , в которой в первой колонке в позиции стоит степень , а во второй колонке в позиции стоит значение . |
Суммирование в |
---|
res = gf_sum(X, Y) — поэлементное суммирование двух матриц |
res = gf_sum(X, [], dim) — суммирование по заданной размерности |
ВХОД |
X, Y — матрица из элементов поля , каждый элемент представляет собой десятичное число, двоичная запись которого соответствует коэффициентам полинома над полем , первый разряд соответствует старшей степени полинома; |
dim — (необязательный параметр) номер размерности для суммирования, по умолчанию = 1; |
ВЫХОД |
res — результат суммирования. |
Умножение/деление в поле |
---|
res = gf_prod(X, Y, pm) — поэлементное умножение двух матриц |
res = gf_divide(X, Y, pm) — поэлементное деление двух матриц |
ВХОД |
X, Y — матрица из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
res — результат операции, при делении на ноль соответствующий элемент равен NaN. |
Решение СЛАУ в поле методом Гаусса |
---|
x = gf_linsolve(A, b, pm) |
ВХОД |
A — квадратная матрица из элементов поля ; |
b — вектор-столбец из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
x — решение СЛАУ, вектор-столбец из элементов поля, в случае вырожденности равен NaN. |
Поиск всех примитивных элементов поля |
---|
alpha = gf_primel(pm) |
ВХОД |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
alpha — найденные примитивные элементы, вектор-столбец десятичных чисел. |
Поиск минимального полинома в с заданным набором корней из |
---|
[p, x_coset] = gf_minpoly(x, pm, method) |
ВХОД |
x — вектор-столбец из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
method — (необязательный параметр) метод поиска, строка, возможные значения 'ls' (с помощью решения СЛАУ) и 'cosets' (с помощью построения циклотомических классов смежности), по умолчанию = 'cosets'; |
ВЫХОД |
p — найденный полином, бинарный вектор-столбец; |
x_coset — все корни минимального полинома (x + все смежные с x элементы), вектор-столбец из элементов поля . |
Значение полинома из на элементе из |
---|
res = gf_polyval(p, X, pm) |
ВХОД |
p — полином из , вектор-столбец коэффициентов, начиная со старшей степени; |
X — вектор-столбец из элементов поля ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
ВЫХОД |
res — значение полинома для всех элементов X. |
Систематическое кодирование циклическим кодом с заданным порождающим многочленом |
---|
V = cyclic_coding(U, g) |
ВХОД |
U — исходные сообщения для кодирования, бинарная матрица размера <число_сообщений> x k; |
g — порождающий полином кода, бинарный вектор-столбец длины m+1; |
ВЫХОД |
V — закодированные сообщения, бинарная матрица размера <число_сообщений> x (k+m). |
Поиск порождающего многочлена для БЧХ-кода |
---|
[g, R, pm] = bch_genpoly(n, d) |
ВХОД |
n — длина кода, число вида ; |
d — минимальное расстояние кода, число; |
ВЫХОД |
g — порождающий полином кода, бинарный вектор-столбец; |
R — нули кода, вектор-столбец чисел; |
pm — матрица соответствия между десятичным и степенным представлением в поле . |
Декодирование БЧХ-кода |
---|
V = bch_decoding(W, R, pm, method) |
ВХОД |
W — набор принятых сообщений, бинарная матрица размера <число_сообщений> x n; |
R — нули кода, вектор-столбец элементов из ; |
pm — матрица соответствия между десятичным и степенным представлением в поле ; |
method — (необязательный параметр) метод декодирования, строка, возможные значения 'pgz' и 'bma', по умолчанию = 'pgz'; |
ВЫХОД |
V — декодированные сообщения, бинарная матрица размера <число_сообщений> x n, в случае отказа от декодирования соответствующая строка состоит из элементов NaN. |
Вычисление минимального расстояния циклического кода путем полного перебора |
---|
d = cyclic_dist(g, n) |
ВХОД |
g — порождающий многочлен кода, бинарный вектор-столбец; |
n — длина кода, число вида ; |
ВЫХОД |
d — минимальное расстояние кода, число. |