Теория информации (стр. 16 из 29)

Этот метод позволяет обнаруживать ошибку. Но с его помощью нельзя определить, в каком разряде слова содержится ошибка, т.е. нельзя исправить ее. Кроме того, при этом методе не могут обнаруживаться ошибки четной кратности, т.е. ошибки одновременно в двух, четырех и т.д. разрядах, так как при таком четном числе ошибок не нарушается четность числа единиц в разрядах слова. Однако наряду с одиночными ошибками могут обнаруживаться ошибки, возникающие одновременно в любом нечетном числе разрядов.

На практике часто вместо признака четности используется признак нечетности, т.е. цифра контрольного разряда выбирается такой, чтобы общее число единиц в разрядах слова было нечетным. При этом, если имеет место, например, обрыв линии связи, это обнаруживается, так как принимаемые слова будут иметь 0 во всех разрядах и нарушится принцип нечетности числа единиц.

Рассмотрим схемы, выполняющие операцию проверки на четность (нечетность). Проверка на четность требует суммирования по модулю 2 цифр разрядов слова. Если а

, а ,…, а — цифры разрядов, результат проверки на четность определится выражением р = а -а -а - ,…, -а . Если р = 0, то число единиц в разрядах слова четно, в противном случае оно нечетно.

Наиболее просто эта операция реализуется, когда контролируемое слово передается в последовательной форме. Суммирование в этом случае может быть выполнено в последовательности р = ...((a

-а ) -а ) - ... -а . К результату суммирования р первых разрядов прибавляется цифра очередного поступающего разряда (i + 1), находится результат суммирования (i + 1) разрядов p = p - а , и так до тех пор, пока не будут просуммированы цифры всех разрядов.

Из таблицы истинности

Таблица 1

для операции p

= p - а (табл. 1) видно, что лог.0 не должен менять состояния устройства суммирования (p = p ), лог.1 переводит устройство в новое состояние (p = ). Эта логика соответствует работе триггера со счетным входом (рис.1).

Рис.1. Триггер со счетным входом.

Действительно, пусть триггер был предварительно установлен в состояние 0, после чего на его синхронизирующий вход стали поступать логические уровни, соответствующие цифрам контролируемого слова. При этом первая лог.1 переведет триггер в состояние 1, вторая лог. 1 вернет триггер в состояние 0 и т.д. Следовательно, после подачи четного числа единиц триггер окажется в состоянии р = 0; при поступлении нечетного числа единиц — в состоянии р = 1.

Если разряды контролируемого слова передаются в параллельной форме, то последовательность действий при проверке на четность может быть следующая:

Согласно этому выражению для нахождения р вначале попарно суммируются по модулю 2 цифры разрядов контролируемого слова, далее полученные результаты также суммируются попарно и т.д.

Этот принцип вычисления р использован в схеме проверки на четность на рис.2.

Рис.2. Схема проверки на четность.

Цифры разрядов (и их инверсии) поступают на входы элементов (на рис.2 обозначены =1) первого яруса схемы, в которых они попарно суммируются по модулю 2. Полученные результаты попарно суммируются в элементах второго яруса и т.д.

Результат проверки на четность образуется на выходе элемента старшего яруса. Каждый из элементов схемы реализует следующую логическую функцию:

Построенная по данному выражению схема элемента, выполняющего операцию суммирования по модулю 2, приведена на рис.3.

Рис.3.Схема элемента, выполняющего операцию суммирования по модулю 2.

Определим число ярусов и число элементов в этой схеме проверки на четность. Пусть число разрядов n контролируемого слова составляет целую степень двух. Число элементов в отдельных ярусах а

составляет геометрическую прогрессию 1,2,4,8,..., n/2, знаменатель которой q = 2. Для последнего k-то яруса а = 1, для первого яруса а =a q откуда 2 = n/2 или 2 = n.

Из этого соотношения можно найти число ярусов k. Число суммирующих элементов в схеме равно сумме членов приведенной выше геометрической прогрессии:

Контроль арифметических операций

В устройствах хранения и передачи информации одиночная ошибка вызывала искажение цифры лишь одного разряда слова. При выполнении арифметических операций одиночная ошибка в получаемом результате может вызвать искажение одновременно группы разрядов. Пусть в суммирующем счетчике хранится число N

= 10111 и на вход поступает очередная единица. Произойдет сложение: N = N +1. При этом

Пусть в процессе суммирования из-за ошибочной работы устройства не будет передан перенос из 2-го разряда в 3-й. Такая одиночная ошибка приведет к следующему результату:

Сравнивая ошибочный результат N

с правильным N , видим, что они различаются в двух разрядах. Тем не менее считаем, что в N содержится одиночная ошибка. Во всех случаях, когда ошибочный результат связан с арифметическим прибавлением (или вычитанием) ошибочной единицы к одному из разрядов, имеет место одиночная ошибка. И если ошибочный результат может быть получен из правильного результата путем арифметического суммирования (или вычитания) единицы не менее чем в k разрядах, кратность ошибки равна k.

Для контроля арифметических операций чаще всего используется контроль по модулю q. Этот метод более универсален и годится также для контроля устройств хранения и передачи информации. Сущность метода состоит в следующем.

Контролируемое число N арифметически делится на q, и выделяется остаток r

. Остаток вписывается в контрольные разряды числа N вслед за его информационными разрядами. Принятое число N* делится на q и выделяется остаток r *. Эту операцию выполняет устройство свертки по модулю q (рис.4).