Nambari zinazofaa zinazotambua hitilafu moja, nyingi na za kupasuka ni pamoja na kanuni za mzunguko(CRC - Msimbo wa Upunguzaji wa Mzunguko). Zinaaminika sana na zinaweza kutumika kwa maingiliano ya kuzuia, ambayo kutenganisha, kwa mfano, usawa usio wa kawaida itakuwa ngumu.

Mojawapo ya lahaja za usimbaji mzunguko ni kuzidisha msimbo wa chanzo kwa g(x) inayozalisha ya polynomial), na utatuzi ni kugawanya kwa g(x). Ikiwa sehemu iliyobaki ya mgawanyiko sio sifuri, basi hitilafu imetokea. Ishara ya hitilafu inatumwa kwa mtoaji, na kusababisha uhamishaji tena.

Polynomial inayozalisha ni uwakilishi wa binary wa mojawapo ya mambo rahisi ambayo nambari X n -1 imetengana, ambapo X n inaashiria moja katika tarakimu ya nth, n ni sawa na idadi ya tarakimu za kikundi cha msimbo. Kwa hivyo, ikiwa n = 10 na X = 2, basi X n -1 = 1023 = 11*93, na ikiwa g(X) = 11 au katika nambari ya binary 1011, basi mifano ya nambari za mzunguko A i *g(X) nambari. A i katika kikundi cha msimbo na polynomial hii inayozalisha inaweza kuonekana katika jedwali lifuatalo. 3.1.

Chaguo la msingi msimbo wa mzunguko, unaotumiwa sana katika mazoezi, hutofautiana na ule uliopita kwa kuwa uendeshaji wa mgawanyiko na polynomial inayozalisha hubadilishwa na algorithm ifuatayo: 1) K zero hupewa nambari ya asili ya A iliyo upande wa kulia, ambapo K ni idadi ya bits katika polynomial inayozalisha, iliyopunguzwa na moja; 2) Operesheni O inafanywa kwa nambari inayosababisha A*(2 K), ambayo inatofautiana na mgawanyiko kwa kuwa katika kila hatua ya operesheni, badala ya kutoa, operesheni ya "kipekee AU" inafanywa kwa busara: 3) iliyobaki. B ni CRC - msimbo wa K-bit usiohitajika, ambao hubadilisha katika nambari iliyosimbwa C zero zilizowekwa upande wa kulia kwa K, i.e.

C= A*(2 K)+B.

Katika mwisho wa kupokea, operesheni O inafanywa kwenye msimbo C. Ikiwa salio sio sifuri, basi hitilafu ilitokea wakati wa maambukizi na msimbo A lazima uhamishwe tena.

MFANO Acha A = 1001 1101, na kuunda polynomial 11001.

Tangu K = 4, basi A*(2 K)=100111010000. Utekelezaji wa operesheni O kwa kuhesabu msimbo wa mzunguko unaonyeshwa kwenye Mtini. 3.2.

Jedwali 3.1

Sifa chanya za misimbo ya mzunguko ni uwezekano mdogo wa kugundua hitilafu na idadi ndogo ya biti zisizohitajika.

Mchele. 3.2. Mfano wa kupata msimbo wa mzunguko

Msimbo wa mzunguko ni msimbo wa mstari, ambayo ni seti ya mwisho ambayo imefungwa chini ya uendeshaji wa mabadiliko ya mzunguko wa vekta za msimbo zinazounda. Hebu itolewe n-vekta ya mwelekeo v = a 0 a 1 …n-1 na viwianishi kutoka uwanja wa mwisho F. Mabadiliko yake ya mzunguko huitwa vector v"=a n-1 kwa 0 kwa 1 ... n -2 .

