Зертханалық жұмыс № 5
Циклдік кодтардың бөгетке тұрақтылығы
Жұмыстың
мақсаты: Циклдік кодтардың бөгетке
тұрақтылығын зерттеу.
Жұмысты келесідегідей тәртіп бойынша орындау қажет:
- циклдік кодтың
полином арқылы құрушы анықтама алгоритмін құрастыру;
- циклдік кодтың
полином арқылы құрушы анықтама алгоритмін жүзеге
асыратын бағдарлама құрастыру.
Жалпы мағлұмат
Циклдік кодтың алгебралық құрылымы алғашқы
рет Боуз, Чоудхури және
Хоквингеммен зерттелді, сондықтан да олар БЧХ – кодтар сияқты
белгілі.
Бұл кодтар келесідегідей қасиеттермен сипатталады:
– кодты жүйеліліктердің ұзындығы:
|
|
Мұндағы m=1, 2, 3, …;
– тексерілетін жеке элементтердің саны шамадан аспайды, о.д.
|
|
– код ұзындық
қателерінің барлық пачкаларын білдіреді
|
|
– кодтың рұқсат етілген кодты
комбинация арқылы циклдік жылжуы осы кодтың рұқсат
етілген комбинациясына ертіп әкеледі. Алгебралық ұғымдармен
орналасқан қарапайым әдістемелерді көбірек қолданамыз.
Бұл жағдайда айнымалы көп мүше түрінде берілген кодты
комбинация жазуы көбіне ыңғайлы болып келеді:
|
|
Мұндағы санау жүйесінің
негізі.
коэффициенті өзімен
берілген санау жүйесінің цифрларын ұсынады. Екілік санау жүйесінің
коэффициенттері екі мәннің біреуін ғана қабылдай алады:
0 немесе 1. Мысалы, екілік төрт разрядты 1001 саны полином түрінде
жазылуы мүмкін
|
|
Бұл өрнек кодты комбинация жазылуындағы
екі форманың арасындағы бір мағыналы сәйкестікті қондырады.
Циклдік кодтар (n-k) дәрежесі
бойынша полином P(x) құрушы, G(x) көп мүшесі
ретінде берілген, түпкілікті k-элементтік
код әрбір кодты комбинациялар арқылы көбейту жолымен құрыларды. Екі модульмен ұқсас
мүшелердің келтіруімен берілген көбейту кәдімгі алгебра
ережелері бойынша шығарылады. Демек, циклдік кодтың кез келген рұқсат
етілген кодтық комбинациясының қателерінің жоқ
болуы кезінде P(x) құрушы
полином қалдықсыз бөлінуі керек. Бөлудің қалдық
көрінуі кодты комбинациялар бойынша қателер барысында көрсетіледі.
1 суретте берілген адалдықты қанағаттандыратын циклдік кодтың полином арқылы
табылатын құрушы алгоритмінің құрылымдық
схемасы көрсетілген.
1. Бірінші
этапта төмендегі шартты қанағаттандыратын n* анықтаймыз:
|
|
2. Берілген k және табылған
мәні n*(m) бойынша тексерілетін жеке элементтер санын анықтаймыз.
|
|
3. Жақын
арадағы кестелік мәнді таңдай отырып, кестедегі
1 қосымшадан тексерілетін жеке элементтер санын анықтаймыз.
4. сәйкес келетін,
табылып жатқан қателердің
кепіл еселік бойынша кестелік мәнін анықтаймыз.
5. Кестелік
код жұптылыққа
тексерумен қосылған бола алады, олай болса барынша көп артықтықты
және табылып жатқан қателердің барынша көп
кепіл еселігін анықтаймыз.
6. Циклдік кодтың кодтық
комбинация ұзындығын анықтаймыз
.
Егер n<n*(m), онда ақпараттық жеке элементтер саны (n*-n) мөлшеріне көбірек болуы мүмкін және түзететін қабілеттілікпен толық
циклдікке кодқа эквивалентті,
аталған қысқартылған циклдік (n,k)-код орын алады.
7. Табылған мәндер
үшін табылусыз
қателердің
ықтималдығын
анықтаймыз.
8. Логикалық шарт бойынша
тексереміз
|
(1) |
1 сурет. Циклдік
кодтың полином арқылы табылатын құрушы алгоритмінің
құрылымдық схемасы
9. (1) шарты орындалмаған кезінде n*(m+1) таңдаймыз және 2-8 б.
қайталаймыз.
10. Егер (1) шарт
орындалса, онда (1) шарт орындалуы үшін асып кету әдісі бойынша
тексерілетін жеке элементтердің ең аз санын және сәйкес
мәндерін
және
анықтаймыз.
11. Сәйкестендіріліп
есептейтін және
мәні, кесте (13 қосымша)
бойынша P(x) полином арқылы
құрушы таңдаймыз.
,
Мұндағы - көрсеткіш
көп мүшелер,
индексі
тексерілетін элементтердің сан
артуымен өседі;
-
сәйкес индексі.
Жұптылыққа
қосымша тексерту жүргізген кезінде
.
1 қосымшадағы
барлық көп мүшелердің жазуларындағы қысқарту
мақсаты сегіздік ұсынылымда көрсетілген. Сонда жазулардағы
әрбір символ сәйкесінше келесі кодпен берілетін үш екілік
белгілермен белгіленеді:
0<=>000 |
4<=>100 |
1<=>001 |
5<=>101 |
2<=>010 |
6<=>110 |
3<=>011 |
7<=>111. |
Екілік жазуындағы көп мүшенің
коэффициенті кему ретімен орналасқан, олай болса, жоғарғы
реттегі қосындылар коэффициенті сол жақта орналасқан. Мысалы,
n*=31 кодындағы 45 саны көп мүшедегі 5-ші дәрежеліні
білдіреді. Бұл санның екілік жазылуы 100 101 санына
эквивалентті және лайықты көп мүшесі тең.
Бастапқы деректер үшін:
полином арқылы құрылатын таңдау
бойынша барлық этаптардың орындалуы кезінде 1 кестені аламыз.
1 кесте
Этап: |
Амалдар: |
Нәтижесі |
№ 01 |
n* табу: |
31 |
|
Осыдан
m : |
5 |
№ 02 |
Анықтау r* : |
14 |
№ 03 |
Анықтау rt : |
10 |
|
және сәйкесінше. gt : |
4 |
№ 04 |
Анықтау rmax : |
11 |
|
Көрсеткіш gmax : |
5 |
№ 05 |
Анықтау n : |
28 |
№ 06 |
Көрсеткіш Pno : |
2,2E-18 |
№ 07 |
Жұптылыққа тексеру бойынша! |
|
|
rmin = |
6 |
|
gmin = |
3 |
|
nmin = |
23 |
|
Ind сәйкес. rmin = |
1 |
|
Осыдан
Pno = |
1,9E-12 |
№ 08 |
Полином: |
|
|
1101111 |
|
|
X^6+X^5+X^3+X^2+X+1 |
|
11 қосымшада
циклді кодтау бағдарламасының негізгі бөлімі, ал 12 қосымшада
– циклді кодтың полином арқылы құрылатын таңдау нұсқасы
көрсетілген.
Бақылау сұрақтары:
1.
Циклдік код қалай
анықталады?
2. Циклдік кодтың табылушы полиномы дегеніміз не?
3. Циклдік кодқа қандай белгілер арқылы сипаттама
беріледі?
4.
Циклдік кодтардың
бөгетке тұрақтылығы қалай анықталады?
1. Бастапқы
деректер үшін: , мұндағы N-нұсқа нөмірі,
циклдік код құру.
2. Циклдік кодтың полином арқылы құралатын таңдау
алгоритмін жүзеге асыратын бағдарлама құрастыру. Қорытынды
жасау.
1. Элементы криптографии. Под
ред. В.И. Нечаев. – М.: Высшая школа, 1999
2. Джордж Ф. Основы кибернетики – М.: Радио и вязь,
1984г.
3. Мастрюков Д. Алгоритмы сжатия информации. – М.:
Монитор, 1994г.