NEVARNOST KAOSA V DIGITALNEM SITU DRUGEGA REDA Matej Šalamon, Tomaž Dogša Univerza v Mariboru, Fakulteta za elektrotehniko računalništvo in informatiko, Maribor, Slovenija Ključne besede: sistemi digitalni, filtri električni, filtri digitalni, kaos, aritmetika komplementa dvojiškega, hiperobčutljivost na pogoje začetne, odpoved sistema, vezja mikroelektronska, filtri reda drugega, modeli linearni, modeli nelinearni, strukture 16-bit Povzetek: Nekateri digitalni sistemi se lahko v določenih razmerah začnejo obnašati kaotično, kar lahko privede do začasne odpovedi sistema, V skupino kaotično potencialnih vezij spadajo tudi digitalna sita, ki so sestavni del mnogih mlkroelektronskih vezij. V prispevku obravnavamo nevarnost kaotičnega obnašanja digitalnega sita drugega reda. Z računalniško simulacijo (programski paket Matlab) smo analizirali obnašanje linearnega in 16-bitnega nelinearnega modela. Ugotovili smo, da se linearni model nikakor ne more obnašati kaotično. Nujna, vendar ne edina pogoja za kaotičnost sta: 1. struktura sita mora biti vsaj 16-bitna, 2. na vhodu ni prisoten noben signal. Kaotičnost je pogojena tudi z ustreznim izborom začetnih stanj in vrednosti koeficientov, ki zagotavljajo, da sito deluje na robu stabilnega območja. Kaotično digitalno sito je možno tudi koristno uporabiti kot generator psevdokaotičnih sekvenc, ki ga potrebujemo pri razvoju čipov na področju kriptografskih sistemov. Danger of Chaos in a Second-order Digital Filter Keywords: digital systems, electrical filters, digital filters, chaos, binary complement arithmetic, sensitive dependence on initial conditions, system failure, microelectronic circuits, second-order filters, linear models, non-linear models, 16-bit structures Abstract: Under certain circumstances some digital systems can exhibit chaotic behaviour resulting in a temporary system failure. Digital filters are very often building blocks of microelectronic circuits. They belong to the group of potentially chaotic circuits. In this paper we discuss the danger of chaos in a second-order digital filter. With the computer simulation program (Matlab) we analysed the behaviour of linear and non-linear 16-bit model. We found that the chaotic behaviour is impossible in the linear model. In order to exhibit chaotic behaviour, a digital filter has to be at least of 16-bit structure and no signals must be present on input, and filter's coefficients must guarantee that filter operates on the boundary of the stable region. The chaotic digital filter can be used as a generator of chaotic sequences that are needed in the cryptographic systems. 1. Uvod Kaotične sistetne srečujemo na različnih znanstvenih področjih l1, smo določiti interval, znotraj katerega se v tem primeru smeta spreminjati začetni stanji xi (0) in X2(0). Ob upoštevanju enačbe 5, vrednosti koeficienta a = 0.5 in enakosti xi (0) = -X2(0) = xo, smo prišli do zaključka, da mora biti xo > 1/2 ■ (2-a) '''^ = 0.612372435695... (12) Na sliki 1a oba seštevalnika združimo in upoštevamo nelinearnost aritmetike dvojiškega komplementa, dobimo nelinearni model digitalnega sita, ki ga prikazuje slika 4. Če na vhodu sita signal ni prisoten, lahko nelinearni model opišemo z naslednjo nelinearno diferenčno enačbo x,(n + 1) X2(n + 1) X2(n) f(b ■ x.|(n) + a ■ Xgin)) (8) kjer je f(*) funkcijska odvisnost, prikazana na sliki 3. Za začetna pogoja xi(0) = X2(0) naj velja, da sta iz množice: x = : -1 < x^ < 1, - 1 < X2 < 1 (9) Ker se bomo v nadaljevanju, podobno kot pri linearnem modelu, osredotočili na obnašanje nelinearnega modela na meji stabilnosti, tj. pri b = -1 in |a| < 2, zapi-šimo ustrezno diferenčno enačbo: x(n + 1) = Xi{n + 1) Xjln + I) X2(n) f(-1 ■ x,(n) + a ■ X2(n) = F[x(n) (10) Kakor hitro bo torej xo > 0.612372435695, bosta začetna pogoja ležala izven območja I lo, kar pomeni, da bo pri operaciji seštevanja prihajalo do prekoračitev. Oglejmo si podrobneje analizo 16-bitne strukture digitalnega sita (slika 5), ki smo jo izvedli s programom Simulink. Koeficienta a in b smo izbrali tako, daje sistem deloval na robu stabilnosti, kar pomeni, da smo izbrali že omenjeni vrednosti: a = 0.5, b = -1. Z namenom, da bi opazovali gibanje trajektorije pn različnih začetnih pogojih xo = X2(0) = -xi(0), smo xo spreminjali na intervalu med O in 1. Dobili smo rezultate, na osnovi katerih smo trajektorije razvrstili v tri različne skupine, in sicer: " Tip I: trajektorija poteka po elipsi. ® Tip II: trajektorija potuje periodično po končnem številu elips. ® Tip lil: trajektorija poteka po neskončno mnogo elipsah in pri tem izkazuje kaotično obnašanje ter fraktalno geometrijo. Pri izboru začetnih pogojev na intervalu O < xo < 0.61232 smo dobili pričakovano trajektorijo tipa I (slika 6a), saj velja, da je xo e I lo. Razlog za nekoliko nižjo zgornjo mejo intervala, ki bi morala biti po analitičnem izračunu 0.612372435695, je 16-bitna omejenost binarnega zapisa števil. S prekoračitvijo vrednosti začetnega pogoja xo > 0.61232 postane ob^ našanje sistema zelo nenavadno. Pri začetnem pogoju xo = 0.615 se pojavi kaotična trajektorija - trajektorija tipa III, ki jo prikazuje slika 6b. Ta trajektorija poteka po mnogih elipsah, ki tvorijo fraktalne vzorce. Med njimi obstajasamopodobnost preko vseh meril, kar je značilnost fraktalnih podob. Če vrednost začetnega pogoja še povečamo, lahko pri xo = 0.6634 opazimo, da se gibanje trajektorije nekako umiri oziroma omeji na gibanje po 10 različnih elipsah (slika 6c). Ker je takšno gibanje trajektorije periodično, mu pravimo perioda 10, sicer pa velja, da številka periode označuje število elips, po katerih se trajektorija giblje. CI3"-»- _ /loor(u'2^JS)mS -->■{ K") --------- —►GD Rezjnje Fixed-Point Add 1 5,00018.013 Fixe d-Poiill Gair.1 0,S O nxed-Point Convefsion/S5tuiation2 1/z o Fixed-Point Unit Oeiayl Fixed-Point Gain C Fixed-Point Conversion/Satutation3 -KD Slika 5: 16-bitna struktura digitalnega sita, uporabljena pri računalniški simulaciji s programom Simulink Spreminjanje začetnih pogojev in posledične spremembe trajektorij lahko strnemo v tabeli 1. Označba "spremenljiv" pomeni, da gre za trajektorije tipa II ali trajektorije tipa III. Vsak interval z omenjeno oznako bi lahko razdelili še naprej v manjše intervale, znotraj katerih bi se pojavljale trajektorije tipa II, in intervale z oznako "spremenljiv". Tabela 1: Tip trajektorije glede na izbran začetni pogoj XQ = X2(0) = -X1(0) Začetni pogoj Tip trajektorije 0_< Xq < 0.61232 I 0.61232 < Xq < 0.61550 0.61550 < Xq < 0.66448 0.66448 < Xq < 0.67757 0.67757 < Xq < 0.92237 spremenljiv perioda = 10 spremenljiv ; perioda = 2 0.92237 < Xq < 0.94932 0.94932 < Xn < 0.98780 0.98780 < Xo< 1,0 spremenljiv ; perioda = 18 spremenljiv 0,8 06 ■ 0,4 02 x-, U -0 2 ■0 4 -OB -0,8 O a=0 5, b=-1 X2=-k,=0S1, šl itetac,j=10000 -1 -0,8 -0,6 -0,4 -0 2 O 0,2 0.4 0,6 0,8 a) -1 • -0,8 -0,3 ■ -0,4 -0,2 0 ., 0,2 ü,4 0,8 U,ö 1 «1 b) a=0,5;,b=-,1;-.xj=-x^=0.66;šl. ileracij=10000 O.....' o o .jO.. .O... -1 -0 8 -0,8 -0 4 -0 2 O 0,2 0 4 0,3 0 8 1 C) Slika 6: Trajektorija: a) tipa I; b) tipa lil; c) tipa II - perioda 10 Slika 7: Razlika med dvema kaotičnima sekvencama izraža hiperobčutljivost kaotičnega digitalnega sita 3.2 Hiperobčutljivost na začetne pogoje Kaotičnost sistema je povezana s hiperobčutljivostjo na začetne pogoje, iahko patudi nadoločenet.i. bifurkacij-ske parametre. Glede na to smo pričakovali, da bo digitalno sito, ki je lahko kaotično, hiperobčutljivo. S simulacijo smo ugotovili, da je obravnavano sito hiperobčutljivo na začetni stanji xi(0) in X2(0), medtem ko hiperobčutljivosti na katerega izmed drugih parametrov nismo odkrili. Z namenom, da bi prikazali hiperobčutljivost kaotičnega digitalnega sita, smo v skladu s tabelo 1 izbrali dva začetna pogoja, pri katerih se sito obnaša kaotično. Poiskali smo pripadajoča poteka trajektorij A in B, ki sta startali iz izbranih začetnih stanj: » Trajektorija A: X2a(0)= 0.987884521484; xia(0) = -0.987884521484 » Trajektorija B: X2b(0)= 0.987915039062; XIb(0)= -0.987884521484 Kljub minimalni razliki med začetnima pogojema'' sta se trajektoriji A in B zelo hitro oddaljili ena od druge. Različnost njunega gibanja oziroma različnost sekvenc spremnijivke X2a in X2b prikazuje siika 7. Sekvenca spremenljivke X2a je predstavljena s polno črto, sekvenca spremenljivke X2b pa s prekinjeno črto. Do približno 27. iteracije se sekvenci zelo dobro ujemata, takoj za tem pa se pričneta druga od druge vse bolj oddaljevati in se nikoli več ne ujameta. To kaže, da je kaotično digitalno sito zares hiperobčutljiv sistem. 4. Vpliv dolžine binarne besede na kaotičnost digitalnega sita čeprav se digitalna sita uporabljajo že več kot dve desetletji, je bil kaos v njih odkrit razmeroma pozno. Razlog za to je prav gotovo uporaba prekratkih binarnih besed pri praktičnih implementacijah. Znano je namreč, da imajo kaotični sistemi teoretično neskončno mnogo stanj, kar pa za realizirana digitalna sita, omejena s končno dolžino binarne besede, ne drži. Zaradi tega so se vedno znova pojavljali dvomi o kaotičnosti realnih digitalnih sit. Pri analitičnih obravnavah digitalnega sita drugega reda smo privzeli, da se digitalno sito obnaša kaotično, če so stanja v situ predstavljena s števili, ki imajo lahko neomejeno število decimalnih mest /4/. V praksi vemo, da to ni mogoče, saj so v digitalnih strukturah števila vedno omejena z določenim končnim številom bitov. Pojavi se vprašanje, ali je takšna "omejena" struktura digitalnega sita torej sploh lahko kaotična. Ker vemo, da so pravi kaotični sistemi zvezni sistemi, iahko v primeru digitalnega sita drugega reda govorimo le o psevdokaotičnem obnašanju /6/. Za praktično realizirano sito velja, da je psevdokaotično le, če je kvan-tizacija dovolj natančna, kar pomeni, da morajo biti števila predstavljena z dovolj dolgo binarno besedo. Če je le-ta prekratka, se zgodi, da je kaotičnost sita prikrita. Glede na to, da sta v obravnavanem sistemu prisotni le dve različni spremenljivki stanj xi in X2, lahko na osnovi vseh možnih kombinacij in dolžine binarne besede L izračunamo število vseh možnih stanj N po enačbi: N = 2^ • 2*- = (13) 1 Začetna pogoja smo izbrali tako, da sta se razlikovala v enem samem bitu. V kolikor uporabimo 16 in več bitov, se kaotično obnašanje sita na videz ne razlikuje več od obnašanja sita s teoretično neomejeno dolžino binarne besede. O tem smo se prepričali z računalniško simulacijo 16-bitne strukture in strukture, kjer so bile obravnavane vrednosti s plavajočo vejico. Ugotovili smo tudi, da 8-bitna struktura ne more biti kaotična, saj je število različnih stanj premajhno. To je razvidno tudi s slike 8, ki kaže, da trajektorija B-bitne strukture, za razliko od trajektorije 16-bitne strukture, ne izriše za kaos značilne fraktalne podobe. T. Lin in L. Chua pravita, da kaos v manj kot 16-bitni strukturi ni mogoč /6/. 5. Zaključek Eden od razlogov za odpoved mikroelektronskih vezij je lahko kaotična narava, skrita v njegovih osnovnih gradnikih. Kljub temu, da je odkrivanje območja kao-tičnosti sistemov v splošnem zelo zahtevno, je kaotič-nost kompleksnega sistema smiselno preveriti s simulatorjem že na konceptualnem nivoju in se na ta način izogniti nezaželjenim in nepredvidljivim težavam pri delovanju. a=0.5, b=-1: x2=-/',=0.615; -St. iteracij=10DOOO c.or I ........L « v. : : : ...... • 0, 4 t...... ? 02 O -0,2 ■C. 4 ■n.6 -0,8 ■•v ^ .....:........:....... .....i........ .....^ '.'i:.......^ : _ P.^ -r A" -I 0 8 -0,6 -0 2 O 0 3 0,4 0 6 0,8 1 a) :a