Hebu tuzingatie n-nafasi ya hesabu ya dimensional juu ya uwanja wa Galois GF(2). Kila vekta a 0 a 1 …n-1 ya GF(2) mtu anaweza kulinganisha polynomial moja kwa moja a 0 +a 1 x+…+n -1 x n-1 na odds kutoka GF(2). Jumla ya vekta mbili a 0 a 1 …n-1 na b 0 b 1 …b n-1 imewekwa kwa mawasiliano na jumla ya polynomials inayolingana nao, bidhaa ya vitu vya shamba na vekta - bidhaa ya polynomial inayolingana na vekta hii kwa kipengele.

Hebu tuchunguze baadhi ya polynomial g(x) kutoka kwa nafasi iliyoelezewa ya mstari. Seti ya polima zote kutoka kwa nafasi hii ndogo ambazo zinaweza kugawanywa bila salio g(x), huunda nafasi ndogo ya mstari. Nafasi ndogo ya mstari inafafanua msimbo fulani wa mstari.

Msimbo wa mstari unaoundwa na aina ya polynomia C(g(x)), mawimbi ya baadhi ya polynomial g(x), inayoitwa polynomial inayozalisha, inaitwa polynomial.

Wacha tuonyeshe jinsi misimbo ya polynomial inahusiana C(g(x)) na misimbo ya mzunguko. Hebu a = a 0 …a n-1 ni neno la msimbo, na nambari inayolingana ya polynomial a(x) = a 0 +...+n -1 x n-1 . Kuhama kwa baiskeli a" inalingana na kanuni ya polynomial a"(x) = n -1 +a 0 x+…+n -2 x n -1 , ambayo inaweza kuonyeshwa kulingana na asili:

Kwa kuwa msimbo wa polynomial lazima ugawanywe na g(x), basi ili iwe cyclic, polynomial a"(x) lazima igawanywe na g(x) Kutokana na mazingatio haya tunaweza kuunda nadharia ifuatayo. Msimbo wa polynomial ni wa mzunguko ikiwa na tu ikiwa ni ya polinomia g(x) ni kigawanyo cha polynomial x n-1. Katika kesi hii, polynomial g(x) inaitwa polynomial inayozalisha ya msimbo wa mzunguko.

Katika nadharia ya usimbaji, nadharia ifuatayo imethibitishwa: ikiwa ni ya polynomial g(x) ana shahada n–k na ni mgawanyiko x n-1, basi C(g(x)) ni mzunguko wa mstari ( n, k) - kanuni.

Polynomial x n-1 kiwanda x n–1 = (x–1)(x n -1 +x n-1 +…+1). Kwa hivyo, misimbo ya mzunguko ipo kwa yoyote n. Idadi ya mzunguko n-bit misimbo sawa na idadi ya vigawanyiko vya polynomial x n-1. Majedwali ya upanuzi wa polynomial yametengenezwa ili kuunda misimbo ya mzunguko x n-1 katika polynomia zisizoweza kupunguzwa, yaani, katika zile ambazo zinaweza kugawanywa tu kwa umoja na yenyewe.

Hebu fikiria, kwa mfano, ni kanuni gani zinaweza kujengwa kulingana na polynomial x 7-1 uwanjani GF(2). Upanuzi wa polynomial katika vipengele visivyoweza kupunguzwa una fomu

Kwa kuwa inawezekana kuunda vigawanyiko sita vya polynomial x 7–1, ikichanganya vigawanyiko visivyoweza kupunguzwa, kuna misimbo sita ya mzunguko wa binary. ( n, k) -code imedhamiriwa, kwanza, na thamani n, na pili, thamani k = n – s, s- shahada ya mgawanyiko wa polynomial x n-1, ambayo inafafanua kanuni. Chini ni vigawanyiko vya polynomial na maadili yao yanayolingana k:

x – 1, s=1, k=6;

x 3 +x 2 +1, s=3, k=4;

x 3 +x+1, s=3, k=4;

(x–1)(x 3 +x 2 +1)=x 4 +x 2 +x+1, s=4, k=3;

