Limita inferioară a complexității unei clase de algoritmi nu este definită în mod unic. De exemplu, f(n) = 0 este întotdeauna limita inferioară, precum și oricare funcție negativă. Cu cât limita inferioară găsită este mai mare, cu atât este mai netrivială și mai valoroasă. Un semnal că nu vom putea construi o limită inferioară mai mare decât

PE capitolul 4 Algoritmi optimi

limita inferioară pe care o avem deja f(n), poate servi, de exemplu, drept prezență A e .s4, pentru care T A (n) = f(n). O astfel de situație o întâlnim în paragraful anterior din Exemplele 14.1 și 14.3. Algoritmul pentru găsirea celui mai mic element cunoscut de noi și algoritmul pentru găsirea binară a locului unui element într-o matrice ordonată au fiecare o complexitate care coincide cu limita inferioară găsită. Acești algoritmi sunt optimi în sensul următoarei definiții.

Definiție 15.1. Lăsa .s4- o clasă de algoritmi pentru rezolvarea unei probleme. Să existe un acord cu privire la modul în care sunt măsurate costurile algoritmilor și ce este considerată dimensiunea intrării și să fie n- desemnarea dimensiunii intrării. Algoritm A e .s4 numit optimîn j4, dacă T A(n) este o limită inferioară a complexității algoritmilor din j4.

Exemplul 15.1. Când se obține o limită inferioară a complexității și se demonstrează optimitatea, uneori este util să se invoce funcții pe seturile acelor valori care apar în timpul execuției algoritmului, de exemplu, pe seturile de valori ale variabilelor utilizate de algoritmul.

Propunerea 15.1.funcția f(n) = Г 2 n 1 - 2 este o limită inferioară a complexității algoritmilor pentru selecția simultană a celor mai mari și mai mici elemente ale unui tablou de lungime n folosind comparații.

Dovada. Fiecare etapă a execuției unui algoritm arbitrar V, bazat pe comparații și conceput pentru a găsi cele mai mari și mai mici elemente ale unui tablou, poate fi caracterizat printr-un cvadruplu ( A, B, C, D) submultimile multimii elementele initiale (x g, x 2, ■ ■ ■, x n ), Unde

A constă din toate acele elemente care nu au fost deloc comparate;

B constă din toate acele elemente care au participat la unele comparații și s-au dovedit întotdeauna a fi mari;

C constă din toate acele elemente care au participat la unele comparații și s-au dovedit întotdeauna a fi mai mici;

D constă din toate acele elemente care au participat la unele comparații, uneori s-au dovedit a fi mai mari și alteori mai mici.

Lăsa a, b, c, d- numărul de elemente ale mulţimilor A, B, C, D respectiv. Situația inițială este caracterizată de egalități a = n, b = = c = d = 0. După finalizarea algoritmului, egal-

§ 15 . Algoritmi optimi

stva A = 0, b = c = 1, d = n-2. După prima comparație, pe parcursul întregii execuții a algoritmului, inegalitățile b^1,c^1.

Toate comparațiile făcute în timpul executării algoritmului V, pot fi împărțite în tipuri, notate AA,AB,AC,AD,BB,BC,BD,CC,CD,DD, ex: comparația aparține tipului AB , dacă unul dintre elementele comparate este luat din DAR , altul-de LA , etc. Pe baza acestui lucru, putem scrie totul posibile modificări patru pași (a, b, Cu, d) sub influenţa comparaţiilor de diferite tipuri.

Deci, cea mai responsabilă acțiune a managerului de memorie este alocarea unui cadru memorie cu acces aleator pentru a plasa în ea o pagină virtuală situată în memorie externa. Amintiți-vă că avem în vedere o situație în care dimensiunea memorie virtuala pentru fiecare proces poate depăși semnificativ dimensiunea memoriei principale. Aceasta înseamnă că atunci când alocați o pagină de memorie principală, este foarte probabil să nu se găsească niciun cadru de pagină liber. În acest caz sistem de operare în conformitate cu criteriile stabilite în acesta ar trebui:

