Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

конспект лекции__1

.3.pdf
Скачиваний:
10
Добавлен:
15.03.2015
Размер:
26.6 Mб
Скачать

из( n+1)-двоичногоэлемента,начинающейся

 

f n .Последующемутактовимпоульсуявится

f n 1,ещечерезтакт

fn-2 ит.д.

 

 

 

 

а)Схедляумыножениямногочленов

 

 

 

Нарис. 6.2

изображениясхема,осуществляющаяумножениелюбогомногочлена,п даваемого

 

навход,например,

a(x) = a0

+ a1 x + ... + ak xk

нафиксированныймногочлен

h(x) = h0 + h1 x + ... + hr xr .

 

 

 

 

 

+

 

 

 

+

 

 

 

+

 

 

+

 

 

 

+

 

 

 

+

hr

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

hr-1

 

hr-2

hr-3

 

h2

h1

 

 

 

h0

вход

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис6.2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Схедляумнамногочленожения

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

h(x) = h0 + h1x + … + hr-1xr-1 + hrxr

 

 

 

 

 

 

 

Висходнпамятистоянииячейкирегистсоденули.Нрвхжатподступают

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

коэффициентымногочл

 

 

 

 

 

ена а(х)

 

,начинаяскоэффициентвысшихпорядк, чеглоедуетвв

 

 

 

 

 

 

 

 

 

 

 

r

нулей.Произведениера

 

 

 

вно:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a(x) h(x) = a0 h0 + (a0 h1 + a1h0 )x + (a0 h2 + a1h1 + a2 h0 )x2 + ... +

 

 

 

 

 

 

 

+ (ak 2 hr + ak 1hr 1 + ak hr 2 )xk +r 2 + (ak 1hr + ak hr 1 )xk +r 1 + ak hr xk +r .

 

Когдапопервотактоимнапульсувходеомупоявляетсяпервыйкоэффициент

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ak

многочлена а(х)

,тонавыходепояв

 

 

ляетсяпервыйкоэфф

 

 

 

 

ициентпроизведения

 

a(x) h(x),равный ak hr

и ak записывперраваетсяый

 

зрядрегистра.Вэтотмомвсостальныентразрярегистрадвигы

 

 

 

 

 

 

 

 

 

 

 

 

содержатнули.Спустяединицувремениповто

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

оявляется ak 1.Как

видноизрис. выход6.по2второтактовомуи равенпульсу

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ak 1 hr

+ ak hr 1 ,т.е.величиневторого

коэффициентавпроизведении

 

a(x) h(x) .Кмоментупоявлениятре

тьегокоэффициентанавходе

( ak 2 )ра зрядырегистсодеэлементыржат

 

 

 

 

 

 

 

 

ak 1 , ak , 0, ..., 0. Выходпотретьемутактуравен

ak 2 hr + ak 1 hr 1

+ ak hr 2 , т.е.третьемукоэффициентупроизведения

 

 

 

 

 

 

 

a(x) h(x).Дальнейшие

операцииоиз

водятсяаналогичнымобразом.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

138

 

По(

r+k)-мутактурегистрсдвигасодержитэлементы0, 0, …, 0,

 

 

 

 

 

 

 

а0,авыходравен

 

 

a h

+ a

0

h ,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

 

1

т.е.предпоследнемукоэффициентупроизведения

 

 

 

 

 

 

a(x) h(x).После(

 

r+k+1)-готактаврегистре

 

 

 

 

остаютсяоднину

 

ли,анавых

одепоявляется

a0 h0 - последнийкоэффиципроизвентдения

 

 

 

 

 

 

a(x) h(x),

такчтопроизведполучполностью.ение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Другаясхедлумноженияа

многпокнчлериса.6зана.3ов

 

 

 

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

 

 

 

+

 

 

+

 

 

 

+

 

 

 

 

+

выход

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

h0

 

 

h1

 

 

h2

hr-2

 

 

hr-1

 

 

 

 

hr

 

 

 

 

вход

 

 

 

Рис6.3

 

 

 

 

 

 

 

Схедляумноженияа

намногочлен

 

 

 

 

 

 

h(x) = h0 + h1x + … + hr-1xr-1 + hrxr

 

 

 

 

Вэтойсхемекоэффициентыпроизведенияформируютсярегиссдвига.Послереого,какпо

 

 

 

 

первотактовоимсипульсумволу

 

