конспект лекции__1
.3.pdfиз( 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 |
высхпоемыодстаршийупитк |
|
|
|
|
оэффициентчастного |
|
|
|
|
qn−r = dn gr−1 ,которыйврассматриваемом |
|
|
|||||||||||||||
двоичномсл |
учаеприметзначение |
d n .Приэтомвпоследнийразрядрегистрабудетзап |
|
|
|
|
|
|
|
|
исансимвол |
|
|||||||||||||||
dn−1 + dn g r −1,впредпоследний |
dn−2 |
+ dn gr −2 ,ит.д.т,.е.содерж |
|
имоеразрядоврегистрабудет |
|
|
|
|
|
|
|||||||||||||||||
соответствоватькоэффпрстепеняхициентам |
|
|
|
|
|
|
|
|
|
|
n − r до n −1 многочлена d (x) + qn−r g(x), |
где |
|||||||||||||||
суммированиеосуществл |
|
|
яетсяпомодулюДля2каждого. последующего( |
|
|
|
|
|
|
|
r+j)-гоэтападеления |
|
|||||||||||||||
содержимоеразрярегистдопвигркоэффеделяетсяа пристепеняхотциентами |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n − r − j |
до |
|||||||
n − j многочлена d (x) + qn−r g(x) + qn−r −1 g(x) + ... + qn−r − 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, g3−1 = 1−1 = 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 n−k −i = ∑ hj f n−i− j . или,чтожесамое |
∑hj fn−i− j = 0. |
|
||
|
j =0 |
j=0 |
|
142
|
Этасхемапредвычисленияназначеналявеличины |
|
fl |
позначению |
k |
предыдущих |
||
коэффициентдлявсехвозможныхстепегочленов |
ни n-1,ортогональныхнекотмн членуму |
|
|
|||||
h(x) степени k.Дляциклического( |
n, k) – кода h(x) – провермногочленк.Исходныечныйдавеличины |
|
|
|
||||
f n−1 , f n−2 , ..., |
f n−k помещаютсявразрядырегистра.Затемосущепослетвляютсяд,вигиовательные |
|
|
|
|
|||
каждыйиз |
оторыхсопровождавы ыодхэлементоводаема,тся |
|
оответствующихрешению |
|||||
указанныхрекурреав.Посленптнрвыхий |
огосднавигаыходпоступаетэлемент |
|
|
f n −1, |
||||
содержимрегистраразря оввигнаоднуединицуетсявправо, |
|
|
чейку |
f n−i −k +1 поступит |
||||
значениек |
оэффициента f n−k −1 ,котвсороеответствиисосхемрис. должно6.бытьравной7 сумме |
|
|
|
|
|||
произведенийкоэффици,запивовсостальныханныхентовразрядахрегистразначенияобратных |
|
|
|
|
||||
связей, |
подключенныхнепосредс |
твенноквыходамразрядоврегистра,.. |
|
|
|
|
||
|
|
|
|
f n−k −1 = h0 f n−1 + h1 f n−2 + h2 f n−3 |
+ ... + hk −1 f n−k , |
|
|
|
чвточнсоответствуетстизначению |
f n−k −1 ,полученнизрекурресоотму. нтногоошения |
|
|
|
||||
|
Аналогичноможнопоказатьф рмированиевсехостальныхреш |
|
ений.Врезультатепервых |
k |
||||
сдвиговнавыхпоемыодсодержимрегистратупитразрядовисходнстоянии.Значением |
|
|
|
|
||||
коэффициента |
f n−k −1 появитсянавыхводерезультатеемы( |
k +1)-госдвига,значение |
|
f n−k −2 - в |
||||
результате ( k +2)-госдвигат.п |
.Посдлякаждогоолькузначенияисходныхсимволоврешение |
|
|
|
|
|||
однозначно,топоследним |
k решенсформирузапишетсяямврегистр |
|
f n −1,затем |
f n−2 ит.д., |
||||
т.е.схемабудетгенерировать |
ешениерекуравренепртсенерогоияра, иодомывным |
|
|
|
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). Какизвнестно |
улевыеэлементыэтогоп лябразуют |
|
|
|||||
циклическуюгруппу |
|
|
|
|
|
|
|
|
||
|
|
|
|
α0,α 1,…α , 2m-2,α 2m-1=α 0, |
|
|
|
|||
|
гдеα -класодержащийвычетов, |
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,α1,α 2 . |
|
|
|
|
|
|
|
|
|
|
Работагенераторапоясняетсяизменениемсодержания |
|
|
|
представлениемдвоичнойпоследовательности |
|
|
|
||||
многочлистеппримитивногоенэлементаьюомα |
|
|
|
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 спредварительнымумножениемна |
|
xn−k .Даннаясхемастросновеитсясхемы, |
|
|
|
||||
представленнойнарис. 6.6 |
|
|
|
бщемслучаеимев, дзобтнар.исаженный6Число.10ячеекпамяти. |
|
|
|
||
вр егистреравно |
n-k,т.е.чизбыточныхслуэлементовкод мбинациивой.О |
|
|
братныесвязи |
|||||
подключенывсо |
ответствииненулевымикоэффициентами |
g(x),следоват,общеч ельно |
ислообратных |
||||||
связейравночислу |
компонентов g(x) (иливесудвоичномпредставлении)Число. сумматоровпо |
|
|
|
|||||
модулюравночислу2 знаков“+”записи |
|
|
|
g(x) ввидемногочлена. |
|
|
|
||
Входсхемыпо |
дключенпослеячейки |
rn −k −1 |
дляосущестпредумножениявленияарительного |
|
|
|
|||
кодируемогосообщения |
|
ai (x) на xn−k .Схемаработаетследующимобразом.Информационные |
|
|
|
||||
символы ai (x) |
поступаютнав |
ходкодирующегоустройс |
тва,начинаясостаршейстепени, |
|
|
||||
одновременнонавысхемы |
|
|
|
– вканалсвязи.Вэтовремянасхему |
|
И1 вцепиобратнойсвязи |
|
||
поступают k тактовыхимпульсоввходаинформационныеимпоступаютульсычерезцепь |
|
|
|
|
|||||
обратнойсвязираз |
рядырегистра |
r0 , r1 , r3 , ..., |
rn−k −1.Кактольковсе |
k информационныхсимволов |
|||||
поступятвустройство,совокупность |
|
|
n-k - символовразрядахрегисовпаостаткомтраотделения |
|
|
|
|||
f0 (x) = a(x) xn − k на |
g(x),т.е.разрядырегистсодепроверочныжат |
|
есимволы |
r(x) |
кодовой |
||||
комбинации. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
147 |