• găsi unele pagina ocupata memoria principala;
• mutați, dacă este necesar, conținutul său în memoria externă;
• rescrieți conținutul paginii virtuale dorite din memoria externă în acest cadru de pagină;
• modificați în mod corespunzător elementul necesar din tabelul de pagini corespunzător;
• continua executarea procesului la care aceasta pagina virtuală Necesar.

Rețineți că la înlocuire, trebuie să transferați pagina de două ori între memoria principală și cea secundară. Procesul de înlocuire poate fi optimizat prin utilizarea bit de modificare(unul dintre atributele paginii din tabelul paginii). Bitul de modificare este setat de computer dacă pe pagină a fost scris cel puțin un octet. Când este selectat un candidat înlocuitor, bitul de modificare este verificat. Dacă bitul nu este setat, nu este nevoie să rescrieți această pagină pe disc, o copie a acesteia este deja pe disc. O metodă similară se aplică și paginilor de numai citire, acestea nu sunt niciodată modificate. Această schemă reduce timpul de procesare a erorilor de pagină.

Există un numar mare de diverși algoritmi de înlocuire a paginii. Toate sunt împărțite în locale și globale. Algoritmii locali, spre deosebire de algoritmii globali, alocă un număr fix sau ajustabil dinamic de pagini fiecărui proces. Când un proces a epuizat toate paginile sale, sistemul va elimina una dintre paginile sale din memoria fizică și nu din paginile altor procese. Algoritmul global de înlocuire, în cazul unei excepții, va fi mulțumit de eliberarea oricăreia pagina fizica, indiferent de proces căruia i-a aparținut.

Algoritmii globali au o serie de dezavantaje. În primul rând, fac unele procese sensibile la comportamentul altor procese. De exemplu, dacă un proces din sistem folosește un număr mare de pagini de memorie în același timp, atunci toate celelalte aplicații se vor confrunta cu o încetinire severă din cauza cadrelor de memorie insuficiente pentru munca lor. În al doilea rând, o aplicație care se comportă greșit poate submina întregul sistem (cu excepția cazului în care, desigur, sistemul are o limită a dimensiunii memoriei alocate procesului), încercând să capteze mai multa memorie. Prin urmare, într-un sistem multitasking, uneori este necesar să se utilizeze algoritmi locali mai complexi. Utilizarea algoritmilor locali necesită ca sistemul de operare să stocheze o listă de cadre fizice alocate fiecărui proces. Această listă de pagini este uneori numită set rezident proces. Într-una din secțiunile următoare, este luată în considerare o variantă a algoritmului de schimb, bazată pe aducerea setului rezident în conformitate cu așa-numitul set de lucru proces.

Eficiența algoritmului de obicei evaluat pe o anumită secvență de referințe de memorie pentru care se numără numărul de erori de pagină care apar. Această secvență se numește linia lovită(șir de referință). Putem genera artificial un șir de lovituri folosind un senzor numere aleatorii sau de urmărire sistem specific. Ultima metoda oferă prea multe link-uri, pentru a reduce numărul cărora puteți face două lucruri:

• pentru o anumită dimensiune a paginii, vă puteți aminti doar numerele acestora și nu adresele către care se duce linkul;
• mai multe link-uri consecutive către o pagină pot fi remediate o dată.

După cum am menționat deja, majoritatea procesoarelor au cele mai simple hardware, permițându-vă să colectați unele statistici privind accesările la memorie. Aceste instrumente includ de obicei două steaguri speciale pentru fiecare intrare în tabelul de pagină. Steagul de referință ( bit de referință ) este setat automat atunci când are loc orice acces la această pagină, iar pavilionul de modificare ( bit de modificare ) deja discutat mai sus este setat dacă se face o scriere pe această pagină. Sistem de operare verifică periodic aceste steaguri pentru a evidenția paginile utilizate în mod activ, după care valorile acestor steaguri sunt resetate.