(x–1)(x 3 +x+1)=x 4 +x 3 +x 2 +1, s=4, k=3;

(x 3 +x 2 +1)(x 3 +x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, s=6, k=1.

Msimbo wa (7, 6) una alama moja tu ya hundi, na msimbo wa (7, 1) una ishara moja tu ya habari. Wao ni, kwa mtiririko huo, msimbo wa kuangalia usawa na msimbo wa kurudia.

Kama msimbo wa kawaida wa mstari, msimbo wa mzunguko unaweza kubainishwa na matrix ya jenereta. Kwa hiyo, kazi ni kupata tumbo vile, yaani, kupata k michanganyiko ya nambari inayojitegemea inayounda. Kwa kusudi hili, tunatumia sifa ya msimbo wa mzunguko unaofungwa kwa heshima na uendeshaji wa mabadiliko ya mzunguko. Kumbuka kwamba mabadiliko ya mzunguko kwenda kulia kwa sehemu moja ni sawa na kuzidisha polynomial g(x) kwenye x. Kisha matrix ya kuzalisha inaweza kujengwa kwa kuchukua polynomial inayozalisha na k mabadiliko yake ya mzunguko:

Hebu sasa tuangalie jinsi gani, kwa kutumia polynomial inayozalisha g(x) = 1+x+x Usimbaji 3 unafanywa na msimbo (7, 4). Chukua, kwa mfano, neno la 4-bit (0101), ambalo linalingana na polynomial f(x) = x + x 3. Kuzidisha hizi polynomia mbili.

Msimbo wa baiskeli

Nambari za mzunguko ni kati ya misimbo ya kimfumo ambayo kila mchanganyiko husimbwa kwa kujitegemea (katika mfumo wa kizuizi) kwa njia ambayo habari k na alama za udhibiti huwa sawa kila wakati.

mavazi katika maeneo fulani. Uwezo wa kugundua na kusahihisha karibu makosa yoyote yenye upungufu wa chini ukilinganisha na nambari zingine, pamoja na unyenyekevu wa utekelezaji wa mzunguko wa vifaa vya usimbaji na kusimbua, ilifanya nambari hizi kuenea. Nadharia ya misimbo ya mzunguko inategemea nadharia ya kikundi na aljebra ya polynomia juu ya uwanja wa Galois.

Nambari ya mzunguko ni nambari ambayo mpangilio wa usambazaji wa mchanganyiko wa nambari unafanywa kwa njia ambayo wakati wa kusonga kutoka kwa mchanganyiko wowote kwenda kwa jirani, kila wakati umbali wa nambari ya Hamming unabaki thabiti.

Misimbo ya mzunguko ni familia nzima ya misimbo inayokinza makosa, ikijumuisha misimbo ya Hamming kama mojawapo ya aina zao, lakini kwa ujumla hutoa unyumbulifu zaidi katika suala la uwezo wa kutekeleza misimbo yenye uwezo muhimu wa kugundua na kusahihisha makosa yanayotokea wakati wa kutuma michanganyiko ya misimbo. juu ya njia ya mawasiliano. Msimbo wa mzunguko unarejelea misimbo ya kuzuia (n, k), ambamo tarakimu za k za kwanza zinawakilisha mchanganyiko wa msimbo msingi, na tarakimu zinazofuata (n ? k) ni tiki.

Uundaji wa misimbo ya mzunguko unategemea utendakazi wa kugawanya mchanganyiko wa msimbo unaopitishwa na polynomial isiyoweza kupunguzwa ya digrii r. Sehemu iliyobaki ya mgawanyiko hutumiwa kuunda nambari za hundi. Katika kesi hii, operesheni ya mgawanyiko inatanguliwa na operesheni ya kuzidisha, ambayo hubadilisha mchanganyiko wa msimbo wa habari wa k-bit upande wa kushoto na bits r.

Polynomial (polynomial) ambayo inaweza kuwakilishwa kama bidhaa ya polynomia za digrii za chini inaitwa reducible (katika sehemu fulani), vinginevyo haiwezi kupunguzwa. Ponomia zisizoweza kupunguzwa zina jukumu sawa na nambari kuu katika nadharia ya nambari. Polinomia zisizoweza kurekebishwa P(X) zinaweza kuandikwa kama nambari za desimali au binary au kama polynomia ya aljebra.

Mchakato wa kuweka msimbo wa baiskeli

Uwekaji wa msimbo wa mzunguko unategemea matumizi ya polinomia P(X) isiyoweza kupunguzwa, ambayo kuhusiana na misimbo ya mzunguko inaitwa jenereta, jenereta au polynomial inayozalisha (polynomial).

Michanganyiko ya msimbo wa binary kwa michanganyiko yote inachukuliwa kama alama za habari k kwa ajili ya kuunda misimbo ya mzunguko. Katika hali ya jumla, ikiwa mchanganyiko wa msimbo uliyopewa Q(x) umezidishwa na P(x) inayozalisha ya polynomial), matokeo yake ni msimbo wa mzunguko ambao una sifa fulani za kurekebisha kulingana na chaguo la P(x). Hata hivyo, katika kanuni hii, alama za udhibiti m zitapatikana katika maeneo mbalimbali katika mchanganyiko wa kanuni. Kanuni hiyo si ya utaratibu, ambayo inafanya utekelezaji wake wa mzunguko kuwa mgumu. Hali inaweza kurahisishwa kwa kiasi kikubwa ikiwa alama za udhibiti zinaongezwa mwishoni, yaani, baada ya alama za habari. Kwa kusudi hili, inashauriwa kutumia njia ifuatayo:

Tunazidisha mseto wa msimbo G(x) unaohitaji kusimba na X m moja yenye digrii sawa na P(x) ya polinomia inayozalisha;

Tunagawanya bidhaa G(x)Х m kwa polynomial inayozalisha Р(х m):

ambapo Q(x) ni mgawo wa mgawanyiko; R(x) - iliyobaki.

Kuzidisha usemi (2.1) na P(x) na kuhamisha R(x) hadi sehemu nyingine ya usawa bila kubadilisha ishara, tunapata:

Kwa hivyo, kulingana na usawa (2.2), nambari ya mzunguko, ambayo ni, ujumbe uliosimbwa F(x), unaweza kuunda kwa njia mbili:

Kuzidisha mseto wa msimbo mmoja wa msimbo binary kwa michanganyiko yote kwa P(x) inayozalisha ya polinomia;

Kwa kuzidisha mchanganyiko wa msimbo uliopeanwa G(x) na msimbo mmoja wa polinomia wa X wenye digrii sawa na P(x) inayozalisha, na kuongeza salio R(x) iliyopatikana baada ya kugawanya bidhaa G(x)X m kwa uzalishaji. polynomial P (X).

Usimbaji wa ujumbe

Inahitajika kusimba mseto wa msimbo 1100, unaolingana na G(x)=x 3 +x 2 kwa kutumia P(x)=x 3 +x+1.

Tunazidisha G(x) kwa X m, ambayo ina nguvu ya tatu, tunapata:

Kugawanya bidhaa G(x)Х m kwa polynomial inayozalisha Р(х m), kulingana na (2.1) tunapata:

au kwa usawa wa binary:

Kwa hivyo, kama matokeo, tunapata mgawo wa Q(x) wa digrii sawa na G(x):

Q(x)=x 3 +x 2 +x>1110

na iliyobaki:

Kama matokeo, mchanganyiko wa nambari ya binary iliyosimbwa na nambari ya mzunguko, kulingana na (2.2), itachukua fomu:

F(x)=1110 1011=1100010

Kwa kuwa kila mseto wa msimbo wa mzunguko unaoruhusiwa unawakilisha hesabu zote zinazowezekana za polynomial G(x) inayozalisha, lazima zigawanywe kwa P(x) bila salio. Kwa hivyo, kuangalia usahihi wa mseto wa msimbo unaokubalika unakuja kwa kutambua salio wakati wa kuigawanya kwa polynomial inayozalisha.

Kupokea salio kunaonyesha kuwepo kwa hitilafu. Sehemu iliyobaki ya mgawanyiko katika misimbo ya mzunguko ina jukumu la dalili.

Kwa mfano, mseto wa msimbo unaosambazwa F(x)=1100010, ulioundwa kwa kutumia polynomial inayozalisha P(x)=1011. Chini ya ushawishi wa kuingiliwa, mchanganyiko wa msimbo ulibadilishwa kuwa mchanganyiko F"(x)=1000010

Tunagawanya mchanganyiko unaokubalika kwa polynomial inayozalisha

Uwepo wa salio R(x)=001 unaonyesha hitilafu. Hata hivyo, haionyeshi moja kwa moja eneo la kosa katika mchanganyiko. Kuamua kosa, kuna mbinu kadhaa kulingana na uchambuzi wa syndrome.

Wacha tuamue eneo la kosa; kufanya hivyo, gawanya moja na nambari ya sifuri na P(x) = 1011.

Hitilafu ilitokea katika nambari ya kipengele:

Idadi ya mabaki -2>4-2=2

Hiyo ni, kosa liko katika kipengele cha pili.

Sifa kuu na jina lenyewe la nambari za mzunguko zinahusiana na ukweli kwamba michanganyiko yote inayoruhusiwa ya alama binary katika ujumbe unaopitishwa inaweza kupatikana kwa utendakazi wa mabadiliko ya mzunguko wa baadhi ya neno chanzo: Kwa kawaida, mchanganyiko wa msimbo wa msimbo wa mzunguko hazizingatiwi kama mlolongo wa sufuri na zile, lakini kama polynomial ya digrii fulani Nambari yoyote katika mfumo wowote wa nambari ya nafasi inaweza kuwakilishwa kwa fomu ya jumla kama: ambapo x ni msingi wa mfumo wa nambari; a - tarakimu za mfumo wa nambari fulani; p-1, p-2,... - kiashiria cha nguvu ambayo msingi hufufuliwa, na wakati huo huo nambari za serial ambazo zinachukua tarakimu. Kwa mfumo wa binary, x = 2, na a ni "O" au "1". Kwa mfano, mchanganyiko wa binary 01001 unaweza kuandikwa kama polynomial ya hoja x: Wakati wa kuandika mchanganyiko wa msimbo kama polynomial, kitengo katika tarakimu ya 1 imeandikwa kama neno "x", na sifuri haijaandikwa hata kidogo. . Kuwakilisha mchanganyiko wa msimbo kwa namna ya polynomials inakuwezesha kuanzisha mawasiliano ya moja hadi moja kati yao na kupunguza vitendo juu ya mchanganyiko wa vitendo kwenye polynomials Hivyo, kuongeza ya polynomials ya binary imepunguzwa kwa kuongeza modulo ya coefficients 2 kwa usawa kwa mfano, Kuzidisha kunafanywa kulingana na kanuni ya kawaida ya kuzidisha vitendaji vya nguvu, lakini mgawo unaotokana na kiwango fulani huongezwa modulo 2. Kwa mfano, Mgawanyiko pia unafanywa kama mgawanyiko wa kawaida wa polynomia Katika kesi hii, operesheni ya kutoa inabadilishwa na operesheni ya kuongeza modulo 2: Kama ilivyoonyeshwa hapo juu, misimbo inaitwa mzunguko kwa sababu mabadiliko ya mzunguko a n ^ a l L,..., a 2, a 1, a d1 a n1 ya mchanganyiko unaoruhusiwa n (, a n _ 2,..., a 1 na 0 pia ni mchanganyiko unaoruhusiwa, wakati wa kutumia uwakilishi katika mfumo wa polynomials, huundwa kama matokeo ya kuzidisha polynomial hii kwa x Ikiwa Y(x) = a pL x n1 + a n2 x n "2 +. .. + a. ( x + a 0, kisha Y(x)x = a n] x n + a n 2 x n "1 +... + a x x 2 + a^x. Ili shahada ya polynomial isizidi n -1, neno x" linabadilishwa na moja, kwa hivyo: Kwa mfano, tuna mchanganyiko wa msimbo 1101110->x katika +x 5 +x 3 +.x g -1-x. Hebu tuihamisha kwa tarakimu moja. Tunapata : Ambayo ni sawa na kuzidisha polima asilia kwenye x: Nadharia ya kuunda misimbo ya mzunguko inategemea sehemu za aljebra za juu ambazo husoma sifa za polimanomia mbili. yaani, polynomials ambazo haziwezi kuwakilishwa kama bidhaa za polynomia za digrii za chini zinaweza kugawanywa peke yake na moja. Kutoka aljebra ya juu inajulikana kuwa binomial x"+1 imegawanywa bila salio na polynomia isiyoweza kupunguzwa. Katika nadharia ya usimbaji, polimanomia zisizoweza kurekebishwa huitwa polimanomia zinazozalisha, kwa kuwa "huunda" michanganyiko ya msimbo inayoruhusiwa (polynomia zisizoweza kupunguzwa zimeorodheshwa, angalia Jedwali 8.4). ) (9). Wazo la kuunda msimbo wa mzunguko linatokana na ukweli kwamba polynomial inayowakilisha sehemu ya habari ya mchanganyiko wa msimbo lazima ibadilishwe kuwa polynomial ya digrii isiyozidi n-1, ambayo inaweza kugawanywa bila a. salio kwa nambari ya P(x) inayozalisha Ni muhimu kwamba kiwango cha mwisho kilingane na idadi ya tiki ya mseto wa msimbo. mgawanyiko bila salio na P(x) ya aina nyingi. Ujenzi wa mseto wa msimbo unaoruhusiwa umepunguzwa hadi zifuatazo: 1. Tunawakilisha sehemu ya taarifa ya mseto wa msimbo na urefu k. . 3. Gawa polima O(x)x" katika polinomia P(x) inayozalisha, kiwango ambacho ni sawa na r. Kutokana na kuzidisha O(x) kwa xr, kiwango cha kila monomia kilichojumuishwa katika O( x) huongezeka kwa r Wakati wa kugawanya bidhaa ya x g O[x) kwa polynomial ya digrii r hutoa mgawo C(x) wa shahada sawa na 0(x) Matokeo ya shughuli hizi yanaweza kuwakilishwa katika fomu: (8.28) ambapo R(x) ni salio la kugawanya 0(x)x r kwa P(x). Kwa kuwa C(x) ina digrii sawa na 0(x), basi C(x) ni mseto wa msimbo sawa wa ¿-bit. Kiwango cha salio kwa wazi hakiwezi kuwa kikubwa kuliko kiwango cha polynomia inayozalisha, yaani, shahada yake ya juu ni sawa na r-1. Kwa hivyo, idadi kubwa ya tarakimu za salio haizidi r Kuzidisha pande zote mbili za (8.28) na P(x), kutambaa: (8.29) (alama ya kutoa inabadilishwa na ishara ya kuongeza modulo 2). Ni wazi, F(x) inaweza kugawanywa na P(x) bila salio. Polynomial F(x) ni muundo wa msimbo wa mzunguko unaoruhusiwa. Kutoka (8.29) inafuata kwamba mchanganyiko wa msimbo unaoruhusiwa wa msimbo wa mzunguko unaweza kupatikana kwa njia mbili: kwa kuzidisha mchanganyiko wa msimbo wa msimbo rahisi C(x) kwa kuzalisha P(x) ya polynomial au kwa kuzidisha mchanganyiko wa msimbo O. (x) ya msimbo rahisi kwa x r moja kwa kuongeza kwenye bidhaa hii ya salio P(x), iliyopatikana kwa kugawanya bidhaa kwa P(x) inayozalisha ya polinomia. Kwa njia ya kwanza ya kuweka msimbo, biti za habari na uthibitishaji hazijatenganishwa kutoka kwa kila mmoja (msimbo hauwezi kutenganishwa). Hii inafanya mchakato wa kusimbua kuwa mgumu kutekeleza kwa vitendo. Kwa njia ya pili, nambari inayoweza kutenganishwa inapatikana: bits za habari huchukua nafasi za juu zaidi, bits za p-c zilizobaki ni za uthibitishaji. Njia hii ya kuweka msimbo hutumiwa sana katika mazoezi. Mfano 3. Kutokana na mchanganyiko wa kanuni 0111. Hebu tujenge kanuni ya mzunguko na d o = 3. Suluhisho. Katika hatua ya kwanza, kwa kuzingatia d o = 3 inayohitajika, tunaamua urefu wa kificho l na idadi ya vipengele vya hundi k. Kwa mchanganyiko wa nambari nne wa nambari N-16. Kisha kwa d = 3 kutoka kwa uhusiano 16 (Jedwali 8.3) tunapata n - 7, kwa mtiririko huo, k = n - m - = 7 - 4 = 3. Kwa hiyo, kanuni (7.4) inahitajika. Kutumia jedwali la polynomials zinazozalisha (Jedwali 8.4) kwa k = 3, tunaamua P (x) = x 3 + x 2 + 1. Ifuatayo: 1) kwa ujumbe 0111 tuna O (x) = x 2 + x + 1 ; 2) zidisha 0(x) kwa x 3 (tangu r = 3): O(x) x 3 = (x 2 -I- x + 1) x 3 = x 5 + x 4 + x 3; 3) gawanya (E(x)x 3 kwa P(x): 4) tunapata: ^(x) = O (x) x 3 0 R (x) = x 5 + x 4 + x 3 + 1. Polynomial hii inalingana na mchanganyiko wa kanuni: Shughuli zote zilizo hapo juu zinaweza pia kufanywa kwa nambari za binary: Jedwali 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001. Hebu sasa tuunde mchanganyiko wa msimbo unaoruhusiwa kwa njia ya kwanza: F( x)=C(x)P(x). Wacha tufanye kuzidisha kwa kuwakilisha polynomials kama nambari za binary: Inaweza kuonekana kuwa katika mchanganyiko wa msimbo unaosababisha haiwezekani kutofautisha bits za habari na uthibitishaji. Ugunduzi wa hitilafu wakati wa usimbaji mzunguko huja hadi kugawanya mseto wa msimbo uliopokewa na polimanomia sawa inayozalisha ambayo ilitumika wakati wa usimbaji (aina yake lazima ijulikane wakati wa upokeaji). Ikiwa hakuna makosa katika mchanganyiko wa msimbo uliopokelewa (au ni kwamba mchanganyiko wa msimbo uliopitishwa unabadilishwa kuwa mwingine unaoruhusiwa), basi mgawanyiko na polynomial inayozalisha utafanywa bila salio. Ikiwa mgawanyiko unasababisha salio, basi hii inaonyesha kuwepo kwa kosa. Mfano 4. Kama mchanganyiko wa msimbo unaoruhusiwa, tunachukua mchanganyiko wa msimbo uliopatikana katika mfano uliopita: P(x) = x 5 + x 4 + x 3 + 1, na P(x) = x 3 + x 2 +1, au kwa fomu ya binary E (0,1) = 0111001; P (0,1) = 1101. Hebu tufikiri kwamba katika sehemu ya habari hitilafu ilitokea katika tarakimu muhimu zaidi (ya 7) (tunahesabu tarakimu kutoka kulia kwenda kushoto). Mchanganyiko wa msimbo unaokubalika unaonekana kama 1111001. Wacha tufanye operesheni ya kugundua makosa: Uwepo wa mabaki ya 110 unaonyesha kosa. Nambari za cyclic hutumiwa sana katika mifumo ya usambazaji wa habari. Kwa mfano, katika itifaki ya modem inayotumiwa sana \ 7.42, kusimba vikundi vya msimbo, jenereta ya polynomial d(X) = X 16 + X "-2 + X 5 + 1 inatumiwa, ambayo ni sawa na nambari 1 0001 0000 0010. 0001, pamoja na jenereta ya juu zaidi ya polynomial d(X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X 4 + X 2 + 1. 8.6.

Nambari rahisi zaidi ya mzunguko c hukuruhusu kugundua makosa moja na makosa ya msururu usio wa kawaida. Polynomial inayozalisha ya msimbo huu ina fomu Miongoni mwa polinomia zisizoweza kupunguzwa zilizojumuishwa katika upanuzi, polynomial hii ni polynomial ya shahada ndogo zaidi Kwa hiyo, kwa idadi yoyote ya bits ya habari, biti moja tu ya hundi inahitajika. Thamani ya ishara ya biti hii inahakikisha usawa wa idadi ya zile katika mchanganyiko wowote wa msimbo unaoruhusiwa. Nambari inayotokana ya usawa wa mzunguko ina uwezo wa kugundua sio makosa moja tu kwenye biti za kibinafsi, lakini pia makosa katika idadi yoyote isiyo ya kawaida ya bits.

Mfano. Tengeneza msimbo wa mzunguko kwa vile polynomial inayozalisha ni polinomia ya shahada ya 1, idadi ya tarakimu za hundi Kwa hivyo, Ili kuunda msimbo wa mzunguko, tunaunda matrix inayozalisha.

Ili kuunda matrix ya ziada, tunapata mabaki kutoka kwa kugawa safu ya mwisho ya matrix iliyopitishwa, iliyowekwa na sufuri, na polynomial iliyochaguliwa:

Kwa hivyo, matrix ya ziada C,k ina fomu

Sasa tunajenga matrix ya kuzalisha

Safu mlalo za matrix hii ni michanganyiko mitatu ya misimbo ya kwanza. Michanganyiko iliyosalia inayoruhusiwa inaweza kupatikana kwa kujumlisha modulo mbili michanganyiko yote ya safu mlalo ya matriki Michanganyiko ya misimbo iliyoharibiwa inayotolewa imetolewa katika Jedwali. 39.

Jedwali 39 (tazama tambazo)

Ya kufurahisha sana ni kuzingatia nambari rahisi ifuatayo iliyoundwa kwa kutumia polynomial isiyoweza kupunguzwa ya digrii ya pili.

Aina ya jumla ya matrix inayozalisha ya msimbo wa mzunguko unaoundwa na polynomial hutofautiana katika muundo wa matrix ya ziada yenye safu mbili.

Ni rahisi kuthibitisha kuwa wakati wa kugawanya na polynomial fulani inayozalisha monomia zinazoonyesha kamba.

matrix ya utambulisho (ili kupata matrix ya ziada, aina tatu za masalio huundwa: 11, 01 na 10. Kwa hivyo, uzito wa kila mchanganyiko wa -code inayotokana itakuwa angalau mbili. Umbali wa chini wa nambari kati ya mchanganyiko wowote mbili pia ni mbili. Lakini moja rahisi pia ina sifa ya maadili sawa na hundi moja ya usawa inayoundwa na binomial ya shahada ya kwanza inawezekana kuchunguza sio tu makosa yoyote ya wingi usio wa kawaida, lakini pia makosa yoyote ya karibu yaliyounganishwa, pamoja na makosa yote yaliyotengwa na kipengele kimoja kisichoharibika.