ak поступилнавход,

ыходстравнымл

 

ak hr ,т.е.коэффициенту

при xk +r ,авразрядахрегистразапис

 

алисьэлементы

ak h0 , ak h1 , ak h2 , ..., ak hr i .Повторому

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

 

ak 1 , выходстановитсяравным

ak 1hr + ak hr 1 ,т.е.коэфф ициенту

при xk +r 1 ,аразрядырегистсодеэлементыржат

 

ak 1 h0 , ak 1 h1 , ..., ak hr 2

+ ak 1 hr 1 .Потретьему

тактоимпульсунавходому

 

оступает ak 2 ивыходравен

ak hr 2 + ak 1 hr 1

+ ak 2 hr - коэффициенту

при xk +r 2 .Дальнейшие операцииоизваналогичнымбразомдятся.

 

 

 

 

 

б)Схемыдляделениямногочленов.

 

 

 

 

 

 

 

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

 

 

 

 

п

намногочлен

g(x) = g0 + g1 x + g2 x2 + ... + gr xr покнриса.6зана.4

.Схемапредставляет

 

обоюрегистрсдвига

обратнысвязями.Обратные

 

связисоответствуют

идумногочлена

g(x).Висходнстояниим

ячейкирегистсоденули.Делимыйржатмногочлен

 

d(x) = d0 + d1 x + ... + dn xn

поднвходается

схемывт

ечение(

n+1)такта.Высхемыделодвт ниячение

r первыхтактовприним

 

аетзначения,

равные 0Когда. первыйвходнойсимвол

d n по( r+1)-мутакт овоимпульсувыйдетизрегистра,тона

 

 

 

 

 

 

 

 

 

 

139

высхпоемыодстаршийупитк

 

 

 

 

оэффициентчастного

 

 

 

 

qnr = dn gr1 ,которыйврассматриваемом

 

 

двоичномсл

учаеприметзначение

d n .Приэтомвпоследнийразрядрегистрабудетзап

 

 

 

 

 

 

 

 

исансимвол

 

dn1 + dn g r 1,впредпоследний

dn2

+ dn gr 2 ,ит.д.т,.е.содерж

 

имоеразрядоврегистрабудет

 

 

 

 

 

 

соответствоватькоэффпрстепеняхициентам

 

 

 

 

 

 

 

 

 

 

n r до n 1 многочлена d (x) + qnr g(x),

где

суммированиеосуществл

 

 

яетсяпомодулюДля2каждого. последующего(

 

 

 

 

 

 

 

r+j)-гоэтападеления

 

содержимоеразрярегистдопвигркоэффеделяетсяа пристепеняхотциентами

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

n r j

до

n j многочлена d (x) + qnr g(x) + qnr 1 g(x) + ... + qnr j +1 g(x),где qi

 

символ,поступающийна

 

 

высх.Послеемыод(

 

 

 

n+1)-готактаработысхемынав появиходечасделениятноеся

 

 

 

 

 

 

 

 

 

 

 

 

 

q(x),ав

ячейкахрегистраб

 

удетзаписделенияостатокот

 

 

 

 

 

 

r(x) = d (x) + g(x)q(x).

 

 

 

 

 

 

 

 

 

Пример6.14

 

.Посхемутроитьдляделенамногочления

 

 

 

 

 

 

 

 

 

 

g(x) = 1 + x + x3 .Регистрдолжен

 

содержчислоячеек,равноестепениь

 

 

 

 

 

 

 

 

g(x),т.е. Обратные3.связидолжнысоответствовать

 

 

 

 

 

 

 

 

 

коэффприциентам

 

xi:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

g0 = 1, g1 = 1, g2 = 0, g31 = 11 = 1.

 

 

 

 

 

 

 

 

 

Сумматорпо

 

модувк2 люнавходеичаетсяточкеподключенияобратнойсвязи

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

g1.Схема,

соответрасствующматслучаюпреив яемому

 

 

 

 

 

 

 

дставленарис. На6этом.5жерисунке. показана

 

 

 

 

 

 

 

 

 

 

работасхемыприделениимногочлена

 

 

 

 

 

 

d(x)

= x

5

+ x +1

.Врезультатеделенияпол

 

 

 

 

 

учасено

тное

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

q(x) = x2 +1 иостаток