Luați în considerare o serie de algoritmi de înlocuire a paginii.

Algoritmul FIFO. Scoaterea primei pagini primite

Cel mai simplu algoritm. Fiecărei pagini i se atribuie un marcaj de timp. Acest lucru este implementat pur și simplu prin crearea unei cozi de pagini, la sfârșitul căreia paginile cad atunci când sunt încărcate memorie fizică, și sunt luate de la început atunci când memoria trebuie eliberată. Selectat pentru înlocuire cea mai veche pagină. Din păcate, această strategie este destul de probabil să înlocuiască paginile foarte utilizate, cum ar fi paginile de cod. procesor de cuvinte la editarea unui fișier. Rețineți că atunci când înlocuiți pagini active totul funcționează corect, dar eroarea paginii apare imediat.

Anomalie Belady

La prima vedere, pare evident că cu cât sunt mai multe cadre de pagină în memorie, cu atât vor apărea mai puține erori de pagină. În mod surprinzător, acesta nu este întotdeauna cazul. După cum au descoperit Bilady și colegii, anumite secvențe de accesări la pagini duc de fapt la o creștere a numărului de încălcări ale paginii la creşterea cadrelor alocate procesului. Acest fenomen se numește „anomaliile lui Bilady” sau „anomalii FIFO”.

Un sistem cu trei cadre (9 defecte) este mai eficient decât cu patru cadre (10 defecte) pentru șirul de acces la memorie 012301401234 la alegerea strategiei FIFO.

Orez. 10.1.

Algoritmul optim (OPT)

Una dintre consecințele descoperirii anomaliei lui Bilady a fost căutarea unui algoritm optim care, atunci când șir dat accesările ar avea frecvența minimă a erorilor de pagină dintre toți ceilalți algoritmi. Un astfel de algoritm a fost găsit. Este simplu: înlocuiți pagina care nu va fi folosită pentru cea mai lungă perioadă de timp.

Fiecare pagină ar trebui să fie etichetată cu numărul de instrucțiuni care vor fi executate înainte ca primul link să fie creat către pagina respectivă. Pagina pentru care acest număr este cel mai mare ar trebui să fie eliminată.

Acest algoritm este ușor de descris, dar imposibil de implementat. Sistemul de operare nu știe ce pagină va fi următoarea accesată. (Anterior astfel de probleme au apărut în timpul programării procesului - algoritmul SJF).

Pe de altă parte, putem concluziona că, pentru ca algoritmul de înlocuire să fie cât mai aproape de algoritmul ideal, sistemul trebuie să prezică cât mai precis posibil accesele la memorie ale proceselor. Acest algoritm este utilizat pentru a evalua calitatea algoritmilor implementați.

Apăsând cea mai lungă pagină nefolosită. algoritmul LRU

Una dintre aproximările la algoritmul OPT este algoritmul bazat pe regulă euristică că trecutul recent este un bun etalon pentru prezicerea viitorului apropiat.

Diferența cheie dintre FIFO și algoritmul optim este că unul privește înapoi, iar celălalt privește înainte. Dacă folosiți trecutul pentru a aproxima viitorul, este logic să înlocuiți pagina care nu a fost folosită de cel mai mult timp. Această abordare se numește cel mai putin recent folosit algoritm (LRU). Funcționarea algoritmului este ilustrată în fig. orez. 10.2. Comparând Fig. 10.1 b și 10.2, se poate observa că utilizarea algoritmului LRU reduce numărul de încălcări ale paginii.

LRU este un algoritm bun, dar greu de implementat. Trebuie avut lista legată dintre toate paginile din memorie, la începutul cărora vor fi stocate cele mai recente pagini utilizate. Mai mult, această listă trebuie actualizată cu fiecare acces la memorie. Este nevoie de mult timp pentru a căuta pagini dintr-o astfel de listă.

