Введение в прикладную комбинаторику, Кофман А. (984071), страница 58
Текст из файла (страница 58)
г) Наконец, для обнаружения трех ошибок нужно взять многочлен вида а (г) = (1 + г) р (г) (Б 4.42) где р(г) примитивен. Действительно, 1+ г позволяет обнару- жить простые ошибки, а р(г) — двойные ошибки. Б5. Коды сцепления Назовем регистром сдвига систему, позволяющую осуществлять последовательное изменение мест г-выборки. Например, если в момент времени (о имеем выборку [а,а, ... ао), в которой места элементов можно характеризовать полиномом (ро(г) = А =аог'+аг'+ ... +аог, то в момент 1о+1 имеем выборку [Оаоа,... а„], характеризуемую полиномом(р, (г) =Ог'+а,г'-1-... ...
+аогоо(, в момент (о+!' выборку [О О ... О аоа,, ао) и полинам (р;(г) =Ого+ Ог'+ ... +Ог' '+а,г'+ ... -[-а,го!!. Можно также усложнить систему, накладывая различные соотношения на компоненты выборки в разные моменты времени, например, а" + и = а"' -'; а',", о о + а(,'+и = а"', о а((а+ (' — апп 2 1 а; ен Сб(2). а(!) = а(о) 1 а(о) о о а(() а(о) о (Б5,!) а(!) — а(о) 2 1 465 Пусть в момент времени 1о регистр находится в состоянии ио а! ам а( ен СП(2). Для обозначения последующих состояний будем использовать верхние индексы. Так, в момент времени !о+ 1 новое состояние регистра выражается через предыдущее состояние с помощью системы соотношений: (Б5.2) где !~ ои! !! — вектор-столбец с компонентами ан>, а!о, а<!1. ЗХ! О 1' г В моменты времени !о+2, !о+3, ..., 1,+!', ...
получаем последовательно !! о!з! !~ — !! „зи !! . !! он1)! 1!,у7 !!з, !! с1о! !!, )! 1!З!!! !! Л!!,!!о1З1!! !! З«!!З,!!в<О!!~ (Б5.3) Мы попытаемся определить такую матрицу |! з!'!1, чтобы для нее существовало целое число и со свойством !!,1«>!! !~ й !!к.!!о1о!!! !!З,1о!!! (Б5.4) и чтобы наименьшее из таких чисел п было равно 2" — 1. Необходимое и достаточное условие для этого дает теорема Гамильтона — Кали '), которая утверждает, что каждая матрица !!Щ является корнем своего характеристического уравнения: !~!О!! — а!!1!~ ~=0. (Б5.5) Пусть )(г) = !!!.»з'!! — г!1!!Ц, Если можно найти такое п, что Г(г) делит г — 1, т.
е, ге — 1 = 1(г) 17(г), то по теореме Гамильтона — Кэли имеем (так как 7" (М) = О) П ли" — !!1>~=Ц.УГ) б(ж) =О, т. е. !!лГ!!"=1!1!1, и !!и !! оо !! !!,о !! или что реализует первое из условий. Заметим, что для реализации второго условия достаточно, чтобы 7"(г) был примитивен, Эти два условия будут, следовательно, удовлетворены, если выбрать регистр сдвига с й позициями и — в качестве соотношения между различными позициями — условие, которому должен удовлетворять корень а примитивного полинома степени й, т.
е. р (а) = О. (Б5,9) П р и м е р. Пусть й = 3. Попытаемся получить двоичную цепь длины 7. Пусть р(г) = 1+ из+ гз. Это — примитивный Это можно записать в матричной форме: о )! сш !! ! 9 О . !! „1о1 !! !! Зи )!. !) „ыо! )! ЗХ1 о ! о ЗХ1 ЗХЗ ЗХ! !! о1о !! !! «з !! . !! „11-! ! !! у! ~г !!1 , !! „<о! !~ '! Ф. Р, Га ит м азер, Теория матриц, изд. З-е, «Наука», !967, 466 (Б5.6) (Б5.7) (Б5.8) многочлен. На позиции в регистре налагаем условия анп = аа " + а,"-'1, о о а1'1 = а!' о аа1 ап-П г (Б5.10) Каждое состояние регистра можно получить тогда из предыдущего с помощью матрицы (см.
Б5,2)) О ЦошЦ= 1 О О ~!Он-"Ц=ЦЯЦ ~!он-пЦ, (5511) О16 например, Ц о!'! Ц = Ц 77 ~! Ц о!'! Ц, ЦО1>Ц ЦЯЦ Цо<1Ц и т, д, (Б5.12) (Б5.13) Напишем характеристическое + 1 = г'+ г'+! = р (г). (Б5.14) Можно проверить непосредственно, что матрица Ц Х 1!, удовлетворяет уравнению г ( зг) ц гг цз ! ц гг (е'+ 1 6 (Б5.15) Придадим компонентам вектора начального состояния Цо'Ц произвольные значения, не все равные нулю, например, О ЦооЦ= О . (Б5, 16) 1 Имеем О! О~~ О О О~ (Б5.! 7) О О О ! о 11~ О'= (Б5.18) Вместо того чтобы продолжать дальше, заметим, что при применении матрицы Ц.я Ц к вектору состояния Ц оч-'1Ц компоненты а" " и а1' " сдвигаются в положения соответственно а",! 467 О г(г)=!Ц„УЦ г~!1Ц!= ! О О (! + г) О 1 г О = (1 + г) г О 1 г 1 Ц о'!!= ,О 1 Ц о'Ц= о уравнение 1 г О О + О г О~ ОО матрицы ~!.й' Ц: о О ! 1 О О 1 1 О и а,"~, а а1оо представляется как сумма а<'-и и а1'-и по модулю 2.
Образование цепи теперь видно непосредственно: О О 1 1 1 О 1О1 1а1 а~ ао 01 Ш 01 1О> + а1О1 оо о~ "о во ао Ф % ов 01, 01 1 1О1 (Б5.19) 100111О1О 1...111010~ а, ...~01011! 6, .... 1011/1~ 7...... ~1/1!1/ а...,... ~111~0~ 5........ Г)ТО~1! 2.......... 1011 ~ О! Вообще и двоичных знаков в цепи максимальной длины а = = 2о — 1 достаточно, чтобы осуществить пересчет, требующий (2о — 1)А двоичных знаков.
Это — принцип кода Бодо. Б6. Декодирование перестановками Пусть С вЂ” множество т-выборок из поля СО(2), образующих код: С=(Сп Со, ..., Со-). (Бб. 1) Мы рассмотрели получение кодов с минимальным расстоянием д = 2е + 1, удовлетворяющих некоторым линейным соот. ношениям; |! Я ~| ~! Со 1~=11 0 1~ для линейных кодов (Б6,2) охг гх~ ох~ г~М(г)+ г(г) =р(г) д(г) для циклических кодов, (Б6.3) В общем случае мы можем предположить, что код получается с помощью некоторого преобразования г"(т), дающего кодовые слова длины т + й. Через т„обозначим значение 468 Заметим, что если в этой последовательности брать трн иду- щих один за другим двоичных знака (в циклическом порядке), то получим все числа от 1 до 7 в двоичной записи (в десятичной системе) последовательности двоичных знаков, расположенной в гп информационных местах кодового слова С„.
Тогда можно записать (Б6.4) Р(т )=С„а С. Напомним, что для линейного кода, например, кодовые слова заполняют подпространство и-мерного линейного пространства. Предположим, что нам удалось найти подстановку з, «сохраняющую закон образования кода Е(т„)», т.
е, при С„~ С имеем з(С„) =С„ен С, (Б6.5) и, следовательно, (Б6,6) Фиксируя некоторую перестановку, дающую порядок компонент векторов пространства д'„, будем рассматривать перестановки и (см. $ 16) и (С„) = С« ~ С (Б6.7) п(С,) =Р(лг„). (Б6.8) Если теперь получено слово С'„с не более чем е ошибками, то могут представиться два случая: 1) в гп информационных местах не содержится ошибок и информация т, полностью восстанавливается, т. е.
можно точно найти кодовое слово: Р (т,) = С„ (Б6.9) так как С, — единственное кодовое слово, находящееся на расстоянии О ( е от полученного слова С',; 2) в гп информационных местах имеются ошибки, полученная гп-выборка гл„ не совпадает с переданной пг„, тогда Р(гл„) = С„=~ С„ (Б6.10) слова С„и С, находятся на расстоянии 0 ) е. Заметим, что перестановка и не изменяет расстояния между С, и С'„: 0 (С„С'„) = 0 (и (С,), и (С'„)).
(Б6.11) На этом замечании основан способ декодирования, позволяющий в некоторых случаях найти переданное кодовое слово, если в полученном слове имеется не более е ошибок. Для этого рассматривается последовательность перестановок, сохраняющих закон образования кода: (Б6.
12) 469 Действуя, как указано в таблице (см. ниже), получаем С„=п !(С!) (Б6.! 3) — искомое слово. К сожалению, нахождение последовательности 7, П4, па, ... ..., и', ..., Пт — трудная задача. Отметим, что рассмотрение степеней циклического сдвига компонент не всегда приводит к цели и часто оказывается необходимым рассматривать другие типы перестановок (см. [251). Расстояние межлу С' н и'(с,'): и [с', и'(с„')) Значения "'л Последовательность перестановок и! ! (лт„) если 0 [Со, 7(С'„) ]) е, то продал каем если 0[С!, !(С„') [>а, и' (С„') и! (лт'„) то продолжаем до тех пор, пока ие получим 0[С!, и'(С'„) ) ~(е и~ (С'„) и4 (пт„) и! (444„) и! (С',) Пример.
Применим изложенный метод к коду Хэмминга из ф БЗ, исправляющему простую ошибку. Выпишем кодовые слова в следующем порядке: г' (лт) (Б6,14) Легко проверить, что циклический сдвиг сохраняет закон образо- 470 ав ат ав ав 0 0 0 0 1 0 1 ! 0 1 1 0 1 1 0 0 1 0 0 0 0 0 О 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 О 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 ав а, а, 0 0 0 0 0 0 0 0 1 О ! О:С 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 1 О 1 0 1 0 0 0 0 1 0 ! 1 1 1 вания кода. Если при передаче кодового слова Са была допущена одна ошибка, а именно, было получено слово С'; = ! ! ! ! О О ! О!, то, применяя метод настоящего параграфа, получаем следовательно, с,= '<с'!=!! ! о о о ! о~.
ЛИТЕРАТУРА [1] Авунпо-Боди но (Атипйо-Вой)по О), Есопогп!с Арр11саВопз о1 Гйе ТЬеогу о! ОгарЬз, Оогйоп апй ВгеасЬ, Н. У., !962. [2] Американское математическое общество (Ашег!сап М а1Ьеш а 11 с а! 5 ос ! е1у), Ргосеей!пяз о1 Гпе Тепрн Ву!прозппп 1п Арр!)ей Ма(Ьеша(!сз, 1958. [3] Американское математическое общество (Агпег1сап М а 1 Ь е гп а 1!с а! 5 о с)е 1 у), СошЬ1па1оПа! Апа1ушз, Ргосеей. Бушр. 1п Арр11ей Ма(Ь., 1960.
[4] Б а л а ш (В а 1 а з Е ), О!зсге1е Ргодгашш(пд Ьу Гйе Р1!1ег Мербой ю!!Ь ех1епмоп 1о !г!(хей-!п!едет рго2гаппп!пя апй аррБсаВопз 1о МасЬше, 5ег(иенс!па. !п1егпаНопа! СогпрШ, Сеп1ег, Коше, 1966. [5] Басекер (ВнзасЬег К. О.) и Саати (5аа1у Т, !..), Р!пВе ОгарЬв апй Не1юогЬв, Ап !п1гойисВоп тт!!Ь Арр11са11опз, Ей. ЫсОгам Н!!1, Н. У., 1965. [6] Б е к к е н ба х (В е с Ь е п Ь а с Ь Е.
Г., ей.), Арр1!ей СогпЫпа1оПа! МайешаНсв, Ей. %!1еу, 1964. [7] Б е н е у н (В е п а у о и п К.), Н г и е м (Н и Ь г е ш Р. Т.) и Р о й (К о у В.), Оп шойе!е 66шр!ап1а1юп е1 й'асЬеш!пешеп1, 0осшпеп( 5. Е. М. А., 1966. [8] Б е р ж (В е г и е С.), Ьа ГйеоПе йез 8гарЬез е1 зез арр1!саБопз, Ей. 0ипой, РаПз, 1958; 2-е ивд., 1965. [Русский перевок: К. Бе р ж, Теория графов и ее применения, ИЛ, 1962.] [9]Берж (Вегае С) и Гуила-Хури (ОЬон!!а-Ноиг! А), Рго. игагпгпез, )енх е1 гезеаих йе 1гапзрог1, Ей.
0нпой, 1962. [19] Берн сайд (Вития)бе %.), ТЬеогу о1 Огопрз о1 Р1пВе Огйег, 2-е иэд., СагпЬПйде Нп(ч. Ргсзз, 1911; 0очег РиЫ., 1955. [11] Б е р т ь е (В е г1! е г Р.), Ргосейигез ропг е!аЬогег йез 1оигпеез йе й!з!г!ЬпВоп, РнЫ!са11оп 5. Е.
М. А., збПез зрес)а]е, № 8, 1966. [12] Бертье (В ег1! ег Р.) и Рой (К о у В ), ()пе ргосейиге йе гезо1иВоп ронг ипе с1аззе йе ргоЫешез роитап! ачо1г ип сагас1еге согпЫпа1о1ге, 0осшпеп1 5. Е. М. А., 1964. [18] Бетте рсби (Ва11е ге Ьу А), Не1ъогЬ Апа1уз!з 1ог Р!апп!пя апй 5сЬейн!!пи, Ей. Мс М!!!ап, 1964. [14] Биркго ф (В ! г 1гЬ о! ! О.), ЬаЬВсе ТЬеогу, Агпсг. Марш Бос, М. у., !948. [Русский перевод: Г. Б и р к го ф, Теория структур, ИЛ, 1952.] [15] Г у те (О о и(а у), Буз1егпе йе иез1!оп й'ип рагс й'епи!пз гпо1еигз, Ме(Ьойез й'а!!ес1а!!оп, 0осшпеп1 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