r(x) = x2 .Длятого,чтобыустановисоответствиемеждуработойсхемыь

 

 

 

 

 

 

 

 

 

 

 

процессомделениямногочлена

 

 

 

d(x) намногочлен

 

q(x) рассмотримделение

x

5

+ x + 1

на

x

3

+ x

.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+ 1

 

 

 

 

 

d(x) = x5 + 0 + 0 + 0 + x +1

 

x3 + 0 + x +1 = g(x)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержимое

 

x5 + 0 + x3 + x2

 

 

 

 

 

 

x2 + 0 +1 = q(x)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0 + x

3

+ x

2

+ x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

регистрапо4

-му

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

такту

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержимое

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x3 + x2

+ x + 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

регистрапо5

 

-му

3 + 0 + x + 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

такту

 

 

 

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержимое регистра

x2 + 0 + 0 = r(x)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

по6

-мутакту

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

140

Остатокпервогошагаделения

1 x2 + 1 x3 + 0 x4 содержитсявразр

ядахрегиповыходастраплервого

 

элементачастногоквыходуемы(4

-йтакт)Остаток. второгошагаделения

 

1 x +1 x2 +1 x3

содержитсявразрядах

региповывстравтлеоэдарого

лементачастногоквыходуемы(5

-йтакт).

Остатокотделения

r(x) = 0 x0 + 0 x1 +1 x2

содержитсявразрядахрегиповыводатрапоследнего

 

элементачастного(6

-йтакт).

 

 

 

g0 +g1x+….+gn-k-1 xn-k-1+gn-kxn-k

 

 

 

 

 

Такты

Вход

Содержимоерегистра

 

Обратнаясвязь

Выход

 

 

 

r0

r1

r2

 

 

0

 

-

0

0

0

0

-

1

 

0·x5

1

0

0

0

0·x6

2

 

0·x4

0

1

0

0

0·x4

3

 

0·x3

0

0

1

0

0·x3

4

 

0·x2

1

1

0

1

1·x2

5

 

1·x1

 

 

 

0

0·x1

1

1

1

6

 

 

 

 

 

 

1·x0

 

1·x0

0

0

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

Остаток r(x)= x2

 

Работасхемыделенаногочления

 

 

g(x)=1+x+x3 приподаченавход

d(x)=1+x+x5

141

 

в)Схемыдляодновремемногочленовумноженияделе

 

 

 

 

 

 

Схема,спомкотмщьюопроизводитьройжносначалаум многочленожение

 

 

 

h(x),азатделением

намногочлен g(x),изображенарис. 6.6

.Каквидноизрисунполучена,онакомбинированиемсхемы

 

 

 

 

умножения,изображен

нойнарис6.3

исхемыде

ления,изобнар.исаженной6.4

 

.Прип

остроении

схемыпредп,чтстепеньомногочленалагается

 

 

h(x) непревосходитст

епени g(x).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

г)Схемыдлярешениярекуррентныхсоотношений

 

 

 

 

Нарис. изображена6.схема7для. ре

шениярекурресоотнтныхош

енийвида

 

k 1

k

 

f nk i = hj f nij . или,чтожесамое

hj fnij = 0.

 

 

j =0

j=0

 

142

 

Этасхемапредвычисленияназначеналявеличины

 

fl

позначению

k

предыдущих

коэффициентдлявсехвозможныхстепегочленов

ни n-1,ортогональныхнекотмн членуму

 

 

h(x) степени k.Дляциклического(

n, k) – кода h(x) – провермногочленк.Исходныечныйдавеличины

 

 

 

f n1 , f n2 , ...,

f nk помещаютсявразрядырегистра.Затемосущепослетвляютсяд,вигиовательные

 

 

 

 

каждыйиз

оторыхсопровождавы ыодхэлементоводаема,тся

 

оответствующихрешению

указанныхрекурреав.Посленптнрвыхий

огосднавигаыходпоступаетэлемент

 

 

f n 1,

содержимрегистраразря оввигнаоднуединицуетсявправо,

 

 

чейку

f ni k +1 поступит

значениек

оэффициента f nk 1 ,котвсороеответствиисосхемрис. должно6.бытьравной7 сумме

 

 

 

 

произведенийкоэффици,запивовсостальныханныхентовразрядахрегистразначенияобратных

 

 

 

 

связей,

подключенныхнепосредс

твенноквыходамразрядоврегистра,..

 

 

 

 

 

 

 

 

