Statistische signaalverwerking [1e dr. ed.] 9789065621450, 9065621458 [PDF]

Zitiervorschau

Uitlae~'ers

Maatschappij

Statistische Signaalverwerking

2532 636 1

c"

/lil

" I " 2082618 11

Statistische Signaalverwerking dr.ir. R. L. Lagendijk prof.dr.ir. J. Biemond Technische Universiteit Delft Faculteit der Elektrotechniek Vakgroep Informatietheorie

Bibliotheek TU Delft Faculteit Luchtvaart- en Ruimtevaarttechniek Klu -yverwe bu 1 2629 HS Delft

Delftse Uitgevers Maatschappij

CIP-gegevens Koninklijke Bibliotheek, Den Haag Lagendijk, R.L. Statistische signaalverwerking / RL Lagendijk, J. Biemond. Delft: Delftse U.M. - lil. Met lito opg., reg. ISBN 90-6562-145-8 Trefw.: statistische signaal verwerking.

©VSSD Eerste druk 1994 Delftse Uitgevers Maatschappij b.v. P.O. Box 2851 , 2601 CW Delft, The Netherlands Tel. 015-123725, telefax 015-143724 Alle rechten voorbehouden. Niets uit deze uitgave mag worden verveelvoudigd, opgeslagen in een geautomatiseerd gegevensbestand, of openbaar gemaakt, in enige vorm of op enige wijze, hetzij elektronisch, mechanisch, door fotokopieën, opnamen, of op enige andere manier, zonder voorafgaande schriftelijke toestemming van de uitgever.

All rights reserved. No part ofthis publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. ISBN 90 6562 145 8

aarwaard

In de laatste decennia heeft de signaalverwerking sterke veranderingen doorgemaakt. Door de opkomst van geïntegreerde digitale signaalverwerkingsprocessoren en door de ontwikkeling van gespecialiseerde geïntegreerde circuits voor complexe signaalverwerkingsalgoritmen heeft de bewerking van elektrische signalen in real-time zich ontwikkeld van abstract idee tot dagelijkse praktijk. Algoritmen die lange tijd slechts conceptuele oplossingen van theoretische problemen waren, worden momenteel routinematig gebruikt in een groot aantal toepassingen binnen de Elektrotechniek (telecommunicatie: detectie en schatting van signalen, netwerktheorie: realisatie van algoritmen, regeltechniek: regelen en meten van systemen, en informatietheorie: transport en extractie van informatie), maar ook daar buiten. De statistische signaalverwerking concentreert zich op dat deel van de signaalverwerking waarin het gebruik van stochastische signaalmodellen en statistische kenmerken essentieel is. Bij alle te bespreken onderwerpen draait het telkens om het scheiden van informatie en verstoring, waarbij de verstoring meestal gemodelleerd wordt als een (additieve) ruiscomponent. Dit boek is gebaseerd op het college Statistische Signaalverwerking zoals dat sinds 1983 gegeven wordt aan de faculteit der Elektrotechniek van de Technische Universiteit in Delft. Door de jaren heen is het studiemateriaal geëvolueerd van collegeaantekeningen, via collegediktaten tot het voor u liggende boek.

Aanpak en inhoud Dit boek behandelt de elementaire onderwerpen uit de statistische signaalverwerking, zodat na bestudering de (vrij uitgebreide) literatuur op dit gebied goed toegankelijk is. Er wordt ingegaan op detectie- en schattingstheorie, lineaire kleinste-kwadraten schatters (Wiener, Kalman schatters en adaptieve filters) en methoden voor het schatten van spectra. In dit boek staan de methodologieën voorop en niet zozeer de toepassingen, alhoewel de behandelde stof wel zoveel mogelijk geïllustreerd wordt aan de hand van voorbeelden uit de praktijk van de signaalverwerking. De methoden die besproken worden, vormen de basis voor veel gerealiseerde systemen. Voordat een gekozen methode in de praktijk gebruikt kan worden, zal eerst een geschikte implementatie gevonden moeten worden. Dit niet onbelangrijke architectuur- en hardware-aspect wordt slechts op enkele plaatsen in het boek genoemd. De nadruk van dit boek ligt dus meer op het

6

Statistische Signaalverwerking

ontwikkelen van methoden en algoritmen dan op de realisatie hiervan. In hoofdstuk 1 wordt een nadere toelichting gegeven op de doelstellingen van de statistische signaalverwerking aan de hand van enkele voorbeelden. Vervolgens wordt een resumé gegeven van de belangrijkste begrippen uit de kansrekening en de theorie van de stochastische processen. Op basis hiervan wordt daarna een aantal stochastische signaalmodellen geïntroduceerd (AR, M 0

(1.5)

Een belangrijke relatie die vaak bij manipuleren van conditionele kansen gebruikt wordt, is de regel van Ba~s : ' ) _P(-,-A-,-,i)_ . / B. _ P( Bj / Ai) P( Ai) _ ~P(-,-B-,,-j_/-,-AI-,P( Al J)--;: P(Bj) P(Ai) PCB) / Ai)

I

(1.6)

In het algemeen is de conditionele kans P(A/ B)) groter of kleiner dan de marginale kans P(Ai). Echter in het geval dat P(A/ B)) = P(A j ) heeft kennis over de gebeurtenis B) blijkbaar geen invloed op de conditionele kans van Ai. We noemen de gebeurtenissen dan stochastisch onafhankelijk. Meestal wordt onafhankelijkheid als volgt geverifieerd: P(A i , B)) = P(Ai ) P(B))

1.2.3.

stochastisch onafhankelijk

( 1.7)

Stochastische variabelen Een stochastische variabele is formeel gesproken een numerieke functie die aan elke uitkomst van een experiment een reëel-waardig getal koppelt. Gebeurtenissen zijn nu eenvoudig te definiëren als een deelverzameling van de reële as. Wanneer de stochastische variabele slechts waarden Xi aanneemt die individueel aanwijsbaar zijn, spreken we van een discrete stochastische variabele. Bij continue stochastische variabelen zijn de uitkomsten van het experiment niet individueel aanwijsbaar.

20

Statistische Signaalverwerking

Het gedrag van een stochastische variabele X wordt volledig beschreven door de cumulatieve distributiefunctie (cdf) F(x), gedefinieerd als: F(x) = P(X ~ x)

-oo q. We moeten nu toestandsgrootheden xiCk) zo kiezen dat het gedrag van y(k) daarmee volledig voorspeld kan worden in de toekomst, gegeven alle voorgaande ingangs- en uitgangssignalen. Omdat de differentievergelijking (1.78) van de p-de orde is, is een geheugenwerking van p elementen nodig, dat wil zeggen, de toestandsvector van het systeem bevat p elementen. De meest gebruikelijke wijze om de toestandsvector te definiëren, is om eerst het MA deel buiten beschouwing te laten. We verkrijgen dan de volgende hulpuitdrukking: rek)

= a J rek -1) + a2r(k -

2) + ... + apr(k - p) + wek)

(1.79)

1. Introductie in de statistische signaalverwerking

43

Nu definiëren we de toestandsgrootheden xi(k) als volgt:

X2(k) = rek -1) = xl (k -1) x 3 (k)

= rek -

2) = x 2(k -1)

xp(k)

= rek - p + 1) = xp_l (k -1)

(1.80)

Gebruikmakend van (1.79) wordt de volgende differentievergelijking verkregen: Xl

(k)

x 2(k)

xp(k)

al a2

ap

0

0

= 0

0

0

Xl

(k -1)

x 2(k -1)

0

+

wek)

0

xp(k -1)

x(k) = Ax(k -1) + Bw(k)

(1.81)

Vervolgens wordt het MA-deel van het ARMA model opgenomen door de coëfficiënten van de uitgangsmatrix C op de juiste wijze te kiezen: Xl (k) y(k)=Cx(k)=[c l C2 ... Cp]

X2(: k)

(1.82)

Uitschrijven van y(k -.e) voor .e = 0, 1, ... , p, vermenigvuldigen met -ae ... , p) en optellen van de resultaten levert: y(k)

