Файл: Толстоусов, Г. Н. Прикладная теория информации учеб. пособие.pdf

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

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

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

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

Добавлен: 30.10.2024

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

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

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

а контрольное число вычисляться по формулам

х 1= е / ©

с ' 0 с? ® с ', 1

 

Яя.=еі® с 'а ѳ с 6'® сJ,

Ш:з)

Так, если

произошла ошибка б информационном

символе Cs ' ,

то контрольное

число

Х.= х,х^рс3= Ю І, что соответствует чис­

лу 5 в двоичной системе.

В заключение отметим, что в коде "7.4" при появлении мно­ гократных ошибок контрольное число также может отличаться от нуля. Однако декодирование в этом случае будет проведено непра­ вильно, так как оно рассчитано на исправление лишь одиночных ошибок.

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

мер, ОН, НО, Ю І.

 

 

 

 

Комбинации

п,

-разрядного двоичного циклического

кода

удобно

представлять

в виде

полиномов степени

( л -4) ,

коэффи­

циентами которого

являются

символы кодовой комбинации. Например:

ОН = 0

I X ' + I Х°

= X + I ; НО =

Л>

; ЮІ =

=I .

Другое важное свойство циклического кода заключается в том, что построение кодовой комбинации возможно путем умножения ком­

бинации первичного кода на некоторый порождающий полином

<Z(x):

А(х,)=А *(х) •С(х.).

Например, кодовая комбинация первичного кода А* = х. = ю при порождающем полиноме Сг(х) -= х + I образует следующую кодовую комбинацию циклического кода:

А(х)-A*(x)Qlx.) =xfxi-i)=x*-+x~ НО.

75

Эти свойства циклического кода приводят к сравнительно не­ сложным техническим средствам кодирования и декодирования, что объясняет широкое применение кода.

При образовании циклического кода используются следующие операции. В качестве слонения - сложение по модулю два. Вычита­ ние идентично сложению по модулю два, например:

® 101

Ѳ 011

w

II I

^ I O I

 

010

HO

Определим операцию умножения. При умножении полиномов по обыч­ ным правилам с приведением подобных членов по модулю два может

нарушиться свойство цикличности, т .е .

может быть получен поли­

ном степени выше, чем

/ъ - I . Поэтому операция умножения ве­

дется но следующим правилам:

 

 

 

 

1. Полиномы перемножаются по обычным правилам с приведени­

ем подобных членов по модулю два.

 

 

П/

2. Если старшая степень полученного полинома не превышает

- I ,

то этот

результат является

окончательным.

п

3. Если старшзя степень полученного полинома превышает

- I ,

то этот полином делится на

 

+ I , и результатом ум­

ножения считается остаток от деления.

 

 

 

 

Действительно, один такт циклического переиоса эквивален­

тен

умножению не

X

. Но кодовая комбинация

+

О о

после у м н о ж е н и я ^ . , +ah.iXn'+'...+CL0)x должна в ре­

зультате

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

переноса образовать коыоимацию

получим

, + djx, + CCn.-i

• Выполняя действия, указанные в п .І-3 ,

 

 

 

 

 

 

 

a n.-1x '+ a n.-z.xп +... ä 0 X

І Л І £ / _

 

Ѳ а.п.<хлч.ал -<

 

I

a «-i

 

 

 

 

 

 

Ä / w -о с т а т о к .

Видно, что остаток равен искомой комбинации.

 

 

Рассмотрим требования, предъявляемые к порождающему поли­

ному

Сг(зо) . Во-первых, все комбинации

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

76

/4(х)должны долиться на него без остатка, так как имеет мес­ то соотношение

А(ос.)~А*(х)'£(х).

Кроме того, все комбинации могут быть получены из любой одной циклическими перестановками, т .е . умножением на Тогда в соот­ ветствии с введенными правилами умножения между двумя произволь­ ными комбинациями А^(л)а ^(-Сосуществует соотношение

 

 

Ас(х,) -X*

 

 

A jfr)

 

 

 

 

 

х л +і

~L

х л+і ’

 

 

 

где

С = 0,

если

степень

 

полинома Аі(х) сс*

меньше

п -

I,

либо

С = 1 ,

если

степень

полинома А^(х) зс к больше

/2. -

1;

Аі

№ - остаток

от деления.

 

 

 

 

 

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

записать

 

 

 

 

A *(x)x*‘£(x}-C(x°+/)+A;(x)

 

 

 

или

 

 

 

 

 

 

 

 

 

 

 

-Ы * > -А У х )* * -С

ж * ) '

 

 

 

 

а ( х )

{

 

 

6

 

 

 

 

Кодовая комбинация Ajfa) будет делиться без остатка на

 

порождающий полином Сг(х)

,

если

I будет делиться без

остатка на £г(х) . Следовательно, порождающий полином<т(х)

 

должен быть одним из делителей полинома

I . Например,для

трехразрядного циклического кода порождающий полином должен

 

быть одним из

делителей

X +

I .

Имеем

 

 

 

Х А+ І=(х +і)(эс,^4-Х + *);

ВЫбйійМ

<т(х) = Х+1.

s

Пусть имеем первичную кодовую комбинацию

А*(х)= И -Х.+1,

77

тогда соответствующая комбинация циклического кода будет

A{x )=A"G=(x +'I)(x .+4)=X'*-+ X ч-х +4= Х*-+І= Л>/.

Можно убедиться, что остальные кодовые комбинации, полученные из ІОІ циклической перестановкой, будут делиться на(f-(x)~jc+S

без остатка. Следовательно, при Сг(х) - . £ + / кодовые комбина­ ции могут быть получены как с помощью циклической перестановки, так и с помощью умножения первичных комбинаций на порождающий полином.

Если порождающий полином не является делителем зоА+4 , а равен, например,

£(йС.)=Х ,

ТО при А*(х) в I I получим

А(х.)~(х.+і)х. - -НО.

Здесь кодовая комбинация ІОІ, получаемая циклической переста­

новкой, на порождающий полином

х

без

остатка не

де­

лится.

 

 

 

комбинация Ъ(х)

Любая принятая

по каналу

связи кодовая

может быть представлена в виде суммы по модулю два передаточ­

ной комбинации А(х,) и вектора

помехи N(x.)

:

 

 

В(х>) -А (х ,)® М х ).

 

 

 

 

При делении В(х) на порождающий полином Сг(х.) ошибка мо­

жет быть обнаружена,

если вектор помехи

А/(х)

не делится

н а ,

(г(х)без остатка.

Исправлено

может быть столько ошибок,

сколь­

ко разных остатков будет получено при делении различных полино­

мов А/(х)

на порождающий полином Сг(х) . Пусть степень порожда­

ющего полинома

 

 

 

/тг - а - к ,

 

где

К -

разрядность первичной комбинации (до внесения избы­

 

п> -

точности);

 

 

разрядность циклического кода.

 

Тогда

наибольшая разрядность

остатков будет пь~ I . Наи­

большее число различных остатков

будет равно Z -■/ (исключая нуле-

76

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