f nk 1 = h0 f n1 + h1 f n2 + h2 f n3

+ ... + hk 1 f nk ,

 

 

чвточнсоответствуетстизначению

f nk 1 ,полученнизрекурресоотму. нтногоошения

 

 

 

 

Аналогичноможнопоказатьф рмированиевсехостальныхреш

 

ений.Врезультатепервых

k

сдвиговнавыхпоемыодсодержимрегистратупитразрядовисходнстоянии.Значением

 

 

 

 

коэффициента

f nk 1 появитсянавыхводерезультатеемы(

k +1)-госдвига,значение

 

f nk 2 - в

результате ( k +2)-госдвигат.п

.Посдлякаждогоолькузначенияисходныхсимволоврешение

 

 

 

 

однозначно,топоследним

k решенсформирузапишетсяямврегистр

 

f n 1,затем

f n2 ит.д.,

т.е.схемабудетгенерировать

ешениерекуравренепртсенерогоияра, иодомывным

 

 

 

n-1.

Максимальноезначениерешений,т..максимальныйпериодпоследовательн

 

ости,м ожноопределитьиз

следующихсоображений.Каждрешениюму

тветствуетоеполнеопределзначениеное

 

 

разрядоврег

истрадвига,сл

едовательно,возможноечислорешенийопрчисдеразличныхомяется

 

 

 

 

состоянрегистра.Таккаккаждаяйячейкаможетхарактеризоватьсядвумя

 

остоязапись(нуляиями

 

илиединицы),ачислоячеврегистреравнок

k,томаксимальноезначение

 

n равно 2k, амаксимальный

 

 

 

 

 

 

 

 

143

периодпоследовательн

остиравен

2k -1 иминимпериодавельный

k.Втехслучаях,когсхемадля

 

решениярекурресоотгенерируеттныхошений

 

последовательнмаксимальнымпериодость

,ее

называют генераторомпоследовательностима

ксимальнойдлины

.Всилутого,чтомногочлен

h(x)

степени k,покоторомустоитсясхгенераторамапоследовательностимаксимальнойдлины,должен

 

 

 

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

 

xn +1 при n = 2k 1 инеможетбытьсомн

ожителемника

кого

двучленасменьшимзначением

 

п (т.к.периодравен2

k -1),то

h(x) долженбытьнеприводимым

 

сомножителем xn +1 инедолженбытьсомножителемдвучленовменьшихстепеней,..должен

 

 

 

принадлежатьпок

азателю п.Поскопоследовательноську

тимаксимальнойдлинысоответствует

2k -1

различныхсостоянрегистрасдвсе(возможныеигйвекторыдлин

 

 

k,кромечистонулевого),для

 

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

имальнойдлинывкачествеисходнмобытьжетянияго

 

 

взятолюб,крчисоме

тонулевого.Обычнодляэтойцелимладшийразрядрегистрапредварительно

 

 

записывают“1”Некото.изнепрмногиводимыхые,пвидукоточленстрообратныеыхсвязиятся

 

 

 

 

регистре,приводятсятаблице6.3

 

для п=2+15.

 

 

 

Таблица6.3

 

 

 

 

 

Число

Неприводимый

ячеек

Многочлен

регистра

 

2

x2 + x + 1

3

x3 + x + 1

4

x4 + x + 1

5

x5 + x2 + 1

6

x6 + x + 1

7

x7 + x + 1

8

x8 + x5 + x3 + x + 1

9

x9 + x4 +1

10

x10 + x3 + 1

11

x11 + x2 + 1

12

x12 + x6 + x4 + x + 1

13

x13 + x4 + x3 + x + 1

14

x14 + x12 + x2 + x + 1

Видобратнойсвязи

Длина

 

периода

h2 , h1 , h0

3

h3 , h1 , h0

7

h4 , h1 , h0

15

h5 , h2 , h0

31

h6 , h1 , h0

63

h7 , h1 , h0

127

h8 , h5 , h3 , h1 , h0

255

h9 , h4 , h0

511

h10 , h3 , h0

1023

h11 , h2 , h0

2047

h12 , h6 , h4 , h1 , h0

4095

h13 , h4 , h3 , h1 , h0

8191

h14 , h12 , h2 , h1 , h0

16383

144

15

x15 + x + 1

 

 

 

h15 , h1 , h0

32767

