Файл: Самохин А.Ф. Эксплуатация цифровых вычислительных машин [учеб. пособие].pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 137
Скачиваний: 0
- 7 3-
считать, |
что |
И = СК f |
где |
С - |
целое число. |
I . |
Пусть |
3, |
р = 2, |
/77 |
= 2. |
Определим вероятность необнаружения двойных ошибок. Вероятностью
появления ошибок больших кратностей пренебрежем. |
|
||||
При двойной |
ошибке разность между правильным и искаженным |
||||
числом равна ( + |
2* + 2-* |
) . |
Разряды числа имеет |
чередующееся |
|
по mod. 5 вычеты I , 2, |
I , |
2 , I , 2, |
. . . . Одинарная ошибка |
||
вызывает изменение вычета числа на + |
I или + 2 . |
При двойной |
|||
ошибке вычет числа изменяется на величину, равную суш е или раз ности этих значений. Двойная ошибка необнаружима, если эта сум
ма или разность |
равна 0 или 3-м . |
|
|
|||
|
Всегда возможны 4 |
комбинации ошибки: 2* + 2 |
, - |
2* - 2^, |
||
i |
'l |
i |
f |
. Очевидно, если ошибки в |
обеих |
позици |
2 - |
2 |
, - 2 |
+ 2 |
|||
ях имеет одинаковые знаки, то общая ошибка кратна 3-м в случа
ях, когда один разряд четный, другой нечетный, т .е . в половине всех возможных стучаев. Если ошибки имеет разные, то ошибка
будет кратна 3-м ,когда или обе позиции четные, или обе нечет
ные, т .е . также в половине всех случаев.
Таким образом, двойные ошибки будут обнаруживаться в по ловине случаев их возникновения, т .е .
|
|
@н.о. |
~ у |
Но |
|
|
|
|
|
|
П -2 |
следовательно, |
|
п -2. |
|
|
|
|
|
|
*но. |
Ц |
|
при |
? = 10 |
п |
= 10 |
За*,8^7.
- 74-
QK0.= |
2,25 •I 0~5 |
, |
|
т .е . из 100 000 слов только в |
2,25-ти ошибки не будут |
обнару |
|
жены. |
|
|
|
Если провести |
аналогичные |
рассуждения для кода по |
inod 7, |
то окажется, что из возникших двойных ошибок только одна шес тая часть не будет обнаружена, т .е . вероятность появдения не-
обнаружимых ошибок будет в три раза меньше, чем при контроле по mod 3 ,
Таким образом, с повышением избыточности кода его коррек тирующая способность растет. Однако, чаще применяется код по
mod. 3 , так как он требует меньше избыточной аппаратуры.
§ 4 .6 . Схемы устройств для нахождения вычетов кода числа
При контроле по наименьшим вычетам необходимо иметь устройство для определения вычетов, схему сравнения контроль ных кодов и устройство для выполнения операций над контрольны ми кодами. Схема сравнения достаточно просто реализуется о помощью небольшого количества избыточной аппаратуры.
Рассмотрим способы реализации устройств для определения вычетов, называемых обычно схемами "свертки ".
По характеру построения схемы свертки можно разделить на два типа:
-схемы с последовательным переносом сигнала образования остатка,
-пирамидальные схемы, которые строятся в несколько яру
сов .
-7 5 -
Ксхемам оверлеи предъявляются требования возможно мень
шего времени образования контрольного кода и возможно меньшей нагрузки на триггеры и другие фиксирующие элементы.
Принцип построения |
схемы |
свертки по mod 3 , |
основанной |
||||||||||||
на формуле (4 .1 3 ), показан |
на рис. |
,4.1. |
|
|
|
|
|
|
|
||||||
Весовые коэффициенты четных разрядов равны единице, нечет |
|||||||||||||||
ных - двум. Поэтому достаточно |
рассмотреть |
работу |
схемы для од |
||||||||||||
ной пары разрядов |
(четного и нечетного). |
Схемы свертки в |
осталь |
||||||||||||
ных парах разрядов будут идентичш. |
|
|
|
|
|
|
|
||||||||
Состояние остатков на выходе нечетного разряда |
(Т „) |
и |
|||||||||||||
четного |
(TR_ j) |
с |
учетом |
переносов |
из младшего нечетного |
разряда |
|||||||||
(Тр.—9) для всех |
12 возможных комбинаций приведено в таблице 4. 1 . |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Таблица 4 .1 . |
||||
Перенос |
из |
(к |
- |
2 )-го |
0 0 0 0 I |
I |
I |
I |
2 |
2 2 |
2 |
||||
разряда |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Четный |
(к - |
1)-й |
|
0 I |
0 I |
0 I |
0 I |
0 |
I 0 I |
||||||
разряд |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нечетный к-й разряд |
0' |
0 |
2 2 |
0 |
0 |
2 |
2 |
0 |
0 |
2 |
2 |
||||
Перенос из |
к -го |
раз |
0 I |
2 0 I |
2 0 I |
2 0 I |
2 |
||||||||
ряда в |
(к + |
I ) —й |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||
Работа схемы свертки начинается подачей импульса образо
вания остатка в младший разряд регистре числа. Работа показан
ных на |
схеме разрядов свертки |
начинается с поступлением им |
||||
пульса |
переноса |
из |
(к |
- 2)-г о |
разряда. |
|
Допустим, |
что |
из |
(к - 2 )-го разряда |
пр’.япел перенос остат |
||
ка, равный I ( т .е . |
на шину " I " ) ; триггер |
(к - 1 )-г о разряда |
||||
- 7 6 -
Puc. k i
- 77-
находнтся в единичном состоянии и триггер "кп-г о разряда - в
единичном состоянии. Тогда импульс с шины I пройдет через по
тенциально открытый элемент И| на элемент М И р что соответст вует остатку, равному 2 , и затем - на элемент Ид и ИЛИ^, что
соответствует остатку на выходе этого разряда, равному едини це. Результат солласуется с таблицей.
Аналогично монет быть построена схема и для других модулей.
Враля образования контрольного кода будет равно
t |
= Л |
+ Т п |
’ |
LK.it. |
L{p.S. |
|
где t y у - время срабатывания фиксирующих элементов (тригге ров) ;
Т- время задержки импульса в одной вентильной груп пе (элементах И и М И ).
Для повышения быстродействия часто применяют пирамидаль ные схемы свертки. Построение пирамидальных схем свертки осно вано на применении следующего алгоритма. Согласно выведенному вш е для контроля по модулю
Иными словами, вычет числа равен сумме по модулю |
f f -жчвых |
цифр, полученных в результате группировки по Ш двоичных |
|
разрядов числа А. |
|
Сложение в пирамидальных схемах осуществляется попарно. |
|
Вначале (в первом ярусе) производится образование |
ичных |
цифр, затем (во втором ярусе) эти цифры складываются попарно,
в третьем ярусе складываются попарно полученные суммы и т .д .
до получения остатка. Блок-схема такой свертки представлена на рис. 4 .2 . Образование контрольного кода начинается подачей
- 7.9-
импульса на схемы выделения |
р |
-ичного кода. |
В качестве |
блоков сложения и выделения р |
-ичных цифр мо1ут |
|||
быть использованы схемы, подобные предыдущим. |
|
|
|
||
Время выделения кода |
^ = tp ? +TS |
, где |
S - |
число |
|
ярусов. |
|
|
|
|
|
Для контроля по mod 3 |
и mod 5 |
3 = |
П |
, |
|
т .е . S |
равно логарифму по |
основанию 2 числа разрядов, |
допол |
||
ненному до ближайшего |
большего целого числа, кратного степени |
|||
ДВУХ* |
|
|
|
|
При модуле 7 |
3 = |
&( п '- /) , где |
П ' - ближайшее |
|
число к П (большее |
П |
) , кратное степени 2. |
||
Из литературы |
|
Л .5 |
известно, |
что пирамидальные |
схемы свертки более экономичны по затрате аппаратуры. Кроме то
- 79-
го , преимуществом таких схем, как следует из формулы для вре мени, является большее быстродействие.
§ 4 .6 . Сложение и вычитание наименьших вычетов
В процессе контроля необходимо выполнять операции сложе ния, вычитания, сдвига и умножения контрольных кодов. При этом еле,дует иметь ввиду, что результат выполнения операций над вы четами должен быть наименьшим вычетом результата выполнения операции над контрольными кодами.
Рассмотрим операцию сложения наименьших вычетов
8(A) + 8(В) = 8(А *В) mod^
При сложении может встретиться два случая:
[ R ( A ) + R ( B ) ] < О |
|
|
|
d |
и |
[ 8 ( A ) + R ( В ) ] > |
|
|
В первом случае результат |
сложения вычетов является наименьшим |
|
вычетом и, следовательно, |
никаких дополнительных действий над |
|
результатом выполнять не нужно. |
|
|
Во втором случае результат не является наименьшим вычетом
так как он больше модуля. Поэтому для получения наименьшего вы чета из результата необходимо вычесть модуль. Вычитание модуля можно заменить прибавлением его инверсии. При этом обязательно
возникает единица циклического |
переноса из |
старшего разряда в |
.младший, которую необходимо учитывать. |
|
|
В случае использования |
^ = р™- / |
инверсия модуля |
равна нулю: |
|
|
= 2 т- / ~ ( 2 т- < ) ~ 0
- п о
следовательно, добавлять инверсию в этом случае нет необходи мости, достаточно лишь учесть перенос из старшего разряда, воз никающий в процессе сложения вычетов, т .е .
R (A + B )= [R(A)+R(B)+dmR (1-2m)]mod
Таким образом, для реализации операции сложения вычетов
по модулю 1 необходимо иметь т -разрядный сумма
тор с цепью циклического переноса из старшего разряда в млад ший.
Пример. R(A)~ 10movl3, R(B) =iDwocl5l R(A+&) =01 mods .
R |
( |
A |
) |
= |
10 |
+ R |
( |
в |
) |
= |
io |
R ( a ) + R |
( |
в |
) |
= ioo |
|
перенос |
|
|
|
|
l—I |
R ( A ) + R ( В ) = 01
Для сокращения записи здесь и дальше мы будем использовать
смешанную запись, записывая числа |
и вычеты в двоичной системе |
||
счисления, а величину модуля - в десятичной. |
|
|
|
Если используется модуль |
2 ™ + 1 , |
|
|
| = 2 m+ i- |
|
t ) * 0 |
|
Следовательно, в этом случае инверсию модуля добавлять необхо |
|||
димо. Сигналом на добавление может |
быть или перенос из |
( 777 + / ) -г о |
|
разряда, или сигнал от специально |
включенного |
в схему |
су ш а то - |
ра дешифратора, свидетельствующий о том, что |
число, полученное |
||
в сумматоре, больше модуля. |
|
|
|