Алгебраические системы и некоторые их приложения в теории информации и автоматизации проектирования, страница 7

ПР Й Р Й(13)" Р Р Й четности является матрипа С ~(1 О 1 ) 1 1/ ПЙ ВР (* Р РРЙ ЗХ6: 100110~ б'= 010011(. ..„„( Сообшения й ~ 100, )2 ~ 010, пй ~ 001 кодируются соответственно первой, второй и третьей строками матрипыС, Полный список ксдировзния следуюший) а.'- ООΠ— 000 000, а'- 100 -1-100 100, а'- 010 — 010 011, а'- 110 110 101', аУ- 001 — 001 111, аз- 101 101 001, а 011 011 100, 2у - 111 -т- 111 010, 2,3, Г поные коды Блочный (Ртт, м )-код незывается групповым, если его кодовые снова обрезуют группу, Заметим, что множество всех двоичных слов длины 7)Рм образует коммугатнвную группу с опервдией покссрдинатного сложения по модулю 2, в ней выяопняется соотяошение а+апО, Следовательно, множество спов-сообшений я дняны г)РТ есть хоммутативиеч группе, Пусть (.

- порождаюшая метрица коде размера ~"гг ктт. Тогда множество кодовых слов пР =ад' есть группа, тек как есчи ~)'хатФ„Ья=аяС, сй~~Ьхяа'С,'+азй'п(а'~аяФ. Следовательно, матричные коды являются групповыми. В групповом коде наименьшее расстояние между кодовыми словами раино накм(зп,шсму весу ненупеврго кодового слова,что зиппо из состношеняя а~9',3~)пи/Я"'Рб'~,) .