Дляпримеранарис.6.8

 

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

оследовательностимаксимальной

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

 

h(x) = x

6

+ x +1

 

 

 

.

 

Числоячеекрегистрасдвигравностепени

 

 

 

h(x),т.ешести.Числосумпоматороводулюна2единицу

меньшечислазнаков“+”зап

 

 

исимногочлена

h(x),т.е.один.Обратныесвязиопределяются

ненулевымик

оэффициентамимн

огочлена h(x) h0 , h1 , h6

 

 

д)СхгенермаполяГаторалуа

 

GF(2m)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Регистр сдвигаобрсвятны,изямиобнар.исаженныйреализу6.4,

 

 

ющийделюбогоение

 

 

многочлена

g(x) степени n-k=m,послез

авершенияделениясодержитостатокотделения

 

 

 

 

 

 

r(x) = r0x0+r1x1+r2x2+…+rm-1x0m-1.

 

 

 

Онможетбытьпредставленвидепоследоват

 

 

 

ельностидлины

m-(r0, r1, r2, .. ,rm-1)

 

 

 

Многочлен r(x) являпретсядставителемклассоввычетовмногпомодулючленног вчлена

 

 

 

 

 

g(x).Приэтомкаждклавычетовссйодержитлиболибо0,многочленстепени

 

 

 

 

m-1 именее.Ноль

 

 

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

 

ногочлены r(x)

степени m-1

именеепринадлежатразличным

 

 

классамвыч

 

етов.Общеечислоклассоввычетоввместеидера2внолом

 

 

 

 

m.

 

 

 

Втомслучае,когдамногочлен

 

g(x) – неприводим,множество

{r(x)} скоэ ффициентами ri

из

поля GF(2) образуетполеГалуа

 

GF(2m). Какизвнестно

улевыеэлементыэтогоп лябразуют

 

 

циклическуюгруппу

 

 

 

 

 

 

 

 

 

 

 

 

α01,…α , 2m-22m-10,

 

 

 

 

гдеα -класодержащийвычетов,

r(x) = x, т.е.корень g(x)

ипримитивныйэлементполя.

 

 

 

Определим,какимобразомможнопреобразоватьсхемурис6.4

 

 

 

 

генераторэлементов

поля

GF(2m). Всхемеделнания

g(x) каждыйизостатков

r(x) можетбытьполученврезультатеподачи

xi

на

входсхемыиосущестпроцедурыделвтлениячение

 

 

 

 

i тактов,.е.остатокотделенияпоявится

 

 

точнона

 

i- мтакте.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

145

 

Этотрезультатмож

 

нополуч,еслвсхемеделиубратьвходния,цепьобратнойсвязиподать

 

 

 

 

 

непосренавходячейкиственно

 

 

 

r0. Приэтомдляг

енерировэлемеполяканктовия

 

 

 

последовательностистепеней

 

αi

ввиде

m-значныхдвоичных

чисел,записанныхвячейкахрегистра

 

 

 

необходимопредвар

ительновячейку

r0

записать«1»Вэтомслучаев. исходстояниина м

 

 

 

улевом

тактеработырассматриваемойсхемыкакгенератораэлементов

 

 

 

 

GF(2m) будетзаписостатокот н

 

деления x0 на g(x). Элементполя

αi появитрегинасятре

i-мтакте,

чтос ответствуетподаченавход

 

 

схемыделения

xi нанулевомтакте

.

 

 

 

 

 

 

 

Все 2m-1 ненулевыхэлементов

 

GF(2m) ,будутполученыза

2m-1 тактовраб

отысхемы.До

m-1

тактаработысхемывключрегистрбудетсодетельно

 

 

 

ржатьвсвоихячейкахтолькооднуединицу

 

 

m-1

нулей.На

 

m-мтактесоде

ржимоерегистрастанетравным

g'(x)=g(x)+xm ,где

 

g'(x)- многочлен,

состоящийизвсехлагаемых

 

 

g(x),кромеслагаемогостаршейстепени

 

xm. Всилут

ого,что

g(x)

принадлежитид,.. алу

 

{g(x)}={0}, получаем g(x)=xm.

 

 

 

 

 

 

Просдвиолжая

 

ги,получим,чтона

m+1

тактесодеячеекржимоеегистрабудет

 

 

 

соответствовать xg(x),т.е.подаченавходсхделениямынанулевомтакте

 

 

