Циклдық кодтарға математикалық кіріспе

Осылай n-разрядты циклдық кодтың ә рбір рұ қ сат етілген комбинациясы екі кө пмү шенің туындысы болып табылады, оның біреусі қ ұ раушы, онда бұ л комбинацияларды n-1 дә режесінен жоғ ары емес кө пмү шелердің барлық туындылары ретінде қ арастыруғ а болады. Бұ л мына ойғ а алып келеді, осы кодтарды қ ұ рау ү шін тағ ы бір алгербралық жү йенің тармағ ынн қ олдануғ а, дә лірек, сақ ина теориясына.

Келтірілген анық тамағ а сү йене отырып, сақ инаны қ ұ рау ү шін кө птеген n-разрядты кодтық комбинацияларғ а екі операция жү ктеу керек, қ осу жә не кө бейту.

Кө пмү шелерді қ осу операциясы модуль екі бойынша келтірілген коэфиценттерге сә йкес таң далғ ан.

Енді кө бейту операциясын қ арастырайық. Кө пмү шелерді кө бейту операциясы қ арапайым ережелер бойынша модуль екі сә йкес мү шелерді келтіру тұ йық талу шартын бұ зуғ а алып келеді.

Расымен, кө бейту нә тижесі бойынша n-1 дә режесінен ү лкен кө пмү шелерді аламыз, дә реже 2(n-1) дейін жетуі мү мкін, ал оғ ан сә йкес кодтық комбинациялар n разрядты саннан кө п болады, осығ ан сә йкес қ арастырылып отырғ ан кө птікке қ атысы болмайды. Сондық тан символдық кө бейту операциясы былай беріледі:

1)кө пмү шелер қ арапайым ереже бойынша кө бейтіледі, бірақ модуль екі бойынша келтірілген мү шелерге сә йкес;

2)егер туындының жоғ ары дә режесі n-1 кө п болмаса, ол символдық кө бейтудің нә тижесі болады;

3)егер туындының жоғ ары дә режесі n-ғ а тең немесе ү лкен болса, онда кө пмү ше туындысы алдын ала анық талғ ан nи дә режесіндегі кө пмү шеге символдық кө бейту бө лудің қ алдығ ы жатады.

Қ алдық тың дә режесі n-1 аспайды, сонымен қ атар, бұ л кө пмү ше k разрядты кодтық комбинациялардың кө птігіне жатады.

Расымен n-1 дә редесіндегі кө пмү шенің кө бейтіндісінің нә тиесінде мынаны аламыз:

G(x) = (x^n-1 + x^n-2 + … + x + 1)x = xⁿ + x^n-1 + … + x

Қ арастыра келе, кө бейту нә тижесі кодтық комбинацияғ а сә йкес келу керек, шық қ ан кодтық комбинациясының циклдық жылжуы жолымен қ ұ ралады, онда хⁿ–ді 1-ге ауыстыру керек. Мұ ндай ауыстыру кө пмү шенің xⁿ+ 1-ге кө бейтіндісінен алынғ ан бө лінуге эквивалентті болады, мұ ны былайша қ алдық ты алу деп атайды немесе модуль xⁿ+ 1 бойынша келтіру.

Мұ нда хⁿна –ны 1ге міндетті тү рде ауыстыру қ ажет. Баламалы бө луге сондай алмастыру бө луден қ алдық қ а нә тижеге сапада жазумен xⁿ+ 1 кө пмү шелікте кө бейтуда алғ ан, не қ алдық тың алынуы деп немесе модул бойынша келтіруде xⁿ+ 1 (ө зі қ алдық шегермеде) деп аталады.

Барлығ ын кө пмү шеліктеріне ішкі жиынымызғ а біздің сақ инамызда енді ерекшелейміз, еселі кейбір g (x) кө пмү шелікке. Сондай ішкі жиынды идеалмен деп атайды, ал кө пмү шелік идеалдың кө пмү шелікпен g (x) тудыратын.

Идеалда ә р тү рлі элементтердің сан кө пмү шеліктің оның тудыратын тү рмен анық талып жатыр. Егер 0 алу кө пмү шелікке тудыратын, біресе кө бейту, барлық идеал тек қ ана бұ л кө пмү шелікті қ ұ рау болады

Егер артына 1 [g (x) = 1] қ абылдау кө пмү шеліктің тудыратын, біресе идеалғ а сақ иналар барлық кө пмү шеліктер кіреді. Дә режелер қ арапайым кө пмү шелікпен туғ ан идеалдың элементтердің саны жалпы алғ анда жағ дайғ а n-k, 2k қ ұ райды.

Тү сінікті енді бола тү сіп жатыр, не циклдік екілік кодқ а салынғ ан бізбен n-дә режелік екілік кодтық комбинацияларғ а сақ инада идеалғ а келіп жатыр. Кө пмү шелікті таң дау сияқ ты, анық тау қ алып жатыр g (x), тап қ алғ ан қ асиеттермен циклдік код қ абілетті тудыру керек.