(.e =

I, 2,

=cl Xl (k) + C2 X2(k)+ ... +cpx p(k)

-al y(k -1) = -cl al Xl (k - 1) - c2a l X2 (k -1)-.. . -C pal x p(k-1) -apy(k - p) = -Cl apx I (k - p) - c2apx2(k - p)-... -cpapxp(k - p) + (l.83)

y(k) - al y(k -1)-.. .-apy(k - p) = Cl

[Xl (k) - al Xl (k -1)-. .. apxI (k - p)] + C2[X2(k) - al x2(k -1)-.. . -a px 2(k - p)]+ ... .. .+C p[ xp(k) - al xp(k -1)-.. .-apxp(k -

p)]

44

Statistische Signaalverwerking

Bekijken we de uitdrukkingen tussen haakjes aan de rechterzijde van deze vergelijking, dan blijkt de volgende herschrijving mogelijk aan de hand van (1.80) en (1.81): Xl

(k) - al Xl (k -1)-.. .-apx l (k - p) = xI (k) - al xI (k -1)-...apxp(k -1) = w(k)

x 2 (k) - al x 2 (k -1)-.. .-apx 2 (k - p)

= xI (k -1) -

al xI (k - 2)-.. . apxp(k - 2) = w(k-1)

xp(k) - al xp(k -1)-.. .-apxp(k - p)

=XI (k - P + 1) - al xI (k -

P )-.. . apxp(k - p)

= w(k - p + 1)

(1.84)

Substitutie van dit resultaat in (1.83) levert y(k) -aly(k -l)-... -apy(k - p) =

cl

w(k)+c 2 w(k -l)+ ... +cpw(k - p+ 1)

(1.85) waaruit blijkt dat de coëfficiënten van de matrix C niets anders zijn dan de coëffi ciënten van het MA deel van (1.78), mits q ~ p - 1, wat al eerder als voorwaarde genoemd was. Dit levert uiteindelijk:

(1.86)

Klaarblijkelijk is de matrix D in (1.77) een nul-matrix. Figuur 1.11 laat een mogelijke realisatie zien van het toestandsmodel voor het ARMA signaalmodel aan

~~'ffi~~ Xl (k)

Z-l

X2(k)

Z-l

x3(k)

Z-l

b

Figuur 1.11.

Xq+1 (k)

2

Z-l

Xq+2(k)

z-l

Xp(k)

___b~__~~

Stroomdiagram behorende bij de toestandsvergelijkingen (1.81) en (1.86).

1. Introductie in de statistische signaalverwerking

45

de hand van een stroomdiagram. Als laatste wordt opgemerkt dat de matrices A, B en C tijd-invariant zijn voor een ARMA model van een zwak-stationair signaal. Zoals uit (1.81) en (1.86) blijkt, kan een ARMA model waarvan de coëfficiënten am en b m van de tijd afhangen, beschreven worden door tijd-variante toestandsvergelijkingen.

1.4.

Samenvatting en belangrijke termen

Dit hoofdstuk heeft een overzicht gegeven van een aantal concepten en definities die voor de statistische signaalverwerking van belang zijn. Speciaal van belang zijn de karakterisering van zwak-stationaire en (zwak-)ergodische signalen door hun verwachting, correlatie- en covariantiefuncties. Ook het vermogensdichtheidsspectrum neemt een belangrijke plaats in. Stochastische signalen worden vaak gemodelleerd door AR, MA, of ARMA processen. Van essentieel belang is dat deze modellen gebaseerd zijn op lineaire causale systemen waarvan het ingangssignaal een tijd-discreet wit ruisproces is. Van elk van de modellen is de overdrachtsfunctie, het vermogensdichtheidsspectrum, en de autocorrelatiefunctie besproken. Tevens is getoond hoe de uitwendige beschrijving van een ARMA model aan de hand van een differentievergelijking omgevormd kan worden tot een inwendige beschrijving door toestandsvergelijkingen. Lijst van belangrijke termen AR model ARMAmodel autocorrelatiefunctie autocovariantiefunctie Bayes, regel van conditionele kansdichtheid cOITelatie covariantie ensemble ergodiciteit gezamenlijke kansdichtheid kruiscorrelatiefunctie kruiscovariantiefunctie kruisvermogensdichtheidsspectrum MA model

marginale kansdichtheid ongecorreleerd orthogonaal realisatie stochastisch onafhankelijk stochastisch signaal stochastische variabele variantie vectoriële stochastische variabele vermogensdichtheidsspectrum verwachting witte ruis zwak-ergodisch zwak -station ai r

Detectietheorie

2.1.

Inleiding

In een geautomatiseerde technische omgeving komt het vaak voor dat een keuze gemaakt moet worden uit verschillende mogelijkheden, met andere woorden: dat er een beslissing genomen dient te worden. Zo wordt bijvoorbeeld in een radardetectieprobleem aan de hand van de echo beslist of er al dan niet een object aanwezig is. Te denken valt aan een vliegtuig dat bij slecht zicht een luchthaven nadert. De verkeersleiding dient dit vliegtuig tijdig op het radarscherm te detecteren en vervolgens de piloot radiografisch te informeren over het al dan niet aanwezig zijn van andere vliegtuigen in zijn baan. Andere voorbeelden van hedendaagse detectors zijn de regendetector, de branddetector en het inbraakalarm. Kenmerkend hierbij is steeds dat op basis van bepaalde beschikbare informatie (meetwaarde, observatie), die soms verre van nauwkeurig is, een beslissing moet worden genomen. Zo is een bepaalde hoeveelheid rookontwikkeling in een ruimte (bijvoorbeeld van een sigarettenpeuk) beslissend voor het afgaan van het brandalarm en het uitrukken van de brandweer. In een digitaal communicatiesysteem wordt de boodschap gecodeerd in een binaire symboolreeks. Voor de verzending van de binaire symbolen '0' en 'I' worden geschikte signaalvormen gekozen. Onder invloed van het transmissiemedium (het kanaal) kunnen deze signalen vervormd raken (symbol interference). Bovendien kan ook de ontvanger nog ruis toevoegen aan het reeds vervormde signaal. Het gevolg hiervan is dat het aan de ontvangstzijde niet altijd duidelijk is welk signaal werd verzonden. Toch moet de ontvanger op basis van de vervormde en verruiste waarnemingen beslissen of er een '0' of een' I' verzonden werd. In de patroonherkenning behoort een patroon tot één van een aantal mogelijke patroonklassen. Zo behoren alle mogelijke schrijfwijzen van de letter a tot de klasse 'a'. De patroonclassificator moet beslissen tot welke klasse een gegeven patroon behoort. In het geval van de handgeschreven letters moet de classificator beslissen welke letter uit het alfabet met de grootste waarschijnlijkheid geschreven werd. De patroonclassificator baseert zijn keuze op waarnemingen en (statistische) kennis over de verschillende voorkomende patroonklassen. In elk van de genoemde voorbeelden is het nodig dat er op grond van vervormde en verruiste waarnemingen (observaties) een beslissing wordt genomen. In dit hoofdstuk worden methoden behandeld die dit detecti~- of beslissingsprobleem oplossen.

2. Detectietheorie

2.2.

47

Het toetsen van hypothesen

In een statistisch toetsingsprobleem moet beslist worden welke hypothese (veronderstelling) de juiste is, gegeven een aantal mogelijke hypothesen. Een hypothese kan hierbij opgevat worden als een bepaalde beslissingsmogelijkheid. Stel dat we in het meest eenvoudige geval te maken hebben met twee mogelijke beslissingen. Bijvoorbeeld in het genoemde radardetectieprobleem hebben we te maken met 'Object niet aanwezig' en 'Object aanwezig'. We duiden deze twee keuzemogelijkheden aan met Ho en H I. Men noemt Ho de nulhypothese en Hl de alternatieve hypothese. We spreken hier van een binair detectieprobleem. Meer in het algemeen hebben we te maken met een meervoudig detectieprobleem waarbij gekozen wordt uit de hypothesen Ho, H" ... ,HM. De basiscomponenten van een eenvoudig binair detectiesysteem zijn weergegeven in figuur 2.1 . Een bron genereert twee mogelijke hypothesen als uitgangsgrootheden. De hypothesen worden uiteraard niet direct waargenomen, anders was er geen beslissingsprobleem. Een kansmechanisme beïnvloedt de waarnemingen van de hypothese. Hierbij kunnen we denken aan allerlei stochastische verstoringen zoals transmissie- en observatieruis.

stochastische verstoring

waarnemingsruimte Z

Figuur 2. 1.

Binair detectiesysteem. ;

We verkrijgen nu één (of in het a1gemeen meer dan één) waarneming (observatie, meting) aan een stochastische variabele, waarbij het gedrag van deze stochastische variabele afhangt van Ho en Hl , en afhangt van het kansmechanisme (verstoring). Het toetsingsprobleem bestaat er uit te beslissen welke hypothese de juiste is op basis van deze ene observatie. Het waardebereik van z vormt de waarnemingsruimte Z. Het beslissingsprobleem kenmerkt zich door het opdelen (partitioneren) van de waarnemingsruimte in twee gebieden Zo en ZI, zodanig dat wanneer z in Zo ligt we rslissen tot Ho en wanneer zi n ZI ligt we beslissen tot Hl . De gebieden Zo en ZI staan bekend als beslissingsgebieden. Het probleem is nu de gebieden Zo en Z I zodanig te kiezen dat we (bijvoorbeeld) het kleinste aantal fouten krijgen bij herhaalde uitvoering van het experiment. Om te kunnen aangeven wat de beste partitionering van de waarnemingsruimte is,

48

Statistische Signaalverwerking

moeten we allereerst een geschikt criterium selecteren. Deze keuze van een foutcriterium komt uitgebreid aan de orde in paragraaf 2.3. Ter illustratie van de beslissingsprocedure kiezen we hier het volgende criterium: Wanneer P(H;lz), i =0, I, de kans is dat Hi de juiste hypothese is, gegeven een waarneming (meting) z, dan wordt die hypothese gekozen die overeenkomt met de grootste van de twee kansen. Het beslissingscriterium om Ho aan te nemen is dan (2.1) waarbij P(H/z) de a posteriori kans op Hi, gegeven z, wordt genoemd. Wordt aan deze ongelijkheid niet voldaan, dan wordt de alternatieve hypothese Hl aangenomen. Dit criterium kunnen we ook schrijven als

P(HI/z) ~I 1 P(Ho/z) {jo

(2.2)

wat bekend staat als het Maximum A Posteriori (MAP) criterium. Met behulp van de Bayesregel

P(H·! ) = p(z/Hi)P(Hi) I Z p(z)

i = 0, 1

(2.3)

waarin P(Hi) de kans is op hypothese Hi, kunnen we het linkerlid van (2.2) ook schrijven als

P(HI/z) _p(z/HI) P(H I ) P(Ho/z) - p(zlHo) P(Ho) De toets wordt hiermee in de volgende meer geschikte vorm gebracht

A( )_p(z/HI) ~I P(Ho) z - p(z/Ho) {jo P(Hd

(2.4)

De verhouding A(z) =p(zlHI)/p(zlHo) wordt de aannemelijkheidsverhouding (likelihood ratio) genoemd, omdat p(zlHj} de likelihood functie van Hi (of de waarschijnlijkheid van z gegeven H i ) is. De toets bestaat dus uit het vergelijken van de verhouding A(z) met een constante, de zogenaamde drempel van de toets en wordt een likelihood ratio test (LRT) genoemd. In de volgende paragraaf zullen we zien dat toetsen gebaseerd op andere criteria ook vallen onder deze algemene klasse van likelihood ratio toetsen, waarbij echter de drempels in het algemeen verschillen voor de verschillende toetsen. Voorbeeld 2.1. Gebruik MAP-criterium We gaan uit van een eenvoudig binair communicatiesysteem waarbij de zender gedurende elk interval van T seconden of een puls y(t) uitzendt met eenheidsamplitude (een' 1') of in het geheel geen signaal (een '0'). Een dergelijk

2. Detectietheorie

49

systeem staat bekend als 'on-off keying' (OOK). Het communicatiekanaal voegt ruis vet) toe, zodat het ontvangen signaal z(t)= y(t) + vet) of zet) = vet) is gedurende elk T-seconden interval. Het probleem is nu op basis van één waarneming z te beslissen of er een 'I' of '0' verzonden is. De gebeurtenis dat geen signaal wordt uitgezonden ('0') noemen we de nulhypothese Ho en de gebeurtenis dat er een signaal met een eenheidsamplitude wordt uitgezonden (' 1') de alternatieve hypothese H I. Het ontvangen signaal onder de twee hypothesen kan dan geschreven worden als: Ho: z