xm+1

ит.д.Такбудет

 

продотехпорлжаться,покасодеячеекржимоеегистрастанетэквивалентнымподаченавход

 

 

 

 

 

 

 

схемыделения

xn. Этос

остоянрегиссооетраветствует

α0=1,т.к.

xn=1(см.6 .1)Всилу.того,что

 

многочлен g(x) примитивен,онпринадлежитпоказателю

 

n=2m-1. Этоозначает,чтодвозвращения

 

 

состояние α0=1 врегистененаразличныхеатактахорарабпоты

 

 

явятсяучётомнулевоготактавсе

 

 

 

ненулевыеп

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

m икаждаятолькоодинраз.

 

 

 

 

 

 

Проиллюстрируемизложенноепримером

 

6.15

 

 

 

 

 

 

Пример6.15

 

 

 

 

 

 

 

 

 

 

Построимгенераторэлеполяентов

 

 

GF(23).Дляэтойцелииспользуемпр

 

имитивный

многочлен 1+x+x3.Классвы

четов {x}=αявляетсякорнем

1+x+x3 ипримитивнымэлементополя

 

 

 

GF(23).Схгенераторамаэлементовполя

 

 

GF(23) представленарис. Предв6.9. ячейкуαрительно

 

 

0

записывается«1»Послеэтогоосуществляются. сдви.Выходомгенератораиявляется

 

 

 

 

 

одержимое

ячеекα

0,α12 .

 

 

 

 

 

 

 

 

 

Работагенераторапоясняетсяизменениемсодержания

 

 

 

представлениемдвоичнойпоследовательности

 

 

 

многочлистеппримитивногоенэлементаьюомα

 

 

 

1.

 

 

 

 

 

α0

 

+

 

 

α1

 

 

α2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

“1”

146

Такты

Последовательность

Многочлен

Степеньα

 

длины3

 

 

 

 

0

(1

0

0)

1

 

α 0

1

(0

1

0)

α

 

α 1

2

(0

0

1)

α 2

α 2

3

(1

1

0)

1

+ α

α 3

4

(0

1

1)

α+α 2

α 4

5

(1 1

1)

1 + α+α 2

α 5

6

(1

0

1)

1

+ α2

α6

7

(1

0

0)

1

 

α7 0

Рис6.9 Генераторэлементовполя

GF(23 )

6.7.3Схемы. кодирующихустройствциклическихкодов

 

а)Кодированиепо

g(x)

 

 

 

 

 

 

Восновекодирующустройслежисхематлениягопорова

 

 

 

ждающиймногочлен

g(x)

степени n-k спредварительнымумножениемна

 

xnk .Даннаясхемастросновеитсясхемы,

 

 

 

представленнойнарис. 6.6

 

 

 

бщемслучаеимев, дзобтнар.исаженный6Число.10ячеекпамяти.

 

 

 

вр егистреравно

n-k,т.е.чизбыточныхслуэлементовкод мбинациивой.О

 

 

братныесвязи

подключенывсо

ответствииненулевымикоэффициентами

g(x),следоват,общеч ельно

ислообратных

связейравночислу

компонентов g(x) (иливесудвоичномпредставлении)Число. сумматоровпо

 

 

 

модулюравночислу2 знаков“+”записи

 

 

 

g(x) ввидемногочлена.

 

 

 

Входсхемыпо

дключенпослеячейки

rn k 1

дляосущестпредумножениявленияарительного

 

 

 

кодируемогосообщения

 

ai (x) на xnk .Схемаработаетследующимобразом.Информационные

 

 

 

символы ai (x)

поступаютнав

ходкодирующегоустройс

тва,начинаясостаршейстепени,

 

 

одновременнонавысхемы

 

 

 

– вканалсвязи.Вэтовремянасхему

 

И1 вцепиобратнойсвязи

 

поступают k тактовыхимпульсоввходаинформационныеимпоступаютульсычерезцепь

 

 

 

 

обратнойсвязираз

рядырегистра

r0 , r1 , r3 , ...,

rnk 1.Кактольковсе

k информационныхсимволов

поступятвустройство,совокупность

 

 

n-k - символовразрядахрегисовпаостаткомтраотделения

 

 

 

f0 (x) = a(x) xn k на

g(x),т.е.разрядырегистсодепроверочныжат

 

есимволы

r(x)

кодовой

комбинации.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

147