Файл: Самохин А.Ф. Эксплуатация цифровых вычислительных машин [учеб. пособие].pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 142
Скачиваний: 0
- н о -
содержать хотя бы одну единицу (в контрольном разряде). Это
дает возможность отличить полное отсутствие передачи информации от передачи нуля.
Код с проверкой на четность имеет небольшую избыточность.
Вместе с тем, он обладает достаточно большой корректирующей
сп особн ость »., так как позволяет обнаруживать все одиночные
ошибки а значительную часть групповых. Для оценки эффективнос
ти кода найдем вероятность того , что в принятом слове возник нет необнаруживаемая ошибка.
При параллельной передаче кодов, как было показано, вероят
ность |
появления |
I -кратной ошибки в слове определяется из |
|||
биномиального закона распределения вероятностей. |
|||||
|
Q i = Cn(),l(1-t)f |
* , |
( = 0,1,2, ... ,п , |
||
или, |
обозначив |
~ ^ |
~ |
’ |
|
|
|
|
|
|
(З.'Д) |
Воспользуемся формулоД разложения |
бинома |
||||
|
/ |
\^ |
^Г" л ^ I П~1 |
||
|
|
|
|
|
(3 .3 ) |
1 |
|
h £ „ с‘ / \ ^ - / |
|||
|
|
|
|
|
(3 .4 ) |
В выражении (3 .3 ) в правой части имеется сумма вероятностей появления любого события (не Пбявления ошибки и появления люг-
бой кратности). В правой части выражения (3 .4 ) - разность ве роятностей событий четной и нечетной кратностей.
- Щ-
Если сложить правые и левые части этих выражений, то в правой части мы получим удвоенную сумму вероятностей событий четной кратности, т .е . вероятность тох’о , что либо ошибки не будет,
либо будет необнаруживаемая ошибка четной кратности, опреде лится выражением
Q?em. ~ 2 |
+ |
2 t-p + ( ^ ) ] |
или, после подстановки |
= / - |
^7, |
Qvem. = Т + |
|
■ |
Вероятность того, что ошибка не возникнет
а„= (#-»)".
Очевидно, вероятность возникновения необнарукиваемой ошибки
|
Qtieo&H. |
Q?ef7!~Qo 2 * 2 |
(^~р) •(3.5) |
Приведенные |
выкладки справедливы, так как события несовместны. |
||
При J = 10-3 |
и 71 = 10 |
Qq= 0,99004 , |
# четн = 0,99009 |
и Q нео(5 = |
0,00005 = |
5 -I0 "5 . |
|
Вероятность же появления ошибки при отсутствии контроля
%Ш.6.К = 1 ~ Qo = 1 ~ 0,99004 = 0,00996 ,
т .е . без контроля приходится одна ошибка на 100 принятых слов, при контроле - одна ошибка на 20 000 слов.
Код с проверкой на четность вследствие своей высокой эф фективности при сравнительно малой избыточности широко исполь зуется в ЭЦВМ. Однако в тех случаях, когда удельный вес груп повых ошибок сравнительно высок, как, например, во внешних накопителях, либо применяют другие кода или дополнительные тех -
JaK.HjV.
- 42-
нические средства, либо увеличивают избыточность кода с про
веркой на четность. Так, например, при записи во внешние нако пители последовательно-параллельным кодом часто используется контроль на четность каждой строки или столбца. В случае про верки на четность и строки, и столбцов может быть осуществле но исправление одиночных ошибок. Однако такой код будет обла дать достаточно большой избыточностью.
Наиболее |
просто выделение контрольного знака четности |
(нечетности) |
выполняется при последовательной передаче кода |
(рис. 3 .1 ) . |
|
Кодируемое аго&о
передачу
(n+i)-u сдВшающий импульс.
Рис. 3.1.
Кодируемое слово подается поразрядно на передачу и на счет ный вход контрольного триггера. В исходном состоянии триггер находится в нулевом состоянии.
Если в слове четное количество единиц, после передачи триггер останется в нулевом состоянии, если - нечетное - в
единичном. Последний (п-ч)-и сдвигающий импульс пропускает анак четности в линию, присоединив его таким образом к слову.
- ц з -
При контроле на четнсоть параллельного кода для -выделения контрольного знака может быть использована схема последователь ного сложения по модулю 2 всех цифр всех разрядов. Однако при.
этом время формирования знака четности будет равно
ta x = tips. + r tf',
где ^(р.Э. ~ время переходного процесса в фиксирующих элементах;
Т- время задержки сигнала в сумматоре по модулю 2;
П- число разрядов.
Поэтому для формирования знака четности при параллельной пере даче слова чаще используются пирамидальные схемы попарного сло жения цифр по модулю 2 (рис. 3 .2 ).
Рис. 3.2.
В качестве логических элементов в этих схемах используются сумматоры по модулю 2.
Построение кодирующего устройства для выделения знака чет ности по пирамидальной схеме позволяет существенно сокра-
- w -
тить время кодированяя по сравнению со схемой последовательно го опроса всех разрядов.
Количество ступеней в схеме выделения контрольного знака
определяется |
из |
выражения |
|
|
|
$ = |
g п |
с округлением в |
сторону увеличения. Время формирования контроль |
||
ного знака : |
t кк ~ tcp.3. + £'£'• |
||
В случае передачи последовательно-параллельным кодом можно проверять на четность с помощью пирамидальной схемы каж
дую строку и сигнал четности (нечетности) в строке подавать на счетный вход триггера. После проверки всех строк триггер будет установлен в положение, соответствующее четности (нечет ности) всего слова.
Проверка правильности передачи слова (декодирование)
выполняется с помощью той же схемы образования знака четности,
с той лишь разницей, что в образовании контрольной цифры прини мает участие и контрольный разряд. Равенство контрольной циф
ры нулю свидетельствует |
об отсутствии ошибки . |
§ 3 .3 . |
Коды Хэмминга |
Кода Хэмминга имеют большую относительную избыточность, |
|
чем кода с проверкой на |
четность , и используются обычно либо |
для исправления одиночных ошибок, либо для исправления одиноч
ных и обнаружения двойных ошибок |
при |
ol = 4. |
|
В таком коде каждый |
из " И |
" контрольных знаков явля |
|
ется знаком четности для |
определенной |
группы информационных |
|
символов. При декодировании осуществляется " 777 " проверок на
- 45-
четность, причем, в каждую проверку включается и соответству
ющий контрольный разряд, В результате проверок в соответству ющий разрял регистра ошибок записывается "О", если проверка
была успешной, и "I" - в противном случае. Группы для провер ки образуются таким образом, что в регистре ошибок получается
" ГМ "-разрядное число, показывающее номер позиции ошибочного
разряда. Это дает основание для исправления.. При отсутствии ошибок содержимое регистра ошибок равно нулю.
Так как в регистре ошибок для случая исправления одиноч
ных ошибок должен содержаться код, однозначно определяющий по
зицию ошибки или ее отсутствие, |
то |
он должен содержать |
столько |
|||||||||
символов, |
чтобы |
обеспечить |
" Л + 1 |
" комбинаций. Отсюда следу |
||||||||
ет, что в этом случае количество контрольных разрядов |
можно оп |
|||||||||||
ределить |
из |
выражения |
|
|
|
|
|
|
|
|||
|
|
|
т>1оу2(п + 1) |
и |
|
ли± n-fo^Cn+J), |
||||||
Здесь |
JT - |
количество |
контрольных разрядов; |
|
|
|||||||
|
ftu - |
количество |
информационных разрядов; . |
|
|
|||||||
|
П - суммарное количество разрядов в коде. |
|
|
|||||||||
Значения ГП и |
П-и для некоторых кодов |
приведены в |
таблице 3 .2 . |
|||||||||
|
|
|
|
|
|
|
|
|
|
Таблица 3 .2 . |
||
п |
3 |
4 |
5 |
7 |
8 9 |
10 |
II |
12 |
13 |
14 15 16 |
17 |
18 |
Пч
т
I |
I |
2 |
4 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
II |
II |
12 |
13 |
2 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
Как видно из таблицы, избыточность кода достаточно |
высокая, |
ппичем, с увеличением разрядности относительная |
избыточность |
-О б
ладает................. |
- |
На рис. 3 .3 |
показан код Хэмминга, содержащий 4 контроль |
ных и II информационных разрядов. |
|
Позиции |
кода |
|
Контрольные |
разряды |
|
||||||
|
_______________________ Л _____________________ |
|
|||||||||
к |
Хэмминга |
|
|
|
|
|
|
|
2 1 |
2 ° |
|
-------------v -------------- |
|
|
|
|
|
|
|
||||
15 |
14 15 |
12 11 10 |
9 |
8 7 |
6 |
5 |
|
Ц |
3 |
2 |
1 |
2ю 2? 2я 27 2 е 25 2Ц |
2* 2 2 2 У |
|
|
|
|
||||||
|
1/шрормациионные разряды |
|
|
|
|
|
|
||||
|
|
Рис. 3 .3 . |
|
|
|
|
|
|
|
||
Контрольные газряды выделены жирным шрифтом. |
|
|
|
|
|||||||
|
Группы разрядов, входящих в каждую проверку,и соответству |
||||||||||
ющие позиции контрольных разрядов показаны в |
таблице 3 .3 . |
||||||||||
|
|
|
|
|
|
|
Таблица 3 .3 . |
|
|||
|
Номер |
Позиция конт |
|
Проверяемые |
позиции |
|
|||||
|
проверки |
рольного |
знака |
|
|
|
|
|
|
|
|
|
I ........ |
I |
|
I , |
3 , |
5, |
7 , |
9, И , 13, 15 |
|||
|
2 |
2 |
|
2 , |
3 , 6 , 7 , |
10, И , |
14, 15 |
||||
|
3 |
4 |
|
4 , |
5, |
6, |
7 , |
12, 13, |
14, |
15 |
|
|
4 |
8 |
|
8, |
9, |
10, |
I I , |
12, 13, 14, 15 |
|||