Файл: Самохин А.Ф. Эксплуатация цифровых вычислительных машин [учеб. пособие].pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.06.2024

Просмотров: 140

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

-52-

Следовательно,

Г(х)

делится на Р(х) без

остатка

и являет­

ся, таким образом, кодовым полиномом.

 

 

Полином X 6(т) имеет нулевые члены в

Ш младших разря­

дах, а И(х) имеет

степень меньше

ГП , следовательно, в резуль­

тате сложения по модулю этих двух

полиномов в /77

младших раз­

рядах расположится остаток Р(х) ,

представляющий контрольные

знаки, а в Пи

старших разрядах

- информационный полином G(x).

Рассмотрим пример кодирования 10-разрядного числа I000III00I,

которое представляется полиномом 9-й степени.

G(x) = OC9+ocS+х 9+х3+4.

Для кодирования выберем порождающий полином 4-й отепени

Р(х)=х‘,+Х + i

 

X kG ( x ) =

e x '3* ос 9 ф х * +

х 9+ х Ч.

Делим Х Ч& ( х ) на

Р(х) :

 

^ X ' 3+ Х 9+ X f + х 7ф х Ч

X + Х -ф i

®

Х п + Х°+ X 9

Х д+Х6ФХ1/+

ъ Х ,о + 0С>+х7+ х ч

 

® х"+ х7*

а:6

 

_

х 6+ х ч

 

+ X * + X s +

х ц

 

Х 3 ФХ

£ ( х ) = Х 3+я

-53-

Таким образом, кодовый полином будет иметь вид:

Г(х) = ( x f3+ scg+ X'g+ x 7+ x ‘')® C x 3+ х )

=

 

= ccl3-h осд+ т! + х 7+ х 1*+х 3+ эс

 

что соответствует

коду 10001II00II0IC) .

 

 

к .р .

 

Практически

процедура получения остатка еще более

проста.

Так как частное нас не интересует, остаток можно получить после­

довательным сложением по mod2 кода,

соответствующего

порож­

дающему полиному из информационного кода,

сдвинутого на

W

разрядов влево. При каждом очередном

сложении код порождающего

полинома совмещается

своим старшим

разрядом со старшим

знача­

щим разрядом кодируемого полинома.

 

 

 

 

Пусть необходимо

закодировать

число

I000III00I с помощью

порождающего полинома

,М,

 

 

которому соответствует

