Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 248

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 242 243 244 245 246 247 < 248 > 249 250 251 252 253 254 .. 371 >> Следующая

М
9.20, Пример. Пусть С - бинарный линейный (4, 2)-код с пЩ рождающей
матрицей О и проверочной матрицей Н:
В)
Ki
¦ш
1 О 1 О \ /1110
0;; Iо 1 1 ii* w-lo 1 о !/• а
Если получено слово у 1110, то можно просто посмотреть, гд|| оно
встречается в приводимой на следующей'странице таблиц^ смежных классов.
дпако для больших таблиц этот процесс требует большоЦ затраты времени.
Следуя алгоритму, найдем сначала S (У)1|
т

$
Линейные коды
XJCJi.
)
? •yw--.......
fi'iwwnM*rr'itrt iv'тда I пи
n e p e д а в a e ш а я и нфо p м а ц и я
тховые слова
1
другие смежные классы
00 10 01 11
0000 1010 0111 1101
1000 0010 1111 0101
0100 шо ООП 1001
0001 1011 оно 1100
лидеры
смежных
классов
/0 \
¦о ) 1
р0 / ! 1 \
Л
-¦О \
ч )
спи-
дромы
в нашем случае S (у) -¦ Ну
т
1
. Полагаем теперь, что ошибка,
наложившаяся на передававшееся кодовое слово, равняется
А ^ \
лидеру смежного класса 0100, имеющему тот же сп ядром ^ ^ ).
Тогда передававшееся кодовое слово скорее всего было словом 1010, а
сообщение, которое передавали, имело вид К). ?
В случае линейных кодов с большими параметрами становится практически
невозможным найти лидеров смежных классов. Таку например, линейный (50,
20)-код над молем ?.г имеет около 10s смежных классов, Таким образом,
чтобы преодолеть подобные а а т редане кия, н е обх од и м о етр о и т ь
с п е ц и а л ь и ы е коды.. Вначале отметим следующее обстоятельство.
0.21. Теорема. В случае бинарного линейного (п, к)-кода с проверочной
матрицей Н синдром получаемого вектора у равняется сумме столбцов матрицы
Н, которые соответствуют те At координатам передававшегося кодового слова
х, в которых появились
ошибка,
жазательствоПусть у б Ра - полученный вектор, у - с, х б С: тогда из
(9.2) получаем, что $ (у) - Неб Пусть И ц, ... - координаты с ошибками,
т. е. е 0 ... 01 *,0 ... 01^0... . 1огда S (у) = h(% + где h, означает
г-й столбец матрицы Н. ?
Вели все столбцы матрицы Н различны, то наличие единственной ошибки в i-й
координате полученного слова приводит к тому, '¦П'о $ (у) hj, и, таким
образом, одна ошибка, может быть исправлена, Локализация ошибок
упрощается при использован ни сле-Д У ю ще го класса к о дов.
9.22. Определение. Бинарный код Ст. длины я ~ 2т - 1, т 2, с проверочной
матрицей Н размера т X (2rn -- I) назы-
И*
596
Гл. 9, Приложения конечных полей
АЬйгКтУЛФ Ь
.irtVJWaWi'* i i i'M
s. o.flVS : y?\\'1
0 m
вается бинарным кодом Хэмминга, если столбцы матрицы представляют собой
двоичную запись чисел 1,2, .2Щ -- 1,
9.23. Лемма. Викарный код Сш является кодом размер ноет - т -¦¦- 1,
исправляющим одну ошибку,
Д о ка за тел ь ство. 11 о определению проверен! и о й матри цы кода Ст
ее ранг равняется т. Кроме того, любые два етолбц этой матрицы линейно
независимы. Так как матрица Н вме с любыми двумя столбцами содержит также
столбец, равный в; сумме, то но лемме 9.И минимальное расстояние кода Сш
н я е т с я 3. Таким об раз о м, в силу т е о р е м ы 9.12 к од С т я в л
я етсЛ кодом, исправляющим одну ошибку,
9.24, Пример. Пусть С3 является (7,4)-кодом Хэмминга с нро-верочиой
матрицей
/ООО! 1 1 1\
н (011001!
у
т
10 10 10 1
Если синдром полеченного слова у равняется, например, S (у)
(10 1)т, то отсюда мы заключаем, что имеется ошибка н пято! координате,
так как 101 является бинарной записью числа 5.
Коды Хэмминга можно также определить и для небинарнор случая, т. е, над
произвольным конечным нолем Fq. Здесь верочпяя матрица // имеет размер т
х 1 (qm- \),'(q- !)] столбцы этой матрицы попарно л и пенно независимы,
Така;
матрица определяет линейный {(qm - 1 );{q - 1), (gln - \)j(q
1) т.фкод с .минимальным расстоянием, равным 3.
Опишем теперь некоторые соотношения между длиной п кщ довых слов, числом
k информационных символов и минимальны! расстоянием dc линейного кода С
над полем ?ч.
9.25. Теорема (граница Хэмминга). Пусть С лем ?ч, исправляющий t ошибок и
содержащий М кодовых слов, а п - длина этого кода. Тогда я
код над пей
М
1) З
ft * *
1)' <9
п
Доказательство. Имеется ровно ( ) (q I)т векторов на|
полем длины п и веса т. Все шары радиуса i с центрами в кодей вых словах
попарно не пересекаются, и каждый из М шар о) содержит
п \
\ I
to - 1)"!
пл
Л * *
W
векторов пространства Fg, которое само содержит cf векторов
• 01
§ 1. Линейные коды 597
___J...................... II ч Ч| I ----- -----------
"^141*-Mihim i || i ^ i 11 .mjaAM ¦,,,,
. Теорема (граница Плоткнна). Для линейного (п, к)-кода С над полем с
минимальным расстоянием dc выполняется не-
clnql; 1 Н - О
6 " Д-i
и v?<i г) iP Q
F i ? •
Доказательство. Пусть 1 Д.. i х:, п таково, что С содержит кодовое слово
с ненулевой /-й координатой. Пусть О - под-пространство в С, состоящее из
всех кодовых слов с /-и координате) г равной 0, Тогда фактор пространство
С/В содержит q элементов, которые соответствуют q возможностям выбора ьй
ком-п о (¦ е н ты в к одо м с л ов е. 'Г а к им образом, и з р аве и ста
Предыдущая << 1 .. 242 243 244 245 246 247 < 248 > 249 250 251 252 253 254 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed