Файл: Бездудный, В. Г. Техника безопасности в шахтном строительстве.pdf

случае алгоритм обнаружения ошибки значительно сложнее: Z =■ Z0U1— (К —-Кош),

где Zom — ошибочная цифра; К — правильная цифра проверочного разряда; Кош — цифра проверочного разряда, полученная в результа­ те контрольных проверок.

Для рассматриваемого примера правильная цифра

1 = 8 — (7 — 6) = 7

или

Z = 8 — (9 — 8) = 7.

Если Z получится отрицательным числом, то следует брать его допол­ нение до модуля. Если Z получается больше модуля, то от Z вычитае­ тся значение модуля.

Контроль по запрещенной части кодовой комбинации основан на том, что из общего числа кодов данной длины выбирается часть кодов

скодовым расстоянием d >• 2. Остальные кодовые комбинации счи­ таются запрещенными. Появление запрещенной комбинации говорит о наличии ошибки. Например, если пятизначный двоичный код раз­ делить на две части таким образом, чтобы в одной из них разрешенными были комбинации только с четным количеством единиц, а во второй —

снечетным, то получается два отдельных кода, обнаруживающих оди­ ночную ошибку (см. тему 13). Обнаружить ошибку элементарно: про­ веркой на четность.

-В случае цифровых кодов, применяемых при механизированной об­ работке информации, в памяти машины записывается кодовая книга — перечень разрешенных комбинаций. Каждая вновь поступившая ком­ бинация сравнивается с разрешенными по кодовой книге, и при отсут­ ствии поступившей комбинации среди разрешенных вырабатывается сигнал ошибки. В качестве примера кодовой книги с d = 2 приведена

174

табл. 33. Естественно, при помощи такой кодовой книги обнаружить адрес ошибки нельзя, так как для этого кодовое расстояние должно быть d > 3.

Кодовая книга с d = 3 изображена в табл. 34. Процесс обнаруже­ ния и исправления ошибки рассмотрим на следующем примере. Пред­ положим, в результате ошибки вместо разрешенного числа 4487 при­ нято число 4488. Первая проверка: Х488, если в кодовой книге (табл. 33) есть числе, оканчивающееся на 488, то ошибка в первом раз­ ряде. Результат проверки: такого числа нет. Вторая проверка: 4X88,

если в кодовой книге есть число, которое начинается на 4 и оканчивается на 88, то ошибка во втором разряде. Результат проверки: такого числа нет. Третья проверка: 44X8, если в кодовой книге есть число, начи­ нающееся на 44 и оканчивающееся на 8, то ошибка в третьем разряде. Результат проверки: такого числа нет. Четвертая проверка: 448Х, если в кодовой книге есть число, которое начинается на 448, то ошибка в четвертом разряде. Результат проверки: такое число есть — 4487. Вывод: ошибка в четвертом разряде, цифру следует изменить на 7.

Контроль на основе запрещния использования части символов —

единственный метод, учитывающий статистику ошибок, возникающих при механизированной обработке.

Анализ ошибок, возникающих при кодировании информации на машинные носители, вызывает следующие соображения. Наибольшее количество ошибок происходит в результате того, что оператор попадает на соседние клавиши, главным образом, по вертикали. Уменьшить вероятность таких ошибок можно, исключив из шифров соседние цифры либо видоизменив клавиатуру перфоратора. Много ошибок возникает от неправильного чтения первичного документа. Путаются цифры О и 9, 4 и 9, 4 и 7. Уменьшить вероятность таких ошибок можно, исклю­ чив из шифров символы 0 и 4. Большой процент ошибок возникает

175

в результате перестановки цифр. Ликвидировать эти ошибки можно путем такого построения кода, при котором все кодовые комбинации идут в возрастающей (либо в убывающей) последовательности. Много ошибок возникает от того, что в результате неисправности машины (пер­ форатора) часть позиций на информационном носителе остается не пробитой, а это воспринимается впоследствии как 0. Для избежания таких ошибок исключают 0 из разрешенных символов кодовых ком­ бинаций.

В качестве примеров в табл. 35 и 36 приведены коды, построенные по принципу запрещения части символов. В коде табл. 35 отсутствует 0,

а цифры в каждом кодовом слове следуют в возрастающем порядке. Поэтому такой код позволяет обнаруживать: все ошибки по перестанов­ ке; все промахи на нуль; все случаи непробивки отверстий; большин­ ство ошибок, обозначенных в табл. 30 и 31 под шифрами 22, 32, 51, 52, 53, 71. Код табл. 36, в котором отсутствуют цифры 0, 4, 5 и 6, кроме перечисленных ошибок, позволяет обнаруживать все промахи на соседние клавиши по вертикали (самый большой процент ошибок) и все промахи по диагонали, в которых участвуют цифры 0, 4, 5, 6.

Анализ, проведенный в работе [1], показывает, что кодом табл. 34 обнаруживается 74,9% всех ошибок, кодом табл. 35 — 37,5%, а ко­ дом табл. 36 — 65,6%, Коэффициенты емкости этих кодов составляют

