Konstruksjon av digital heltallsaritmetikk: Kompakte initialverditabeller for multiplikative divisjons algoritmer

Abstract

Jeg har i denne oppgaven jobbet med digital heltallsaritmetikk, og da sett spesielt på feltet deling. Deling er en meget ressurskrevende opperasjon i digitalteknikk, det er derfor mye tid og areal å spare på å forbedre delingsopperasjonen. Jeg ser her på hvordan det er mulig å benytte multiplikative algoritmer til å utføre delingen, og da med hovedfokus på Newton- Raphson metoden. Newton-Rapson metoden er en gammel algoritme som har vært gjenstand for en mengde analyser rettet mot flere bruksområder, det finnes altså gode bevis på nøyaktighet, beregningsmengde og ressursbruk ved implementering i digitalekretser. Det er derfor ikke blitt utviklet noe nye algoritme basert på Newton-Raphson, men benyttet en godt dokumentert algoritme, da denne ser ut til å være den best egnede for implementasjon. Som andre iterative algoritmer trenger Newton-Raphson metoden et startpunkt for å kunne finne frem til det riktige svaret. Som vist i oppgaven har Newton-Raphson metoden den egenskapen at den fordobler antallet korrekte siffer per iterasjon og derfor er det viktig med et bra startpunkt hvis algoritmen skal komme fort fram til det antall korrekte bit som er ønsket i svaret. Problemet med å startverdier er hvis man skal ha stort antall korrekte bit trenger man mange verdier lagret og dette vil ta stor plass, eller man trenger en egen utregnings krets noe som ville ta ekstra tid. Oppgaven her viser først den simpleste formen for startverdi der algoritmen benytter samme startverdi til alle innverdier. Bare en innverdi vil gi lite areal kostnad men det vil føre til at man trenger flere iterasjoner for å finne det korrekte svaret og dermed vil det ta lenger tid. Oppgaven viser vider mer kompliserte oppslagstabeller og lineære interpolasjons metoder for å kunne øke antall korrekte bit i startverdien til minst mulig arealkostnad. Noen typer av oppslagstabellene er også blitt simuler for å vise at de faktisk gir tilstrekkelig korrekt svar. Til slutt i oppgaven er det hvis hvordan Newton-Raphson metoden og startverditabellene kan implementeres i FPGA.