Введение в прикладную комбинаторику, Кофман А. (984071), страница 56
Текст из файла (страница 56)
!Хп пХЙ 1Х~п !лхл лХЙ 1ХЛ Мы видим, что !!лэ"!!' переводит в нулевой вектор любой вектор !!и!! нз д' . Проверочная матрица. Матричное соотношение !! о !! !! тэ !!' = !! 0 !! (БЗ.ЗО) 1Хп лХЛ 1Хл (Б3.29) можно переписать в виде !! Уэ !! !! и !!' = !! 0 !!. (БЗ.З1) ЛХп пХ1 ЛХ1 Это — система й линейных однородных уравнений с й неизвестными, и й-мерные векторы, компоненты которых — символы кодовых слов на контрольных местах, будут ее решениями. Ввиду этого !!Ж!! называют проверочной матрицей. Обнаружение ошибок. Для вектора !! и (! из подпростран1Хп ства Е, порожденного строками матрицы !!У!!, имеем !! Ж !! !1 и !!' =!! 0 |!. (БЗ.З2) ЛХп 'лХ1 ХХ1 Если теперь на выходе получаем некоторый вектор !! в !! с 1Хп !! Я !! !! ш !!'= !! г !!Ф!! 0 !!, (БЗ.ЗЗ) ЛХл пХ1 ЛХ1 ЛХ1 ьи ьм то !!ш!! не принадлежит э и мы обнаружили ошибку.
Замечание. Очевидно, что при !!У6!! !!и1!!'= |!О!! можно лишь утверждать, что при передаче по линии не произошло ошибки какого-то определенного типа, но нет гарантии, что отсутствуют ошибки других типов. Действительно, вектор !!а!! имеет й компонент н поэтому не дает возможности выявить больше чем рл — 1 типов ошибок (р — число элементов поля). Поэтому необходимо с самого начала установить, какие ошибки мы хотим обнаруживать. Запишем матрицу !! пэ!! в виде последовательности ее столбцов: !! Я !!=!!!! С1!!!! Сл !!...
!! Су !!... !! Сп !!|!, (Б3.34) !!С,!!= ЛХ1 (БЗ,ЗЗ) Для вектора 1)о)1=1)аа,...а!...а„)1, а!~10, !), у=), 2,..., и, (Б338) ~х« в пространстве над полем из двух элементов имеем 11 М 1! 11 о 11 = а, 11 С, 11+ а, 11 С, 11+ ех«лх~ ех~ лх~ ... +а,)1 С, 11+ ... +а„)1 С„)1=110 11. (БЗ,Зу) ех~ лх~ лх1 Если при передаче 11 о !1 принимается как 1!и)1 с ошибками на ~хл 1Хл местах г, е и 1, то пусть 11 М 11 11 и 11' = а, 11 С, 11 + аД С, 11 + лх« «х1 ех1 лх~ ...
+ Ь, 11 С, 11+ Ь, 11 С, 11+ Ь, 11 С, 11+ ... + а„!1 С„!! М О, (БЗ 38) лх'~ ' лх~ лх1 лх~ Складывая (Б3.37) и (Б3.38) по модулю 2, получаем 11 М 11 11 ы 11' = (а, + а,К) С, 11+ (а, + а,) 11 С, 11+ лхл «х! лх1 ех1 ... + (а„+ Ь )11 С„)1+ (а«+ Ь )11 С,)1+(а, + Ь))!С,)1+ ...
+(а„+а„)))С„))ФО, (Б3.39) лх1 Так как а,+а,=О, Ь+а =(, (Б3.40) (Б3.4!) то 11 М 11 11 в 11' = 11 С, 11+ 11 С, 11+ 11 С, 11 = 11 г 11 Ф 11 0 11. (Б3.42) Всегда возможно указать сочетания столбцов матрицы 1Ю11, соответствующие наиболее вероятным ошибкам, исходя из 2л — ! значений ненулевого вектора !!г)!. Остается теперь установить связь между проверочной матрицей !!М!! и минимальным расстоянием д ) 2е + ), или д ) 2е, нли даже И ) е+ ! + 1, если устанавливать различные границы возможностей для обнаружения и для исправления ошибок. Хэмминг доказал, что минимальное расстояние равно Ы, если любые е( — ! столбцов матрицы линейно независимы. С другой стороны, Мак-Класки доказал методами линейного программирования, что ))Зе!11 дает код с минимальным расстоянием Н тогда и только тогда, когда подматрица — 1!А)1' этой матрицы обладает тем свойством, что каждый ее столбец содержит не меньше д — ! ненулевых элементов, а любые ! столбцов— не меньше Ы вЂ” ! ненулевых произведений элементов по строке, 452 Примеры линейных двоичных кодов.
1) Код Хэмминга для исправления прог!ой ошибки. Если длина колового слова равна и, то необходимо, чтобы и <2" — 1. (Б3.43) При п=7 имеем 2' — 1=7 и й=З, аз=4. По МакКласки кажлый столбец матрицы — ЦА Ц' должен иметь не меньше 7! — 1 = 2е = 2 единиц, каждая пара столбцов — не меньше а — 2 = 1 ненулевых произведений элементов по строке и каждая триада — не меньше а — 3 = 0 таких произвелений. Матрица !О ЦАЦ )1 о О (Б3.44) удовлетворяет этим условиям.
Дополняя ее единичной матрицей порядка 3, получаем проверочную матрицу 1О 1 ! 111 0 0 ЦЯЦ=Ц вЂ” Ц АЦ'-:Ц 1 ЦЦ= ! 0 1 1! :о 1 о (БЗ 45) !! 1 0 1!О О 1, Заметим, что каждый столбец матрицы ЦЖЦ совпалает с вектором Ц г Ц, когда ошибка произошла на соответствующем месте ЗХ1 кодового слова: Ц 7в Ц Ц о Ц'=Ц С, Ц=Ц з Ц.
(Б3.45) ЗХ7 7Х1 ЗХ! ЗХ1 Если переставить столбцы в матрице Ц ззЦ так, чтобы 1-й столбец представлял собой двоичную запись числа 11 ! 2 3 4 6 6 7 0 0 0 1 ! ! цубц=о ! 1оо 1 0 1 0 1 0 1 (Б3.47) места кодового слова 3 6 6 7 4 2 1, то при умножении ЦЖЦ на ЦоЦ' получающийся вектор ЦзЦ пред. ставляет собой двоичную запись номера места, где произошла ошибка (или нулевой вектор).
Пусть кодовое слово обозначается Ц о Ц = Ц а!азиза азиза~ Ц (Б3.48) Из ЦЯЦ в фор.,зе (Б3.45) получаем матрицу ЦУЦ, порождающую код: 1 0 0 0 0 1 1 ЦэЦ ЦЦ ! Ц!Ц4ЦЦ о о 1 о 1 1 о ' (БЗ49) ;0 0 0 1 ! ! 1 Быпишем полностью линейный код, получающийся с по- мошью 1У!!, для всех возможных двоичных слов длины 4: Сообщения Кодированные сообщения о о о оооо оо!!оо о!о!о!о о!оо (Б3.50) !! в !1= аз 4!4 аз аб 417 ~4 Три контрольных соотношения для кодовых слов: а7 аз аз 474 аз ав а7 ооо !1,ок !! .
!1 в !!' = о ! ! о о о!о!о (Б3.51) или а, +аз+аз+а,=О, а, + аз + а, + а, = О, а, +аз+ а, +а,=О. Пусть, например, передается сообщение (Б3.52) (Б3.53) !)а ~~=!)1 0 1 1!1, 1~0110011!!, закодированное (Б3.54) и на третьем месте принимается ошибочный символ, т. е. при приеме получается ЦО100011Ц, (Б3.55) оооо ооо оо!о о о о!оо О!О о1!о о !ооо о о о ! о ! о 1ОО ! о о 1 1 1 1 о о 1 1 о о о о 1 1 о о 1 ! о о ! о о о о о о ! ! !!а! аз ооо о!о О1О ооо о о о о о о о о о о !оо 1 1 1 о ! о 1 1 1 о о ! ! о о о о 1 ! о о о 1 О ! 1 который не принадлежит ебб, т. е, не является кодовым словом; тогда (Б3.56) !!М!!.
что как раз и означает, что ошибка была допущена на третьем месте и там нужно О исправить на 1. 2) Код Хэмминга, исправляющий простую ошибку и обнаруживающий двойную, Из кода (и, т) можно получить код (и + 1, т) со словами длины п + 1, имеющий т информационных символов, если присоединить 1 на (и + 1)-м месте каждого слова кода (и, т) и ввести еще одно проверочное соотношение: ее! 2~ а,=О'). (Б3,57) Тогда: если я+ 1 проверочных соотношений выполняются, то не произошло простой ошибки; если последнее соотношение не выполняется, то произошла простая ошибка, которую можно исправить с помощью первых й соотношений; если последнее соотношение выполняется, но не выполняется по крайней мере одно из первых й соотношений, то обнаружена двойная ошибка; исправить ее нельзя.
Вернемся к предыдущему примеру. Действуя, как описано, получаем код (8,4) с проверочной матрицей 'О О О О 1 1 1 1 О О 1 1 О О 1 1 О ! О 1 О 1 О 1 1 1 ! ! 1 1 1 1 )!М!!= (БЗ.58) и соотношениями (ВЗ.59) коды, нам потреалгебры, которые ач + аб + аб + а,+а,+аз+ а! + аз+ аб+ а, + а, + а, + об + а, + а, + а, -(- Циклические коды. Чтобы изучать эти буются некоторые сведения из современной мы кратко изложим.
з) ~ означает сложенне по модулю 2. а,=О, а,=О, а,=О, а,=О, Теория присоединения.Многочлен хз + 1 не имеет корней над полем действительных чисел (К, +, ). Он неприводим над этим полем, т. е. не разлагается в произведение многочленов меньшей степени с действительными коэффициентами. Присоединим теперь к элементам поля К символ 1, для которого предполагаем выполненным соотношение 1' = — 1, и на этом расширенном множестве элементов рассмотрим операции + и, считая для них справедливыми все аксиомы операций поля.
Получаем тогда новое поле (К(1), +, ), в котором многочлен р(х) = х'+! уже разлагается на множители: р (х) = х' + 1 = (х + 1) (х — 1). (Б3.60) Таким образом, мы приходим к полю комплексных чисел (С, +, ), в котором операции + и задаются соотношениями (а+1Ь)+(с+1с()=(а+с)+1(Ь+а), (Б3.61) (а + 1Ь) (с + 1д) = (ас — Ы) + )'(Ьс + ас(). (Б3.62) В общем случае, если задан неприводимый над полем К (основным полем) многочлен степени й Ф О: р(х)=а,х'+а,х'+ ... +а;х'+ ...
+аьхь, (Б3.63) где а; ен К и ах чь О, то всегда можно присоединить к К последовательно символы а, 6, у, ... так, чтобы р(х) полностью разлагался на множители в новом поле (К(а, (1,у, ...), +, ), называемом полем разложения многочлена р(х). В дальнейшем мы будем рассматривать лишь конечные поля СО(р), где р — число элементов поля, н, как правило, ограничиваться случаем р = 2. Над полем СО(2) любой многочлен можно представить в виде р(г)=а,гс+а,г'+ ...
+а,г'+ ... +аьг~, (Б3.64) где и; ев (О, Ц и ад Ф О, если степень многочлена равна й. Если р(г) неприводим над СО(2), то можно добиться его разложения на неприводимые сомножители, присоединяя к СО(2) лишь один элемент а. Можно показать (см. 3 А5), что й корней этого многочлена — степени элемента а: р(г)=(г+а')(г+а')... (г+а')...
(г+аьь ). (Б3.65) Так как а — корень р(г), то в поле СО(2) (а) выполняется а,аз+ а,а'+ ... + а;а'+ ... + аьа' =О, (Б3.66) или аьа"=а а'+а а'+ ... +а а'+ ... +аь,а' ', (Б367) что можно также записать как аз=а'а'+а',а'+ ... +а,'.а'+ ... +а',аы, (Б3.68) если / а; = а,а». (Б3.69) Соотношение (Б3.68) показывает, что все степени а можно выразить как линейные комбинации первых й — 1 степеней с коэффициентами из СП(2). Действительно, а» '"' = а„'а' + а',а'+ ...
+ а',.а'+' + ... + а',а» (Б3,70) и, если а" заменить по формуле (Б3.68), то получаем а'+'=а,"а'+а",а'+ ... +а,"а'+ ... +а,",,а»-'. (Б3.71) Вообще в поле Сб(р), р = д», где д — характеристика поля, всегда существует элемент а, для которого д» вЂ” 1 является периодом (минимальным показателем е с а' = !). Все элементы поля СС (р) тогда представляются как линейные комбинации а'=~р;(а», а', ..., а»-'), ю'=1, 2, ..., д» вЂ” 1, (Б3.72) соответствует линейной комбинации а' = <р; (а', а', ..., а»-') и обратно.
Элементы г,(г), ! = 1, 2,..., д» вЂ” 1, вместе с г,(г) = 1 образуют множество со структурой поля (р(г) — неприводимый многочлен). Элементы т,(г) называют вычетами по модулю р(г) многочленов ~р(г) ~ А(г): ~р(г) — = т; (г) (шоб р(г)), ~р (г) = в (г) р (г) + г (г) (БЗ.74) где (Б3.75) бед т; (г) ( бед р (г). (Б3.76) Для любых!, ! между 1 и д» вЂ” 1 найдутся такие Ь и и в этих же пределах, что т; (г) + г~ (г) — = т„(г) (глоб р (г)) (Б 3.77) (Б3.78) гс(г) г (г) = г„ (г). р (г) 1 ! гг ! з Пример. Пусть (Б 3.
79) 457 Элемеят а называется элементом порядка д» вЂ” 1, а непрнводимый многочлен р(г) такой, что р(а) = О, — примитивным многочленом, Каждой степени а*' = ~р, (а', а', ..., а»-') соответствует и-выборка элементов поля СС (в) (всего таких й-выборок будет д»). Поле СП(р) называется расширением поля СС(в).
Многочлен р(г) имеет в СП(р) и корней а»~, ач~, „а»~ ~. Если рассмотреть кольцо А(г) многочленов над СП(д), то каждый элемент фактор-множества г~(г) =а,г'+а,г'+ ... + а»,г» ' Это — примитивный многочлен над СП(2). Действительно, он, во-первых, неприводим иад СП(2), так как р(о) =1+о+0=1. -о (БЗ.80) и р (1) = 1 + 1 + 1 =! чь 0; (Б3.81) во-вторых, присоединяя к СП(2) элемент а, для которого р(а) = 1+а~+а'=О, (Б3.82) видим, что а имеет порядок 2' — ! =1, Покажем теперь непосредственно, что р (») — (» и) (» оэ) (» п4) (Б3.83) Действительно, Р (а') = 1 + а' + а' = 1 + 1+ а + а' + а + а' = 0 (Б3.84) и аналогично р(а')=О. (Б3.85) Если период е элемента Ь меньше д' — 1, то этот элемент порождает циклическую группу порядка е: Ь', Ь', ..., Ь', ..., Ь' — Ь' = !.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
