Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
.. ** _rf*"4 s .'lit
линейного кода L. . :;1
,1"
уь
3
/
С ч*
9.12. Теорема. Код С с минимальным расстоянием dc можетЩ исправлять t
ошибок, если ас Д 2/
Доказательство, Шар Bt (х) радиуса t с центром в точке х ?4§
? FJ состоит из всех векторов у ? таких, что d (х, у) -<у С у| Правило
декодирования в ближайшее кодовое слово гарантирует, что каждое
полученное в результате передачи слово, содержащее ? не более i ошибок,
должно лежать в таре радиуса i с центром в переданном кодовом слове. Для
того чтобы можно было исправить i ошибок, шары радиуса, i с центрами в
кодовых словах х должны не пересекаться. Если и ? Bt (х) и u ? Bt (у), х,
у ? С, х ф то
а (х, у) -< а (х, и) -f d (и, у) у 2Е
что противоречит тому, что dc Д 21 4- 1. П
9.13. Пример, Код из примера 9.1 имеет минимальное расстояние, dc =* 3 и,
следовательно, может исправлять одну ошибку.
Следующая лемма часто бывает полезна при определении минимального
расстояния кода.
9.14. Лемма. Для того чтобы линейный код С с проверочной матрицей И имел
минимальное расстояние dc Д s 4- 1, необходимо и достаточно, чтобы любые
s столбцов матрицы Н были л ине й н о не зав ис и м. ы.
Доказательство. Предположим, что найдутся s линейно за- | ацеимых
столбцов матрицы Н\ тогда Яст •¦=¦- 0 и w (с) д! s для некоторого с б С,
с Ф 0. Отсюда следует, что dG Д s. Аналогично |
§ i. Линейные коды 593
-II IЦ ¦ IjIjVrW
если любые .s столбцов матрицы // линейно независимы, то ие существует с
? С, с ^ 0, е весом w (с) <е $: следовательно,
dc > ^ - 1- ?
пнем теперь простои алгоритм декодирования линейных кодов. Пусть С
является лиггещгым (и, к)-кодом над нолем Fq.
Векторное пространство Fj/С состоит из всех смежных классов
а ; С -¦ {а + с [ с б С}, где а ? F?. Каждый смежный класс
содержит if векторов. Можно считать, что пространство FJ разбивается на
смежные классы по подпространству С, а именно
Г? = (а,0> г с) и (а<!> 4-С) и... и (aw 4 С),
где а11)1 О и s qn'~"k - I. Вектор у принятого сообщения
должен лежать в одном из этих смежных классов, например в : С. Если
передаваемым кодовым еловом было с, то для вектора ошибок е получаем
равенство
е -- у с а(Л 4- z? а(;'> j- С
для некоторого х б С. Отсюда приходим к следующей схеме декодирования.
9,15. Декодирование линейных кодов. Еслн после передачи по.-!учен вектор
у, то осе возможные значения вектора ошибок е лежат в одном смежном
классе с вектором у, Наиболее вероятным вектором ошибок является вектор
е. имеющий минимальный вес среди всех векторов смежного класса,
содержащего вектор у,
'Тогда мы декодируем у как х - у е
Описанную выше процедуру можно реализовать с помощью алгоритма
декодирования по лидеру смежного класса.
9.16. Определение. Пусть С Fq - линейный (п., к}-код, и
пусть \t %/С - факторпространство пространства Гф Элемент минимального
веса в смежном классе а Д- С называется лидером смежного класса а -г С\
Если в смежном классе a -f С несколько векторов имеют минимальный вес, то
в качестве лидера смежного класса выбирается любой из них,
Пусть а<3Д аб> - лидеры смежных классов, отличных от С\
и пусть с(!> --- 0, все кодовые слова из С. Рас-
гм(ггрим следующую таблиду:
сп) с<2> . . , с?*И' ] строка кодовых слов
:|i!i 1-т,1! а*]>-г-с(?) ... а(!) -f
У
остальные смежные классы
>94 Гл, 9, Приложения конечных полей ,%
" г-г уву*д
Ec.ni принято слово у -- аП) -j- с(/"Е то получатель считает^ что вектор'
ошибок е совпадает с а(° - лидером соответствующего
смежного класса - и декодирует слово у как кодовое слово х = у __ е ---¦
с*Д Таким образом, у декодируется как коде" слово, стоящее в
приведенной'выше таблице в столбце, содер| жащем слово у. Смежный класс,
содержащий вектор у, можно orJ|| ределить с помощью так называемого
синдрома вектора у,
9,17. Определение. Пусть И - - проверочная матрица линейЦ
ного (п, ?)-кода С. Тогда вектор S (у) - Ну1' длины п - к нш зывается
синдромом .вектора у.
Щ
<&
3':<М
i&il
1
9.-18. Теорема. Если у. /. >"• Г", то
:• ->з
(О S (у) ~ 0 тогда и только тогда, когда у ? С;
(if) $ (у) S (г) тогда и только тогда, когда v 4- С ?Щ
г -}- С.
Доказательство, Пункт (i) немедленно следует из определен кода С через
матрицу Н. Дли доказательства п. (ii) заметим, чтвЦ равенство S (у) S (г)
имеет место тогда и только тогда,
Нут = НхТ или, что то же самое, когда // (у -- - г)1 0, т.
у - г б С. Последнее равносильно тому, что у ; С -- г 4- С.
Если е. ~ у - с, с б С, у ? fq. то
-п
м
•ГС
$ (у) - $ (с + е) - S (с) 4 S (е) ^ 5 (е), (9.
т. е. векторы у и е лежат в одном смежном классе. Лидер этог| смежного
класса имеет тот же синдром. Таким образом, полу| чаем следующий алгоритм
декодирования.
9.19. Алгоритм декодирования по лидеру смежного кдасс%
Пусть С ^ fq - линейный (п., &)-КОД, и пусть у - ПрИННТЦ вектор. Для того
чтобы исправить ошибки, имеющиеся в у, в числим $ (у) и найдем такой
лидер смежного класса е, еиндро!
которого равен $ (у). Тогда декодируем у как х у е. Здееф
х - кодовое слово, находящееся на минимальном расстоянии от у|