Р(х) =ХЧ+Х+ {

 

код ШОП.

 

 

 

 

 

С,двигаем кодируемое число на четыре разряда влево и производим последовательное сложение по mod 2 код порождающего полинома:

10001110010000

©1001 1

Л00010110010000

©10011

©

00101010000

3 .8 .

10011

 

©

001100000

 

10011

 

©

0101100

 

 

10011

 

001010 - остаток

Таким образом, циклический код будет иметь вид:

I О О О I I I О О I 1 0 1 0

 

информационная

контрольные

 

часть

разряды

Этот алгоритм при последовательной передаче кодов реаяизу-

ei с.г достаточно просто.

 

 

Проблема

разработки

циклического

кода сводится к нахождению

■° >р сдающего

полинома, обеспечивающего

выполнение ноставлепной

залечи. При этом руководствуются следующим отправкам положени-

Закодированное

слово,

содержащее

ошибки, можно записать и виде

 

 

 

 

 

 

И ( а ) = Г(х) ® Е (х ) ,

 

 

 

где

£ (эс)

-

модель

ошибок, т .е .

полином той же степени,

что

F(x)

,

имеющий ненулевые члены в каждой ошябо’йюй позиции

полинома

 

Н М .

 

 

 

 

 

 

 

 

 

 

Если

И (X)

не делится на

Р ( х )

,

имеется ошибка.

 

Если Н(х)

 

делится

на Р(ос)

, то либо ошибки нет, либо

 

ошибка такова, что Е (х )

также дичится на

Р ( х ) .

Следова­

тельно, модель ошибок обнаружила только

 

тогда, когда

Е ( х )

не

делится на

 

Р (х ) .

Такал образом,

порождающий полином Р (я )

должен бить выбран таяш , чтобы

Е(Х)

 

при контролируемых

 

ошибках

не

делилась

на Р ( х )

. Кроме того , полином

Р(х) не

должен быть кратным

X ,

т .е .

должен обязательно иметь нуле­

вой член, так как в противном случае и кодовый полином не бу­

дет никогда иметь нулевого члена, т .е .

в

одной позиции кода

 

всегда

будет

ноль.

Но такая

позиция

не

несет

информации: и,

сяе—

- 55-

довательяо, бесполезна.

 

 

 

Рассмотрим

нахождение

Р (х ) для обнаружения одиночных

ошибок.

 

 

 

 

 

В этом случае,

очевидно,

модель ошибок будет

иметь вид Е(х)=Х

(ошибка произошла в

*

-й

I

не делится на лю­

i

позиции). Но ОС

бой полином с числом членов больше одного. Простейшим полино­ мом с числом членов больше одного, дающим код с минимальной из­

быточностью,

является

 

 

 

Р (х)

= 1+ X .

Остаток

от деления кодового

полинома на /+ X имеет нулевую

степень,

т .е .

в коде будет

о,дин контрольный знак. Можно пока­

зать, что назначение контрольного знака состоит в том, чтобы сделать число единиц в коде четным.

Если F(x) - кодовый полином, то он делится на Р(х)

без остатка. Следовательно, можно записать

Р(х) =-Р‘( х ) й ( х ) = ({+х)-Q ( x ) .

Но в результате умножения полинома на двучлен получается поли­

ном с четным числом членов,и, следовательно,

в кодовой

комби­

нации всегда будет четное число единиц.

 

 

 

 

В случае минимального

кодового

расстояния

d = 3

для

обнаружения двойных ошибок, очевидно, модель ошибок будет

Е ( х ) = X 1+

= х 1( / + x J l ) .

 

Л этом случае полином

ш

должен быть выбран таким, чтобы

( i + X^~L ) не

делилооь на

Р(х)

(

х {

 

не делится на

Р(%) , так

как

последний не кратен

X

) .

Порождающие

полиномы для кода

с

d -S

при различной длине кода имеют вид:

 

 

 

 

 

- 5 6

-

 

 

 

 

 

 

ДЛЯ

Л

£

7

Р ( х )

=

 

 

 

 

 

для

п

£

/5

Р ( Х )

=

X

4+ X + i

 

 

 

ДЛЯ

п

б з ;

Р ( л )

=

х *+ х 2* -1

 

 

 

В таблице

3 .5 приведен семизначный циклический код дяя

 

чисел

от 0 до

9.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблица 3 .5 .

Число Двоичный код Циклический

Число

Двоичный код Циклический

 

 

 

 

код

 

 

 

 

 

код

 

0

0000

 

 

0000

000

 

5

 

0101

0101

100

I

0001

 

 

0001

ОН

 

6

 

ОНО

ОНО 001

2

0010

 

 

0010

НО

 

7

 

О Ш

О Ш 010

3

ООН

 

 

ООН 101

 

8

 

1000

1000

101

4

0100

 

 

0100

I I I

 

9

 

1001

1001

НО

Здесь так же, как в коде Хэмминга, на четыре информационных

 

знака приходится три

контрольных. Этот

код может быть использо­

ван для исправления ошибок,

так

как между остатком

(контроль­

ной частью)и моделью одиночных ошибок имеется однозначное со ­

ответствие. Ошибке в любой из

П

позиций соответствует один

из 2

- 1 ненулевых остатков.

 

 

 

 

Схема для кодирования и декодирования последовательного

кода

по порождающему полиному

Р (х)

’ +J

показана на

рис.

3 .6 .

В основу работы схемы положен алгоритм,

рассмотренный

в примере

(3 .8 ) . Как видно из

примера,, даш шеажучшжя о статка,

достаточно в старшем значащем разряде шящщуаюзй® ■акаа я в

двух

разрядах, отстоящих от него на две шашициг. иэвеяшчь с о -

Смотрите также файлы