ПРИМЕР.В таблице задано представление поля GF(16) как расширение поля GF(2),построенное по примитивному полиному p(z) = z^4 + z + 1, в неё включены также минимальные полиномы GF(2) для всех элементов поля GF(16),где a=z - примитивный элемент GF(16).Заметим,что элементы B и B^2 для любых В имеют одинаковые минимальные полиномы над полем GF(2).
Представления поля GF(2^4).
───────────────────────────────────────────────────────────────────
В виде В виде В двоичном Минимальные степени многочлена виде полиномы
───────────────────────────────────────────────────────────────────
0 0 0 0 0 0
a^0 1 0 0 0 1 X + 1
a^1 z 0 0 1 0 X^4+X+1
a^2 z^2 0 1 0 0 X^4+X+1
a^3 z^3 1 0 0 0 X^4+X^3+X^2+X+1
a^4 z+1 0 0 1 1 X^4+X+1
a^5 z^2+z 0 1 1 0 X^2+X+1
a^6 z^3+z^2 1 1 0 0 X^4+X^3+X^2+X+1
a^7 z^3+z+1 1 0 1 1 X^4+X^3+1
a^8 z^2+1 0 1 0 1 X^4+X+1
a^9 z^3+z 1 0 1 0 X^4+X^3+X^2+X+1
a^10 z^2+z+1 0 1 1 1 X^2+X+1
a^11 z^3+z^2+z 1 1 1 0 X^4+X^3+1
a^12 z^3+z^2+z+1 1 1 1 1 X^4+X^3+X^2+X+1
a^13 z^3+z^2+1 1 1 0 1 X^4+X^3+1
a^14 z^3+1 1 0 0 1 X^4+X^3+1
───────────────────────────────────────────────────────────────────
Можно заметить,что элементы поля GF(2^4) в двоичном виде представляют собой не что иное,как остатки от деления 1 с i нулями на полином p(z) ,причём i соответствует показателю степени (a^i).Таким образом,эти элементы поля можно получить в РСЛОС с образующим полиномом p(z).
Путём подстановки в минимальном полиноме вместо фиктивной переменной X соответствующего элемента поля В в виде полинома,можно показать,что полученный таким образом полином делится без остатка на
p(z),т.е.f(B) = 0.
К О Д Ы Б Ч Х
Порождающий полином для исправляющего две ошибки кода БЧХ длины 15
получается следующим образом:
K(X) = HOK [f1(X),f3(X)] = HOK [X^4+X+1,X^4+X^3+X^2+X+1] =
X^8+X^7+X^6+X^4+1.
n = 15, p = 8, k = n - p = 15 - 8 = 7.
Пусть S = 3 :
K(X) = HOK [f1(X),f3(X),f5(X)] = (X^4+X+1)*(X^4+X^3+X^2+X+1)*
*(X^2+X+1)=X^10+X^8+X^5+X^4+X^2+X+1.
Получился порождающий полином (15,5) - кода БЧХ,исправляющего три ошибки.
Пусть S = 4 :
K(X) = HOK [f1(X),f3(X),f5(X),f(7)] = (X^4+X+1)*(X^4+X^3+X^2+X+1)*
*(X^2+X+1)*(X^4+X^3+1)=X^14+X^13+X^12+X^11+X^10+X^9+X^8+X^7+
+X^6+X^5+X^4+X^3+X^2+X+1.
Получился порождающий полином (15,1) - кода БЧХ.Это простой код с повторением,исправляющий семь ошибок (при S = 5,6,7 - получается такой же полином).
Итак,рассмотрим построение кодов БЧХ с d min = 5,исправляющих двухразрядные ошибки.Образующий полином кодов БЧХ имеет следующий вид:
G(X) = G1(X)*G3(X), где G1(X),G3(X) - неприводимые полиномы.
Полиномы G1(X) и G3(X) выбираются таким образом,чтобы при одноразрядной ошибке синдром S3,соответствующий остатку от деления считанного слова на G3(X),равнялся S1^3,соответствующему остатку от деления считанного слова на G1(X).
Тогда при наличии двухразрядной ошибки в слове
S1i + S1j = S1, S3i + S3j = S3, где S1i,S1j,S3i,S3j - синдромы,соответствующие одиночным ошибкам в
i-м и j-м разрядах по модулю G1(X) и G3(X),соответственно.Подставляя в это выражение значения S3i = S1i^3 и S3j = S1j^3,получим
S1i + S1j = S1, S1i^3 + S1j^3 = S3.
Решение этой системы двух уравнений с двумя неизвестными позволяет определить синдромы и,следовательно,номера каждого из двух отказавших разрядов.При возникновении одиночной ошибки S1^3 = S3,и по значению S1 определяется положение ошибочного символа.
Аналогичные рассуждения справедливы также для кодов БЧХ,исправляющих S > 2 ошибок.
Ц И К Л И Ч Е С К И Е К О Д Ы , И С П Р А В Л Я Ю Щ И Е
П А К Е Т Ы О Ш И Б О К .
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.