спедоватепы(о, код П ьсп(.рс 3 (с"л,()ш ((. 2).2) (п(ос(:(к и п(проспят(, пдпокроткук~ шы кт к о(пп)ружишш(, пь()внук), т()к,,к )((()гп(п(.(пиД ()ос коп( зов ,ЧШО ( ППРН Пусть задан групповой код с порождающей матрицей б и кодирование происходит по схеме Ь =ао'. При передаче кодовые слова могут исказиться, и мы при- нимаем сообщение С С..., С,, гдеС=З~Р иР=Р„., Ррх вектор (строка) ошибок. Предлагается следующая схема декодирования, при которой вероятность того, чтоЮ~~?Д~й, будет минимальна, Обозначим череэС множество всех слов, которые могут быть принягы.

Это множество всех двоичных слов длины и, и оно образует коммутативную группу, МножествоЮ всех кодовых слов есть подгруппа С . Рассмотрим множество смежных клас совС по сч, т.е. фактор-группу С/3 . Лидером смежного класса назовем слово наименьшего веса. Поскольку смежные классы либо не пересекаются, либо совпадают, то любой элемент слс' однозначно преудстевляется в виде суммыс=РР4 Ь кодового слова Ь и лидера Р, Декодирование слова С состоит в выборе кодового слова 5 в качестве переданного и последующем пере- ходе к слову а ° где Ь=ГР~д) ° Этот метод декодирования удобно реализовать с помощью таблицы, первая строка которой есть множество кодовых слов, т.е. смежный класс 0+В, состоящий из элементов~В,...,Ь" а остальные строки соответсгвуке остальным смежным классам по В, причем первый столбеп этой таблипы есть столбец лиде- ров, Для примера 3 иэ равд.

2,2 приведем таблицу декодирова- ния (табл. 2.1), Здесь первая строка строка кодовых слов, первый столбец - столбец лидеров, Чтобы декодировать принятое слово С=С "ЬР, где Р Р лидер, следует отыскать его в таблипе и выбрать в качестве переданного кодового слово ЬР в том же столбце и первой строке, Таблица 2.1 Например, если принято слово 110011, то считается, что передано слово 010011, если принято 100101, то считается, что передано 110101, если принято 110101, то считается, что опо и было передано. Можно показать, что при таком способе декодированяя.' 1) исправлшотся те сгрокн ошибок, которые были лндерамв; 2) кодовое слово, стояшее в данном столбце, является ближайшим кодовым словом ко всем словам этого столбца Действительно; 1) если прн передаче слова Ь произошла ошибка Г, где Е - лидер, тоСл Ь+к и есть искомое представление слова Е и прн декодированик считается, что передано кодовое словоЬ, т,е.

ошибка Е исправляется; 2) пусть с переданное слово, стошцее в том же столбце, что н кодовое СЛОВО Э б . 'ТОГДа О =Ь'+Е', где Г - лидер соответствуЮШеГо смежного класса, Имеем Ф/СО'/ =/// Ю ЕСЛИЬ~ другое кодовое слово, тоС*Ь~+ Г ~ н поскольку3/-Ь/аВ, тол ~лЬ/-Ь~~ ~.с лежат в том же смежном классе, что и 8 . Следовательно, с~1с, Ь~') = игоре '.) х иг(е). 2,4, Коды Хеммиига /ООО 11111 '))М у= ~О 1 1 О О 1 11; 1010101 00000 11111111 0111100001111 10011 60110011 / 1010101010101 '~~,У ~ 10 0 О 00 ~/-т 0 1 1 0 4. Запишем систему уравнений Ь/'/" =~7, (2,1) Опишем один иэ классов групповых кодов - коды Кемминга, которые попрана~у)т одвнарную ошибку, Это (/тт, гх)-коды, где /ттлХ "/ Г'//лЯ-/ДЛЯ ЛЮбоГО 7 Схема кодярования такова: 1.

Сообшения - слова длины.с'-/- Г', где У'- произволь- ное положительное число, кодовые слова - длины,с ~-/. 2. В каждом кодовом слоэеЬ=Ь ...Ь~у / - символы, вн- декс которых является сгепенью двойки, т.е. Ь Л,Ь~М..., Ь~г являются коитрольнымн, а остальные символами сообшенвя, раслоложеинымн в том же порядке, Например, прн 7 = 4 сшлво- лы А~, ~~ 4~ ~/г контрольные Ь дч,Ал,~т 4у'Фа Ф// Ал э Я/, Д/т,Д ~- симэОлы сосбпюннэ, э, /Я ~ 3, Рассмотрим матрицуМ порядкау'хф-/,) такую, что в р -м столбце этой матрипы стоят символы двоичяого разложе- ния числа Е . Матрицы ЛУ для Г 2, 3, 4 вмеют, следователь- но, вид Например, для у~ * 3 ета система имеет вид Ьсс "Бэ +Ьн т Ьт = Ос Ь~+Бя + Ь|+Ъу =д, (2,2) Ь еЬя 'Ь~+Ьу О.

Заметим, что по построению матрипы М в каждое нз уравнений системы (2.1) входвт одни и только один символ Б се с индекс которого есть степень двойки, 5. При кодировании сообщения значения контрольных снмэоловЬ~е,Ь~~с...„Ь~х уполучим из системы (2.1). При этом символы ф, где~' йе есть степень двойки, соответствуют символам передаваемого сообщения, В качестве примера найдем порождающую матрицу для (4,7)- кода Хемминга, Для этого определим фундаментальную систему решений системы (2,2): йс 1110000, сс~ 1001100, й~ ° 0101010, сйсс 1101001, Порождающей лсатрицей будет матрипас составленкая из этих векторов 1 1 1 О 0 0 О у 1 0 0 1 1, 0 0 0 1 0 1 0 1 О 1 1 О 1 0 О 1 Схема декодирования кода Хемминга такова: пусть принято слово СеЬеб', где Ь - кодовое слово, Г - ошибка, Тогда ЬМгабс и, следовательно, (Ь ~'е ) М г= ЬМ Г+ РМ на 8 М ' .

ЕслиУМ ~ О, то считается, что ошибки не было. Так, дей ствительно, бывает, если 8 = О. Если произошла ошибка только в одной позиции, т,е, вектор ошибок б' имеет только одну единицу в с' -й позиции, то ГМ г есть вектор, совпадающий с сс -м столбцом матрицы М, т„е, двоичным разложением числа с, Тогда в переданном слове скЬсс' надо изменить символ в с' -й позиции, вычеркнуть символы, стоящие в позициях, номер которых есть степень двойки, и полученное слово считать результатом декодирования, Если ошибка допущена более чем в одной позиции, декоди.- рование дает неверный результат. Например, если строка ошибок 8 будет кодовым словом, то(5сб)МггО и мы в результате декодирования не изменим слова, Код Хемминга исправляет однократную ошибку. Если к нему добавить проверку четности, то он будет обнаруживать две ошибки, Рассмотрим пример для (4,7 )-кода Хемминс а, Пус;.ь С 0011111, Тогда л"=Ь~Г, где Ь .= 0001111 - кодовое сло- ,Е = 0010000 - строка ошибок ГМглсЬсЕ)М'=ЕМгео~д, ,37 Это есть двоичное разложение числа 3, следовательно, ошибка совершенв в третьей лозинки: С 0001111 и, декодируя, попучим слово <2 0111, 3.

АЛГЕБРА СТРУКТУРНЫХ ЧИСЕЛ В настояшее время методы дискретной мвтематики находят все большее применение прн исследовении и описании пропессов, протекаюших в системах управления. Тек, язык н методы теории графов используются для описания и исследования структурных (комбинаторных) свойств систем управления„Топологическими сгруктурамн (графамн) систем упрввлення являются свгнельныо графы, отображеюшие тем вли иным способом систему уравнений, описываюшую анелнзируемую систему, Широкое применение при исследовании систем управления нашли сягнапьиыо графы Мозоле( 1, 111, соответствуюшне системе уревлений, приведенных к причинно-следственной форме, Приоушие графу Меэона ограничения на структуру исходных уравнений снимаются при использовании графа Коутса ( 1,7с12) или обобшениого св'нального графа ( 1).

Однако методы получения системных хврэктористик на основе топологяческих структур - сигнальных грлфовне приспособлояы к их программированию нэ ЬВМ, Сиять такое ограничение позволяет элгебрапческий метод метод структурных чисел, Он предлагвет методнку отыскания некасаюшихся контуров и путей в сигнэльном графе, которая удобив для программирования на ВВМ„Соедянение топологнческих и ллгебранческих методов позволяет решить задачу автоматизированного рэсчета систелшых характеристик Подсистема таких программ и алгоритмов обеспечивает решение залечи автоматвэадни проехтвровения систем управления в совокупности с другими программными системами и алгоритмами. 3.1, Основные определения н понятия структурных чисел пусть 7ст;А - элементы произвольной природы, принндлежа- шпо множеству Х;, Рассмотрим прямое произвепенне с мно- Х,с,Л„~, ...,К;„ )' ~ = я, кА .

л к д ° (3,1) сс сс ' ° Злемшсты мво»«*стел У с обозначим ~о~в», '. сй ' )- тэс'1 "гс;,й,. » с; А >,бслсс ~»с',' х. =- ' ' ' ' ' ' ' (3.2) .„, Если~ =у. Обр: уем г; элс желтова' » с- У и сс ст1 э с '~' На каждую пару элементоваС,Ей,осу яйй ( сь' 1„Ьд, с) Х, ,Ь~, сс Ф ч. ) каложнм ограничеииес 7>с, 4 Фарг (',с - се 1. (3 4) н у ..Ф Из элементов (3,3) вновь образувм множества +~ гйС * > йС ~ . (3.5) С числом и ядка Е называется множество вида с элемептамк 3,3) при ограничениях (3,4), которое изо- (3.5 бражается в виде таблицы >К о х >с>с .

оСЕ с>» с>с множества вида ( Е Е ос,г сс (3.6) Столбцы таблицы представляют З.З). Естесгвенно считать два столбца равными, если оии состоят иэ одних и тех же элементов. По определенао структурного числа порядка Е таблипа (3,6) не содержит одинаковых столбцов, а сто>абды - одинаковых элементов, т.е.йС.эйС.(с Ф~) иск ° ~ г (с Е~ ). Перестановка элементов в столбце, в столбцов в таблице (3,6) не ведет к взменению структурного числа поряд- хаг . Два структурных числа порядкаЕ»с~ и Кр>> считаются равными тогда и только тогда, хогда из того, что йй с.сСс е г следует й» б.т' и обратно, Е Иведем множество Г, состояшюе нз элементов типа (3.6). Зададим в нем системух>> ((+),®)бинарных алгебраических операций, определякипих сумму и произведение С ой чисел по яака Е.