Файл: Самохин А.Ф. Эксплуатация цифровых вычислительных машин [учеб. пособие].pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 143
Скачиваний: 0
-Ц7-
Втаблице 3 .4 показан семиразрядный код Хэмминга, обес
печивающий исправление |
одиночных ошибок. |
|
|
|
||||||
|
|
|
|
|
|
|
Таблица 3 .4 . |
|
||
|
Двоичный |
Код |
Двоичный |
К од. . |
||||||
|
код |
Хэмминга |
|
код |
Хэмминга |
|
||||
|
ОООС |
0000000 |
|
ОНО |
|
оноон |
|
|||
|
0001 |
0000III |
|
О Ш |
|
0II0I00 |
|
|||
|
0010 |
00II00I |
|
1000 |
|
I00I0II |
|
|||
|
ООН |
ооипо |
|
1001 |
|
IOOIIOO |
|
|||
|
0100 |
0I0I0I0 |
|
1010 |
|
I0I00I0 |
|
|||
|
0101 |
oioifoi |
|
• |
а |
• |
а • а |
а |
|
|
|
Проверка осуществляется в соответствии с таблицей 3 .3 . |
|||||||||
Пусть передано число 6, что соответствует коду |
0 II0 0 II, а при |
|||||||||
нят код 0I000II, |
т .е . |
произошла ошибка в |
5-й позиции. . |
|||||||
Первая проверка |
(1 ,3 ,5 ,7 ) |
дает |
I , |
вторая |
проверка |
(2 ,3 ,6 ,7 ) |
||||
дает |
0 и третья |
(4 ,5 ,6 ,7 ) |
дает |
I . |
Таким образом, |
номер ошибоч |
||||
ной |
позиции 101 |
(5 ) . |
|
|
|
|
|
|
|
|
Сравнивать код с проверкой на четность и код Хэмминга трудно, так как первый используется только для обнаружения оши бок, второй же позволяет и исправлять.
Сравнение можно провести для случая, когда код Хэмминга используется только для обнаружения, например, одиночных и двойных ошибок при d — 3. В этом случае можно, пренебрегая ошибками высших кратностей, считать, что вероятность необнару-
жимых ошибок приблизительно равна вероятности тройных ошибок,
- 48-
т ,е . |
|
|
|
|
|
Q . m - ° 3 |
|
° ' 6 ' |
|
Сравнение следует проводить при одинаковой информационной |
||||
возможности |
кода, т ,е . |
|
|
|
|
|
^ л-г |
~ К их |
' |
Если |
принять |
те же условия, что в рассмотренном выше примере |
||
для |
кода с проверкой на |
четность, |
то для кода Хэмминга |
|
Q h.0 = 0 5 - 1 0 ' 7 ,
т .е . корректирующая способность этого кода выше, что и сле довало ожидать.
Для образования кода Хэмминга (кодирования) необходимо
провести я? проверок на четность и результаты занести в соот
ветствующие позиции кода, в которых до выполнения кодирования
должны быть записаны |
нули. Есе проверки и запись контрольных |
||
|
|
Числоt |
|
г |
Р е г и с т р к ода |
П |
|
'— |
5 7 |
Г - |
S 617 |
3 |
3 Б 7 |
||
m2 |
|
m i ___ 1 |
m 2 | |
|
л * . |
к Тг |
к Тц |
|
__ |
|
|
Рис. 5. if.
-ча-
знаков могут осуществляться одновременно. Сумматоры для про верки групп на четность строятся по тому же способу, что был рассмотрен раньше. Схема кодирующего устройства для семираз рядного кода показана на рис. 3 .4 .
В некоторых схемах число на кодирующее устройство пода ется с одного регистра, а запись полученного кода (числа и контрольных знаков) производится на другой регистр.
Декодирующее устройство для исправления ошибок (р и с.3 .5 )
содержит регистр кода, ГП сумматоров для проверки на четность,
регистр ошибок на 777 разрядов и дешифратор.
Код гиола
Рис. 3.5.
-50-
Врезультате проверок в регистре ошибок записывается номер ошибочной позиции. Выхода дешифратора поданы на счетные входа триггеров регистра кода. Дешифратор расшифровывает адрес ошибоч
ной позиции, обеспечивая передачу исправляющего импульса на счет ный вход триггера в ошибочной позиции. В результате происходит исправление ошибки.
§ 3 .4 . Циклические коды
Циклические кода находят применение в системах с последова
тельной передачей кодов. Характерная особенность циклических
кодов состоит |
в том, что если Л -значная |
кодовая комбинация |
йП1 |
принадлежит к данному коду, |
то и комбинация |
Qn.f , |
Qп-2 • П0ЛУченная циклической перестановкой |
|
знаков, также принадлежит к этому коду.
Мы ограничимся рассмотрением некоторых циклических кодов,
применяемых для контроля записи и чтения во внешних накопителях ЦВМ.
В циклических кодах двоично кодированное |
Л -разрядное чис |
||
до представляется полиномом ( П-1 ) - й степени |
некоторой |
пере |
|
менной X |
. Коэффициентами при этом являются двоичные |
знаки |
|
соответствующих разрядов кода. Так, например, код I0II00I пред-
отавдяется полиномом 6-й степени
X s * X^-h Х 3+Х ° .
Такие полиномы рассматриваются в соответствии с законами обычной алгебры о той лишь разницей, что сложение и вычитание заменяются сложением по модулю два.
Контрольные знаки в коде располагаются в младших разрядах.
Код образуется с помощью так называемого порокдаицего поли нома Р (х ) степени Л7 .
Видом этого полинома определяется избыточность и корректирующая
способность |
кода. |
|
|
|
|
|
|
|
|
|
|
|
|||
Кодовым полиномом |
|
называется полином |
степени, |
меньшей |
|||||||||||
Пи +/П , |
если он делится без остатка |
на порождающий полином |
|||||||||||||
степени |
т . |
|
|
|
|
|
|
|
|
|
|
|
|||
Принятая кодовая |
комбинапия |
И (х) , |
если |
нет ошибок, равна |
|||||||||||
F(x) , т .е . |
Н(Т.)$0 -Т (х) , и, |
|
следовательно, |
Н (х) |
делится |
||||||||||
на Р(х) без |
остатка. |
Если же |
в слове |
возникла |
обнар,ужимая |
||||||||||
ошибка, полином Н(х) не |
будет |
делиться |
на |
Р(х) без |
остатка, |
||||||||||
что и-служит признаком ошибки. |
|
|
|
|
|
|
|
|
|||||||
Образование кода осуществляется следующим образом. |
|
||||||||||||||
Информационный полином |
G(x) степени,меньшей |
Пи , который |
|||||||||||||
нужно закодировать, умножается на |
X 171 , |
что |
|
соответствует сдви |
|||||||||||
гу на |
ТП |
разрядов влево. Полученный таким образом полином де |
|||||||||||||
лится |
на |
? (х ) для определения |
остатка |
Р (х ) |
. |
Остаток |
|||||||||
складывается |
по модулю 2 |
с |
X m ■Q (x) |
и таким образом полу |
|||||||||||
чается |
кодовый полином. |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
F ( x ) - x m G(x) © |
Р (х ) . |
|
(3 .7 ) |
||||||||
Покажем, |
что Т (х ) |
|
при этом делится |
на |
|
Р (х ) , |
а Л(х) |
||||||||
представляет контрольные знаки и занимает |
не |
более /77 |
млад |
||||||||||||
ших членов полинома |
F ( х ) . |
|
|
|
|
|
|
|
|
||||||
Можно записать |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
x mG(x) = Q(T> Р(х) ® Ъ(Я), |
|
|
|||||||||
где Q (х ) |
- |
частное от деления |
СС^-б (X) |
|
на Р (х ) . |
||||||||||
Так как сложение и вычитание по модулю 2 - |
одно и то же, то пе |
||||||||||||||
ренеся Р(Х) |
в левую часть, мы получим |
|
|
|
|
|
|
||||||||
|
|
F (x) = ccmG(x) ®R(x)=Q(x) P fx). |
|
|
|
||||||||||