Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 131
Текст из файла (страница 131)
Кодировав означает, что блок из й символов передаваемого сообщен атае а», а; Е Гч, заменяется кодовым глооом с,се ... г„дли н > и, которое образонано символамн г; Е Кч Мы будем ра сматринать кодовое слово как п-мернуи> вектор-строку с ~ !гт Таким образом, отобоажение ) на рис. !).! являегся функци » из ге в К'ц, называемой гхпиой кодцроаиннл, а д — функцн' из Ц в $'», называемой схемой дикое!нрованцн. Простая разновидность схемы кодирования возникает в с чае. когда в сообщении каждый блок нз й символов а»ае ...
кодируется кодовым словом вида атае... а»г»„, ... гп где первые й символов совпадают с й символамн исходного с щения и иазываьотся инфорьиацнонныии аьиполплш, а допол тельные и — й символов с; Е ') е называкпси нпопсдочныжи (и контрольнпьип) снлюолп.ин. Такую схему кодирования часто пр ставляют в следующем виде. Пусть Н вЂ” заданная (и — й) х матрица, образованная элементами поля Тч и имеющая вид Н=- (А!и„), где А — матрица размера (н — й) к /г, а т'„» — единичн' матрица порядка и — )е. То~да проверочные символы г»,,, ..., могут быть определены из системы уравнений Нс" -= О, где с — кодовое слово, а т обозначает траиспо»щрование.
Ура, пения, образующие эту систему, называются проверочными Др, нснияма или уравнениями аропсрка на чгтносбчо '). ' ! Нппиаиие берет свое начало и иееледопаииях по бииарпмм кодам„т. кодаи иад полем Ке — Прим, иерее. й !. Линейные коды и,). Пример. Пусть Н есть 3)С7-матрица над полем ге след) )О!и!его аида: О ) ) ) О О Н))О)О)О. Обо ))!)оь)срочные символы можно на!тти из системы уравнений Нет О, читая с,, с,„св с, )алаш!ыми; С, - Са',1, Са - О, с, с, !с, !са =О, с, -'- са -'г са 14 =' О.
))нда иРОВСРО'!нью символы са. сш 1; можно вьб)а)5мь следУ!О!цим )кзоа:)о)4: Сь -С) .' Са ) С), С„== С,,-Са . Схо ьт ' с1 ! 11 ! Са. :)5ч):!ит, схема кодирования в этом случае является линейным ,5! )Оражеипем нз Г в Г ы которое имеет внд го). От Ва. О,) О)! о) оа. О), и) ) ит О4 11! ' 0" ' О4 и! От ' оа) В Общем случае В связи со схемами кодирования. Задаваемыми ли!иейными отображениями, мы будем пользоваться следуя)щей терминологией. О.2.
Определение. Пусть Н вЂ” матрица над полем !~г' размера И )с и и ранга и — й. Множество С всех и-к)ерных векторов с 'с !! „, таких, что Нс =- О, называется лингинь)м 5и, й)-кодом иад полем К„. Число л называется длиной кода, а /г — ))азмсри сшью кода. клементы множества С называются кодовыми с:!ов))ив 5!)ли кодовыми аектоуами), ма~рипа Н называется пров!)))очно)! мосчричей кода с. если 4) — 2, с называется бинырньс)1 кидом. Е1'ли матрица Н имеет внд Н .— )А 1'и ь), то код С называется 1'14 ЛИ'МО)ИЦЧССКЦМ КОдОМ ° :)1!ые!им, что множество С решений системы линейных урав- 5!"ии!! Нет' — О является й-мерным подпространством векторного ир'итранства г",.
Так как кодовые слова образуют группе но сл')жению, то С также называется гррплолым кодом. ))роме того. можно рассматривать как нуль-пространство матрицы Н '). ) то есть как идро лилейного отображении, задаваемого 4)атриией Р!, иаи 'Г)к154авство решений одвородиой системы лвиейных краш!евий с ватри а"! Н вЂ” Пд м. лере., Гл 9 Приво!левик коне итх волен ио 8,3, Пример (код с оба!сй проверкой на сстнасть). Пу 2, и пусть передаваемое сообщение имеет внд а, ...
а„. Тог !пре селим схему кодирования ) следующим образом 1: а,, аль-е(з! ... аллы !дс а! =- и; для !' — 1, ..., )и а ~„"а; —.- О, с=! ~а; ---1. б если с=-! / )л ат (а ()! Лт))т — Л/ !де а а, ... аи — передаваемое сообщение, а с -- с, ... с„, соответствующее кодовое слово. Это приводит к следующ определению. 9.5. Определение.
й!атрипз 6 -- (с„— Лт) размера )е .шзывается канонической (илн тпандортной1 нсазожданза!ей ( соднрусс!сс(с*с!) жатрицей линейного (и, й)-кода с провероч митр!щей 0 - (Л 1я л) Из уравнений Ост - О и с а6 следует, что матрипы 6 связаны равенством 66т — О !сс!.! 6 'овпидает с иростраисзвом строк клнсишчс ской порож шей митрвсы 6 '). В более общем случае любая й х и-матрипа '! То есн, е !призом лииеаиого отис!рзиеиия, задаваемою мвтрицей а. ' ария. Перев. !'ледоватсльио, сумма всех элементов лкзбого халово~о сл :>, ... !з„„! равна О. Если сумма элементов полученного сл равняется 1, то получатель узнает, что в нропессе передачи в !!сини появилась ошибка. Если положить и — )е ) 1, то по !сивые код является линейным (л, а — 1)-кодом с провероч ма гриней Н - (11 . ! ).
9.4. Пример (код г ловторенмеи), В коде с повторением к " !и кодовое слово содержит только один информационный с ,изл а, и и — 1 проверочных символов с, — ... - св = а,, т, . пивал а, повторяется еще и — 1 раз. Этот код является ли ным (и, 1)-кодом с проверочной матрипей Н = ( — 1 с„!). Из проверочного уравнения ггст — О, где Н вЂ” (Л зи" следует, по 9 Е Линейные коды йкыт»я»ство строк которой равняется С, взвыв~с~~я пороэкдаюк.» мо;прниеи кода С. 9 9. Оример. Каноническая порождающая матрнпа для кода ,, „; „верочкой матрппей Н из примера 9.) имеет вид ООО О) ООО Оо)О)б (:) ООО) ) ) О 9.7. Определение. Если с — кодовое слово„а у — — слово, пок» п»ог после передачи сообщении по зашумленному каналу, р;юность е - у -- с —: е, ...
е„называется вектором тиибок :л» трлювым словом. 9.8. Определение. Пусть х и у — два вектора пространства ')'о1 да (О расстоянием Хэмминга д (х, у) между векторами х и у гигется число координат, которыми векторы х и у отличаются 'о, ~ от друга; (й) весом (Хэммикга) ю (х) вектора х называется число нсну»ык координат этого вектора. Ттснм образом, если х — передаваемое кодовое слово, а у— , олучтпюс после передачи слово, то величина д (х, у) дает число пнибок, появившихся при передаче слова х, Ясно, что гв (х) -= д ('х, 9) и д (х, у) --= ю (х — у). Доказательство следующей нины оставляется читателю в качестве упражнения.
9.9, Лемма, Расстояние Хэмминга является метрикой в прозпоанстве Г", т. е, для любых х, у, х Е Ц выполняются следую- П. е соотноиген ия: О) д (х, у) == 0 тогда и пголько тогда, когда х .—.- у; (й) д(х, у) =: — д(у, х); (ОО) д (х, з) . д (х, у) -',— д (у, х). При декодировании полученного слова у обычно стараются п»)г ~ кодовое слово с, для которого гв (у — с) принимает наиитыиее возможное значение, исходя прн этом из естественного "Род»сложения, что малое число ошибок встречается чаще, чем оол пюе. Таким образом, при декодировании мы ищем кодовое "а ~во с, ближайшее в смысле расстояния Хэммпнга к получен»опт слову у.
Это правило называется декодированием в блпясайъее кодовое слово. Ч 19. Определение. Гслп г — некоторое натуральное число, "' код С с: — К" называется кодом, исправляюи(им ( осиибок, если лля любого уй 9'" найдетси пе более одного слова с Е С, такого, й(у, с) ~г.' Гл Ч. Прялсженяя конечнмк полез Если с Е С вЂ” переггггвзеыое кодовое слово и при передач появилось не более» ошибок, то г» (у, с) -- » для полученног слова у. Если С вЂ”. код, исправляющий» ошибок, то для всех кодо. Вых с:гОВ х =е'= с ЯО'!жпо ВыполнйтьсЯ сооз'нопгение !» (У, х) зто О;нзчзсг, что с являетси блнжайпшм к у кодовым словом и чт> декодпровзнис в ближайшее кодовое слово дзе! ПравильныгТг резульгзгз Таким образом, Одна пз задач гс рнп кодпрОВания! щгстоиг я нос!роении таких кодов.
для кото!Зых кодовые слова! находится па зпзчптельном рагттоянин друг от друг ь С другой" стОропы, ест!'ств!'пно стр!'мпться переда'и ПО Возможности больше информации в единицу времени. Согласование этих двух: тспдсицпи составляет одну нз проблем теории кодирования. 9.11. Определение. Число йо -- пцп й(н, «) — гп!п иг(с) и, чГ с ь -сГс О-~' гшзывается м«нимальным ршгстоян«ем (пли просто»гас!о!!!я««ем) ~ линейного кода С.
9.12. Теорема. Кос) С с м!«гимольным росстани«ел! дс может ьс«ров!в«ь» гшшбок, соли !»! 2ы 2» ! 1. Дгг азательство. Шар В, (х) радиуса» с центром в точке х Е ' Е $'" состоит из всех векторов у е р';, таких, что г» (х, у) ': ». ". (!равнло декодировзния в ближайшее кодовое слово гарантирует,, что каждое полученное в результате передачи слово, содержащее нс более» ошибок, должно лежать в шаре радиуса» с центром в переданном кодовом слове. Для того чтобы можно было исправить» ошибок, шары радиуса» с центрами в кодовых словах х должны не пересекаться.
Если и е В, (х) и н с В! (у), х, у с С, х~у, то й(х, у) -Гй(х. ц) .! с»(ц, у) =.- 2», что противоречит тому, что с»с . 2» -- !. Б 9.13. Пример. Код из примера 9.! имеет минимальное рас. сто!шве г»с = 3 и, следовательно, может испРавлЯть однУ ошибкУ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
