Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
h --- 1, то соответствующий БЧХ-код называется ЬЧХ-хоФш в узком смысле.
Если п - цт - 1, то соответствующий БЧХ-код называется примитивным. Если
rt ц- 1, то
ЬЧХ-код длины п над нолем Fg называется кодом Рида - Соломона. .
9-45. Теорема. Минимальное расстояние БЧХ-кода с кон-('тРУктивным
расстоянием d не меньше, чем d.
Доказательство. БЧХ-код совпадает с нуль-пространством п Р о в ерочной
матрицы
сТО a2h . . . сс(л"-Бл
ыо
Гл. 9. Приложения конечных полей
NrtNfi4J ЩбУ^нн i ;
I • ((- .vW I ¦-¦ х-Г'ПШщ- |ПИШ'*Ч11УГ|1',' n.Vnl %
•кажем, что любые d - 1 столбцов этой матрицы линейно н#: зависимы. Если
мы рассмотрим определитель для любых d -¦ различных столбцов матрицы //,
то получим
а!пъ
оЛ"
а" п><.
Р <* Р
awd-l
а
а
<й-М-i?)*
а
а
- LAr
(W-rf-
1
а'Л
J
± J <*
I
i
i.
p >
i
a
о
a
ft
'V
Л
S'
Э,
. ->N i ;,v
i
ft
О 5 "
'•+'d-i> n ("0 -
1 - / ^/^n- i
. Ч Ц.
Следовательно, минимальное расстояние этого кода не меныгцЦ чем с/,
9.46. Пример. Пусть /?йп (х) х4 -! х -}- 1 - минимальны^ многочлен над
полем Г-> для примитивного элемента а б ft Представим степени об, 0 <, *
-С И, в виде линейных комбинр ций элементов I, а, а2, <Д и получим, таким
образом, проверок ную матрицу Н для кода, эквивалентного (15,11)-коду
Хэмминг!
1
О
0
1
/1 0 0 0 I 0 0 1 ) 0 1 0 1
и 1 0 I 0 0 1 I 0 1 0 1 1 1 1
Я - 1 о 0 1 0 0 I I 0 1 0 1 I
1
\° 0 0 1 0 0 i 1 0 1 0 1 1
(tm) {! сх а2 а3 гх4 а5 ае ап сх8 а9 а1й а11 а12
а-ы
Ч
0
1 1
• "Й-
сс14),
•*!
/lV.
код в узкд
Этот код можно также рассматривать как
смысле над нолем (р2 с конструктивным расстоянием d -- 3 (зЙ метим, что
элемент а8 также является корнем многочлена m*1) (х| Минимальное
расстояние этого кода также равно 3, поэтому может исправлять одну
ошибку. Для того чтобы декодировав
полученный вектор v ? Гь нам надо найтн синдром S (v) % - Иvr. В данном
случае для циклического (15Д1)-кода этот сн| дром определяется
разложением элемента v (ос) в базисе |К а2, а3). Чтобы получить его,
разделим v (х) на tnS^ (х). ПустМ скажем, о (х) а (х) rrdl) (х) |- г
(лг), где deg (г (г)) < 4; v (а) г (а), так что компоненты синдрома
равняются циентам многочлена г (ж),
Например, пусть
. v - 0 1 0 1 10 0 0 10 1 1 10 1,
TOR
> .
р
2. Циклические коды
6)
то гдг
t Ь| |SVV<4MAUd •
t i'hW *^'.^~i~i~*~i~i~i~i~i~i~i~i~< rfj I |V^|V| J
¦...............................................¦- I yj .*
411 <. И ЬЧ frrtr-l ^+Ь->3 < рУйЦ РД { Л лК'.*
л "X чпнччЧ -'Wsrt rJwaV
Г (*1
х и. следовател ьно
5 (У) - ЯVT (I 1 0 0)
VI
а"
/|a,.iее, нам надо найти вектор ошибки е веса w (е) т;б !, имеющий тот же
самый синдром_ Для этого мы должны определить /, 0 -С .ц j .ш 14, такое,
что об ^ Яу'Ч В нашем случае / --- 4, т. е. в'полученном векторе v
ошибочной является пятая координата таким обратом, переданное слово имело
вид
*
w О I 0 1 0000 10 1110 1.
I I ы*
/
г
f _
..-1
Притер, Пусть q 2, л - 15f d - 4, Тогда многочлен 1 является неприводимым
иад нолем Г2, а его корпи - оимнтиапые элементы поля Ты. Еслн а - один нз
этих корней,
т
то "о также является корнем этого многочлена, а а
3
А
А
О
>**!
корень
многочлена х* ¦+¦ хх -г .v* 4- т Э !. Тогда БЧХ-код в узком
I *
смысле с конструктивным расстоянием d ~ 4 может порождаться
многочленом
х) (х
А
X
1) (х
X
X
Л
х 't-
этот многочлен будет также порождающим для БЧХ-кода с конструктивным
расстоянием d 5, так как а4 также является корнем многочлена х* -f- х -f
1. Размерность этого кода равна 15 - ¦ (ley (g (х)) 1, Этот код уже
был детально изучен в примере 9,43, П
БЧХ-коды важны ввиду того, что для любого положительного целого числа d
можно построить БЧХ-код с минимальным расстоянием, не меньшим чем. d. Для
того чтобы получить БЧХ-код о большим минимальным расстоянием, мы должны
увеличить его длину п и, следовательно, степень т расширения поля [F^m
над полем Fq, БЧХ-код с конструктивным расстоянием d > 21 + 1 будет
исправлять t ошибок (и, разумеется, любое меньшее число ошибок), но в то
же время дли того, чтобы получить код с таким кодовым расстоянием, мы
должны использовать кодовые слова
большей длины.
Опишем теперь алгоритм декодирования ВЧХ-юхЪж Обозначим через w (х), v
{.*) н е (х) соответственно пере/хаваемый кодовый многочлен, принимаемый
многочлен и многочлен ошибок; тогда 0 41 w (х) i е (т). Прежде всего нам
надо найти синдром век-
т0|> а у
Г П(-
S (v) = tfvT = (Sb, Sb+1,
Т
С, Я
^j ~ v (об) ~ w (об) -j- е (а') ~ е (а/), b О / дс) б -j(tm) d имеется г t
ошибок, то
2,
81
Гл. 9. Приложения конечных полей
....I ¦¦¦¦ ................
где av, .
а,
- различные элементы из {О, I, п - I}. Эл
менты гц - aGi Г f т называются локаторами ошибки, а зл
менты си ? -значениями ошибки. Таким образом, для си
дрома вектора v получаем формулу
Sf ^ е (У) = ? ац1?
(^¦1
Ь .< / < Ь -f (1-2
Учитывая правила вычисления в поле F"m, приходим к pasei ствам
Sf
'Г \ q
~л / CiW
\/=Ы
S С'Д
1.^1
V
Н
I
1 Cirf?