Кө пмү шелікке талаптарды, жасаушысығ а ұ сыну

Оның кодтық комбинацияларғ а лайық ты барлық кө пмү шеліктер циклдік код анық тау бойынша, қ алдық сыз g (x) жіктелуге тиісті. Кодсыз кө пмү шеліктерсіз, қ ұ райтын жасаушы матрицасыз қ алдық сыз g (x) жіктелу ү шін, ү шін бұ л жеткілікті. Циклдік жылжумен соң ғ ы пайда болып жатыр, не 1 xn модул бойынша келтірумен х g (x) біртіндеп кө бейтуғ а сә йкес келіп жатыр.

Демек, кө пмү шелік жалпы алғ анда жағ дайғ а осылай жазып алғ ан xn 1и мү мкін болу g (x) •хiна кө пмү шеліктен шығ армадан бө луден қ алдық пен gi (x) келіп жатыр:

g_i(x)=g(x)xⁱ+ c(xⁿ + 1)

мұ ндағ ы с=1 болады, егер g(x) хⁱ дә режесі п-1-ден асып тұ рса, егер g(x) хⁱдә режесі п-1-ден аспай тұ рса.

Осыдан кө руге болады, егер xⁿ + 1 мына кө пмү шелік g(x)-ке қ алдық сыз бө лінсе барлық матрицаның кө пмү шеліктері жә не барлық код кө пмү шеліктер g(x)-ке қ алдық сыз бө лінеді.

Осылайша, егер g(x) идеалды жә не циклдық кодты шығ арғ ысы келсе, онда ол xⁿ + 1 кө пмү шелігінің бө лінгіші болу керек.

Сақ ина ү шiн топтың барлық касиеттері ә діл болғ андық тан, ал мінсіз ү шін - шағ ын топтың барлық қ асиеттерi, сақ инаны шағ ын топтарғ а жiктеуге болады, бұ л жағ дайда оны мінсіз санақ тобы деп атайды. Жiктеудiң бiрiншi жолын мінсізден тұ рады жә не де нө лдiк элемент шеткi сол жағ ында орналасады. Қ ұ растыратын шегерiмдердiң бiрiншi табы сапада мінсіз тә уелдi емес кез келген кө пмү шелiкті таң дауғ а болады. Шегерiмдердiң табы мінсіздін кө пмү шелiгiмен ә рбір қ ұ растыратын кө пмү шелiктiң жинақ тауы жолымен қ ұ рады. Егер дә реже m = n-k (x ) g кө пмү шелiк xn + 1-шi бө лгiші болып табылса, онда сақ инаның кез келген элементi немесе (x ) g қ алдық сыз бө лiседi, немесе бө лiнудiң нә тижесiнде дә реженiң r(х) ө зiмен кө рiнетiн кө пмү шелiгi қ алдық m-1 ден ү лкен болмайды. Нә тижесінде бір ғ ана мінсіз мә н беретін сақ ина элементі шегерімдердін бір таптарына жатады. Дә реже m (x ) g қ ұ растыратын кө пмү шелiкпен r(х) шегерiмдердiң кластарын қ ұ растыратын элементтер сақ инасының жiктеуiне кесте кө рсетуге болады. Таблица 4. 12.

		g(x)	x·g(x)	(x+1)·g(x)	…	f(x)·g(x)
r₁(x) r₂(x) … … r_n(x)		g(x) + r₁(x) g(x) + r₂(x) … … g(x) + r_n(x)	x·g(x) + r₁(x) x·g(x) + r₂(x) … … x·g(x) + r_n(x)	(x+1)·g(x) + r₁(x) (x+1)·g(x) + r₂(x) … … (x+1)·g(x) + r_n(x)	… … … … …	f(x)·g(x) + r₁(x) f(x)·g(x) + r₂(x) … … f(x)·g(x) + r_n(x)
	Жоғ арыда айтылғ андай, топтық код корсетилген жіктеуде қ анша тү р болса, соншалық ты қ ателіктер тү рін тузете алады. Демек, циклдық кодтың тузету қ абілеті бұ рмаланғ ан код комбинациясына сә йкес кө пмү шені кодты қ ұ раушы кө пмү шеге бө лгенде қ аншалық ты қ алдық қ алса, соншалық ты артады. Қ алдық тардың ен кө п саны 2m-1 (нольды алмағ анда) тек жай кө пмү шені қ амтамасыз ете алады, бұ л кө пмү ше тек ө зіне ө зі бө ліне алады жане басқ а кө пмү шеге бө лінбейді (1 ден баска).

Бақ ылау сұ рақ тары:

4. Циклдық кодтар қ алай қ ұ рылады?

5. Циклдық кодтарғ а математикалық кіріспе.

6. Туындатушы кө пмү шелікке қ ойылатын талап.

⇐ Предыдущая 29 30 31 32 333435 36 37 38 Следующая ⇒