Бройдо В.Л. Вычислительные системы, сети и телекоммуникации (2002) (1186248), страница 158
Текст из файла (страница 158)
д, При независимости возникновения искажений в символах вероятность появления однократной ошибки подчиняется биномиальному закону так, гго соотношение частот появления однократных и двукратных ошибок лежит в пределах 500 — 1000. Из этого следует, что наиболее эффективны для информационных систем коды, обнаруживаюшне и исправляющие ошибки малой кратности и, в частности, однократные ошибки.
Десятичные коды с обнаружением однократных ошибок В общем случае в исходное десятичное число (слово) вводится один или несколько дополнительных контрольных разрядов так, чтобы сумма всех цифр числа была кратна е, то есть: ~1г,А, =01подд, где А — цифра 1-го разряда числа, 1г, — весовой коэффициент ~'-го разряда числа.
В простейшем случае прн д - 10 добавлястся всего один контрольный разряд, обнаруживаются все однократные ошибки и болыцннство ошибок более высоких кратностей. 647 Достоверность информационных систем Например, исходное число 90723092001, с)гмма цифр числа равна 33.
Чтобы сумма цифр кодового слова была кратна 10, сле~й~ет добавить в конце числа цифру 7— новое число 907230920017. Это кодовое слово будет разрешенным, ибо сумма цифр у него кратна д = 10. Любая однократная ошибка (искажение одной цифры) переведет это кодовое слово в категорию запрещенных — сумма цифр не будет кратна 10. Повысить обнаруживаюшую способность кода для ошибок второй и больших кратностей (в частности, для обнаружения ошибок типа перестановок соседних цифр) можно, использовав при д - 10 следующую оптимальную последовательность весовых коэффициентов: р; = 1,7,9,3,1,7 и т. д. (в качестве р, нельзя брать значения четные или кратные 5, поскольку д - 10 - 2 5, о — составное число).
Этого же можно достигнуть и при любых значениях р„взяв в качестве модуля простое число, например ц = 11, но в последнем случае придется добавить два контрольных разряда (кстати, при двух контрольных разрядах оптимальное значение г) = 97). Десятичные коды с автоматическим исправлением однократных ошибок В качестве примера возьмем двоичный код Хзмминга, модифицированный автором на произвольную систему счисления [6, 71. В исходное т-разрядное кодовое слово вводится дополнительно я контрольных разрядов так, что их номера)' равны целой степени цифры 2: )'- 1, 2, 4, 8, 18, 2' '.
Обозначим через 1 номера разрядов в образованном кодовом слове, тогда номера контрольных разрядов будут)-). Значение символа А, вуьм контрольном разряде выбирается из условия кратности д = 10 контрольной суммы Е„соответствующей этому разряду: Е, = ~ рА, = 0 пкк110, м где п = т «-Й, 0 при Я=2/, р = 1 при ~-,'~=2/+1, 7 =1л (р, = 0 прн четном значении ближайшего большего целого частного гД и р, = 1 при нечетном значении ближайшего большего целого частного 1Д). ПРИМЕЧАНИЕ Мнемоническое правило — контрольный разряд с номером! проверяет подряд по 1 разрядов через 1разрядов, начиная с себя самого.
Приведем пример помехозашищенного кодирования. Запишем разрядную сетку (курсив) избыточного слона: 648 Глава 20. Качество и эффективность информационных систем 1 2 Э 4 5 6 7 5 9 10 11 12 1Э 14 15 6 2 9 Я О 7 2 5 Э О 9 2 О О 1 Подчеркнутые разряды считаем проверочными, а в остальные разряды записывается исходное слово — 90723092001 для кодирования. Контрольная цифра в7'-м контрольном разряде (А1, А2, А4, А8) рассчитывается так: Е~ =- А1 ч- АЗ; — А5 ч- А7 ч- А9 е А11 чА13 ч- А15 = 0 мог)10; А1 ч- 9 + 0 ч- 2 ч- 3 ч- 9 ч- 0 ч- 1 = 0 той 10, А1 - 8; Ек = А2 ч- АЗ ч- Аб ч- А7 ч- А10 ч-А11 ч- А14 ч- А15-0 шог)10, А2-2; Еч " А4 ч- А5 ь Аб ч- А7 ч- А12 ч- А13 ч. А14 ч- А15 = 0 шод10, А4 = 8; Ек = А8 ч- А9 ч.
А10 ч- А11 ч- А12 ч- А13 ч- А14 ч- А15 = 0 шос110, А8 = 5. Сформированное таким образом разрешенное избыточное кодовое слово позволяет не только обнаружить, но и автоматически исправить любую однократную ошибку. Любая однократная ошибка переведет кодовое слово в категорию запрещенных, так как хотя бы одна частная контрольная сумма Е, по модулю 10 будет отлична от О. Это определяет правило обнаружения ошибки: если проверка кодового слова после его информационного преобразования, производимая путем подсчета частных сумм Еь Еь Е,, Е,,, Е, даст хотя бы одну Е,, не равную нулю по модулю 10, значит, при преобразовании была допущена ошибка.
Для исправления ошибки следует проанализировать значения частных сумм, отличных от нуля, и определить адрес этой ошибки. При проверке могут встретиться следующие три случая: 1. Все частные суммы Е, = О. Это означает отсутствие однократных ошибок при выполнении преобразования (и с большой вероятностью — отсутствие ошибок вообще). 2. Хотя бы одна из сумм Е, не равна нулю, но все не равные нулю частные суммы Е; равны между собой (по молулю 10). Можем считать с большой вероятностью, гго произошла однократная ошибка при преобразовании; ее адрес — номер искаженного разряда в виде двоичного кода можем определить из выражения: 1.,„= Е, Е,д ...
Е» Е~ Еь где Е, = О, если Е, = О, и Е = 1 в противном случае (мнемоническое правило: адрес ошибки равен сумме индексов частных контрольных сумм, пе равных нулю). Кроме здреса ошибки, следует проанализировать значение любой из частных сумм, пе равных нулю, и значение цифры, стоящей по адресу 1„„„чтобы определить, на какую величину была допущена ошибка. Допустим, мы имеем Е, = Е,в О. Следовательно, при преобразовании произошло либо увеличение цифры, стоящей по найденному адресу 1„„„на Е, единиц, либо ее уменьшение ца 10 — Е„единиц.
В любом случае, чтобы исправить эту ошибку, можно вычислить правильное значение цифры по формуле; А, „„= (А, „— Е,)тог110. 3. Две или более частные суммы Е, не равны нулю и хотя бы две из цих не равны межлу собой. Это означает наличие ошибки кратности больше единицы, и ее исправить нельзя.
Безопасность информационных систем 7 б 9 10 11 12 13 14 15 2 6 3 О 9 2 О О г г|г г = ггг„„, — Е„= (Π— 8) пюг)10 = 2. ПРИМЕЧАНИЕ Если при вычислениях по модулю (в конечных полях Галуа) получается отрицательное число, то к нему добавляется значение модуля. Действительно, верное значение цифры в 12-м разряде — 2. Ошибка исправлена. Данный код позволяет обнаружить подавляющее число ошибок кратности 2 и выше (без их исправления).
Для более высокой зффективности обнаружения ошибок к рассматриваемому кодовому слову можно добавить еще один проверочный разряд (ггулевой), которым контролировать по шог)10 сумму всех пифр избыточного кодового слона (включая контрольные разряды). Более полное исследование зффективности рассматриваемых кодов приведено в работах [б, 8]. В!ирако известные двоичные коды Хэмминга с автоматическим исправлением ошибок являются частным случаем рассмотренных кодов при модуле г) - 2. Безопасность информационных систем Безопасность информационной системы — свойство, заключагощееся в способности системы обеспечить конфиденциальность и целостность информации, то есть защиту информации от несанкционированного доступа с целью се раскрытия, изменения или разрушения.
Информационную безопасность часто указывают среди основных информационных проблем ХХ1 века. Действительно, вопросы хищения информации, ее сознательного искажения и уничтожения часто приводят к ~рагическим для пострадавшей стороны последствиям, ведущим к разорению и банкротству фирм, к человеческим жертвам, наконец. Достаточно в качестве примера привести мировую трагедию, Теперь рассмотрим пример декодировандя. Допустим, в разрешенном кодоном слоне 2 3 4 5 б 7 в 9 го гг 12 13 г4 15 6 2 9 6 О 7 2 6 3 О 9 2 О О г допущена ошибка в 12-м разряде: вместо 2 появилась ошибочная цифра О, то есть получили кодовое слово: 1 2 3 4 5 б 6 2 9 6 О 7 Это слово относится к категории запрещенных, поскольку по модулю 10 (учитывается только разряд единиц, а десятки, сотни и т.
д. отбрасываются) Е, - О, Е, = О, Е, = 8, Е, = 8. Все не равные нулю частные контрольные суммы равны между собой и равны Е„= 8, следовательно, произошла однократная ошибка и ее можно исправить. Адрес огпибки — двоичный код номера искаженного разряда: г„„, = 1100, то есть ошибка произошла в 12 разряде (сумма индексов частных когпрольных сумм не равных 0 равна: 8 + 4 - 12). Исправляем ее: 650 Глава 20. Качество и эффективность информационных систем приведшую к жертвам нескольких тысяч людей, — атаку террористов на Всемирный торговый центр в Нью-Йорке и министерство обороны США в Вашингйэне. Подобный террористический акт был бы невозможен, если бы террористы не вывели предварительно из с~роя компьютерную систему управления безопасностью страны, то есть не разрушили бы систему информационного обеспечения безопасности.
А тысячи коммерческих компьютерных преступлений, приводящих к потерям сотен миллионов долларов, а моральные потери, связанные с хищением конфиленциальной информации... Перечень бед от нарушения безопасности информации можно было бы продолжать бесконечно (если раньше для успешного совершения революции или переворота важно было захватить почту и телеграф, то теперь необходимо парализовать системы компьютерных телекоммуникаций). Достаточно сказать, что: гз суммарный ущерб от нарушения безопасности информации в период с 1997 по 2000 год только в США составил $626 млн; гз мировой годовой ущерб от несанкционированного доступа к информации, составляющий сейчас около $0,5 млрд, ежегодно увеличивается в 1,5 раза; гз ущерб, нанесенный распространявшимся по электронной почте самым «эффективным» вирусом «11оче уоц» в 1999 году, превысил $10 млрд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