=v

We veronderstellen dat veen Gaussische kansdichtheid bezit met gemiddelde waarde nul en variantie ~. De kansdichtheid van z wordt bepaald door de hypothese H i , en levert p(zIHo)

= .1rr>:

p(zIHI)

=

a v'l2n

[Z2...2 ]

exp -

20;;

en

I

[ (z - 1)2]

.rr>: exp -~

a v'l2n

20;;

De aannemelijkheidsverhouding wordt dan gegeven door

A( ) _ p(zIHt> _ .11

Z - p(zlHo) -

exp

(2Z -

2ifv

I)

wat leidt tot de volgende MAP beslissingsregel

2Z -

I) It.1

exp ( ---:2 20;;

P(Ho)

(2.5)

< P(H)

Ho

1

Vaak is het gemakkelijker om met de natuurlijke logaritme van de aannemelijkheidsverhouding te werken. Omdat de logaritme een monotoon stijgende functie is zal de ongelijkheid in de beslissingsregel nog steeds gelden en kunnen we de regel schrijven als L(z)

2z - I 1f.1 =In A(z) =---:2 < 20;;

Ho

P(Ho)

In P(H ) 1

of

De beslissing komt dus tot stand door eerst het ontvangen signaal te bemonsteren en vervolgens deze bemonstering te vergelijken met een drempel. Wan-

50

Statistische Signaalverwerking

neer de bemonstering groter dan de drempel is, wordt beslist dat er een '1' is verzonden, terwijl in het andere geval beslist wordt dat er een '0' is verzonden. Dit voorbeeld illustreert nogmaals de basiscomponenten van het binaire detectieprobleem: bron (y(t», kansmechanisme (ruis v(t» en waarnemingsruimte (Z). Van belang zijn in dit geval de kansdichtheden p(zlHo) en P(Z/HI), terwijl de waarnemingsruimte wordt gerepresenteerd door de reële as van -00 tot +00. De beslissingsregel verdeelt de reële as in twee stukken Zo en Z I, en kent elk punt in de beide delen toe aan één van de twee mogelijke hypothesen. Eén en ander is geïllustreerd in figuur 2.2. Verder is aan de beslissingsregel af te lezen dat voor P(Ho) :t:. P(H)) de variantie van de ruis een belangrijke rol speelt. Bijvoorbeeld als P(Ho) > P(H I ) dan zal voor toenemende ei; de detectiedrempel steeds groter worden. Omdat bij toenemende hoeveelheid ruis de waarnemingen steeds meer onbetrouwbaar worden, zal de detector meer en meer af moeten gaan op de a priori informatie over de hypothesen, en zal er dus steeds vaker voor Ho gekozen moeten worden, wat consistent is met een grotere waarde voor de beslissingsdrempel. 0

bron

~:~

--.....,,==------1""=---'-=""'1-----="""""--

z

o l'

pi.. Hol

"2 + In pl..H1l _14

Z1 Figuur 2.2.

2.3.

Binair beslissingsschema voor voorbeeld 2.1 met P(Ho} > P(Hd, en

Coo

en

(2.12)

2. Detectietheorie

53

Deze aanname betekent dat beide termen binnen de vierkante haken positief zijn. Minimalisatie van C wordt nu bereikt door alle waarden van z die er voor zorgen dat de tweede term groter is dan de eerste, toe te kennen aan Zo, en alle waarden van z die er voor zorgen dat de tweede term kleiner is, weg te laten uit Zo, dat wil zeggen toe te kennen aan ZI. Punten waar beide termen even groot zijn worden willekeurig toegekend aan ZI. De beslissingsgebieden worden dus als volgt gedefinieerd:

De waarneming z wordt aan ZI toegekend en vervolgens wordt tot Hl beslist als (2.13) De waarneming z wordt toegekend aan Zo en vervolgens wordt tot Ho beslist wanneer niet aan (2.13) voldaan wordt. In termen van de aannemelijkheidsverhouding A( ) - p(z/HJ}

(2.14)

z - p(z/Ho)

en de drempel

P(Ho) (CIO - Coo)

7]

=P(HJ} (COl -

CII)

(2.15)

luidt de beslissingsregel dan Hl A(z) ~ 7]

(2.16)

Ho Dit is opnieuw een likelihood ratio toets (LRT). Nemen we de natuurlijke logaritme dan geldt voor de beslissingsregel Hl

In A(z) ~ In 7] Ho

(2.17)

Het is belangrijk om op te merken dat het berekenen van A(z) geheel los staat van de a priori kansen en het toekennen van kosten. De likelihood ratio hangt slechts af van hoe de waarnemingen tot stand komen (bijvoorbeeld wat de eigenschappen van de ruis zijn). In een praktische implementatie kan de drempel variabel gekozen worden om te kunnen anticiperen op wijzigingen in kosten en a priori kansen. Veelal wordt LRT (2.17) zo herschreven dat een eenvoudige functie J(.) van de observatie(s) z vergeleken kan worden met een drempel: Hl f(z) ~ J{7])

Ho De drempel yhangt hierbij af van de eerder berekende Bayes drempel 7].

54

Statistische Signaalverwerking

Voorbeeld 2.2. Toets op basis van Bayes criterium Veronderstel dat onder beide hypothesen het uitgangssignaal van een stochastische bron Gaussisch verdeeld is met gemiddelde waarde nul. Echter onder hypothese H J is de variantie van het signaal gelijk aan en onder Ho gelijk aan De kosten worden gegeven door: Coo = Cl I = 0; Clo = 2 en COl = 3, terwijl P(Ho) =~ . De kansdichtheidsfunctie van de observatie z onder elke van beide hypothesen

01

05.

is i = 0,1

De aannemelijkheidsverhouding wordt dan gegeven door

(Jo exp [Z2 1 -1 )] A(z)=- (-

05 01

2

(Jl

zodat de beslissingsregel wordt

Nemen we aan beide zijden de natuurlijke logaritme dan kunnen we schrijven

Als we stellen dat

Z2 ~l Ho

01 > 05, dan kan de toets geschreven worden als

20501 01- 05

In

e(JI) ~ r (Jo -

o

De kwaliteit van een detector wordt bepaald door de gemiddelde kosten en/of de fouten verbonden aan het beslissingsproces. De grootheden die hierbij van belang zijn, zijn de kansen op fouten van de eerste en de tweede soort. We roepen in herinnering dat een fout van de eerste soort (loos alarm) correspondeert met het beslissen tot Dl wanneer Ho juist is. Uitgaande van (2.8) kunnen we schrijven voor de loos alarrnkans PL :

f

PL = P(DI/Ho) = p(z/Ho) dz

(2.18)

ZI

Een fout van de tweede soort (misser) correspondeert met de beslissing tot Do terwijl H J juist is, dat wil zeggen

2. Detectietheorie

P M =P(Do/HI)

=f p(z/H I ) dz

55

(2.19)

Zo Op gelijke manier kan voor de detectiekans PD geschreven worden:

f

PD = P(DI/H I ) = p(z/H I ) dz = 1 - PM

(2.20)

Z,

De gemiddelde foutkans Pe verbonden aan het beslissingsproces wordt gegeven door (2.21) Tenslotte kunnen we de gemiddelde kosten C in (2.9) schrijven in termen van hen PM als (gebruik makend van P(Ho) = 1 - P(HI»:

C

= CooP(Ho)(1- Pd + CIOP(Ho)PL + CoIP(HdPM + CllP(HI)(1 = Coo(1 - Pd + CIOPL + P(HI)[(C II

-

Coo) + (COl - Cll)PM- (CIO - Coo)PLl

PM)

(2.22)

Bij vaste kosten en vaste waarden van P L en PM worden variaties in de gemiddelde kosten C als functie van P(H I ) gerepresenteerd dooreen rechte lijn. Hiervan zullen we gebruik maken in paragraaf 2.3.4 bij de behandeling van het Minimax criterium.

2.3.2

MAP-criterium

Wanneer de a priori kansen P(Ho) en P(H I ) bekend zijn en wanneer we de kosten in (2.15) kiezen overeenkomstig Cl 0 - Coo = Co I - C II dan is direct in te zien dat het Maximum A Posteriori criterium in (2.4) een speciaal geval van het algemene Bayes criterium in (2.16) is.

2.3.3

Minimale foutkans criterium

Wanneer we Coo = Cl I = 0 en C IO = COl = 1 kiezen, dan geldt voor de gemiddelde kosten in (2.9):

f

f

C = P(Ho) p(z/Ho) dz + P(H I ) p(z/H I ) dz z, Zo

(2.23)

wat juist gelijk is aan de gemiddelde foutkans Pe in (2.21). Genoemde keuze van de kosten leidt tot het minimale foutkans criterium. De beslissingsregel wordt dan A( )

~I

P(Ho)

z Ro P(HI)

(2.24)

De ontvanger die gebaseerd is op dit beslissingscriterium wordt vaak een ideale ontvanger genoemd. Merk op dat alhoewel het criterium verschillend is, de beslissingsregel gelijk is aan die voor het MAP criterium.

56

Statistische Signaalverwerking

Voorbeeld 2.3. Toets op basis van minimale foutkans criterium We veronderstellen dat we onder de hypothese Hl een constant signaal met amplitude m waarnemen dat verstoord is door witte Gaussische ruis v met gemiddelde waarde nul en variantie (J2. Onder de hypothese Ho nemen we slechts ruis v waar. Op basis van een observatie z moeten we beslissen of het signaalniveau gelijk is aan m of aan nul. De waarnemingen en de likelihoodfuncties worden als volgt beschreven:

I r.tv.f Z2] .-:J vv27r 20-

p(z/Ho) =~'tt -

Ho: z= v

Als we verondersteIIen dat beide hypothesen even waarschijnlijk zijn én we het minimale foutkans criterium hanteren, dan geldt voor de toets:

/f.l

In [PCz/H1h

Ro

p(z/HoP

0

Deze toets kan na substitutie van de kansdichtheden p(zIHi ) worden vereenvoudigd tot: Hl m

z >< -2 Ho

In dit geval bevindt de drempelwaarde zich midden tussen de twee niveaus van de ongestoorde signalen, en tevens midden tussen de twee kansdichtheden (zie figuur 2.3) Inzicht in de kwaliteit van deze toets wordt verkregen door de foutkans uit te rekenen. Vanwege de symmetrie geldt hiervoor: I

I

Pe =2PL+2PM=PL=

. Figuur 2.3.

o

-z

y=m/2 m

., Zo

Z1

Beslissingsgebieden voorbeeld 2.3.

2. Detectietheorie 2

=f _100

exp [- _Z_] dz m/2affir 2a2

m/2

=t - f _

57

2

1_ exp [- _Z_] dz 0 affir 2a2

Door invoeren van een nieuwe variabele u =z/afï is dit te schrijven als m

2cr...J2

Pe =

i [1 - -v_~ 0Jexp(-u

2

)

du]

(2.25)

1r

De vorm x

f

erf(x) =_~ exp (_u 2) du -v Tt 0 staat bekend als de error-functie (erf(x» en is slechts afhankelijk van de bovengrens x van de integraal, in dit geval dus x = m/2afï. Deze integraal is niet analytisch uit te rekenen en dient aan de hand van tabellen of numerieke benaderingen opgelost worden. Kortweghalve wordt het de foutkans geschreven als p

e

= 1.2 [l-erf(~)] 2afï

Op te merken valt dat de verhouding m/a een maat is voor de signaal-ruisverhouding. Des te groter deze verhouding is, des te grotere waarde zal de error functie aannemen, en des te kleiner zal de foutkans worden. De foutkans is dus afhankelijk van de signaal-ruisverhouding wat intuïtief juist is. 0

Minimax criterium 2.3.4 We hebben gezien dat het Bayes criterium en de twee hier uit af te leiden criteria voorschrijven dat we naast het toekennen van kosten aan de verschillende beslissingen ook a priori kansen moeten toekennen aan de twee hypothesen. Vaak is er echter niet genoeg bekend omtrent de hypothesen om a priori kansen te bepalen. Om toch een beslissingsregel te kunnen formuleren wordt de Bayes oplossing gebruikt die correspondeert met de waarde van P(H,) waarvoor de minimale gemiddelde kosten C (ook wel de Bayeskosten genoemd) maximaal zijn. Het criterium wordt zodoende het minimax criterium genoemd. Voor een vaste instelling van de kosten Ci} varieert de drempel van de Bayestoets met P(H,). De loos-alarmkans PL en de miskans PM variëren mee met deze drempel. Dit is ook het geval met de gemiddelde kosten, die zodoende geïnterpreteerd kunnen worden als een functie van P(Hd , aangegeven met C(P(H,)). Wanneer we nu de minimale kosten C rnin (Bayeskosten) tekenen als functie van P(H,) dan krijgen we een kromme zoals in figuur 2.4 is weergegeven. Gewoonlijk heeft de kromme een

58

Statistische Signaalverwerking

30 ,--------~/

Cmin

/

25

~..,...---=-

20

10 C005~--------~~--------~

0,0 Figuur 2.4.

P1

Pt

RH1) 1,0

Voorbeeld Bayeskosten als functie van P(H 1).

maximum bij een waarde P~ van P(H I)' Opgemerkt wordt dat deze kromme het totale resultaat toont van een verandering in P(HI), PL en PM. Veronderstel nu dat we aannemen dat P(HI) een vaste waarde PI heeft en dat we de Bayestoets overeenkomstig deze waarde ontwerpen. De beslissingsgebieden zijn dan vastgelegd door de drempel van de toets. Dit geldt dan evenzo voor de foutkansen PL en PM. Wanneer de werkelijke waarde van P(H I ) een andere is, dan is de beslissingsregel niet langer optimaal en de bijbehorende gemiddelde kosten zijn niet langer de Bayeskosten. In feite, zoals uit (2.22) volgt, worden variaties in de gemiddelde kosten C als functie van P(HI) gerepresenteerd door een rechte lijn (merk op dat PL en P M een vaste waarde hebben en niet mee variëren met P(H I) omdat de beslissingsdrempel vast ligt). Deze rechte lijn is de raaklijn aan de C min-kromme op het punt PI omdat de toets optimaal is voor deze waarde van P(H I)' De werkelijke kosten kunnen dus erg groot worden afhankelijk van de werkelijke waarde van P(HI).

Wanneer we echter onze toets ontwerpen onder de aanname dat de a priori kans gelijk was aan P~, dan is de raaklijn aan de Cmin kromme horizontaal. Bedenk dat P~ een 'worst-case' situatie is, waarbij de Bayeskosten op dit punt maximaal zijn. We zijn er dan echter wel van verzekerd dat onafhankelijk van de werkelijke waarde van P(H]) de gemiddelde kosten niet groter zullen zijn dan c min(P7). In het gezochte punt p7 is de; partiële afgeleide van C(P(H I» naar P(H I) nul (vaste waarden van PL en PM!). Uitgaande van (2.22) levert dit (2.26) Vergelijking (2.26) wordt wel de minimax vergelijking genoemd. Omdat PM en PL afhankelijk zijn van de drempel 11 van de LRT, kan (2.26) gebruikt worden om de drempelwaarde van de toets te bepalen. Voor he: speciale geval dat Coo = Cl I = 0, en CIO = COl = I reduceert de minimax vergelijking tot

2. Detectietheorie

59

(2.27) waaruit eenvoudig de optimale drempel 11 kan worden afgeleid.

Voorbeeld 2.4. Toets op basis van minimax criterium We beschouwen hetzelfde probleem als in voorbeeld 2.3, waarbij echter nu de a priori kansen P(HJ} en P(Ho) niet bekend zijn. We maken gebruik van het minimax-kosten criterium. Voor de eenvoud kiezen we de kosten als Coo = Cl I = 0, en CIO = COl = 1. We maken nu gebruik van de gelijkheid (2.27) om de drempel te vinden. Eenvoudig valt aan te tonen dat voor dit voorbeeld geldt

_~

pL=jP(ZIHO)dz=j exp r r U'I27r

[_L] 202

dz

en

De optimale drempel levert

i

wordt verkregen wanneer PM

=PL volgens (2.27). Dit

2.3.5 Neyman-Pearson toets In veel gevallen zijn niet alleen de a priori kansen maar ook de kosten moeilijk te bepalen. Neem als voorbeeld een radardetectieprobleem waarbij de kosten verbonden aan een misser niet gemakkelijk te ramen zijn. Een eenvoudige procedure om deze problemen te omzeilen is alleen te werken met de kansen P L en PD. In het algemeen willen we de loos-alarmkans zo klein mogelijk maken en de detectiekans zo groot mogelijk. Dit zijn echter tegenstrijdige doelstellingen omdat loos-alarmkans en detectiekans via de detectiedrempel direct aan elkaar gekoppeld zijn. Het is daarom gebruikelijk een acceptabele waarde voor PL te bepalen (bijvoorbeeld maximaal 1 op de 1000 keer) en een beslissingsstrategie te zoeken die PL bindt aan deze waarde, terwijl tegelijkertijd PD wordt gemaximaliseerd. Dit laatste is identiek aan het minimaliseren van P M. Deze toets wordt een Neyman-Pearson toets genoemd. De beslissingsregel wordt verkregen door PM te minimaliseren onder de voorwaarde dat PL een vaste waarde heeft: minPM

met

We construeren daartoe de Lagrange functie:

60

Statistische Signaalverwerking

(2.28) waarin À ~ 0 een Lagrange vermenigvuldiger is. Wanneer we voor PL en PM de uitdrukkingen uit (2.18) en (2.19) substitueren, dan verkrijgen we

=f p(zlH\) dz + À [f p(zlHo) dz - a]

J(PM,)")

Zo

Z,

=Jp(zlHd dz + À [1- Jp(z/Ho) dz - a] Zo

Zo

f

=).(1 - a) + [P(Z/Hl) - À p(zlHo)] dz Zo

(2.29)

De Lagrange functie wordt geminimaliseerd door de integraal over Zo zo klein mogelijk te maken. Een dergelijk probleem kwamen we eerder tegen bij het Bayes Criterium (vergelijking (2.11)). Ook nu verkrijgen we als antwoord een likelihood ratio toets (LRT):

Hl

A(z) ~ À

(2.30)

Ho De drempel van de toets 11 is hier gelijk aan de Lagrange vermenigvuldiger À, en wordt zodanig gekozen dat wordt voldaan aan de voorwaarde PL = a. Dit levert

a

=PL =Jp(zlHo) dz

(2.31)

2,

Voorbeeld 2.5. Neyman-Pearson toets We ontwerpen een Neyman-Pearson toets voor het volgende binaire detectieprobleem, waarbij voor de kansdichtheid van de observatie z onder de nulhypothese geldt: e-z

p(z/Ho)

={ 0

z~o

elders

en onder de alternatieve hypothese -re--rz

p(z/Hd

={ 0

z~o

elders

We veronderstellen -r > 1. Deze a priori kansdichtheden zijn geschetst in figuur 2.5.

2. Detectietheorie

61

5,00 4,50 4,00 3,50

,, , "'P(Z IK,) ,, ,, ,

3,00 2,50 2,00

,,

,

-

1,50 p(z I liJ) 1,00 ] -_ _ _ _...:..:.::."--.'"="::-:--_ _ _ _ __ 0,50 ............... ...

--- -----

O,OO-r---.---.---.----.---,---.---,----,~=r~~--_.

0,00 Figuur 2.5.

0,10

0,20

0,30

0,40

0,50

0,60

0,70

0,80

0,90

1,00

z

A priori kansdichtheden voor voorbeeld 2.5.

De likelihood ratio wordt gegeven door

A(z) =p(z/H]) p(z/Ho)

=re-('r - l)z

zodat de beslissingsregel volgens Neyman-Pearson luidt:

A(z) = re-(T-I)z

Hl ~

À.

Ho met À. de Lagrange vermenigvuldiger. Uitwerken van de toets, zodat in het linkerlid slechts de observatie z staat, levert

Hl À.

e-(T- l)z

~ -

Ho r ~

Hl À. ~ lnr Ho

-(r-1)z

Ho

1 À. - - ln - = r Hl l - r r ~

z

De drempel rwordt nu zodanig gekozen dat wordt voldaan aan de voorwaarde PL = a. Dit levert: y

y

a=PL=f p(z/Ho)d z =f e-zdz= l-e- Y

o

0

Met andere woorden, de drempel r wordt gegeven door r = -In (1- a). Door substitutie van

62

Statistische Signaalverwerking

1 r=-1-'t'

À.

ln't'

vinden we voor de drempel À. de waarde À. = 't' (l - a)1"- l. De detectiekans kan nu worden bepaald:

r

f

r

PD = p(zlHt> dz

o

=f 't'e- 'lZ dz = 1 - e-1"Y 0

Het kan nu voorkomen dat de gekozen (kleine) waarde voor de loos-alarmkans aanleiding geeft tot een onacceptabele (kleine) waarde voor de detectiekans PD' Echter voor toenemende waarden van PL zal ook PD toenemen, zoals zal blijken uit de hierna te behandelen detectiekromme of 'receiver operating characteristic' (ROC). D We hebben gezien dat alle tot nog toe gebruikte criteria de berekening van een likelihood vereisen. Het is slechts de waarde van de drempel 1] waarmee deze verhouding wordt vergeleken die per criterium varieert. De kwaliteit van de verschillende toetsen kan het beste worden geanalyseerd aan de hand van een grafiek waarin de detectiekans PD wordt uitgezet tegen de loos-alarmkans PL voor variërende drempelwaarden. Een dergelijke kromme wordt detectiekromme of receiver operating characteristic (ROC) genoemd. Hij hangt slechts af van de kansdichtheden van de waarneming onder de twee hypothesen en niet van de kosten of a priori kansen. In tabel 2.2 zijn voor voorbeeld 2.5 voor variërende waarden rde bijbehorende PL en PD waarden bepaald voor vaste 't'= 16. Tabel 2.2.

Detectie- en loos-alarm kans bij variërende

r 0 0,05 0,10 0,20 0,30 00

a = PL = 1 - e- r 0,000 0,049 0,095 0,181 0,259 1,000

r voor voorbeeld 2.5 (-r =

16).

Po = 1 - e- 16r 0,000 0,551 0,798 0,959 0,992 1,000

Figuur 2.6 toont de bijbehorende ROe en laat tevens gelijksoortige curven zien voor variërende waarden van 't'. Naarmate de geschetste kromme verder af komen te liggen van de diagonaal neemt de kwaliteit van de detector toe, met andere woorden, voor toenemende waarden van 't' wordt de hiervoor ontworpen detector beter. Immers bij een gelijkblijvende waarde van de loos-alarmkans P L = a neemt de detectiekans PD toe. Voor de Neyman-Pearson toets in voorbeeld 2.5 (met 't'= 16) is een goede keus voor de loos-alarmkans een waarde tussen 0,1 en 0,2. Immers uit figuur 2.6 blijkt dat een grotere waarde van a (a> 0,2) slechts resulteert in een

2. Detectietheorie

63

Toenemende waarde van 1" (1"= 2, 4, 6,10,16)

0,5

P

OL-------L-------L-------~

° Figuur 2.6.

0,2

0,4

L ______~____~

0,6

0,8

ROC's voor voorbeeld 2.5.

kleine vermeerdering van PD, terwijl een waarde van vermindering resulteert van PD.

a < 0,1 in een aanzienlijke

Maximum likelihood criterium 2.3.6. Als de kans P(HI) en de kosten Cij niet bekend of betekenisvol zijn, en ook aan de loos-alarmkans geen zinvolle waarde kan worden gegeven, rest slechts het maximum likelihood (ML) criterium. In dit geval besluit men die hypothese te kiezen die met de grootste waarschijnlijkheid tot de observatie Z heeft geleid, met andere woorden: Hl p(z/HI) ~ p(z/Ho) Ho

(2.32)

Hieruit volgt onmiddellijk dat weer de LRT (2.16) gebruikt kan worden, nu echter met een vaste drempelwaarde TI

= 1. Merk op dat het verschil tussen het ML en het

MAP criterium de voorkennis over P(Hi ) is.

2.4.

Meervoudige waarnemingen

Het is vaak wenselijk de beslissing tot de nulhypothese Ho of de alternatieve hypothese Hl niet op één waarneming te baseren maar op meer waarnemingen . Stel we hebben N waarnemingen ZJ, Z2, . .. ZN die opeenvolgende metingen representeren aan dezelfde gebeurtenis of gelijktijdige metingen aan verschillende gebeurtenissen of combinaties van beide. De waarnemingen worden beschreven door de meerdimensionale conditionele kansdichtheden P(ZI ,Z2 , ... , zN/Ho) en p(zo, ZI, ... , zN/H I )· De beslissingsregels voor dit probleem kunnen eenvoudig worden afgeleid door de

64

Statistische Signaalverwerking

waarnemingen te beschouwen als een punt in een N-dimensionale ruimte dat wil zeggen de vector z:

De beslissingsregel verdeelt de waarnemingsruimte in twee gebieden. We beslissen tot Ho wanneer de waarnemingsvector z in Zo ligt en beslissen tot Hl wanneer zin ZI ligt. Het vlak dat beide gebieden scheidt wordt het beslissingsvlak genoemd. De ligging van dit beslissingsvlak wordt bepaald door het gebruikte criterium. Om het Bayes criterium te kunnen toepassen, moeten we weer de a priori kansen P(Ho) en P(HI) kennen en de kosten Cj}. Evenals in (2.9) worden de gemiddelde kosten gegeven door: C

=P(Ho) Coo f p(zlHo) dz + P(Ho) CIO f p(zlHo) dz + Zo

z)

f

f

P(Hd COl p(zlHI) dz + P(HJ} CII p(zlHJ} dz Zo z)

(2.33)

De integralen zijn hier N-voudige integralen dat wil zeggen dz = dZI dZ2 .. . dZN. Vervolgens kiezen we het beslissingsvlak zo dat de gemiddelde kosten C worden geminimaliseerd. Op dezelfde manier als voor het geval met één waarneming kan de beslissingsregel worden afgeleid: A( ) _p(zlH I ) _l!J!J, .. .,zNIHI) 1f,.1 z - p(zlHo) - P(ZI, ... ,ZN1Ho);jo 1]

(2.34)

Wanneer wel de kosten gespecificeerd zijn maar de a priori kansen op de twee hypothesen zijn onbekend, kunnen we weer het minimax criterium gebruiken. Als ook de kosten onbekend zijn, kan weer het Neyman-Pearson criterium worden gebruikt.

Voorbeeld 2.6. Detectie bij meervoudige waarnemingen We veronderstellen dat we N waarnemingen Zj, i = 1,2, ... , N hebben gedaan aan een ontvangen signaal zet). De waarnemingen zijn onder beide hypothesen onafhankelijke Gaussische stochastische variabelen. Onder Hl veronderstellen we dat de variabelen een gemiddelde m en een variantie a 2 hebben, terwijl hebben. We ontwerpen onder Ho ze een gemiddelde 0 en dezelfde variantie een beslissingsregel volgens het minimale foutkans criterium waarbij we veronderstellen dat P(Ho) =P(Hd. Voor willekeurige i kunnen we schrijven:

cr

p(z/HI)

1 =0'1210 _r;c

[ exp -

(z I·-m? - ' -J 20-

2. Detectietheorie

65

[Z·2] ~

1 v'l2rr

p(z/Ho) = _I'>: exp -

20-

Omdat de waarnemingen Zi onafhankelijk verondersteld zijn, geldt voor de gezamenlijke kansdichtheden: N

p(z/Hj ) = I1p(z/Hj ) ,

j = 0, 1

i=I

In termen van de vectoren (met m de kansdichtheden

p(z/H[)

=

~ Nn

exp [-

p(z/Ho)

=(2rr~Nn )

exp[-

(2rr

)

= [m, m, ... , m]l}kunnen we schrijven voor ~.

(z-m)t(z-m)]

~

ztz]

20-

20-

De likelihood ratio wordt zodoende

en de beslissingsregel: exp [ - 1 (mtz - -I mtm) ]

d2

2

Hl ~ 1]

Ho

Uitgaande van het minimale foutkanscriterium en P(Ho) = P(H I) is de drempel 1] gelijk aan één. Wanneer we aan beide zijden van de ongelijkheid de logaritme nemen, krijgen we de meer geschikte vorm

~. ~I L..JZt

i=I

Nm

< 2 Ho

wat herschreven kan worden als:

We zien dus dat deze minimale foutkansdetector het rekenkundig gemiddelde bepaalt van de waarnemingen en deze vergelijkt met de drempel ml2. 0

66

Statistische Signaalverwerking

2.5.

Sequentiële detectie

In de vorige paragrafen lag het totale aantal waarnemingen vast. In veel praktische situaties zijn echter de waarnemingen sequentieel van aard. Er komt meer informatie beschikbaar naarmate de tijd verloopt. In dergelijke gevallen is het wenselijk de waarnemingen sequentieel te behandelen. We vestigen onze aandacht hjer op een gemodificeerde Neyman-Pearson toets, ook wel sequentiële toets van Wald genoemd. Het voordeel van sequentiële toetsen is dat nu niet slechts óf de loosalarmkans óf de detectiekans vrij gekozen kan worden, maar dat voor beide een vrij te kiezen waarde genomen kan worden, mits er voldoende aantal waarnemingen gedaan kan worden. In een sequentiële toets wordt in elk stadium van de beslissingsprocedure de likelihood ratio vergeleken met twee drempels 1]0 en 1]1. Deze drempels zijn bepaald op basis van specifieke waarden van de foutkansen PL en P M . Wanneer de aannemelijkheidsverhouding groter of gelijk is aan 1]1 beslissen we ten gunste van Hl. Wanneer deze verhouding kleiner is dan 1]0 beslissen we tot Ho. Wanneer de waarde ligt tussen 1]0 en 1]1 concluderen we dat we niet voldoende informatie bezitten om te kunnen beslissen tussen de twee hypothesen met de voorgeschreven waarden voor PL en PM en nemen zodoende nog een waarneming. Eén en ander is geïllustreerd in figuur 2.7. Het sleutelprobleem in het ontwerpen van de toets is het bepalen van de drempels 1]1 en 1]0 voor gegeven PL en PM. We beperken ons hier tot het geval dat de waarnerrungen stochastisch onafhankelijk zijn. Stel dat ZI,

Z2, .•. , Zj, •••

de waarnemingen zijn en dat Zj de vector is gedefinieerd door

De aannemelijkheidsverhouding gebaseerd op j waarnemingen wordt dan gegeven

-N Figuur 2. 7.

Sequentiële detectie.

2. Detectietheorie

door

67

.

(2.35) Om A(Zj) te kunnen berekenen op elk discreet tijdstip j moeten we de gezamenlijke kansdichtheden kennen van de waarnemingen ZI, Z2, ... , Zj tot aan dat tijdstip. Wanneer deze waarnemingen onafhankelijk zijn, dan kan A(zj) op de volgende wijze recursief berekend worden:

(2.36) of: (2.37) met beginconditie

Veronderstel nu dat de foutkansen als volgt gekozen zijn: (2.38)

en

Merk op dat bij niet-sequentiële detectie de waarden van a en {J gekoppeld zijn via de waarde van de beslissingsdrempel van de LRT. We leiden nu een tweetal ongelijkheden af voor de drempels 110 en 11 1 in termen van a en (J. We roepen in herinnering dat de loos-alarmkans en de detectiekansen gegeven worden door: PL

=P(DI IHo) =f p(z/Ho)dzj

(2.39)

ZI

(2.40)

waarbij in (2.40) gebruik is gemaakt van (2.35), en waarin ZI het beslissingsgebied voorstelt voor hypothese Hl, Wanneer Hl de juiste hypothese is en de beslissing is Dl, dan moet gelden A(zj) ~ 111, zodat (2.40) herschreven kan worden als: PD

=P(D 1IH 1) ~ 111 f p(z/Ho)dzj = 111 a ZI

Omdat PD

=1 -

PM

= 1 - (J kan (2.41) geschreven worden als

zodat voor de drempel geldt

(2.41)

68

Statistische Signaalverwerking

111

1-{3

(2.42)

~-­

a

Op dezelfde manier kan voor de drempel 110 worden afgeleid:

110~L 1-

(2.43)

a

Verder kan aangetoond worden dat voor gegeven waarden van PL en PM de toets gemiddeld genomen eerder gereed is op basis van minder waarnemingen dan de toets met vaste lengte.

2.6.

Detectie van bekende signalen in witte ruis

Het detectieprobleem heeft tot zover in het teken gestaan van het detecteren van hypothesen die te maken hadden met eenvoudige signaalvormen (bijvoorbeeld twee verschillende gemiddelde waarden of varianties). Een uitbreiding van de detectietheorie naar een voor digitale communicatie belangrijk geval, is het detecteren van complexere maar wel bekende signaalvormen in de aanwezigheid van ruis. Deze theorie heeft als meest bekende resultaat het zogenaamd matched filter.

2.6.1.

Tijd-discrete geval We bekijken een eenvoudig binair communicatiesysteem waarin een zender één van de twee mogelijke signalen Yik (i = 0, 1) uitzendt waarvan de golfvormen volledig bekend zijn. Het signaal aan de ontvanger wordt waargenomen over een interval [to,~] en resulteert in N bemonsteringen. Aangenomen wordt dat het signaal verstoord is door additieve ruis Vk. Gevraagd wordt een ontvanger te ontwerpen die het ontvangen signaal Zk zodanig bewerkt dat op betrouwbare wijze één van de twee mogelijke hypothesen kan worden gekozen:

Ho:

Zk

=YOk +Vk

1 ~k~N

(2.44) l~k~N

We veronderstellen dat de bemonsteringen van de ruis onderling onafhankelijk zijn De waarneminen Gaussisch verdeeld met gemiddelde waarde nul en variantie gen onder de twee hypothesen zijn dan ook onafhankelijk en Gaussisch verdeeld met

cr.

E [zklHil

= Yik

var[zklHil = var[vJ =

(2.45)

cr

i =0, 1

2. De tee tie theorie

69

Wanneer we de vectoren Yo, Yl en z als volgt definiëren: Yo

=[YOl, Y02, ... , YON]t

Yl

= [YII, Y12, ... , YINJI

dan volgt dat de aannemelijkheidsverhouding wordt gegeven door:

(2.46) De beslissingsregel wordt Hl

A(z) ~

(2.47)

T/

Ho Na substitutie van (2.46) in (2.47), het nemen van de logaritme en het opnieuw rangschikken van de termen, krijgen we de volgende beslissingsregel: N

Hl

N

LZkYlk- LZkYOk ~ k=l

N

o2ln(T/) +f

Ho

k=l

LMk - Y50

(2.48)

k=l

In vectomotatie luidt de beslissingsregel

If.1

~.

I

t

I

zt(Yl-YO) < u-In(T/)+2(YlYl-YOYO)

(2.49)

Ho De meest belangrijke grootheid om deze regel te kunnen implementeren is zt(Yl - YO). De andere termen zijn niet afhankelijk van de waarnemingen z en kunnen vooraf berekend worden. Tijd-continue geval 2.6.2. We relateren nu de gevonden beslissingsregel voor het tijd-discrete geval aan het continue geval, waar we beslissen tussen de tijd-continue golfvormen YOCt) en Yl (t) op basis van een ontvangen tijd-continu signaal zet) waargenomen over een interval [to,tr], met

zet) = Yi(t) + vet)

We veronderstellen dat vet) Gaussische observatieruis is met een bandbegrensd vlak

70

Statistische Signaalverwerking

spectrum:

No

Ifl~W

(2.50)

Svv(}) ={ :

elders

De hieraan gerelateerde autocorrelatiefunctie is (2.51) Om nu het tijd-discrete geval te kunnen relateren aan het continue geval, veronderstellen we dat de tijd-discrete ruisbijdrage Vk in (2.44) tot stand is gekomen door bemonstering van z(t) op tijdstippen .. =kl2 W, k = 1, 2, 3 .. .. Met andere woorden, er wordt precies bemonsterd in de nuldoorgangen van de sinc-functie in (2.51), wat resulteert in onafhankelijke ruisbemonsteringen Vk. Het aantal bemonsteringen in het interval [to,~] is zodoende N 2W(tf- to), en de variantie van de ruisbemonsteringen is volgens (2.51)

=

a2 =Rv/..O) =No W We kunnen nu de beslissingsregel formuleren in termen van de continue signaalvormen door het aantal bemonsteringen te laten toenemen. In de limiet N ~ wordt vet) een wit proces. Uit (2.46) volgt dan 00

In A(z(t»

= lim

N~oo

In A(z)

~

~

~

=~o f z(t)Yl (t)dt - ~o f z(t)yo(t)dt + ~o f flo(t) - YT(t)]dt ~

~

(2.52)

~

De beslissingsregel kan nu worden geschreven als ~

~

JZ(t)Yl (t)dt - Jz(t)yo(t)dt

H

10

Ho

10

~l Y

(2.53)

met als drempel II

y= tNo ln( 17) +

t f fyy(t) - Y5(t)]dt

(2.54)

10

De structuur van de ontvanger is geschetst in figuur 2.8 . De ontvanger wordt een correlatieontvanger genoemd, omdat het ontvangen signaal zet) kruisgecorreleerd wordt met de signalen Yo(t) en Yl (t). Merk op dat wanneer de signalen gelijke energie hebben, de drempel signaalonafhankelijk is.

2. Detectietheorie

71

tf

f

ta

z(tl

vergelijk met drempel r tf

fta Figuur 2.8.

Correlatieontvanger voor binair beslissingsprobleem.

2.6.3. Matched filter implementatie van de ontvanger De implementatie van de beslissingsregel (2.53) vereist de berekening van de integralen tJ

ri

=f z(t)Yi(t)dt

(2.55)

to

wat een hardware vermenigvuldiger en een integrator vereist. We kunnen op de volgende manier een alternatieve implementatie verkrijgen van de correlatieontvanger. Veronderstel dat we zet) toevoeren aan een lineair tijd-invariant filter met impulsresponsie hi(t). Dan wordt het uitgangssignaal van het filter op tijdstip r gegeven door tJ

ri( r)

=f hl r -

(2.56)

t)z(t)dt

to

Iï 11

Door vergelijken van (2.56) met (2.55) zien we dat wanneer we h i( r - t) = Yi(t) stellen voor to ~ t ~ tJ (of hi(t) =Yi( r - t) voor r - tJ ~ t ~ r - to), dat het uitgangssignaal van het filter gelijk is aan de correlatie tussen de signalen zet) en Yi(t). Een dergelijke implementatie wordt een matchedfilter genoemd. Deze matched filter implementatie verdient in de praktijk vaak de voorkeur en is getoond in figuur 2.9. In (2.56) is de waarde van 'r in principe vrij te kiezen. Echter voor 'r - tJ < 0 is het filter (2.56) niet causaal (niet fysisch realiseerbaar), omdat het uitgangssignaal op tijdstip r afhangt van waarden van het uitgangssignaal in het interval [r,ttJ. Wanneer echter 'r gelijk gekozen wordt aan tris het filter causaal met impulsresponsie: voor 0 :s; t :s; tr - to

(2.57)

De impulsresponsies hi(t) van de causale matched filters worden dus gevonden door de signalen Yi(t), i = 0, I te spiegelen in t = en vervolgens te vertragen over de tijd

°

tr·

72

Statistische Signaalverwerking

z(t)

Figuur 2.9.

vergelijk met drempel r

Matched filter implementatie van de correlatieontvanger.

Voorbeeld 2.7. Matchedfilter Een matched filter implementatie wordt gezocht voor de volgende signalen (zie figuur 2.10): Zet) = Yo(t) { zet) =Yl (t)

We kiezen 7J = 1, waardoor de drempel rin (2.54) gelijk wordt aan O. De impuls responsies hj(t) van de causale matched filters worden bepaald volgens (2.57), en zijn getekend in figuur 2.11 (to = 0, fJ= 3). 4,00 3,00

4,00 3,00

Yo(t)

y,(t)

2,00

2,00 1,00

1,00

0,00 -1,00

0,00 -1,00 -2,00

-2,00 0,00

2,00

4,00

6,00

0,00

8,00

(a)

2,00

4,00

6,00

8,00

6,00

8,00

(b)

Figuur 2. 10. 4,00 3,00 2,00 1,00 0,00 -1,00

De signalen yo(t) en YI(t) waar tussen beslist moet worden. 4,00 3,00

holt)

h,(t)

2,00 1,00 0,00 -1,00

-2,00

-2,00 0,00

(a) Figuur 2. 11.

2,00

4,00

6,00

8,00

0,00

(b) Impuls responsies van de matched filters.

2,00

4,00

2. Detectietheorie

73

4,00

4,00 3,00

3,00

2,00

2,00

1,00

1,00 0,00 -I--k----j'---\----7I''------''----+-

0,00 +--k--+--*--r---..... -1,00 -2, 00

+--t--.-----.~__"T___,__,,_,__,--,

0,00

2,00

4,00

6,00

8,00

-1,00 -2, 00 -+---t--.-----.-+~__"T___,__,-r__l 0,00 2,00 4,00 6,00 8,00

4,00

4,00

3,00

3,00

2,00

2,00

1,00 0,00

-t-f--'Io;;~(__+~----+-

-1,00 -2,00

+-+-'1---'1-+,-"'-1""'-1"---1'1 1"-'1

-1,00

I 0,00

(a)

2,00

1,00 0,00

4,00

6,00

w

-2,00

8,00

1

0,00

1

2,00

w

1

1

4,00

1

1

6,00

1

1

1

8,00

(b)

Figuur 2. 12.

Uitgangssignalen van de matched filters voor (a) ingangssignaal Vort), en (b) ingangssignaal VI (t).

Het uitgangssignaal ri( 1'), i = 0, 1 van de matched filters wordt door convolutie verkregen en is geschetst in figuur 2.12. De waarde van toets (de correlatiewaarde) is nu te vinden voor l' = tj = 3. Voor het geval yo(t) het ingangssignaal is, geldt ro(ft) = 3 en rl (ft) = -1 (figuur 2.12a), terwijl wanneer Y 1(t) het ingangssignaal is geldt dat ro(tj) = -1 en r, (ft) = 3 (figuur 2.11 b). In beide gevallen is een juiste beslissing mogelijk door de correlatiewaarden onderling te vergelijken, wat hier niet verwonderlijk is omdat de signalen ruisvrij zijn. Een meer realistische situatie wordt in figuur 2.l3b getoond, namelijk het uitgangssignaal van de matched filters voor het geval het aangeboden signaal een sterk verruiste versie van y, (t) is (zie figuur 2.l3a). Ook nu is een juiste beslissing mogelijk.

2.7.

Samenvatting en belangrijke termen

De detectietheorie houdt zich bezig met het kiezen tussen twee of meer hypothesen op grond van waarnemingen. Deze hypothesen kunnen betrekking hebben op signaalgemiddelden, varianties, kansverdelingen en zelfs signaalvormen. Het probleem bij het maken van een beslissing is dat door verstoringen in de waarnemingen (ruis) de keuze tussen de nulhypothese en de alternatieve hypothese niet eenduidig is. Dit houdt in dat welk beslissingscriterium ook gebruikt wordt, er altijd fouten gemaakt zullen worden.

74

Statistische Signaalverwerking 4,00 z(t) 3,00 2,00 1,00 0,00 ~tEt---ltllH-+

-1,00 -2,00 +-+---.r--i----,----,--,---,-'--,---,-----, 0,00 2,00 4,00 6,00 8,00 (a)

3,00

4,00 3,00

2,00

2,00

4,00

rolt)

1,00 0,00 -+-+--'=--f--\----,.---1,00 -2,00 +--+----.-----.----,----,-----,----,-,--,.--, 0,00 2,00 4,00 6,00 8,00

r, (t)

1,00 0,00 -1,00 -2,00 0,00

2,00

4,00

6,00

8,00

(b)

Figuur 2. 13.

(a) Aangeboden verruiste signaal, (b) uitgangssignalen matched filters.

De likelihood ratio test (LRT) blijkt een toets te zijn die vanuit een aantal totaal verschillende overwegingen te motiveren valt. De toets luidt A( ) - p(z/HI) 1$1 z - p(z/Ho) < 1] Ho

De waarde 1] is de drempel, waarvan de waarde op grond van een zeker criterium gekozen wordt. Tabel 2.3. geeft een overzicht van een aantal bekende criteria en de daarbij behorende drempelwaarde. Tevens is hierbij de a priori kennis aangegeven die noodzakelijk is om de toets te kunnen gebruiken. Uiteraard zijn voor elke toets de kansdichtheden p(zlHj ) noodzakelijk om de likelihood ratio A(z) te kunnen bepalen. De fouten die gemaakt worden bij de detectietheorie zijn het 'loos-alarm' (beslis tot DI terwijl Ho juist is) en de 'misser' (beslis tot Do terwijl Hl juist is). De kansen op deze loos-alarm en misser spelen een grote rol in de detectietheorie. De ROe-curven (waarin uitgezet worden PL en PD = 1 - PM ) is een middel om de kwaliteit van een detector te bepalen. Andere veel gebruikte foutmaten zijn de gemiddelde foutkans en de gemiddelde kosten. De likelihood ratio toets kan ook worden uitgevoerd wanneer meer dan één waarneming beschikbaar is. Een alternatief hiervoor is de sequentiële detectie waarbij zoveel waarnemingen genomen worden als nodig zijn om tot een beslissing te komen. Het matched filter of correlatieontvanger is een efficiënte manier om de LRT voor de detectie van bekende signalen (in witte ruis) te implementeren. Dit kan voor zowel tijd-discrete als tijd-continue signalen.

2. Detectietheorie Tabel 2.3.

75

Overzicht beslissingscriteria voor de likelihood ratio toets.

criterium

doel

Bayes

kosten C

MAP

p(H,/z) ~ p(Ho/z)

P(H;)

AHa) AH,)

minimale foutkans

minimaliseer Pe

AH;)

AHa) AH,)

minimax

de Bayes kosten (minimale kosten) worden gemaximaliseerd

C'ï

los TI uit (2.26) op

Neyman-Pearson

maximaliseer Po bij vaste waarde van PL

-

los

maximum likelihood

p(z/H,) ~ p(z/Ho)

-

a priori kennis

drempel

P(H,), Cij

P(Ho)( ClO - Cool

minima~gemiddelde

Lijst van belangrijke termen aannemelijkheidsverhouding . alternatieve hypothese Bayes criterium beslissingscriterium beslissingsgebieden binair detectieprobleem detectiekans correlatieontvanger detectiecri teri urn detectieprobleem gemiddelde kosten ideale ontvanger likelihood ratio likelihood ratio test (LRT)

P(H,)(Co,- Cl')

À

uit (2.31) op 1

loos alarm matched filter maximum a posteriori (MAP) criterium maximum likelihood criterium minimale foutkans criterium rninimax criterium misser Neyman-Pearson toets nulhypothese receiver operating characteristic (ROC) sequentiële detectie sequentiële toets van Wald waarnemingsruimte

Vraagstu kken 2.1. Beschrijf het binaire detectieprobleem. Behandel hierbij de volgende essentiële elementen: Ho en H J hypothesen, kansmechanisme, partitionering van de waarnemingsruimte, beslissingsregel. 2.2. a. Aan welke voorwaarde(n) moeten p(z/Ho) en p(z/HI) voldoen zodanig dat de loos-alarm kans gelijk aan nul is in een binair detectieprobleem? Kunt u uitspraken doen over de detectiekans en de kans op een misser? b. Aan welke voorwaarde moeten p(Ho) en p(H I) voldoen zodanig dat de loos-

76

Statistische Signaalverwerking

alarmkans gelijk aan nul is realistische voorwaarden?

ID

een binair detectieprobleem? Zijn dit

2.3. Een detectiesysteem dient op basis van een ontvangen signaal y een beslissing te nemen over het al dan niet aanwezig zijn van een boodschap B. Het niet aanwezig zijn van de boodschap B wordt de nulhypothese Ho genoemd, terwijl de alternatieve hypothese H I het wel aanwezig zijn van B aanduidt. De kans van optreden van B is P(H() = pCB)

=t

Het ontvangen signaal y bezit de volgende, op B geconditioneerde, kans dichtheden:

=e-Y p(yl B) =0,5e-y/2 p(y/B)

o