Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 132
Текст из файла (страница 132)
Следующая лемма час!о бывает полезна прн определении минимального расстояния кода. 9.14. Лемма. Для того чтобы:г«нейный код С с проверочной мат«иней' Н «мел м«н«мальное расстояние г»с,з. х г 1, необхо. дилго «достатошо, чтобы люль!с х столбцов матрицы !! были линейно нехао«симы. д .. Пред ....
йдутся з л ейио за- висимых столбгцов матрицы Н; тогда Нет =: 9 и ш (с) < х для г! некоторого с Г С, с ~ О. Отсюда следует. что д, сь з. Аналогичио;, 5 >. Лияейвые коды сели л>обые х столбцов матрицы 1т лпиейяо иеззвисимы, то ис ,,цестиует с Е С. с чь О, с весом ш (с! .=., ес следовательно. !з Пикшем теперь простой алгоритм декодирования линейных к„лоз Пусть С является липейиым (и, я)-кодом иад полем Еч, 1)скгориое иростраиство К",>С сос>оит из всех смежных классов а С (а -'- с ~ с Е С), где а Е Ц.
Каждый смежный класс ;о,в рж>п >1 векторов. Можно считать, что пространство Г„раз- >-;цвз> гся па смежные классы по иодпрострзиству С, а именно Г" ,=(а' >+С)Ц(а!» Ф-С)!)... О (а" з С), >з> з»» О и з -- у" ' - — !. Вектор у прииятого сообщеиия ло.> к> и лежать в одном из згих смежиых классов, например » а"' С. Если передаваемы» ко,>овым словом оьшо с, то лля ш к. >р;> ошибок е по;гччзем равенство е==- у с--= а>м -- ара>'> 1- С ш которо>о г е С. Отснздз приходим к следую>цей схеме .>гк >лир>>взвив.
О.15. Декодирование лииейиых кодов. Если после передачи » >,» чея вектор у, то все возможные зизчеиия вектора ошибок е .и жз, в одном смежном классе с вектором у, Наиболее вероятиым иск>ором ошибок является вектор е, имеющий мииимальиый иес рс;ш всех векторов смежного класса, содержщцего вектор у. уоглз»ь> декодируем у как х — у — е.
Пппсзииую выше процедуру можно рез.>и>овзт> с помощью н. у пи>мо декодирования по лидеру смелея>мз к,ги>ти. 9.16. Определение. Пусть С с= Е," — линейный 1л, Й)-код, и и) г>ь 11'„"!С -- факториростраиство иростраиствз >т,". Элемент »шш»зльиого веса в смежном классе а > С иззывается лидером гз *ясно>к> класса а -' С. Если в смежном классе а -' С несколько з> к' оров имеют минимальный вес, то в качестве лидера смежш>го кл;шгз выбирается „иобой из иих. 11) г>ь аи>, ..., аы> — .тидеры смежиых классов, отличиых ог С, >гть си> -- О, с<'-'>, ..., с!ее) — все кодовые слова из С. Ряс- *' »о;ри» следующую >зблипу: с>'> с'"> ...
сге ); строка кодовых сл»в зо' ->- с » а>» . с<>> а>»-' с(ч) 1 остальные смсжиыс классы '. с"' аы> Л- сы> ... а>'> — к с! ~) ~ !'л. В. !!р>меженин коне н>мл нолей Если принято слово у а<'> -; с»>, то получатель считает что вектор' ошибок е совпадает с а<'> — лидером соответствующе смежного класса — н декодирует слово у как кодовое слово х --- у .— е — с»>. Таким образом, у декодируется как кодов слово, стоящее в приведенной выше таб>лице в сголбце, соде жащем слово у.
Смежный класс, содержащий вектор у, можно о ределить с помощью так называемого синдрома вектора у. 9.17. Определение. Пусть Н вЂ” проверочная матрица линейу ного (о, )е)-кода С. Тогда вектор 5 (у) Ну' длины л — й нае( зывается синс)ромом вектора у. 9.18. Теорема. Бо>и у, х Е Ке", ош (!) 5 (у) — 9 тогда и люлько тогда>, когда у р С; (») 5 (у) — 5 (х) тогда и толью> тогда, когда у >- С =',>! - в+С. Докааательс>нво. Пункт (>) немедленно следует из онределени кода С через матрицу Н.
Для доказательства и. (!!) заметим, ч равенство 5 (у) — 5 (х) имеет место тогда и только тогда, когд ', Чу: Нх~ или, что то же самое, когда Н (у — х) — 9, т. е г — х Е С. Последнее равносильно тому, что у С - х > С. Если е — у -- с, с е С, у 6 Ге, то 5(у) =- 5(с —;-е) = 5(с) 5(е) =- 5(е), (9. т. е. векторы у и е лежат в одном смежном классе.
Лидер это межного класса имеет тот же синдром. Таким образом, иолу, >аем следукнций алгоритм декодировапня. 9.!9. Алгоритм декодирования по лидеру смежного класса Пусть С е= Г", — - линейный (н, )е)-ко>с, и пусть у - — нриниты, вектор. Для того чтобы исправить ошибки, имекнциеся в у, в числим 5 (у) и найдем такой лидер смежного класса е, синдро которо>х> равен 5 (у).
Тогда декодируем у как х у — е. Здес' с — кодовое слово, находящееся на минимальном расстоянии от у' 9.20. Пример. Пусть С -- бинарный линейный (4, 2)-код с и,' оождак>щей матрицей 6 и проверочной матрнцей Н: Если получено слово у 11!1>, то можно просто посмотреть, гдв, оно встречается в приводимой на следую>цей странице таблиц, > межных классов.
Однако для больших таблиц этот процесс требует большо. затраты времени. (:ледуя ал> оритму, найдем сначала 5 (у)! з !. Лиж иные коли вяз передаваемая информапия 00 10 01 ОООО 1010 И)1 !! 1101 ~ ) !0) 1001 (, ) (,) 0 кодовые слова ! 1000 ОО)0 О)ОО 1!10 0011 ,по~не смежные классы 0001 ВП) И)О сои- дромм лидеры смсмимх ххэссов и!з а шин и случае 5 (у):х Нут ( ! ). Полагаем теперь, что ошибка, на,попавшаяся на передававшееся кодовое слово, равняется г!1 ли,сру смежного класса 0100, име>ощему тот же синдром ( й гда передававшееси кодовое слово скорее всего было сло- вом 1010, а сообщение, которое передавалп, имело аид 10.
В случае линейных кодов с большнмн параметрами стано- ашся практически невозможным найти лидеров смежных классов. Таь, например, линейный (50, 20)-код над полем,', нмес.г около 10" смежных классов. Таким образом, чтобы преодолеть подобнгяе з; труднения, необходимо строить специальные коды. Вначале огмс1им следукящее обстоятельство. й.21. Теорема. В случае бинарного линейного (и, й)-кода с про- еирочной магприцей Н синдром получаемого вектора у равняется сумме сгполбцое матрицы Н, ктнпорые соогпаепилпвуют тем коор- динатпм передававшегося кодового слова х, о которых пояеилиеь ыииоки, Л леазательеп1ео. Пусть у е 'г"и — полученный вектор, у х,; е, х Е С; тогда из (9.2) получаем, что 5 (у) — Не'.
Пусть 'р *',, ... — координаты с ошибками, т, е, е = 0 ... 0)пО ... 01нО,... Тогда 5 (у) =- )зп. )зц -г ..., где )з; означает )-й столбец матрицы Н. 1) 1'.ели все столбцы матрицы Н различны, то наличие единствен- ноп ошибки в (-й координате полчченного слова приводк1 к тому, ' о 'о (у) ==- пе, и, таким образом, одна ошибка может быть исправ- лена, у!окализацпя ошибок упрощается прн использовании следукицего класса колов. и 22.
Определение. Ьинарный код С длины и — 2'" — 1, "' -':: 2, с проверочной матрицей Н размера т ск (2'" — 1) назы- Гл 9. Приложения конеяньм но.ни вается бинирным кодом Хзмминга, если столсшы матрицы гг!эедставг>ян>т собой двоггчиук! запись чисел 1, 2,, 2~ 9.23. Лемма. Бинарнь<>1 к«д С„, яшгягтсн к<>д«,г< рисочгрност 2'я — и — 1, и< пр«гляющнлг <>дну «иибку.
гл«к<>э<гиге.гьспг<з«. 1!о определению проверочной матрицы кода Сн, се ранг равняется и. Кроме того, любые два столбц этой матрицы линейно независимы. Так как матрица Н вмес с .иобыми двумя столбцами содержит также столбец, равный и сумме, то ио лемме 9.14 минималшнге расстг>яиие кода С,„ра '. ияется 3. Таким образом, в силу теоремы 9.!2 код Сн, являетс ' кодом, ис>грав.>якнцим одну ошибку. 9.24.
Пример. Г!усть С, является (7,!)-кодом Хэмминга с нр верочиой матринен О О 0 1 1 ! ! П О ! ! О О 1 О 1 0 ! О 1 Если синдром полученного слова у равняется, например, Я (у) 4 (1 0 1)", то отсюда мы заключаем, по имеется ошибка в пята координате, так киь !01 является бинарной записьк> числа 5, Коды Хэмминга ыож>го также определить и для небинарног случая, т. с. гшд произвольным конечным полем г„. Здесь пр ' верочная маг ршш П >гъгеет размер и:.' !(<)н — 1!>(<1 — !)! столбцы этой ма>рицы ио>трио линейно независимы. Така матрица определяет линейный ((г)"' — 1)«(д — 1) (<) ' — 1)г(<[ — !) — и)-код с минимальным расстоянием, равным 3.
Опишем теиерь некоторые соотношения между длиной п к довых слов, числом >г информационных символов и минимальны, расстоянием дс линейного кода С над полем гч. 9.25. Теорема (граница Хэммиига). Пусть С вЂ” код над лгм Кт испрааля>ощий 1 «шиб«к и содержащий М кодовых сл а и — длина зт«г«кода. Тогда и(<- (,)« ",(,)<,, >)е П«каза>пглг<а>го. Имеется ровно ( ) (д — 1)н' векторов на полем <Тн дл>г>гы п н веса и, Все шары радиуса !с центрами в код вых словах гин>арно ие пересекаются, и каждый из М шаро содержит 1-,— (,~(у--1) -'.
+ („1(Ч--1) векторов пространства [[я, которое само содержит д векторов. 597 й !. 7!внойиьв коды й Вб. Теорема (грапица Плоткипа). Длл лингиьи го (а, й)-к~х)ц С ,вц иним !)ч г минимильньгм ригсииьчнигм ~1г выиилииетги нером итиио —,1 х 9 Лниизиииипитао. Пусть 1 и 7:.. и таково, что С ~ одержит кодов< е слово с ненулевой ~'-п коордииатои. Пусть О -- поди)нк'.)гаиство в С, состоящее из всех кодовых слов с ~'-и коордии;,г»й, равной 0 Тогда факторпростраиство С7О сод<ржит ц элемевзов, которые соотВетствуют ц Возмоим!Ост'ям Выбора йй ком. ищи иты в кодом слове. Таким образом, из равенства ! СИ О) ! СЛ ! вытекает, что )О) .— д"- '.
Подсчитывая сумму весов ниловых слов из С, получаем, что оиа ие превьппает величины и,г' ' (ц — 1). ч)ииимальпое расстояние дс кода С равняется мипимальиому весу ненулевого слова и, следовательно, должио цв вл~ творять доказываемому ие!7авепсзву, так как общее число ь гдовых слов иеиулевого веса равио ~)е — - 1. 1 1ц27 Теорема (граница Варшамова — Гилберта). Если вмнил»и ии ч нрпвггнтиио до ь~~~г~(, )(д - 1)', ьно .«~н)яиыугт аннин)иыи (и, й)-иод над лилем (ьо г дгпиимпльиым Ииг инщнгнм, нь меньниав и,ч г(. у(~ юглиии'игщмь двиганьем э1у тьорему путем иоьтроеиия п)тощ ри1иой !и — й) х л-матрицы О искомого кода. В качестве иерщио стслсща матрицы г) выберем ироизвольиый набор длины й элементов поля Гч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