În [Tanenbaum, 2002], o variantă a implementării algoritmului LRU cu un pointer special de 64 de biți care este incrementat automat cu unul după execuția fiecărei instrucțiuni, iar tabelul de pagini are un câmp corespunzător în care valoarea pointerului este introdus pentru fiecare link către pagină. Când apare o eroare de pagină, pagina cu cea mai mică valoare a acestui câmp este descărcată.

Atât algoritmul optim, cât și LRU nu suferă de anomalia Bilady. Există o clasă de algoritmi pentru care, având în vedere același rând de accesări, setul de pagini din memorie pentru n cadre este întotdeauna un subset de pagini pentru n + 1 cadre. Acești algoritmi nu prezintă anomalii Bilady și sunt numiți algoritmi de stivă.

Impingând o pagină rar folosită. Algoritmul NFU

Din moment ce majoritatea procesoare moderne nu oferă suport hardware adecvat pentru implementarea algoritmului

Cel mai bun algoritm de înlocuire a paginii este ușor de descris, dar complet imposibil de implementat. În ea, totul se întâmplă după cum urmează. În momentul erorii de ieșire a paginii, există un anumit set de pagini în memorie. Unele dintre aceste pagini vor fi accesate literalmente din următoarele comenzi (aceste comenzi sunt conținute în pagină). Este posibil ca alte pagini să nu fie accesate după 10, 100 sau chiar 1000 de comenzi. Fiecare pagină poate fi etichetată cu un număr de comenzi care trebuie executate înainte ca pagina să fie prima accesată.

Algoritmul optim de înlocuire a paginii afirmă că pagina este marcată cu cea mai mare valoare. Dacă o pagină nu este utilizată pentru 8 milioane de comenzi și o altă pagină nu este utilizată pentru 6 milioane de comenzi, atunci ștergerea primei pagini va duce la o eroare de paginare, ca urmare a căreia aceasta va fi preluată din nou de pe disc în viitorul cel mai îndepărtat. Calculatoarele, ca și oamenii, încearcă să amâne cât mai mult posibil evenimentele neplăcute.

Singura problemă cu un astfel de algoritm este imposibilitatea implementării acestuia. În momentul în care apare o eroare de pagină, sistemul de operare nu are de unde să știe când fiecare dintre pagini va fi solicitată. ( Situație similară a fost observat mai devreme când am luat în considerare algoritmul de programare care selectează mai întâi cel mai scurt job - cum poate sistemul să determine care dintre joburi este cel mai scurt?) Cu toate acestea, atunci când rulează programul pe simulator și urmărește toate accesările la pagină, devine posibil să se implementeze algoritmul optim de înlocuire a paginii la a doua rulare, folosind informațiile de acces la pagină colectate în timpul primei rulări.

Astfel, devine posibilă compararea performanței algoritmilor fezabil cu cel mai bun posibil. Dacă sistemul de operare atinge o performanță care este, să zicem, cu 1% mai slabă decât cea a algoritmului optim, atunci efortul depus în găsirea unui algoritm mai bun nu va produce o îmbunătățire mai mare de 1%.

Pentru a evita orice potențială confuzie, ar trebui să fie clar că această înregistrare a accesului la pagină se aplică doar unui program care a fost evaluat și numai pentru un set bine definit de intrări. Astfel, algoritmul de înlocuire a paginii rezultat se aplică numai acestui lucru program specificși intrări specifice. Deși această metodă este folosită pentru a evalua algoritmii de înlocuire a paginii, în sisteme reale el este inutil. În continuare, vom lua în considerare acei algoritmi care sunt cu adevărat utili pentru sistemele reale.