Как Видим, код табл. 36 имеет в два раза меньшую избыточность, чем код табл. 34, а процент обнаружения ошибок лишь на 9,3% меньше.' Однако, если учитывать специфику экономической информации, выигрыш в избыточности может оказаться еще более ощутимый. Так, например, при исключении трех видов клавиш используется 49 пози­ ций из 100. Двузначный код видов оплат использует только 40—45 позиций из 99 возможных (по числу видов оплат). Для такого кода

176

при исключении трех знаков помехоустойчивость значительно увели­ чится без введения дополнительной избыточности. То же самое можно сказать по поводу кодов балансовых счетов, статей цеховых и обще­ заводских расходов, групп материальных ценностей и т. д.

Сжатие технико-экономической информации при ее машинной обработке. Необходимость хранения в памяти ЭВМ огромных массивов технико-экономической информации, которые возникают в процессе

Таблица 36

Двузначный код на 21 слово (запрещены цифры 0, 4, 5, 6 и оставлены только восходящие значения цифр в числе)

ее механизированной обработки, заставляет ученых вести непрерывные поиски все более и более эффективных способов сжатия информации. Сколь бы совершенной ни была память ЭВМ, вместить в себя весь побуквенный код слов, которые составляют словари современных инфор­ мационно-поисковых и информационно-управляющих систем, она прак­ тически не может. Действительно, если взять слово «монтаж» в широко распространенном неизбыточном (т. е. в одном из кратчайших) двоич­ ном коде Бодо, то адрес этого слова занял бы 30 двоичных разрядов. Очевидно, что память машины, хранящей такие длинные адреса, не сможет хранить много слов, тем более словосочетаний или текстов. Кроме того, слишком длинные адреса усложняют и удорожают про­ цедуру поиска.

Сжатие информации представляет собой такую форму кодирования, в результате которой данному сообщению ставится в соответствие дру­ гое, более короткое. Аннотирование, реферирование и даже оптималь­ ное кодирование являются примерами сжатия информации. Однако здесь мы остановимся лишь на некоторых, наиболее характерных, способах сжатия информации непосредственно при помощи ЭВМ.

Вопросами сжатия информации машинными способами одним из первых советских ученых занялся Л. Н. Королев. Он предложил три способа сжатия:

177

1)отбрасывание разрядов слова, превышающего некоторую на­ перед заданную величину а;

2)деление кода на части, меньшие а хотя бы на один разряд, и сложение их по правилам двоичной арифметики. Например, исходный код 100011101011101111011, а = 9. Делим код на части < а 1000111, 0101110,1111011. Слагаем эти части:

1000111

+0101110

1111011

11101100

Сжатый код 11101100; 3) аналогичный способу 2, но сложение производится по моду­

лю 2. Например, для предыдущего исходного кода

1000111

001 0 11 1 0

1111011

0010010

Сжатый код 0010010. Применение этого способа позволяет почти в два раза сократить объем машинного словаря исходных слов и разме­ стить сжатый код вместе со своим номером по машинному словарю в одной ячейке.

При рассмотренных способах сжатия информации возможны ва­

— 1100 слов при а — 30 двоичных разрядов средняя вероятность неод­ нозначного сжатия с использованием третьего способа равна 0,0005.

Большой практический интерес представляет собой способ по­ словного сжатия, предложенный К- И. Курбаковым и Р. В. Смирновым. При этом кодирование осуществляется путем преобразования кодов букв исходного слова в двоичный код его адреса. Например, слово «га­ зета» кодом с т = 8 (где т — длина кодовой комбинации буквы) коди-

руется так: г — 01000111; а — 11110000; з — 01100011; е — 00010111;

т — 11011000. Сжатие такого кода К. И. Курбаков и Р. В. Смирнов предлагают осуществлять путем сложения по модулю 2 с побуквенным сдвигом в каждом разряде:

01000111 г

1001100010011

Сжатый код 1001100010011.

178

Однако сжатые коды, полученные таким способом, не всегда удо­ влетворяют требованиям к максимальной длине слова, записываемого в ЗУ. Допустимое количество разрядов сжатого кода является вполне определенной величиной, зависящей от способа кодирования и от ем­ кости ЗУ. Количество адресов, а следовательно, и количество кодов определяется из следующего соотношения:

где «марс — максимально допустимая длина (количество двоичных разрядов) сжатого кода; М — возможное количество адресов в ЗУ.

Рис. 50. К объяснению сжатия кодов путем побуквенного сдвига.

Если представить процесс побуквенного сдвига в общем виде, как показано на рис. 50, а, то длина сжатого кода

п = k -\-tn ,

где k — число побуквенных сдвигов; т — длина кодовой комбинации буквы.

Так как сдвигаются все буквы, кроме первой, то число сдвигов

k = L — 1,

где L — число букв в слове. Тогда п = т + (L — 1).

В русском языке наиболее длинные слова имеют 23—25 букв. Если принять Тмакс == 23 с условием осуществления побуквенного сдвига с каждым шагом ровно ца один разряд, для п я т могут быть получены следующие соотношения:

т— 6, «макс “ 28,

т= 7, «макс ~ 29,

т= 8; «макс = 30;

т= 9; «макс — 31.

Если значение « макс не удовлетворяет неравенству (104), конечные буквы слова можно складывать по модулю 2 без сдвига относительно

179