Abstract
Jeg har i denne oppgaven studert metoder for å utføre divisjon og kvadratrot av binære tall. Fokus for oppgaven har vært multiplikative divisjons- og kvadratrotalgoritmer basert på numerisk tilnærming av resiprokalet og kvadratrotresiprokalet.
Første del av oppgaven besto av en litteraturstudie av de mest kjente multiplikative tilnærmingsalgoritmer for beregning av divisjon og kvadratrot. Ut fra litteraturstudiet ble to algoritmer, Newton-Raphson og Goldschmidt valgt ut for nærmere analyse. De matematiske prinsippene bak disse algoritmene ble så gjennomgått. Deretter fulgte en studie av forskjellige metoder for å finne initielle tilnærminger til resiprokalet og kvadratrotresiprokalet.
Andre del av oppgaven tok for seg implementeringen av de utvalgte algoritmene. Steg-for-steg algoritmer som viser hvordan metodene kan implementeres i samsvar med et fixed-point tallformat, ble presentert i detalj. Størrelsen til viktige enheter som multiplikatorer, adderere, registre, databusser og oppslagstabeller ble dokumentert.
Algoritmene ble deretter sammenlignet mot hverandre. Ut fra ytelse og maskinvarekostnad ble Goldschmidt-algoritmen valgt ut for implementering i en multifunksjonell beregningsenhet. Det ble også vist hvordan algoritmene kan benyttes til å utføre heltallsdivisjon.
Den tredje delen av oppgaven omhandlet implementeringen av beregningsenheten. Først ble ytelseskravene til beregningsenheten gjennomgått. Deretter fulgte en detaljert beskrivelse av hvordan beregningsenheten ble implementert og bygd opp. Enheten benytter Goldschmidt-algoritmen for beregning av divisjon og kvadratrot.
I tillegg kan beregningsenheten utføre operasjoner for multiplikasjon, multipliser-og-adder, addisjon, subtraksjon og restberegning. Beregningsenheten ble realisert ved hjelp av syntese og sammenlignet mot radiks-2 SRT-divisjonsenhet med hensyn på ytelse og maskinvarekostnad.
Den fjerde og siste delen av oppgaven dokumenterte jeg hvordan implementeringen av algoritmene og beregningsenheten ble utført.
Det ble også vist hvordan algoritmene og beregningsenheten ble testet og verifisert gjennom simuleringer.