Să presupunem că toate distorsiunile din canal sunt strict determinate și numai zgomotul aditiv gaussian n(t), care se presupune inițial a fi alb, cu o densitate spectrală N 0 , este aleatoriu. Aceasta înseamnă că la transmiterea unui semnal u i (t) (simbol b i (i = 0,1,...,m-1), semnalul de intrare poate fi descris prin modelul (3.38):

z(t) = s i (t) + n(t), (0≤t≤T), (6.17)

unde toate s i (t) = ku i (t-τ) (i = 0, 1,..., m-1) sunt cunoscute. Nu sunt cunoscute decât implementarea interferenței și indicele i al semnalului efectiv transmis, ceea ce ar trebui determinat de circuitul de decizie.

Vom presupune, de asemenea, că toate s i (t) sunt semnale finite, a căror durată este T. Acest lucru se întâmplă dacă semnalele transmise u i (t) sunt finite și au aceeași durată (sistem sincron), și nu există nici propagare pe mai multe căi, nici distorsiune liniară în canal , provocând o creștere a duratei semnalului (sau sunt corectate).

În cele ce urmează, vom presupune peste tot că în sistem este asigurată o sincronizare fiabilă a ceasului, adică limitele intervalului de ceas la care sosește semnalul s(t) sunt cunoscute exact. Problemele de sincronizare sunt foarte importante în implementarea demodulatoarelor optime și a sistemelor de comunicații sincrone în general, dar ele depășesc scopul acestui curs. Momentul începerii trimiterii s(t) va fi luat ca zero.

În aceste condiții, definim algoritmul pentru funcționarea unui demodulator optim (adică, pe baza regulii de probabilitate maximă) care analizează semnalul la intervalul de ceas 0-T. Pentru a face acest lucru, este necesar să găsiți rapoartele de probabilitate pentru toți m semnale posibileîn raport cu ipoteza nulă (s(t)=0; z(t) = n(t)).

Problema este îngreunată de faptul că lățimea spectrului de semnal este infinită (deoarece este finită) și, prin urmare, spațiul semnalului este infinit-dimensional L 2 (T). Pentru astfel de semnale (sau vectori infiniti-dimensionali), după cum s-a menționat, nu există o densitate de probabilitate. Cu toate acestea, există densități de probabilitate „-dimensionale pentru orice secțiuni de semnal n (a se vedea § 2.1).

Să înlocuim mai întâi zgomotul alb cu zgomotul cvasi-alb, având aceeași densitate spectrală de putere unilaterală N 0 , dar numai într-o anumită bandă de frecvență F = n/2T, unde n>>1. Să luăm în considerare mai întâi o ipoteză suplimentară, adică vom presupune că Z(t) este zgomot. Să luăm n secțiuni echidistante pe intervalul de ceas prin Δt = 1/2F = T/n. Citirile Z 1 ,...., Z n din aceste secțiuni pentru zgomotul gaussian cvasi-alb sunt independente în conformitate cu (2.49). Prin urmare, densitatea de probabilitate n-dimensională pentru probele prelevate

unde σ 2 = N 0 F este dispersia (puterea) zgomotului cvasi-alb.

Sub ipoteza că simbolul b i a fost transmis, conform (6.17) n(t) = z(t) - s i (t). Prin urmare, densitatea de probabilitate n-dimensională condiționată a secțiunilor Z(t) este determinată de aceeași formulă ca (6.18), dacă z(t k) este înlocuit cu diferența z(t k)-s i (t k), care în această ipoteză reprezinta zgomotul:

Raportul de probabilitate pentru semnalul s i (față de ipoteza suplimentară), calculat pentru n secțiuni:

Să înlocuim dispersia σ 2 cu expresia ei: σ 2 = N 0 F = N 0 /(2Δt). Apoi

Conform regulii de maximă probabilitate, în cazul zgomotului cvasi-alb, circuitul de decizie trebuie să aleagă valoarea lui i care furnizează maximul Λ i [n] . În loc de maximul lui Λ i, se poate găsi maximul logaritmului său:

Al doilea termen din (6.22) nu depinde de t și poate fi ignorat la compararea ipotezelor. Atunci regula de decizie conform căreia simbolul b i a fost transmis, conform (6.10), poate fi exprimată prin sistemul de inegalități

Să revenim acum la problema inițială pentru zgomotul alb. Pentru a face acest lucru, vom extinde banda F, apoi numărul de secțiuni n tinde spre infinit, iar Δt tinde spre zero. Sumele din (6.22) se transformă în integrale, iar otrava soluției este definită după cum urmează:

Expresia (6.24) determină acele operații (algoritm de operare) pe care receptorul optim trebuie să le efectueze asupra oscilației de intrare z(t).

Pe fig. 6,2 pentru m = 2 arată schema structurala dispozitivul de recepție funcționează în conformitate cu algoritmul (6.24).

Aici "-" - dispozitive de scădere; Γ 0 , Γ 1 - generatoare de semnal de referinţă s 0 (t), s 1 (t); „KB” - cuadratorii; ∫ - integratori; RU este un dispozitiv de decizie care determină uneori care sunt multipli ai lui T (când cheile sunt închise), numărul ramificației cu semnalul minim.

Pentru m>2 în schema din Fig. 6.2 și alte scheme de mai jos, numărul de ramuri de procesare a semnalului care cad pe aparatul de comutare crește în mod corespunzător.

În spațiul Hilbert

definește norma diferenței dintre vectorii z și s sau distanța dintre ei * . Prin urmare, algoritmul (6.24) poate fi scris ca

||z - s i ||

și dați-i o interpretare geometrică simplă: demodulatorul optim ar trebui să înregistreze pe cel al semnalelor s i (t) (corespunzător simbolului b i), care este „mai aproape” de forma de undă primită z(t). De exemplu, în fig. 6.3 arată partiția optimă spațiu bidimensional semnalele primite z(t) în timpul transmiterii semnalelor s 1 (t) şi s 0 (t). Zonele de decizie în favoarea simbolurilor 0 sau 1 sunt situate pe ambele părți ale dreptei 0-0, perpendicular pe segmentul care leagă punctele semnalelor și îl împarte la jumătate.

Prezența în diagrama din Fig. 6.2 quads concepute pentru a oferi o transformare pătratică a valorilor instantanee semnale de intrareîn toate interval dinamic, îngreunează adesea implementarea. Prin urmare, pe baza (6.24), obținem un algoritm de recepție echivalent care nu necesită dispozitive de pătrare.

Deschiderea parantezelor sub semnul integral și anularea termenului în ambele părți ale inegalităților (6.24)

ajungem la algoritmul de recepție:

unde E j este energia semnalului așteptat s j (t):

Pentru un sistem binar, algoritmul (6.25) se reduce la verificarea unei inegalități

Dispozitiv care calculează direct produsul punctual

numit filtru activ, sau un corelator, deci receptorul care implementează algoritmul (6.25) se numește receptor de corelație.

* (Pentru un spațiu euclidian n-dimensional, această normă este egală cu)

Pe fig. 6.4 prezintă o diagramă bloc a unui receptor care funcționează în conformitate cu (6.27). Aici blocurile × sunt multiplicatori; Γ 0 , Γ 1 - generatoare de semnal de referinţă s 0 (t) s 1 (t); ∫ - integratori; "-" - dispozitive de scădere; RU este un dispozitiv de decizie care determină uneori care sunt multipli ai lui T (când cheia este închisă), i = 0, 1 este numărul ramificației cu semnalul maxim.

Dacă semnalele u i (t) sunt alese în așa fel încât toate realizările lor (și, în consecință, toate realizările s i (t) să aibă aceleași energii (E i = const), algoritmul de recepție (6.25) (și, în consecință, implementarea lui) se simplifică (nu este nevoie de scăderi) și ia forma

Din (6.29) se poate observa că regula de decizie nu se modifică dacă semnalul z(t) la intrarea demodulatorului este înmulțit cu orice număr. Prin urmare, un sistem în care toate realizările semnalului au energie egală diferă prin faptul că algoritmul optim de recepție din acesta nu necesită cunoașterea „scării” semnalului de intrare sau, cu alte cuvinte, cunoașterea câștigului canalului k. Acest caracteristică importantă a condus la utilizarea pe scară largă a sistemelor de semnale cu energie egală, care sunt de obicei numite sisteme cu o pauză activă. Acest lucru este deosebit de important pentru canalele de estompare unde amplificarea fluctuează (vezi §6.7).

Rețineți că pentru un sistem binar inegalitatea (6.27) poate fi reprezentată într-o formă mai simplă:

unde s Δ (0 \u003d s 1 (t) - s 0 (t) este semnalul de diferență; λ \u003d 0,5 (E 1 -E 0) este nivelul pragului. Pentru un sistem cu o pauză activă, X \u003d 0, ceea ce simplifică foarte mult schema optimă de implementare.

Când inegalitatea (6.30) este satisfăcută, se înregistrează simbolul 1, în in caz contrar- 0. A implementa (6.30) în schema din fig. 6.4 necesită o singură ramură.

Pe fig. 6.5a prezintă un circuit care implementează algoritmul (6.30) pentru un sistem de transmisie binar cu impulsuri unipolare (cu o pauză pasivă): s 1 (t) = a, s 0 (t) = 0. Cu aceste semnale, s Δ ( t) = s 1 (t) = a, E 1 = a 2 T, E 0 = 0, λ = a 2 T/2 și (6.30) ia următoarea formă:

Sistemul considerat de semnale binare este utilizat în cele mai simple dispozitive de comunicație cu fir. În canalele de radio, precum și în cele moderne canale prin cablu utilizați semnale de înaltă frecvență. Cel mai simplu sisteme binare cu semnale armonice sunt sisteme cu codare în amplitudine (AM), fază (PM) și frecvență (FM).

În AM binar s 1 (t) = acos(ω 0 t + φ), s 0 (t) = 0. Se presupune că toate constantele (a, ω 0 , φ) din această secțiune sunt cunoscute. Deoarece aici s Δ (t) \u003d s 1 (t), E 1 \u003d a 2 T / 2 și E 0 \u003d 0, regula (6.30) se va scrie după cum urmează:

Este implementat de diagrama din Fig. 6.5.6, care diferă de fig. 6.5,a prin blocul de multiplicare a semnalului de intrare cu semnalul de referință cos(ω 0 t + φ). Nivelul pragului λ în acest caz este egal cu aT/(4RC).

Cu un sistem FM binar s 0 (t) = a cos (tω 0 + φ), s 0 (t) = a cos (tω 0 + φ + π) = -s 1 (t). Acesta este un sistem cu o pauză activă și, prin urmare, în (6.30) λ = 0. Este ușor de observat că regula de decizie se reduce la următoarele:

și este implementat de același circuit din Fig. 6.5.6 pentru λ÷ = 0. În acest caz, RU joacă rolul unui discriminator de polaritate.

Orez. 6.6. Demodulator optim de văruire pentru zgomotul „colorat” gaussian

Să luăm în considerare pe scurt cazul în care zgomotul gaussian din canal nu este alb sau cvasi-alb, ci „colorat”, adică are o densitate de putere neuniformă G(f) în banda spectrului de semnal. Să trecem suma semnalului și a zgomotului care vin la intrarea demodulatorului printr-un filtru cu funcția de transfer k(i2πf), astfel încât produsul G(f) |k(i2πf)| 2 a fost valoare constantă N0. Dintre toate filtrele posibile cu k(i2πf) care satisfac această condiție și diferă numai răspuns de fază, puteți alege faza minimă, care este reversibilă. Evident, zgomotul la ieșirea filtrului va fi cvasi-alb: G out (f)=N 0 . Prin urmare, un astfel de filtru se numește filtru de albire.

Semnalul s i (t) după trecerea prin filtrul de albire se va transforma într-un alt semnal, pe care îl notăm s "i (t). Forma lui poate fi determinată cunoscând s i (t) și k (i2πf). Dacă acum aplicăm oscilații de la ieșirea filtrului de albire la demodulator, care este optim pentru primirea semnalelor s "i (t) (i \u003d 0, 1, ..., m-1), apoi obținem circuitul din Fig. 6.6, care este evident optim pentru semnalele s i (t) cu zgomot colorat.

Trebuie remarcat faptul că în diagrama din fig. 6.2, 6.4 și 6.5, semnalul de referință trebuie să aibă aceleași faze inițiale ca și semnalele de intrare așteptate sau, cu alte cuvinte, trebuie să fie coerent cu semnalele de intrare. Această cerință complică de obicei implementarea demodulatorului și necesită introducerea în acesta, pe lângă blocurile indicate în figuri, dispozitive suplimentare, conceput pentru a regla fazele semnalelor de referință.

Toate metodele de recepție pentru care este necesară cunoașterea a priori exactă a fazelor inițiale semnale de intrare sunt numite coerente. În cazurile în care informații despre fazele inițiale semnalele așteptate sunt extrase din semnalul recepționat în sine (de exemplu, dacă faza fluctuează, dar atât de lent încât poate fi prezis din elementele de semnal anterioare), recepția se numește cvasi-coerentă. Dacă nu există informații despre fazele inițiale ale semnalelor de intrare sau din anumite motive nu sunt utilizate, atunci recepția se numește incoerentă (vezi § 6.6).

În interviuri, oamenii întreabă adesea care tip este cel mai rapid. Intrebare capcana. Vă explicăm de ce și căutăm cea mai bună opțiune.

Ca răspuns, ar trebui să întrebați: „Și pentru ce caz este ales sortarea optimă pentru timp?” Și numai atunci când condițiile sunt anunțate, puteți sorta în siguranță opțiunile disponibile.

Exista:

• algoritmi de sortare O(n2) cum ar fi sortarea prin inserare, sortarea cu bule și sortarea selecției, care sunt utilizate în cazuri speciale;
• sortare rapida ( scop general): in medie O(n log n) schimburi, dar cel mai rău moment – O(n2) dacă matricea este deja sortată sau elementele sunt egale;
• algoritmi O(nButurugan), cum ar fi sortare de îmbinare și sortare heap (sortare heap), care sunt de asemenea algoritmi buni sortare de uz general;
• Pe) sau algoritmi de sortare liniară (select, select-swap, select-count) pentru liste de numere întregi, care pot fi adecvate în funcție de natura numerelor întregi din listele dvs.

Dacă tot ce știi este atitudinea ordine generalăîntre elemente, atunci algoritmii optimi vor avea complexitate O(n log n). Pentru algoritmi liniari nevoie Informații suplimentare despre structura elementelor.

Optimitatea algoritmului depinde în mare măsură de tipul de liste/matrice pe care urmează să le sortați și chiar de modelul computerului. Cum mai multe informatii la dispoziția dumneavoastră, cu atât selecția va fi mai precisă. În baza unor ipoteze foarte slabe despre factori, complexitatea optimă în cel mai rău caz poate fi Pe!).

Acest răspuns este doar despre complexitate. Timpul real de execuție al algoritmilor depinde sumă uriașă factori.

Testare

Deci, ce fel este cel mai rapid?

Vizualizarea

O bună vizualizare a sortării este demonstrată în acest videoclip:

Pare să răspundă la întrebarea care tip este cel mai rapid, dar rețineți că viteza este afectată de mulți factori, iar aceasta este doar una dintre opțiunile demonstrate.